C1.2 Gödel's Incompleteness Theorems (2024-25)
Main content blocks
- Lecturer: Profile: Robin Knight
Course information
General prerequisites:
This course presupposes knowledge of first-order predicate logic up to and including soundness and completeness theorems for a formal system of first-order predicate logic (B1.1 Logic).
Course term: Hilary
Course lecture information: 16 lectures.
Course weight: 1
Course level: M
Assessment type: Written Examination
Course overview:
The starting point is Gödel's mathematical sharpening of Hilbert's insight that manipulating symbols and expressions of a formal language has the same formal character as arithmetical operations on natural numbers. This allows the construction for any consistent formal system containing basic arithmetic of a `diagonal' sentence in the language of that system which is true but not provable in the system. By further study we are able to establish the intrinsic meaning of such a sentence. These techniques lead to a mathematical theory of formal provability which generalizes the earlier results. We end with results that further sharpen understanding of formal provability.
Learning outcomes:
Understanding of arithmetization of formal syntax and its use to establish incompleteness of formal systems; the meaning of undecidable diagonal sentences; a mathematical theory of formal provability; precise limits to formal provability and ways of knowing that an unprovable sentence is true.
Course synopsis:
Gödel numbering of a formal language; the diagonal lemma. Expressibility in a formal language. The arithmetical undefinability of truth in arithmetic. Formal systems of arithmetic; arithmetical proof predicates. \(\Sigma_0\)-completeness and \(\Sigma_1\)-completeness. The arithmetical hierarchy. \(\omega\)-consistency and 1-consistency; the first Gödel incompleteness theorem. Separability; the Rosser incompleteness theorem. Adequacy conditions for a provability predicate. The second Gödel incompleteness theorem; Löb's theorem. Provable \(\Sigma_1\)-completeness. The \(\omega\)-rule. The system GL for provability logic. The fixed point theorem for GL. The Bernays arithmetized completeness theorem; undecidable \(\Delta_{2}\)-sentences of arithmetic.
Section outline
-
-
Opened: Tuesday, 11 February 2025, 9:22 AMDue: Wednesday, 12 February 2025, 9:00 AM
-
-
Registration start: Monday, 13 January 2025, 12:00 PMRegistration end: Friday, 14 February 2025, 12:00 PM
-
Class Tutor's Comments Assignment
Class tutors will use this activity to provide overall feedback to students at the end of the course.
-