# [FOM] 492:Invariant Maximality/conjectures

Friedman, Harvey friedman at math.ohio-state.edu
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.

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

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?

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

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
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

```