[FOM] 355: Mahlo Cardinals in HIGH SCHOOL 2

Harvey Friedman friedman at math.ohio-state.edu
Mon Aug 10 17:40:03 EDT 2009


WE CORRECT THE RELATION GAME (not the function game).

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

Here we modify the game so that the function f is a polynomial with  
integer coefficients. We use Z = set of all integers instead of the  
previous Z+ = the set of all positive integers.

I was deliberately verbose in http://www.cs.nyu.edu/pipermail/fom/2009-August/013912.html 
  in order to give an indication as to how these games can be  
explained to high schoolers. I will now stop putting in all this prose  
- until it is time to actually promote this in high schools.

Incidentally, one big help for making the previous high school game  
with function high school ready is to avoid k-ary functions, and  
instead use, say, arity 2 or 3. Perhaps the best would be arity 2 or  
3, with only 3 rounds, using <=k length sums. I have not had the time  
to focus on such selection of small parameters yet. Also, another  
ideal situation would be arity 2 or 3, 3 or 4 rounds, <= 4 length  
sums, and showing that in order to prove it, you can either use large  
cardinals with something like 20 pages, or stay in ZFC and use more  
than 2^2^2^2^2^1000 pages. Again, I have not had the time to focus on  
such computations.

There is also the matter of experimenting with particular simple f of  
small arity, such as affine functions from N^4 into Z. (We really do  
not need that the range of f is a subset of Z+). It may well be the  
case that even for such simple f, it might be very difficult to avoid  
using the large cardinals, even though it would also be very difficult  
to show that it is necessary.

Let me begin by restating the games from http://www.cs.nyu.edu/pipermail/fom/2009-August/013912.html 
  in ordinary *undergraduate* - not high school - mathematical terms.  
We also correct the High School Relation Game.

PREVIOUS HIGH SCHOOL GAME WITH FUNCTION

Let f:Z+^k into Z+. We define a solitaire game with k rounds. Each  
round results in a subset of Z+. The set resulting from a round is a  
subset of the set resulting from the succeeding rounds. The game is  
considered won if and only if no element of the final set is the value  
of f at strictly smaller elements of the final set.

At the first round, any subset of Z+ can be played.

Let X be the set resulting from round i, 1 <= i < k. At round i+1,  
(possibly) new integers are thrown into X by a specific  
nondeterministic process.

The player first enumerates the sums of pairs from X in numerical  
order (although this is not really important). These are the  
candidates for insertion into the set. For each candidate n, the  
player either throws n into the set, or instead writes n =  
f(m_1,...,m_k), m_1,...,m_k < n, and throws m_1,...,m_k into the set.  
It may be the case that numbers thrown into the set here are already  
in the set.

This game can be won, even if we require that the first round play be  
an infinite set of odd integers. However, it is necessary and  
sufficient to use large cardinals to prove this fact. It is  
equivalent, over ACA, to 1-Con(SMAH). The same results hold if f is  
required to be piecewise linear.

If f is piecewise linear and p,t are sufficiently large, then the game  
can be won with first play {1,p,p^2,...,p^t}. However, this also is  
equivalent to 1-Con(SMAH) over ACA.

PREVIOUS HIGH SCHOOL GAME WITH RELATION (CORRECTED)

Let R contained in Z+k x Z+k. We define a solitaire game with k  
rounds. Each round results in a subset of Z+^k. The set resulting from  
a round is a subset of the set resulting from the succeeding rounds.  
The game is considered won if and only if we do not have x,y,z in the  
final set, with x R y and max(x) < max(y) = max(z)+1.

In the first round, any S^k can be played, where S is a set of  
positive integers.

Let X be the set resulting from round i, 1 <= i < k. At round i+1,  
(possibly) new vectors are thrown into X by a specific  
nondeterministic process.

The player first enumerates all k tuples of the field of X (i.e., the  
cube generated by X). E.g., first by max, and second  
lexicographically, although the exact method of enumeration is not  
important. For each vector y in the list, the player either throws in  
y, or instead throws in x, where x R y and max(x) < max(y). It may be  
the case that vectors thrown into the set here are already in the set.

This game can be won, even if we require that the first round play be  
infinite. However, it is necessary and sufficient to use large  
cardinals to prove this fact. It is equivalent, over ACA, to  
Con(SMAH). The same results hold if R is required to be order  
invariant (as a subset of Z+^2k).

If R is order invariant, and p,t > (8k)!, then the game can be won  
with first play {1,p,p^2,...,p^t}^k. However, However, it is necessary  
and sufficient to use large cardinals to prove this fact. It is  
equivalent, over ACA, to Con(SMAH). This is an explicitly Pi01  
independence result.

NEW POLYNOMIAL HIGH SCHOOL GAME

Let P,Q:Z^k into Z be polynomials. We define a solitaire game with k  
rounds. Each round results in a subset of Z. The set resulting from a  
round is a subset of the set resulting from the succeeding rounds. The  
game is considered won if and only if no element n of the final set  
can be written as Q(m_1,...,m_k), where m_1,...,m_k is in the final  
set, and 0 <= m_1,...,m_k < n/2.

At the first round, any subset of Z can be played.

Let X be the set resulting from round i, 1 <= i < k. At round i+1,  
(possibly) new integers are thrown into X by a specific  
nondeterministic process.

The player first enumerates the elements of P[X^k] in increasing  
magnitude, with negatives before positives (although this is not  
really important). These are the candidates for insertion into the  
set. For each candidate n, the player either throws it into the set,  
or instead writes n = Q(m_1,...,m_k), 0 <= m_1,...,m_k < n/2, and  
throws m_1,...,m_k into the set. It may be the case that numbers  
thrown into the set here are already in the set.

This game can be won, even if we require that the first round play be  
an infinite set of positive integers. However, it is necessary and  
sufficient to use large cardinals to prove this fact. It is  
equivalent, over ACA, to 1-Con(SMAH).

If P,Q are polynomials and p,t are sufficiently large, then the game  
can be won with first play {p!!,(p+1)!!,...,t!!}. However, it is  
necessary and sufficient to use large cardinals to prove this fact. It  
is equivalent, over ACA, to 1-Con(SMAH). This is an explicitly Pi03  
independence result.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 355th 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

Harvey Friedman


More information about the FOM mailing list