[FOM] 364:Anticipation Function Games/Largest Cardinals/simplified
Harvey Friedman
friedman at math.ohio-state.edu
Sun Sep 6 23:29:46 EDT 2009
We found significant simplifications in Bob's move requirement. We
restate #363: Greedy Function Games/Largest Cardinals 1 accordingly.
Perhaps it is not so good an idea to link this up now with Greed. It
is more an issue of Anticipation. Hence we rename these three games
Basic Anticipation Function Game
Strong Anticipation Function Game
Wild Anticipation Function Game
In our simplified versions, all three of these games have exactly the
same parameters and exactly the same rules. The winning conditions for
Bob vary.
#################################
We formulate this basic Greedy Function Game in such a way that it
naturally strengthens to a version where Bob also wins, but this fact
is a Pi01 sentence that is independent of ZFC.
We then strengthen further so that extremely large cardinals are
required - stronger than a rank into itself.
1. Basic Anticipation Function Game.
2. Strong Anticipation Function Game.
3. Wild Anticipation Function Game.
1. BASIC ANTICIPATION FUNCTION GAME
The factorials are the integers 1!,2!,... .
GAME PARAMETERS. k,n,s >= 1, and an order invariant relation R
contained in [1,s]^2k+1.
GAME STRUCTURE. Alice and Bob make n alternating moves. Each move by
Alice is an element of [1,s]^k. Each move by Bob is a partial function
f:[1,s]^k into [1,s+1]. At each move, Bob plays a function extending
his previous move at at most one new argument, with a PROMISE FOR ThE
FUTURE. Bob's integer moves are considered to be the integers that
appear in his function (either in the domain or in the range).
ALICE'S MOVES. Alice plays x from [1,s]^k, with the requirement that
each coordinate is either a factorial or one of Bob's previous integer
moves.
BOB'S MOVES. Let f be Bob's previous move (the empty function if this
is Bob's first move). Bob is required to
(accept x) extend f by defining f'(x) > min(x) and PROMISE that, for
Bob's final move g, there will be no y with max(y) < max(x) and
R(x,y,g(y)); or
(reject x) PROMISE that, for Bob's final move g, g(x) will be
undefined, and define some f'(y) > min(y) with max(y) < max(x) and
R(x,y,f'(y)).
WINNING CONDITION. Bob is declared the winner of the Basic
Anticipation Function Game if and only if Bob has met all of his
PROMISES.
THEOREM 1.1. Bob wins the Basic Anticipation Function Game. This is
provable in RCA_0.
2. STRONG ANTICIPATION FUNCTION GAME
We play the Basic Anticipation Function Game, except that we impose an
additional requirement on Bob in order for Bob to be declared the
winner.
STRONG WINNING CONDITION. Bob is declared the winner of the game if
and only if Bob has met all of his PROMISES, where his final move
partially maps [1,(8kn)!)^k into [1,(8kn)!).
PROPOSITION 1.2. Bob wins the Strong Anticipation Function Game.
Note that Proposition 1.2 is an explicitly Pi01 sentence.
THEOREM 1.3. Proposition 1.2 is provable in SMAH+ but not in any
consistent finite fragment of SMAH. It is provably equivalent, in ACA,
to Con(SMAH).
3. WILD ANTICIPATION FUNCTION GAME
Here the explicitly Pi01 sentence expressing that Bob wins the Wild
Anticipation Function Game is trapped between the consistency of two
extremely strong large cardinal axioms. From Kanamori, The Higher
Infinite, page 325:
I1. For some alpha, there is a proper elementary embedding j:V(alpha +
1) into V(alpha + 1).
I2. There is a j:V into M such that V(alpha) is contained in M for
some alpha > crit(j) satisfying j(alpha) = alpha.
I3. For some alpha, there is a proper elementary embedding j:V(alpha)
into V(alpha).
The Pi01 sentence A below is provable in NBG + AxC + I2 but not in any
consistent fragment of ZFC + I3. The following is provable in ACA:
Con(NBG + AxC + I2) implies A implies Con(ZFC + I3).
Actually this holds for strong forms of I3, involving a proper class
of alpha's with j's with a common critical point.
For n >= 1 and m >= 0, we write n*m for the m tuple (n,...,n). If m =
0, then n*m is the empty sequence.
Let A contained in N^k and g:N into N be partial. We say that g
diagonally maps A into itself if and only if for all x_1,...,x_k in
dom(g),
if (x_1,...,x_k) in A then (f(x_1),...,f(x_k)) in A.
The Wild Anticipation Function Game has exactly the same parameters
and exactly the same rules as the Basic Anticipation Function Game. We
only change the winning condition.
WILD WINNING CONDITION. Bob is declared the winner of the Wild
Anticipation Function Game if and only if Bob has met all of his
PROMISES, where for all r in [1,s], the cross section of Bob's final
move at r!*k-1 diagonally maps its domain intersect [(8kn)!,r!)^k into
itself.
PROPOSITION. Bob wins the Wild Anticipation Function Game.
Note that this Proposition is explicitly Pi01.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 364th 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 http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
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 5:43PM
361: Finite Promise Games
362: Simplest Order Invariant Game
363: Greedy Function Games/Largest Cardinals 1
Harvey Friedman
More information about the FOM
mailing list