[FOM] 382:Upper Shift Greedy Cliques and Large Cardinals

[Harvey Friedman]

This is a comprehensive restatement. It contains various  
simplifications.

This supersedes all earlier versions of the SRP and HUGE level  
independence, and is completely self contained.

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 CLIQUES AND LARGE CARDINALS
by
Harvey M. Friedman
December 30, 2009

1. TERMINOLOGY.
2. THE UPPER SHIFT GREEDY CLIQUE THEOREM.
3. THE FINITE UPPER SHIFT GREEDY CLIQUE THEOREMS.
4. THE FINITE UPPER SHIFT GREEDY CLIQUE GAMES.
5. GREEDY SET FORMULATIONS.
6. EXTREME TERMINOLOGY.
7. THE EXTREME UPPER SHIFT GREEDY SET THEOREM.
8. THE FINITE EXTREME UPPER SHIFT GREEDY SET THEOREM.
9. TEMPLATES.
10. EXERCISES

1. Terminology.

We use Q for the set of rationals. A Q tuple is a nonempty finite  
sequence from Q. We index tuples from 1.

For Q tuples x,y, we define x <= y iff max(x) <= max(y).

Let A,B be sets of Q tuples. We say that A almost contains B if and  
only if every element of B that is <= some element of A, is an element  
of A.

A simple graph on Q^k is a graph with vertex set Q^k, whose edge set
is a symmetric set of ordered pairs from Q^k whose two coordinates are
distinct.

Note that we can also view the edge set of G as a subset of Q^2k by
concatenating the two vertices in the edges.

We say that A is a clique in G if and only if for all distinct x,y in  
A, (x,y) is an edge of G.

We say that A is a greedy clique in G if and only if

i. A is a clique in G.
ii. For all x in (fld(A) union {0})^k, there exists y <= x from A such  
that (x,y) is not an edge of G.

Let x,y be Q tuples. We say that x,y are order equivalent if and only if

i. x,y are of the same length.
2. for all 1 <= i,j <= lth(x), x_i < x_j iff y_i < y_j.

We say that a set E of Q tuples is order invariant if and only if for  
all order equivalent Q tuples x,y, x in E iff y in E.

We say that G is a simple order invariant graph on Q^k if and only if
G is a simple graph on Q^k whose edge set is order invariant as a
subset of Q^2k.

The upper shift of a Q tuple is the result of adding 1 to all of its  
nonnegative coordinates.

The upper shift of a set of Q tuples is the set of upper shift of its  
elements.

The complexity of rationals is defined as follows. c(q) is the least  
integer n such that q is the ratio of integers of magnitude at most n.  
The complexity of tuples of rationals, c(x), is the maximum of the  
complexities of its coordinates.

SRP+ = ZFC + "for all k there exists a limit ordinal with the k-SRP".  
SRP = ZFC + {there is a limit ordinal with the k-SRP}_k. Here SRP =  
"stationary Ramsey property". The SRP hierarchy is intertwined with  
the subtle, almost ineffable, and ineffable cardinal hierarchies. EFA  
= exponential function arithmetic.

2. The Upper Shift Greedy Clique Theorem.

PROPOSITION 2.1. THE UPPER SHIFT GREEDY CLIQUE THEOREM. Every simple  
order invariant graph on Q^k has a greedy clique containing its upper  
shift.

THEOREM 2.2. Proposition 2.1 is provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 2.1 is  
provably equivalent to Con(SRP) over WKL_0.

3. The Finite Upper Shift Greedy Clique Theorems.

Let G be a simple graph on Q^k. We say that A_1,...,A_n, n >= 1, is a  
(finite) greedy clique tower in G if and only if

i. A_1 containedin ... containedin A_n are (finite) cliques in G.
ii. For all x in (fld(A_i) union {0})^k, 1 <= i < n, there exists y <=  
x from A_i+1 such that (x,y) is not an edge of G.

We also consider (finite) greedy clique towers in G of infinite length.

PROPOSITION 3.1. THE FINITE UPPER SHIFT GREEDY CLIQUE THEOREM. Every  
simple order invariant graph on Q^k has finite greedy clique towers of  
every finite length, where each term almost contains its upper shift.

PROPOSITION 3.2. Every simple order invariant graph on Q^k has a  
finite greedy clique tower of infinite length, where each term almost  
contains its upper shift.

PROPOSITION 3.3. Every simple order invariant graph on Q^k has a  
finite greedy clique tower of length k, where each term almost  
contains its upper shift.

PROPOSITION 3.4. THE CONCRETE UPPER SHIFT GREEDY CLIQUE THEOREM. Every  
simple order invariant graph on Q^k has a finite greedy clique tower  
of length k, where each term almost contains its upper shift, and has  
complexity at most (8k)!!.

Note that Propositions 3.1,3.3 are explicitly Pi02, and Proposition  
3.4 is explicitly Pi01.

THEOREM 3.5. Propositions 3.1-3.4 are provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 3.2 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 3.1,3.3,3.4  
are provably equivalent to Con(SRP) over EFA.

4. The Finite Upper Shift Greedy Clique Games.

Let G be a simple graph on Q^k, and 1 <= n <= infinity.

In the game #(G,n,us), Alice and Bob alternately make n moves,  
starting with Alice.

Alice's moves are elements of Q^k, with no restrictions. Bob's moves  
also are elements of Q^k, but with restrictions.

Suppose Alice has just played the vertex x.

case 1. This is Alice's first move, or every coordinate of x is a  
coordinate of some previous move of Bob. Bob must play some vertex y  
<= x, where {x,y} is not an edge of G.

case 2. Otherwise. Then Bob must play the upper shift of his preceding  
move.

Bob is considered the winner if and only if at the end of the game,
the set of vertices Bob has played is a clique in G.

PROPOSITION 4.1. THE FINITE UPPER SHIFT GREEDY CLIQUE GAME THEOREM.  
For all k,n >= 1 and simple order invariant graphs G on Q^k, Bob wins  
#(G,n,us).

PROPOSITION 4.2. For all simple order invariant graphs G on Q^k, Bob  
wins #(G,infinity,us).

PROPOSITION 4.3. For all simple order invariant graphs G on Q^k, Bob  
wins #(G,k,us).

PROPOSITION 4.4. THE CONCRETE UPPER SHIFT GREEDY CLIQUE GAME THEOREM.  
For all simple order invariant graphs G on Q^k, Bob wins #(G,k,us) by  
playing moves whose complexity is at most (8kr)!!, where r is the  
complexity of Alice's first move. (A ridiculously large, but safe,  
upper bound).

Note that Proposition 4.4 is explicitly Pi01.

THEOREM 4.5. Propositions 4.1-4.4 are provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 4.2 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 4.1,4.3,4.4  
are provably equivalent to Con(SRP) over RCA_0. Proposition 4.4 is  
provably equivalent to Con(SRP) over EFA.

5. Greedy Set Formulations.

The greedy clique formulations in sections 1-4 reflect the intense  
interest in cliques and clique constructions in graph theory and  
theoretical computer science.

There is an alternative formulation, using what we call greedy sets,  
which has some advantages. One particular advantage is that greedy  
clique formulations don't work well for the Extreme Theorems, but  
greedy set formulations do.

For Q tuples x,y, we define x < y if and only if max(x) < max(y), and  
x > y if and only if max(x) > max(y).

A digraph on Q^k is a graph G whose vertex set is Q^k, and whose edge  
set is a set of ordered pairs from Q^k.

We say that A is a greedy set in G if and only if for all x in (fld(A)  
union {0})^k, x is in A if and only if for all y < x from A, (x,y) is  
an edge of G.

PROPOSITION 5.1. THE UPPER SHIFT GREEDY SET THEOREM. Every order  
invariant digraph on Q^k has a greedy set containing its upper shift.

THEOREM 5.2. Proposition 5.1 is provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 2.1 is  
provably equivalent to Con(SRP) over WKL_0.

For The Finite Upper Shift Greedy Set Theorems, we make the following  
definition.

Let G be a digraph on Q^k. We say that A_1,...,A_n, n >= 1, is a  
(finite) greedy set tower in G if and only if

i. A_1 containedin ... containedin A_n.
ii. For all x in (fld(A_i) union {0})^k, 1 <= i < n, x is in A if and  
only if for all y < x from A_i+1, (x,y) is an edge of G.

We will also consider (finite) greedy set towers in G of infinite  
length.

PROPOSITION 5.3. THE FINITE UPPER SHIFT GREEDY SET THEOREM. Every  
order invariant digraph on Q^k has finite greedy set towers of every  
finite length, where each term almost contains its upper shift.

PROPOSITION 5.4. Every order invariant digraph on Q^k has a finite  
greedy set tower of infinite length, where each term almost contains  
its upper shift.

PROPOSITION 5.5. Every order invariant digraph on Q^k has a finite  
greedy set tower of length k, where each term almost contains its  
upper shift.

PROPOSITION 5.6. THE CONCRETE FINITE UPPER SHIFT GREEDY SET THEOREM.  
Every order invariant digraph on Q^k has a finite greedy set tower of  
length k, where each term almost contains its upper shift, and has  
complexity at most (8k)!!.

Note that Propositions 5.3,5.5 are explicitly Pi02, and Proposition  
5.6 is explicitly Pi01.

THEOREM 5.7. Propositions 5.3-5.6 are provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 5.4 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 5.3,5.5,5.6  
are provably equivalent to Con(SRP) over EFA.

To transfer the results from section 4 over to the Greedy Set  
formulation, we need an additional definition.

Let G be a digraph on Q^k, and 1 <= n <= infinity. We say that A is a  
down clique in G if and only if for all x > y from A, (x,y) is an edge  
of G.

In the game #'(G,n,us), Alice and Bob alternately make n moves,  
starting with Alice.

Alice's moves are elements of Q^k, with no restrictions. Bob's moves  
also are elements of Q^k, but with restrictions.

Suppose Alice has just played the vertex x.

case 1. This is Alice's first move, or every coordinate of x is a  
coordinate of some previous move of Bob. Bob plays x, or some y < x  
such that (x,y) is not an edge of G.

case 2. Otherwise. Then Bob must play the upper shift of his preceding  
move.

Bob is considered the winner if and only if at the end of the game,
the set of vertices Bob has played is a down clique in G.

PROPOSITION 5.8. THE FINITE UPPER SHIFT GREEDY SET GAME THEOREM. For  
all k,n >= 1 and order invariant digraphs G on Q^k, Bob wins #'(G,n,us).

PROPOSITION 5.9. For all order invariant digraphs G on Q^k, Bob wins  
#'(G,infinity,us).

PROPOSITION 5.10. For all order invariant digraphs G on Q^k, Bob wins  
#'(G,k,us).

PROPOSITION 5.11. THE CONCRETE UPPER SHIFT GREEDY SET GAME THEOREM.  
For all order invariant digraphs G on Q^k, Bob wins #'(G,k,us) by  
playing moves whose complexity is at most (8kr)!!, where r is the  
complexity of Alice's first move.

Note that Proposition 5.11 is explicitly Pi01.

THEOREM 5.12. Propositions 5.8-5.11 are provable in SRP+ but not in  
any consistent fragment of SRP that proves RCA_0. Proposition 5.9 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 5.8,5.10,5.11  
are provably equivalent to Con(SRP) over RCA_0. Proposition 5.11 is  
provably equivalent to Con(SRP) over EFA.

6. Extreme Terminology.

A digraph on Q^k union Q^k+1 is a graph G with vertex set Q^k union Q^k 
+1, whose edge set is a set of ordered pairs from Q^k union Q^k+1.

We say that A is a greedy set in G if and only if A is a subset of Q^k  
union Q^k+1 such that for all x in Q^k, x is in A if and only if for  
all y < x from A, (x,y) is an edge of G.

Let A be contained in Q^k union Q^k+1. The k dimensional upper shift  
of A is the upper shift of A intersected with Q^k.

The cross sections of A are the sets A_q = {x in Q^k: (q,x) is in A}.  
According to this definition, only the Q^k+1 part of A creates cross  
sections.

We write A|<q for {x in A: max(x) < q}.

Let A,B be contained in Q^k union Q^k+1. We say that B is amenable in  
A if and only if for all positive integers n, B|<n is a cross section  
of A. This immediately implies that B is a subset of Q^k+1 or empty.

We say that B is almost amenable in A if and only if for all positive  
integers n <= some element of A, B|<n = A_n+(1/2).

HUGE+ = ZFC + "for all n, there is an n-huge cardinal". HUGE = ZFC +  
{there exists an n-huge cardinal}_n.

7. The Extreme Upper Shift Greedy Set Theorem.

PROPOSITION 7.1. Every order invariant digraph on Q^k union Q^k+1 has  
a greedy set containing its upper shift.

PROPOSITION 7.2. THE EXTREME UPPER SHIFT GREEDY SET THEOREM. Every  
order invariant digraph on Q^k union Q^k+1 has a greedy set whose k  
dimensional upper shift is an amenable subset.

THEOREM 7.3. Proposition 7.1 is provable in SRP+ but not in any  
consistent fragment of SRP that proves RCA_0. Proposition 7.1 is  
provably equivalent to Con(SRP) over WKL_0.

THEOREM 7.4. Proposition 7.2 is provable in HUGE+ but not in any  
consistent fragment of HUGE that proves RCA_0. Proposition 7.2 is  
provably equivalent to Con(HUGE) over WKL_0.

8. The Finite Extreme Upper Shift Greedy Set Theorems.

Let G be a digraph on Q^k union Q^k+1. We say that A_1,...,A_n, n >=  
1, is a (finite) greedy set tower in G if and only if

i. A_1 containedin ... containedin A_n.
ii. For all x in (fld(A_i) union {0})^k, 1 <= i < n, x is in A if and  
only if for all y < x from A_i+1, (x,y) is an edge of G.

We will also consider (finite) greedy set towers in G of infinite  
length.

PROPOSITION 8.1. THE FINITE EXTREME UPPER SHIFT GREEDY SET THEOREM.  
Every order invariant digraph on Q^k has finite greedy set towers of  
every finite length, where the k dimensional upper shift of each term  
is an almost amenable subset.

PROPOSITION 8.2. Every order invariant digraph on Q^k has a finite  
greedy set tower of infinite length, where the k dimensional upper  
shift of each term is an almost amenable subset.

PROPOSITION 8.3. Every order invariant digraph on Q^k has a finite  
greedy set tower of length k, where the k dimensional upper shift of  
each term is an almost amenable subset.

PROPOSITION 8.4. THE CONCRETE FINITE UPPER SHIFT GREEDY SET THEOREM.  
Every order invariant digraph on Q^k has a finite greedy set tower of  
length k, where the k dimensional upper shift of each term is an  
almost amenable subset, each term having complexity at most (8k)!!.

Note that Propositions 8.1,8.3 are explicitly Pi02, and Proposition  
8.4 is explicitly Pi01.

THEOREM 8.5. Propositions 8.1-8.4 are provable in HUGE+ but not in any  
consistent fragment of HUGE that proves RCA_0. Proposition 8.2 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 8.1,8.3,8.4  
are provably equivalent to Con(HUGE) over EFA.

9. Templates, Completeness.

We let PPL(Q) be the family of partial rational piecewise linear
functions f:Q into Q given by

a_1x + b_1 if x in I_1
...
a_nx + b_n if x in I_n

where n >= 1, the a's,b's are rationals, and the I's are pairwise
disjoint nonempty intervals with rational endpoints (or +-infinity).

COMPLETENESS CONJECTURE 1. In The Upper Shift Greedy Clique Theorem,  
if we fix k and replace the upper shift by any finite list from  
PPL(Q), then the resulting statement is provable or refutable in SRP.

COMPLETENESS CONJECTURE 2. In The Extreme Upper Shift Greedy Set  
Theorem, if we fix k and replace the upper shift by any finite list  
from PPL(Q), then the resulting statement is provable or refutable in  
HUGE.

I believe in the Completeness Conjecture 1, but not in the  
Completeness Conjecture 2. I think that I can go well beyond I3, and  
likely beyond I1 - but I am not ready to claim it. However, I do think  
it holds if we replace HUGE by the NBG + "there exists a nontrivial  
elementary embedding from V into V".

The instances of the Templates for the shift s:Q into Q, where s(x) = x
+1, are refutable in RCA_0.

The instances of the Templates for the restricted upper shift rus:Q
into Q, where rus(x) = x_1 if x = 0; undefined otherwise, are provable
in RCA_0.

10. Exercises.

There are two obvious kinds of exercises.

i. Make the dimension k very small, or make the length n very small.
Then try to prove the statements.
ii. Make the dimension k small, or even moderate, and write down some
specific simple order invariant graphs, order invariant digraphs on  
Q^k and on Q^k union Q^k+1. These can be presented by merely listing  
finitely many 2k tuples from {1,...,2k} (and 2k+2 tuples from {1,...,2k 
+2}), whose set of coordinates is an initial segment of {1,...,2k} (or  
{1,...,2k+2}). Try to prove the statements for just G.

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

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

Harvey Friedman