To support the students into an in-depth analysis of the main results of first order classical logic and to study some of their remarkable consequences.
teacher profile teaching materials
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.
Fruizione: 20710122 TEOREMI SULLA LOGICA, 2 in Scienze filosofiche LM-78 TORTORA DE FALCO LORENZO
Programme
Logic and Arithmetic: incompletenessPart 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
V.M. Abrusci, L. Tortora de Falco, Logica Volume 2- Incompletezza, teoria assiomatica degli insiemi. Springer, (2018).Type of delivery of the course
The course includes Face-to-face lectures; Discussions with students and debates on the discussed topics; Exercices; Attendance is not mandatory but strongly recommended.Type of evaluation
Oral exam, of a duration usually between 45 and 60 minutes.