[FOM] 379: Greedy Sets and Huge Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
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
More information about the FOM
mailing list