Mathematical Logic

Fall term 2024/25, course code NMAG331, Tuesday 10:40, room K334KA

Consultations: after each lecture, or drop me an email to arrange a meeting

More resources on Jan Krajíček’s website

Syllabus

• Review of basic syntax and semantics of propositional and first-order logic. The completeness and compactness theorems.
• Computability: Turing machines, computable functions, universal TM, the halting problem.
• Formal arithmetic: Peano arithmetic, arithmetization of syntax, Gödel’s incompleteness theorems.

Exam questions

This lecture in fall term 2023/24, fall term 2022/23

Exercises (voluntary) from 2023/24

Lecture notes from 2023/24 (courtesy of J. Novák)

---

Recommended literature

• Lou van den Dries, Lecture notes on mathematical logic
• Vítězslav Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002
• Michael Sipser, Introduction to the theory of computation, 2nd ed., Thomson, 2006
• René Cori and Daniel Lascar, Mathematical logic: A course with exercises (Part I and Part II), Oxford University Press, 2000
• Joseph R. Shoenfield, Mathematical logic, Addison-Wesley, London, 1967

NB: These electronic materials are provided strictly for individual study purposes, not for further distribution. I hold no copyrights to any of these.

Further resources

• Turing machine simulator by Martin Ugarte

---

Lectures

#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, Δ₀ and Σ₁ formulas.
• Σ₁-completeness of Q.

Exercises

#11 (17 Dec 2024)

• Δ₀ functions.
• Pairing function, sequence encoding.
• Σ₁-definability of semidecidable sets.

Exercises