[FOM] 386:Terrifically and Extremely Long Finite Sequences
Harvey Friedman
friedman at math.ohio-state.edu
Fri Jan 1 13:18:47 EST 2010
We define what we mean by the thread of a sequence of Q tuples. We
also define the open threads.
Given an appropriate G on Q^k (Q^k union Q^k+1), there exists a
corresponding Sequence with an open thread. This will be equivalent to
1-Con(SRP) and 1-Con(HUGE). The associated growth rates are
Terrifically and Extremely long - i.e., correspond to the provably
recursive functions of SRP and HUGE.
We have also made a nice simplification in the definition of Extreme
Upper Shift Greedy Down Clique Sequence. NOW, this definition looks
only a bit more complicated than the definition of Upper Shift Greedy
Down Clique Sequence. Yet this change takes us from SRP to HUGE.
CURRENT BOILER PLATE (heating up!)
I am scheduled to give a talk at the upcoming Richard Laver conference
in Boulder. That is my target date for having solid sketches of the
greedy stuff at SRP and HUGE, and also I3/I2 (I3/I2 not discussed here).
This plan will smoke out any errors, as there are now some NONTRIVIAL
LAYERED IDEAS that need to be CAREFULLY CHECKED.
In the short run, I am tied up with finishing touches on my book
Boolean Relation Theory and Incompleteness (March 2009 version on my
website).
************************
UPPER SHIFT GREEDY CLIQUE SEQUENCES
Let G be a simple graph on Q^k. An Upper Shift Greedy Clique Sequence
for G is a nonempty sequence x[1],...,x[n] from Q^k with the following
properties.
i. x[1] is the 0 tuple in Q^k.
ii. Let 2 <= 2m <= n-1. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1]. Then
a. x[2m] <= y and (y,x[2m]) is not an edge of G.
b. If x[2m+1] is the upper shift of x[2m].
iii. {x[2],...,x[n]} is a clique in G.
UPPER SHIFT GREEDY DOWN CLIQUE SEQUENCES
Let G be a digraph on Q^k. An Upper Shift Greedy Down Clique Sequence
for G is a nonempty sequence x[1],...,x[n] from Q^k with the following
properties.
i. x[1] is the 0 vector in Q^k.
ii. Let 2 <= 2m <= n-1. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1]. Then
a. x[2m] = y, or (x[2m] < y and (y,x[2m]) is not an edge of G).
b. If x[2m+1] is the upper shift of x[2m].
iii. {x[2],...,x[n]} is a down clique in G.
EXTREME UPPER SHIFT GREEDY DOWN CLIQUE SEQUENCES
Let G be a digraph on Q^k union Q^k+1. An Extreme Upper Shift Greedy
Down Clique Sequence for G is a nonempty sequence x[1],...,x[n] from
Q^k union Q^k+1 with the following properties.
i. x[1] is the 0 vector in Q^k.
ii. Let 2 <= 2m <= n-1. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1]. Then
a. x[2m] = y, or (x[2m] < y and (y,x[2m]) is not an edge of G).
b. If x[2m] lies in [0,k]^k then x[2m+1] = (k+(1/2),x[2m]+1]).
c. If x[2m] > k lies in Q^k then x[2m+1] = x[2m]+1.
d. If x[2m] = (k+(1/2),z) lies in Q^k+1 then x[2m+1] = z-1.
iii. {x[2],...,x[n]} is a down clique in G.
INFINITE SEQUENCES
We also allow infinite sequences by replacing
2 <= 2m <= n-1
with
m >= 1.
THREADS AND OPEN THREADS
A Q tuple is a tuple from the set of rationals, Q.
Let x[1],...,x[n] be Q tuples. The thread of x[1],...,x[n] is the
subsequence u[1],...,u[r] of 1,...,n defined inductively as follows.
u[1] = 1.
Suppose u[i] has been defined. Start with the j's among {u[i],u[i]
+1,...,2^u[i] such that x[j] < x[u[i]]. Cut down to those j's where
max(x[j]) is maximum. Then set u[i+1] to be the largest of these j's.
Obviously, there may be no such starting j's, in which case u[i+1] is
undefined.
We say that the thread u[1],...,u[r] is open if and only if 2^u[r] <=
n. This means that we couldn't find any such j's when trying to
construct u[r+1].
We also allow define the thread of an infinite sequence of Q tuples.
Note that in the infinite case, the thread is open if and only if the
thread is finite.
THEOREM 1. Every simple order invariant graph on Q^k has an upper
shift greedy clique sequence of finite length with an open thread.
THEOREM 2. Every order invariant digraph on Q^k has an upper shift
greedy down clique sequence of finite length with an open thread.
THEOREM 3. Every order invariant graph on Q^k union Q^k+1 has an upper
shift greedy down clique sequence of finite length with an open thread.
THEOREM 4. Theorem 1 with infinite length.
THEOREM 5. Theorem 2 with infinite length.
THEOREM 6. Theorem 3 with infinite length.
THEOREM 7. Theorems 1,2,4,5 are provable in SRP+ but not in any
consistent fragment of SRP which proves RCA_0. Theorems 1,2 are
provably equivalent to 1-Con(SRP) over EFA. Theorems 4,5 are provably
equivalent to 2-Con(SRP) over RCA_0.
THEOREM 7. Theorems 3,6 are provable in HUGE+ but not in any
consistent fragment of HUGE which proves RCA_0. Theorem 3 are provably
equivalent to 1-Con(HUGE) over EFA. Theorem 6 is provably equivalent
to 2-Con(HUGE) over RCA_0.
We define the witness functions for Theorems 1,2,3 as follows. W(k) is
the least integer such that the Theorem holds with "finite length"
replaced by "length at most W(k)".
THEOREM 8. The witness functions for Theorems 1,2 grow faster than
the provably recursive functions of SRP. The witness function for
THeorem 3 grows faster than the provably recursive functions of HUGE.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 386th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-349 can be found at http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.
350: one dimensional set series 7/23/09 12:11AM
351: Mapping Theorems/Mahlo/Subtle 8/6/09 10:59PM
352: Mapping Theorems/simpler 8/7/09 10:06PM
353: Function Generation 1 8/9/09 12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1 8/9/09 6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2 8/10/09 6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem 8/14/09 9:31AM
357: HIGH SCHOOL Games/Update 8/20/09 10:42AM
358: clearer statements of HIGH SCHOOL Games 8/23/09 2:42AM
359: finite two person HIGH SCHOOL games 8/24/09 1:28PM
360: Finite Linear/Limited Memory Games 8/31/09 5:43PM
361: Finite Promise Games 9/2/09 7:04AM
362: Simplest Order Invariant Game 9/7/09 11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1 9/24/09 1:06PM
366: Free Reductions and Large Cardinals/polished 9/28/09 2:19PM
367: Upper Shift Fixed Points and Large Cardinals 10/4/09 2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction 10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement 10/29/09 2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09 12:14PM
371: Vector Reduction and Large Cardinals 11/21/09 1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09 5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals 12/7/09 9:17AM
374: Upper Shift Greedy Chain Games 12/12/09 5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09 2:23PM
377: The Polynomial Shift Theorem 12/25/09 2:39PM
378: Upper Shift Clique Sequences and Large Cardinals 12/25/09 2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems 12/28/09 7:06AM
381: Trigonometric Shift Theorem 12/29/09 11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals 12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09 3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences
Harvey Friedman
More information about the FOM
mailing list