[FOM] 378: Upper Shift Clique Sequences and Large Cardinals

[Harvey Friedman]

We like the Upper Shift Clique Sequences from http://www.cs.nyu.edu/pipermail/fom/2009-December/014267.html

We improve on the terminology.

So we now restate section 8 from http://www.cs.nyu.edu/pipermail/fom/2009-December/014267.html

8. UPPER SHIFT CLIQUE SEQUENCES.

The complexity of a rational is the least n such that it is the ratio  
of two integers of magnitude at most n.

The complexity of a tuple of rationals is the maximum of the  
complexities of its terms.

We use alpha for sequences of length 1 <= n <= infinity from Q^k. We  
define alpha[i] to be the i-th term of alpha, provided 1 <= i <= n and  
i is finite.

Let G be a simple graph on Q^k and alpha be a sequence from Q^k.

An upper shift clique sequence for G,alpha is a sequence beta from Q^k  
of the same length as alpha, such that the following holds.

i. If i = 1 or x_i is a subsequence of (the concatenation of)  
alpha[1],...,alpha[i-1], then beta[i] <= alpha[i] and  
{alpha[i],beta[i]} is not an edge of G.
ii. Otherwise, beta[i] is the upper shift of beta[i-1].
iii. The set of terms of beta is a clique in G.

We say that alpha is restrained if and only if the complexity of each  
term after the initial term is at most the sum of the complexities of  
the rationals in the previous terms.

PROPOSITION 8.1. Every simple order invariant graph on Q^k with  
sequence from Q^k, has a restrained upper shift clique sequence.

PROPOSITION 8.2. Every simple order invariant graph on Q^k with finite  
sequence from Q^k, has a restrained upper shift clique sequence.

Note that Proposition 8.2 is explicitly Pi01.

THEOREM 8.3. Propositions 8.1,8.2 are provably equivalent to Con(SRP)
over RCA_0. Proposition 8.2 is provably equivalent to Con(SRP) over  
EFA (exponential function arithmetic).

A variant that leads to the same results is:

i'. If i = 1 or x_i consists of rationals that appear in  
alpha[1],...,alpha[i-1], then beta[i] <= alpha[i] and  
{alpha[i],beta[i]} is not an edge of G.
ii'. Otherwise, beta[i] is the upper shift of beta[i-1].
iii'. The set of terms of beta is a clique in G.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 378th 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

Harvey Friedman