The course of Theorems on Logic 2 part of the program in Philosophical Sciences (MA level) and it is included among the characterising training activities. Upon completion of the course students will have a good knowledge of recursion theory and will have understood the links between logic and arithmetic through the study of Godel’s incompleteness theorems.
teacher profile teaching materials
Part 2: Peano arithmetic. Peano's axioms and first order Peano’s axioms. The models of (first order) Peano arithmetic. The representable functions in (first order) Peano arithmetic. Incompleteness and undecidability: Church’s undecidability theorem, fixed point, Gödel’s first incompleteness theorem, Gödel’s second incompleteness theorem, final remarks on incompleteness, hints on incompleteness and second order logic.
Programme
Part 1: Decidability and fundamental results of recursion theory. Primitive recursive functions and elementary functions: definitions and examples, elementary coding of the finite sequences of natural numbers, an alternative definition of the set of elementary functions. Ackermann's function and the (partial) recursive functions. Arithmetical hierarchy and representation (in N) of recursive functions. Arithmetization of syntax: coding of terms and formulas, satisfiability in N of Delta formulas is elementary, coding of sequence and derivations. The fundamental theorems of recursion theory. Decidability, semi-decidability, undecidability.Part 2: Peano arithmetic. Peano's axioms and first order Peano’s axioms. The models of (first order) Peano arithmetic. The representable functions in (first order) Peano arithmetic. Incompleteness and undecidability: Church’s undecidability theorem, fixed point, Gödel’s first incompleteness theorem, Gödel’s second incompleteness theorem, final remarks on incompleteness, hints on incompleteness and second order logic.
Core Documentation
Testi: V. Michele Abrusci e Lorenzo Tortora de Falco, Logica. Vol. 2 Incompletezza, teoria assiomatica degli insiemi, Springer, 2018Attendance
Attendance is not mandatory but strongly recommended.Type of evaluation
Oral exam, of a duration usually between 45 and 60 minutes.