Unit · year 4
MU-403 · Logic & Set Theory
Threads logic26 lectures5 theorems
The foundations examined: choice, ordinals, and the limits of proof.
PREREQUISITES
Lectures
| L01 | Formal Languages and Syntax — |
| L02 | Propositional Logic: Semantics — |
| L03 | Completeness for Propositional Logic — |
| L04 | First-Order Languages — |
| L05 | Structures and Satisfaction — |
| L06 | Theories, Models, and Logical Consequence — |
| L07 | Deductive Systems and Formal Proofs |
| L08 | Soundness |
| L09 | Gödel's Completeness Theorem |
| L10 | The Compactness Theorem |
| L11 | Applications of Compactness |
| L12 | Non-Standard Models of Arithmetic |
| L13 | The Löwenheim–Skolem Theorems |
| L14 | Skolem's Paradox |
| L15 | Zermelo–Fraenkel Set Theory — |
| L16 | Ordinals and Transfinite Induction — |
| L17 | Cardinals and Cardinal Arithmetic — |
| L18 | The Axiom of Choice |
| L19 | Zorn's Lemma |
| L20 | Equivalents of Choice |
| L21 | Recursion Theory: Computable Functions — |
| L22 | The Halting Problem |
| L23 | Representability and Arithmetisation |
| L24 | Gödel's First Incompleteness Theorem |
| L25 | The Second Incompleteness Theorem |
| L26 | Synthesis: The Reach and the Limits of Formal Method |
Theorems in this unit
T-126
Zorn's lemma
Every chain-bounded poset has a maximal element — equivalent to choice.
T-127
The compactness theorem
A theory is satisfiable iff every finite subset is.
T-128
The Löwenheim–Skolem theorem
First-order theories with infinite models have models of every infinite size.
T-129
Gödel's completeness theorem
Every logically valid first-order formula is provable.
T-130
Gödel's incompleteness theorems
Sufficiently strong consistent systems cannot prove their own consistency.