Sets are not the end all be all

Disclaimer: I am by no means an expert on foundations, so I cannot guarantee that mistakes, pedagogical/philosophical oversights, etc are not present.

Mathematicians study collections of objects. (Here when we say “collection” we mean it in a very informal sense.) For instance, we can make claims about every even integer, or every isosceles triangle.

Once upon a time, there was this naive conception of collections as sets, and in order to describe as many collections as possible using the language of naive set theory, a notion of unrestricted comprehension was adopted. (We will get into what that means shortly.)

However, this wasn’t good enough: with unrestricted comprehension we got Russell’s Paradox. This is probably old news for most readers of this blog, but we will quickly and informally cover Russell’s Paradox again.

Unrestricted comprehension says that given some predicate $\phi$, there exists a set $S$ whose members are precisely those that satisfy $\phi$. Because $x \not \in x$ is a valid predicate, there exists a set $S$ consisting of sets that do not contain themselves. Yet the existence of this $S$ is self-contradictory:

• If $S \in S$, then $S \not \in S$ is false, meaning that $S$ cannot be a member of $S$, contradiction.
• If $S \not \in S$, then $S \not \in S$ is true, meaning that $S$ must be a member of $S$, contradiction.

The axiom of unrestricted comprehension was strong. Too strong, in fact, which is why it led to a contradiction. So rather than having a set of implicit, “obvious” axioms with which you could construct sets, mathematicians actually shored up the exact axioms. They comprise Zermelo–Fraenkel Set Theory with the Axiom of Choice, abbreviated to ZFC.

So how does our newly constructed set theory really work, exactly? In other words, what is ZFC? This is where the YouTube videos all stop, and where the meat really begins.

I am sure that at many points in your life, you have referred to the set of all natural numbers. But step back for a second. How do we even know such a set exists? In other words, what justifies us taking this collection of all natural numbers (which may or may not be a set) and decreeing it to be a set? It is ZFC that precisely allows us to do this.

Our set theory is constructive in nature. Here is how ZFC works: given some pre-existing sets, we can apply an axiom of ZFC to explicitly construct another set.¹ For example, given two sets $A$ and $B$, we may construct the set ${A, B}$. Furthermore, ZFC gives us two sets to start with: the empty set, i.e. the set with no elements, and an infinite set. And we may only decree a collection as a set once we have shown it can be constructed via the axioms of ZFC.²

Furthermore, in ZFC, the only objects of study are sets. On the surface, this seems inadequate: how can we define the natural numbers, let alone functions, shapes, etc? But the answer is simple: we define the natural numbers as a sequence of sets. In particular, we define

• $0 = \{\}$, i.e. the empty set,
• and for each $n \geq 0$, we define $n + 1 = n \cup \{n\}$.

(Note that this implies $n + 1 = {0, 1, \ldots, n}$ as well.)

We also define functions as subsets of Cartesian Products. Say we have a function $f \colon \{0, 1\} \to \{0, 1\}$ where $f(x) = x$. Then we may define $f$ to be the set $\{(0, 0), (1, 1)\}$. Note that there is exactly one ordered pair with $0$ as the $x$-coordinate, and likewise for $1$. The $y$-coordinate is the value associated with the function.

Of course, you might ask what an ordered pair is. And the answer, again, is a set: specifically, $(x, y) = \{x, \{x, y\}\}$. (It is left as an exercise to show that $(x_1, y_1) = (x_2, y_2)$ if and only if $x_1 = x_2$ and $y_1 = y_2$, in other words, that ordered pairs indeed uniquely identify the values of the two coordinates.)

You get the idea. We now can explicitly show that certain sets exist and study them. Furthermore, we can encode the rest of mathematics within the language of set theory.

But there is one major catch. Let’s go back to the reason mathematicians created ZFC in the first place: because naive set theory led to a contradiction (Russell’s Paradox). And all of our work with ZFC is largely pointless if ZFC turns out to also lead to a contradiction. So is ZFC consistent? That is, is ZFC free of contradictions?

I have two pieces of bad news for you. The first is that we don’t know whether ZFC is consistent. And the second much worse piece of news is that if ZFC is consistent, we will never know. This is because of Godel’s Second Incompleteness Theorem: because ZFC is sufficiently strong,

• we can use ZFC to make the statement “ZFC is consistent”,
• and we cannot prove it in ZFC.

Therefore, the only way we will ever know whether ZFC is consistent is by finding an inconsistency. And this is true of any logical system that is strong enough to perform arithmetic. So we will never truly know whether our model of set theory is self-consistent, regardless of what model we use.

But ZFC seems reasonable enough and no one has found a contradiction yet. Having done the best we can, we move on.³

Classes

I can prove to you that any singleton set $S$ satisfies the (trivial) statement “$x \in S \land y \in S \implies x = y$”. Similarly, I can make claims about every group, every homeomorphism, and so on. So the collection of, say, singleton sets is worth making statements about.

But the collection of all singleton sets is not a set! For if it was, then we may take $\bigcup \{\{a\}, \{b\}, \ldots\}$ and get $\{a, b, \ldots\}$, i.e. the set of all sets, which leads to a contradiction (as that set would then contain itself).

It is possible to just be satisfied with statements like “for every singleton set…” and move on. But it is quite natural to ask what the collection of singleton sets really is, and whether it has anything in common with other non-set collections like the collection of groups. To that end, we define a notion of a class.

Very briefly, a class is just a collection of sets that can be described. To really understand what a class is, we return to unrestricted comprehension.

We cannot define $\{S \mid S \text{ is a singleton set}\}$ as a set. But we may define it as a class. And this is how classes are defined in general: it is just the collection of sets satisfying a certain predicate $\phi$. So saying that set $S$ belongs to class $C$ really just means that $S$ satisfies $\phi$.

A little more detail about ZFC: because unrestricted comprehension leads to Russell’s paradox, we instead have a notion of restricted comprehension. That is, we may not say $\{x \mid x \text{ satisfies } \phi\}$, but given some “parent set” $S$, we may say $\{x \in S \mid x \text{ satisfies } \phi\}$, which means that we can construct subsets of an already existing set whose members satisfy some predicate. This is why it is a big deal to talk about collections formed by unrestricted comprehension, because they cannot be sets.

You might be asking why classes don’t run into Russell’s paradox. Why isn’t there a class of all classes that do not contain themselves? Because by definition, classes may only contain sets as members. So it does not make sense to talk about classes of classes, and the hope is we sidestep such paradoxes.

Probably. Recall by Godel’s Second Incompleteness Theorem that we have no way of actually knowing whether our universe of sets and classes leads to a paradox. And again, there are multiple ways of creating new axioms to define classes, each of which may be subtly different. The same way set theory does not necessarily have to be formalized via ZFC, class theory does not have to be formalized via any particular set of axioms.

There does exist a conservative extension of ZFC with classes known as NBG. By “conservative” I mean that any proof in NBG that solely refers to sets is also valid in ZFC. And there is a very good StackExchange post concerning the relative advantages of ZFC and NBG.

Finally, I must mention that not every collection of objects may be modeled as a class. Why? As a dumb example, the collection of all classes is surely something worth studying. But it is not a class, because every member of a class must be a set. The existence of proper classes means the collection of classes cannot be a class itself.

More generally, classes are “describable” by a predicate, but not all collections are describable.

Why bother?

Quick note: when I say “proper class” I mean a class that cannot be modeled as a set.

In most fields of math, as far as I am aware, there is no reason to prefer discussing something like “the class of all continuous functions” as opposed to just saying “if a function is continuous…” So as one would expect, these fields implicitly use ZFC as their set theory and make no mention of classes.

But there is one field that explicitly does mention such collections: category theory. For example, the collection of objects in the category of sets is “the class of all sets”. And by making a distinction between sets and classes, we may describe a category as “small” if the collection of its objects and the collection of its arrows are both sets, and “large” if one of these collections is a proper class. Then we may discuss, for instance, the category of all small categories, which avoids the issue of self-containment (as this category would be large).