Lectures in fall term 2024/25
All exercises in one file
#1 (1 Oct 2024)
- Propositional atoms, connectives, De Morgan language, formulas in infix and prefix notation, unique readability.
- Boolean assignments, tautologicity and entailment, satisfiability.
- Boolean functions, functional completeness of the De Morgan language.
- Conjunctive and disjunctive normal form.
Exercises
#2 (8 Oct 2024)
- Size of formulas, complexity of SAT.
- De Morgan laws, Boolean algebra laws.
- Propositional proof system. Deduction theorem.
- Propositional soundness and completeness theorem.
Exercises
#3 (15 Oct 2024)
- Propositional compactness theorem. De Bruijn–Erdős theorem.
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences, substitution.
- Expansion with constants, evaluation of terms.
Exercises
#4 (22 Oct 2024)
- Satisfaction relation, theories, models, entailment.
- Prenex normal form.
- First-order proof system. Deduction theorem.
- First-order soundness and completeness theorem.
Exercises
#5 (29 Oct 2024)
- Proof of the completeness theorem.
- Downwards Löwenheim–Skolem theorem.
#6 (12 Nov 2024)
- Compactness theorem, Löwenheim–Skolem theorem, Vaught’s test.
- The Entscheidungsproblem. Models of computation, the Church–Turing thesis.
Exercises
#7 (19 Nov 2024)
- Turing machines. Computable sets and functions.
- Variant definitions. Example.
#8 (26 Nov 2024)
- Representations of natural numbers.
- Encoding of Turing machines, universal Turing machine.
Exercises
#9 (3 Dec 2024)
- Undecidability of the Halting problem.
- Many-one reductions.
- Computability of elements of syntax. Recursively axiomatizable and decidable theories.
Exercises
#10 (10 Dec 2024)
- Peano and Robinson arithmetic.
- Bounded quantifiers, Δ0 and Σ1 formulas.
- Σ1-completeness of Q.
Exercises
#11 (17 Dec 2024)
- Δ0 functions.
- Pairing function, sequence encoding.
- Σ1-definability of semidecidable sets.
Exercises
#12 (7 Jan 2025)
- Gödel’s first incompleteness theorem (undecidability and incompleteness of Σ1-sound extensions of Q).
- Church’s theorem (undecidability of the Entscheidungsproblem).
- Gödel–Rosser theorem, interpretations, adjunctive set theory.
- Gödel’s diagonal lemma.
- Sketch of Gödel’s second incompleteness theorem:
- Arithmetization of syntax in PA.
- Hilbert–Bernays–Löb derivability conditions.
Exercises