[FOM] 383:Upper Shift Greedy Clique Sequences and Large Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
Wed Dec 30 15:25:21 EST 2009
Notice that in #382, I dropped the sequences. However, I have a
different way of doing them so that they work well for both the SRP
statements and the HUGE statements.
CURRENT BOILER PLATE
I am scheduled to give a talk at the upcoming Richard Laver conference
in Boulder. That is my target date for having solid sketches of the
greedy stuff at SRP and Huge, and also I3/I2 (I3/I2 not discussed here).
This plan will smoke out any errors, as there are now some NONTRIVIAL
LAYERED IDEAS that need to be CAREFULLY CHECKED.
In the short run, I am tied up with finishing touches on my book
Boolean Relation Theory and Incompleteness (March 2009 version on my
website).
ALERT!! First of all, there was a typo in the definition of rus at the
very end. This is corrected below.
***We now think that instead of using the upper shift, with its
discontinuity at 0, we can use simply the +1 function defined only on
the nonnegative rationals***
I.e., the new upper shift would be defined as us:Q into Q, where
us(x) = x+1 if x >= 0; undefined otherwise.
Of course, this has the proper bite only because we incorporate 0
properly into the definitions.
I want to think a bit more about this important improvement.
UPPER SHIFT GREEDY CLIQUE SEQUENCES AND LARGE CARDINALS 1
by
Harvey M. Friedman
December 30, 2009
1. TERMINOLOGY.
2. THE UPPER SHIFT GREEDY CLIQUE SEQUENCE THEOREMS.
3. THE UPPER SHIFT GREEDY SET SEQUENCE THEOREMS.
4. EXTREME TERMINOLOGY.
5. THE EXTREME UPPER SHIFT GREEDY SET SEQUENCE THEOREMS.
6. TEMPLATES.
7. EXERCISES
1. Terminology.
We use Q for the set of rationals. A Q tuple is a nonempty finite
sequence from Q. We index tuples from 1.
For Q tuples x,y, we define x <= y iff max(x) <= max(y), and x < y iff
max(x) < max(y).
A simple graph on Q^k is a graph with vertex set Q^k, whose edge set
is a symmetric set of ordered pairs from Q^k whose two coordinates are
distinct.
Note that we can also view the edge set of G as a subset of Q^2k by
concatenating the two vertices in the edges.
We say that A is a clique in G if and only if for all distinct x,y in
A, (x,y) is an edge of G.
Let x,y be Q tuples. We say that x,y are order equivalent if and only if
i. x,y are of the same length.
2. for all 1 <= i,j <= lth(x), x_i < x_j iff y_i < y_j.
We say that a set E of Q tuples is order invariant if and only if for
all order equivalent Q tuples x,y, x in E iff y in E.
We say that G is a simple order invariant graph on Q^k if and only if
G is a simple graph on Q^k whose edge set is order invariant as a
subset of Q^2k.
The upper shift of a Q tuple is the result of adding 1 to all of its
nonnegative coordinates.
The upper shift of a set of Q tuples is the set of upper shift of its
elements.
The complexity of rationals is defined as follows. c(q) is the least
integer n such that q is the ratio of integers of magnitude at most n.
The complexity of tuples of rationals, c(x), is the maximum of the
complexities of its coordinates.
Let alpha be a finite or infinite sequence. We enumerate the
subsequences of alpha of length k according to their sequence of
indices in alpha, under reverse lexicographic order, indexed from 1.
If alpha has repetitions then this enumeration has repetitions.
SRP+ = ZFC + "for all k there exists a limit ordinal with the k-SRP".
SRP = ZFC + {there is a limit ordinal with the k-SRP}_k. Here SRP =
"stationary Ramsey property". The SRP hierarchy is intertwined with
the subtle, almost ineffable, and ineffable cardinal hierarchies. EFA
= exponential function arithmetic.
2. The Upper Shift Greedy Clique Sequence Theorems.
Let G be a simple graph on Q^k. A G-sequence is a nonempty sequence
x[1],...,x[n] from Q^k with the following properties.
i. x[1] is the 0 vector.
ii. Let 2 <= 2m <= n. Let y be the m-th subsequence of length k of the
concatenation of x[1],...,x[2m-1]. Then x[2m] <= y and (y,x[2m]) is
not an edge of G. If 2m < n then x[2m+1] is the upper shift of x[2m].
iii. {x[2],...,x[n]} is a clique in G.
We also define G-sequences of infinite length in the obvious way.
THEOREM 2.1. THE G-SEQUENCE THEOREM. For every simple order invariant
graph G on Q^k, there are G-sequences of every finite length.
THEOREM 2.2. For every simple order invariant graph G on Q^k, there is
an infinite G-sequence.
THEOREM 2.3. For every simple order invariant graph G on Q^k, there is
a G-sequence of length k.
THEOREM 2.4. THE CONCRETE G-SEQUENCE THEOREM. For every simple order
invariant graph G on Q^k, there is a G-sequence of length k, whose
terms have complexity at most (8k)!!. (A ridiculously large but safe
upper bound).
Note that Theorems 2.1, 2.3 are explicitly Pi02. Note that Theorem 2.4
is explicitly Pi01.
THEOREM 2.5. Theorems 2.1 - 2.4 are provable in SRP+ but not in any
consistent fragment of SRP that proves RCA_0. Theorem 2.2 is provably
equivalent to Con(SRP) over WKL_0. Theorems 2.1,2.3,2.4 are provably
equivalent to Con(SRP) over EFA.
3. The Upper Shift Greedy Set Sequence Theorems.
This is an entirely parallel development. We need a few additional
definitions.
A digraph on Q^k is a graph with vertex set Q^k, whose edge set is a
set of ordered pairs from Q^k.
We say that A is a down clique in G if and only if for all x > y from
A, (x,y) is an edge of G.
Let G be a digraph on Q^k. A G-sequence is a nonempty sequence
x[1],...,x[n] from Q^k with the following properties.
i. x[1] is the 0 vector.
ii. Let 2 <= 2m <= n. Let y be the m-th subsequence of length k of the
concatenation of x[1],...,x[2m-1]. Then x[2m] = y, or (x[2m] < y and
(y,x[2m]) is not an edge of G). If 2m < n then x[2m+1] is the upper
shift of x[2m].
iii. {x[2],...,x[n]} is a down clique in G.
We also define G-sequences' of infinite length in the obvious way.
THEOREM 3.1. THE G-SEQUENCE THEOREM. For every order invariant digraph
G on Q^k, there are G-sequences of every finite length.
THEOREM 3.2. For every order invariant digraph G on Q^k, there is an
infinite G-sequence.
THEOREM 3.3. For every order invariant digraph G on Q^k, there is a G-
sequence of length k.
THEOREM 3.4. THE CONCRETE G-SEQUENCE' THEOREM. For every order
invariant digraph G on Q^k, there is a G-sequence of length k, whose
terms have complexity at most (8k)!!. (A ridiculously large but safe
upper bound).
Note that Theorems 3.1, 3.3 are explicitly Pi02. Note that Theorem 3.4
is explicitly Pi01.
THEOREM 3.5. Theorems 3.1 - 3.4 are provable in SRP+ but not in any
consistent fragment of SRP that proves RCA_0. Theorem 2.2 is provably
equivalent to Con(SRP) over WKL_0. Theorems 2.1,2.3,2.4 are provably
equivalent to Con(SRP) over EFA.
4. The Extreme Upper Shift Greedy Set Sequence Theorems.
A digraph on Q^k union Q^k+1 is a graph G with vertex set Q^k union Q^k
+1, whose edge set is a set of ordered pairs from Q^k union Q^k+1.
We say that A is a down clique in G if and only if for all x > y from
A intersect Q^k, (x,y) is not an edge of G.
We define [a,b] = {q in Q: a <= q <= b}.
HUGE+ = ZFC + "for all n, there is an n-huge cardinal". HUGE = ZFC +
{there exists an n-huge cardinal}_n.
Let G be a digraph on Q^k union Q^k+1. A G-sequence is a nonempty
sequence x[1],...,x[n] from Q^k union Q^k+1 with the following
properties.
i. x[1] is the 0 vector.
ii. Let 2 <= 4m <= n-3. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1] and z be the m-th subsequence of
length 2. Then x[2m] = y, or (x[2m] < y and (y,x[2m]) is not an edge
of G). x[2m+1] is the upper shift of x[2m]. If x[2m+1] in [1,k]^k then
x[2m+2] = (k+(1/2),x[2m+1]). If x[2m] = (k+(1/2),y) then x[2m+3] = y-1.
iii. {x[2],...,x[n]} is a down clique in G.
ALERT!! If the alert at the top of the page is confirmed, there will
be some simplifications in clause ii above.
We also define G-sequences of infinite length in the obvious way.
THEOREM 4.1. THE G-SEQUENCE THEOREM. For every order invariant digraph
G on Q^k union Q^k+1, there are G-sequences of every finite length.
THEOREM 4.2. For every order invariant digraph G on Q^k union Q^k+1,
there is an infinite G-sequence.
THEOREM 4.3. For every order invariant digraph G on Q^k union Q^k+1,
there is a G-sequence of length k.
THEOREM 4.4. THE CONCRETE G-SEQUENCE THEOREM. For every order
invariant digraph G on Q^k, there is a G-sequence of length k, whose
terms have complexity at most (8k)!!. (A ridiculously large but safe
upper bound).
Note that Theorems 4.1, 4.3 are explicitly Pi02. Note that Theorem 4.4
is explicitly Pi01.
THEOREM 4.5. Theorems 4.1 - 4.4 are provable in SRP+ but not in any
consistent fragment of SRP that proves RCA_0. Theorem 2.2 is provably
equivalent to Con(SRP) over WKL_0. Theorems 4.1,4.3,4.4 are provably
equivalent to Con(SRP) over EFA.
5. Templates, Completeness.
We let PPL(Q) be the family of partial rational piecewise linear
functions 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).
COMPLETENESS CONJECTURE 1. In The Upper Shift Greedy Clique Theorem,
if we fix k and replace the upper shift by any finite list from
PPL(Q), then the resulting statement is provable or refutable in SRP.
COMPLETENESS CONJECTURE 2. In The Extreme Upper Shift Greedy Set
Theorem, if we fix k and replace the upper shift by any finite list
from PPL(Q), then the resulting statement is provable or refutable in
HUGE.
I believe in the Completeness Conjecture 1, but not in the
Completeness Conjecture 2. I think that I can go well beyond I3, and
likely beyond I1 - but I am not ready to claim it. However, I do think
it holds if we replace HUGE by the NBG + "there exists a nontrivial
elementary embedding from V into V".
The instances of the Templates for the shift s:Q into Q, where s(x) = x
+1, are refutable in RCA_0.
The instances of the Templates for the restricted upper shift rus:Q
into Q, where rus(x) = x+1 if x > 0; undefined otherwise, are provable
in RCA_0.
See ALERT!! at the top of this posting.
6. Exercises.
There are two obvious kinds of exercises.
i. Make the dimension k very small, or make the length n very small.
Then try to prove the statements.
ii. Make the dimension k small, or even moderate, and write down some
specific simple order invariant graphs, order invariant digraphs on
Q^k and on Q^k union Q^k+1. These can be presented by merely listing
finitely many 2k tuples from {1,...,2k} (and 2k+2 tuples from {1,...,2k
+2}), whose set of coordinates is an initial segment of {1,...,2k} (or
{1,...,2k+2}). Try to prove the statements for just G.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 383rd 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
Harvey Friedman
More information about the FOM
mailing list