Logic II : Computability, Set Theory, and Model Theory (Fall 2025)

Logic II is a second level logic course, giving an introduction to major topics of modern mathematical logic. It consists of three main parts:

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

Textbooks

The course textbook is the following book:

R. Cori, D. Lascar, 2001, Mathematical Logic, A Course with Exercises, Part II: Recursion Theory, Gödel’s Theorems, Set Theory, Model Theory, Oxford University Press.

I also highly recommend Jeremy Avigad’s excellent book:

Avigad, Jeremy. 2022. Mathematical Logic and Computation. Cambridge University Press.

For Turing Machines we use

Bridges, Douglas. 1994. Computability: A Mathematical Sketchbook. Springer.

Course Materials

The course page on kurser.math.su.se

Some Slides

• History of computability

The Lean Diary

https://github.com/sinhp/CompLean/

Lean is used as a digital diary for the first part of the course. The companion Lean code contains detailed definitions of the main concepts of the lectures, some basic examples and computations, and verified proofs of some of main theorems of computability and incompleteness.