# [FOM] 458: Sequential Construction for Large Cardinals

Harvey Friedman friedman at math.ohio-state.edu
Fri May 6 01:01:18 EDT 2011

```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)!!.

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

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

```