[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