[FOM] 374:Upper Shift Greedy Chain Games

[Harvey Friedman]

The current state of the art is http://www.cs.nyu.edu/pipermail/fom/2009-December/014221.html

We now correct a typo there, involving the background result we called  
The Greedy Chain Theorem. The real action starts with the Upper Shift  
Greedy Chain Theorem, and the typo is not connected to that.

We wrote

THEOREM 2.1. THE GREEDY CHAIN THEOREM. Let R be contained in
Q^k x Q^k, and S be a subset of Q. The following are equivalent.
i. There is an S-greedy chain for R contained in S^k.
ii. S is a well ordered subset of Q.

The quantifiers are flipped. This should read

THEOREM 2.1. THE GREEDY CHAIN THEOREM. Let S be contained in Q. The
following are equivalent.
i. For all R contained in Q^k x Q^k, there is an S-greedy chain for R
contained in S^k.
ii. S is a well ordered subset of Q.

**********

We have found an improvement in the finite game. Such improvements,  
although small, add up nicely in the long run!

THIS IS A SELF CONTAINED ABSTRACT.

Let R be contained in Q^k x Q^k. We say that A is an R chain if and
only if for all distinct x,y in A, R(x,y).

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 R contained in Q^k x Q^k is order invariant if and only if
R is order invariant as a subset of Q^2k.

We define the upper shift function us:Q into Q, by us(q) = q+1 if q >=
0; q otherwise.

The function us naturally lifts to us:Q^k into Q^k by acting
coordinatewise. I.e., the upper shift of x in Q^k is obtained by
adding 1 to all of its nonnegative coordinates.

The upper shift of A is the set of upper shifts of its elements. I.e.,
us(A) = {us(x): x in A}.

THE UPPER SHIFT GREEDY CHAIN GAMES

Let R be contained in Q^k x Q^k. We present the game G(R,n), where 1
<= n <= infinity.

In G(R,n), Alice and Bob alternately make n moves, starting with  
Alice. Every move of Alice and Bob is an element of Q^k.

There is no restriction on Alice's first move. Every subsequent move  
of Alice is required to consist of rationals, each of which has  
appeared in earlier moves of the game (by Alice or by Bob).

Suppose Alice has just played x in Q^k. If this is an odd numbered  
move of Alice (counting from 1 through n), then Bob is required to  
play either x, or some y with max(y) <= max(x), such that x,y are  
distinct and {x,y} does not form an R chain.

If this is an even numbered move of Alice, then Bob is required to  
play the upper shift of Bob's previous move. Thus, Bob ignores Alice's  
even numbered moves.

Bob is considered the winner if and only if Bob's set of moves forms  
an R chain.

PROPOSITION 1. For all order invariant R contained in Q^k x Q^k, and
1 <= n <= infinity, Bob wins the game G(R,n).

PROPOSITION 2. For all order invariant R contained in Q^k x Q^k, and
n >= 1, Bob wins the game G(R,n).

Proposition 2 is not explicitly arithmetical. We can easily give  
explicitly Pi02 and Pi01 forms as follows.

PROPOSITION 3. For all order invariant R contained in Q^k x Q^k, and t  
 >> k,n >= 1, Bob wins G(R,n) if the rationals used by Alice and Bob  
are required to be shifts of the rationals used in Alice's first move,  
by: various multiples of 1/t lying in [-t,t].

PROPOSITION 4. In Proposition 3, it suffices to use any t > (8k)^2n.  
(This is far from best possible).

THEOREM 5. Propositions 1-4 are provably equivalent over RCA_0  
(exponential function arithmetic), to Con(SRP). Propositions 3,4 are  
provably equivalent, over EFA (exponential function arithmetic) to  
Con(SRP).

Recall that SRP = ZFC + {there is a limit ordinal with the k- 
stationary Ramsey property}_k.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 374th 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

Harvey Friedman