Unprovability 1000-1M18ND

The syllabus will consist of the following parts.

1. Unprovability in general: around Gödel's Theorems.

Peano Arithmetic PA as the canonical theory of finite objects. Connections between expressibility in arithmetic and computability. Diagonal sentences. Gödel's Theorems and related results (Tarski, Rosser). Unprovability of reflection principles.

2. Combinatorial statements that cannot be proved without referring to infinity.

Example of a combinatorial statement unprovable in PA: the Paris-Harrington Theorem. The unprovability of variants of Kruskal's Tree Theorem in theories of strength comparable to PA.

3. Strengths and limitations of compactness arguments.

Weak König's Lemma: an axiom formalizing compactness arguments in logic, topology, and analysis. Harrington's Theorem on the conservativity of Weak König's Lemma over the comprehension axiom for computable sets. Applications of forcing to axiomatic theories of arithmetic.

4. Necessary references to exponentially large objects.

Bounded arithmetic: a formalized version of the idea of arithmetic without exponentiation. Unprovability of the pigeonhole principle in bounded arithmetic. If we have time: provability of the existence of infinitely many primes in bounded arithmetic (the Paris-Wilkie-Woods Theorem).

5. Additional topics (depending on time).

- Matiyasevich's Theorem on the nonexistence of an algorithm solving the problem whether a Diophantine equation has a solution (Hilbert's 10th Problem). Corollary: no sufficiently strong theory proves all true statements on the nonexistence of solutions to Diophantine equations.
- Unprovability of variants of Kruskal's Theorem in non-predicative theories considerably stronger than PA.
- Possible dessert: Algebraic methods in the study of unprovability, or what axioms are needed to prove the irrationality of the square root of 2?