[FOM] 389: Finite Games and Large Cardinals 1

Tue Feb 9 05:44:50 EST 2010

We expect that there will be several postings. These initial postings  
will not contain expositional background, but get right down to the  
heart of the matter.

The finite games are improving at a rapid rate. The goal is to get  
them to be extremely elegant and memorable, yet be equivalent to the  
consistency (not 1-consistency) of ZFC + j:V(lambda + 1) into V(lambda  
+ 1), and also NBG + j:V into V, and more.

However, at least this first posting will only be at the level of the  
stationary Ramsey property hierarchy - intertwined with the subtle,  
almost ineffable, or ineffable cardinal hierarchies.

Q is the set of all rationals. When we finally get down to making the  
game statements explicitly Pi01, we use the following notion of  
complexity. Let x be in Q^k. We write c(x) for the least positive  
integer n such that all coordinates of x can be written with numerator  
and denominator of magnitude at most n.

1. THE GAMES G(R,k,f).

We use Q for the set of all rationals. For x,y in Q^k, we say that x  
is lower than y if and only if max(x) < max(y).

Let R be contained in Q^2k = Q^k x Q^k. We treat R as if it is the  
edge set of a simple (undirected) graph with vertex set Q^k. We say  
that x,y are related if and only if x,y are distinct and (R(x,y) or  
R(y,x)).

We now define the game G(R,k,f). Here R is a subset of Q^2k, and f is  
a function. For the sake of generality, we will not assume anything  
about the function f.

For x,y in Q^k, we say that x is bounded by y if and only if max(x) <=  
max(y).

The two players are Alice and Bob, who alternately play rounds. In  
each round, Alice first plays an element of Q^k. Then Bob plays one or  
two elements of Q^k. Thus Alice plays exactly one move per round,  
whereas Bob plays one or two moves per round.

These moves are subject to the following simple conditions.

1. Alice's first move is subject to no condition. Alice's subsequent  
moves are required to be made up of rationals that have appeared in  
earlier rounds (in Alice's and Bob's moves in previous rounds).
2. Within each round: Bob's first move must be
    i. unrelated (by R) to each of Bob's moves in previous rounds;
    ii. bounded by Alice's move;
    iii. be Alice's move or related (by R) to Alice's move.
3. Within each round: Bob's second move must be the value of f at  
Bob's first move (within this round). In case f is undefined at Bob's  
first move (within this round), Bob will not make a second move  
(within this round).

Note all blockages (inability to make a legal move) must occur at  
Bob's first move in round 2 or later. Alice has no blockages.

THEOREM 1.1. Let k >= 1 and R contained in Q^2k. Bob has a strategy  
for avoiding all blockages in the game G(R,k). I.e., a strategy for  
continuing to play for infinitely many rounds of G(R,k). In fact, Bob  
has a strategy for avoiding all blockages using only rationals present  
in Alice's first move.

The shift is the function s:Q into Q given by sh(x) = x+1. The  
positive (nonnegative) shift is the function psh on the positive  
(nonnegative) rationals given by f(x) = x+1. The upper shift is the  
function ush:Q into Q given by f(x) = x+1 if x > 0; x otherwise. Note  
the singularity (critical point) of the upper shift at 0.

These functions are extended to all finite tuples from Q by acting  
coordinatewise.

THEOREM 1.2. Let k >= 1 and R contained in Q^2k. Bob has a strategy  
for playing infinitely many rounds in G(R,k,nsh). In fact, Bob has a  
strategy for avoiding all blockages using only rationals present in  
Alice's first move.

THEOREM 1.3. For all k >= 1, there exists order invariant R contained  
in Q^2k such that Bob is always blocked at the second round in  
G(R,k,sh).

PROPOSITION 1.4. Let k >= 1 and R be an order invariant subset of  
Q^2k. Bob has a strategy for playing infinitely many rounds in  
G(R,k,ush).

PROPOSITION 1.5. Let k,n >= 1 and R be an order invariant subset of  
Q^2k. Bob has a strategy for playing n rounds in G(R,k,ush).

PROPOSITION 1.6. Let k >= 1 and R be an order invariant subset of  
Q^2k. Bob has a strategy for playing k rounds in G(R,k,ush).

PROPOSITION 1.7. Let k >= 1 and R be an order invariant subset of  
Q^2k. Bob has a strategy for playing k rounds in G(R,k,ush), making  
only moves of complexity at most (8kc(x))!!, where x is Alice's first  
move.

Note that Proposition 1.7 is explicitly Pi01.

THEOREM 1.8. Propositions 1.4 - 1.7 are provable in SRP+ but not in  
any consistent consequence of SRP that proves RCA_0. Propositions 1.4  
- 1.7 are provably equivalent to Con(SRP) over WKL_0. Propositions 1.5  
- 1.7 are provably equivalent to Con(SRP) over RCA_0. Proposition 1.7  
is provably equivalent to Con(SRP) over EFA.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 388th 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  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1  9/24/09  1:06PM
366: Free Reductions and Large Cardinals/polished  9/28/09  2:19PM
367: Upper Shift Fixed Points and Large Cardinals  10/4/09  2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction  10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09  2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09  2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09  2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION  12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10  7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM

Harvey Friedman