Introduction

Set theoretic ideas were banging around the mathematical world for a long time, but Georg Cantor and Richard Dedekind are usually credited as the pro- genitors of what we call naïve set theory. Naïve set theory doesn’t refer to one theory but rather to a collection of informal, natural language descriptions of set theory. It wasn’t long after these descriptions emerged that fundamental problems inherent in them–including but not limited to famous Russell’s paradox–also emerged. The need to exorcise these paradoxes from the foundations of math gave rise to different axiomatic systems to formally define a more robust set theory. The most widely used of those systems comes from Ernst Zermelo and Abraham Fraenkel, so it’s called ZF.

My primary reference for this series of posts is the third edition of Set Theory by Thomas Jech, considered the best survey of its titular field. I read parts of it to prepare for the oral exams of an undergraduate set theory class, but much of the material it covers is new to me. I’ll do my best to informally cite other references I use and make it clear what observations are my own.

The axioms

Let’s first list the ZF axioms later to explore each in further detail.

1. (Extensionality) If $X$ and $Y$ have the same elements, then $X = Y$.

2. (Pairing) For any $a$ and $b$, there exists a set $\{a, b\}$ that contains exactly the elements $a$ and $b$.

3. (Schema of separation) If $P$ is a predicate with parameter $p$, then for any $X$ and $p$, there exists a set $$Y = \{ u \in X \mid P(u,p) \} $$ That is, the set $Y$ of elements in $X$ that satisfy $P$ under parameter $p$ is guaranteed to exist.

4. (Union) For any $X$ there exists a set $Y = \bigcup X$, the union of all elements in $X$.

5. (Power set) For any $X$ there exists a set $\mathcal{P}(X)$ which contains all subsets of $X$.

6. (Infinity) There exists a set $I$ that contains

   • The empty set $\emptyset$, and
   • The successor $x \cup \{x\}$ for each element $x$ in $I$.

   Or more plainly, there exists an infinite set.

7. (Schema of replacement) If a class¹ $F$ is a function, then for any $X$ there exists a set $$Y = F(X) = \{F(x) \mid x \in X\}$$ That is, the image of a set under a function is also a set.

8. (Regularity) Every set $X \neq \emptyset$ contains an element $x$ such that $X \cap x = \emptyset$.

Those are the ZF axioms. Not always included in them is the Axiom of Choice (AC), which goes like this:

9. (Choice) Let $C$ be a collection of sets. Then there exists a choice function $f$ over $C$ such that, for each set $S$ in $C$, $f(S) \in S$.

In plain language, the AC says that for any collection of sets, we can define a choice function that picks an element out of each set in the collection. While that might seem intuitive, allowing the AC into our set of axioms will commit us to accept some very unintuitive consequences later on.

More detail on each axiom

Extensionality

A formal restatement of the axiom of extensionality I stole off Wikipedia is $$ \forall A \forall B (\forall x (x \in A \iff x \in B) \implies A = B) $$ Note that the converse of the final implication is also true–Jech cites “an axiom of predicate calculus”, which is convincing enough for now. So we get: for any $A$, $B$, and $x,$ $$(x \in A \iff x \in B) \iff A = B$$ The axiom of extensionality tells us that sets are determined by their elements.

Pairing

The axiom of pairing gives us unordered sets: by pairing, $\{a, b\}$ exists for any $a$ and $b$. Any other set with exactly those two elements must be the same set by the axiom of extensionality, so the unordered pair is unique.

Ordered tuples and their uniqueness

Jech takes a second to note that we can define ordered pairs² as: $$ (a,b) = \{ \{a\}, \{a, b\} \} $$ The uniqueness proof for ordered pairs is straightforward. We want to show $$ (a,b) = (c,d) \iff (a = c \land b = d) $$ Take a second to prove this on your own before reading my proof sketch.

Clearly if $a = c$ and $b=d$, then $(a,b) = (c,d)$ by definition. How about the converse? We have to show $$ \{ \{a\}, \{a,b\} \} = \{ \{c\}, \{c,d\} \} \implies (a = b \land c = d) $$ First suppose $a = b$. Then our ordered pair $(a,b)$ becomes $(a,a) = \{ \{a \} \}$. If $c \neq d$, we obtain $\{a\} \neq \{a\}$ by “unpacking” the elements on the right-hand side of the equality using the converse of the axiom of extensionality, obtaining a contradiction. Therefore $c = d$, and by unpacking the RHS set again we get $(a,b) = (c,d)$ as desired. Finally, suppose $a \neq b$. By the same logic we used earlier, $c \neq d$. So $\{a,b\} = \{c\} or \{c, d\}$. But $\{a,b\} = \{c\}$ leads to another contradiction: $c = a$ and $c = b$ can’t be true since $a \neq b$ by assumption. So $\{a,b\} = \{c,d\}$. We can play the same game to obtain $\{a\} = \{c\}$, finishing the proof.

Jech closes out the section on the axiom of pairing by defining ordered $n$-tuples in the natural way: triples are $$ (a_1, a_2, a_3) = ((a_1, a_2), a_3)$$ and so on, up to $n$-tuples $$(a_1, a_2, …, a_n) = ((a_1,…,a_{n-1}), a_n) $$ Notice that since an ordered pair is by definition a set, an ordered triple is, by means of wrapping the first two elements in an ordered pair, also an ordered pair and thus a set (and so on for ordered $n$-tuples).

This post is getting long so I’ll cap it off here. Maybe in the future I’ll combine the next Jech posts into one. Enjoy the math and stay safe.