[FOM] 390: Finite Games, Vector Reduction, and Large Cardinals 2
Harvey Friedman
friedman at math.ohio-state.edu
Sun Feb 14 22:27:58 EST 2010
We are working on a series of simplifications and improvements
starting with posting #389 http://www.cs.nyu.edu/pipermail/fom/2010-February/014386.html
Some of these simplifications that we are working on are
substantially more dramatic than #389 and this present posting - but
it will take time to get them just right and checked. I am also
juggling some heavy duty deadlines elsewhere, which is slowing me
down. The plan is to roll out a series of substantial improvements and
simplifications. The present posting is the first such improvement.
1. The Games G(R).
2. The Games G(R,ush).
3. Vector Reduction.
4. Templating.
1. THE GAMES G(R).
We use Q for the set of all rationals.
Let R be contained in Q^2k = Q^k x Q^k. We say that R is a reducer if
and only if for all x,y in Q^k,
i. x R x.
ii. x R y implies x = y or max(x) > max(y).
We say that x,y are related by R if and only if x R y or y R x. We say
that x,y are properly related by R if and only if x,y are distinct and
x,y are related by R.
For all nonempty R contained in Q^2k, we first define the two person
game G(R). This game can be played for any number of moves.
The two players are Alice and Bob, who alternately play a single
element of Q^k. There are restrictions on Alice's moves, but she will
always have legal moves available. There are different restrictions on
Bob's moves, but he may (rather easily) get into a situation where he
has no legal moves available.
We focus on Bob's effort to make infinitely many moves, or at least a
given finite number of moves.
Alice's first move can be any element of Q^k. Subsequently, Alice must
always play an element of Q^k composed of rationals which have
previously appeared in the game.
Suppose Alice has just played x. Bob is required to play some y in Q^k
such that
i. x R y.
ii. y is not properly related by R to any of Bob's previous moves.
THEOREM 1.1. Let k >= 1 and R contained in Q^2k be a reducer. Bob has
a strategy for making infinitely many moves in G(R). In fact, Bob has
a strategy for making infinitely many moves in G(R) using only
rationals appearing in Alice's move in round 1.
2. THE GAME G(R,ush).
The upper shift (on Q) is the function ush: Q into Q given by ush(x) =
x+1 if x >= 0; x otherwise. We extend the upper shift to ush:Q^k into
Q^k by acting coordinatewise.
For all nonempty R contained in Q^2k, we define the two person game
G(R,ush), which is a simple modification of the game G(R). The rules
for Alice are the same as for G(R).
Suppose Alice has just played x. Bob is required to play some y in Q^k
such that
i. x R y
ii. y and ush(y) are each not properly related by R to any of Bob's
previous moves.
Because of the specific use of ush, and for the sake of concreteness,
we move to order invariant R. Specifically, x,y in Q^k are said to be
order equivalent if and only if for all 1 <= i,j <= k, x_i < x_j iff
y_i < y_j. E contained in Q^p if said to be order invariant if and
only if for all order equivalent x,y in Q^p, x is in E iff y is in E.
Order invariant R contained in Q^2k are of special importance, viewed
as binary relations on Q^k.
PROPOSITION 2.1. For all order invariant reducers R contained in Q^2k,
Bob has a strategy for playing infinitely many moves in G(R,ush).
PROPOSITION 2.2. For all order invariant reducers R contained in Q^2k
and n >= 1, Bob has a strategy for playing n moves in G(R,ush).
PROPOSITION 2.3. For all order invariant reducers R contained in Q^2k,
Bob has a strategy for playing k moves in G(R,ush).
Note that Propositions 2.3, 2.4 are already in implicit Pi01 form in
the following sense. Note that for each k,n,R, Bob having such a
strategy is a sentence in (Q,<,+1) effectively obtained from k,n,R.
However, we can easily make Propositions 2.2 and 2.3 explicitly Pi01
by using a very crude estimate. Define the complexity c(x) of x in Q^k
as the maximum of the magnitudes of the denominators and numerators of
the coordinates when put in reduced form.
PROPOSITION 2.4. Let R contained in Q^2k be an order invariant
reducer. For any first play x for Alice, Bob has a strategy function
for playing n moves in G(R,ush), involving only rationals of
complexity at most (8knc(x))!!.
PROPOSITION 2.5. Let R contained in Q^2k be an order invariant
reducer. For any first play x for Alice, Bob has a strategy function
for playing k moves in G(R,ush), involving only rationals of
complexity at most (8kc(x))!!.
Let k >= 1. We say that lambda has the k-SRP if and only if lambda is
a limit ordinal, where for all partitions of the unordered k-tuples
from lambda into two pieces, there is a stationary subset of lambda
all of whose k-tuples lie in the same piece. This results in a
hierarchy that is intertwined with the subtle, almost ineffable, and
ineffable cardinal hierarchies. It is simpler to state.
SRP+ = ZFC + "for all k there exists lambda with the k-SRP". SRP = ZFC
+ {there exists lambda with the k-SRP}_k. EFA = exponential function
arithmetic, or ISigma_0(exp).
THEOREM 2.6. Propositions 2.1 - 2.5 are provable in SRP+ but not in
any consistent consequence of SRP that proves RCA_0. Propositions 2.1
- 2.5 are provably equivalent to Con(SRP) over WKL_0. Propositions
2.2, 2.3 are provably equivalent to Con(SRP) over RCA_0. Propositions
2.4, 2.5 are provably equivalent to Con(SRP) over EFA.
3. THE GAMES G(R,ush)*.
G(R,ush)* is a modification of G(R,ush), which is more demanding on Bob.
For all R contained in Q^2k, we define the two person game G(R,ush),
which is a simple modification of the game G(R).
As in G(R,ush), Alice's first move can be any element of Q^k. Alice's
subsequent moves must consist of rationals that are the sum of any
nonnegative integer with any rational that has previously appeared in
the game.
Suppose Alice has just played x. Bob is required to play some y in Q^k
such that
i. x R y
ii. y is not related by R to any previous move of Bob (other than y).
iii. The moves played by Bob, including y, together with their upper
shifts, form a set where no two distinct elements are related by R.
PROPOSITION 3.1. For all order invariant reducers R contained in Q^2k,
Bob has a strategy for playing infinitely many moves in G(R,ush)*.
PROPOSITION 3.2. For all order invariant reducers R contained in Q^2k
and n >= 1, Bob has a strategy for playing n moves in G(R,ush)*.
PROPOSITION 3.3. For all order invariant reducers R contained in Q^2k,
Bob has a strategy for playing k moves in G(R,ush)*.
THEOREM 3.4. Propositions 3.1 - 3.3 are provable in SRP+ but not in
any consistent consequence of SRP that proves RCA_0. Propositions 3.1
- 3.3 are provably equivalent to Con(SRP) over WKL_0. Propositions
3.2, 3.3 are provably equivalent to Con(SRP) over RCA_0.
4. VECTOR REDUCTION.
The games G(R,ush) are obviously based on vector reduction. I.e., Bob
is required to play a vector that reduces Alice's most recent play.
We now consider vector reduction independently of games.
Let A be a subset of Q^k. We define the cute of A, or cube(A), as the
least set B^k containing A. We define the field of A, or fld(A), as
the set of all coordinates of elements of A. Note that cube(A) =
fld(A)^k.
We define the upper shift of A, as the set of all upper shift of
elements of A. We define the inclusive upper shift of A as A union the
upper shift of A.
Let R be a subset of Q^2k. We say that A is R free if and only if no
two distinct elements of A are related by R.
We say that B is an R reduction of A if and only if
i. (forall x in A)(therexists y in B)(x R y).
ii. Clause i fails for all proper subsets of B.
THEOREM 4.1. Free Reduction Theorem. Let R contained in Q^2k be a
reducer. Every finite A contained in Q^k has a unique R free R
reduction contained in A. In fact, every S contained in Q^k with well
ordered field, has a unique R free R reduction contained in S.
THEOREM 4.2. Let R contained in Q^2k be an order invariant reducer.
Every finite A contained in Q^k has an R reduction whose inclusive
upper shift if R free.
Now fix R contained in Q^2k and A contained in Q^k. We define the
"cubic R reduction sequences" as follows. These are finite or infinite
sequences of subsets A_1,A_2,... of Q^k such that for all 1 <= i <
lth(alpha), A_i+1 is an R reduction of cube(A_i). Cubic R reduction
sequences can have any length from 1 through infinity.
The proper union of a cubic R reduction sequence is the union of all
of its terms after A_1.
THEOREM 4.3. Let R contained in Q^2k be a reducer and S be a well
ordered subset of Q. S^k starts a unique cubic R reduction sequence of
infinite length whose proper union is an R free subset of S^k.
PROPOSITION 4.4. Let R contained in Q^2k be an order invariant
reducer. Every A_1 contained in Q^k with well ordered field starts a
cubic R reduction sequence of infinite length, where the inclusive
upper shift of its proper union is R free.
PROPOSITION 4.5. Let R contained in Q^2k be an order invariant
reducer. Every finite A_1 contained in Q^k starts a cubic R reduction
sequence of length 3, where the inclusive upper shift of its proper
union is R free.
The "cubic,+1 R reduction sequences" are the finite or infinite
sequences alpha of subsets A_1,A_2,... of Q^k such that for all 1 <= i
< lth(alpha), A_i+1 is an R reduction of cube(A_i + {0,1}).
PROPOSITION 4.6. Let R contained in Q^2k be an order invariant
reducer. {(0,...,0)} starts a cubic,+1, R reduction sequence of length
k, where the inclusive upper shift of its proper union is R free.
Note that Propositions 4.5 and 4.6 are Pi01 because of the obvious
bounds that can be placed on the complexity of its noninitial terms,
relative to the complexity of the initial term.
THEOREM 4.7. Propositions 4.4 - 4.6 are provable in SRP+ but not in
any consistent consequence of SRP that proves RCA_0. Propositions 4.5,
4.6 are provably equivalent to Con(SRP) over EFA.
We expect to be making postings claiming the independence of yet more
concrete statements with large cardinals.
5. TEMPLATING.
As in earlier FOM postings, we can view ush:Q into Q as an example of
a partial piecewise linear function with rational coefficients from Q
into Q. We can ask what happens if we replace ush with such a partial
function. Or even with several such functions. What equivalences do we
get with metamathematical statements?
Another aspect worth templating is the definition of reducer. This is
a condition on R involving x R y, max(x), max(y), <. It's a bit
premature for me to worry about the exact setup for this templating,
but I envision first a separate templating of ush and of reducer.
Then, a combined templating of ush and of reducer.
Even order invariance is subject to templating, by introducing the
relation of order equivalence into the mix.
Right now, the emphasis is on more specific forms of these independent
statements that are still independent.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 390th 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
382: Upper Shift Greedy Cliques and Large Cardinals 12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09 3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences 1/1/10 7:35PM
386: Terrifically and Extremely Long Finite Sequences 1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos 1/6/10 10:41PM
388: Goedel's Second Again/definitive? 1/7/10 11:06AM
389: Finite Games and Large Cardinals 1 2/9/10 3:32PM
Harvey Friedman
More information about the FOM
mailing list