A pocket dictionary of infinities - Before we get ourselves into the blow I'm supposed to brag about how ridiculously far beyond omega the following ordinals occur. You do remember "w", the foremost and smallest ordinal infinity, don't you?
This is a repost of an article I had published on g+ in June 2016. Here's the archive version, which includes most of the comments.
Yeah. Stunningly exasperating. So grossly far out it's utterly silly. And yet, a perfectly valid gem of fascinating mathematical reasoning from yestercentury.
Of course, we'll only be looking at normal functions: continuous, strictly increasing functions from the ordinals to the ordinals. Let's bring it on!
In 1908, Oswald Veblen proved the fixpoint lemma, that all normal functions have fixpoints, and then he went on and gave an example, now well known as his hierarchy of ordinal functions phi.
A bit about the celebrated geometer from Iowa himself: https://en.wikipedia.org/wiki/Oswald_Veblen
A fixed point seems to be a strange notion for a strictly increasing function, doesn't it? It still makes me cringe, but however I look at it, it really fits the bill:
The Knaster–Tarski theorem states that any order-preserving function on a complete lattice has a fixed point, and indeed a smallest fixed point.
And another interesting bit I wouldn't want to keep from you:
[...] in light of the Church–Turing thesis their intuitive meaning is the same: a recursive function can be described as the least fixed point of a certain functional, mapping functions to functions.
Of all the normal functions, phi is the one which has such a fixpoint for the power-over-omega function like so:
phi(a) = w^phi(a)
Starting with this function, Veblen's hierarchy concludes an unending list of functions with ever more parameters. Know that leading zeros can be removed, the longer functions don't contain the shorter ones, so they all give distinct fixpoints! Let's name a few:
phi(0) = 1 phi(a) = w^a phi(1,a) = epsilon_a phi(1,a,0) = kappa_a phi(1,0,a) = Gamma_a phi(1,0,0,0) = Ackermann ordinal
...and so on. We always get these loads upon loads of fixpoints! Look again! Since phi's arguments are also ordinals, there are many more things we can name than what might appear at first!
Let me help. We might start by provisionally ordering the phi functions by number of arguments first, and then lexicographically. That would mean whatever we put into a or b, the next phi should dominate all that:
phi(a,b) < phi(1,0,0)
So phi(1,0,0) is also larger than these:
phi(w) < phi(1,0) < phi(1,w) < phi(w,phi(w)) < phi(phi(w),w) < phi(1,0,0)
What's going on?
Of course, any of the ordinals we can get using a chosen notation, are again available to define larger ones within that notation. That is what it means, that the function phi, making up our notation, is closed.
Only after we have exhausted all possibilities we need to make another jump. Remember "the end of the epsilons"? In a previous post about counting sheep, I had alluded to nesting epsilons like so:
and called that Feferman-Schütte's Gamma_0. But meh, I was wrong. I had forgotten to ask: How many e's?
Well, we could have an omega's worth of nested epsilons. Hello kappa_1, nice to meet you! Or ask for the full menu and get an e_0's worth of e's nested within e's. In other words, an omega of kappas nested in kappas! That is better, because we only have to overcome a tower of symbols of height omega at a time.
Puzzle 1: Does our kappa have anything to do with the first uncountable regular cardinal also named kappa?
And phi(0,phi(1,0,0))? Is it smaller than phi(1,0,0) or what? The answer is no, that would be too much. Lexicographical order isn't quite sufficient, and maybe just the wrong tool to apply to exploding alphabets.
To see more clearly, let's turn to Herman Ruge Jervell 's elegant tree notation! He renders n-argument functions as nodes with n branches, where each arm accepts any ordinal you want as an argument to hold up.
A tree! More precisely, the syntax tree of a nested expression. Of a fixpoint cascade similar to phi's. Veblen's functions start a bit late, so phi can't express addition or multiplication. That's okay, we're expected to write a sum of multiples of phis with different arguments to label all ordinals.
However, if we start a bit earlier, we get the same overall cascade, but without the need to have two separate notations for building all ordinals! With it, we can label all ordinals below the small Veblen with finite trees! Each branching node corresponds to an invocation of these (you know, rather large) fixpoints labeled by a phi.
I'll make it a bit more explicit for you: A single node corresponds to zero, a single edge to one:
. = 0 and | = 1
Every tree has finite height, a root, and attaching that root to a linear chain (a unary tree) is called adding:
a + n = a n
This one is called omega, and dominates all unary trees:
w = \/
It has two parameters, the first corresponds to multiplication, the second to powers of omega:
a b \/ = (w^w^b)·a
I just described a way to construct all binary trees. Those are dominated by this simplest possible ternary tree, put it anywhere into a binary tree (even the empty one) and you get something bigger! We know that that must be e_0:
\|/ = e_0
The first parameter corresponds to putting something into e's index. We don't need to model any of the earlier operations here. If we want those, we can "add" them below.
a \|/ = e_a
The second parameter gives us those ominous kappas! They correspond to an omega's amount of e's in its index.
| \|/ = e_e_e_e... = k_1 b \|/ = k_b
These trees are always finite in height, and anytime you need one an omega high, you add a slightly bigger branching shape. So, only when we really can't get any further we finally need another jump... to Gamma_0:
| \|/ = Gamma_0
It seems peculiar that this first one isn't called Gamma_1 instead. I have no idea why. Look at the funny shape we're allowed to sprinkle all over a tree before it reaches Gamma_0:
a b . \|/
So in the end, if a tree contains an n-shape, then it is larger than any tree containing only smaller ones. And therefore, indeed:
phi(1,0) < phi(0,phi(1,0))
Since the upper parameters escalate quickly, a tree with a larger node at its root cannot have any smaller components, like for example a lonely trailing +1, in Cantor normal form.
Always remember, ordinal arithmetic isn't commutative:
x \/ \/ \/ | * \/ = | = (w+1)w = w^2 + 1 \/ x \/ | \/ * | = \/ = w(w+1) = w^2 + w
Because "trees are everywhere" we might associate ordinals to many other kinds of things: https://plus.google.com/+RefurioAnachro/posts/MRPFF5oMRHZ
For example, that's a tree, right?:
/\ /\/ \ / \
Puzzle 2: w^w contains elements of this "polynomial" form:
w^i*a_i + ... + w*a_1 + a_0
now, doesn't w^w (or some slightly larger ordinal) also contain all infinite, w-long polynomials? Wouldn't that imply a model for the reals?
Puzzle 3: How are these trees related to recursion schemes? I've already promised you another functional attack, but you don't need to wait for me... For every tree we should be able to find a function calling itself in a particular manner corresponding to that tree. How?
Special thanks to +John Baez for kindly getting me to read these nice papers by Herman Ruge Jervell:
"Finite Trees as Ordinals" , "Constructing Ordinals" , and "Ordinal Notations" .