In this document I attempt to build some intuition for the ordinals by constructing several concrete well-orderings of the naturals with order types up to (and including!) epsilon 0.
Ordinals are all about well-orderings. A well ordering of the naturals is an ordering -- call it <~ -- on the naturals that has no infinitely descending chains. So the reverse ordering, x <~ y iff y < x, is obviously not a well-ordering because it has the infinitely descending chain 1 ~> 2 ~> 3 ~> ....
However, the usual ordering is a well-ordering, because if you start at n, you only get at most n steps before you have to hit 0. The usual ordering is called "omega", which I denote w.
However, let's take zero out and put it at the top. So 0 is greater than all other numbers, and the other numbers use the usual ordering:
1 2 3 4 5 6 ... 0
This is also a well-ordering, but a bit more subtly. If you start at n, you only get at most n-1 steps to get to the least element 1. But if you start at 0, there is no longer a bound on how many steps it will take. But you have to choose some number less than 0 to descend to, and that number will be finite, giving a finite number of steps. We call this ordering w+1.
Ordinals are equivalence classes of well-orderings; that is, if you make an order isomorphism between the naturals and themselves with a different order, those will be represented by the same ordinal. So we are really interested in seeing the structure of what is less than what, rather than the specific numbers. But I wanted to use specific numbers to make it more "real"; what does an order of type w^2 look like, after all? And we will go far beyond w^2.
When I'm writing these down, I try to use a number of dots corresponding to the number of "levels of iteration" that I am handwaving over. This kind of breaks down when we get to w^w, so it turns into more of a suggestive intuition than something formal.
Without further ado! The simplest ordinals:
w = 0 1 2 ..
w+1 = 1 2 3 .. 0
w+w = w*2 = 0 2 4 .. 1 3 5 ..
w*2+1 = 1 3 5 .. 2 4 6 .. 0
w*3 = 0 3 6 .. 1 4 7 .. 2 5 8 ..
For w*w, we need to get a copy of w at each point in w; that is, an infinite series of infinite sequences
Let B(n) = the increasing sequence of binary numbers with n 1s.
w*w = w^2 = 0 1 2 4 8 .. 3 5 6 9 .. 7 11 13 14 ...
[ B(1) ][ B(2) ][ B(3) ]..
For w^3, we need to get a copy of w at each point in w^2. B*(S) gets the sequence for each number in S and "concatenates" them.
w^3 = 0 1 2 4 .. 3 5 6 9 .. 15 23 27 ... 7 11 13 .. 31 47 55 ... 127 191 223 .. 2047 3071 3583 ....
[ B(1) ] [ B(2) ] [ B(4) ] .. [ B(3) ] [ B(5) ] .. [ B(7) ] [ B(11) ] ...
[ B*(B(1)) ] [ B*(B(2)) ] [ B*(B(3)) ] ..
For order type w^w, we need to construct an ordering which contains w^n for each natural n. Order lexicographically by prime decomposition, comparing larger primes before smaller ones.
1 = 1
2^1 = 2
2^2 = 4
2^3 = 8
..
3^1 = 3
3^1 * 2^1 = 6
3^1 * 2^2 = 12
3^1 * 2^3 = 24
..
3^2 = 9
3^2 * 2^1 = 18
3^2 * 2^2 = 36
...
5^1 = 5
5^1 * 2^1 = 10
5^1 * 2^2 = 20
..
5^1 * 3^1 = 15
5^1 * 3^1 * 2^1 = 30
....
5^2 = 25
5^2 * 3^1 = 75
5^2 * 3^1 * 2^1 = 150
.....
7^1 = 7
......
.......
........
Note that a number is a successor if and only if it has a factor of 2. If n is the pth prime, then the order type of all numbers less than n in this ordering is w^p.
For w^w^w = w^(w^w), we still use the prime decomposition, but we compare the primes according
the w^w ordering above as opposed to the usual w ordering, by acting on their prime index.
So factors of 2 (the 1st prime) are still successors, the next limit is 3 (the 2nd prime),
the next limit is 7 (the 4th(!) prime), etc.
1 = 1
2^1 = 2 (prime 1)
2^2 = 4
..
3^1 = 3 (prime 2)
3^1 * 2^1 = 6
3^1 * 2^2 = 12
..
3^2 = 9
3^2 * 2^1 = 18
...
7^1 = 7 (prime 4)
7^1 * 2^1 = 14
..
7^1 * 3^1 = 21 [..]
7^1 * 3^2 = 63
...
7^2 = 49
.....
5^1 = 5 (prime 3)
5^1 * 2^1 = 10 [...]
5^1 * 3^1 = 15 [....]
5^1 * 7^1 = 35 [.....]
.......
13^1 = 13 (prime 6)
........
23^1 = 23 (prime 9)
.........
11^1 = 11 (prime 5)
..........
And so on, with the primes following the w^w ordering. The number 5 in this ordering has a copy of w^w below it (5 is the 3rd prime, 3 is the first limit ordinal in w^w).
We can iterate this process to get all the ordinals below epsilon 0 (all w^w^w^..^w some finite number of times), by using the previous ordering O to order the primes w^O.
We are almost to understanding epsilon 0, the proof theoretic ordinal of Peano Arithmetic (that is, the least ordinal that PA cannot prove is well-ordered). That means that the ordering we construct for epsilon 0, assuming we get there, will be beyond PA's grasp.
epsilon 0 is the least fixed point of (w^), that is, w^epsilon 0 = epsilon 0. So if we do this crazy relabeling-of-primes-and-lexicographic-ordering process using epsilon 0 as the ordering on prime indices, what we get back has the same order type as epsilon 0. That doesn't really help us construct a concrete ordering, since the numbers may be different; all we know is their order type is the same.
How shall we compute a concrete ordering for epsilon 0? It must contain all the orderings constructed above, w, w^w, w^w^w. There is a straightforward construction from this idea, that we could have used for taking limits at earlier stages (but it would give rise to less-understandable simple orderings). Prime-decompose the number, and let the exponent on the power of 2 select which of these orderings we will use on "the rest". To construct the rest, shift all the primes down by one. So for example:
84 = 2^2 * 3^1 * 7^1
2^2 means interpret from w^w^w
3^1 * 7^1 "shifted down" is 2^1 * 3^1 = 6
So 84 has the same position as 6 in w^w^w
(the successor of 3, which is the first limit ordinal, so 84 "=" w+1)
We will denote this (2,6)
And we say that first we compare on the power of 2. So 2^6 * stuff > 2^4 * stuff. It's only when they
are equal that we compare them according to that power's associated "omega tower" ordering.
(all odd numbers appear below in w ordering)
(0,1) = 2^0 = 1
(0,2) = 2^0*3^1 = 3
(0,3) = 2^0*5^1 = 5
(0,4) = 2^0*3^2 = 9
(0,5) = 2^0*7^1 = 7
..
(numbers with exactly one factor of 2 appear below in w^w ordering)
(1,1) = 2^1 = 2
(1,2) = 2^1*3^1 = 6
(1,4) = 2^1*3^2 = 18
(1,8) = 2^1*3^3 = 54
..
(1,3) = 2^1*5^1 = 10
(1,6) = 2^1*3^1*5^1 = 30
...
(1,5) = 2^1*7^1 = 14
(1,10) = 2^1*3^1*7^1 = 42
....
(numbers with exactly 2 factors of 2 appear below in w^w^w ordering)
(2,1) = 2^2 = 4
(2,2) = 2^2*3^1 = 12
(2,4) = 2^2*3^2 = 36
..
(2,3) = 2^2*5^1 = 20
(2,6) = 2^2*3^1*5^1 = 60
....
(2,7) = 2^2*11^1 = 44
.....
(numbers with 3 factors of 2 appear in w^w^w^w ordering)
...........
This is a concrete ordering of the integers with order type epsilon 0. It is computable (for fun, write a program that computes it!). You can start from any number and pick a number at random (or equivalently, according to some input) that is less than it in this ordering, and you will always eventually hit 1. HOWEVER, the axioms of Peano arithmetic are not strong enough to prove this fact; so really you will only always hit 1 if you believe in axioms stronger than PA. Real question, philosophical answer :-)