Content-Type: text/shitpost

I was going to write something about the ordinal number !!ω^ω!!, but then I got bogged down in a lot of blather about well-orders and smaller ordinal numbers. I asked folks in Recurse Center if this article was interesting and they very genrly and constructively said it was not. So I am publishing it here.

Caveat lector

Well-founded ordering is a fundamental idea in set theory, the basis of all inductive arguments. The idea of a set with a well-founded ordering is that if you start somewhere, and the moved to an element of the set that is “smaller” in the ordering, and then do it again and again, you must eventually get stuck at an element for which there is no “smaller” element.

The prototypical example of a well-founded ordering is the ordinary !! \lt !! relation on the natural numbers. You can't keep passing from one natural number to a smaller one without eventually getting stuck at !!0!!. And the prototypical example of a not well-founded ordering is the ordinary !! \lt !! relation on the integers, because you can move to !!-1!!, then !!-2!!, then !!-3!!, and you never do get stuck. Or for a slightmy more subtle non-example, the ordinary !!\lt!! relation on the positive rational numbers, whre you can go !!1, \frac12, \frac13, \frac14,\ldots!! and you still never do get stuck.

To see the relationship with inductive arguments, think of induction as working this way. In an inductive argument you say well, if the claim were false for some large example it would also be false for a smaller example, then also for an even smaller one, and you could keep going like that until you got down to a trivial example, but the claim is easy to verify for the trivial examples, so it must be true for the large ones also. To work, the notion of "smaller" has to guarantee to end at a trivial example after a finite number of steps, and that's what "well-founded" gets you.

There are lots of examples of well-founded orders of the natural numbers that aren't the usual !!\lt !! relation. The simplest nonstandard one is:

1. Exactly the same as the usual order, except…

2. Instead of !!3!! being smallest, Every number is considered to be less than !!3!!.

$$ 0\prec 1\prec 2 \prec 4 \prec 5 \prec \ldots \prec 3 $$

We use the symbol !!\prec!! instead of !!\lt!! to remind ourselves that this is something like but not the same as the usual less-than relation. It doesn't have to be !!3!! that is out of line, it doesn't matter. I just picked !!3!! to emphasize that the choice was arbitrary.

This is not just a simple renaming of the natural numbers, because in the usual ordering there is no largest number, and here there is a largest number, namely !!3!!. But the order is still well-founded. Even if you start at !!3!!, the first time you move to a smaller number, it's some other finite number and at that point you can be sure that the process can't go on forever. You can move from !!3!! down to !!1000007!!, but from there you have at most !!1000007!! moves before you are certain to get stuck at !!0!!.

The way I presented this ordering is a little bit odd to set theorists, because set theorists have a standard set of names and notations for different well-founded orders. The ordinary natural numbers one is called !!\omega!!. The one above, which is like !!\omega!! except it has one extra element on the end, larger than the others, is called !!\omega + 1!!. Instead of describing it the way I did, with !!3!! pulled out of line and stuck at the end, set theorists usually call that largest element “!!\omega!!” and write it like this:

$$ 0\prec 1\prec 2 \prec 3 \prec 4 \prec 5 \prec \ldots \prec \omega $$

It's the same thing, just with slightly less silly names. But it's important to remember that something like !!\omega + 1!! describes a perfectly well-defined ordering relation that could be put on the ordinary natural numbers, not the usual ordering but no less legitimate.

Of course you can add more than one big element on the right-hand end; those orderings are !!\omega+1, \omega+2,!! and so on.

You can even add an infinite number of elements on the right. Suppose we take two copies of the natural numbers, one painted blue and one painted green. Then we define the following order:

1. If !!n!! and !!m!! are the same color, then !!n!! is smaller than !!m!! in the usual way, just if !!n\lt m!! as ordinary unpainted numbers
2. If they are different colors then one is blue and one is green, and the blue one is smaller

Now we have this ordering:

$$ \underbrace{ \color{darkblue}{0} \prec \color{darkblue}{1} \prec \color{darkblue}{2} \prec \color{darkblue}{3} \prec \ldots }_{\text{blue numbers}} \prec \underbrace{ \color{darkgreen}{0} \prec \color{darkgreen}{1} \prec \color{darkgreen}{2} \prec \color{darkgreen}{3} \prec \ldots }_{\text{green numbers}} $$

If we don't like using paint, we could phrase it like this:

1. If !!n!! and !!m!! are the same parity, then !!n!! is smaller than !!m!! in the usual way, just if !!n\lt m!! as ordinary unpainted numbers
2. If they are different parities then one is even and one is odd, and the even one is smaller

$$ \underbrace{ 0 \prec 2 \prec 4 \prec 6 \prec\ldots }_{\text{even numbers}} \prec \underbrace{ 1 \prec 3 \prec 5 \prec 7 \prec\ldots }_{\text{odd numbers}} $$

The standard name for this is !!\omega + \omega!! or !!2\cdot\omega !! and the elements are usually written like this:

$$ 0 \prec 1 \prec 2 \prec 3 \prec\ldots \prec \omega \prec \omega+1 \prec \omega+2 \prec\ldots $$

I like to think of !!\omega!! as a game in which there is a track of squares extending forever to the right. The leftmost square is labeled !!0!!. One one square there is a penny. Two players play a game in which they take turns moving the penny to the right some number of squares. If a player moves the penny to !!0!!, they lose. Must the game come to an end, or could it go on forever? Clearly it must come to an end, even though the track itself is infinite. If the penny starts on square 1000007, the game can't possibly last more than 1000007 moves. (As a game this is no fun at all, since the first player can immediately move the penny to square !!1!!, but I'm only interested in whether the game will end.)

!!\omega+1!! is the game where, instead of starting somewhere on the track, the penny starts in player 1's pocket, and their first move is to take it out and place it on one of the squares of the track. Again the game must come to an end, although unlike in the previous case we can't say ahead of time how long it will take. If we say “no more than 1000007 moves”, player 1 can belie us by taking out the penny and placing it on square 2061982 instead. But what we can say at the beginning of the game is “I can't tell you now how long the game will take, but I will once Player 1 makes her first move.”

For !!2\cdot\omega!! I like to think of two tracks, one above the other. Now a player has two kinds of move:

1. Move the penny to a square farther left in the same track, or
2. If the penny is in the upper track, move it to any square in the lower track

Again Player 1 begins the game by taking the penny from her pocket and placing it on any square.

If the penny is on square 1000007 of the top track, I can't tell you how long the game will take to end. But I can say “I will tell you how much longer the game will take, not right now but after no more than 1000008 moves from now.” Because after 1000007 moves, either someone will have moved the penny to the lower track, and I can tell how long the rest of the game will take, or the penny will have moved left 1000007 times and be on the leftmost square of the top track and the next move must take it to the lower track.

And if the game hasn't started yet, I can't yet tell you when I will be able to say how much longer the game will take. But I will be able to do that once Player 1 has made her first move and put the penny on the board.

This reminds me of an anecdote I once heard from another programmer. He told me his boss had come to him to ask him if he could do a certain task; he had replied that he could, and the boss had asked him how long he thought it would take.

He said “I don't know.”

His boss, being a reasonable woman, asked him when he would be able to tell her.

He said “I don't know.”

The boss, having dealt with this guy before, did not lose her temper. Instead, she asked “How long will it take you to figure that out?”

“Not more than two days,” he said at once.

“Okay, just to make sure there is no miscommunication, are you telling me that in two days you will be able to tell me how long it will take you to estimate how long the task will take?”

“That's right.”

And they parted amicably, both parties satsified, at least for the time being. Communication between management and engineering doesn't always turn out so well!

In that programmer's game, there were three tracks, and the penny was on the second space on the topmost track. He was playing the game !!2\cdot\omega + 1!!. At most two days later, the penny had moved to !!\omega + n!!, where !!n!! was how long it would take him produce his estimate of the project timeline.

It's easy to add more tracks. Let's add an infinite stack of tracks, one atop the other. Now when Player 1 takes the penny from her pocket she can put it on any space on any track. Again, a legal move is to move the penny left on the same track, or to any space on any lower track.

How long before you can say how long the game ends? Human language is not well-suited to this guarantee.

Even once Player 1 was made her first move, I may not be able to tell you how long the game will take,
and I also may not be able to tell you how long before I can tell you how long the game will take.

And I may not be able to tell you how long before I can tell you how long before I can tell you how long the game will take.

And I can't even tell you now how many times I will have to stack up “I may not be able to tell you”.

BUT once Player 1 has made her first move, I will be able to tell you how many times I have to stack it up.

Is the game really guaranteed to end? Yes, it really is. After Player 1's first move, the penny is on some square of some track, say square !!n!! of track !!m!!. After at most !!n+1!! moves, the track number !!m!! must decrease. And then there can only be a finite number of moves before it decreases again. And it can decrease at most !!m!! times before the penny is on the bottom track, and then the game must end after a bounded number of moves.

This ordering is called !!\omega^2!!. A penny on square !!n!! of track !!m!! is said to be at !!m·\omega + n!!. If we want to think about a way to order the natural numbers with order type !!ω^2!!, we can do it like this:

Every number larger than !!0!! can be put in the form !!2^i·j!! where !!j!! is odd. For example, !!200 = 2^3·25!! and !!37 = 2^0·37!!.

1. !!0!!, as usual, is smaller than every other number.
2. Otherwise, the numbers can be thought of as !!n = 2^i·j!! and !!n' = 2^{i'}·j'!!. Consider !!n\prec n'!!:
   1. if !!i \lt i', or
   2. if !!i = i'!!, and !!j\lt j'!!

Written out explicitly, the ordering looks like this:

$$\begin{array}{l} 0 \prec \\ 2^0\cdot 1 \prec 2^0·3 \prec 2^0·5\prec 2^0·7 \prec\ldots \\ 2^1\cdot 1 \prec 2^1·3 \prec 2^1·5\prec 2^1·7 \prec\ldots \\ 2^2\cdot 1 \prec 2^2·3 \ldots \end{array} $$

or if you prefer

$$\begin{array}{l} 0 \\ \prec 1 \prec 3 \prec 5 \prec 7 \prec \ldots \\ \prec 2 \prec 6 \prec 12 \prec 24 \prec \ldots \\ \prec 4 \prec 12 \prec 20 \prec 28 \prec \ldots \end{array} $$

Well, none of that was actually what I planned to write about, but I am going to stop here and continue tomorrow.