Posted by: holdenlee | July 16, 2010

## 2 Problems on Ordinal Numbers

From Josh Nichols-Barrer’s Algebra 3.5 class at AwesomeMath.

1. Let $n$ be a positive integer. Express $n$ in base 2, expressing each exponent in base 2 and so on. For example, if $n=140$, write

$n=2^{2^2+2+1}+2^{2+1}+2^2.$

Now replace each instance of $2$ with $3$ and subtract 1 from the result, expressing what remains in base 3 similarly:

$3^{3^3+3+1}+3^{3+1}+2\cdot 3^2+2\cdot 3^1+2$

Increment the base and subtract 1 each step:

$4^{4^4+4+1}+4^{4+1}+2\cdot 4^2+2\cdot 4^1+1.$

Prove that the sequence eventually reaches 0.

2. The Tree of Life is a rooted tree with many branches. Michael the Lumberjack would like to chop it down, but he can only cut a branch at a time, at a node where it joins a lower branch or at the root. (He cuts just above the node.) However, every time the Tree loses a branch at a node not the root, any finite number of new branches grow from the next node down, each identical to what is left of the branch where Michael cut. Prove that no matter what plan Michael has or how many branches the Tree grows, Michael can finish the job.

Solutions: The idea is to associate each state in the problem with an ordinal number, show that it is decreasing, and use the fact that the ordinals are well-ordered; that is, there is no infinite decreasing sequence of ordinal numbers.

1. When the number is written in base $n$, replace every occurence of $n$ by $\omega$ to get an ordinal number. For example, associate $n=2^{2^2+2+1}+2^{2+1}+2^2$ with $\omega^{\omega^{\omega}+\omega+1}+\omega^{\omega+1}+\omega^{\omega}$. When we subtract 1 from the $b'$-ary expansion, we either delete an 1 in the expansion, or replace $b^t$ with $\sum_{i=0}^{t-1} (b'-1)b^{t-1}$; replacing $b$ by $\omega$ we get that the corresponding ordinal number decreases.

2. Label rooted trees with ordinal numbers recursively as follows: Label a point 0, and if a tree has $n$ edges coming out of its root, where the trees obtained by deleting those edges are labeled $a_1,\ldots ,a_n$, then label the original tree $\sum_{i=1}^n \omega^{a_i}$. When Michael cuts a branch, the ordinal number corresponding to the subtree rooted 1 node below has one term that changes from $\omega^{\alpha}$ to $k \omega^{\beta}$ where $\beta<\alpha$ because Michael cut a branch off, and with a nonnegative integer $k$ in front because there are now $k$ copies of the branch. Thus the ordinal number corresponding to the whole tree decreases. Again we get a decreasing sequence of ordinal numbers.