[FOM] 391: Finite Games, Vector Reduction, and Large Cardinals 3
Harvey Friedman
friedman at math.ohio-state.edu
Sun Feb 21 05:54:13 EST 2010
In this installment, we focus only on the finite and infinite games.
Here we switch to the setting of nonempty finite sets of rationals.
These games are motivated by a concept of BASIS of a relation. The
relevant underlying notion of BASIS will be a topic for a soon-to-be
posting in this series. We can think of these games here as "Bob is
trying to build a BASIS". We believe that the relevant notion of BASIS
may provide an initial hook into core mathematics. Stay tuned.
*****************************
1. GAMES BASED ON FINITE SETS OF RATIONALS.
2. GAMES BASED ON BOUNDED SIZE SETS OF RATIONALS.
3. CHALLENGE.
1. GAMES BASED ON FINITE SETS OF RATIONALS.
Let Q be the set of rationals and N be the set of nonnegative
integers. Let NFS(Q) be the space of nonempty finite subsets of Q.
Let R be contained in NFS(Q)^2. We view R as a binary relation on
NFS(Q). We say that y is a strict R reduction of x if and only if x R
y and min(y) < min(x). We say that y is an R reduction of x if and
only if x = y or y is a strict R reduction.
We first define the game G(R).
Alice and Bob alternately play elements of NFS(Q), Alice moving first.
In each round, Alice must play a subset of the union of N and Bob's
previous moves. Bob must respond with an R reduction of Alice's move
which is not a strict R reduction of any of Bob's previous moves.
Note that Alice's first move must be an element of N. It is clear that
Alice always has legal moves available (e.g., 0) - but Bob may not, in
which case the game stops. The focus is on how many moves Bob can
manage to make.
THEOREM 1.1. For all R contained in NFS(Q)^2, Bob has a strategy for
playing infinitely many moves in G(R).
The upper shift of x in NFS(Q) is the union of the negative elements
of x and the shifts (+1) of the nonnegative elements of x.
In the game G(R,ush), Alice and Bob alternately play elements of
NFS(Q), Alice moving first. In each round, Alice must play a subset of
the union of N and Bob's previous moves. Bob must respond with an R
reduction of Alice's move which is not a strict R reduction of any of
Bob's previous moves or their upper shifts.
In the formulation of G(R,ush), we have given special status to the +1
function on the nonnegative rationals. Therefore, we can no longer
expect to use arbitrary R contained in NFS(Q)^2.
For x,y,z,w in NFS(Q), we say that (x,y) and (z,w) are order
equivalent if and only if
i. x,z have the same cardinality.
ii. y,w have the same cardinality.
iii. The i-th element of x is less than the j-th element of y if and
only if the i-th element of z is less than the j-th element of w.
PROPOSITION 1.2. For all order invariant R contained in NFS(Q)^2, Bob
has a strategy for making infinitely many moves in G(R,ush).
PROPOSITION 1.3. For all order invariant R contained in NFS(Q)^2, Bob
has a strategy for making any given finite number of moves in G(R,ush).
Let SRP+ = ZFC + (for all k)(there exists lambda with the k-SRP). Let
SRP = ZFC + {there exists lambda with the k-SRP}_k. Here SRP =
"stationary Ramsey property", which asserts that any partition of the
unordered k-tuples has a stationary homogenous set. The SRP hierarchy
is intertwined with the subtle, almost ineffable, and ineffable
cardinal hierarchies.
THEOREM 1.4. Propositions 1.2, 1.3 are provable in SRP+ but not in any
consistent fragment of SRP that proves RCA_0. Propositions 1.2, 1.3
are provably equivalent to Con(SRP) over WKL_0.
Note that an order invariant subset of NFS(Q)^2 is not necessarily a
concrete object. There are continuumly many such, as they may involve
arbitrarily large finite subsets of Q. So even though Propositions 1.2
and 1.3 are provably equivalent to a common Pi01 sentence, they are
very far from being Pi01 themselves, or even arithmetical. This
situation is remedied in the next section.
2. GAMES BASED ON BOUNDED SIZE SETS OF RATIONALS.
For k >= 1, define NS(Q,<=k) as the space of all nonempty subsets of Q
with at most k elements.
For R contained in NS(Q,<=k)^2 and k >= 1, we define the games
G(R,<=k), G(R,<=k,ush) as follows.
In the game G(R,<=k), Alice and Bob alternately play elements of
NS(Q,<=k), Alice moving first. In each round, Alice must play a subset
of the union of N and Bob's previous moves. Bob must respond with an R
reduction of Alice's move which is not a strict R reduction of any of
Bob's previous moves.
In the game G(R,<=k,ush), Alice and Bob alternately play elements of
NS(Q,<=k), Alice moving first. In each round, Alice must play a subset
of the union of N and Bob's previous moves. Bob must respond with an R
reduction of Alice's move which is not a strict R reduction of any of
Bob's previous moves or their upper shifts.
The order invariant R contained in NS(Q,<=k) are very concrete
objects. They have a canonical presentation as a set of ordered pairs
of finite subsets of N, whose integers appearing form an initial
segment of N.
There are 2^3 = 8 order invariant R contained in NS(Q,<=1)^2. There
are 2^23 = 8,388,608 order invariant R contained in NS(Q,<=2).
Note that the number of order invariant R contained in NS(Q,<=k) is
bounded by a suitable triple exponential in k.
PROPOSITION 2.1. For all order invariant R contained in NS(Q,<=k)^2,
Bob has a strategy for making infinitely many moves in G(R,<=k,ush).
PROPOSITION 2.2. For all order invariant R contained in NS(Q,<=k)^2,
Bob has a strategy for making any given finite number of moves in
G(R,<=k,ush).
PROPOSITION 2.3. For all order invariant R contained in NS(Q,<=k)^2,
Bob has a strategy for making k moves in G(R,<=k,ush).
Note that in Propositions 2.2, 2.3, for each fixed order invariant R
contained in NS(Q,<=k)^2, and finite number of moves, the existence of
a strategy for Bob asserts that an effectively generated first order
sentence holds in the very decidable structure (Q,<,N,+1). Hence in
this sense, Propositions 2.2, 2.3 are implicitly Pi01.
However, we can go further and give explicitly Pi01 independence
results through a simple modification of the games.
For R contained in NS(Q,<=k)^2 and k,r >= 1, we define the games
G(R,<=k,r), G(R,<=k,r,ush) as follows.
In the game G(R,<=k,r), Alice and Bob alternately play elements of
NS(Q,<=k). In each round, Alice must play a subset of the union of
{0,...,r} and Bob's previous moves. Bob must respond with an R
reduction of Alice's move which is not a strict R reduction of any of
Bob's previous moves.
In the game G(R,<=k,r,ush), Alice and Bob alternately play elements of
NS(Q,<=k). In each round, Alice must play a subset of the union of
{0,...,r} and Bob's previous moves. Bob must respond with an R
reduction of Alice's move which is not a strict R reduction of any of
Bob's previous moves or their upper shifts.
PROPOSITION 2.4. For all order invariant R contained in NS(Q,<=k)^2,
Bob has a strategy for making any given finite number of moves in
G(R,<=k,ush).
PROPOSITION 2.5. For all order invariant R contained in NS(Q,<=k)^2,
Bob has a strategy for making k moves in G(R,<=k,ush).
We now give Pi01 forms of Propositions 2.4, 2.5 as follows. Define the
complexity of a finite set of rationals as the sum of the magnitudes
of the numerators and denominators of its elements, when the elements
are put in reduced form. I.e., {2/3,-7/5} has complexity 17.
PROPOSITION 2.6. For all order invariant R contained in NS(Q,k)^2, Bob
has a strategy for making n moves in G(R,k,ush) involving only sets of
rationals of complexity at most (8knr)!!, where Alice's first move is
r-1 in N.
PROPOSITION 2.7. For all order invariant R contained in NFS(Q)^2 of
index k < infinity, Bob has a strategy for making k moves in G(R,ush)
involving only sets of rationals of complexity at most (8kr)!!, where
Alice's first move is r-1 in N.
Note that Propositions 2.6, 2.7 are explicitly Pi01. The expressions
(8knr)!! and (8kr)!! are intended as extremely crude but safe upper
bounds.
THEOREM 2.8. Propositions 2.1 - 2.7 are provable in SRP+ but not in
any consistent fragment of SRP that proves RCA_0. Propositions 2.2 -
2.7 are provably equivalent to Con(SRP) over RCA_0 (even EFA if we
incorporate the decision procedure for (Q,<,N,+1)). Propositions 2.6,
2.7 are provably equivalent to Con(SRP) over EFA.
3. CHALLENGES.
Prove Proposition 2.2 for k = 2, with 1,2,3,4,5,6,7,8 moves, using
accepted mathematical methods, perhaps with the aid of a computer.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 391st 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
389: Finite Games and Large Cardinals 1 2/9/10 3:32PM
390: Finite Games and Large Cardinals 2 2/14/09 10:27PM
Harvey Friedman
More information about the FOM
mailing list