[FOM] 389: Finite Games and Large Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
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
More information about the FOM
mailing list