[FOM] 361: Finite Promise Games

[Harvey Friedman]

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