Our last post took us through the axioms of ZF and explored the first two in detail. This post explores the schema of separation and the notion of classes in ZF.

Schema of separation

Recall that the fourth axiom of ZF is the schema of separation, which states that 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) \}$. In formal notation, $$ \forall X \forall p \exists Y \forall u ( u \in Y \iff u \in X \land P(u,p)) $$

We can augment the schema of separation to work with predicates of $n$ parameters using our previous definition of ordered $n$-tuples (see my previous post for that definition). Let $\psi(u, p_1, p_2, \dots, p_n)$ be a predicate with $n$ parameters. Since we’ve so far only defined the schema of separation for predicates of a single parameter, we need a “wrapper” for $\psi$. This wrapper puts the parameters $p_1, \dots, p_n$ in an ordered $n$-tuple. Since an ordered $n$-tuple is a set–a single object–by our previous definition, we can pass these wrapped parameters as a single parameter and so the schema of separation will apply. Define $$\phi(u, (p_1, \dots, p_n)) = \psi(u, p_1, \dots, p_n)$$ Then by applying the schema of separation we are guaranteed for any set $X$ and parameters $p_1, \dots, p_n$ that the set $$\{ u \in X \mid \phi(u, (p_1, \dots, p_n))$$ exists.

The upshot of this is that the schema of separation is actually as many axioms as there are natural numbers. This is in fact what we mean by calling the schema of separation a schema: axiom schemata “represent infinitely many axioms”.

We can restate the axiom of separation in the following way. Let $C$ be the class $C = \{ u \mid \phi(u, p_1, \dots, p_n) \}$. Then for any set $X$, $C \cap X$ exists (and is thus a set, since everything in ZF is a set). Jech restates this in English as “a subclass of a set is a set”.

One immediate result of this Jech points out is that, given at least one set $X$ exists (which is guaranteed by the axiom of infinity), the empty set also exists because, by the schema of separation, $\{x \in X \mid x \neq x \} = \emptyset$ exists.

The what and why of classes

I’ve used the term class enough times that some explanation is owed. Classes don’t formally exist in ZF set theory–the only type of object is a set. Instead, classes are an “informal notion” used for the practical reason of being easier to manipulate due to their looser rules. For any predicate $P(x, p)$ with parameter $p$ we can define the class $C = \{u \mid P(u,p) \}$. We can use the usual operations we use on sets–$\cup$, $\cap$, $\setminus$, $\bigcup$, and $\subset$–in the obvious way based on the predicate definition of a given class. I think the reason we’re allowed allowed to do this is that we haven’t introduced a new type of object into ZF: by saying an element $x$ is in a class $C$ defined from a predicate $P$, we’re not saying anything about $C$ (or that $C$ properly exists)–we’re saying that $P(x)$ is true. Introducing the notion of a class is just a useful shorthand.

Proper classes and Russell’s paradox

Let’s remind ourself why, from our informal definition, a class is not equivalent to a set. Define a proper class to be a class that isn’t a set In ZF, if something’s not a set, it doesn’t exist. Proper classes don’t exist in ZF set theory, but they do in other axiomatic set theories like NBG¹.

By example, let’s recall why no universal set exists. This is Russell’s paradox, the most famous argument in set theory. Call $U$ the universal class, defined as $U = \{ x \mid x = x \}$. Suppose $U$ is a set. Then we can define a set $V = \{ u \in U \mid u \not \in u \}$. N.b. that $V$ must exist in ZF set theory by the schema of separation ($P(x) = x \not \in x$ is a predicate and $U$ is a set by supposition, so $V$ must be a set).

But then we can ask: is $V$ a member of $V$? If not, then it satisfies the predicate $V \not \in V$, so $V \in V$. But if $V \in V$, then $V$ fails its own definition–it contains an element that is a member of itself. Since we’ve obtain a contradiction, we have to conclude that $U$ is not a set. Instead, $U$ is a proper class, which doesn’t exist in ZF.

Axiom of union

Recall the axiom of union states that the union of any set exists. That is $$ \forall X \exists Y \forall u ( u \in Y \iff \exists z ( z \in X \land u \in z)) $$ We define that set $Y$ as $\bigcup X$ and note that it’s unique by the axiom of extensionality. The axiom of union also lets us define some more useful concepts, like taking the union of two sets: $$ X_1 \cup X_2 \equiv \bigcup \{ X_1, X_2 \}$$ and then naturally taking the union of $n$ many sets $$ X_1 \cup X_2 \cup \dots \cup X_n \equiv \bigcup \{ X_1, X_2, \dots, X_n \} $$

The symmetric difference of two sets $X$ and $Y$ can also be defined from the axiom of union as $$X \triangle Y = (X \setminus Y) \cup (Y \setminus X)$$

That’s enough for now. Our next post will explore the axioms of power set, union, and infinity.