FOM: Degenerative Growth

[Harvey Friedman]

NOTE: We are trying to find simple, basic, and compelling transformations
on geometric objects that exhibit exotic metamathematical behavior. I have
obviously started with processes corresponding to epsilon_0 and lower, as
not only preparatory, but also in the hope of presenting things that are
readily transparent, attractive and understandable to the widest possible
audience, including nonmathematicians. What remains to be seen is how much
of this transparency can be preserved as we move, as planned, to higher and
higher ordinals.

Obviously, this work is related to previous work involving "hydra games"
and "Goodstein sequences". There has also been work on relating higher
ordinals to operations on trees (Buchholz and others). It makes sense to
eventually compare the end result of what I am doing here - after it has
stabilized - with this earlier work.

In this posting I consider processes that are simpler than cloning. I
expect to return to cloning shortly.

Note that throughout this study, I have opted for looking at
transformations on objects. One can alternatively take an object, and
transform it by a process which involves counting the stages at which it is
applied. This uses the additional parameter i, where one is at the i-th
stage. One generally gets similar results that way.

######################

We now consider finite sets of disjoint polygons. The order of a polygon is
the number of its sides, which is a finite number >= 3.

VERSION 1.

Let S be a nonempty finite set of pairwise disjoint polygons. We locate any
polygon P of order >= 4 which has no polygons inside. We then insert any
finite number of polygons, side by side, inside P, where the polygons
inserted are of lower order than P.

This process continues until we cannot locate any polygon P of order >= 4
which has no polygons inside.

THEOREM 1.1. For every S, this process must terminate. This is provably
equivalent to "omega^omega is well ordered" over RCA_0.

VERSION 2.

Let S be a nonempty finite set of pairwise disjoint polygons. We locate any
polygon P of order >= 4 which has no polygons inside. We then insert
polygons, side by side, inside P, each of which are of lower order than P,
until we have exactly doubled the total number of polygons.

This process continues until we cannot locate any polygon P of order >= 4
which has no polygons inside.

THEOREM 2.1. The following are equvialent over EFA (exponential function
arithmetic).
1) For every S there exists n such that this process must terminate in at
most n steps.
2) For every single polygon there exists n such that this process must
terminate.
3) The Ackermann function exists.

How long can this process take, or how big can the end result be, as a
function of S? This grows like the Ackermann function, even if we start
with a single polygon.

In fact, let f(n) be the largest number of steps possible starting with a
polygon of order n, n >= 3.

THEOREM 2.2. f(3) = 0, f(4) = 1, f(5) = 2, f(6) = 4, f(7) = 136, f(8) >=
2^[1000] = A_3(1000), f(9) >= A_4(2^[1000]). In general, f(p) >= A(p-5) =
A(p-5,p-5), for p >= 8.

That's a big jump from a septagon to an octagon!

VERSION 3.

We use finite sequences of positive integers.

Let x be a finite sequence of positive integers. Replace any term, i >= 2,
by any finite sequence of positive integers smaller than i.

THEOREM 3.1. For any x, this process can only take place finitely many
times, ending with all 1's. This is provably equivalent, over RCA_0, to
"omega^omega is well ordered".

As in version 2, we can insist that the result of each operation doubles
the length of the sequence. Then we obtain the analogous result to Theorem
2.1. One can also develop similar estimates.

There is a convenient way to make this deterministic. Always act on the
rightmost term that is greater than 1, and again double the length of the
sequence. The same results hold for this deterministic version.

Let g(n) be the number of times the deterministic process applies starting
with the sequence <n>.

THEOREM 3.2. g(1) = 0. g(2) = 1. g(3) = 2, g(4) = 39, g(5) >= 2^[2^39] =
A_3(A_2(39)), g(6) >= A_4(g(5)). For all p >= 3, g(p) >= A(p-2) =
A(p-2,p-2).