[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