[FOM] 458: Sequential Construction for Large Cardinals

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

We restate the Sequential Construction in section 5 of http://www.cs.nyu.edu/pipermail/fom/2011-May/015381.html

It is now much clearer, and also (0,...,0) should have been  
(0,1,...,k-1).

Note that the Finite Greedy Clique Construction Theorem is explicitly  
Pi02, and the Estimated greedy Clique Construction Theorem is  
explicitly Pi01.

MAXIMAL CLIQUES AND LARGE CARDINALS
by
Harvey M. Friedman

1. Graphs, Cliques, and Order Invariance.
2. Maximal Clique Upper Split Theorem.
3. Maximal Clique Embedding Theorems.
4. Greedy Cliques and Huge Cardinals.
5. Sequential Constructions.
6. Finite Games.
7. Templates.

5. Sequential Constructions and Concreteness.

The statement that lends itself best to sequential constructions is  
the following weakening of the Greedy Clique Upper Shift Theorem.

NONUNIFORM GREEDY CLIQUE UPPER SHIFT THEOREM. For any order invariant  
graph on Q^k, the induced subgraph on some Ak, 0 in A contained in Q,  
has a greedy clique containing its upper shift.

THEOREM 5.1. The Nonuniform Greedy Clique Upper Shift Theorem is  
provably equivalent, over WKL_0, to Con(SRP). It is provable in SRP+  
but not in any consistent fragment of SRP that logically implies RCA_0.
Let x_1,...,x_r,y in Q^k. The birthdate of y over x_1,...,x_r is the  
least 1 <= i <= r such that every coordinate of y is a coordinate of  
some x_j, 1 <= j <= i.

Fix an order invariant graph G on Q^k. We define the G sequences.

A G sequence is a nonempty finite or infinite sequence x_1±,x_2±,...,  
where each x_i in Q^k, such that the following holds. Here each ± is  
either + or -.

i. x_1 = (0,1,...,k-1)±. Now assume that the (i+1)-st entry exists, i  
 >= 1.
ii. If the i-th entry is x_i+, then x_i+1 has the smallest possible  
birthdate of any vector over x_1,...,x_i.
iii. If the i-th entry is x_i-, then the (i+1)-st entry is x_i+1+,  
where x_i,x_i+1 are not G related.

INFINITE GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k, there is an infinite G sequence in which the vectors  
occurring positively, together with their upper shifts, form a G clique.

FINITE GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k, there is a G sequence of any given finite length in  
which the vectors occurring positively, together with their upper  
shifts, form a G clique.

ESTIMATED GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k and n >= 1, there is a G sequence of length n in which  
the vectors occurring positively, together with their upper shifts,  
form a G clique, and where the numerators and denominators in the  
reduced forms of x_1,...,x_n are of magnitude at most (8kn)!!.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 457th 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-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM
453: Rational Graphs and Large Cardinals III  1/20/11  2:33AM
454: Three Milestones in Incompleteness  2/7/11  12:05AM
455: The Quantifier "most"  2/22/11  4:47PM
456: The Quantifiers "majority/minority"  2/23/11  9:51AM
457: Maximal Cliques and Large Cardinals  5/3/11  3:40AM