MU-403 Logic & Set Theory

Unit · year 4

MU-403 · Logic & Set Theory

Threads logic26 lectures5 theorems

The foundations examined: choice, ordinals, and the limits of proof.

PREREQUISITES

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 Gödel's completeness theorem
L08	Soundness Gödel's completeness theorem
L09	Gödel's Completeness Theorem Gödel's completeness theorem
L10	The Compactness Theorem The compactness theorem
L11	Applications of Compactness The compactness theorem
L12	Non-Standard Models of Arithmetic The compactness theorem
L13	The Löwenheim–Skolem Theorems The Löwenheim–Skolem theorem
L14	Skolem's Paradox The Löwenheim–Skolem theorem
L15	Zermelo–Fraenkel Set Theory —
L16	Ordinals and Transfinite Induction —
L17	Cardinals and Cardinal Arithmetic —
L18	The Axiom of Choice Zorn's lemma
L19	Zorn's Lemma Zorn's lemma
L20	Equivalents of Choice Zorn's lemma
L21	Recursion Theory: Computable Functions —
L22	The Halting Problem Gödel's incompleteness theorems
L23	Representability and Arithmetisation Gödel's incompleteness theorems
L24	Gödel's First Incompleteness Theorem Gödel's incompleteness theorems
L25	The Second Incompleteness Theorem Gödel's incompleteness theorems
L26	Synthesis: The Reach and the Limits of Formal Method Gödel's completeness theorem, Gödel's incompleteness theorems

Every chain-bounded poset has a maximal element — equivalent to choice.

A theory is satisfiable iff every finite subset is.

First-order theories with infinite models have models of every infinite size.

Every logically valid first-order formula is provable.

Sufficiently strong consistent systems cannot prove their own consistency.