[FOM] 450: Maximal Sets and Large Cardinals II
Harvey Friedman
friedman at math.ohio-state.edu
Mon Dec 6 00:50:30 EST 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS SELF CONTAINED.
There were a couple of misstatements in section 3 of 449: Maximal Sets
and Large Cardinals I http://www.cs.nyu.edu/pipermail/fom/2010-December/015157.html
(as well as some minor typos elsewhere). We also improve on some
expositional points.
Since this appears to be a natural stopping or pausing point of the
search for Concrete Mathematical Incompleteness of ZFC at the Pi01
level, we present a complete restatement with these misstatements fixed.
We also add a section at the end on Templates.
NOTE: We use the terminology "locally maximal" here. I was also
thinking of using "initially maximal". Comments on the terminology
would be appreciated.
*****************************************
MAXIMAL SETS AND LARGE CARDINALS
by
Harvey M. Friedman
December 5, 2010
1. A-RELATIONS, CLIQUES, UPPER SHIFT.
2. UPPER SHIFT CLIQUE THEOREMS.
3. SEQUENTIAL CLIQUE CONSTRUCTION THEOREMS.
4. TEMPLATES.
1. A-RELATIONS, CLIQUES, UPPER SHIFT.
Fix a subset A of the set Q of all rationals. The A-relations on A^k
are the order invariant subsets R of A^k x A^k = A^2k. I.e., binary
relations R, where if x,y in A^2k are order equivalent, then x in R if
and only if y in R.
The A-relations are the A-relations on the various A^k.
Let R be contained in A^k x A^k. B is an R clique if and only if B x B
is contained in R.
B is a maximal R clique if and only if B is an R clique which is not
properly contained in any R clique.
B is a locally maximal R clique if and only if for all x in A, B|<=x
is a maximal R|<=x clique. Here T|<=x is T restricted to the
vectors whose coordinates are <= x.
Note that local maximality implies maximality. However, the converse
fails.
The upper shift of a vector from Q is obtained by adding 1 to all
nonnegative coordinates. The upper shift of a set of vectors from Q is
the set of upper shifts of its elements.
2. UPPER SHIFT CLIQUE THEOREMS.
THE UPPER SHIFT MAXIMAL CLIQUE THEOREM. There exists 0 in A contained
in Q such that every A-relation has a maximal clique that contains its
upper shift.
THE UPPER SHIFT LOCALLY MAXIMAL CLIQUE THEOREM. There exists 0 in A
contained in Q such that every A-relation has a locally maximal clique
that contains its upper shift.
The only proof we know of The Upper Shift Maximal Clique Theorem uses
large cardinals. We don't know if it can be proved in ZFC, or even in
RCA_0.
We do know that it is necessary and sufficient to use large cardinals
in order to prove The Upper Shift Locally Maximal Clique Theorem.
The same situation obtains even if we restrict ourselves to symmetric
A-relations.
Specifically, let SRP+ = ZFC + "for all k, there is a limit ordinal
with the k-SRP". SRP = ZFC + {there is a limit ordinal with the k-
SRP}_k. The k-SRP asserts that every 2 coloring of the unordered k-
tuples has a stationary monochromatic set.
THEOREM 2.1. SRP+ proves The Upper Shift Locally Maximal Clique
Theorem. In fact, it is provably equivalent to Con(SRP) over WKL_0.
3. SEQUENTIAL CLIQUE CONSTRUCTION THEOREMS.
Fix a reflexive order invariant R contained in Q^k x Q^k. We present a
nondeterministic construction of a "rich" R clique. It won't quite be
a locally maximal R clique, because the field of R is much too large.
However, it will be a locally maximal R clique as far as vectors whose
coordinates are coordinates of elements of the clique are concerned.
In this sense, the Clique Construction Theorems below are more closely
related to a somewhat different form of the Upper Shift Locally
Maximal Clique Theorem than was presented in section 2. However, we
continue to believe that the versions presented in section 2, and the
versions in this section, are the most natural choices for their
purposes, even though they are not optimally synchronized. Such issues
will be explored more explicitly in a final manuscript.
The R clique constructions take the following form:
INITIALIZATION. Form the sequence of length 1 consisting of (0,...,0)
in Q^k. This is obviously an R clique.
CONTINUATION. Make successive R clique continuations, as prescribed
below.
INFINITE SEQUENTIAL CLIQUE CONSTRUCTION THEOREM. For each reflexive
order invariant R contained in Q^k x Q^k, there is an R clique
construction with infinitely many continuations.
FINITE SEQUENTIAL CLIQUE CONSTRUCTION THEOREM. For each reflexive
order invariant R contained in Q^k x Q^k, there are R clique
constructions with any given finite number of continuations.
Let x_1,...,x_p, p >= 1, be an R clique (i.e., the set {x_1,...,x_p}
is an R clique). An R clique continuation of
x_1,...,x_p takes the general form of an R clique
x_1,...,x_p,y_1',...,y_q',ush(y_1'),...,ush(y_q')
where ush is the upper shift.
The R clique continuations are constructed in two steps.
STEP 1. Choose an enumeration y_1,...,y_q without repetition, of all k-
tuples whose coordinates are among the coordinates of x_1,...,x_p. Of
course, we cannot expect x_1,...,x_p,y_1,...,y_q to be an R clique.
The order of this enumeration will play no role.
STEP 2. For each 1 <= i <= q, choose y_i' be y_i, or a vector from Q^k
of equal or lesser maximum coordinate, which is not related to y_i by
R (not an R predecessor and not an R successor). Return
x_1,...,x_p,y_1',...,y_q',ush(y_1'),...,ush(y_q').
Note that the Finite Sequential Clique Construction Theorem is
explicitly Pi02. However, it can easily be put into Pi01 form by the
following considerations.
1. Because of the enumeration without repetition in STEP 1, we have
obvious bounds on the lengths of successive continuations.
2. We then put the Finite Sequential Clique Construction Theorem in
the form "for all relevant R,n, there is an R clique construction with
n continuations according to the decision procedure for the ordered
group of rationals".
3. Alternatively, we can put bounds on the numerators and denominators
needed for the Finite Sequential Clique Construction Theorem, relative
to k,n, (dimension k with n continuations), by working directly with <
on Q and +1 on Q.
THEOREM 3.1. The Infinite Sequential Clique Construction Theorem is
provably equivalent to Con(SRP) over WKL_0. The Finite Sequential
Clique Construction Theorem is provably equivalent to Con(SRP) over EFA.
THEOREM 3.2. If we modify STEP 1 by using only the k-tuples that are
a subsequence of the concatenated sequence x_1,...,x_p. The same
results apply using this alternative.
THEOREM 3.3. If we modify STEP 2 by omitting the ush terms, then the
Infinite Sequential Clique Construction Theorem is provable in RCA_0.
4. TEMPLATES.
The upper shift function on vectors is naturally viewed as the
coordinatewise extension of the one dimensional upper shift function
ush:Q into Q given by
ush(q) = q+1 if q >= 0; q otherwise.
We can replace ush throughout by any finite set of partial piecewise
linear functions from Q into Q. A variety of statements will result.
We conjecture that there is a sensible effectively decidable criterion
for determining the metamathematical status of the resulting statements.
We intend to develop such a criterion as these developments stabilize.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 450th 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 1graham
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 12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09 3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences 1/1/10 7:35PM
386: Terrifically and Extremely Long Finite Sequences 1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos 1/6/10 10:41PM
388: Goedel's Second Again/definitive? 1/7/10 11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3 2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4 2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5 2/22/10
3:50AM
394: Free Reduction Theory 1 3/2/10 7:30PM
395: Free Reduction Theory 2 3/7/10 5:41PM
396: Free Reduction Theory 3 3/7/10 11:30PM
397: Free Reduction Theory 4 3/8/10 9:05AM
398: New Free Reduction Theory 1 3/10/10 5:26AM
399: New Free Reduction Theory 2 3/12/10 9:36AM
400: New Free Reduction Theory 3 3/14/10 11:55AM
401: New Free Reduction Theory 4 3/15/10 4:12PM
402: New Free Reduction Theory 5 3/19/10 12:59PM
403: Set Equation Tower Theory 1 3/22/10 2:45PM
404: Set Equation Tower Theory 2 3/24/10 11:18PM
405: Some Countable Model Theory 1 3/24/10 11:20PM
406: Set Equation Tower Theory 3 3/25/10 6:24PM
407: Kernel Tower Theory 1 3/31/10 12:02PM
408: Kernel tower Theory 2 4/1/10 6:46PM
409: Kernel Tower Theory 3 4/5/10 4:04PM
410: Kernel Function Theory 1 4/8/10 7:39PM
411: Free Generation Theory 1 4/13/10 2:55PM
412: Local Basis Construction Theory 1 4/17/10 11:23PM
413: Local Basis Construction Theory 2 4/20/10 1:51PM
414: Integer Decomposition Theory 4/23/10 12:45PM
415: Integer Decomposition Theory 2 4/24/10 3:49PM
416: Integer Decomposition Theory 3 4/26/10 7:04PM
417: Integer Decomposition Theory 4 4/28/10 6:25PM
418: Integer Decomposition Theory 5 4/29/10 4:08PM
419: Integer Decomposition Theory 6 5/4/10 10:39PM
420: Reduction Function Theory 1 5/17/10 2:53AM
421: Reduction Function Theory 2 5/19/10 12:00PM
422: Well Behaved Reduction Functions 1 5/23/10 4:12PM
423: Well Behaved Reduction Functions 2 5/27/10 3:01PM
424: Well Behaved Reduction Functions 3 5/29/10 8:06PM
425: Well Behaved Reduction Functions 4 5/31/10 5:05PM
426: Well Behaved Reduction Functions 5 6/2/10 12:43PM
427: Finite Games and Incompleteness 1 6/10/10 4:08PM
428: Typo Correction in #427 6/11/10 12:11AM
429: Finite Games and Incompleteness 2 6/16/10 7:26PM
430: Finite Games and Incompleteness 3 6/18/10 6:14PM
431: Finite Incompleteness/Combinatorially Simplest 6/20/10 11:22PM
432: Finite Games and Incompleteness 4 6/26/10 8:39PM
433: Finite Games and Incompleteness 5 6/27/10 3:33PM
434: Digraph Kernel Structure Theory 1 7/4/10 3:17PM
435: Kernel Structure Theory 1 7/5/10 5:55PM
436: Kernel Structure Theory 2 7/9/10 5:21PM
437: Twin Prime Polynomial 7/15/10 2:01PM
438: Twin Prime Polynomial/error 9/17/10 1:22PM
439: Twin Prime Polynomial/corrected 9/19/10 2:16PM
440: Finite Phase Transitions 9/26/10 1:28PM
441: Equational Representations 9/27/10 4:59PM
442: Kernel Structure Theory Restated 10/11/10 9:01PM
443: Kernels and Large Cardinals 1 10/21/10 12:16AM
444: The Exploding Universe 1 11/1/10 1:46AMs
445: Kernels and Large Cardinals II 11/17/10 10:13PM
446: Kernels and Large Cardinals III 11/22/10 2:50PM
447: Kernels and Large Cardinals IV 11/23/10 3:51PM
448: Naturalness/PA Independence 12/3/10 12:19AM
449: Maximal Sets and Large Cardinals I 12/4/10 6:57PM
Harvey Friedman
More information about the FOM
mailing list