# [FOM] 372:Maximal Lower Chains, Vector Reduction, and Large Cardinals

Harvey Friedman friedman at math.ohio-state.edu
Thu Nov 26 05:05:32 EST 2009

```This version, with The Upper Shift Maximal Lower Chain Theorem - seems
to be more direct, natural, and compelling than the Upper Shift Fixed
Point Theorem of http://www.cs.nyu.edu/pipermail/fom/2009-October/014153.html
Accordingly, we now recast all of the work in this new way.

Finite Forms, Games and Sequences are done on both the rationals and
the integers.

We also give a pruned tree formulation, with a probabilistic form that
may become closely connected with percolation theory.

It is easy to prove the equivalence of the previous independent
statements from these new ones.

MAXIMAL LOWER CHAINS, VECTOR REDUCTION, AND LARGE CARDINALS
by
Harvey M. Friedman
November 26, 2009

1. Terminology.
2. The Lower Maximal Chain Theorem.
3. The Maximal Chain Theorem (digression).
4. The Upper Shift Lower Maximal Chain Theorem.
5. The Extreme Upper Shift Lower Maximal Antichain Theorems.
6. Finite Forms in Q and Z.
7. Upper Shift Vector Reduction Games.
8. Upper Shift Vector Reduction Sequences.
9. Tree Pruning.
10. Templates.
11. Exercises.

1. TERMINOLOGY.

Let Q be the set of all rationals. Let Z be the set of all integers,
and N be the set of all nonnegative integers.

Let x,y in Q^k. We define x < y if and only if max(x) < max(y), and x
> y if and only if y < x.

Let A be contained in Q^k x Q^k. We write fld(A) for the set of all
rationals appearing in A.

Let R be contained in Q^k x Q^k. We say that A is a lower chain for R
if and only if for all x,y in A, if x > y then R(x,y).

Let S be contained in Q. We say that A is an S-maximal lower chain for
R if and only if A is a lower chain for R, where

for all x in (fld(A) union S)^k, either x in A or there exists y
< x from A such that not R(x,y).

We also work with the following natural generalization.

Let R be contained in V x W, where V,W are contained in Q^k. We say
that A is a lower chain for R if and only if for all x in A intersect
V, and y in A intersect W, if x > y then R(x,y).

We say that A is a S-maximal lower chain for R if and only if A is a
lower chain for R, where

for all x in (fld(A) union S)^k intersect V, either x in A, or
there exists y < x from A intersect W such that not R(x,y).

NOTE: These notions depend only on R at pairs x,y such that x in V, y
in W, and x > y. The rest of R is irrelevant.

We define the upper shift function us:Q into Q, by us(q) = q+1 if q >=
0; q otherwise.

The function us naturally lifts to us:Q^k into Q^k by acting
coordinatewise. I.e., the upper shift of x in Q^k is obtained by
adding 1 to all of its nonnegative coordinates.

The upper shift of A is the set of upper shifts of its elements. I.e.,
us(A) = {us(x): x in A}.

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 A contained in Q^k is order invariant iff for all order
equivalent x,y in Q^k, x in A iff y in A.

We say that R contained in V x W is order invariant iff for all x,y in
V and z,w in W, if (x,z) and (y,w) are order equivalent (as elements
of Q^2k)), then R(x,z) iff R(y,w).

2. THE MAXIMAL LOWER CHAIN THEOREM.

THEOREM 2.1. THE MAXIMAL LOWER CHAIN THEOREM. Let R be contained in
Q^k x Q^k, and S be a subset of Q. The following are equivalent.
i. There is an S-maximal lower chain for R contained in S^k.
ii. There is a unique S-maximal lower chain for R contained in S^k.
iii. S is a well ordered subset of Q.

THEOREM 2.2. If R is contained in V x W, where V,W are contained in
Q^k, and S is a well ordered subset of Q, then there is a unique S-
maximal lower chain for R contained in S^k union W.

THEOREM 2.3. The following special case of The Maximal Lower Chain
Theorem is provably equivalent to ATR_0 over RCA_0 (even if we remove
"contained in S"). If R is contained in Q x Q and S is a well ordered
subset of Q, then there is an S-maximal lower chain for R contained in
S. Theorems 2.1 and 2.2 are provable in ATR_0.

THEOREM 2.4. If R is order invariant, then the N-maximal lower chain
contained in N^k is elementary recursive, but can have a rather
complicated structure. The statement "every order invariant R
contained in Q^k x Q^k has an S-maximal lower chain contained in S^k"
holds for continuumly many S up to order isomorphism. In fact, the S
can be classified up to isomorphism, and the classification
necessarily involves recursion theoretic notions. As long as k is
sufficiently large, the classification does not depend on k. In fact,
something like >= 4 suffices.

3. THE MAXIMAL CHAIN THEOREM (digression).

It is interesting to compare The Maximal Lower Chain Theorem with The
Maximal Chain Theorem. We will only consider R contained in Q^k x Q^k.
We say that A is a chain for R if and only if for all x,y in A, R(x,y).

Let S be contained in Q. We say that A is a S-maximal chain for R if
and only if A is a chain for R, where

for all x in (fld(A) union S)^k, either x in A, or there exists y
in A such that not R(x,y).

Chains and S-maximal chains for R behave quite differently from lower
chains and S-maximal lower chains for R. Compare the following with
The Maximal Lower Chain Theorem.

THEOREM 3.1. For all R contained in Q^k x Q^k and S contained in Q,
there is an S-maximal chain for R contained in S^k. For some R and
well ordered S, there are continuumly many S-maximal chains for R
contained in S^k. These statements are provable in RCA_0.

4. THE UPPER SHIFT MAXIMAL LOWER CHAIN THEOREM.

PROPOSITION 4.1. THE UPPER SHIFT MAXIMAL LOWER CHAIN THEOREM. Every
order invariant R contained in Q^k x Q^k has an N-maximal lower chain
containing its upper shift.

Proposition 4.1 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 4.2. The Upper Shift Maximal Lower Chain Theorem is provable
in SRP+ but not in any consistent fragment of SRP. The Upper Shift
Maximal Lower Chain Theorem is provably equivalent, over WKL_0, to
Con(SRP). This is also true if we replace N by {0} in The Upper Shift
Maximal Lower Chain Theorem.

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

THEOREM 4.5. Let k be sufficiently large. Proposition 4.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 (tentative, may
have to be raised somewhat) is not provable in ZFC.

5. EXTREME UPPER SHIFT MAXIMAL LOWER CHAIN THEOREMS.

Let A be contained in Q^k. We write Ane for the set of all elements of
A whose coordinates are distinct. Here ne stands for the unequal sign.

The lower sections of A are sets of the form {y < max(x): (x,y) in A},
for fixed x in Q^k-1.

Let f:Q into Q. We use the coordinatewise lifting of f to f:Q^k into
Q^k. We say that f is nontrivial if and only if f is not the identity
function.

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

We say that a lower section is below a rational p if and only if all
of its elements are < p.

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

for all lower sections E of A, f[E] is a lower section of A.

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

for all lower sections E of A below p, f[E] is a lower section of
A below p.

Here are three variants of the Upper Shift Lower Maximal Chain
Theorem, Proposition 4.1, that is just as strong.

PROPOSITION 5.1. Every order invariant R contained in Q^kne x Q^k
(Q^kne x Q^kne, Q^k x Q^kne) has an N-maximal lower chain containing
its upper shift.

Here is our first Extreme Theorem.

PROPOSITION 5.2. THE EXTREME UPPER SHIFT LOWER MAXIMAL CHAIN THEOREM.
Every order invariant R contained in Q^kne x Q^k, k >= 3, has an N-
maximal lower chain that is strongly upper shift closed.

Here is a more abstract form of Proposition 3.2.

PROPOSITION 5.3. Every order invariant R contained in Q^kne x Q^k, k
>= 3, has an N-maximal lower chain that is strongly f closed for some
nontrivial f.

PROPOSITION 5.4. Every order invariant R contained in Q^kne x Q^k, k
>= 3, has an N-maximal lower chain that is 2-strongly f closed for
some f with f(0) = 1 and f(2) = 2.

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 5.5. The three forms of Proposition 5.1 are provably
equivalent to The Upper Shift Maximal Lower Chain Theorem over WKL_0.
Hence Theorem 4.2 applies. Propositions 5.2,5.3 are provable in HUGE+
but not in any consistent fragment of HUGE. Propositions 5.2,5.3 are
provably equivalent, over WKL_0, to Con(HUGE). Proposition 5.4 is
provable in NBG + I2 but not in any consistent fragment of ZFC + I3.
The implications Con(NBG + I2) implies Proposition 5.4 implies Con(ZFC
+ I3) are provable in WKL_0. Proposition 5.4 is provably equivalent to
a Pi01 sentence over WKL_0. We can use a strengthened from of I3;
e.g., there are arbitrarily large alpha with a proper elementary
embedding j:V(alpha) into V(alpha), and more.

6. FINITE FORMS IN Q AND Z.

We first give finite forms for The Upper Shift Maximal Lower Chain
Theorem and The Extreme Upper Shift Maximal Lower Chain Theorem.

Let R be contained in V x W, where V,W are contained in Q^k. We say
that A,B is a lower chain pair for R if and only if

i. A is contained in B.
ii. for all x in B intersect V, and y in B intersect W, if x > y then
R(x,y).

We say that A,B is an S-maximal lower chain pair for R if and only if

i. A,B is a lower chain pair for R.
ii. for all x in (fld(A) union S)^k intersect V, there exists y < x
from B intersect W such that not R(x,y).

Let A,B be contained in Q^k. We say that A,B is us closed if and only
if B contains us(A).

PROPOSITION 6.1. For all order invariant R contained in Q^k x Q^k,
there exist finite A_1,A_2,... contained in Q^k such that each
consecutive pair is a us closed {0}-maximal lower chain pair for R.

PROPOSITION 6.2. For all order invariant R contained in Q^k x Q^k, and
n >= 1, there exist finite A_1,...,A_n contained in Q^k such that each
consecutive pair is a us closed {0}-maximal lower chain pair for R.

PROPOSITION 6.3. For all order invariant R contained in Q^k x Q^k, and
n >= 1, there exist finite A_1,...,A_n contained in Q^k such that each
consecutive pair is a us closed {0}-maximal lower chain pair for R,
where each rational used, in reduced form, has numerator and
denominator of magnitude at most (8kn)!!.

Note that Proposition 6.2 is explicitly Pi02, and Proposition 6.3 is
explicitly Pi01.

THEOREM 6.4. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.2),
and Propositions 6.1-6.3 are provably equivalent over WKL_0. Hence
Theorem 4.3 applies.

We now give a finite form of The Extreme Upper Shift Maximal Lower
Chain Theorem.

We say that A,B,C is an S-maximal lower chain triple for R if and only
if A,B and B,C are S-maximal lower chain pairs for R.

We say that A,B,C is strongly us closed if and only if

i. A,B and B,C are us closed.
ii. us of any lower section of C at an element of fld(A)^k-1 is a
lower section of C at an element of fld(B)^k-1.

PROPOSITION 6.5. For all order invariant R contained in Q^kne x Q^k, k
>= 3, there exist finite A_1,A_2,... contained in Q^k such that each
consecutive triple is a strongly us closed {0}-maximal lower chain
triple for R.

PROPOSITION 6.6. For all order invariant R contained in Q^kne x Q^k,
k,n >= 3, there exist finite A_1,,...,A_n contained in Q^k such that
each consecutive triple is a strongly us closed {0}-maximal lower
chain triple for R.

PROPOSITION 6.7. For all order invariant R contained in Q^kne x Q^k,
k,n >= 3, there exist finite A_1,,...,A_n contained in Q^k such that
each consecutive triple is a strongly us closed {0}-maximal lower
chain triple for R, where each rational used, in reduced form, has
numerator and denominator of magnitude at most (8kn)!!.

Note that Proposition 6.6 is explicitly Pi02, and Proposition 6.7 is
explicitly Pi01.

THEOREM 6.8. The Extreme Upper Shift Maximal Lower Chain Theorem
(Proposition 5.2),
and Propositions 6.5-6.7 are provably equivalent over WKL_0. Hence
Theorem 5.3 applies.

We can transfer the setting to the set of all integers, Z.

Let r be a positive integer. We define us^r:Q into Q by us^r(x) = x+r
if x >= 0; x otherwise. We lift us^r to us^r:Q^k into Q^k
coordinatewise.

We extend the definitions of us closed and strongly us closed to us^r
closed and strongly us^r closed by simply replacing us with us^r.

PROPOSITION 6.9. For all order invariant R contained in Z^k x Z^k and
r >> k,n >= 1, there exist A_1,...,A_n contained in [-rn,rn]^k such
that each consecutive pair is a us^r closed {0}-maximal lower chain
pair for R. In fact, r > (8kn)!! suffices. Here the interval is from Z.

PROPOSITION 6.10. For all order invariant R contained in Z^kne x Z^k
and r >> k,n >= 3, there exist A_1,...,A_n contained in [-rn,rn]^k
such that each consecutive triple is a strongly us^r closed {0}-
maximal lower chain triple for R. In fact, r > (8kn)!! suffices. Here
the interval is from Z.

Note that Propositions 6.9 and 6.10 are explicitly Pi01.

THEOREM 6.11. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.1) is provably equivalent to Proposition 6.9 over WKL_0. Hence
Theorem 4.3 applies. The Extreme Upper Shift Maximal Lower Chain
THeorem (Proposition 5.2) is provably equivalent to Proposition 6.10
over WKL_0. Hence Theorem 5.3 applies.

Going further, treating Proposition 5.4 between I3 and I2, starts to
get awkward. Rather than go that route here, we instead use a general
theory of finite forms for statements of this kind.

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 6.12. 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.5), 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 Maximal Lower Chain Theorem and the Extreme
Upper Shift
Maximal Lower Chain Theorem, and even Proposition 5.4, without having
to give a specific finite form.

7. UPPER SHIFT VECTOR REDUCTION GAMES.

We will focus on a finite game theoretic form of The Upper Shift
Maximal Lower Chain Theorem only.

Let R be contained in Z^k x Z^k. We present the game G(R,us,r,n),
where 1 <= n,r <= infinity. In G(R,us,r,n), Alice and Bob alternately
make n moves, starting with Alice. Every move of Alice is an element
of [-rn,rn]^k. Every move of Bob has two parts. Each part is an
element of [-rn,rn]^k.

Alice's first move is required to be 0 in Z^k. Each of Alice's later
moves are required to be a length k subsequence of the concatenation
of Bob's previous moves.

Suppose Alice has just played x. The first part of Bob's response is
required to be x, or some y < x with not R(x,y). The second part of
Bob's response is required to be us^r of the first part of Bob's
response.

At the end of the game, the winner is determined as follows. Bob wins
if and only if his moves form a lower chain for R.

PROPOSITION 7.1. For all order invariant R contained in Z^k x Z^k, and
r >> k,n >= 1, Bob wins G(R,us,r,n). Here r > (8kn)!! suffices.

Note that Proposition 7.1 is explicitly Pi01.

THEOREM 7.2. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.1),
and Proposition 7.1 are provably equivalent over WKL_0. Hence Theorem
4.2 applies.

8. UPPER SHIFT VECTOR REDUCTION SEQUENCES.

We can remove Alice from the picture by providing Alice with what we
call a schedule. Then she no longer has any freedom, and so we are
back into the realm of pure combinatorics, and away from game theory.

A k,n-schedule consists of a list Gamma = alpha_1,...,alpha_n, where
alpha_i is a subsequence of 1,2,...,2ik.

Let R be contained in Z^k x Z^k. An R,Gamma,r,n sequence is a sequence
x_1,...,x_2k from [-rn,rn]^k such that

i. x_1 = 0 or (x_1 < 0 and R(0,x_1)).
ii. x_2 = us^r(x_1).
iii. for all odd 3 <= i < 2k, x_i = y or (max(x_i) < max(y) and
R(x_i,y)).
iv. for all odd 3 <= i < 2k, x_i+1 = us^r(x_i).

Here y is the subsequence of x_1,...,x_2i according to the positions
given by alpha_i.

PROPOSITION 8.1. For all order invariant R contained in Z^k x Z^k, r
>> k,n >= 1, and k,n-schedules Gamma, there is an R,Gamma,r,n
sequence. Here r > (8kn)!! suffices.

THEOREM 8.3. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.1),
and Propositions 8.1,8.2 are provably equivalent over WKL_0. Hence
Theorem 4.2 applies.

We also consider the following probabilistic weakening.

PROPOSITION 8.2. Let R be an order invariant subset of Z^k x Z^k, and
let r >> k,n >= 1. For most k,n-schedules Gamma, there is an
R,Gamma,r,n,sequence. Here r > (8kn)!! suffices.

THEOREM 8.3. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.1),
and Propositions 8.1,8.2 are provably equivalent over WKL_0. Hence
Theorem 4.2 applies.

9. TREE PRUNING.

Let R be an order invariant subset of Z^k x Z^k, and let r >> k,n >= 1.

We begin by describing a natural finite labeled tree T(k,r,n) of
height 3n over the root. Each label is an element of [-rn,rn]^k. This
very thick tree does not depend on R.

We then prune the tree in a simple way according to R. It is still
clear that this pruned tree, T(R,k,r,n), has height 3n.

So far, the constructions are deterministic.

Finally, we nondeterministically prune the tree severely at all levels
3 < 3i+1 < 3n, creating TREE(R,k,r,n). It is natural to start this
final pruning from level 4 up. In this pruning, every vertex of level
3i+1 with a son, is left with exactly one son. The Unprovable Theorem
states that no matter how this pruning is done, we are left with a
tree of height 3n. I.e., there is a path though the pruned tree with
3n vertices (repetitions may be present).

We also consider the weakened statement: if this final pruning is done
randomly, then it is likely that the pruned tree has height 3n. This
weakened statement is also an Unprovable Theorem.

The root of T(k,r,n) is labeled 0 in [-rn,rn]^k. This completes the
construction of the first level of T(k,r,n). Suppose the first 3i+1
levels of T(k,r,n) have been constructed, 3 < 3i+1 < 3n. Let v be a
vertex of level 3i+1 with label x in Q^k. We create a son of v with
label y for every y in [-rn,rn]^k. Let v' be one of these sons of v,
with label y. We create exactly one son of v', with the label us(y).

The above defines the first 3i+3 levels of T(k,r,n). Now suppose 3i+3
< 3n. Let v be a vertex of level 3i+3, with label y. Let beta be the
concatenation of the labels used along the path from the root up
through v. We create a son of v for each z in [-rn,rn]^k that is a
subsequence of beta. We will have exactly one son for each
subsequence, so we won't repeat labels. Of course, a label used for a
son of v may already appear as a label lower down.

This completes the deterministic construction of T(k,r,n).

We now deterministically prune T(k,r,n) according to R. It is natural
to prune inductively. We consider level 1 as having been pruned (this
is only the root).

Suppose we have already pruned the first 3i+1 levels of T(k,r,n), 0 <=
i < n, so that we have determined what the first 3i+1 levels of
T(R,k,r,n) are. Let v be a remaining vertex of level 3i+1 with label x
in [-rn,rn]^k. Let v' be a son of v with label y, in T(k,r,n). Then v'
survives the pruning if and only if

i. y = x or (max(y) < max(x) and R(x,y)).
ii. The labels of the vertices in the path from the root up through
v', whose levels are NOT 1,4,7,10,..., form an R chain.

After this pruning, there is no pruning at the next two levels. This
completes the deterministic construction of T(R,k,r,n).

Finally, we come to the nondeterministic inductively implemented
pruning to form TREE(R,k,r,n).

Suppose we have already pruned the first 3i levels of T(R,k,r,n), 1 <=
i < n. Let v be a remaining vertex of level 3i. There may or may not
be a son of v in T(R,k,r,n). If there is none, then we do no pruning
of the sons of v, since there aren't any. If there is at least one son
of v in T(R,k,r,n), then we remove all of these sons but one.

This is the only pruning done to create TREE(R,k,r,n).

PROPOSITION 9.1. For all order invariant R contained in Z^k x Z^k and
r >> k,n, >= 1, every TREE(R,k,r,n) has height 3n. Here r > (8kn)!!
suffices.

PROPOSITION 9.2. Let R contained in Z^k x Z^k be order invariant, and
r >> k,n, >= 1. Most TREE(R,k,r,n) have height 3n. Here r > (8kn)!!
suffices.

THEOREM 9.3. The Upper Shift Maximal Lower Chain Theorem (Proposition
4.1),
and Propositions 9.1,9.2 are provably equivalent over WKL_0. Hence
Theorem 4.2 applies.

The only really specialized feature of the construction of
TREE(R,k,r,n) is, of course, clause i above (and the upper shift).
However, this can be Templated by considering all possible conditions
on vectors x,y of that form. E.g., consider all possible propositional
formulas in two variables x,y, with the operator max, and the
relations <,=,R. I should be able to completely analyze their effect
on this statement (and also other statements in this abstract).

The next section discusses the Templating of the upper shift.

10. 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 this abstract, 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 SRP - whereas some instances are neither provable nor
refutable in SRP (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
here 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 here are provable in ZFC.

11. 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.

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

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
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals,
12:14PM
371: Vector Reduction and Large Cardinals, November 21, 2009  1:34AM

Harvey Friedman

```