"Computability and Logic" (4th ed.), Cambridge
University Press, Cambridge 2002 (especially
chapters 1-8; 18, 23-25, 2 7
) . As historical reference essay: G. Lolli, Da Euclide a Goedel, Il Mulino,
Fixing the theoretical understanding of a nowadays fundamental
epistemological notion: effective computability; enhancing a proper
understanding of the Goedelian results and hence of metatheoretical
abilities in philosophy.
An introduction to formal logic (12 CFU), covering the basics of formal
deducibility and classical Tarskian semantics
Lectures and exercises proposed by the instructor.
Type of Assessment
Oral examination: it consists of a topic chosen by the candidate, and by handling two additional themes chosen by the instructor, within the full range of arguments dealt within the lectures.
Basic recursion theory: primitive recursive functions, partial recursive
functions and their closure properties. Recursively enumerable sets,
recursive sets; basic theorems. Formal provability (with respect to a
suitable subsystem of elementary number theory); formal representation
of functions and sets. Fixed point lemma. Proving Goedel's first
incompleteness theorem. Proving the unprovability of consistency and
the undefinability of truth as corollaries of Loeb's theorem. Link to modal
logics. Possible additional topics:nonstandard models; introduction to
second order logic.