[FOM] 376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Thu Dec 24 14:23:30 EST 2009
This is a definitive restatement, obsoleting http://www.cs.nyu.edu/pipermail/fom/2009-December/014221.html
and incorporating #375.
In section 8, we have a new direct and concrete way of saying things
at the level of SRP.
THIS IS A SELF CONTAINED ABSTRACT.
THE UPPER SHIFT GREEDY CLIQUE THEOREM, AND LARGE CARDINALS
by
Harvey M. Friedman
December 24, 2009
1. Terminology.
2. The Greedy Clique Theorem.
3. The Upper Shift Greedy Clique Theorem.
4. The Extreme Upper Shift Greedy Clique Theorems.
5. Finite Upper Shift Greedy Clique Theorems.
6. Finite Extreme Upper Shift Greedy Clique Theorems.
7. Upper Shift Clique Games.
8. Upper Shift Clique Sequences.
9. Templates, Dichotomy, Trichotomy.
10. Exercises.
1. TERMINOLOGY.
We use Q for the set of all rationals.
We define x <= y if and only if x,y are tuples from Q such that max(x)
<= max(y). We define x < y if and only if x,y are tuples from Q such
that max(x) < max(y).
For A contained in Q^k, we define fld(A) to be the set of all
rationals appearing in A.
We use simple graphs G on Q^k. Here G is given by its set of edges,
where each edge is a subset of Q^k of cardinality 2.
A clique in G is a set A of vertices of G such that for all distinct
x,y in A, {x,y} is an edge of G.
A greedy clique in G is a clique A in G such that 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.
We say that x,y in Q^k are order equivalent iff for all 1 <= i,j <= n,
x_i < x_j iff y_i < y_j.
We say that A contained in Q^k is order invariant iff for all order
equivalent x,y in Q^k, x in A iff y in A.
We focus on the simple order invariant graphs on Q^k. These are simple
graphs on Q^k where the edge set is order invariant as a subset of
Q^2k. These are very concrete simple graphs - there are at most
2^((2k)^(2k)) of them.
The upper shift of x in Q^k is obtained by adding 1 to all nonnegative
coordinates. The upper shift of a subset of Q^k is the set of upper
shifts of its elements.
For the Extreme Theorems (sections 4,6), we will not use cliques.
Instead, we use simple graphs G on Q^k union Q^k+1. Here G is given by
its set of edges, where each edge is a subset of Q^k union Q^k+1 of
cardinality 2.
A greedy set in G is a subset A of Q^k union Q^k+1 such that 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.
Let A be contained in Q^k union Q^k+1. The lower 1-sections of A are
the subsets of Q given by
{y in Q: y < x_1,...,x_k-1 and (x_1,...,x_k-1,y) is in A}.
{y in Q: y < x_1,...,x_k and (x_1,...,x_k,y) is in A}.
for some fixed x_1,...,x_k in A.
Let A,B be contained in Q^k union Q^k+1. The lower 1-sections of A in
B are the subsets of Q given by
{y in Q: y < x_1,...,x_k-1 and (x_1,...,x_k-1,y) is in B}.
{y in Q: y < x_1,...,x_k and (x_1,...,x_k,y) is in B}.
for some fixed x_1,...,x_k in A.
2. THE GREEDY CLIQUE THEOREM.
THEOREM 2.1. THE GREEDY CLIQUE THEOREM. Let A be a subset of Q. The
following are equivalent.
i. Every simple graph with vertex set A^k has a greedy clique.
ii. A is well ordered.
THEOREM 2.2. Theorem 2.1 is provably equivalent to ATR_0 over RCA_0.
In fact, ii arrows i is provably equivalent to ATR_0 over RCA_0,
whereas i arrows ii is provable in RCA_0.
3. THE UPPER SHIFT GREEDY CLIQUE THEOREM.
PROPOSITION 3.1. THE UPPER SHIFT GREEDY CLIQUE THEOREM. Every simple
order invariant graph on Q^k has a greedy clique that contains its
upper shift.
Proposition 3.1 is provable using large cardinals, but not in ZFC. The
large cardinals associated with Proposition 3.1 are most intuitively
described in terms of the SRP = stationary Ramsey property. We say
that a limit ordinal lambda has the k-SRP if and only if any partition
of the unordered k-tuples from lambda into two pieces has a
homogeneous set that is stationary in lambda.
The least limit ordinal lambda with the k-SRP, k >= 2, is a large
cardinal (strongly inaccessible, strongly Mahlo, weakly compact,
etcetera). These form the SRP hierarchy, which is intertwined with the
subtle, almost ineffable, and ineffable cardinal hierarchies. See
H. Friedman, Subtle Cardinals and Linear Orderings, Annals of Pure and
Applied Logic 107 (2001), 1-34.
for a modern treatment of these hierarchies that go back to James
Baumgartner.
SRP+ = ZFC + (forall k)(some lambda has the k-SRP). SRP = ZFC + {some
lambda has the k-SRP}_k.
THEOREM 3.2. The Upper Shift Greedy Clique Theorem is provable
in SRP+ but not in any consistent fragment of SRP implying RCA_0. The
Upper Shift
Greedy Clique Theorem is provably equivalent, over WKL_0, to
Con(SRP).
THEOREM 3.3. Let k >= 1. Proposition 3.1 for k is provable in ZFC +
"there exists lambda with the k-SRP".
THEOREM 3.4. Let k be sufficiently large. Proposition 3.2 for k is not
provable in any consistent fragment of ZFC + "there exists lambda with
the k-1-SRP" implying RCA_0. In particular, Proposition 3.2 for k = 4
(tentative, may
have to be raised somewhat) is not provable in ZFC, assuming ZFC is
consistent.
4. THE EXTREME UPPER SHIFT GREEDY CHAIN THEOREMS.
PROPOSITION 4.1. THE EXTREME UPPER SHIFT GREEDY SET THEOREM. Every
simple order invariant graph on Q^k union Q^k+1 has a greedy set such
that the upper shift of every element or lower 1-section of the greedy
set is an element or lower 1-section of the greedy set.
Let A be a subset of Q^k union Q^k+1, and f:Q into Q. We say that A is
f closed if and only if for all x in A, f(x) in A. Here f is extended
to tuples coordinatewise.
We say that A is strongly f closed if and only if A is f closed, and
for all lower 1-sections S of A, f[S] is a lower 1-section of A.
PROPOSITION 4.2. Every simple order invariant graph on Q^k union Q^k+1
has a greedy set which is strongly f closed, for some f:Q into Q with
f(0) = 1 and f(2) = 2.
HUGE+ = ZFC + "for all k, there is a k-huge cardinal". HUGE = ZFC +
{there is a k-huge cardinal}_k.
Nearly the most extreme large cardinal hypotheses are stated in
Kanamori, The Higher Infinite, page 325:
I1. For some alpha, there is a proper elementary embedding j:V(alpha +
1) into V(alpha + 1).
I2. There is a j:V into M such that V(alpha) is contained in M for
some alpha > crit(j) satisfying j(alpha) = alpha.
I3. For some alpha, there is a proper elementary embedding j:V(alpha)
into V(alpha).
THEOREM 4.3. Proposition 4.1 is provable in HUGE+ but not in any
consistent fragment of HUGE that implies RCA_0. Proposition 4.1 is
provably equivalent, over WKL_0, to Con(HUGE). Proposition 4.2 is
provable in NBG + I2 but not in any consistent fragment of ZFC + I3.
The implications Con(NBG + I2) implies Proposition 4.2 implies Con(ZFC
+ I3) are provable in WKL_0. Proposition 4.2 is provably equivalent to
a Pi01 sentence over WKL_0. We can use a strengthened from of I3;
e.g., there are arbitrarily large alpha with a proper elementary
embedding j:V(alpha) into V(alpha), and more.
5. FINITE UPPER SHIFT GREEDY CLIQUE THEOREMS.
For A contained in Q^k, we define fld(A) as the set of rationals
appearing in A.
Let G be a simple graph on Q^k. We have already defined the greedy
cliques in G.
We say that A_1,...,A_n is a greedy clique sequence in G if and only if
i. The union of the A's is a finite clique in G.
ii. For all 1 <= i < n and x in (fld(A_i) union {0})^k, there exists y
<= x from A_i+1 such that {x,y} is not an edge of G.
PROPOSITION 5.1. For all n >= 1, every simple order invariant graph on
Q^k has a greedy clique sequence of length n, where the upper shift of
each nonterminal term is contained in the next.
PROPOSITION 5.2. Every simple order invariant graph on Q^k has a
greedy clique sequence of length k, where the upper shift of each
nonterminal term is contained in the next, and where the numerators
and denominators used are of magnitude at most (8k)!!.
Note that Proposition 5.1 is explicitly Pi02, and Proposition 5.2 is
explicitly Pi01.
THEOREM 5.3. Propositions 5.1,5.2 are provably equivalent to Con(SRP)
over EFA (exponential function arithmetic).
6. FINITE EXTREME UPPER SHIFT GREEDY CLIQUE THEOREMS.
Let G be a simple graph on Q^k x Q^k+1.
We say that A_1,...,A_n is a greedy set sequence in G if and only if
i. The A's are finite subsets of Q^k union Q^k+1.
ii. For all 1 <= i < n and x in (fld(A_i) union {0})^k, x is in A_i if
and only if for all y < x from A_i+1, {x,y} is an edge of G.
PROPOSITION 6.1. For all n >= 1, every simple order invariant graph on
Q^k union Q^k+1 has a greedy set sequence A_1,...,A_n, where for all 1
<= i < n, the upper shift of A_i is contained in A_i+1, and the upper
shift of every lower 1-section of A_i in A_n is a lower 1-section of
A_i+1 in A_n.
PROPOSITION 6.2. Every simple order invariant graph on Q^k union Q^k+1
has a greedy set sequence A_1,...,A_k, where for all 1 <= i < k, the
upper shift of A_i is contained in A_i+1, the upper shift of every
lower 1-section of A_i in A_k is a lower 1-section of A_i+1 in A_k,
and the numerators and denominators used are of magnitude at most
(8k)!!.
Note that Proposition 6.1 is explicitly Pi02, and Proposition 6.2 is
explicitly Pi01.
THEOREM 6.3. Propositions 6.1,6.2 are provably equivalent to Con(HUGE)
over EFA (exponential function arithmetic).
PROPOSITION 6.4. For all n >= 1, every simple order invariant graph on
Q^k union Q^k+1 has a greedy set sequence A_1,...,A_n and an f:Q into
Q sending 0 to 1 and 2 to 2, where for all 1 <= i < n, the f image of
A_i is contained in A_i+1, and the f image of every lower 1-section of
A_i in A_n is a lower 1-section of A_i+1 in A_n.
PROPOSITION 6.5. Every simple order invariant graph on Q^k union Q^k+1
has a greedy set sequence A_1,...,A_k and an f:Q into Q sending 0 to 1
and 2 to 2, where for all 1 <= i < k, the f image of A_i is contained
in A_i+1, the f image of every lower 1-section of A_i in A_n is a
lower 1-section of A_i+1 in A_k, and the numerators and denominators
used are of magnitude at most (8k)!!.
THEOREM 6.6. Propositions 6.4,6.5 are provable in NBG + I2 but not in
any consistent fragment of ZFC + I3 implying RCA_0. The implications
Con(NBG + I2) implies Propositions 6.4,6.5 implies Con(ZFC + I3) are
provable in EFA (exponential function arithmetic). Propositions
6.4,6.5 are provably equivalent to a Pi01 sentence over EFA. We can
use a strengthened from of I3; e.g., there are arbitrarily large alpha
with a proper elementary embedding j:V(alpha) into V(alpha), and more.
There is a general theory of finite forms for infinitary statements of
the kind considered here.
Consider all sentences of the following form:
#) There exists A_1,...,A_n contained in Q^k such that for all 1 <= i
<= m, P(i,A_1,...,A_n) holds.
Here k,n,m are specific positive integers, and P is a specific first
order property of the structure (Q,<,A_1,...,A_n), where the A's act
as k-ary relation symbols.
THEOREM 6.7. There is an effective procedure that converts any
sentence phi of form #) into an algorithmic process Gamma, such that
phi holds if and only if Gamma does not terminate.
We can expand #) to allow the upper shift us, and constants, provided
that we require P to be in prenex form and allow only bounded
quantifiers after initial universal quantifiers. This will allow us to
treat the Upper Shift Greedy Chain Theorem and the Extreme
Upper Shift Greedy Chain Theorem, and even Proposition 4.2, without
having
to give a specific finite form.
7. UPPER SHIFT CLIQUE GAMES.
Let G be a simple graph with vertex set Q^k, and 1 <= n <= infinity.
The game #(G,n) comes equipped with a basket, which is to hold a set
of vertices of G. At the beginning of the game, the basket is empty.
In #(G,n), Alice and Bob alternately make n moves, starting with Alice.
Alice's first move can be any vertex of G. Alice's subsequent moves
must be vertices of G that use only rationals that currently appear in
the basket.
Suppose Alice has just played the vertex x. Bob must throw some vertex
y <= x into the basket, where {x,y} is not an edge of G.
Bob is considered the winner if and only if at the end of the game,
the set of vertices in the basket is a clique in G.
THEOREM 7.1. Bob wins #(G,infinity). In fact, Bob has a winning
strategy that uses only rationals that appear in Alice's first move.
Let G be a simple graph, with vertex set Q^k, and 1 <= n <= infinity.
The game #(G,n,us) comes equipped with a basket, which is to hold a
set of vertices of G. At the beginning of the game, the basket is empty.
In #(G,n,us), Alice and Bob alternately make n moves, starting with
Alice.
Alice's first move can be any vertex of G. Alice's subsequent moves
must be vertices of G that use only rationals that currently appear in
the basket.
Suppose Alice has just played the vertex x. Bob must throw some vertex
y <= x and its upper shift into the basket, where {x,y} is not an edge
of G.
Bob is considered the winner if and only if at the end of the game,
the set of vertices in the basket is a clique in G.
PROPOSITION 7.2. For all simple order invariant graphs G on Q^k and 1
<= n <= infinity, Bob wins #(G,n,us).
PROPOSITION 7.3. For all simple order invariant graphs G on Q^k, Bob
wins #(G,k,us).
THEOREM 7.4. Propositions 7.1,7.2 are provable in SRP+ but not in any
consistent fragment of SRP implying RCA_0. Propositions 7.2,7.3 are
provably equivalent to Con(SRP) over RCA_0.
Propositions 7.2,7.3 are not explicitly arithmetical. We give
explicitly Pi01 forms by putting a quantitative restriction on Bob's
moves.
Let G be a simple graph, with vertex set Q^k, and 1 <= n <= infinity.
The game #'(G,n,us) comes equipped with a basket, which is to hold a
set of vertices of G. At the beginning of the game, the basket is empty.
In #'(G,n,us), Alice and Bob alternately make n moves, starting with
Alice.
Alice's first move can be any vertex of G. Alice's subsequent moves
must be vertices of G that use only rationals that currently appear in
the basket.
Suppose Alice has just played the vertex x. Bob must throw some vertex
y <= x and its upper shift into the basket, where {x,y} is not an edge
of G, and c(y) is at most the sum of all c(z), for rationals z that
have appeared in the game thus far.
Bob is considered the winner if and only if at the end of the game,
the set of vertices in the basket is a clique in G.
Note that in order for Bob to win #'(G,n,us), n finite, all vertices
thrown into the basket by Bob must have a complexity bounded above by
an exponential expression in the complexity of Alice's first move.
Thus a winning strategy for Bob, relative to any initial move of
Alice, is a function whose field is bounded by an exponential
expression in the complexity of Alice's first move. Hence we can
express "Bob wins #'(G,n,us)" in the form "relative to any initial
move of Alice, there is a winning strategy for Bob involving rationals
whose complexity is bounded by a particular exponential expression".
This provides a natural Pi01 formalization of "Bob wins #'(G,n,us)".
PROPOSITION 7.5. For all simple order invariant graphs G on Q^k and 1
<= n <= infinity, Bob wins #'(G,n,us).
PROPOSITION 7.6. For all simple order invariant graphs G on Q^k, Bob
wins #'(G,k,us).
Note that Proposition 7.6 is explicitly Pi01 according to the above
remarks. The same applies to Proposition 7.5 for finite n.
THEOREM 7.7. Propositions 7.5,7.6 are provably equivalent to Con(SRP)
over RCA_0. Proposition 7.5 for finite n, and Proposition 7.6 are
provably equivalent to Con(SRP) over EFA (exponential function
arithmetic).
The finite games associated with the Extreme Theorems are, at the
moment, awkward.
8. UPPER SHIFT CLIQUE SEQUENCES.
We say that a finite or infinite sequence from Q^k is restricted if
and only if the complexity of each term after the initial term (i.e.,
c(x)) is at most the sum of the complexities of the rationals in the
previous terms.
Let G be a simple graph on Q^k, and alpha = x_1,... be a sequence from
Q^k of length 1 <= n <= infinity.
A G,alpha sequence is a restricted sequence y_1,... from Q^k of length
n such that the following holds.
i. If i = 1 or x_i is a subsequence of (the concatenation of)
y_1,...,y_i-1, then y_i <= x_i and {x_i,y_i} is not an edge of G.
ii. Otherwise, y_i is the upper shift of y_i-1.
PROPOSITION 8.1. Let G be a simple order invariant graph on Q^k, and
alpha be a sequence from Q^k of length 1 <= n <= infinity. There is a
G,alpha sequence whose set of terms is a clique in G.
PROPOSITION 8.2. Let G be a simple order invariant graph on Q^k, and
alpha be a sequence from Q^k of length k. There is a G,alpha sequence
whose set of terms is a clique in G.
Note that Proposition 8.2 is explicitly Pi01. Also Proposition 8.1 for
finite n is explicitly Pi01.
THEOREM 8.3. Propositions 8.1,8.2 are provably equivalent to Con(SRP)
over RCA_0. Proposition 8.1 for finite n, and Proposition 8.2 are
provably equivalent to Con(SRP) over EFA (exponential function
arithmetic)
9. TEMPLATES, DICHOTOMY, TRICHOTOMY.
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).
In this abstract, wherever we have used the upper shift from Q into Q,
we can instead consider using T_1,...,T_r from PPL(Q), r >= 0. The T's
are extended to Q^k coordinatewise, just as the upper shift on Q was
extended coordinatewise to Q^k. This provides various Templates for
the statements that are equivalent to Con(SRP).
The dichotomy conjectures asserts that each instance of the Templates
is provable or refutable in SRP.
The trichotomy conjecture asserts that each instance of the Template is
i. Provable in RCA_0; or
ii. Refutable in RCA_0; or
iii. Provably equivalent, in RCA_0, to Con(SRP).
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 G on Q^k. These can be
presented by merely listing finitely many 2k tuples from {1,...,2k},
whose set of coordinates is an initial segment of {1,...,2k}. Try to
prove the statements for just G.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 376th 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
Harvey Friedman
More information about the FOM
mailing list