Fall term 2026/27, course code NMAG331, Friday 10:40, room K334KA
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
Exercises (voluntary) from 2025/26
This lecture in fall term 2025/26
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
Lectures
#1 (2 Oct 2026)
- Syntax and semantics of propositional logic.
- Propositional proof system. Deduction lemma.
- Propositional soundness and completeness theorem.
#2 (9 Oct 2026)
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences. Substitution.
- Expansion with constants, satisfaction relation, entailment.
- First-order proof system. Deduction lemma.
#3 (16 Oct 2026)
- First-order soundness and completeness theorem.
#4–5 (23–30 Oct 2026)
Home reading: