[FOM] 373:Upper Shifts, Greedy Chains, Vector Reduction, and Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Mon Dec 7 09:17:16 EST 2009
We make various improvements on http://www.cs.nyu.edu/pipermail/fom/2009-November/014188.html
One is to use what is arguably the most common notion of chain - that
any two distinct elements are related. We did not use the most common
notion of chain - but rather "lower chain" - in http://www.cs.nyu.edu/pipermail/fom/2009-November/014188.html
I had previously thought that using the most common notion of chain
would come at a serious cost, but I was mistaken. This is clearly
preferable.
We have also dropped some material in order to focus on the most
elegant. In particular, we no longer use Z (always use Q), and we drop
the Tree Pruning.
At the moment, the connection with Greedy Algorithms from computer
science looks most promising.
THIS IS A SELF CONTAINED RESTATEMENT.
THE UPPER SHIFT GREEDY CHAIN THEOREM, AND LARGE CARDINALS
by
Harvey M. Friedman
December 7, 2009
1. Terminology.
2. The Greedy Chain Theorem.
4. The Upper Shift Greedy Chain Theorem.
5. The Extreme Upper Shift Greedy Chain Theorems.
6. Finite Forms.
7. Upper Shift Vector Reduction Games.
8. Upper Shift Vector Reduction Sequences.
9. Templates.
10. 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 A be contained in 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 an R chain if and
only if for all distinct x,y in A, R(x,y).
We say that A is a maximal R chain if and only if
i. A is an R chain.
ii. For all x in fld(A)^k, x in A, or there exists y in A such that
{x,y} is not an R chain.
We will not be using maximal chains, but rather a strong form of
maximal chains, called greedy chains.
We say that A is a greedy R chain if and only if
i. A is an R chain.
ii. For all x in fld(A)^k, x in A, or there exists y in A such that
max(y) <= max(x) and {x,y} is not an R chain.
More generally, let S be contained in Q. We say that A is an S-greedy
R chain if and only if
i. A is an R chain.
ii. For all x in (fld(A) union S)^k, x in A, or there exists y in A
such that
max(y) <= max(x) and {x,y} is not an R chain.
NOTE: It is easy to see that {x,y} is not an R chain if and only if
x,y are distinct and R incomparable.
We also work with the following more specialized notion.
Let R be contained in Q^k x Q^k, and V be contained in Q^k.
We say that A is an R,V chain if and only if
i. A is contained in Q^k.
ii. For all x,y in A, if max(y) < max(x) and x in V, then R(x,y).
Let S be contained in Q. We say that A is an S-greedy R,V chain if and
only if
i. A is an R,V chain.
ii. For all x in V intersect (fld(A) union S)^k, x in A, or there
exists y in A such that
max(y) < max(x) and not R(x,y).
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 Q^k x Q^k is order invariant if and only if
R is order invariant as a subset of Q^2k.
2. THE GREEDY CHAIN THEOREM.
THEOREM 2.1. THE GREEDY 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-greedy chain for R contained in S^k.
ii. S is a well ordered subset of Q.
THEOREM 2.2. If R is contained in V x Q^k, where V is contained in
Q^k, and S is a well ordered subset of Q, then there is an S,V-
greedy chain for R that is contained in S^k.
THEOREM 2.3. The following special case of The Greedy 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-greedy 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-greedy 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-greedy 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 UPPER SHIFT GREEDY CHAIN THEOREM.
PROPOSITION 3.1. THE UPPER SHIFT GREEDY CHAIN THEOREM. Every
order invariant R contained in Q^k x Q^k has an N-greedy chain
containing its upper shift.
Proposition 3.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 3.2. The Upper Shift Greedy Chain Theorem is provable
in SRP+ but not in any consistent fragment of SRP. The Upper Shift
Greedy 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
Greedy Chain Theorem.
THEOREM 3.3. Let k >= 1. Proposition 3.2 for k is provable in ZFC +
"there exists lambda with the k-SRP".
THEOREM 3.4. Let k be sufficiently large. Proposition 3.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.
4. EXTREME UPPER SHIFT GREEDY 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.
PROPOSITION 4.1. THE EXTREME UPPER SHIFT GREEDY CHAIN THEOREM. For all
order invariant R contained in Q^kne x Q^k, k >= 3, there is an N-
greedy R,Q^kne chain that is strongly upper shift closed.
Here is a more abstract form of Proposition 4.1.
PROPOSITION 4.2. For all order invariant R contained in Q^kne x Q^k,
k >= 3, there is an N-greedy R,Q^kne that is strongly f closed for some
nontrivial f.
PROPOSITION 4.3. For all order invariant R contained in Q^kne x Q^k,
k >= 3, there is an N-greedy R,Q^kne 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 4.4. Propositions 4.1,4.2 are provable in HUGE+
but not in any consistent fragment of HUGE. Propositions 4.1,4.2 are
provably equivalent, over WKL_0, to Con(HUGE). Proposition 4.3 is
provable in NBG + I2 but not in any consistent fragment of ZFC + I3.
The implications Con(NBG + I2) implies Proposition 4.3 implies Con(ZFC
+ I3) are provable in WKL_0. Proposition 4.3 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.
5. FINITE UPPER SHIFT GREEDY CHAIN THEOREMS.
Let S be contained in Q. We say that B is an S-greedy R chain over A
if and only if
i. A union B is an R chain.
ii. For all x in (fld(A) union S)^k, x in A, or there exists y in B
such that max(y) <= max(x) and {x,y} is not an R chain.
PROPOSITION 5.1. 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
A_i+1 is a {0}-greedy R chain over A_i that contains the upper shift
of A_i.
PROPOSITION 5.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
A_i+1 is a {0}-greedy R chain over A_i that contains the upper shift
of A_i, and where each rational used has numerator and denominator of
magnitude at most (8kn)!!.
Note that Proposition 5.1 is explicitly Pi02, and Proposition 5.2 is
explicitly Pi01.
THEOREM 5.3. The Upper Shift Greedy Chain Theorem (Proposition
3.1), and Propositions 5.1-5.3 are provably equivalent over WKL_0. Hence
Theorem 3.4 applies.
6. FINITE EXTREME UPPER SHIFT GREEDY CHAIN THEOREMS.
Let R be contained in V x Q^k. Let S be contained in Q. We say that B
is an S-greedy R,V chain over A if and only if
i. A union B is an R,V chain.
ii. For all x in (fld(A) union S)^k, x in A, or there exists y in B
such that max(y) <= max(x) and {x,y} is not an R,V chain.
We say that C is strongly upper shift closed over A,B if and only if
i. C contains the upper shift of A union B.
ii. For all x in fld(A^k-1), there exists y in fld(B^k-1), such that
the lower cross section at y in C is the upper shift of the lower
cross section at x in C.
PROPOSITION 6.1. For all order invariant R contained in Q^kne x Q^k,
and n >= 1, there exist finite A_1,...,A_n contained in Q^k such that
each A_i+2 is a {0}-greedy R,Q^kne chain over A_i+1 that is strongly
upper shift closed over A_i,A_i+1.
PROPOSITION 6.2. For all order invariant R contained in Q^kne x Q^k,
and n >= 1, there exist finite A_1,...,A_n contained in Q^k such that
each A_i+2 is a {0}-greedy R,Q^kne chain over A_i+1 that is strongly
upper shift closed over A_i,A_i+1, where each rational used, in
reduced form, has numerator and denominator of magnitude at most
(8kn)!!.
Note that Proposition 6.1 is explicitly Pi02, and Proposition 6.2 is
explicitly Pi01.
THEOREM 6.3. The Extreme Upper Shift Greedy Chain Theorem (Proposition
4.1), and Propositions 6.1-6.2 are provably equivalent over WKL_0. Hence
Theorem 4.4 applies.
Going further, treating Proposition 4.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.4. 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 4.2 and 4.3 are of the above
form. Hence by general principles (i.e., Theorem 6.4), 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 Greedy Chain Theorem and the Extreme
Upper Shift Greedy Chain Theorem, and even Proposition 4.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
Greedy Chain Theorem only. NOTE: We expect to make a later posting
where we treat The Extreme Upper Shift Greedy Chain Theorem in this way.
Let R be contained in Q^k x Q^k. We present the game G(R,n), where 1
<= n <= infinity.
In G(R,n), Alice and Bob alternately make n moves, starting with
Alice. Every move of Alice is an element of Q^k. Every move of Bob has
two parts. Each part is an
element of Q^k.
Every move of Alice is required to consist of rationals, each of which
is 0, or has appeared in earlier moves of the game (by Alice or by Bob).
This requirement does not apply to Bob.
NOTE: There is a lot of robustness here. We can vary this requirement
on Alice's moves in many ways without changing our results. E.g., we
can demand that Alice play a subsequence of the concatenation of Bob's
previous moves. From a game theoretic point of view, probably our
present choice of requirement on Alice's moves is most natural.
NOTE: This requirement forces Alice's first move to be the zero vector.
Suppose Alice has just played x in Q^k. The first part of Bob's
response is
required to be x, or
some y with max(y) <= max(x) such that {x,y} is not an R chain.
The second part of Bob's response is required to be the upper shift of
the first part of Bob's response.
Bob is considered the winner if and only if the set of Bob's moves
constitute an R chain.
PROPOSITION 7.1. For all order invariant R contained in Q^k x Q^k, and
1 <= n <= infinity, Bob wins the game G(R,n).
Note that Proposition 7.1 is not explicitly Pi01, or even
arithmetical. First of all, let us omit infinite length games here.
PROPOSITION 7.2. For all order invariant R contained in Q^k x Q^k, and
n >= 1, Bob wins the game G(R,n).
To make this explicitly Pi01, we define G(R,n,t) to be the same as
G(R,n), except that all rationals used in the plays must have
numerators and denominators of magnitude at most t.
PROPOSITION 7.3. For all order invariant R contained in Q^k x Q^k, and
t >> n >= 1, Bob wins the game G(R,n,t). In fact, t > (8kn)!! is
sufficient. (This is a ridiculously high expression. We'll take this
seriously at a later time).
THEOREM 7.4. The Upper Shift Greedy Chain Theorem (Proposition
3.1), and Propositions 7.1-7.3 are provably equivalent over WKL_0.
Hence Theorem
3.4 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 a k-tuple from 1,2,...,2ik.
Let R be contained in Q^k x Q^k. An R,Gamma,n sequence is a sequence
x_1,...,x_2n from Q^k such that
i. x_1 = 0 or (max(x_1) <= 0 and {0,x_1} is not an R chain).
ii. x_2 is the upper shift of x_1.
iii. for all odd 3 <= i < 2k, x_i = y or (max(x_i) <= max(y) and
{x_i,y} is not an R chain).
iv. for all odd 3 <= i < 2k, x_i+1 is the upper shift of x_i.
Here y is the k-tuple of coordinates of x_1,...,x_2i, according to the
positions
given by alpha_i (i.e., according to the schedule Gamma).
PROPOSITION 8.1. For all order invariant R contained in Q^k x Q^k,
k,n >= 1, and k,n-schedules Gamma, there is an R,Gamma,n
sequence.
PROPOSITION 8.2. For all order invariant R contained in Q^k x Q^k, k,n
>= 1, and k,n-schedules Gamma, there is an R,Gamma,n sequence, where
the magnitudes of the denominators and numerators used are at most
(8kn)!!.
We also consider the following probabilistic weakening.
PROPOSITION 8.3. Let R be an order invariant subset of Q^k x Q^k, and
let k,n >= 1. For most k,n-schedules Gamma, there is an
R,Gamma,n,sequence.
THEOREM 8.4. The Upper Shift Greedy Chain Theorem (Proposition 3.1),
and Propositions 8.1,8.2 are provably equivalent over WKL_0. Hence
Theorem 3.4 applies.
9. 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.
10. 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
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 373rd 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
Harvey Friedman
More information about the FOM
mailing list