[FOM] 382:Upper Shift Greedy Cliques and Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Wed Dec 30 02:31:17 EST 2009
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
More information about the FOM
mailing list