[FOM] 354: Mahlo Cardinals in HIGH SCHOOL 1
Harvey Friedman
friedman at math.ohio-state.edu
Sun Aug 9 14:45:40 EDT 2009
I was preparing Function Generation 2. I suddenly realized that a form
of the story can be given in high school.
HIGH SHCOOL GAME WITH FUNCTION
We are going to play a game. We start by my giving you any function f
from length k vectors of positive integers into positive integers.
I.e., f:Z+^k into Z+.
The rest of the game is a solitaire game, where you are in complete
control.
The game consists of k rounds of play. During these rounds, you insert
positive integers into a basket. You are not allowed to take any
numbers out of the basket.
You win the game if and only if the contents of the basket at the end
of round k (the final set) forms an f-independent set in the following
sense: no integer in the set is the value of f at strictly smaller
integers in the set.
WARNING: This definition of f-independence is a bit nonstandard. It is
often stated without the numerical condition.
In the first round, you simply choose any set of positive integers
that you like, and throw them into the basket. Of course, you will
want your first round set to be f-independent, in order to have a
chance to win the game.
EXERCISE: This can always be done. I.e., if the game has only one
round, then you can win.
The second round has the following rules.
You first list all sums of pairs of numbers in the basket in strictly
numerical order. These are called the candidates. I.e., they are
candidates for being inserted into the basket. Don't worry that some
of the candidates may already be in the basket. You go through these
candidates, one by one, in numerical order. You either throw candidate
n into the basket; or, instead, you choose positive integers
m_1,...,m_k < n such that f(m_1,...,m_k) = n, and throw m_1,...,m_k
into the basket. Don't worry if some or all of the m's that you choose
are already in the basket.
You have thus, generally speaking, enlarged the basket by the end of
the second round.
The third round proceeds in exactly the same way, based on what is in
the basket at the end of the second round.
Continue for k rounds. OF course, if k = 1, then there is only one
round, and if k = 2, then there is only two rounds.
As I said earlier, you win the game if and only if the contents of the
basket, at the end of the final, k-th round, forms an f-independent set.
EXERCISE: For any f:Z+^k into Z+, you can win this game, even if your
first play is required to infinite. In fact, you can win this game by
cleverly picking the right first round infinite f-independent set,
with the amazing property that you can play all subsequent rounds in
such a way that this exact same set is the result at all subsequent
rounds. This means that, in fact, you can win this game even if there
are infinitely many rounds!!
HIGH SCHOOL GAME WITH FUNCTION - ODD INTEGER RULE
Here is the challenge: to win the game, where, for your first play,
you throw AN INFINITE SET OF ODD INTEGERS into the basket (and nothing
else). This requirement is intended only for the first round.
Note that this requirement causes no difficulties for the first round.
However, it creates subtle difficulties for later rounds.
**********************
SMAH+ = ZFC + "for all k there is a strongly k-Mahlo cardinal". SMAH =
ZFC + {there is a strongly k-Mahlo cardinal}_n.
PROPOSITION 1. For all f:N^k into N, the high school game with f and
the odd integer rule is winnable.
PROPOSITION 2. For all f:N^k into N, the odd high school game with f
and the odd integer rule, using <=k sums (instead of sums of pairs),
is winnable.
PROPOSITION 3. Let p,t >> k. For all unit piecewise linear f:[1,t]^k
into [1,t], the high school game with f and first round play
{1,p,p^2,...,p^t} is winnable.
PROPOSITION 4. Let p,t >> k. For all unit piecewise linear f:[1,t]^k
into [1,t], the high school game with f and first round play
{1,p,p^2,...,p^t}, using <=k sums (instead of sums of pairs), is
winnable.
Note that Propositions 3,4 is explicitly Pi03.
THEOREM 5. SMAH+ proves Propositions 1-4. Propositions 1-4 are not
provable in any consistent fragment of SMAH. Propositions 1-4 are
provably equivalent, in ACA, to 1-Con(SMAH). The same holds for
Propositions 2,4 even if we restrict the number of rounds to 3.
*************************
We now use a binary relation on Z+^k instead of a function from Z+^k
into Z+. The purpose of changing the setting is to develop an
explicitly Pi01 sentence.
HIGH SHCOOL GAME WITH RELATION
We are going to play a game. We start by my giving you any relation
binary relation on the length k vectors of positive integers. I.e., R
is a subset of Z+^k x Z+^k.
The rest of the game is a solitaire game, where you are in complete
control.
We write x R y to indicate that x is related by R to y. This just
means that the ordered pair (x,y) lies in R.
For length k vectors x, we write x+1 for the successor of x, which is
obtained by adding 1 to all coordinates of x.
For any subset E of Z+^k, we write E+1 for the successor of E, which
consists of all of the x+1 for x in E.
A cube in Z+^k is a set of the form S^k, where S is a set of positive
integers.
WARNING: This definition of cube is not standard. It arises naturally
in certain branches of mathematics (Ramsey theory).
Let E be a subset of Z+^k. The field of E is the set of all
coordinates of vectors in E. The cube of E is the set of all length k
vectors from the field of E.
The game consists of k rounds of play. During these rounds, you insert
length k vectors of positive integers into a basket. You are not
allowed to take any vectors out of the basket.
You win the game if and only if the contents of the basket at the end
of the k-th and last round, forms a set with the following property.
The vectors in the set, which are also successors of vectors in the
set, form an infinite R-independent set of vectors, in the following
sense: no one of them is related by R to any one of them with a
strictly greater maximum coordinate.
WARNING: This definition of R-independence is a bit nonstandard. It is
often stated without the numerical condition.
EXAMPLE: Assume the dimension k is 2. Suppose (3,2) R (2,5), and (2,1),
(3,2),(1,4),(2,5) are all in the set. This is a violation of the
requirement for winning, because 3 < 5.
In the first round, you are required to play any cube in N^k.
The second round has the following rules.
You first list all vectors in the cube of the vectors in the basket.
The exact way in which you list these is not important. However, you
can use the following definite way of listing them. List them first
according to the maximum coordinate, and second lexicographically.
(You can use any method of listing that you like, instead).
You go through these vectors, one by one, in the order listed. When
working on vector x, you either throw vector x+1 in the basket; or,
instead, you choose a vector y in Z+^k such that y+1 is related to x+1
by R (i.e., y R x), and the maximum coordinate of y is strictly
smaller than the maximum coordinate of x, and throw y,y+1 in the
basket. Don't worry if the vector(s) you decide to throw in is (are)
already in the set.
Subsequent rounds proceed in the same way, relative to the contents of
the basket at the end of the preceding round.
Continue for k rounds. Of course, if k = 1, then there is only one
round, and if k = 2, then there are only two rounds.
Remember, you win if and only if the contents of the basket at the end
of the last round forms a set with the following property: the set of
successors of elements of the set that are in the set, forms an R-
independent set.
**********************
PROPOSITION 6. For all R contained in N^k x N^k, the high school game
using R, where the first round play is required to be infinite, is
winnable.
PROPOSITION 7. For all order invariant R contained in N^k x N^k, the
high school game with R, where the first round play is required to be
infinite, is winnable.
PROPOSITION 8. Let p,t > (8k)!. For all order invariant R contained in
[1,t]^k x [1,t]^k, the high school game with R, where the first round
play is required to be {1,p,p^2,...,p^t}^k, is winnable.
Note that Proposition 8 is explicitly Pi01.
THEOREM 9. SMAH+ proves Propositions 6-8. Propositions 6-8 are not
provable in any consistent fragment of SMAH. Propositions 6-8 are
provably equivalent, in ACA, to Con(SMAH). The same holds for
Propositions 6-8 even if we restrict the number of rounds to 3.
**********************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 354th 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
Harvey Friedman
More information about the FOM
mailing list