Unit · year 4
MU-403 · Logic & Set Theory
Threads logic5 theorems
The foundations examined: choice, ordinals, and the limits of proof.
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.