The Universe of Discourse

Starting to understand epsilon-zero

This post is going to be about what infinite ordinal numbers are, and about !!{\epsilon_0}!! is in particular. I had a brainwave a while back (18 months now, wow, I have definitely not been blogging enough) and suddenly understood !!{\epsilon_0}!! much better than I did before. I have several related ideas here and I am going to try to write one blog post about each of them, instead of one gigantic blog post about all of them together that I never finish.

I really like the ordinal numbers. For some reason I was repeatedly exposed to the infinite cardinals as a child and, while they are pleasingly mysterious, they're also somewhat uninteresting because they have no internal structure, they are just bignesses. It's super cool that there is more than one possible bigness of an infinite set, of course, but sets can have all sorts of interesting structure, and looking just at the bigness ignores all that.

The ordinals are much more satisfying, and also I feel that they are more like numbers. This post explains how they work and introduces the interesting ordinal !!{\epsilon_0}!!.

(I wrote an article a while back about how, when your twelve-year-old asks “what is infinity” you should answer as if they had asked “what is !!\omega!!”. Later I found out that Joel Hamkins recommended the same strategy, and I still stand by it.)

What we're doing

The idea behind the ordinals is that we want to define something like the “natural” numbers !!0, 1, 2, \dots!!, where each number has a successor and there is a less-than relation. But we want to do it in the context of elementary set theory, which is simpler. Extremely simple, in fact.

What is set theory?

I don't know how intelligible this article will be if you don't already know, but I am going to try to explain it as briefly as possible. People who already know what !!a\in B!! means can skip to the next section.

In set theory, the only kind of object is a “set”, which is like a featureless bag of things, which are called elements. What kind of things? We don't care, that's not part of the model. The only properties a set has are which things are in the bag.

It doesn't make sense to ask what color a set is or whather it is a citizen of Belgium; sets don't have colors, they aren't citizens of anywhere, and they don't have any other extrinsic properties. The only kind of question you can ask is about a set is:

Is this thing !!a!! in that set !!B!!?

When it is, we write !!a\in B!!, and when it isn't we write !!a\notin B!!.

When a set contains the things !!p, q, !! and !!r!!, and nothing else, we write it as

$$ \{ p, q, r\} $$

so for example !!\text{carrot}\in\{\text{fish}, \text{dog}, \text{carrot}\}!! but !!\text{raincoat}\notin\{\text{fish}, \text{dog}, \text{carrot}\}!!

There is one special set called the “empty set” that has nothing in it at all; it's written !!\{\}!!.

The one other piece of set theory you need to know for this article is that if you have two or more sets, you can combine them into a single set that contains everything that the original sets did. This is called the union of the sets. When combining two sets !!a!! and !!b!!, we write !!a\cup b!! for their union. For example:

$$ \{\text{tea}, \text{coffee}\} \cup \{\text{mango}, \text{octopus}\} = \{ \text{tea}, \text{coffee}, \text{mango}, \text{octopus} \} $$

There is a lot more than that to set theory but that is the basic idea and I think it's enough to get pretty far in this article.

To define numbers in the context of elementary set theory means that we want to find sets that we can interpret as numbers, and a way to interpret arithmetic and such as being operations on these sets. We want to show that those sets can be made to behave the way we expect numbers to behave, and that we can prove that the arithmetic operations have the properties that we expect numbers to have. For numbers, it's true that !!1+1=2!!, and we want to be sure that, whatever we decide that !!+!! means for sets, and whatever sets we've chosen to stand in for !!1!! and !!2!!, we should still have !!1+1=2!!.

Understanding when we can model a complicated system in terms of a simpler one, and how to do that, is one of the main concerns of mathematics. Set theory is just about the simplest system there is, so mathematics spends a lot of time trying to interpret various complicated systems in terms of set theory.

Less-than

Numbers have a less-than relation !!\lt !!, and elementary set theory has only one relation, !!\in!!, so it makes sense to try to use that for less-than, and see if it works. We’ll say that if !!a!! and !!b!! are sets that represent numbers, then !!a\lt b!! means the same as !!a\in b!!.

We want !!\lt !! to be transitive. That is if !!a\lt b!! and !!b\lt c!! then we should also have !!a\lt c!!.

If we're taking !!\lt!! to be synonymous with !!\in!!, then this means that if !!a,b,!! and !!c!! are sets that represent numbers, and if !!a\in b!! and !!b\in c!!, then we should also have !!a\in c!!. This is kind of a weird situation. It means that !!c!! is not a set of fish or carrots, it means that !!c!! is a set of sets. And it means any element of any of !!c!!’s sets is also an element of !!c!! itself. When this happens we say that the set !!c!! is transitive, using the word “transitive” analogously to the way we do what we say that !!\lt!! is transitive.

Transitivity puts fairly strict constraints on what a set can be like. There are lots of sets, but relatively few of them are transitive. Here are some examples of transitive sets, and the numbers they represent:

$$ \begin{align*} 0 &= \{\}\\ 1&=\{0\} \\ \end{align*} $$

Since we are using !!0!! here as just another way to write the empty set !!\{\}!!, we could have written !!1=\{\{\}\}!! instead of !!1=\{0\}!!. They mean exactly the same. But I feel that the nested curly braces quickly get confusing and don't really contribute to understanding. Still, remember that when we write the symbols !!0, 1!!, and so on, we're not using them in their usual sense of numbers. Rather, we are talking about these particular transitive sets.

The next one is:

$$ \begin{align*} 2 & = \{0, 1\} \\ \end{align*} $$

Since !!0=\{\}!! and !!1=\{\{\}\}!! the !!\{0, 1\}!! is an abbreviation for the set

$$ \{\{\}, \{\{\}\} \}. $$

I hope you can see why I want to avoid the raw curly-brace notation.

Continuing, we have:

$$ \begin{align*} 3 & = \{0, 1, 2\}\\ 4 & = \{0, 1, 2, 3\}\\ \vdots\\ 9 & = \{0, 1, 2, 3, 4, 5, 6, 7, 8\},\\ \vdots\\ 53 &= \{0, 1, 2, \dots, 52\}\\ \vdots \end{align*} $$

And so on.

These sets are all transitive. For example, !!3\in 4!! and !!4\in 9!! and sure enough, !!3 \in 9!! also. This isn’t trivial: Not every set of numbers is transitive. For example !!\{3, 4\}!! is not a transitive set because !!2\in4!! and !!4\in \{3, 4\}!! but !!2\notin \{3, 4\}!!.

We'll say that an ordinal number is a set that is transitive, and whose elements are also all transitive. All the sets in the list above are examples. There are transitive sets that aren't ordinals, but we're not interested in them in this article, because they aren't number-like in the same way.

This identification of numbers as theser particular sets does also make !!\in!! behave like the less-than relation in the way we wanted. For example, we have !!1\lt 2!! because !!1\in\{0,1\}!!, but not vice versa, it's not true that !!2\lt 1!! because !!2\notin\{0\}!!.

Technically this definition has a lot to recommend it. It’s extremely simple, which makes it easy to work with, and many natural theorems are easily proved. For example, when dealing with familiar numbers, it’s always false that !!a\lt 0!!, for any !!a!!. We'd like to able to prove the analogous thing for our synthetic sets-as-numbers. If we can’t (or worse, if we can prove the opposite) then our model is missing something important (or worse, it’s just wrong).

Well, by our definition of less-than, !!a\lt 0!! simply means !!a\in\{\}!!, which is false because !!\{\}!! has no elements, and that's the proof that !!a\lt 0!! is false.

Successorship

Another thing we need from numbers is a successor operation: each number should be followed by another, different one, and it should be possible to calculate which one. This has been recognized since the 19th century as the most important organizing principle that the natural numbers have. It’s is one of the few foundational things that almost every mathematician not only accepts but is happy with.

If !!T!! is some transitive set, we should be able to identify another, different transitive set that we can designate as the successor of !!T!!, the number that follows !!T!! in the sequence of numbers. It’s not hard to show that if !!T!! is transitive then so is

$$ T\cup \{T\} $$

See how it works when !!T=2 = \{0,1\}!!: the successor of !!2!! is

$$ 2\cup\{2\} = \{0, 1\}\cup\{2\} = \{0,1,2\} = 3 $$

as we would hope.

Limits

This gets us the numbers, as we wanted, and we could go on from here to explain how !!+!! and !!\times!! work and so on, but today we are going a different direction. It turns out that if we add one more ingredient we get a lot more than just familiar numbers. There’s one other way of making an ordinal number out of smaller ordinal numbers. If !!O_1, O_2, O_3, \dots!! is any family of transitive sets, then their union, the set that contains everything that is in any of them, is an ordinal also.

When the family has a largest element !!O_{\rm max}!!, (typically because it’s a finite family) then the union is not anything new, it’s just !!O_{\rm max}!! again. For example !!1\cup 3\cup 53 = 53!!. But if the family of transitive sets has no largest element, we do get something new. In particular, the union

$$ \omega = 0\cup 1\cup 2\cup\dots $$

is an ordinal number.

By constructing the numbers as transitive sets, we got what we wanted: the finite ordinals behave just like numbers. But if we also consider infinite ordinals, we get infinite numbers like !!\omega!! that behave, in some ways, like bigger siblings of the numbers. !!\omega!! participates very nicely in less-than comparisons and minimum and maximum operations, and somewhat nicely in addition and multiplication.

!!\omega!! is an ordinal number but not a familiar one. Under our definition of !!\lt!! as a synonym for !!\in!!, every finite number !!n!! is less than !!\omega!!; there's no familiar number that behaves that way. It’s different from finite numbers in another way also: except for !!0!!, each finite number is a successor of some other finite number and so has a predecessor, whereas !!\omega!! is not a successor of anything and has no predecessor. Ordinals like !!\omega!! that are not successors are called limit ordinals.

Every ordinal has a successor, and !!\omega!! is an ordinal set, so it has one, !!\omega \cup \{\omega\},!! usually written as !!\omega+1!!, which is the next ordinal after !!\omega!!. Then there follow !!\omega + 2, \omega+3,\dots!!, and the union of all of these is the set

$$ \{0, 1, 2, \dots, \omega, \omega+1, \omega+2,\dots\} $$

which is called !!\omega·2!!—still an ordinal.

After these come !!\omega·3, \omega·4\dots!!, and eventually !!\omega^2!!. Then after a long series of things like $$\omega^2·17 + \omega·39+117$$ comes !!\omega^3!!, then !!\omega^4, \omega^5\dots!! including an infinite ordinal for every polynomial involving !!\omega!!, and then the union of all those, !!\omega^\omega!!.

The series continues — it continues forever, we can always find a bigger transitive set — with things like

$$ \omega^{\omega^{\omega^{53}·3+11}·2+\omega·19+1}·7 + \omega^{\omega^{17}·143+53}·12 + \omega^{99938}·12712781 + \omega^{99936}·12712781 +\omega+ 2 $$

where it’s like a polynomial in !!\omega!!, except that the exponents don’t have to be finite numbers, they can be other super-polynomials in !!\omega!! whose exponents don’t have to be finite. And then, after all of these, the limit of this mind-boggling sequence, is the ordinal called

$$ \epsilon_0 $$

It’s just gotten too complicated to express with regular mathematical expressions involving !!\omega!!. It transpires that this is the smallest ordinal !!x!! satisfying the property that

$$ x = \omega^x $$

This is the thing I have finally been able to get my head around, a little.

The next article will explain how.

[Other articles in category /math] permanent link