[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