FOM: Re: Degenerative Cloning/Deterministic Formulations

[Harvey Friedman]

In my 4:00AM 5/8/01 I wrote

>Here is a fix of the computation I gave in my 10:57AM 5/2/01 posting. Let
>me know if you spot another error.

I meant my 10:57AM 5/4/01 posting.

Also, in my 4:00AM 5/8/01 posting I wrote

>THEROEM 5. Let S be a nonempty finite set of pairwise disjoint circles. The
>largest length among the proper SDC sequences starting with S is alpha(S).
>The largest size among terms in any proper SDC starting with S is beta(S).
>The greatest number of successive proper SDC operations starting with S is
>alpha(S) - 1.

This is not quite right. The largest length among the proper SDC sequences
starting with ((())()()) is 18, whereas the preferred SDC sequences are of
length 17. However, the largest size claim is correct:

THEOREM 5'. Let S be a nonempty finite set of pairwise disjoint circles.
THe largest size among terms in any proper SDC starting with S is beta(S).
The largest length among the proper SDC sequences starting with S is at
least alpha(S). The largest number of successive proper SDC operations
starting with S is at least alpha(S) - 1.

Simiarly, I wrote

>THEOREM 6. Let S be a nonempty finite set of pairwise disjoint circles. The
>largest size among terms in any SDC sequence starting with S is beta(S).
>The largest length among the SDC sequences starting with S is alpha(S) +
>beta(S). The greatest number of successive SDC operations that can be
>applied starting with S is alpha(S) + 2^beta(S) - 1.

This should be corrected to

THEOREM 6'. Let S be a nonempty finite set of pairwise disjoint circles.
The largest size among terms in any SDC sequence starting with S is
beta(S). The largest length among the SDC sequences starting with S is at
least alpha(S) + beta(S). The largest number of successive SDC operations
that can be applied starting with S is at least alpha(S) + beta(S) - 1.

NOTE: The 2^beta(S) was a typo.

But what about the longest length of a proper SDC sequence starting with S?
How does it relate to beta(S)? I wrote

>THEOREM 2. Let S = x1 union ... union xk, where each xi has a maximum
>circle and k >= 1. Then alpha(S) = alpha(x1) + ... + alpha(xk) -k + 1 and
>beta(S) = beta(x1) + ... + beta(xk). Let S = {C} union x, where x lies
>inside C. Then alpha(S) = alpha(x) + 2^beta(x) - 1, and beta(S) =
>2^beta(x). And alpha({C}) = beta({C}} = 1.

It would have been clearer to have written

alpha(S) = alpha(x) + beta(S) - 1 >= beta(S).

But what about an upper bound for maximal length SDC sequences in terms of
beta(S)?

LEMMA 3. Let S be a finite set of pairwise disjoint circles. For any proper
SDC sequence starting with S there is a proper SDC sequence of the same
length starting with S which begins with SDC operations applied to parts of
cardinality >= 3 and ends with SDC operations applied to parts of
cardinality 2. All SDC operations applied to parts of cardinality >= 3
increase the total number of circles.

THEOREM 4. Let S be a finite set of pairwise disjoint circles. The longest
length of a proper SDC sequence starting from S lies in the interval
[beta(S),2beta(S)].

LEMMA 5. Let S be a finite set of pairwise disjoint circles. For any SDC
sequence starting with S there is an SDC sequence of the same length
starting with S which begins with proper SDC operations and ends with
improper SDC operations (i.e., that just delete a circle).

THEOREM 6. Let S be a finite set of pairwise disjoint circles. The longest
length of an SDC sequence starting from S lies in the interval
[2beta(S),3beta(S)]. (Recall that longest SDC sequences end with the empty
set).

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

We now consider a natural kind of deterministic single degenerative cloning.

It is high time that we use the terminology "finite circle system" for a
nonempty finite set of pairwise disjoint circles. We abbreviate this as
FCS.

1. SINGLE DEGENERATIVE CLONING - A DETERMINISTIC FORM.

Note that the "preferred proper SDC sequences" in 4:00AM 5/8/01 are not
fully deterministic, because of the ambiguity in the representation S = x1
union ... union xk, which is unique only up to permutations. We now give a
simple deterministic form.

Let S be a FCS. A simple part of S is a subset of S that consists of a
circle C together with one or more circles inside C, no one of which lies
in any other. C is called the principal circle of the simple part.

Note that among the principal circles of the simple parts, no one lies
within any other.

In deterministic single degenerative cloning, or DSDC, we apply SDC to
EVERY principal part. In particular, we clone each principal part and
delete a circle inside the principal circle of each principal part and its
clone.

DSDC takes place if and only if there is a principal part.

Let S be a FCS. Apply DSDC successively starting with S until we cannot
continue. Let DSDC(S) be the number of circles in the resuilting FCS.

THEOREM 1.1. Let S be a FCS. The number of elements of DSDC(S) is beta(S).
In the case of p concentric circles, p >= 1, this is 2^[p-1].

The definition of beta(S) is in the posting 4:00AM 5/8/01.

Recall from 10:57AM 5/4/01 that the statement "for all S, any sequence of
multiple degenerative cloning operations must end" is equivalent to
"epsilon_0 is well ordered" within RCA_0. The same is true of proper
multiple degenerative cloning - i.e., where one is not allowed to merely
delete a circle.

However, consider multiple degenerative cloning which is required to act
only on a simple part. What is the status of "for all S, any sequence of
multiple degenerative cloning operations applied only to simple parts must
end"?

This is equivalent to "omega^omega is well ordered" over RCA_0, which is a
lot weaker. For any specific S, this is provable in RCA_0.

2. FINITE LEVELED CIRCLE SYSTEMS.

We introduce finite leveled circle systems, FLCS. These are nonempty finite
circle systems, for any two distinct circles, either one is surrounded by
the other, or one is wholly to the right of the other. I.e., every first
coordinate of every point on one circle is less than every point on the
other circle.

This additional requirement allows us to look for the rightmost simple
part, since the principal circles of the simple parts don't surround each
other. This allows us to construct new kinds of deterministic procedures.
In this section we merely consider an obvious one which still corresponds
to beta(S).

When we perform single or multiple degenerative cloning with FLCS, we
require that we always maintain an FLCS. When we make clones of a part of
an FLCS, the clones are to be placed outside of that part, but in the
vicinity of that part.

In the case of nondeterministic degenerative cloning, clones are required
to be isomorphic copies in the sense that the surround relation is
preserved, and also the left/right order of the circles is preserved.
Placement of clones is always in the vicinity of the part being cloned, in
the obvious sense, and clones can be placed on the left or right side of
the part - some on the left, some on the right.

In the case of deterministic degenerative cloning, we sometimes need to be
specific about which circle is removed from the part and its clones.

Let S be a FLCS. In right simple single degenerative cloning, or right
simple SDC, we find the rightmost simple part, and apply SDC to it. It
obviously doesn't make any difference which circles inside the principal
circles are removed.

THEOREM 2.1. Let S be a FLCS. Let S' be the result of applying rightmost
SDC as many times as possible starting with S. The number of elements of S'
is beta(S). In the case of p concentric circles, p >= 1, this is 2^[p-1].

3. RESTRICTED MULTIPLE DEGENERATIVE CLONING - FIRST DETERMINISTIC FORM.

For this purpose, we use finite leveled circle systems, FLCS. These are
finite circle systems where the centers of the circles all lie on the x
axis.

Recall that in restricted multiple degenerative cloning in S, multiple
degenerative cloning is performed in C where the number of clones made is
such that the result S' of the entire process (after circle deletion) has
at most double the number of circles that S has.

NOTE: We will also assume from now on that all cloning is proper; i.e.,
does not simply delete a circle.

Let S be an FLCS. In rightmost simple restricted multiple degenerative
cloning, or rightmost simple RMDC, we perform RMDC to just the RIGHTMOST
simple part T of S, which in effect replaces T with many copies of the
inside of its principal circle less one inside circle. We use as many
copies as possible so long as the process results in at most double the
number of circles that are in S.

We now make some calculations for rightmost simple RMDC. Let S be an FLCS.
Apply rightmost restricted RMDC as many times as possible, resulting in S'.
We write F(S) for the number of circles in S'.

For p >= 1, write F(n) for F(S), where S is p concentric circles.

THEOREM 3.1. For all S in FLCS, F(S) exists. This fact can be proved in 2
quantifier arithmetic but not in 1 quantifier arithmetic. It is equivalent
over RCA_0 to "the Ackermann function exists".

THEOREM 3.2. Let n >= 2. Then F(n) lies in the interval
[A^[n](1),A^[n+1](1)], where A^[n](1) = AA...A1, with n A's. Here A is the
unary Ackermann function = A(n,n).

4. RESTRICTED MULTIPLE DEGENERATIVE CLONING - SECOND DETERMINISTIC FORM.

We now introduce a much more powerful deterministic procedure for FLCS.

Let S be an FLCS. A critical part of S is a part of S whose principal
circle surrounds a circle which does not surround any circle.

Look at the maximal critical parts of S; i.e., the critical parts of S
whose principal circle is not surrounded by the principal circle of any
other critical part of S. Finally, look at the RIGHTMOST maximal critical
part of S, call it S'.

We now apply RMDC to S'. We have to specify which circle is deleted from
the part and its clones. In each case, delete the RIGHTMOST circle that
surrounds no circles.

THEOREM 4.1. For all S in FLCS, there are only finitely many times that
this process can be applied. This fact is provably equivalent to the
1-consistency of PA over EFA. The number of times is an epsilon_0 recursive
function that is not <epsilon_0 recursive. The same is true for the size of
the final FLCS in the process. This behavior is illustrated by starting
with concentric circles only.