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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: