Logic and set theory form the foundational bedrock of modern mathematics. This course develops both the formal languages we use to express mathematical statements and the axiomatic systems that govern the objects we study. Rather than treating logic and set theory as separate subjects, we weave them together, revealing a deep parallel between semantic notions (what statements mean, what objects exist) and syntactic notions (what we can prove, what rules of inference are valid). This interplay culminates in the completeness theorems—first for propositional logic, later for predicate logic—which show that semantic truth and syntactic provability coincide.

The course begins with propositional calculus, where we learn to manipulate truth values and build formal derivations. We then introduce order structures—well-orderings, ordinals, and posets—which organize mathematical objects hierarchically and lead us to Zorn's lemma, a principle so powerful it underlies the existence of bases in vector spaces, maximal ideals in rings, and choice functions on infinite collections. Alongside these set-theoretic ideas, we develop predicate logic, the machinery for quantifying over objects and deriving consequences about them. This prepares us for axiomatic set theory itself: the Zermelo–Fraenkel axioms, the von Neumann cumulative hierarchy that constructs all sets from the empty set, and the theory of cardinals that measures infinite sizes. We close with incompleteness—Gödel's profound result that no consistent formal system rich enough to capture arithmetic can prove all truths about itself—a humbling boundary on what axioms can achieve.

By the end of this course, you will understand how modern mathematics rests on explicit, verifiable principles; how the concept of infinity is formalized and studied rigorously; and why certain mathematical questions cannot be resolved within standard axioms. You will have internalized the language of logic and developed facility with the set-theoretic constructions that underpin nearly every mathematical discipline.

# Introduction

This course is, at its core, about the foundations of mathematics itself. Most working mathematicians treat sets as self-evident objects — things can belong to other things, collections can be formed freely, and familiar operations like union, intersection, and subset are taken as given. This naive picture feels secure until it collapses. The first chapter explains why that collapse is inevitable, why it led to the formal apparatus studied in this course, and why that apparatus is genuinely difficult to set up without getting into trouble.

## The Problem with Naive Set Theory

The naive idea is simple: given any property $\phi$, we can form the set of all objects satisfying it. This principle is called **unrestricted comprehension**, and it is what allows us to write down familiar sets like $\{x \in \mathbb{Z} : x > 0\}$, the set of even integers, or the empty set $\varnothing = \{x : x \neq x\}$.

[definition: Unrestricted Comprehension] The **unrestricted comprehension principle** (also called naive comprehension) asserts: for any property $\phi$, the collection \begin{align*} \{x : \phi(x)\} \end{align*} is a set. That is, for any formula $\phi$, there exists a set whose members are precisely those objects $x$ for which $\phi(x)$ holds. [/definition]

The difficulty — discovered by Bertrand Russell in 1901 — is that unrestricted comprehension leads immediately to a contradiction. Consider the property $\phi(x) := x \notin x$, the property that a set does not contain itself as a member. By unrestricted comprehension, the collection

\begin{align*} X := \{x : x \notin x\} \end{align*}

is a set. But now ask: does $X$ belong to itself?

[quotetheorem:620]

The paradox is not an incidental flaw that might be patched by minor adjustment — it exposes a structural defect in unrestricted comprehension itself. The single axiom the paradox exploits is the claim that *any* formula $\phi$ determines a set; the self-referential nature of $\phi(x) := x \notin x$ is what turns this freedom into a contradiction. One might hope that simply forbidding the specific property "$x \notin x$" would suffice, but this response is inadequate for two reasons. First, Russell's paradox is only the most transparent of a family of such contradictions: **Cantor's paradox** (the set of all sets has a power set strictly larger than itself, contradicting the assumption that the set of all sets is maximal) and the **Burali-Forti paradox** (the collection of all ordinals is itself an ordinal strictly larger than itself) arise from the same permissive stance toward set formation, without any overt mention of self-membership. Second, banning self-referential definitions piecemeal does not touch the underlying pathology, which is that *any* comprehension scheme liberal enough to permit "the set of all sets" will generate paradoxes. The correct response is not to prohibit particular formulas but to restrict comprehension itself: sets may only be carved out of already-existing sets, never conjured from a universe of all objects.

[remark: The Barber Paradox] Russell popularised an informal version: a barber shaves exactly those people who do not shave themselves. Does the barber shave himself? The logical structure is identical to the set-theoretic paradox. The informal version makes the contradiction vivid, but the mathematical version is what matters: naive set theory is inconsistent, not merely paradoxical. [/remark]

This is not a curiosity about a strange, pathological set. It is a proof that the unrestricted comprehension principle is logically untenable. Any mathematical system built on it is inconsistent — every statement is provable, which means nothing is provable in any meaningful sense. The entire edifice of mathematics, if resting on naive set theory, is built on sand.

## The Response: Axiomatic Set Theory

The response to Russell's paradox was to replace the naive picture with a carefully chosen list of axioms — specific, explicit principles about what sets exist and how they can be formed, chosen precisely to be strong enough to derive all of mathematics while avoiding the contradictions that unrestricted comprehension produces. This is the programme of **axiomatic set theory**, most fully developed by Zermelo and Fraenkel in the early twentieth century.

The analogy with Euclid's geometry is apt. Euclid did not define lines and points in terms of anything more primitive; he stated axioms about how they behave. Similarly, axiomatic set theory does not define what sets *are* — it states axioms about membership $\in$, and derives everything from those axioms alone. The axioms of ZF set theory (Zermelo–Fraenkel) will be developed in detail later in the course. They include, for instance, a restricted comprehension principle: given an *existing* set $A$, one may form $\{x \in A : \phi(x)\}$, but one may not form $\{x : \phi(x)\}$ without first specifying the ambient set $A$. This single restriction blocks Russell's paradox: the set $X = \{x : x \notin x\}$ would require an ambient set of *all* sets, and the axioms do not permit that set to exist.

The contrast between the two comprehension principles is important enough to illustrate concretely.

[example: Unrestricted vs Restricted Comprehension] Consider the property $\phi(x) :=$ "$x$ is an even integer." **Under unrestricted comprehension**, we may form $E := \{x : x \text{ is even}\}$ outright, with no ambient set required. This particular set causes no trouble — the even integers form a perfectly coherent collection. But unrestricted comprehension makes no distinction between benign properties and dangerous ones. The same principle that produces $E$ also produces $X := \{x : x \notin x\}$, which we have already seen leads to contradiction. **Under restricted comprehension** (as in ZF), we must first specify an ambient set. Given the set $\mathbb{Z}$ of integers (whose existence is guaranteed by the axioms), we may form \begin{align*} E := \{x \in \mathbb{Z} : x \text{ is even}\}, \end{align*} and this is a legitimate set. But we cannot form $\{x : x \notin x\}$ without an ambient set — and no axiom of ZF provides a set of all sets to serve as that ambient. The dangerous collection is blocked at the source. The key point is that restricted comprehension gives us all the sets we need for ordinary mathematics (we can always specify a suitable ambient set), while ruling out exactly the self-referential constructions that cause paradoxes. [/example]