Mathematical Logic (NMAG331)

Lectures in fall term 2025/26

All exercises in one file

This lecture now, in fall term 2024/25, fall term 2023/24, fall term 2022/23

#1 (3 Oct 2025)

• 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.

Exercises

#2 (10 Oct 2025)

• Conjunctive and disjunctive normal form. Size of formulas, complexity of SAT.
• Boolean algebra laws, De Morgan laws.
• Propositional proof system. Deduction theorem.
• Propositional soundness and completeness theorem.

Exercises

#3 (17 Oct 2025)

• Proof of the propositional completeness theorem.
• Propositional compactness theorem. De Bruijn–Erdős theorem.
• First-order languages, structures, terms, formulas.
• Free and bound variable occurrences.

Exercises

#4 (24 Oct 2025)

• Substitution. Expansion with constants, evaluation of terms.
• Satisfaction relation, theories, models, entailment.
• Prenex normal form.
• First-order proof system.
• Propositional reasoning.

Exercises

#5 (31 Oct 2025)

• First-order deduction theorem.
• First-order soundness and completeness theorem.

Exercises

#6 (7 Nov 2025)

• Finish the proof of the completeness theorem.
• Compactness theorem, Löwenheim–Skolem theorem.

#7 (14 Nov 2025)

• Categoricity, Vaught’s test, Morley’s theorem, examples.
• The Entscheidungsproblem. Models of computation, the Church–Turing thesis.
• Turing machines. Configurations.

Exercises

#8 (21 Nov 2025)

• Computable sets and functions.
• Variant definitions. Example.
• Representations of natural numbers.

Exercises

#9 (28 Nov 2025)

• Encoding of Turing machines, universal Turing machine.
• Undecidability of the Halting problem.
• Many-one reductions.
• Computability of elements of syntax.

Exercises

#10 (5 Dec 2025)

• Recursively axiomatizable and decidable theories.
• Hilbert’s program.
• Peano and Robinson arithmetic.
• Bounded quantifiers, Δ₀ and Σ₁ formulas, numerals.

Exercises

#11 (12 Dec 2025)

• Σ₁-completeness of Q.
• Δ₀ functions.
• Pairing function, sequence encoding.

Exercises

#12 (19 Dec 2025)

• Σ₁-definability of semidecidable sets.
• Gödel’s first incompleteness theorem (undecidability and incompleteness of Σ₁-sound extensions of Q).
• Church’s theorem (undecidability of the Entscheidungsproblem).
• Gödel–Rosser theorem, interpretations, adjunctive set theory.

Exercises

#13 (9 Jan 2026)

Sketch of Gödel’s second incompleteness theorem:

• Arithmetization of syntax in PA.
• Gödel’s diagonal lemma.
• Hilbert–Bernays–Löb derivability conditions.

Exercises