[FOM] 362: Simplest Order Invariant Game
Harvey Friedman
friedman at math.ohio-state.edu
Thu Sep 3 12:42:09 EDT 2009
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
More information about the FOM
mailing list