[FOM] 393: Finite Games, Vector Reduction, and Large Cardinals 5
Harvey Friedman
friedman at math.ohio-state.edu
Mon Feb 22 03:50:43 EST 2010
In this installment, we focus only on TWO ROUND GAMES, where Alice and
Bob both play finite lists of nonempty finite sets of rationals, of
the same length.
*****************************
TWO ROUND GAMES BASED ON FINITE SETS OF RATIONALS
by
Harvey M. Friedman
February 22, 2010
1. TWO ROUND GAMES.
2. VARIANTS IN THE TWO ROUND GAMES.
3. THREE HALF MOVE GAMES.
4. CHALLENGE.
1. TWO ROUND GAMES.
Let Q be the set of rationals and N be the set of nonnegative
integers. Let NS(Q,<=k) be the space of nonempty finite subsets of Q
with at most k elements, k >= 1.
Let R be contained in NS(Q,<=k)^2. We view R as a binary relation on
NS(Q,<=k). We say that y is a strict R reduction of x if and only if x
R y and min(y) < min(x). We say that y is an R reduction of x if and
only if x = y or y is a strict R reduction.
We now define the two round game G2(R,<=k,n).
Alice and Bob alternately play a list of n elements of NS(Q,<=k),
Alice moving first. The game lasts only two rounds, so each player
makes a total of two moves.
Alice's first move can be any x_1,...,x_n from NS(Q,<=k).
Bob's first move must be some y_1,...,y_n such that each y_i is an R
reduction of x_i.
Alice's second move must be some z_1,...,z_n, each contained in x_1
union ... union x_n union y_1 union ... union y_n.
Bob's second move must be some w_1,...,w_n such that each w_i is an R
reduction of z_i.
BOB WINS G2(R,<=k,n) IF AND ONLY IF NONE OF y_1,...,y_n,w_1,...,w_n IS
A STRICT R REDUCTION OF ANY OF y_1,...,y_n,w_1,...,w_n.
THEOREM 1.1. For all R contained in NS(Q,<=k)^2 and n >= 1, Bob wins
G2(R,<=k,n).
We next define the two round game G2(R,<=k,n,ush). Recall the upper
shift function which is first defined on rationals by ush(q) = q+1 if
q >= 0; q otherwise. Define the upper shift of x in NS(Q,<=k) to be
given by ush(x) = ush[x].
The only difference between G2(R,<=k,n,ush) and G2(R,<=k,n) is the
winning condition for Bob, which is made more difficult:
BOB WINS G2(R,<=k,n,ush) IF AND ONLY IF NONE OF
y_1,...,y_n,w_1,...,w_n,ush(y_1),...,ush(y_n),ush(w_1),...,ush(w_n) IS
A STRICT R REDUCTION OF ANY OF
y_1,...,y_n,w_1,...,w_n,ush(y_1),...,ush(y_n),ush(w_1),...,ush(w_n).
PROPOSITION 1.2. For all order invariant R contained in NS(Q,<=k)^2
and n >= 1, Bob wins G2(R,<=k,n,ush).
PROPOSITION 1.3. For all order invariant R contained in NS(Q,<=k)^2,
Bob wins G2(R,<=k,k,ush).
PROPOSITION 1.4. For all order invariant R contained in NS(Q,<=k)^2
and n >= 1, Bob wins G2(R,<=k,n,ush), using only numerators and
denominators of magnitude at most (8knr)!, where the denominators and
numerators appearing in Alice's first move have magnitude at most r.
PROPOSITION 1.5. For all order invariant R contained in NS(Q,<=k)^2,
Bob wins G2(R,<=k,n,ush), using only numerators and denominators of
magnitude at most (8kr)!, where the denominators and numerators
appearing in Alice's first move have magnitude at most r.
Note that for each fixed k,R,n, Propositions 1.2,1.3 assert an
effectively obtained first order sentence in the very decidable
structure (Q,<,0,+1). In this sense, Propositions 1.2,1.3 are Pi01.
Note that Propositions 4,5 are explicitly Pi01. The factorial estimate
there is very crude but safe.
Let SRP+ = ZFC + (for all k)(there exists lambda with the k-SRP). Let
SRP = ZFC + {there exists lambda with the k-SRP}_k. Here SRP =
"stationary Ramsey property", which asserts that any partition of the
unordered k-tuples has a stationary homogenous set. The SRP hierarchy
is intertwined with the subtle, almost ineffable, and ineffable
cardinal hierarchies.
THEOREM 1.6. Propositions 1.2-1.5 are provable in SRP+ but not in any
consistent fragment of SRP that proves EFA. Propositions 2-5 are
provably equivalent to Con(SRP) over EFA.
For fixed small k, we already get independence from ZFC. The question
is: how small k is needed? I believe in the range from 4 to 6. This
requires some detailed work, which I don't have the time for now. I
think 4 is a nice challenge, and 3 would be unexpected.
2. VARIANTS IN THE TWO ROUND GAMES.
Here are some variants.
i. We can insist that Alice's second move consist of subsets of the
union of Bob's moves only.
ii. We can weaken the winning condition for Bob to read
BOB WINS IF AND ONLY IF NONE OF w_1,...,w_n IS A STRICT R REDUCTION OF
ANY OF y_1,...,y_n,w_1,...,w_n,ush(w_n).
iii. We can weaken the winning condition for Bob to read
BOB WINS IF AND ONLY IF NONE OF w_1,...,w_n IS A STRICT R REDUCTION OF
ANY OF y_1,...,y_n,w_1,...,w_n,ush(y_1).
We can make any subset of these three changes, and obtain the same
results.
3. THREE HALF MOVE GAMES.
Here we have Bob moving first, then Alice moves, and then Bob moves.
Bob's first move is some x_1,...,x_n in NS(Q,<=k), where each x_i is
an R reduction of (i-1,...,i+k-2).
Alice's only move is some y_1,...,y_n in NS(Q,<=k), each a subset of
x_1 union ... union x_n.
Bob's second move is some z_1,...,z_n in NS(Q,<=k).
BOB WINS IF AND ONLY IF NONE OF
x_1,...,x_n,z_1,...,z_n,ush(x_1),...,ush(x_n),ush(z_1),...,ush(z_n) is
a strict R reduction of any of
x_1,...,x_n,z_1,...,z_n,ush(x_1),...,ush(x_n),ush(z_1),...,ush(z_n).
We can also make modifications as before, including from section 2. We
obtain the same results.
CHALLENGE
Investigate Proposition 1.2 for k = 2, and various small n, using
accepted mathematical methods. There are 2^23 = 8,388,608 such R.
Consider using a computer.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 393rd 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, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3
392: Finite Games, Vector Reduction, and Large Cardinals 4
More information about the FOM
mailing list