Fall term 2023/24, course code NMAG331, Tuesday 14:00, room K5

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

More resources on Jan Krajíček’s website

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

Exercises (voluntary) all in one file

The lecture in fall term 2022/23

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

- Turing machine simulator by Martin Ugarte

Review of propositional logic:

- 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, size of formulas, complexity of SAT.
- De Morgan laws, Boolean algebra laws.
- Propositional proof system, deduction theorem, completeness theorem.

- Proof of the propositional completeness theorem. Compactness theorem.
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences.

- Substitution.
- Satisfaction relation, theories, models, entailment.
- Prenex normal form.
- First-order proof system.

- First-order deduction theorem.
- Soundness and completeness theorem.

- Finish the proof of the completeness theorem.
- Downward Löwenheim–Skolem theorem.

- Compactness theorem.
- Löwenheim–Skolem theorem, Vaught’s test.
- Examples.

- Models of computation, the Church–Turing thesis.
- Turing machines. Computable sets and functions.
- Variants, example.

- Universal Turing machine, encoding of Turing machines.
- Undecidability of the Halting problem.
- Many-one reducibility.

- Peano and Robinson arithmetic.
- Bounded quantifiers, Δ
_{0}and Σ_{1}formulas, Σ_{1}-completeness of Q. - Pairing function, sequence encoding.

- Sequence encoding, Σ
_{1}-definability of semidecidable sets. - Computability of elements of syntax.
- Gödel’s first incompleteness theorem (undecidability and incompleteness of Σ
_{1}-sound extensions of Q.) - Church’s theorem (undecidability of the Entscheidungsproblem), adjunctive set theory.

Back to the main site