[FOM] 370:Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Thu Nov 19 03:46:05 EST 2009
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
More information about the FOM
mailing list