Mathematical Logic (NMAG331)

Lectures in fall term 2022/23

All exercises in one file

#1 (5 Oct 2022)

Review of propositional logic:

• Propositional atoms, connectives, De Morgan language, prefix and infix formulas, inductive definition, unique readability.
• Boolean assignments, tautologicity and entailment, satisfiability.
• Boolean functions, functional completeness of De Morgan language.

#2 (12 Oct 2022)

Review of propositional logic:

• 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 (19 Oct 2022)

Review of propositional and first-order logic:

• Propositional completeness and compactness theorems. De Bruijn–Erdős theorem.
• First-order languages, structures, terms, formulas.
• Free and bound variable occurrences, substitution.

Exercises

#4 (26 Oct 2022)

Review of first-order logic:

• Simultaneous substitution. Satisfaction relation, theories, models, entailment.
• Examples of theories. Prenex normal form.

Exercises

#5 (2 Nov 2022)

• Freeness for substitution.
• First-order proof system. Soundness, deduction theorem.
• Completeness theorem.

#6 (16 Nov 2022)

• Proof of the completeness theorem.

Exercises

#7 (23 Nov 2022)

• Compactness theorem, Löwenheim–Skolem theorem, Vaught’s test.
• The Entscheindungsproblem. Models of computation, Church–Turing thesis.
• Turing machines.

#8 (30 Nov 2022)

• Turing machines, variants, examples. Computable sets and functions.
• Encoding of Turing machines.

#9 (7 Dec 2022)

• Universal Turing machines. Halting problem. Many-one reducibility.
• Computability of logical syntax.
• Recursively axiomatizable, decidable, and complete theories.

#10 (14 Dec 2022)

• Peano and Robinson arithmetic.
• Bounded quantifiers, Δ₀ and Σ₁ formulas.
• Σ₁-completeness of Q.
• A pairing function.

Exercises

#11 (21 Dec 2022)

• Chinese remainder theorem, sequence encoding, Gödel numbering of finite strings.
• Σ₁-definability of semidecidable sets.
• Undecidability of Σ₁-sound extensions of Q.
• Representability of decidable sets in Q.

Exercises

#12 (4 Jan 2023)

• Gödel’s first incompleteness theorem (undecidability and incompleteness of extensions of Q).
• Undecidability of the Entscheidungsproblem. The adjunctive set theory.
• Sketch of Gödel’s second incompleteness theorem:
  • Arithmetization of syntax in PA.
  • Gödel’s diagonal lemma.
  • Hilbert–Bernays–Löb derivability conditions.

Exercises