FOM: 106:Degenerative Cloning
Harvey Friedman
friedman at math.ohio-state.edu
Fri May 4 10:57:23 EDT 2001
We consider finite sets of pairwise disjoint circles in the plane. The
circles are circumferences of nondegenerate circles.
Let X be a finite set of pairwise disjoint circles. A part of X is a set
consisting of a circle C in X together with the circles in X that are
surrounded by C.
Single cloning in X occurs as follows:
a. A part Y of X is chosen.
b. A copy Y' of Y is placed to the side of Y in X.
This results in a larger finite set X' containing X of pairwise disjoint
circles.
In b, we mean that Y' is isomorphic to Y in the sense that Y' is a finite
set of pairwise disjoint circles and there is a bijection from Y onto Y'
that preserves the "surrounding" relation among circles (which is a strict
partial ordering). And also that the largest circle in Y' lies outside the
largest circle in Y, but inside any circle in X that surrounds the largest
circle in Y.
Multiple cloning in X occurs as follows:
a. A part Y of X is chosen.
b. One or more copies, Y1,Y2,...,Yn, of Y are placed, side by side, to the
side of Y in X.
Single degenerative cloning in X occurs as follows:
i. Single cloning in X occurs with some Y,Y'.
ii. One circle is removed from Y and one circle is removed from Y'.
Multiple degenerative cloning in X occurs as follows:
i. Multiple cloning in X occurs with some Y,Y1,...,Yn, n >= 1.
ii. One circle is removed from each of Y,Y1,...,Yn.
We now consider how many times degenerative cloning can occur from a given
finite set of pairwise disjoint circles. Note that degenerative cloning can
always be performed on any nonempty finite set of pairwise disjoint
circles. So successive degenerative cloning ends if and when one reaches
the empty set of circles.
THEOREM 1. It is impossible for multiple degenerative cloning to occur
infinitely many times in succession in any given finite set of pairwise
disjoint circles. The multiple degenerative cloning relation among finite
sets of pairwise disjoint circles has ordinal epsilon_0.
THEOREM 2. The largest number of times that single degenerative cloning can
occur in any given finite set of k >= 1 pairwise disjoint circles is
exactly one less than an exponential stack of 2's of height k. This maximum
is realized with k concentric circles. E.g., 1, 3, 15, 65,535,
(2^65,536)-1 for 1,2,3,4,5 concentric circles, respectively.
We can even give an exact computation of the largest number of successive
single degenerative cloning steps in a given finite set of pairwise
disjoint circles as follows.
We inductively define #(A) for any finite set A of pairwise disjoint
circles. Let B1,...,Bn be the maximal proper parts of A. Note that A is
empty if and only if n >= 0.
1. A does not have a largest circle. Define #(A) = #B1 + ... + #Bn.
3. A has a largest circle. Define #A = (2^(#B1 + ... + #Bn))-1.
THEOREM 3. Let A be a finite set of pairwise disjoint circles. The largest
number of successive single degenerative cloning steps in A is exactly
#(A).
Restrained multiple degenerative cloning in X occurs when multiple
degenerative cloning in X occurs and the resulting finite set of disjoint
circles (including the unaffected parts of X) has at most twice as many
circles as X.
THEOREM 3. For any finite set X of pairwise disjoint circles, there is a
bound on the number of times restrained multiple degenerative cloning can
occur in X. This fact cannot be proved in Peano Arithmetic. It is
equivalent over EFA (exponential function arithmetic) to the 1-consistency
of PA.
For each k, let RMDC(n) be the largest number of successive restrained
multiple degenerative cloning steps in n concentric circles.
THEOREM 4. RMDC(n) is an epsilon_0 recursive function but eventually
dominates every <epsilon_0 recursive function.
Note that RMDC(1) = 1 and RMDC(2) = 5.
To give bounds for RMDC(3), we introduce a standard form of the Ackermann
hierarchy. We define functions A_k, k >= 1.
A_1(n) = 2n. For k >= 1, A_k+1(n) = A_kA_k...A_k(1), where this is n
repeated applications of the function A_k. The unary Ackermann function is
given by A(n) = A(n,n).
Note that A_2 is base 2 exponentiation and A_3 is base 2 iterated
exponentiation.
THEOREM 5. RMDC(3) > A_4(64,000).
Recall that for RMDC(3), we start with a single circle surrounding a circle
surrounding a circle. We now see what happens starting with two copies of a
single circle surrounding a circle surrounding a circle. Let RMDC(3,3) be
the largest number of successive restrained multiple degenerative cloning
steps in this situation.
THEOREM 6. RMDC(3,3) > AA(5).
We now come to RMDC(4).
THEOREM 7. RMDC(4) > AA...A(1), where there are A(5) A's.
Lower bounds for RMDC(n) are perhaps most dramatically stated in terms of
independence results.
THEOREM 8. Let n >= 4. RMDC(n) is larger than the number of steps of any
Turing machine that can be proved to halt using at most A_3(n + 100)
symbols in n-3 quantifier induction. RMDC(n) is smaller than the number of
steps of some Turing machine that can be proved to halt using at most A_2(n
+ 100) symbols in n-2 quantifier induction.
The lower bounds in Theorems 4-8 are conveniently stated but very crude,
and can be improved considerably - especially Theorem 7.
******************************
This is the 106th 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
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
50:Enormous Integers/Number Theory 7/17/99 11:39PN
51:Enormous Integers/Plane Geometry 7/18/99 3:16PM
52:Cardinals and Cones 7/18/99 3:33PM
53:Free Sets/Reverse Math 7/19/99 2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry 8/27/99 3:01PM
57:Fixpoints/Summation/Large Cardinals 9/10/99 3:47AM
57':Restatement 9/11/99 7:06AM
58:Program A/Conjectures 9/12/99 1:03AM
59:Restricted summation:Pi-0-1 sentences 9/17/99 10:41AM
60:Program A/Results 9/17/99 1:32PM
61:Finitist proofs of conservation 9/29/99 11:52AM
62:Approximate fixed points revisited 10/11/99 1:35AM
63:Disjoint Covers/Large Cardinals 10/11/99 1:36AM
64:Finite Posets/Large Cardinals 10/11/99 1:37AM
65:Simplicity of Axioms/Conjectures 10/19/99 9:54AM
66:PA/an approach 10/21/99 8:02PM
67:Nested Min Recursion/Large Cardinals 10/25/99 8:00AM
68:Bad to Worse/Conjectures 10/28/99 10:00PM
69:Baby Real Analysis 11/1/99 6:59AM
70:Efficient Formulas and Schemes 11/1/99 1:46PM
71:Ackerman/Algebraic Geometry/1 12/10/99 1:52PM
72:New finite forms/large cardinals 12/12/99 6:11AM
73:Hilbert's program wide open? 12/20/99 8:28PM
74:Reverse arithmetic beginnings 12/22/99 8:33AM
75:Finite Reverse Mathematics 12/28/99 1:21PM
76: Finite set theories 12/28/99 1:28PM
77:Missing axiom/atonement 1/4/00 3:51PM
78:Quadratic Axioms/Literature Conjectures 1/7/00 11:51AM
79:Axioms for geometry 1/10/00 12:08PM
80.Boolean Relation Theory 3/10/00 9:41AM
81:Finite Distribution 3/13/00 1:44AM
82:Simplified Boolean Relation Theory 3/15/00 9:23AM
83:Tame Boolean Relation Theory 3/20/00 2:19AM
84:BRT/First Major Classification 3/27/00 4:04AM
85:General Framework/BRT 3/29/00 12:58AM
86:Invariant Subspace Problem/fA not= U 3/29/00 9:37AM
87:Programs in Naturalism 5/15/00 2:57AM
88:Boolean Relation Theory 6/8/00 10:40AM
89:Model Theoretic Interpretations of Set Theory 6/14/00 10:28AM
90:Two Universes 6/23/00 1:34PM
91:Counting Theorems 6/24/00 8:22PM
92:Thin Set Theorem 6/25/00 5:42AM
93:Orderings on Formulas 9/18/00 3:46AM
94:Relative Completeness 9/19/00 4:20AM
95:Boolean Relation Theory III 12/19/00 7:29PM
96:Comments on BRT 12/20/00 9:20AM
97.Classification of Set Theories 12/22/00 7:55AM
98:Model Theoretic Interpretation of Large Cardinals 3/5/01 3:08PM
99:Boolean Relation Theory IV 3/8/01 6:08PM
100:Boolean Relation Theory IV corrected 3/21/01 11:29AM
101:Turing Degrees/1 4/2/01 3:32AM
102: 102:Turing Degrees/2 4/8/01 5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01 11:10AM
104:Turing Degrees/3 4/12/01 3:19PM
105:Turing Degrees/4 4/26/01 7:44PM
More information about the FOM
mailing list