[FOM] 489:Invariant Maximality Programs
Harvey Friedman
friedman at math.ohio-state.edu
Sat Mar 24 01:35:59 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
FEEDBACK FROM FOM SUBSCRIBERS IS REQUESTED
as to the fundamental naturalness of the
Invariant Maximality Program
*****************************************
We are fine tuning the statement of the Invariant Maximality Program.
There seem to be a lot of interesting Templates, which we conjecture
that large cardinals can completely analyze, but where we know that
ZFC cannot.
These Templates have varying scope. It seems important to have a
variety of these Templates.
Such Templates with the smallest scope are important because
completely analyzing them using large cardinals is most plausible and
doable.
Such Templates with the biggest scope are important because they may
be the most compelling. Of course, the strongest ones are the most
difficult to analyze, and where I am most likely to be wrong - they
may be "unanalyzable". The most obvious kind of "unanalyzability" is
undecidability. However, even for the strongest Templates, there are
natural finite fragments that would be analyzable.
INVARIANT MAXIMALITY PROGRAMS
by
Harvey M. Friedman
March 23, 2012
The present development of Invariant Maximality Program lives entirely
in the rationals, Q, with its usual linear order. (Q,<) may seem like
an impoverished structure, but it is enough to drive the discussion
beyond ZFC and into large cardinals.
We actually use Q[a,b], which is the set of rationals in [a,b]. The
right endpoint is important for the theory.
We also use Z+ for the set of all positive integers.
For the programmatic statements, it is most natural to normalize the
space as Q]0,1].
The elementary subsets of Q[0,1]^k are very familiar. These are the
subsets of Q[0,1]^k defined by a Boolean combination of inequalities
alpha < beta, where alpha,beta are each either a variable v_1,...,v_k,
or a constant from Q[0,1].
The purely elementary subsets of Q[0,1]^k are defined by a Boolean
combination of inequalities alpha < beta, where alpha,beta are among
the variables v_1,...,v_k. I.e., no parameters are allowed.
Note that the purely elementary subsets of Q[0,1]^k are the same as
the order invariant X contained in Q[0,1]^k. They are finite in number.
Also note that the number of elementary subsets of Q[0,1]^k
presentable with a given finite set of parameters from Q[0,1] is finite.
***TRANSFORMATIONAL INVARIANCE***
It is also customary to treat transformations T:Q[0,1]^k into Q[0,1]^k
as subsets of Q[0,1]^2k.
We say that S contained in Q[0,1]^k is T invariant if and only if T[S]
is a subset of S.
We start with
EVERY SUBSET OF Q^2k HAS A MAXIMAL SQUARE
which is proved by an obvious greedy construction. The proof is
entirely constructive.
TEMPLATE A. Let T:Q[0,1]^2k into Q[0,1]^2k be elementary. DOES EVERY
PURELY ELEMENTARY SUBSET OF Q[0,1]^2k HAVE A T INVARIANT MAXIMAL SQUARE?
OBSERVATION: Note that for a given k and a given number of parameters
used to present T, there are only finitely many instances of Template
A under provable equivalence in RCA_0.
THEOREM 1. There is an instance of Template A which is independent of
ZFC. There is such an instance with k = 16 and involving 16 positive
parameters, including 1. Thus a complete analysis of Template A cannot
be given in ZFC, even with k = 16 and 16 parameters. SRP is sufficient
to prove this instance.
CONJECTURE. SRP is sufficient to give a complete analysis of Template
A with k = 16 and using at most 16 parameters. By the above
Observation, this constitutes only finitely many statements.
CONJECTURE. SRP is sufficient to give a complete analysis of Template A.
Here SRP = ZFC + {there is an ordinal with the k-SRP)_k. The k-SRP
asserts that every partition of the unordered k-tuples from lambda
into two pieces has a homogenous set stationary in lambda.
We can now view our previous work concerning
EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 CONTAINS A COMPLETELY Z+UP
INVARIANT MAXIMAL SQUARE
EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 CONTAINS A COMPLETELY Z+UP
INVARIANT MAXIMAL SQUARE
using Z+up:Q[0,16)^2k into Q[0,16]^2k. I.e., T(x) is the result of
adding 1 to all coordinates greater than all coordinates not in Z+.
Complete T invariance means x in S iff T(x) in S. This is stronger
than T invariance, which is x in S implies T(x) in S.
In order to use Invariance instead of Complete Invariance, we have to
do some routine fiddling around with Z+up. So this previous work can
be viewed as fitting squarely into the Invariant Maximality Program as
given by Template A. I.e., it is completely natural partial
information concerning Template A.
Alternatively, we could modify Template A by
TEMPLATE B. Let T:Q[0,1]^2k into Q[0,1]^2k be elementary. DOES EVERY
PURELY ELEMENTARY SUBSET OF Q[0,1]^2k HAVE A COMPLETELY T INVARIANT
MAXIMAL SQUARE?
Of course, Template B is a little more technical than Template A. But
my instance of Template B is more natural by far than the doctored
instance for Template A.
We now expand the Templates further.
TEMPLATE C. Let T:Q[0,1]^2k into Q[0,1]^2k be elementary. DOES EVERY
ELEMENTARY SUBSET OF Q[0,1]^2k HAVE A T INVARIANT MAXIMAL SQUARE?
TEMPLATE D. Let T:Q[0,1]^2k into Q[0,1]^2k be elementary. DOES EVERY
ELEMENTARY SUBSET OF Q[0,1]^2k HAVE A COMPLETELY T INVARIANT MAXIMAL
SQUARE?
QUESTION. Can Templates C,D be analyzed within ZFC? Within ACA'?
The difficulty is that the parameters for the given set may overlap
with the parameters for T, thereby taking the statement refutable in
RCA_0.
However, this problem does not arise with the "fine grained" form of
these Templates which we now present.
TEMPLATE E. Let X contained in Q[0,1]^2k and T:Q[0,1]^2k into
Q[0,1]^2k be elementary. DOES X HAVE A T INVARIANT MAXIMAL SQUARE?
TEMPLATE F. Let X contained in Q[0,1]^2k and T:Q[0,1]^2k into
Q[0,1]^2k be elementary. DOES X HAVE A COMPLETELY T INVARIANT MAXIMAL
SQUARE?
THEOREM 2. There is an instance of Template E which is independent of
ZFC. There is such an instance with k = 16 and involving 16 positive
parameters, including 1. Thus a complete analysis of Template E cannot
be given in ZFC, even with k = 16 and 16 parameters. SRP is sufficient
to prove this instance. These results hold also for Template F.
CONJECTURE. SRP is sufficient to give a complete analysis of Templates
E,F with k = 16 and using at most 16 parameters. By the above
Observation, this constitutes only finitely many statements.
CONJECTURE. SRP is sufficient to give a complete analysis of Templates
E,F.
NOTE: Every instance of Templates E,F is equivalent to the
satisfiability of a sentence in predicate calculus, over RCA_0. Thus
every instance of Templates A-F is Pi01 in virtue of its logical form.
***EQUIVALENCE CLASS INVARIANCE***
Let E be an equivalence relation on Q[0,1]^k. We say that S contained
in Q[0,1]^k is E invariant if and only if for all E equivalent x,y in
Q[0,1]^k, x in S iff y in S.
Of special importance are the elementary equivalence relations on
Q[0,1]^k.
PROBLEM. CLassify all elementary equivalence relations on Q[0,1]^k.
We first have the analogs of Templates A,C,E, as follows.
TEMPLATE G. Let E be an elementary equivalence relation. DOES EVERY
PURELY ELEMENTARY SUBSET OF Q[0,1]^2k HAVE AN E INVARIANT MAXIMAL
SQUARE?
TEMPLATE H. Let E be an elementary equivalence relation. DOES EVERY
ELEMENTARY SUBSET OF Q[0,1]^2k HAVE AN E INVARIANT MAXIMAL SQUARE?
TEMPLATE I. Let X contained in Q[0,1]^2k and the equivalence relation
E on Q[0,1]^2k both be elementary. DOES X HAVE AN E INVARIANT MAXIMAL
SQUARE?
THEOREM 4. There is an instance of Template G which is independent of
ZFC. There is such an instance with k = 16 and involving 16 positive
parameters, including 1. Thus a complete analysis of Template G cannot
be given in ZFC, even with k = 16 and 16 parameters. SRP is sufficient
to prove this instance. These results hold also for Template I.
QUESTION. Can Template H be analyzed within ZFC? Within ACA'?
NOTE: Every instance of Template I is equivalent to the satisfiability
of a sentence in predicate calculus, over RCA_0. Thus every instance
of Templates G,H,I is Pi01 in virtue of its logical form.
We now enlarge the scope of the Templates by using two equivalence
relations.
TEMPLATE J. Let E_1,E_2 be elementary equivalence relations on
Q[0,1]^2k. DOES EVERY E_1 INVARIANT SUBSET OF Q[0,1]^2k HAVE AN E_2
INVARIANT MAXIMAL SQUARE?
THEOREM 5. There is an instance of Template J which is independent of
ZFC. There is such an instance with k = 16 and involving 16 positive
parameters, including 1. Thus a complete analysis of Template J cannot
be given in ZFC, even with k = 16 and 16 parameters. SRP is sufficient
to prove this instance.
NOTE: Every instance of Template I is equivalent to the satisfiability
of a sentence in predicate calculus, over RCA_0. Thus every instance
of Templates G-I is Pi01 in virtue of its logical form. THis applies
also to Template J provided that E_1 has finitely many equivalence
classes - a condition that can be effectively recognized.
***OTHER STRUCTURES***
We can of course use (Q,<) instead of (Q[0,1],<). Then we don't have
an instance of Templates A,B,C,D,G,H that is independent of ZFC.
However, we do have such an instance in the case of Templates E,F,I,J.
Since (Q,<) is so natural, we will explicitly present these Templates.
TEMPLATE K. Let X contained in Q^2k and T:Q^2k into Q^2k be
elementary. DOES X HAVE A T INVARIANT MAXIMAL SQUARE?
TEMPLATE L. Let X contained in Q^2k and T:Q^2k into Q^2k be
elementary. DOES X HAVE A COMPLETELY T INVARIANT MAXIMAL SQUARE?
TEMPLATE M. Let X contained in Q^2k and the equivalence relation E on
Q^2k be elementary. DOES X HAVE AN E INVARIANT MAXIMAL SQUARE?
TEMPLATE N. Let E_1,E_2 be elementary equivalence relations on Q^2k.
DOES EVERY E_1 INVARIANT SUBSET OF Q^2k HAVE AN E_2 INVARIANT MAXIMAL
SQUARE?
Obviously, we can use any relational structure M whatsoever for these
Templates. Here elementary means quantifier free definable, and purely
elementary means quantifier free definable without parameters.
You can choose your favorite structure M, and investigate all of these
Templates. If you are a logician, you might also want to use
"definable" instead of "quantifier free".
There are a large number of very tame M to investigate, not only with
domain Q, but also with domains N,Z,R,C, etcetera. We have only looked
at M = (Q,<) and (Q intersect J,<), for intervals J in the reals.
***SOME EXPECTATIONS***
I expect a complete analysis of all these Templates for (Q,<),
(Q[0,1],<), with k = 2 within Z_3. The case k = 1 should be within
RCA_0.
There will be a complete analysis of Templates A-N in SRP sometime
this century.
There will be a complete analysis of Templates A-N, for an assortment
of basic structures M, using large cardinals, sometime this century.
**********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 489th 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-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120324/879b9a61/attachment-0001.html>
More information about the FOM
mailing list