[FOM] 364:Anticipation Function Games/Largest Cardinals/simplified

[Harvey Friedman]

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