[FOM] 379: Greedy Sets and Huge Cardinals 1

Sun Dec 27 20:20:10 EST 2009

We have found simplifications in the Extreme statements, which now  
enable us to give good finite forms, at the level of HUGE (the n-huge  
cardinal hierarchy).

This supersedes all earlier versions of the Extreme statements.

We find it a bit more convenient to modify the definition of simple  
graph on Q^k - see below. This applies to the SRP level statements as  
well.

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.

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

GREEDY SETS AND HUGE CARDINALS
by
Harvey M. Friedman
December 27, 2009

1. TERMINOLOGY.
2. THE EXTREME UPPER SHIFT GREEDY SET THEOREM.
3. THE FINITE EXTREME UPPER SHIFT GREEDY TOWER THEOREM.
4. TEMPLATES.
5. EXERCISES

1. Terminology.

We use Q for the set of rationals. For tuples x,y from Q, we define x  
< y iff max(x) < max(y).

For E contained in Q^k, define E* = {x in E: x_1 > x_2,...,x_k}.

For q in Q, we define the 1-section of E at q to be the set of all x  
in Q such that (q,...,q,x) is in E. Here there are k-1 q's. We will  
use this notation only for k >= 3.

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 greedy set in G if and only if A is a subset of Q^k  
such that for all x in (fld(A) union {0})^k*, x in A if and only if  
for all y < x from A, (x,y) is an edge of G.

For x,y in Q^k, we say that x,y are order equivalent if and only if  
for all 1 <= i,j <= k, x_i < x_j iff y_i < y_j.

We say that E contained in Q^k is order invariant if and only if for  
all order equivalent x,y from Q^k, 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 tuple from Q is the result of adding 1 to all of  
its nonnegative coordinates.

2. The Extreme Greedy Set Theorem.

We first state a much weaker theorem.

PROPOSITION 2.1. Every simple order invariant graph on Q^k has a  
greedy set containing its upper shift.

Also, recall the following from http://www.cs.nyu.edu/pipermail/fom/2009-December/014267.html

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

Now for the Extreme form.

PROPOSITION 2.3. THE EXTREME UPPER SHIFT GREEDY SET THEORM. Every  
simple order invariant graph on Q^k, k >= 3, has a greedy set A  
containing its upper shift, whose 1-section at k+(1/2) is the  
intersection of (-infinity,k] with the upper shift of its field.

THEOREM 2.4. Propositions 1,2 are provably equivalent, over WKL_0, to  
Con(SRP). Proposition 3 is provably equivalent, over WKL_0, to  
Con(HUGE).

For the SRP level, we prefer Proposition 2.2 to Proposition 2.1, as  
Cliques play a particularly important role in graph theory and  
computer science. We can't use Cliques in the same way for the Extreme  
statements.

3. The Finite Extreme Greedy Tower Theorem.

Let G be a simple graph on Q^k. A greedy tower for G consists of  
finite sets A_1 contained in ... contained in A_n such that for all 1  
<= i < n and x in (fld(A_i) union {0})^k*, x is in A_i+1 if and only  
if for all y < x from A_i, (x,y) is an edge of G.

PROPOSITION 3.1. THE FINITE EXTREME GREEDY TOWER THEOREM. For all k,n  
 >= 3, every simple order invariant graph on Q^k  has a greedy tower  
A_1,...,A_n, such that for all 1 <= i < n, A_i+1 contains the upper  
shift of A_i, and the 1-section of A_i at k+(1/2) is the intersection  
of (-infinity,k] with the upper shift of fld(A_i).

PROPOSITION 3.2. THE FINITE EXTREME GREEDY TOWER THEOREM. For all k,n  
 >= 3, every simple order invariant graph on Q^k, k >= 3, has a greedy  
tower A_1,...,A_n, such that for all 1 <= i < k, A_i+1 contains the  
upper shift of A_i, and the 1-section of A_i at k+(1/2) is the  
intersection of (-infinity,k] with the upper shift of fld(A_i), where  
the rationals used are ratios between integers of magnitude at most  
(8kn)!!.

PROPOSITION 3.3. THE FINITE EXTREME GREEDY TOWER THEOREM. Every simple  
order invariant graph on Q^k, k >= 3, has a greedy tower A_1,...,A_k,  
such that for all 1 <= i < k, A_i+1 contains the upper shift of A_i,  
and the 1-section of A_i at k+(1/2) is the intersection of (- 
infinity,k] with the upper shift of fld(A_i).

PROPOSITION 3.4. THE FINITE EXTREME GREEDY TOWER THEOREM. Every simple  
order invariant graph on Q^k, k >= 3, has a greedy tower A_1,...,A_k,  
such that for all 1 <= i < k, A_i+1 contains the upper shift of A_i,  
and the 1-section of A_i at k+(1/2) is the intersection of (- 
infinity,k] with the upper shift of fld(A_i), where the rationals used  
are ratios between integers of magnitude at most (8k)!!.

Note that Propositions 3.1,3.3 are explicitly Pi02, whereas  
Propositions 3.2,3.4 are explicitly Pi01.

THEOREM 3.5. Propositions 3.1-3.4 are provably equivalent, over EFA,  
to Con(HUGE). For each fixed k, Propositions 3.1,3.2 are provable in  
HUGE, but they are intertwined with Con(ZFC + 1-huge), Con(ZFC + 2- 
huge),... .

4. Templates.

We can template the upper shift with one or more partial rational  
piecewise linear functions from Q into Q, extended to tuples  
coordinatewise.

See http://www.cs.nyu.edu/pipermail/fom/2009-December/014267.html

5. Exercises.

We can create exercises as in http://www.cs.nyu.edu/pipermail/fom/2009-December/014267.html

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

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

Harvey Friedman