FOM: 42:Mythical Trees

[Harvey Friedman]

This is the 42nd in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
36:Adjacent Ramsey Theory  3/23/99  1:00AM
37:Adjacent Ramsey Theory/more  5:45AM  3/25/99
38:Existential Properties of Numerical Functions  3/26/99  2:21PM
39:Large Cardinals/synthesis  4/7/99  11:43AM
40:Enormous Integers in Algebraic Geometry  5/17/99 11:07AM
41:Strong Philosophical Indiscernibles  5/19/99  11:09PM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

FAVORITE SELF CONTAINED POSTINGS: 21, 25, 27, 31, 32, 34, 35', 37, 38, 39,
40, 41.

CLARIFICATION OF #41. I wrote the following:

>iii) for all phi(x) with only the free variable shown and no occurrence of IN:
>for all x,y in the extension of IN and of the same finite cardinality,
>phi(x) iff phi(y).

>iv) for all phi(x) with only the free variable shown and no occurrence of
>IN: for all x,y in the extension of IN and of the same at most
>countable cardinality, phi(x) iff phi(y).

>The additional axiom is: Let F:A into x, where A is a proper class and x
>is a set. There exists a proper class B contained in A such that for all n
>>= 2, F is constant on the n element subsets of B.

>Let F:A into x, where A is a proper class and x is a set. There exists a
>proper class B contained in A such that for F agrees at any two at most
>countable subsets of B of the same cardinality.

Insert "included" after x,y in the first two. In the last two, Replace "Let
F:A into x" by "Let F be a class function from the class of all subsets of
A into x".
********************

Here is a combinatorial high school problem. It is closely related to what is
needed for the lower bounds in the recent work on decreasing sequences of
algebraic sets.

There was a Mythical Tree which simply got too big to survive. It wasn't
that it grew very tall. In fact, a squirrel could get to any top of the
tree from its root using exactly four branch segments.

The tree had a very peculiar growth pattern.

In its first growth stage, the root grew two branch segments, forming two
treetops. In its second growth stage, one of the
two treetops grew three branch segments. Now there was a total of four treetops.
In its third growth stage, one of the four treetops grew four branch
segments. Now
there was a total of seven treetops. Etcetera.

What is the largest number of branch segments that could have been created
in the Mythical Tree's final growth stage? Remember, a squirrel could get
to any treetop from the root using exactly four branch segments.

ANSWER: 21 trillion 990 billion 232 million 555 thousand 518. This is
exactly the largest possible number of branch segments created in the final
growth stage.

The story of the Mythical Tree got wilder as time went on. In a second
version of the story, the root grew three branch segments instead of just
two. Then a treetop grew four branch segments. Etcetera.

What is the largest number of branch segments that could have been created
in the Mythical Tree's final growth stage? Remember, a squirrel could get
to any treetop from the root using exactly four branch segments.
ANSWER: More than 2^2^95.

For many years, every time the story was told the root was said to have
grown one more branch segment at the
beginning, and just as in the original story, at each growth stage one of
the treetops grew one more branch segment than at the preceding stage. It
was still
required that a squirrel could get to any top of the tree from its root
using exactly four branch segments. And every time the largest number of
possible branch segments created in the final growth stage was at least
exponentially greater than it was previously.

Finally, the story was told with a squirrel getting up to any top of the
tree from the root using exactly five branch segmentss. Yet the root grew
only 2 branch segments as in the original story. Then how many branch
segments could the Mythical Tree have grown in its final growth stage?

ANSWER: Greater than an exponential stack of 2's of height 2^2^95.
********************

Now for the theory. We obtain exact recursion equations for the answer.

**********
NOTE: Randy Dougherty observed that this problem can be embedded in the
Hercules/Hydra game.
**********

We consider finite rooted trees. The valence of a vertex is the number of
its children (immediate successors). The leaves are the vertices of valence
0. The valence of a tree is the largest valence of its vertices.

Let k,n >= 1. We define a k,n-construction to be a certain kind of
sequential construction of a tree. Formally, a k,n-construction is a
sequence of trees, T_1,...,T_r, r >= 1, where

1) T_1 is the tree consisting of a root and n immediate successors;
2) each T_i+1 is obtained from T_i by creating n+i immediate successors of
some leaf of T_i;
3) T_r has height at most k.

We have to consider slightly more general constructions. Let k,n,m >= 1. A
k,n,m-construction is a sequence of trees, T_1,...,T_r, r >= 1, where

1) T_1 is the tree consisting of a root and n children;
2) each T_i+1 is obtained from T_i by creating n+i children of some leaf of
T_i;
3) T_r has height at most k;
4) for all i >= 2, in T_i at most m children of the root have valence > 0.

We refer to 2) as "visiting" that leaf.

We are interested in the largest possible valence of the last term in any
k,n-construction, and more generally, in any k,n,m-construction. Note that
the k,n-constructions are exactly the k,n,n-constructions. In fact, if m >=
n then the k,n-constructions are exactly the k,n,m-constructions.

We define the following function V:Z+^3 into Z+.

V(1,n,m) = n. V(k+1,n,1) = V(k,n+1,n+1). V(k+1,n,m+1) =
V(k,V(k+1,n,m)+1,V(k+1,n,m)+1).

An optimal k,n,m-construction is a k,n,m-construction of the greatest
possible valence. This is the same as requiring that it be of the longest
possible length or the greatest number of vertices.

A normal k,n,m-construction is a k,n,m-construction where once an immediate
successor of the root is visited, the construction stays above that
immediate successor for zero or more steps until it leaves, and then never
returns.

LEMMA 1. Let k,n,m >= 1. Every optimal k+1,n,m-construction is normal.

Proof: Fix k >= 1. We prove the following by induction on m >= 1. For all n
>= m, every optimal k+1,n,m-construction is normal.

This is obvious for m = 1. Assume m >= 2 and this is true below m. Let C be
an optimal k,n,m-construction. We can assume that m <= n.

Without loss of generality we assume that we have ordered the children of
the root in the order in which C visits them (only the first m such are
visited). We have to show that after creating n children of the root, C
first works above the first of these, then above the second of these,
etcetera, and never backtracks.

Let j be the largest such that some initial segment of C is an optimal
k+1,n,j-construction. We can assume that 0 <= j <= m-1. We now look at the
tail of C that starts just after the completion of this initial segment.
Then this tail is an optimal k+1,t,m-j-construction, for some t. If j >= 1
then by induction hypothesis the initial segment and the tail are both
normal, in which case C is normal. Hence we can assume that j = 0.

Let C_1 be the longest initial segment of C that is a k+1,n,1-construction.
In C_1 the first immediate successor of the root is visited, but C_1 is not
an optimal k+1,n,1-construction.

We now show that C itself is not an optimal k+1,n,m-construction. We modify
C to obtain a new k+1,n,m-construction which is longer than C.

Let t be such that C creates t children of the 2nd child of the root. Let
C* start off with an optimal k+1,n,1-construction, whose length is t' >= t,
by nonoptimality. Then C* continues by creating t'+1 > t children of the
second child of the root. At this point we are longer than C. However, we
cannot blindly continue by imitating C since C may revisit above the first
child of the root, and C* doesn't have any room left there. However, if we
were to imitate C then we would use only the first t of the t' children of
the 2nd child of the root. Let x be the last of these t' children of the
2nd child of the root. At this point create a bloated copy of C_1 where x
takes the place of the first child of the root. We can now continue by
imitating C using this bloated copy of C_1 when C does its revisting above
the first child of the root. QED

Let C be a normal k+1,n,m-construction, m <= n. We can write C =
C_1,...,C_m, where C_i is the portion of C that starts with the visitation
of the i-th immediate successor of the root that is visited, and ends just
before C visits a vertex that is not at or above that immediate successor
of the root. (Strictly speaking, before C_1 comes the visitation of the
root, when n immediate successors of the root are created). Each C_i is a
k,t_i,t_i-construction, for some unique t_1 < ... < t_m.

LEMMA 2. Let C be an optimal k+1,n,m-construction, m <= n. The components
C_1,...,C_m are, respectively, optimal k,t_i,t_i-constructions.

Proof: Let C,k,n,m be as given. Suppose i is least such that C_i is not an
optimal k,t_i,t_i-construction. Then we could replace C_i by an optimal
k,t_i,t_i-construction. We would have to create more vertices in
C_i+1,...,C_m, but they do not interfere with the imitation of
C_i+1,...,C_m. Hence we obtain a k+1,n,m-construction of greater valence.
QED

THEOREM 3. Let k,n,m >= 1 and m <= n. Every optimal k,n,m-construction has
valence V(k,n,m).

Proof: First suppose k = 1. Obviously every optimal 1,n,m-construction has
valence n+m = V(1,n,m). Now suppose this is true for k >= 1. We wish to
prove this for k+1. Let 1 <= m <= n and C be an optimal
k+1,n,m-construction.

Let C have components C_1,...,C_m. Each C_i is an optimal k,t_i,t_i
construction. Hence the valence of each C_i is V(k,t_i,t_i). Also, clearly
t_1 = n+1 and t_i+1 = V(k,t_i,t_i)+1. We claim that each t_i+1 =
V(k+1,n,i)+1. To see this, first note that t_2 = V(k,t_1,t_1)+1 =
V(k,n+1,n+1)+1 = V(k+1,n,1)+1. Suppose t_j+1 = V(k+1,n,j+1)+1. Then t_j+2 =
V(k,V(k+1,n,j+1)+1,V(k+1,n,j+1))+1 = V(k+1,n,j+1)+1 as required. Hence the
valence of C, which is the same as the valence of C_m, is V(k,t_m,t_m) =
V(k,V(k+1,n,m)+1,V(k+1,n,m)+1) = V(k+1,n,m) as required. QED

The following is of independent interest.

THEOREM 4. Let k,n,m >= 1 and m <= n. The optimal k,n,m-constructions are
exactly the k,n,m-constructions in which at each stage, a vertex of highest
height is visited.

Proof: By induction on k. The case k = 1 is trivial.

Let C be an optimal k+1,n,m-construction with components C_1,...,C_m. By
the induction hypothesis, each C_i is of the required form. Hence C is of
the required form.

Let C be a k+1,n,m-construction whwere, at each stage, a vertex of highest
height is visited. C starts off by visiting the root. It then visits a
child, v_1, of the root. It must remain above v_1 until this is no longer
possible. Then it visits another child, v_2, of the root. Again, it must
remain above v_2 until this is no longer possible. This continues for m
stages, creating components C_1,...,C_m which are k,t_i,t_i-constructions,
where t_1 < ... < t_m.

By induction hypothesis, each C_i is an optimal k,t_i,t_i-construction. By
Theorem 3, each C_i has valence V(k,t_i,t_i). We then argue as in the proof
of Theorem 3 that the valence of C, which is the same as the valence of
C_m, is V(k+1,n,m). Hence C is optimal. QED

COROLLARY 5. V(1,n,m) = n. V(2,n,m) = n+m. V(3,n,m) = 2^m(n+2)-2. V(4,2,1)
= V(3,3,3) = 8(5)-2 = 38. V(4,2,2) = V(3,V(4,2,1)+1,V(4,2,1)+1) =
V(3,39,39) = 2^39(40)-2 = 549755813888(40)-2 = 21990232555520-2 = 21
trillion 990 billion 232 million 555 thousand 518. V(4,3,1) = V(3,4,4) =
16(6)-2 = 94. V(4,3,2) = V(3,V(4,3,1)+1,V(4,3,1)+1) = V(3,95,95) =
2^95(97)-2. V(4,3,3) = V(3,V(4,3,2)+1,V(4,3,2)+1) =
V(3,2^95(97)-1,2^95(97)-1) > 2^2^95. V(4,4,4) > 2^2^2^95. V(5,2,1) =
V(4,3,3) > 2^2^95. V(5,2,2) = V(4,V(5,2,1)+1,V(5,2,1)+1) >
V(4,2^2^95+1,2^2^95+1) > an exponential stack of 2^2^95 2's.

Proof: We will be content to verify only the second and third claims by
induction. V(2,n,1) = V(1,n+1,n+1) = n+1. V(2,n,m+1) =
V(1,V(1,n,m)+1,V(1,n,m)+1)) = V(1,n,m)+1 = n+m+1.

V(3,n,1) = V(2,n+1,n+1) = 2n+2. V(3,n,m+1) = V(2,V(3,n,m)+1,V(3,n,m)+1) =
2V(3,n,m)+2 = 2(2^m(n+2)-2)+2 = 2^m+1(n+2)-4+2 = 2^m+1(n+2)-2. QED

A standard presentation of the Ackerman hierarchy is as follows. A:Z+^2
into Z+. A(1,n) = 2n. A(k+1,1) = A(k,1). A(k+1,n+1) = A(k,A(k+1,n)). A_k(n)
= A(k,n).
Thus A_1 is doubling, A_2 is base 2 exponentiation, A_3 is base 2 iterated
exponentiation.

THEOREM 6. For all k,n >= 1, A(k,n) <= V(k+1,n,n) <= A(k,5n).

Proof: This is obviously true for k = 1,2 since V(2,n,n) = A(1,n) and
V(3,n,n) = 2^n(n+2)-2 <= 2^2n = A(2,2n). Assume true for k >= 2. We show
that it is true for k+1.

It is useful to define the functions V_k(n) = V(k,n,n). Then V_k+1(n) is
computed by starting with n and applying the function V_k(x+1) exactly n
times. And A_k+1(n) is computed by starting with 1 and applying the
function A_k(x) exactly n times.

By induction hypothesis, V_k+1(x+1) <= A_k(5x+5). Hence V_k+2(n) is at most
the result of starting with n and applying the function A_k(5x+5) exactly n
times. This is at most the result of starting with n and applying the
function A_k(x) exactly 4n times, since 5x+5 <= 2^2^2^x. which is at most
the result of starting with 1 and applying the function A_k(x) exactly 5n
times, which is A_k+1(5n) as required. We have made no attempt to optimize
the expression 5n. QED