This is a continuation of my earlier set theory post. In this post, I’ll describe the next three axioms of ZF and construct the ordinal numbers.
1. The Previous Axioms
As review, here are the natural descriptions of the five axioms we covered in the previous post.
Axiom 1 (Extensionality) Two sets are equal if they have the same elements.
Axiom 2 (Empty Set Exists) There exists an empty set which contains no elements
Axiom 3 (Pairing) Given two elements and , there exists a set containing only those two elements. (It is permissible to have , meaning that if is a set then so is .)
Axiom 4 (Union) Given a set , we can create , the union of the elements of . For example, if , then is a set.
Axiom 5 (Power Set) Given any set , the power set is a set.
I’ll comment briefly on what these let us do now. Let , and recursively define . So for example,
Now let’s drop the formalism for a moment and go on a brief philosophical musing. Suppose we have a universe (I’ll explain later what is) where the only sets are those which appear in some . You might then see, in fact, that the sets in actually obey all five axioms above. What we’ve done is provide a model for which the five axioms are consistent.
But this is a pretty boring model right now for the following reason: even though there are infinitely many sets, there are no infinite sets. In a moment I’ll tell you how we can add new axioms to make infinite sets. But first let me tell you how we construct the natural numbers.
2. The Axiom of Foundation
We’re about to wade into the territory of the infinite, so first I need an axiom to protect us from really bad stuff from happening. What I’m going to do is forbid infinite chains.
Axiom 6 (Foundation) Loosely, there is no infinite chain of sets
You can see why this seems reasonable: if I take a random set, I can hop into one of its elements. That’s itself a set, so I can jump into that guy and keep going down. In the finite universe , you can see that eventually I’ll hit , the very bottom of the universe. I want the same to still be true even if my sets are infinite.
This isn’t the actual statement of the axiom. The way to say this in machine code is that for any nonempty set , there exists a such that for any . We can’t actually write about something like in machine code (yet). Nevertheless this suffices for our axioms.
There’s an important consequence of this.
Theorem 1 for any set .
Proof: For otherwise we would have which violates Foundation.
3. The Natural Numbers
Note: in set theory, is considered a natural number.
Now for the fun part. If we want to encode math statements into the language of set theory, the first thing we’d want to do is encode the numbers , , in there so that we can actually do arithmetic. How might we do that?
What we’re going to do is construct a sequence of sets of sizes , , and let these correspond to the natural numbers. What sets should we choose? Well, there’s only one set of size , so we begin by writing
I’ll give away a little more than I should and then write
Now let’s think about . If we want to construct a three-element set and we already have a two-element set, then we just need to add another element to that’s not already in there. In other words, to construct I just need to pick an such that , then let . (Or in terms of our axioms, .) Now what’s an easy way to pick such that ? Answer: pick . By the earlier theorem, we always .
Now the cat’s out of the bag! We define
And there you have it: the nonnegative integers. You can have some fun with this definition and write things like
now. Deep down, everything’s a set.
4. Finite Ordinals
We’re currently able to do some counting now, because we’ve defined the sequence of sets
by and . This sequence is related by
Some properties of these “numbers” I’ve made are:
- They are well-ordered by (which corresponds exactly with the which we're familiar with; that's a good motivation for choosing this construction, as the well-ordering property is one of the most important properties of , and using for this purpose lets us do this ordering painlessly). That means if I take the elements of , then I can sort them in a transitive chain like I've done above: for any and , either or . For example, the elements of are , , , and . It also means that any subset has a “minimal'' element, which would just be the first element of the chain. Here is the complete definition.
- The set is transitive. What this means that it is a “closed universe” in the sense that if I look at an element of , all the elements of are also in . For example, if I take the element of , all the elements of are in . Looking deeply into won’t find me anything I didn’t see at the top level.
In other words, a set is transitive if for every , .
A set which is both transitive and well-ordered by is called an ordinal, and the numbers are precisely the finite ordinals. But now I’d like to delve into infinite numbers. Can I define some form of “infinity”?
5. Infinite Ordinals
To tell you what a set is, I only have to tell you who its elements are. And so I’m going to define the set
And now our counting looks like this.
We just tacked on an infinity at the end by scooping up all the natural numbers and collecting them in a set. You can do that? Sure you can! All I’ve done is written down the elements of the set, and you can check that is indeed an ordinal.
Well, okay, there’s one caveat. We don’t actually know whether the I’ve written down is a set. Pairing and Union lets us collect any finite collection of sets into a single set, but it doesn’t let us collect things into an infinite set. In fact, you can’t prove from the axioms that is a set.
For this I’m going to present another two axioms. These are much more technical to describe, so I’ll lie to you about what their statements are. If you’re interested in the exact statements, consult the lecture notes linked at the bottom of this post.
Axiom 7 (Replacement) Loosely, let be a function on a set . Then the image of is a set:
Axiom 8 (Infinity) There exists a set .
With these two axioms, we can now write down the first infinite ordinal . So now our list of ordinals is
But now in the same way we constructed from , we can construct a set
and so on — all of these are also transitive and well-ordered by . So now our list of ordinals is
Well, can we go on further? What we’d like is to define an “ or ”, which would entail capturing all of the above elements into a set. Well, I claim we can do so. Consider a function defined on which sends to . So , , . (Strictly, I have to prove that set-encoding of this function, namely , is actually a set. But that’s put that aside for now.) Then Replacement tells me that I have a set
From here we can union this set with to achieve the set . And we can keep turning this wheel repeatedly, yielding the ordinal numbers.
I won’t say much more about these ordinal numbers since the post is already getting pretty long, but I’ll mention that the ordinals might not correspond to a type of counting that you’re used to, in the sense that there is a bijection between the sets to . It might seem like different numbers should have different “sizes”. For this you stumble into the cardinal numbers: it turns out that a cardinal number is just defined as an ordinal number which is not in bijection with any smaller ordinal number.
6. A Last Few Axioms
I’ll conclude this exposition on ZFC with a few last axioms. First is the axiom called Comprehension, though it actually can be proven from the Replacement axiom.
Axiom 9 (Comprehension) Let be some property, and let be a set. Then the notion
is a set. More formally,
Notice that the comprehension must be restricted: we can only take subsets of existing sets. From this one can deduce that there is no set of all sets; if we had such a set , then we could use Comprehension to generate , recovering Russel’s Paradox.
So anyways, this means that we can take list comprehensions.
Finally, I’ll touch a little on why the Axiom of Choice is actually important. You’ve probably heard the phrasing that “you can pick a sock out of every drawer” or some cute popular math phrasing like that. Here’s the precise statement.
Axiom 10 (Choice) Let be a set such that . Then we can define a function on such that for every . The function is called a choice function; given a bunch of sets , it chooses an element out of every . In other words, for any with , there exists a set
with for every .
In light of the discussion in these posts, what’s significant is not that we can conceive such a function (how hard can it be to take an element out of a nonempty set?) but that the resulting structure is actually a set. The whole point of having the ZF axioms is that we have to be careful about how we are allowed to make new sets out of old ones, so that we don’t run ourselves into paradoxes. The Axiom of Choice reflects that this is a subtle issue.
So there you have it, the axioms of ZFC and what they do.
Thanks to Peter Koellner, Harvard, for his class Math 145a, which taught me this material. My notes for this course can be downloaded from my math website.
Thanks to J Wu for pointing out a typo in Replacement and noting that I should emphasize how leads to the well-ordering for the ordinals.
2 thoughts on “Set Theory, Part 2: Constructing the Ordinals”
[…] this we need a notion of an ordinal number. I defined these in their full glory a previous blog post, but I don’t need the full details of that. Here’s what I want to say: after all the […]
Perhaps it’d be nice to mention that a finite ordinal is an ordinal that either (i) is ∅, or (ii) isn’t ∅, has ∅ as its only non-successor element, and has a maximum element. We can thus rule out ω as a finite ordinal because, although it has ∅ as its only non-successor element, it has no maximum element. We can also rule out ω + 1 as a finite ordinal because, although it has a maximum element, it has both ∅ and ω as non-successor elements.