![]() |
Logic & Set Theory |
Time. Friday, Monday, Wednesday
11–12.
Location. MR2.
Example Sheets. Example sheets for the course will be available at
http://www.dpmms.cam.ac.uk/study.
Example
Sheet #1
Example
Sheet #2
Example
Sheet #3
Example
Sheet #4
Lecture Notes. Typed lecture notes are available here: pdf file (last updated: 31 March 2026).
| Week 1. | Lecture I. Friday, 23 January 2026. Overview of the relationship between logic, philosophy, and mathematics. Leibniz's calculemus and the idea that reasoning is calculation. Boole. Boolean algebras. Formulas. Lecture Notes | Lecture II. Monday, 26 January 2026. Remarks on formulas: formulas are strings, induction and recursion, parentheses are annoying. Meaning of formulas. Structures and homomorphisms. Valuations. Validity. Equivalence. Truth tables and calculation of validity. Lecture Notes | Lecture III. Wednesday, 28 January 2026. Truth tables and calculation of equivalence. The meaning of a formula. Defining \(+,\cdot,-,1\) in terms of \(\to,0\). Reducts. Equational definability. Implication algebras. Implicative formulas. Every formula is equivalent to an implicative formula. Proofs: axioms of type 1, 2, 3, and 4. Lecture Notes |
|---|---|---|---|
| Week 2. | Lecture IV. Friday, 30 January 2026. Modus ponens. Proofs. Properties of proofs. The Lemma on lemmas. Examples. The Soundness Theorem. The Deduction Theorem (start of proof). Lecture Notes | Lecture V. Monday, 2 February 2026. The Deduction Theorem (end of proof). Consistency: basic properties. Negation completeness. Lindenbaum's Lemma. The model existence theorem. The compactness theorem. Lecture Notes | Lecture VI. Wednesday, 4 February 2026. Proof of the completeness theorem from the model existence theorem. Predicate Logic: non-logical symbols, quantifiers, terms, formulas. Free variables. Sentences. Lecture Notes |
| Week 3. | Lecture VII. Friday, 6 February 2026. Assignments. Recursive definition of \(\mathbf{X},\mathfrak{I}\models\varphi\). Coincidence Lemma. Isomorphism Lemma. Quantifier-free formulas. Substructure Lemma. Definability over a structure \(\mathbf{X}\). Lecture Notes | Lecture VIII. Monday, 9 February 2026. Most sets are not definable. Examples of non-definable sets over the integers and the complex numbers. Gödel's Completeness Theorem (no proof). Compactness Theorem. Application. Axiomatisability. Axiomatisable: the class of infinite structures. Not axiomatisable: the class of finite structures; the class of structures isomorphic to the natural numbers. Lecture Notes | Lecture IX. Wednesday, 11 February 2026. Set theory: the birth of set theory (1874). Set theory as a foundation of mathematics. Hilbert's programme. Gödel's incompleteness theorem (no precise statement). The language of set theory, \(\in\)-structures, visualisation as directed graphs. Extensionality. The axiom schema of comprehension. Russell's paradox. The axioms of \(\mathsf{FST}\): empty set, pairing, union, powerset, separation. Notation for set operations in \(\mathsf{FST}\). Lecture Notes |
| Week 4. | Lecture X. Friday, 13 February 2026. Models of \(\mathsf{FST}\) are infinite. Reconstruction of abstract mathematics: binary unions, intersections, ordered pairs, Cartesian products, relations, functions, orders, equivalence relations, quotients. Additional axioms: Infinity, Replacement, Choice. Lecture Notes | Lecture XI. Monday, 16 February 2026. Addition axiom: Foundation. Wellfoundedness. The smallest inductive set \(\mathbb{N}\). Properties. Transitivity. The ordering of natural numbers by \(\in\). Algebraic constructions to add additive and multiplicative inverses: definition of \(\mathbb{Z}\) and \(\mathbb{Q}\). Lecture Notes | Lecture XII. Wednesday, 18 February 2026. Natural numbers and their syntactic representation. Definition of \(\mathbb{R}\) and \(\mathbb{C}\). Induction: complete induction and order induction. Order induction and wellfoundedness. Examples of wellfounded sets that do not satisfy complete induction. Recursion. Statement of the recursion theorem. Proof of Claim 1 and uniqueness. Lecture Notes |
| Week 5. | Lecture XIII. Friday, 20 February 2026. Recursion theorem: Proof of Claims 2 & 3. Discussion of the use of the replacement axiom. Examples: an inductive set not equal to \(\mathbb{N}\); the transitive closure of a set. Wellorders: examples and non-examples. Initial segments and proper initial segments. Characterisation of proper initial segments in wellorders. Sums of wellorders. Lecture Notes | Lecture XIV. Monday, 23 February 2026. Finiteness, infinity, countability, uncountability. Products of wellorders. Countable wellorders as subsets of \(\mathbb{N}\times\mathbb{N}\). Uniqueness of isomorphisms. Ordering of wellorders by being isomorphic to a proper initial segment. Fundamental Theorem on Wellorders. Ordinals. Examples. Proper initial segments in ordinals. Lecture Notes | Lecture XV. Wednesday, 25 February 2026. Successor and limit ordinals. Elements of ordinals are ordinals. Ordinals are unique up to isomorphism. Transitive sets of ordinals are ordinals. Burali-Forti Paradox. Representation Theorem for wellorders. Mostowski collapse. Existence of uncountable ordinals. Hartogs's Theorem. Lecture Notes |
| Week 6. | Lecture XVI. Friday 27 February 2026. Hartogs aleph. Transfinite induction & recursion. Ordinal arithmetic: addition, multiplication, and exponentiation. Properties. Ordinal addition and multiplication and the sum and product operations on wellorders. Ordinal subtraction. Zermelo's Wellordering Principle. Lecture Notes | Lecture XVII. Monday, 2 March 2026. \(\mathsf{ZWOP}\) implies \(\mathsf{AC}\). Wellorderability and functions between sets and ordinals. Zermelo's Theorem. Chain-complete partial orders. Zorn's Lemma. \(\mathsf{ZL}\) implies \(\mathsf{AC}\). List of theorems that use the axiom of choice. Lecture Notes | Lecture XVIII. Wednesday, 4 March 2026. Sizes of infinite sets. Cantor-Schröder-Bernstein Theorem (no proof; cf. Example Sheet #4). Cantor's Theorem. Cardinality of a set. Initial ordinals or cardinals. The aleph hierarchy and alephs. All cardinals are alephs. Successor and limit cardinals. Notation \(\omega_\alpha\). Cardinal addition and multiplication. Hessenberg's Theorem (no proof). Lecture Notes |
| Week 7. | Lecture XIX. Friday, 6 March 2026. Proof of Hessenberg's theorem. Cardinal exponentiation. The continuum function. The beth hierarchy. The continuum problem. Hilbert's problems. Solution of the continuum problem (without proofs): Gödel 1938, Cohen 1962. Easton's theorem (without proof). Silver's theorem (without proof). Lecture Notes | Lecture XX. Monday, 9 March 2026. Infinite descending sequences and the axiom of foundation. \(\in\)-induction. The von Neumann hierarchy. Mirimanoff rank. Foundation implies that every set is von Neumann. Pictures of the von Neumann universe and characterisation of sets as bounded classes. Hereditarily finite sets and their Mirimanoff rank. Axioms in \(\mathbf{HF}\). Lecture Notes | Lecture XXI. Wednesday, 11 March 2026. Classes, sets, and coextensionality. Axioms in \(\mathbf{HF}\): rank arguments and non-absoluteness. Pairing, separation, and replacement. Failure of replacement in \(\mathbf{V}_{\omega+\omega}\). Recap and overview of the second part of Predicate Logic. Lecture Notes |
| Week 8. | Lecture XXI. Friday, 13 March 2026. Clarification on classes and boundedness in the von Neumann hierarchy. Substitution. The substitution lemma. Implicative formulae in predicate logic. Desirable properties of \(\vdash\) (1)–(11). Completeness Theorem. Model Existence Theorem. Proof of the Completeness Theorem from the Model Existence Theorem. The term structure and term interpretation. Lecture Notes | Lecture XXIII. Monday, 16 March 2026. In general, the term structure is not a model of the theory: issues with negation completeness and lack of witnesses for existential quantifiers. Lindenbaum's Lemma for arbitrary languages. Having witnesses. Henkin's Lemma. Henkinisation: definition of \(T_\infty\). Lecture Notes | Lecture XXIV. Wednesday, 18 March 2026. Proof that the Henkinisation is consistent, negation complete and has witnesses. Non-examinable: Definition of proofs, proof of properties of the \(\vdash\) relation, proof of the consistency of adding Henkin constants. Upward and downward Löwenheim-Skolem Theorems. Skolem Paradox. Categoricity and \(\kappa\)-categoricity. Examples of \(\aleph_0\)-categorical theories and of \(\aleph_1\)- but not \(\aleph_0\)-categorical theories. Łoś-Vaught-Test. Morley's Theorem (without proof). Lecture Notes |