[FOM] 362: Simplest Order Invariant Game

[Harvey Friedman]

The order invariant games have the big advantage that there is no talk  
about "sufficiently large". Also, order invariant relations are nearly  
the most concrete relations.

In every dimension k, there are only finitely many order invariant  
relations, where the number is given by some double exponential  
expression in k.

Furthermore, we can always broaden out the order invariant relations  
to the piecewise linear relations with integer coefficients, or even  
the rationally semi algebraic relations restricted to N. The  
independence results still hold with minor modifications.

So we now concentrate on the order invariant relations, and make  
further serious simplifications in the games.

THIS HAS THE LOOK AND FEEL OF THE VERSION TO BE CHECKED IN DETAIL AND  
WRITTEN UP SOON FOR PUBLICATION!

Let R be a subset of N^2k. For x in N^k, an R inversion at x is a y in  
N^k such that max(y) < max(x) and R(y,x).

PARAMETERS. We will use k for the dimension and n for the length of  
the game. We will use s to bound the integers played. The fourth  
parameter is an order invariant R contained in [0,s]^2k. Here order  
invariant means that if 0 <= n_1,...,n_k,m_1,...,m_k <= s, and the  
order types of n_1,...,n_k and m_1,...,m_k are the same, then  
R(n_1,...,n_k) iff R(m_1,...,m_k).

GAME STRUCTURE. G(R,k,n,s). Alice and Bob make n alternating plays.  
Every play by Alice and Bob has two parts. For both players, the  
integer part is a single integer from [0,(8kn)!), and the vector part  
is a k tuple of integers from [0,s]. Thus, during the course of the  
game, each player creates n integer parts and n vector parts.  
Repetitions of any kind are allowed. The integer plays are taken to be  
the integer parts together with the components of the vector parts.  
The vector plays are taken to be the vector parts. Thus at every  
stage, each player makes k+1 integer plays and 1 vector play, for a  
total of n(k+1) integer plays and n vector plays, during the course of  
the game.

Here (8kn)! is just some convenient definite overkill number. When  
things settle down, I can come up with a number in k,n that is more  
sensitive.

EXAMPLE OF STRUCTURE. k = 3, n = 4, s = 1000. R irrelevant (so far).
Alice: 10,000  (85,0,11567)
Bob: 7  (0,654,130)
Alice: 9826  (35,1000,0)
Bob: 35095  (35,1000,0)
Alice: 0  (3420,234,1)
Bob: 35095  (0,99,35)
Alice: 10,000  (97,17,2985098)
Bob: 7  (2876,0,3)

These numbers are very arbitrary and have absolutely no significance.  
They just illustrate the structure.

REQUIREMENTS ON ALICE. At a given stage, Alice must play an integer  
x_0 from [0,(8kn)!) and integers x_1,...,x_k from [0,s]. It is  
required that each x_i be a previous integer play of Bob, or a  
factorial.

REQUIREMENTS ON BOB. In response to Alice, Bob must play an integer y  
from (x_0,(8kn)!). Also Bob must

(accept) play x_1,...,x_k and PROMISE that there is no R inversion of  
x_1,...,x_k among Bob's integer plays; or
(reject) PROMISE x_1,...,x_k is not a vector part of Bob, and play  
some R inversion of x_1,...,x_k.

Bob WINS THE GAME if and only if the game has finished and Bob has  
kept all of his PROMISES.

THEOREM 1. Bob wins G(R,k,n,s) if we remove the requirement on y. We  
do not need that R is order invariant.

PROPOSITION 2. Bob wins G(R,k,n,s).

Note that Proposition 2 is explicitly Pi01.

THEOREM 3. Proposition 2 is provable in SMAH+ but not in any  
consistent fragment of SMAH. Proposition 2 is provably equivalent, in  
ACA, to Con(SMAH).

Theorem 3 holds even if k is very small and n varies, or n is very  
small and k varies. Just how small we can take these numbers to be  
will be investigated soon - assuming this remains the FEATURED version.

Also, if n,k are both fixed then the statement is provable in EFA.  
However, there is the real possibility that if we fix n,k,s to be all  
small, then any proof in ZFC would still have to be ridiculously long  
- with a proof in 25 pages in SMAH+. We shall see...


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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 359th 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  9/2/09  12:08PM
361: Finite Promise Games

Harvey Friedman