[FOM] 363:Greedy Function Games/Largest Cardinals 1

[Harvey Friedman]

Greedy Algorithms figure prominently in computer science and  
combinatorics - particularly combinatorial optimization.

All of our games can be viewed as Greedy Function Games in a very  
natural way. The Greed involved is more subtle than usual - PROMISES  
REFLECTING GREED.

We begin by giving a reformulation of our main order invariant game of  
#362 as a Greedy Function Game.

In this Greedy Function Game, Bob builds a function. There are many  
variants of this basic Greedy Function Game, with the same results.  
This will be taken up later.

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 Greedy Function Game.
2. Strong Greedy Function Game.
3. Wild Greedy Function Game.

1. BASIC GREEDY FUNCTION GAME

Let Z+ be the set of all positive integers. The factorials are the  
integers 1!,2!,... .

Let f:Z+^k into Z+ be partial, B contained in Z+^k, and C contained in  
Z+. We say that f partially maps B into C if and only if every value  
of f at elements of A lies in B.

GAME PARAMETERS. k,n,s >= 1, and an order invariant relation R  
contained in [1,s]^2k+2.

GAME STRUCTURE. Alice and Bob make n alternating moves. Each move by  
Alice is an elements of [1,s]^k. Each move by Bob is a partial  
function f:[1,s]^k into [1,s]. At each move, Bob plays a function  
extending his previous move at at most 2 new arguments, and defined at  
Alice's previous move, with PROMISES REFLECTING GREED. 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 play an extension f* of f,  
perhaps with a PROMISE REFLECTING GREED.

i. there exists y such that max(y) < max(x) and R(x,y,f*(x),f*(y)) and  
dom(f*) = dom(f) union {x,y}; or

ii. Bob PROMISES that there never will be y,u such that max(y) <  
max(x) and R(x,y,u,g(y)), where g is Bob's final move, and dom(f*) =  
dom(f) union {x}.

WINNING CONDITION. Bob is declared the winner of the game if and only  
if Bob has met all of his PROMISES. I.e., that, in retrospect, his  
moves were, in fact, Greedy.

THEOREM 1.1. Bob wins this game. This is provable in RCA_0.

2. STRONG GREEDY FUNCTION GAME

We play the basic greedy 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 this strong 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 GREEDY FUNCTION GAME

Here the explicitly Pi01 sentence expressing that Bob wins the 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,m >= 1, we write n*m for the m tuple (n,...,n).

Let f be a partial function from N^r into N and m >= 1. We write f|<m  
for the restriction of f to [0,m)^r. f|<m could have values > m.

Let f:N^r into N and g:N into N both be partial. We say that g  
diagonally maps f into f if and only if for all x_1,...,x_r,y,

f(g(x_1),...,g(x_r)) = g(f(x_1,...,x_r))

provided both sides are defined.

GAME PARAMETERS. k,n,s >= 1, and an order invariant relation R  
contained in [0,s]^2k+2 such that R(x_1,...,x_k,y_1,...,y_k,z,w)  
implies max(x_1,...,x_k) < max(y_1,...,y_k) = y_k.

GAME STRUCTURE AND RULES. Identical to the Basic Greedy Function Game  
in section 1 above.

WILD WINNING CONDITION. Bob is declared the winner of the wild 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!*2k+1 diagonally maps h|<r!  
into h|<r!, and omits (8kn)!.

PROPOSITION. Bob wins this wild game.

Note that this Proposition is explicitly Pi01.

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

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