[FOM] 375: Upper Shift Clique Games and Large Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
Wed Dec 23 00:47:41 EST 2009
The current state of the art is http://www.cs.nyu.edu/pipermail/fom/2009-December/014221.html
See the correction of a typo, in http://www.cs.nyu.edu/pipermail/fom/2009-December/014231.html
The Game associated with large cardinals is getting attractive. We now
want to make it yet more attractive.
Firstly, we switch to standard graph theoretic notation, using simple
graphs (undirected, with no loops).
We have Alice playing elements of Q^k, and Bob is now throwing
elements of Q^k into a basket. Bob wins if the set of vectors in the
basket forms a clique in G.
We also do something much nicer than we did before in order to get an
explicitly Pi01 statement.
The improvements that we have made for these games also apply to the
original infinitary form, and other forms. Rather than give a
comprehensive abstract covering all important aspects, we just present
The Upper Shift Greedy Clique Theorem in section 5.
THIS IS A SELF CONTAINED ABSTRACT.
UPPER SHIFT CLIQUE GAMES AND LARGE CARDINALS 1
by
Harvey M. Friedman
December 23, 2009
1. CLIQUE GAMES.
2. UPPER SHIFT CLIQUE GAMES.
3. RESTRICTED UPPER SHIFT CLIQUE GAMES.
4. TEMPLATE.
5. UPEPR SHIFT GREEDY CLIQUE THEOREM.
6. EXERCISES.
A simple graph G is a pair (V,E), where V is a nonempty set, and E is
a set of unordered pairs from V. Here unordered pairs have cardinality
2.
V is called the set of vertices, and E is called the set of edges.
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.
We will be considering simple graphs whose vertex set is Q^k, where Q
is the set of all rationals, and k >= 1.
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 say that G is a simple order invariant graph on Q^k if and only if
i. G is a simple graph with vertex set Q^k.
ii. E(G) is order invariant as a subset of Q^2k.
We define the upper shift of x in Q^k as the result of adding 1 to all
of its nonnegative coordinates.
We define x <=k y if and only if x,y in Q^k and max(x) <= max(y).
For x in Q^k, we define c(x) to be the least integer r such that the
coordinates of x are ratios of integers of magnitude at most r.
1. 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 y <=k
x into the basket, where y <=k x and {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 1.1. Bob wins #(G,infinity). In fact, Bob wins by using only
rationals that appear in Alice's first move.
2. Upper Shift Clique Games.
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 and its upper shift into the basket, where y <=k x and {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 2.1. For all simple order invariant graphs G on Q^k and 1
<= n <= infinity, Bob wins #(G,n,us).
THEOREM 2.2. Proposition 2.1 is provable in SRP+ but not in any
consistent fragment of SRP containing RCA_0. Proposition 2.1 is
provably equivalent to Con(SRP) over RCA_0, even for n = k.
Recall that SRP = ZFC + {there is a limit ordinal with the k-
stationary Ramsey property}_k. This stationary Ramsey property
hierarchy is intertwined with the subtle, almost ineffable, and
ineffable cardinal hierarchies.
3. Restricted Upper Shift Clique Games.
Proposition 2.1 is not explicitly arithmetical, even for finite n. In
this section, we give the explicitly Pi01 form 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 and its upper shift into the basket, where y <=k x and {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, the 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 bounded by the
exponential expression". This provides a natural Pi01 formalization of
"Bob wins #'(G,n,us)".
PROPOSITION 3.1. For all simple order invariant graphs G on Q^k and 1
<= n <= infinity, Bob wins #'(G,n,us).
THEOREM 3.2. Proposition 3.1 is provably equivalent to Con(SRP) over
RCA_0. For finite n, Proposition 3.1 is provably equivalent to
Con(SRP) over EFA (exponential function arithmetic). For n = k,
Proposition 3.1 is provably equivalent to Con(SRP) over EFA.
Recall that SRP = ZFC + {there is a limit ordinal with the k-
stationary Ramsey property}_k. This stationary Ramsey property
hierarchy is intertwined with the subtle, almost ineffable, and
ineffable cardinal hierarchies.
4. Template.
The game #(G,n) is so natural, that we will focus on templating the
upper shift.
Note that we have the obvious generalization #(G,n,T_1,...,T_r), where
T_1,...,T_r:Q into Q are partial functions. Here T_1,...,T_r are
lifted to partial functions from Q^k into Q^k, by acting coordinatewise.
Specifically, in the game #(G,n,T_1,...,T_r), Bob is required to throw
some vertex y and (the defined) T_1(y),...,T_r(y) into the basket,
where y <=k x and {x,y} is not an edge of G.
Thus our game #(G,n,us) fits under this notation, where we take us to
be the upper shift function us:Q into Q.
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).
TEMPLATE. Let T_1,...,T_r be in PPL(Q), r >= 0. Consider the game
#(G,n,T_1,...,T_r).
The dichotomy conjecture asserts that each instance of the Template 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 Template instance for the shift s:Q into Q, where s(x) = x+1, is
refutable in RCA_0.
The Template instance of the restricted upper shift rus:Q into Q,
where rus(x) = x_1 if x = 0; undefined otherwise, is provable in RCA_0.
5. Exercises.
There are two obvious kinds of exercises.
i. Make k very small, or make n very small. Then try to prove the
statements.
ii. Make k small, or even moderate, and write down some specific
order invariant simple graph 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.
6. Upper Shift Greedy Clique Theorem.
For A contained in Q^k, we define fld(A) to be the set of all
rationals appearing in A.
The upper shift of A contained in Q^k is the set of all upper shifts
of its elements.
Let G be a simple graph with vertex set Q^k. We say that A is a greedy
G clique if and only if
i. A is a G clique.
ii. For all x in (fld(A) union {0})^k, there exists y <=k x from A,
such that {x,y} is not an edge of G.
UPPER SHIFT GREEDY CLIQUE THEOREM. Every simple order invariant graphs
G on Q^k has a greedy clique that contains its upper shift.
THEOREM 6.1. The Upper Shift Greedy Clique Theorem is provably
equivalent to Con(SRP) over WKL_0. It is provable in SRP+ but not in
any consistent fragment of SRP containing RCA_0.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 375th 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 Reductio, and Large
Cardinals 12/7/09 9:17AM
374: Upper Shift Greedy Chain Games 12/12/09 5:56AM
Harvey Friedman
More information about the FOM
mailing list