# Mathematical Logic

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

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

Exercises (voluntary) all in one file

The lecture in fall term 2022/23

## Recommended literature

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

## Lectures

### #1 (3 Oct 2023)

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.

Exercises

### #2 (10 Oct 2023)

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

Exercises

### #3 (17 Oct 2023)

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

Exercises

### #4 (24 Oct 2023)

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

Exercises

### #5 (31 Oct 2023)

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

### #6 (7 Nov 2023)

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

Exercises

### #7 (21 Nov 2023)

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

Exercises

### #8 (5 Dec 2023)

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

### #9 (12 Dec 2023)

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

### #10 (19 Dec 2023)

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

Exercises

### #11 (9 Jan 2024)

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

Exercises

Back to the main site