[FOM] 359:finite two person HIGH SCHOOL games
Harvey Friedman
friedman at math.ohio-state.edu
Mon Aug 24 12:22:01 EDT 2009
We now discuss a new development - very elementary two person games.
It is slightly advantageous to use N = the set of nonnegative
integers, rather than Z+, for these games.
The most straightforward two person games arise out of piecewise
linear f:N^k into N, polynomials P:N^k into N, and order invariant
binary relations on N^k. We will restrict attention to these, at least
for now.
The restriction to these objects will not be a problem when the
material is sculpted for use in high school, undergrads, math
amateurs, etcetera, since the examples one might naturally use of
functions and relations are of this anyway.
All games considered are of finite length, with only finitely many
possible plays. I.e., entirely finite.
###############################
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 solitaire games can be won, is provable in SMAH+ but not in ZFC.
1. PL Copy/Inversion game.
2. Polynomial Copy/Inversion game.
3. Order Invariant Copy/Inversion games.
1. PL COPY/INVERSION GAME.
Let T:N^k into N be piecewise linear. This means that T is piecewise
defined by affine functions with integer coefficients, where each of
the finitely many pieces is defined by a set of linear inequalities
with integer coefficients.
A T inversion of x is some y_1,...,y_k < x such that f(y_1,...,y_k) = x.
We define a finite two person game, with Alice and Bob making n
alternating plays, n >= 1, subject to parameters m,s >= 1. We call
this the PL Copy/Inversion game with f,n,m,s.
Alice can play any nonnegative integers <= s during the course of the
game. Bob will play either a nonnegative integer or k nonnegative
integers, where in both cases, the integers played are <= m^s.
Bob's plays are subject to two rules. Suppose Alice plays x <= s.
RULE 1. x is the sum of a pair of integers previously played by Bob.
In this case, Alice has "challenged" Bob. Bob must copy or invert;
i.e., play x or a T inversion of x.
RULE 2. Otherwise. Bob must play m^x.
Bob is declared the winner if and only if
NO INTEGER PLAYED BY BOB HAS A T INVERSION AMONG THE INTEGERS PLAYED
BY BOB.
PROPOSITION 1.1. Let T:N^k into N be piecewise linear, and n >= 1. If
m,s are sufficiently large, then Bob wins the PL copy/inversion game
with f,n,m,s.
Note that Proposition 1.1 is explicitly Pi03.
THEOREM 1.2. Proposition 1.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition 1.2 is provably equivalent,
in ACA, to 1-Con(SMAH).
Theorem 1.2 holds for a small fixed k. A challenge is to see just how
small k can be. Getting k = 2 would be rather impressive.
How large do m,s have to be as a function of the "size" of T and n?
The growth rate is beyond any provably recursive function of SMAH. In
fact, for fairly small f,n, Proposition 1.1 cannot be proved in any
consistent fragment of SMAH, where the proof and the fragment uses
less than 2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2 symbols.
2. POLYNOMIAL COPY/INVERSION GAME.
Let P:Z^k into Z be a polynomial with integer coefficients. A special
P inversion of x is some 0 < y_1,...,y_k < x/2 such that
P(y_1,...,y_k) = x.
We define a finite two person game, Alice and Bob making n alternating
plays, n >= 1, subject to parameters m,s >= 1. We call this the
Polynomial Copy/Inversion game with P,n,m,s.
Alice can play any nonnegative integers <= s during the course of the
game. Bob will play either a positive integer or k nonnegative
integers, where in either case, all integers involved are <= (ms)!.
Bob's plays are subject to two rules. Suppose Alice plays x <= s.
RULE 1. x is the sum or difference or product of a pair of integers
previously played by Bob. In this case, Alice has "challenged" Bob.
Bob must copy or invert; i.e., play x or a special P inversion of x.
RULE 2. Otherwise. Bob must play (mx)!.
Bob is declared the winner if and only if
NO INTEGER PLAYED BY BOB HAS A SPECIAL f INVERSION AMONG THE INTEGERS
PLAYED BY BOB.
PROPOSITION 2.1. Let P:Z^k into Z be a polynomial with integer
coefficients, and n >= 1. If m,s are sufficiently large, then Bob wins
the polynomial copy/inversion game with P,n,m,s.
Note that Proposition 2.1 is explicitly Pi03.
THEOREM 2.2. Proposition 2.1 is provable in SMAH+ but not in any
consistent fragment of SMAH. Proposition 2.1 is provably equivalent,
in ACA, to 1-Con(SMAH).
Theorem 1.2 holds for a small fixed k. A challenge is to see just how
small k can be. Getting k = 2 would be rather impressive.
How large do m,s have to be as a function of the "size" of P and n?
The growth rate is beyond any provably recursive function of SMAH. In
fact, for fairly small P,n, Proposition 2.1 cannot be proved in any
consistent fragment of SMAH, where the proof and the fragment uses
less than 2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2 symbols.
3. ORDER INVARIANT COPY/INVERSION GAME.
Let R be an order invariant binary relation on N^k (order invariant as
a subset of N^2k). An R inversion of x is some y in N^k such that
max(y) < max(x) and R(y,x).
We define a finite two person game, Alice and Bob making n plays, n >=
1, subject to parameters m,s >= 1. We call this the Order Invariant
Copy/Inversion game with R,n,m,s.
Alice can play any x in [0,s]^k during the course of the game. Bob
will play elements of [0,m^s]^k.
Bob's plays are subject to two rules. Suppose Alice plays x in [0,s]^k.
RULE 1. x is the result of taking any k coordinates from various
previous plays of Bob, and adding 1 to at least one of them. In this
case, Alice has "challenged" Bob. Bob must copy or invert; i.e., play
x or an R inversion of x.
RULE 2. Otherwise, Bob must play m^x, evaluated coordinatewise.
Bob is declared the winner if and only if
NONE OF ALICE'S CHALLENGES HAS AN R INVERSION PLAYED BY BOB.
PROPOSITION 3.1. Let R be an order invariant binary relation on N^k,
and n >= 1. If m,s are sufficiently large, then Bob wins the order
invariant copy/invert game with R,n,m,s.
PROPOSITION 3.2. Let R be an order invariant binary relation on N^k,
and m,s > 8kn >= 1. Then Bob wins the order invariant copy/invert game
with R,n,m,s.
Note that Proposition 3.2 is explicitly Pi01.
THEOREM 3.3. Propositions 3.1, 3.2 are provable in SMAH+ but not in
any consistent fragment of SMAH. Propositions 3.1, 3.2 are provably
equivalent, in ACA, to Con(SMAH).
Theorem 1.2 holds for a small fixed k. A challenge is to see just how
small k can be. Getting k = 2 would be rather impressive, k = 4 more
realistic.
We anticipate showing that for reasonably small k,n,m,s, Proposition
3.2 is provable in SMAH+ in about 50 pages, but not provable in ZFC
using 2^2^1000 symbols, even with abbreviations.
**********************
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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected
from the original.
250. Extreme Cardinals/Pi01 7/31/05 8:34PM
251. Embedding Axioms 8/1/05 10:40AM
252. Pi01 Revisited 10/25/05 10:35PM
253. Pi01 Progress 10/26/05 6:32AM
254. Pi01 Progress/more 11/10/05 4:37AM
255. Controlling Pi01 11/12 5:10PM
256. NAME:finite inclusion theory 11/21/05 2:34AM
257. FIT/more 11/22/05 5:34AM
258. Pi01/Simplification/Restatement 11/27/05 2:12AM
259. Pi01 pointer 11/30/05 10:36AM
260. Pi01/simplification 12/3/05 3:11PM
261. Pi01/nicer 12/5/05 2:26AM
262. Correction/Restatement 12/9/05 10:13AM
263. Pi01/digraphs 1 1/13/06 1:11AM
264. Pi01/digraphs 2 1/27/06 11:34AM
265. Pi01/digraphs 2/more 1/28/06 2:46PM
266. Pi01/digraphs/unifying 2/4/06 5:27AM
267. Pi01/digraphs/progress 2/8/06 2:44AM
268. Finite to Infinite 1 2/22/06 9:01AM
269. Pi01,Pi00/digraphs 2/25/06 3:09AM
270. Finite to Infinite/Restatement 2/25/06 8:25PM
271. Clarification of Smith Article 3/22/06 5:58PM
272. Sigma01/optimal 3/24/06 1:45PM
273: Sigma01/optimal/size 3/28/06 12:57PM
274: Subcubic Graph Numbers 4/1/06 11:23AM
275: Kruskal Theorem/Impredicativity 4/2/06 12:16PM
276: Higman/Kruskal/impredicativity 4/4/06 6:31AM
277: Strict Predicativity 4/5/06 1:58PM
278: Ultra/Strict/Predicativity/Higman 4/8/06 1:33AM
279: Subcubic graph numbers/restated 4/8/06 3:14AN
280: Generating large caridnals/self embedding axioms 5/2/06 4:55AM
281: Linear Self Embedding Axioms 5/5/06 2:32AM
282: Adventures in Pi01 Independence 5/7/06
283: A theory of indiscernibles 5/7/06 6:42PM
284: Godel's Second 5/9/06 10:02AM
285: Godel's Second/more 5/10/06 5:55PM
286: Godel's Second/still more 5/11/06 2:05PM
287: More Pi01 adventures 5/18/06 9:19AM
288: Discrete ordered rings and large cardinals 6/1/06 11:28AM
289: Integer Thresholds in FFF 6/6/06 10:23PM
290: Independently Free Minds/Collectively Random Agents 6/12/06
11:01AM
291: Independently Free Minds/Collectively Random Agents (more) 6/13/06
5:01PM
292: Concept Calculus 1 6/17/06 5:26PM
293: Concept Calculus 2 6/20/06 6:27PM
294: Concept Calculus 3 6/25/06 5:15PM
295: Concept Calculus 4 7/3/06 2:34AM
296: Order Calculus 7/7/06 12:13PM
297: Order Calculus/restatement 7/11/06 12:16PM
298: Concept Calculus 5 7/14/06 5:40AM
299: Order Calculus/simplification 7/23/06 7:38PM
300: Exotic Prefix Theory 9/14/06 7:11AM
301: Exotic Prefix Theory (correction) 9/14/06 6:09PM
302: PA Completeness 10/29/06 2:38AM
303: PA Completeness (restatement) 10/30/06 11:53AM
304: PA Completeness/strategy 11/4/06 10:57AM
305: Proofs of Godel's Second 12/21/06 11:31AM
306: Godel's Second/more 12/23/06 7:39PM
307: Formalized Consistency Problem Solved 1/14/07 6:24PM
308: Large Large Cardinals 7/05/07 5:01AM
309: Thematic PA Incompleteness 10/22/07 10:56AM
310: Thematic PA Incompleteness 2 11/6/07 5:31AM
311: Thematic PA Incompleteness 3 11/8/07 8:35AM
312: Pi01 Incompleteness 11/13/07 3:11PM
313: Pi01 Incompleteness 12/19/07 8:00AM
314: Pi01 Incompleteness/Digraphs 12/22/07 4:12AM
315: Pi01 Incompleteness/Digraphs/#2 1/16/08 7:32AM
316: Shift Theorems 1/24/08 12:36PM
317: Polynomials and PA 1/29/08 10:29PM
318: Polynomials and PA #2 2/4/08 12:07AM
319: Pi01 Incompleteness/Digraphs/#3 2/12/08 9:21PM
320: Pi01 Incompleteness/#4 2/13/08 5:32PM
321: Pi01 Incompleteness/forward imaging 2/19/08 5:09PM
322: Pi01 Incompleteness/forward imaging 2 3/10/08 11:09PM
323: Pi01 Incompleteness/point deletion 3/17/08 2:18PM
324: Existential Comprehension 4/10/08 10:16PM
325: Single Quantifier Comprehension 4/14/08 11:07AM
326: Progress in Pi01 Incompleteness 1 10/22/08 11:58PM
327: Finite Independence/update 1/16/09 7:39PM
328: Polynomial Independence 1 1/16/09 7:39PM
329: Finite Decidability/Templating 1/16/09 7:01PM
330: Templating Pi01/Polynomial 1/17/09 7:25PM
331: Corrected Pi01/Templating 1/20/09 8:50PM
332: Preferred Model 1/22/09 7:28PM
333: Single Quantifier Comprehension/more 1/26/09 4:32PM
334: Progress in Pi01 Incompleteness 2 4/3/09 11:26PM
335: Undecidability/Euclidean geometry 4/27/09 1:12PM
336: Undecidability/Euclidean geometry/2 4/29/09 1:43PM
337: Undecidability/Euclidean geometry/3 5/3/09 6:54PM
338: Undecidability/Euclidean geometry/4 5/5/09 6:38PM
339: Undecidability/Euclidean geometry/5 5/7/09 2:25PM
340: Thematic Pi01 Incompleteness 1 5/13/09 5:56PM
341: Thematic Pi01 Incompleteness 2 5/21/09 7:25PM
342: Thematic Pi01 Incompleteness 3 5/23/09 7:48PM
343: Goedel's Second Revisited 1 5/27/09 6:07AM
344: Goedel's Second Revisited 2 6/1/09 9:21PM
345: Thematic Pi01 Incompleteness 4 6/15/09 1:15PM
appears misnumbered as 344.
346: Goedel's Second Revisited 3 6/16/09 11:04PM
347: Goedel's Second Revisited 4 6/20/09 1:25AM
348: Goedel's Second Revisited 5 6/22/09 11:00AM
349: Pi01 Incompleteness/set series 7/20/09 11:21PM
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
Harvey Friedman
More information about the FOM
mailing list