[FOM] 492:Invariant Maximality/conjectures

Fri Mar 30 11:02:38 EDT 2012

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

**********************************

We can present Invariant Maximality in the following way.

We begin with the two specific Invariant Maximality statements that we  
have presented, with specific invariance notions.

Then we provide general Templates, not mentioning any specific  
invariance notions.

The two specific Invariant Maximality statements can be properly  
viewed as partial results concerning the general Templates.

**********************************

We start with the following two Invariant Maximality statements:

EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k HAS A COMPLETELY Z+UP  
INVARIANT MAXIMAL SQUARE.

EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k HAS AN UPPER Z+ INVARIANT  
MAXIMAL SQUARE.

As in several previous postings,

i. Q[0,n] is Q intersect [0,n].
ii. Z+up:Q* into Q* is given by: Z+up(x) is the result of adding 1 to  
all coordinates greater than all coordinates not in Z+ (the set of all  
positive integers).
iii. upper Z+ equivalence is the equivalence relation on Q* given by:  
x,y are upper Z+ equivalent if and only if x,y are order equivalent,  
and for all 1 <= i <= lth(x), if x_i not= y_i then every x_j >= x_i is  
in Z+ and every y_j >= y_i is in Z+.

THEOREM A. As stated several times previously, the above two  
Propositions are provably equivalent to Con(SRP) over ACA'. For each  
n,k, they are provable in SRP. This last sentence does not hold for  
any finite fragment of SRP. The two instances and all of their  
instances, are Pi01 statements in virtue of their logical form, via  
the completeness theorem for predicate calculus.

For the programmatic formulations, we use the following Templates.  
(Q,<) elementary in (Q,<) is mathematically familiar: Boolean  
combinations of inequalities alpha < beta, where alpha,beta are  
variables or constants from Q. Functions are treated as graphs. This  
is exactly analogous to semialgebraic sets in the ordered field of  
real numbers (or, less commonly, in the ordered field of rational  
numbers).

TEMPLATE 1. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q,<) elementary. EVERY  
ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A T INVARIANT MAXIMAL SQUARE.

TEMPLATE 2. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q,<) elementary. EVERY  
ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A COMPLETELY T INVARIANT  
MAXIMAL SQUARE.

TEMPLATE 3. Let E be a (Q,<) definable equivalence relation (with  
parameters) on Q[0,1]^2k. EVERY ORDER INVARIANT SUBSET OF Q[0,1]^2k  
HAS AN E INVARIANT MAXIMAL SQUARE.

THEOREM B. ZFC is not sufficient to prove or refute all instances of  
any one of Templates 1,2,3. In fact, no finite fragment of SRP suffices.

CONJECTURE. SRP suffices to prove or refute every instance of  
Templates 1-3.

We believe that that an extended effort will resolve this Conjecture  
in the affirmative in <= 10 years.

We have been thinking about an easier form of Template 2, where we  
place a condition on T. Specifically, if x_i < x_j = T(x)_j, then x_i  
= T(x)_i. This seems to substantially simplify some serious technical  
issues. This should reduce the time from <= 10 years to <= 1 year, for  
Template 2. I.e., I am not quite ready to claim an analysis of this  
easier form of Template 2.

THeorem B is of course an immediate consequence of Theorem A for  
Templates 2,3. It also can be used to obtain Theorem B for Template 1,  
from Theorem A, with a little bit of fiddling. So Theorem A can be  
viewed as a *natural* partial result on the Conjecture - and also on  
the easier form of the Conjecture stated in the previous paragraph.

There are more ambitious Templates where "order invariant" is also  
templated. In this case, we can either use [0,1] or Q, and still carry  
over Theorem B. Most elegant is to use equivalence relations for the  
front and back:

TEMPLATE 4. Let E_1,E_2 be (Q,<) elementary equivalence relations on  
Q^2k. EVERY E_1 INVARIANT SUBSET OF Q^2k HAS AN E_2 INVARIANT MAXIMAL  
SQUARE.

THEOREM C. ZFC is not sufficient to prove or refute all instances of  
Template 4. In fact, no finite fragment of SRP suffices.

CONJECTURE. SRP suffices to prove or refute every instance of Template  
4.

QUESTION TO FOM READERS. Is this situation natural, fundamental, and  
inevitable in the non-sociological sense? Is this situation natural,  
fundamental, and inevitable in various sociological senses?

QUESTION TO FOM READERS. Is this situation more "convincing" than if  
some typical, specialized, open question in the core mathematical  
literature, which is arithmetic in virtue of its logical form, is  
shown to be independent of ZFC?

**********************************************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 492nd 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
489: Invariant Maximality Programs  3/24/12  2:31PM
490: Invariant Maximality Program 2  3/24/12  3:19PM
491: Formal Simplicity  3/25/12  11:50PM

Harvey Friedman