I have another blog that doesn't suck. Archive:
Comments disabled 
I was going to write something about the ordinal number !!ω^ω!!, but then I got bogged down in a lot of blather about wellorders 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 Wellfounded ordering is a fundamental idea in set theory, the basis of all inductive arguments. The idea of a set with a wellfounded 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 wellfounded 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 wellfounded 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 nonexample, 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 "wellfounded" gets you. There are lots of examples of wellfounded orders of the natural numbers that aren't the usual !!\lt !! relation. The simplest nonstandard one is:
$$ 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 lessthan 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 wellfounded. 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 wellfounded 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 welldefined 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 righthand 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:
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:
$$ \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:
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.
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 wellsuited to this guarantee.
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:
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.
