Please take this page in conjunction with the Part III Guide to Courses Foundations section.

Traditionally, mathematical logic is divided into areas such as category theory, computability theory, model theory, proof theory, and set theory.

*Category theory and model theory* deal with general constructions and concepts that can be applied in many other areas of mathematics: as a consequence, these courses will use examples from courses such as Part Ia *Groups*, Part Ib *Groups, Rings, & Modules*, and Part Ib *Analysis & Topology*. Students are expected to be familiar with the main definitions and techniques from these courses or willing to achieve that familiarity by reading the corresponding textbook literature.

Courses in *set theory* are given under various names, e.g., *Topics in Set Theory,* *Forcing & the Continuum Hypothesis, Infinite Games* or *Large Cardinals*. Some parts of set theory closely link to the general theory of metric and topological spaces, so Part Ib *Analysis & Topology* can be relevant.

The course *Logic & Computability* covers topics from proof theory and computability theory. Parts of the course may rely on very basic material from computability theory, as it is taught in the Part II course *Automata Formal Languages*.

All Part III Foundations courses build on the material of the Part II course *Logic & Set Theory*. This course covers the basics of mathematical logic (syntax and semantics of propositional and first order logic, completeness and compactness) as well as axiomatic set theory (axioms of Zermelo-Fraenkel set theory, ordinals, cardinals). The amount of knowledge in logic and set theory assumed in the Part III logic courses differs by course:

- Logic: essential for courses in model theory and set theory as well as
*Logic & Computability*; important for courses in category theory. - Set Theory: essential for courses in set theory; important for courses in model theory.

## Logic

The Part III Foundations courses generally assume that students are familiar with syntax and semantics of first order logic, Gödel's Completeness Theorem, and its consequences, such as compactness and various results on non-definability or non-axiomatisability.

As a reality check, have a look at Examples 8 to 13 Example Sheet #3 of the 2021/22 version of Part II *Logic & Set Theory*. You can also find a quick self-test with nine simple multiple choice questions here. You should easily get most of these right without any effort or preparation. Once you have done them, you can test if you are right by highlighting the text beside each question number below, which are white so hidden.

- B 2. D 3. C 4. A 5. D 6. B 7. B 8. D 9. C

If you feel that you need to brush up on your logic background, the following resources will be useful:

- The lecture notes Logic and Set Theory by Imre Leader. These notes formed the basis of the Part II course
*Logic & Set Theory*as offered in the academical years 2017/18, 2018/19 and 2021/22. - Peter T. Johnstone, Notes on Logic and Set Theory, Cambridge Mathematical Textbooks (Cambridge University Press, 1987).
- Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Mathematical Logic, Undergraduate Texts in Mathematics (Springer-Verlag, 1994).

## Set Theory

(Some of the) Part III Foundations courses assume that students are familiar with the basics of axiomatic set theory such as the axioms of Zermelo-Fraenkel set theory, the Axiom of Choice, and ordinals and cardinals.

As a reality check, have a look at Examples 9 and 10 on Example Sheet #2, Example 6 on Example Sheet #3, and Examples 7, 8, 10, and 11 on Example Sheet #4 of the 2018/19 version of Part II *Logic & Set Theory*. You can also find a quick self-test with fourteen simple multiple choice questions here. You should easily get most of these right without any effort or preparation. Once you have done them, you can test if you are right by highlighting the text behind each bullet point, which is white so hidden.

- Basics: 1C 2D 3C 4C 5D 6D
- Ordinals: 7B 8C 9A
- Cardinals: 10A 11D 12D 13D 14B

If you feel that you need to brush up on your set theory background, the following resources will be useful:

- The lecture notes Logic and Set Theory by Imre Leader. These notes formed the basis of the Part II course
*Logic & Set Theory*as offered in the academical years 2017/18, 2018/19 and 2021/22. - Peter T. Johnstone, Notes on Logic and Set Theory, Cambridge Mathematical Textbooks (Cambridge University Press, 1987).
- Kenneth Kunen, Set Theory, Studies in Logic Vol. 34 (College Publications, 2011).

## Computability Theory

Some of the Part III Foundations courses (in particular *Logic & Computability*) assume very basic familiarity with the definitions and concepts from computability theory. It is expected that students know the definitions of what computable and computably enumerable sets are, why these two notions are not equivalent, and how to encode machines and formulas as natural numbers via Gödel numbering. This material can be obtained from the introductory chapters of textbooks in computability theory such as

- Robert I. Soare, Turing Computability, Theory and Applications, Theory and Applications of Computability. (Springer-Verlag, 2016).
- S. Barry Cooper, Computability Theory, (Chapman & Hall, 2004).