[FOM] 370:Upper Shift Fixed Points, Sequences, Games, and Large Cardinals

[Harvey Friedman]

This is a self contained restatement and improvement and extension of  
previous postings, including the previously comprehensive http://www.cs.nyu.edu/pipermail/fom/2009-October/014153.html

UPPER SHIFT FIXED POINTS, SEQUENCES, GAMES, AND LARGE CARDINALS
by
Harvey M. Friedman
November 19, 2009

1. Terminology.
2. Upper Shift Fixed Point Theorem.
3. Extreme Upper Shift Fixed Point Theorems.
4. Finite Forms.
5. Upper Shift Vector Sequences.
6. Upper Shift Vector Games.
7. Probabilistic Upper Shift Vector Games.
8. Templates.
9. Exercises.

1. TERMINOLOGY.

Let Q be the set of all rationals.

We say that x,y in Q^k are order equivalent iff for all 1 <= i,j <= n,  
x_i < x_j iff y_i < y_j.

We say that E contained in Q^k is order invariant iff for all order  
equivalent x,y in Q^k, x in E iff y in E.

We say that R contained in Q^k x Q^k is order invariant iff R is order  
invariant as a subset of Q^2k.

We say that R contained in Q^k x Q^k is strictly dominating iff for  
all x,y, R(x,y) implies max(x) < max(y).

We write R[A] = {y: (therexists x in A)(R(x,y))}, where we require  
that A be contained in Q^k.

The upper shift of x in Q^k is obtained by adding 1 to all of the  
nonnegative coordinates, and leaving the negative coordinates fixed.

The upper shift of A contained in Q^k is the set of upper shifts of  
its elements.

Let A contained in Q^k. We write fld(A) for the set of all coordinates  
of elements of A. We write cube(A,0) for (fld(A) union {0})^k.

2. THE UPPER SHIFT FIXED POINT THEOREM.

THEOREM 2.1. For all strictly dominating order invariant R contained  
in Q^k x Q^k, there exists A = cube(A,0)\R[A].

Proof: Take A = {(0,...,0)}. QED

PROPOSITION 2.2. THE UPPER SHIFT FIXED POINT THEOREM. For all strictly  
dominating order invariant R contained in Q^k x Q^k, there exists A =  
cube(A,0)\R[A] containing its upper shift.

Proposition 2.2 is provable using large cardinals, but not in ZFC. The  
large cardinals associated with Proposition 2.2 are most intuitively  
described in terms of the SRP = stationary Ramsey property. We say  
that a limit ordinal lambda has the k-SRP if and only if any partition  
of the unordered k-tuples from lambda into two pieces has a  
homogeneous set that is stationary in lambda.

The least limit ordinal lambda with the k-SRP, k >= 2, is a large  
cardinal (strongly inaccessible, strongly Mahlo, weakly compact,  
etcetera). These form the SRP hierarchy, which is intertwined with the  
subtle, almost ineffable, and ineffable cardinal hierarchies. See

H. Friedman, Subtle Cardinals and Linear Orderings, Annals of Pure and  
Applied Logic 107 (2001), 1-34.

for a modern treatment of these hierarchies that go back to James  
Baumgartner.

SRP+ = ZFC + (forall k)(some lambda has the k-SRP). SRP = ZFC + {some  
lambda has the k-SRP}_k.

THEOREM 2.3. Proposition 2.2 is provable in SRP+ but not in any  
consistent fragment of SRP. Proposition 2.2 is provably equivalent,  
over WKL_0, to Con(SRP).

THEOREM 2.4. Let k >= 1. Proposition 2.2 for k is provable in ZFC +  
"there exists lambda with the k-SRP".

We have prepared a sketch of the proof of Proposition 2.2 from SRP+.  
See http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html  
Preprints, Drafts, and Abstracts, 64.

and we can see Theorem 2.4 from that sketch.

We do not have a detailed sketch of the reversal of Proposition 2.2 at  
this time, but we know that Proposition 2.2 begins to be strong when k  
is bigger than a very small number. A guesstimate is 4.

THEOREM 2.5. Let k be sufficiently large. Proposition 2.2 for k is not  
provable in any consistent fragment of ZFC + "there exists lambda with  
the k-1-SRP". In particular, Proposition 2.2 for k = 4 is not provable  
in ZFC. (tentative) k >= 4 is sufficient.

3. EXTREME FIXED POINT THEOREMS.

Let A be contained in Q^k. We write A^ne for the set of all elements  
of A whose coordinates are distinct. The cross sections of A are sets  
of the form {y in Q^k-1: (x,y) in A}, for fixed x in Q.

We write us:Q into Q for the upper shift us(x) = x+1 if x >= 0; x  
otherwise.

Let f:Q into Q. Take f to lift to higher dimensions by acting  
coordinatewise (as we have done with the upper shift).

We say that A containedin Q^k is f closed if and only if f[A] is  
contained in A.

We say that f is nontrivial if and only if f is not the identity  
function.

Clause ii is used to avoid trivialities.

We say that A containedin Q^k is strongly f closed if and only if

i. f[A] is contained in A.
ii. for all upper bounded cross sections E of A, f[E] is an upper  
bounded cross section of A.

We say that A containedin Q^k is p-strongly f closed if and only if

i. f[A] is contained in A.
ii. for all cross sections E of A below p, f[E] is a cross section of  
A below p.

For the Extreme Theorems, we need to use the modified fixed point  
equation

A^ne = cube(A,0)^ne\R[A].

Here is a corresponding modification of the Upper Shift Fixed Point  
Theorem, Proposition 2.2.

PROPOSITION 3.1. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists a us closed A^ne = cube(A,0)^ne 
\R[A].

Here is our first Extreme Theorem.

PROPOSITION 3.2. EXTREME UPPER SHIFT FIXED POINT THEOREM. For all  
strictly dominating order invariant R contained in Q^k x Q^k, there  
exists A^ne = cube(A,0)^ne\R[A], where A is strongly us closed.

Here is a more abstract forms of Proposition 3.2.

PROPOSITION 3.3. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists A^ne = cube(A,0)^ne\R[A], where A  
is strongly f closed for some nontrivial f.

PROPOSITION 3.4. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists A^ne = cube(A,0)^ne\R[A], where A  
is 2-strongly f closed for some f with f(0) = 1.

HUGE+ = ZFC + "for all k, there is a k-huge cardinal". HUGE = ZFC +  
{there is a k-huge cardinal}_k.

Nearly the most extreme large cardinal hypotheses are stated in
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).

THEOREM 3.5. Propositions 3.1 is provable in SRP+ but not in any  
consistent fragment of SRP. Propositions 3.1 is provably equivalent,  
over WKL_0, to Con(SRP). Propositions 3.2,3.3 are provable in HUGE+  
but not in any consistent fragment of HUGE. Propositions 3.2,2.3 RE  
provably equivalent, over WKL_0, to Con(HUGE). Proposition 3.4 is  
provable in NBG + I2 but not in any consistent fragment of ZFC + I3.  
The implications Con(NBG + I2) implies Proposition 3.4 implies Con(ZFC  
+ I3) are provable in WKL_0. Proposition 3.6 is provably equivalent to  
a Pi01 sentence over WKL_0. We can use a strengthened from of I3.

4. FINITE FORMS.

The Upper Shift Fixed Point Theorem has nice finite forms involving  
finite sequences of finite subsets of Q^k. In sections 5-7, we give  
finite forms that state the existence of finite sequences of elements  
of Q^k. These can be viewed as more concrete.

PROPOSITION 4.1. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists finite A_1,A_2,... contained in  
Q^k such that each A_i+1 = cube(A_i+1,0)\R[A_i+2] contains A_i union  
us(A_i).

PROPOSITION 4.2. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists finite A_1,...,A_k contained in  
Q^k such that each A_i+1 = cube(A_i+1,0)\R[A_i+2] contains A_i union  
us(A_i).

PROPOSITION 4.3. For all strictly dominating order invariant R  
contained in Q^k x Q^k, there exists finite A_1,...,A_k contained in  
Q^k such that each A_i+1 = cube(A_i+1,0)\R[A_i+2] contains A_i union  
us(A_i), where the magnitudes of the numerators and denominators of  
the rationals in the A's in reduced form are < (8k)!.

Note that Proposition 4.2 is explicitly Pi02 and Proposition 4.3 is  
explicitly Pi01.

THEOREM 4.4. The Upper Shift Fixed Point Theorem (Proposition 2.2),  
and Propositions 4.1-4.3 are provably equivalent over WKL_0. Hence  
Theorem 2.3 applies.

The stronger Propositions from section 3 do not lend themselves to  
such simple finite forms. However, there is a general theory of finite  
forms for statements of this kind.

Note that these finite forms of the Unprovable Upper Shift Fixed Point
Theorem are quite simple. However, the somewhat similarly constructed
finite forms of the Unprovable Internal Embedding Theorem are not as
simple. Rather than present them, we present a general treatment of
finite forms of such statements.

Consider all sentences of the following form:

#) There exists A_1,...,A_n contained in Q^k such that for all 1 <= i
<= m, P(i,A_1,...,A_n) holds.

Here k,n,m are specific positive integers, and P is a specific first
order property of the structure (Q,<,A_1,...,A_n), where the A's act
as k-ary relation symbols.

THEOREM 4.5. There is an effective procedure that converts any
sentence phi of form #) into an algorithmic process Gamma, such that
phi holds if and only if Gamma does not terminate.

Note that every instance of Propositions 3.3 and 3.4 are of the above
form. Hence by general principles (i.e., Theorem 4.2), both have
finite forms that are Pi01.

We can expand #) to allow the upper shift us, and constants, provided  
that we require P to be in prenex form and allow only bounded  
quantifiers after initial universal quantifiers. This will allow us to  
treat the Upper Shift Fixed Point Theorem and the Extreme Upper Shift  
Fixed Point Theorem, without having to give a specific finite form  
(although we have given simple ones for the former above).

5. UPPER SHIFT VECTOR SEQUENCES.

We now give finite forms for the Upper Shift Fixed Point Theorem which  
are more down to earth in the sense that instead of producing finite  
sequences of finite subsets of Q^k, we produce finite sequences from  
Q^k. We will not attempt to treat the Extreme Upper Shift Fixed Point  
Theorem and variants at this time.

Let R contained in Q^k x Q^k. We can view R as imposing a constraint  
on finite sequences x_1,...,x_n from Q^k. Namely that x_1,...,x_n be R  
free. I.e., for no x_i,x_j is it the case that R(x_i,x_j).

As we build R free sequences from Q^k of length n, we want to provide  
candidates for the next term. These are provided by means of a  
function. Write Q^<=p for the set of all tuples from Q of nonzero  
length at most p.

Let R containedin Q^k x Q^k and C:Q^<=nk into Q^k. A C,R generated  
sequence is a sequence x_1,...,x_n from Q^k such that

i. x_1 = 0 or R(x_1,0).
ii. for all 2 <= i <= n, x_i = C((x_1,...,x_i-1)) or  
R(x_i,C((x_1,...,x_i-1)).

Here we think of the function C as generating candidates for insertion  
into the sequence.

THEOREM 5.1. The following is false. Let R containedin Q^k x Q^k be  
strictly dominating and C:Q^<=nk into Q^k. There is an R free C,R  
generated sequence.

Theorem 5.1 is quite far from being true. We need R,C to be order  
invariant. We say that C is order invariant if and only if its graph  
is order invariant as a subset of Q^<=nk+k. It is easily seen that if  
C is order invariant, then every coordinate of C(alpha) is a  
coordinate of alpha.

THEOREM 5.2. For every strictly dominating order invariant R contained  
in Q^k x Q^k and order invariant C:Q^<=nk into Q^k, there is an R free  
C,R generated sequence.

Proof: Trivial. We can take all terms to be the 0 vector. C can only  
produce the 0 vector, and so the C,R generated sequence can be taken  
to consist entirely of the 0 vector. QED

A C,R generated upper shift sequence is a sequence x_1,...,x_n from  
Q^k such that

i. x_1 = 0 or R(x_1,0).
ii. for odd 3 <= i <= n, x_i is C(x_1,...,x_i-1) or  
R(x_i,C(x_1,...,x_i-1)).
iii. for even 2 <= i <= n, x_i is the upper shift of x_i-1.

PROPOSITION 5.3. For every strictly dominating order invariant R  
contained in Q^k x Q^k and order invariant C:Q^<=nk into Q^k, there is  
an R free C,R generated upper shift sequence. In fact, we can require  
that all numerators and denominators of rationals used have magnitude  
at most (8kn)!.

THEOREM 5.4. Proposition 5.3 is provably equivalent to the Upper Shift  
Fixed Point Theorem over WKL_0, and to its finite forms over EFA.  
Hence it can be proved from large cardinals but not in ZFC.

Note that Proposition 5.3 is explicitly Pi02; with the numerical  
requirement, is explicitly Pi01.

We can relax the condition that C is order invariant. We say that  
C:Q^<=nk into Q^k is conservative if and only if for all alpha, every  
coordinate of C(alpha) is a coordinate of alpha. It is easy to see  
that if C is order invariant then C is conservative.

There is also a strengthening of conservativity. We say that C is  
subsequential if and only if each C(alpha) is a subsequence of alpha.  
Here subsequences can skip over terms. Of course, there are now  
continuumly many C in each dimension, as opposed to only finitely many  
order invariant C. This makes the following statement not nearly so  
concrete. However, it does not change its status:

PROPOSITION 5.5. For every strictly dominating order invariant R  
contained in Q^k x Q^k and subsequential C:Q^<=nk into Q^k, there is  
an R free C,R generated upper shift sequence.

PROPOSITION 5.6. For every strictly dominating order invariant R  
contained in Q^k x Q^k and order invariant subsequential C:Q^<=nk into  
Q^k, there is an R free C,R generated upper shift sequence.

THEOREM 5.7. Propositions 5.5,5.6 are also provably equivalent to the  
Upper Shift Fixed Point Theorem over WKL_0, and to its finite forms  
over EFA. Hence they can be proved from large cardinals but not in ZFC.

Further natural restrictions on C can certainly be given, with the  
same result. We have not made a thorough study of such restrictions yet.

These results hold if we set n = k. These results also hold if we fix  
k to be at least a fixed small number, and let n be arbitrary. They  
also hold if we fix n to be at least a fixed small number, and let k  
be arbitrary. How small is small? A guesstimate is 4 for both k and n,  
separately.

6. UPPER SHIFT VECTOR GAMES.

Let R be contained in Q^k x Q^k. In the R upper shift vector game,  
Alice and Bob alternately move. Alice's moves are single elements of  
Q^k. Bob's moves are two elements of Q^k. I.e., Bob's moves have two  
parts.

Alice must open the game with the zero vector in Q^k.

Any subsequent move of Alice must be an element of Q^k whose  
coordinates appear among the previous plays of Alice and Bob.

Suppose Alice has just played C (C for candidate, as in section 5) in  
Q^k. The first part of Bob's response must be C or some y with R(y,C).  
The second part of Bob's response must be the upper shift of his first  
part.

Bob has made a losing move if two of Bob's plays (including both parts  
of Bob's plays) are related by R. I.e., Bob's plays are not R free. In  
this case, the game stops.

PROPOSITION 6.1. For every strictly dominating order invariant R  
contained in Q^k x Q^k, Bob can play the R upper shift game for k  
rounds without making a losing move.

PROPOSITION 6.2. For every strictly dominating order invariant R  
contained in Q^k x Q^k and n >= 1, Bob can play the R upper shift game  
for n rounds without making a losing move.

PROPOSITION 6.3. For every strictly dominating order invariant R  
contained in Q^k x Q^k, Bob can play the R upper shift game forever  
without making a losing move.

PROPOSITION 6.4. For every strictly dominating order invariant R  
contained in Q^k x Q^k, Bob can play the R upper shift game for k  
rounds without making a losing move, playing only rational numbers  
whose numerators and denominators have magnitude at most (8k)!.

PROPOSITION 6.5. For every strictly dominating order invariant R  
contained in Q^k x Q^k and n >= 1, Bob can play the R upper shift game  
for n rounds without making a losing move, playing only rational  
numbers whose numerators and denominators have magnitude at most (8kn)!.

THEOREM 6.6. Propositions 6.1 - 6.5 are provably equivalent to the  
Upper Shift Fixed Point Theorem over WKL_0. can be proved in SUB+ but  
not in SUB. They are provably equivalent, over EFA (exponential  
function arithmetic) to Con(SUB).

Note that Propositions 6.1 - 6.3 are not explicitly arithmetical,  
since they involve an existential quantifier over infinite functions  
(strategies). However, Propositions 6.4 - 6.5 are explicitly Pi01  
since the strategies have domain and range contained in explicitly  
given finite sets.

Again, we can fix k and let n be arbitrary, or fix n and let k be  
arbitrary, and get the same results. Probably something like 4 is big  
enough.

7. PROBABILISTIC UPPER SHIFT VECTOR GAMES.

Here we consider the Upper Shift Vector Game of section 6, where Alice  
is required to mindlessly play RANDOMLY. Then we can think of Bob as  
playing a solitaire game against NATURE.

Of course, by the Propositions of section 6, Bob has a winning  
strategy for which it is 100% certain that Bob will not make a losing  
move.

But we can merely assert that it is likely that Bob will not make a  
losing move. The result is that this change from "certainly" to  
"likely" yields the same results as in section 6. Instead of using  
1/2, we can use any given positive probability.

8. TEMPLATES.

The choice of the upper shift function can be conveniently abstracted  
away.

Note that the upper shift if the obvious lifting of the one  
dimensional upper shift from Q into Q to higher dimensions.

We let PPL(Q) be the family of partial f:Q into Q given by

a_1x + b_1 if x in I_1
...
a_nx + b_n if x in I_n

where n >= 1, the a's,b's are rationals, and the I's are pairwise  
disjoint nonempty intervals with rational endpoints (or +-infinity).

In sections 2-6, we can use any finite list from PPL(Q) instead of  
just the upper shift. Thus instead of setting an extra term to be the  
upper shift of the previous term, we can reserve several terms, one  
each for each function in the finite list from PPL(Q). Take care of  
undefinedness using repeats.

The conjecture is that this leads to statements that are provable or  
refutable in SUB+ - whereas some instances are neither provable nor  
refutable in SUB (namely the ones using the upper shift). So,  
according to this conjecture, large cardinals are sufficient to settle  
all resulting questions, but ZFC is not sufficient.

If we use the shift f:Q into Q, where f(x) = x+1, then the statements  
are refutable in RCA_0.

If we use the restricted upper shift f:Q into Q, where f(x) = x+1 if x  
 >= 0; undefined otherwise, then the statements are provable in ZFC.

9. EXERCISES.

There are two obvious kinds of exercises.

i. Make k very small, or make n very small. Then try to prove the  
statements.
ii. Make k small, or even moderate, and write down some specific  
strictly dominating order invariant R contained in Q^k x Q^k. These  
can be presented by merely listing finitely many 2k tuples from  
{1,...,2k}. Try to prove the statements for just R.

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

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

Harvey Friedman