Ämnesdisposition

  • Logic II MM7022, HT2023

    Fäll ihop allt Expandera allt

    Logic II is a second course in logic, on the advanced level. It gives an introduction to major topics of modern mathematical logic, including axiomatic set theory, model theory, computability theory (including Gödel's incompleteness theorems), model theory, and nonstandard analysis.

    In more detail, the course will cover:

    • Axiomatic foundations: Zermelo–Fraenkel set theory; the development of mathematics therein; elementary theory of ordinals, cardinals, and transfinite recursion; the axiom of choice and its applications; and first independence results.
    • Model theory: structures, embeddings, isomorphisms; elementary equivalence and embeddings; the Löwenheim–Skolem theorems; categoricity and back-and-forth arguments; and applications/examples, including non-standard analysis.
    • Computability and incompleteness: models of computation; classes of computable functions; (un)decidability; Gödel’s encoding of logic, and Gödel’s incompleteness theorems.

    Teaching

    Lecturer

    Peter LeFanu Lumsdaine, <p.l.lumsdaine@math.su.se>; please include "MM7022" in the subject line of all course-related emails.

    Course literature

    • Main course text: René Cori, Daniel Lascar, 2001 — Mathematical logic, a course with exercises, Part II: Recursion Theory, Gödel’s Theorems, Set Theory, Model Theory (Oxford University Press; ISBN 0198500505) — SU library details. Also available in French.
    • For background, see Part I of the same series: René Cori, Daniel Lascar , 2000— Mathematical logic, a course with exercises, Part II: Propositional Calculus, Boolean Algebras, Predicate Calculus, Completeness Theorems, Oxford University Press, 2000 (ISBN: 0198500483). Also available in French.
    • For alternative reading on set theory, and especially for extra exercises, I recommend Ioannis Moschovakis, 2006, Notes on Set Theory (Springer; ISBN 9780387287232), available as e-book in SU library.
    • Another very readable treatment, highly recommended for set theory and model theory: Moerdijk, van Oosten, 2018, Sets, Models, Proofs (Springer, ISBN 978-3-319-92413-7, https://doi.org/10.1007/978-3-319-92414-4), not yet available in SU library but hopefully soon.

    Schedule

    • Classes are each Tuesday 13:00–15:00 (lecture) and 15:00–16:00 (problem session), from 29 Aug Sep (week 35) to 5 Dec (week 49).
    • Classes will be on the Albano campus, with the precise classroom varying from week to week — see full schedule below.
    • Exam: Friday 15 December; time and location TBA.
    • Full schedule on TimeEdit

    Examination

    Examiner

    Peter LeFanu Lumsdaine

    Examination

    Written exam at the end of the course. Non-obligatory homework problems (four sets) give bonus points. See grading criteria below.

    Homework problems and deadlines for their solution will appear below.

    Examination Rules at the Department of Mathematics.

    Old exams are available under Resources below.


    Resources

  • Topics overview

    Check back for regular updates.

    • Lecture 1, 29/9.  Brief review of prerequisites: language, structure, theory, mode, soundness, completeness (C–L Vol. 1).  Historical context and goals of axiomatic foundations.  Axioms of ZF(C) set theory, informally and formally. (C-L §7.1)
    • Lecture 2, 5/9.  Encoding fundamental mathematical notions in ZF: ordered pairs, functions, products. (C-L §7.1)  Axiom of infinity, \mathbb{N}.   The reals.  (C–L §7.2–3)
    • Lecture 3, 12/9:  Fundamentals of cardinality; (un)countability; Cantor’s diagonal argument.  Cantor–Schröder–Bernstein theorem; the continuum hypothesis.  (C–L §7.2–3)  Recommended exercises: Moschovakis Ch.2, x2.1–x2.10.
    • Lecture 4, 19/9: Well-orderings; ordinals; transfinite induction. Recommended exercises: Moschovakis Ch.7, x7.1, x7.5, x7.10, x7.12, x7.15.  (Notation: Moschovakis writes [0,n) for the well-ordering usually just called n.)
    • Lecture 5, 26/9: Hartogs’ lemma; more on cardinality.  The axiom of choice; the well-ordering principle; consequences for cardinal arithmetic.  Alternative forms of finiteness and well-foundedness under AC. (C–L §7.2–3).   Recommended exercises: C–L Ch. 7 Exs 2, 6, 7, 8.
    • (lecture 3/10 cancelled due to illness)
    • Lecture 6, 10/10: Zorn’s lemma.  Equivalences AC => ZL => WOP => AC.  Applications of ZL.  (C–L §7.3.2, §7.5.1.)
    • Lecture 7, 17/10:  Review of model theory background.  The compactness theorem and applications.  Maps between structures: homomorphisms, embeddings, elementary embeddings, isomorphisms.  (C–L Vol. I, §4.6.)
    • Lecture 8, 19/10: Automorphisms; applications for undefinability.  Constructing elementary embeddings: the Tarski–Vaught test; downward Löwenheim–Skolem theorem.  (C–L §8.1, 8.2.)
    • Lecture 9, 24/10: Method of diagrams, downward Löwenheim–Skolem.  Categoricity, back-and-forth method.  (C–L §8.2, §8.5.)
    • Lecture 10, 2/11: General translations between languages/theories; applications to provability, consistency. Examples from algebra, plus standard model of PA in ZF. (not in C–L; notes to come)
    • Lecture 11, 9/11: Relativisation in set theory; transitive class models (aka inner models); the class of well-founded sets, relative consistency of Foundation. (C–L §7.5.1–2.)
    • Lecture 12, 16/11: Independence of Foundation by Rieger–Bernays models; independence of infinity by HF.  (C–L §7.5.2–3.)
    • Lecture 13, 23/11: A crash course on computability theory: definitions of primitive recursive and recursive (=computable) functions and predicates, with examples. (C–L §5.1, 5.2)
    • Lecture 14, 30/11: More on recursive functions and sets; sketch of equivalence with Turing-computability;  simulation, universal recursive functions; the halting problem. (C–L §5.2, 5.4.)
    • Lecture 15, 7/12: Connecting Peano Arithmetic with computability theory; representability of recursive functions in arithmetic; Gödel’s Incompleteness Theorems (full proof of first, sketch of second).  (C–L §5.2, 5.5.)