The axioms of set theory, part 2

The problem with the axiom schema of comprehension is very simple. By the axiom schema of comprehension there must be a set, which we’ll call the Russell set, which consists of the sets which do not contain themselves. Consider the question of whether the Russell set contains itself. Well, if the Russell set contained itself, that would mean it was a set which did not contain itself, since all the members of the Russell set do not contain itself. Since this is contradictory, the Russell set must not contain itself. But the Russell set contains every set which does not contain itself, so it must contain the Russell set. No matter how you answer the question, a contradiction is inevitable.

[Russell’s paradox was actually not the only paradox in naive set theory; there were also, for example, the Burali-Forti paradox and Cantor’s paradox. However, these involve the concepts of ordinals and cardinals, respectively, which would take a lot of explaining. Maybe I’ll do a post about them later.]

Like most paradoxes, Russell’s paradox could be worked around; but mathematicians came up with a few different ways to work around the paradox. In this post I’m talking about ZF, the most popular set theory, but there are others, like Quine’s New Foundations (NF), which are just as adequate for mathematics and work around Russell’s paradox in a completely different way. This is problematic if you think of axioms as self-evident truths, since ZF and NF contradict each other, so their axioms can’t all be self-evident. It’s probably for this reason that mathematicians have generally abandoned this definition.

I’ll list the axioms of ZF which replace the axiom schema of comprehension below.

• The axiom schema of specification is a limited version of comprehension, which asserts the existence of arbitrary sets provided they are subsets of an existing set. A notable consequence of this is that no superset of the Russell set can exist, including the set of all sets.
• The axiom of pairing says that for every pair of sets, there is a set containing both of those sets.
• The axiom of union says that for every set $A$, there is a set, called the union of $A$ whose members are all the members of members of $A$. In other words, the union of $A$ is what you get when you merge all the sets that $A$ contains into a single set.
• The axiom of power set says that for every set $A$, there is a set, called the power set of $A$, whose members are all the subsets of $A$.
• The axiom schema of replacement says that for every function whose domain is a set, the range is a set as well. This is an axiom schema, because a function is essentially a logical formula with the property that for every member $x$ of the domain, there is exactly one object satisfying the formula when $x$ is taken as its argument (this object is the output of the function for the input $x$.

All these axioms are very plausible, though one might wonder how the existence of these sets in particular is any more self-evident than the existence of, for example, the set of all sets. The last two axioms of ZF are somewhat more controversial. By the way, both of these aren’t implied by the axiom schema of comprehension; they would be necessary even in naive set theory, if you accepted their truth.

First, there is the axiom of infinity, which essentially states that a set exists of infinite size. You might wonder how this can be phrased in logical language. Well, first you say that the set contains some particular set, such as the empty set, as a kind of starting point. Then you think of an operation that can be performed on a set, so that if you applied it repeatedly to the starting point set, you would get an infinite sequence of distinct sets. Such an operation is called a successor operation. Then the axiom can say that a set exists which contains the starting point set and has the property that if you apply the successor operation to any one of its members, the resulting set is still a member. The operation usually used is to construct a set consisting of all the members of the original set, plus the original set itself. This reason for this is that if we call the empty set 0, the successor of 0 consists of just 0. We can call this set 1. The successor of 1 consists of 0 and 1; we can call this set 2. The successor of 2 consists of 0, 1 and 2; we can call this set 3. We can go on like this and define all the natural numbers as sets, with every natural number being the set of all the preceding natural numbers.

The reason the axiom of infinity is controversial is because infinity is controversial. There are mathematicians, known as finitists, who essentially deny the existence of any infinite quantities, or at least (since it’s not clear what it means for a mathematical concept to exist or not exist) believe that infinity is not a useful mathematical concept.

[There are even mathematicians, called ultrafinitists, who deny the existence of all the natural numbers… according to them, the existence of sufficiently large natural numbers must be considered, at least, unproven. This isn’t as stupid as it might sound at first.]

The final axiom is the axiom of choice. Strictly speaking, this is not part of ZF. It’s controversial enough that if you include the axiom of choice in the theory, you have to refer to it as ZFC (Zermelo-Fraenkel set theory with choice). This one deserves a whole page about it, so it’ll be the subject of part 3!