[FOM] 390: Finite Games, Vector Reduction, and Large Cardinals 2

[Harvey Friedman]

We are working on a series of simplifications and improvements  
starting with posting #389 http://www.cs.nyu.edu/pipermail/fom/2010-February/014386.html 
  Some of these simplifications that we are working on are  
substantially more dramatic than #389 and this present posting - but  
it will take time to get them just right and checked. I am also  
juggling some heavy duty deadlines elsewhere, which is slowing me  
down. The plan is to roll out a series of substantial improvements and  
simplifications. The present posting is the first such improvement.

1. The Games G(R).
2. The Games G(R,ush).
3. Vector Reduction.
4. Templating.

1. THE GAMES G(R).

We use Q for the set of all rationals.

Let R be contained in Q^2k = Q^k x Q^k. We say that R is a reducer if  
and only if for all x,y in Q^k,

i. x R x.
ii. x R y implies x = y or max(x) > max(y).

We say that x,y are related by R if and only if x R y or y R x. We say  
that x,y are properly related by R if and only if x,y are distinct and  
x,y are related by R.

For all nonempty R contained in Q^2k, we first define the two person  
game G(R). This game can be played for any number of moves.

The two players are Alice and Bob, who alternately play a single  
element of Q^k. There are restrictions on Alice's moves, but she will  
always have legal moves available. There are different restrictions on  
Bob's moves, but he may (rather easily) get into a situation where he  
has no legal moves available.

We focus on Bob's effort to make infinitely many moves, or at least a  
given finite number of moves.

Alice's first move can be any element of Q^k. Subsequently, Alice must  
always play an element of Q^k composed of rationals which have  
previously appeared in the game.

Suppose Alice has just played x. Bob is required to play some y in Q^k  
such that

i. x R y.
ii. y is not properly related by R to any of Bob's previous moves.

THEOREM 1.1. Let k >= 1 and R contained in Q^2k be a reducer. Bob has  
a strategy for making infinitely many moves in G(R). In fact, Bob has  
a strategy for making infinitely many moves in G(R) using only  
rationals appearing in Alice's move in round 1.

2. THE GAME G(R,ush).

The upper shift (on Q) is the function ush: Q into Q given by ush(x) =  
x+1 if x >= 0; x otherwise. We extend the upper shift to ush:Q^k into  
Q^k by acting coordinatewise.

For all nonempty R contained in Q^2k, we define the two person game  
G(R,ush), which is a simple modification of the game G(R). The rules  
for Alice are the same as for G(R).

Suppose Alice has just played x. Bob is required to play some y in Q^k  
such that

i. x R y
ii. y and ush(y) are each not properly related by R to any of Bob's  
previous moves.

Because of the specific use of ush, and for the sake of concreteness,  
we move to order invariant R. Specifically, x,y in Q^k are said to be  
order equivalent if and only if for all 1 <= i,j <= k, x_i < x_j iff  
y_i < y_j. E contained in Q^p if said to be order invariant if and  
only if for all order equivalent x,y in Q^p, x is in E iff y is in E.

Order invariant R contained in Q^2k are of special importance, viewed  
as binary relations on Q^k.

PROPOSITION 2.1. For all order invariant reducers R contained in Q^2k,  
Bob has a strategy for playing infinitely many moves in G(R,ush).

PROPOSITION 2.2. For all order invariant reducers R contained in Q^2k  
and n >= 1, Bob has a strategy for playing n moves in G(R,ush).

PROPOSITION 2.3. For all order invariant reducers R contained in Q^2k,  
Bob has a strategy for playing k moves in G(R,ush).

Note that Propositions 2.3, 2.4 are already in implicit Pi01 form in  
the following sense. Note that for each k,n,R, Bob having such a  
strategy is a sentence in (Q,<,+1) effectively obtained from k,n,R.  
However, we can easily make Propositions 2.2 and 2.3 explicitly Pi01  
by using a very crude estimate. Define the complexity c(x) of x in Q^k  
as the maximum of the magnitudes of the denominators and numerators of  
the coordinates when put in reduced form.

PROPOSITION 2.4. Let R contained in Q^2k be an order invariant  
reducer. For any first play x for Alice, Bob has a strategy function  
for playing n moves in G(R,ush), involving only rationals of  
complexity at most (8knc(x))!!.

PROPOSITION 2.5. Let R contained in Q^2k be an order invariant  
reducer. For any first play x for Alice, Bob has a strategy function  
for playing k moves in G(R,ush), involving only rationals of  
complexity at most (8kc(x))!!.

Let k >= 1. We say that lambda has the k-SRP if and only if lambda is  
a limit ordinal, where for all partitions of the unordered k-tuples  
from lambda into two pieces, there is a stationary subset of lambda  
all of whose k-tuples lie in the same piece. This results in a  
hierarchy that is intertwined with the subtle, almost ineffable, and  
ineffable cardinal hierarchies. It is simpler to state.

SRP+ = ZFC + "for all k there exists lambda with the k-SRP". SRP = ZFC  
+ {there exists lambda with the k-SRP}_k. EFA = exponential function  
arithmetic, or ISigma_0(exp).

THEOREM 2.6. Propositions 2.1 - 2.5 are provable in SRP+ but not in  
any consistent consequence of SRP that proves RCA_0. Propositions 2.1  
- 2.5 are provably equivalent to Con(SRP) over WKL_0. Propositions  
2.2, 2.3 are provably equivalent to Con(SRP) over RCA_0. Propositions  
2.4, 2.5 are provably equivalent to Con(SRP) over EFA.

3. THE GAMES G(R,ush)*.

G(R,ush)* is a modification of G(R,ush), which is more demanding on Bob.

For all R contained in Q^2k, we define the two person game G(R,ush),  
which is a simple modification of the game G(R).

As in G(R,ush), Alice's first move can be any element of Q^k. Alice's  
subsequent moves must consist of rationals that are the sum of any  
nonnegative integer with any rational that has previously appeared in  
the game.

Suppose Alice has just played x. Bob is required to play some y in Q^k  
such that

i. x R y
ii. y is not related by R to any previous move of Bob (other than y).
iii. The moves played by Bob, including y, together with their upper  
shifts, form a set where no two distinct elements are related by R.

PROPOSITION 3.1. For all order invariant reducers R contained in Q^2k,  
Bob has a strategy for playing infinitely many moves in G(R,ush)*.

PROPOSITION 3.2. For all order invariant reducers R contained in Q^2k  
and n >= 1, Bob has a strategy for playing n moves in G(R,ush)*.

PROPOSITION 3.3. For all order invariant reducers R contained in Q^2k,  
Bob has a strategy for playing k moves in G(R,ush)*.

THEOREM 3.4. Propositions 3.1 - 3.3 are provable in SRP+ but not in  
any consistent consequence of SRP that proves RCA_0. Propositions 3.1  
- 3.3 are provably equivalent to Con(SRP) over WKL_0. Propositions  
3.2, 3.3 are provably equivalent to Con(SRP) over RCA_0.

4. VECTOR REDUCTION.

The games G(R,ush) are obviously based on vector reduction. I.e., Bob  
is required to play a vector that reduces Alice's most recent play.

We now consider vector reduction independently of games.

Let A be a subset of Q^k. We define the cute of A, or cube(A), as the  
least set B^k containing A. We define the field of A, or fld(A), as  
the set of all coordinates of elements of A. Note that cube(A) =  
fld(A)^k.

We define the upper shift of A, as the set of all upper shift of  
elements of A. We define the inclusive upper shift of A as A union the  
upper shift of A.

Let R be a subset of Q^2k. We say that A is R free if and only if no  
two distinct elements of A are related by R.

We say that B is an R reduction of A if and only if

i. (forall x in A)(therexists y in B)(x R y).
ii. Clause i fails for all proper subsets of B.

THEOREM 4.1. Free Reduction Theorem. Let R contained in Q^2k be a  
reducer. Every finite A contained in Q^k has a unique R free R  
reduction contained in A. In fact, every S contained in Q^k with well  
ordered field, has a unique R free R reduction contained in S.

THEOREM 4.2. Let R contained in Q^2k be an order invariant reducer.  
Every finite A contained in Q^k has an R reduction whose inclusive  
upper shift if R free.

Now fix R contained in Q^2k and A contained in Q^k. We define the  
"cubic R reduction sequences" as follows. These are finite or infinite  
sequences of subsets A_1,A_2,... of Q^k such that for all 1 <= i <  
lth(alpha), A_i+1 is an R reduction of cube(A_i). Cubic R reduction  
sequences can have any length from 1 through infinity.

The proper union of a cubic R reduction sequence is the union of all  
of its terms after A_1.

THEOREM 4.3. Let R contained in Q^2k be a reducer and S be a well  
ordered subset of Q. S^k starts a unique cubic R reduction sequence of  
infinite length whose proper union is an R free subset of S^k.

PROPOSITION 4.4. Let R contained in Q^2k be an order invariant  
reducer. Every A_1 contained in Q^k with well ordered field starts a  
cubic R reduction sequence of infinite length, where the inclusive  
upper shift of its proper union is R free.

PROPOSITION 4.5. Let R contained in Q^2k be an order invariant  
reducer. Every finite A_1 contained in Q^k starts a cubic R reduction  
sequence of length 3, where the inclusive upper shift of its proper  
union is R free.

The "cubic,+1 R reduction sequences" are the finite or infinite  
sequences alpha of subsets A_1,A_2,... of Q^k such that for all 1 <= i  
< lth(alpha), A_i+1 is an R reduction of cube(A_i + {0,1}).

PROPOSITION 4.6. Let R contained in Q^2k be an order invariant  
reducer. {(0,...,0)} starts a cubic,+1, R reduction sequence of length  
k, where the inclusive upper shift of its proper union is R free.

Note that Propositions 4.5 and 4.6 are Pi01 because of the obvious  
bounds that can be placed on the complexity of its noninitial terms,  
relative to the complexity of the initial term.

THEOREM 4.7. Propositions 4.4 - 4.6 are provable in SRP+ but not in  
any consistent consequence of SRP that proves RCA_0. Propositions 4.5,  
4.6 are provably equivalent to Con(SRP) over EFA.

We expect to be making postings claiming the independence of yet more  
concrete statements with large cardinals.

5. TEMPLATING.

As in earlier FOM postings, we can view ush:Q into Q as an example of  
a partial piecewise linear function with rational coefficients from Q  
into Q. We can ask what happens if we replace ush with such a partial  
function. Or even with several such functions. What equivalences do we  
get with metamathematical statements?

Another aspect worth templating is the definition of reducer. This is  
a condition on R involving x R y, max(x), max(y), <. It's a bit  
premature for me to worry about the exact setup for this templating,  
but I envision first a separate templating of ush and of reducer.  
Then, a combined templating of ush and of reducer.

Even order invariance is subject to templating, by introducing the  
relation of order equivalence into the mix.

Right now, the emphasis is on more specific forms of these independent  
statements that are still independent.

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

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

Harvey Friedman