[FOM] 361: Finite Promise Games
Harvey Friedman
friedman at math.ohio-state.edu
Wed Sep 2 13:02:05 EDT 2009
We have had the idea that perhaps it would be even more elementary to
have Bob make PROMISES during the game. Then Bob wins the game if and
only if all of Bob's PROMISES are kept.
I had thought till now that this was purely cosmetic, and might even
obscure the mathematical content - i.e., possible connections with
core mathematics.
However, I now realize that bringing in promises during the game
serves to open up new possibilities for further simplifications of the
game - especially from the point of view of the nonprofessional.
FINITE INTEGER GAMES WITH PROMISES
by
Harvey M. Friedman
September 2, 2009
As usual, SMAH+ = ZFC + "for all k there is a strongly k-Mahlo
cardinal". SMAH = ZFC + {there is a strongly k-Mahlo cardinal}_k. That
various two person games can be won, is provable in SMAH+ but not in
ZFC.
1. Finite PL Copy/Inversion game.
2. Finite Polynomial PL Copy/Inversion game.
3. Finite Order Invariant Copy/Inversion game.
4. Finite Linear Copy/Inversion game.
1. FINITE PL COPY/INVERT GAMES.
Z is the set of all integers. N is the set of all nonnegative
integers. All letters represent integers.
We say that T:N^k into N is PL if and only if it is piecewise linear
with integer coefficients. I.e., T can be defined by various affine
functions with integer coefficients on each of finitely many pieces,
where each piece is defined by a finite set of linear inequalities
with integer coefficients.
Let T:N^k into N be PL. A T inversion of x is some y_1,...,y_k < x
such that T(y_1,...,y_k) = x.
We now define the game G(T,n,s), n,s >= 1. G(T,n,s) consists of n
alternating plays by Alice and Bob.
At every stage of the game, Alice is required to play x in [0,s] of
the form y + z or w!, where y,z are integers previously played by Bob
(Alice's offering). Bob is then required to
(accept x) play x and PROMISE that there will be no T inversion of x
among the integers ever played by Bob; or
(reject x) PROMISE that x is never played by Bob, and play a T
inversion of x.
AS IN ALL GAMES THROUGHOUT THIS ABSTRACT, Bob wins if and only if Bob
has kept all of his PROMISES. We will not mention this obvious winning
condition again.
THEOREM 1.1. Let T be in PL and n,s >= 1. Bob wins G(T,n,s).
PROPOSITION 1.2. Let T be in PL and n >= 1. If m,s are sufficiently
large then Bob wins G(T,n,s) even if Bob accepts all factorials > m
offered by Alice.
THEOREM 1.3. Theorem A1.1 is provable in RCA_0. Proposition 1.2 is
provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition 1.2 is provably equivalent, in ACA, to 1-Con(SMAH). The
"sufficiently large" as a function of T,n is a provably recursive
function of SMAH+ that eventually dominates all provably recursive
functions of SMAH. For each n, Proposition 1.2 is provable in RCA_0,
but the proofs grow in length as n increases, according to a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH.
2. FINITE POLYNOMIAL COPY/INVERT GAMES.
Let P:Z^k into Z be a polynomial with integer coefficients. A special
P inversion at x in Z consists of 0 < y_1,...,y_n < x/2 such that
P(y_1,...,y_n) = x.
We now define the game G(P,Q,n,s), n,s >= 1, where P,Q:Z^k into Z are
polynomials with integer coefficients. G(P,Q,n,s) consists of n
alternating plays by Alice and Bob.
At every stage of the game, Alice is required to play x in [-s,s] of
the form P(y), Q(y), or z!!, where y is a k tuple of integers
previously played by Bob (Alice's offering). Bob is then required to
(accept x) play x and PROMISE that there will be no special P or Q
inversion of x among the integers ever played by Bob; or
(reject x) PROMISE that x is never played by Bob, and play a special P
or Q inversion of x.
THEOREM 2.1. Let P,Q:Z^k into Z be polynomials with integer
coefficients, and n,s >= 1. Bob wins G(P,Q,n,s).
PROPOSITION 2.2. Let P,Q:Z^k into Z be polynomials with integer
coefficients, and n >= 1. If m,s are sufficiently large then Bob wins
G(P,Q,n,s) even if Bob accepts all double factorials > m offered by
Alice.
THEOREM 2.3. Theorem 2.1 is provable in RCA_0. Proposition 2.2 is
provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition 2.2 is provably equivalent, in ACA, to 1-Con(SMAH). The
"sufficiently large" as a function of P,Q,n is a provably recursive
function of SMAH+ that eventually dominates all provably recursive
functions of SMAH. For each n, Proposition 2.2 is provable in RCA_0,
but the proofs grow in length as n increases, according to a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH.
3. FINITE ORDER INVARIANT COPY/INVERT GAMES.
Let R be contained in N^2k be order invariant. An R inversion of
x_1,...,x_k consists of some y_1,...,y_k such that max(y_1,...,y_k) <
max(x_1,...,x_k) and R(x_1,...,x_k,y_1,...,y_k).
We now define the game G(R,n,s), n,s >= 1. G(R,n,s) consists of n
alternating plays by Alice and Bob.
At every stage of the game, Alice is required to play k integers
x_1,...,x_k in [-s,s], each of the form z or z+1 or w!, where z is an
integer previously played by Bob (Alice's offering). Bob is then
required to
(accept x) play x_1,...,x_k and PROMISE that no R inversion of
x_1,...,x_k is the k tuple ever simultaneously played by Bob; or
(reject x) PROMISE that x_1,...,x_k is not the k tuple ever
simultaneously played by Bob, and play an R inversion of x_1,...,x_k.
THEOREM 3.1. Let R contained in N^2k be order invariant and n,s >= 1.
Bob wins G(R,n,s).
PROPOSITION 3.2. Let R contained in N^2k be order invariant and n,s >=
1. Bob wins G(R,n,s) even if Bob always plays outside the interval
((8kn)!/2,(8kn)!).
Note that Proposition 3.2 is explicitly Pi01.
THEOREM 3.3. Theorem 3.1 is provable in RCA_0. Proposition 3.2 is
provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition 3.2 is provably equivalent, in ACA, to Con(SMAH).
Note how large factorials are being protected from below. They are
"limit points".
4. FINITE LINEAR COPY/INVERT GAMES.
DEFINITION. We say that x,y in N^k are additively equivalent if and
only if the following holds. Suppose some given length <= k sum of
coordinates of x is less than another given length <= k sum of
coordinates of x. Then the corresponding length <= k sum of
coordinates of y is less than the corresponding length <= k sum of
coordinates of y.
We now define the game G(v_1,...,v_p;n,s), p,n,s >= 1, v_1,...,v_p in
N^k. G(v_1,...,v_p;n,s) consists of n alternating plays by Alice and
Bob.
At every stage of the game, Alice is required to play an integer x in
[0,x] of the form y + z or w!, where y,z are integers previously
played by Bob (Alice's offering). Bob is then required to
(accept x) play x and PROMISE that x cannot be written as y_1 + ... +
y_k, where (y_1,...,y_k) is additively equivalent to some v_j, and
y_1,...,y_k are integers played by Bob at various times: or
(reject x) PROMISE that x is never played by Bob, and play
y_1,...,y_k, where x = y_1 + ... + y_k and (y_1,...,y_k) is additively
equivalent to some v_j.
THEOREM 4.1. Let v_1,...,v_p be in N^k and n,s >= 1. Bob wins
G(v_1,...,v_p;n,s).
PROPOSITION 4.2. Let v_1,...,v_p be in N^k and n,s >= 1. If m is
sufficiently large then Bob wins G(v_1,...,v_p;n,s) even if Bob
accepts all factorials > m offered by Alice.
THEOREM 4.3. Theorem A4.1 is provable in RCA_0. Proposition A4.2 is
provable in SMAH+ but not in any consistent fragment of SMAH.
Proposition A4.2 is provably equivalent, in ACA, to 1-Con(SMAH). The
"sufficiently large" as a function of v_1,...,v_p is a provably
recursive function of SMAH+ that eventually dominates all provably
recursive functions of SMAH. For each n, Proposition 4.2 is provable
in RCA_0, but the proofs grow in length as n increases, according to a
provably recursive function of SMAH+ that eventually dominates all
provably recursive functions of SMAH.
*************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 361s6 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 n/a 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 6:14PM
Harvey Friedman
More information about the FOM
mailing list