[FOM] 363:Greedy Function Games/Largest Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
Sat Sep 5 14:15:23 EDT 2009
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
More information about the FOM
mailing list