Mathematical Logic

Fall term 2025/26, course code NMAG331, Friday 14:00, room K8

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

Syllabus

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

Lecture notes

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

More resources on Jan Krajíček’s website

Exam questions

You will get a question chosen randomly from the following list:

• Syntax and semantics of first-order logic. The completeness and compactness theorems.
• Turing machines, decidable and semidecidable sets. Universal Turing machine, the halting problem and its undecidability.
• Robinson and Peano arithmetic and its incompleteness (Gödel’s first incompleteness theorem). Undecidability of first-order logic (Hilbert’s Entscheidungsproblem).

---

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 (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)

Plan:

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