[FOM] 487:Invariant Maximality/Naturalness

Harvey Friedman friedman at math.ohio-state.edu
Tue Mar 20 22:22:39 EDT 2012


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

FEEDBACK FROM FOM SUBSCRIBERS IS REQUESTED
are the many uses of "natural" appropriate?

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

INVARIANT MAXIMALITY

We frame a completely natural investigation - the determination of  
what natural (in a precise natural sense) equivalence relations can be  
used in Invariant Maximality. We give a natural strong partial result,  
leaving the general natural investigation open.

The natural investigation certainly appears to be doable over a few  
years.

QUESTION: What kind of VICTORY can now be claimed? What kind of  
VICTORY can be later claimed when the complete determination is  
finished?

In the meantime, the question is: just what partial results to offer  
up, and how to present them.

GENERAL PRINCIPLE. Suppose we start with a completely natural general  
problem - calling for a determination of which (of finitely many)  
cases have a certain outcome. The expectation is that the completely  
natural general problem (with finitely many cases) will have a  
complete solution in a reasonable amount of time. We then give a  
partial result that is completely natural in the context of the given  
completely natural general problem. Then the partial result is  
consequently completely natural.

As usual, we start with

EVERY SET OF ORDERED PAIRS HAS A MAXIMAL SQUARE

which is equivalent to Zorn's Lemma in the general case. We are only  
concerned with

EVERY COUNTABLE SET OF ORDERED PAIRS HAS A MAXIMAL SQUARE

which is proved constructively by an obvious greedy construction.

We are going to place invariance conditions on the given countable set  
of ordered pairs and the resulting maximal square.

For this purpose, we work within ambient spaces rich enough to support  
interesting notions of invariance.

We use Q for the set of all rationals, Z+ for the set of all positive  
integers, and Q[0,n] for the set of all rationals in the interval [0,n].

***AMBIENT SPACE Q[0,16]^32***

In the first version of the results, we focus on just one ambient  
space, Q[0,16]^32. Thus we investigate

EVERY INVARIANT SUBSET OF Q[0,16]^32 HAS AN INVARIANT' MAXIMAL SQUARE

for various notions of invariance.

We say that x,y in Q[0,16]^32 are order equivalent if and only if for  
all 1 <= i,j <= 32, x_i < x_j iff y_i < y_j.

We say that S contained in Q[0,16]^32 is order invariant if and only  
if for all order equivalent x,y in Q[0,16]^32, x in S iff y in S.

NOTE: There are only finitely many order invariant S contained in  
Q[0,16]^32.

We consider statements of the form

EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS AN INVARIANT MAXIMAL  
SQUARE.

It is natural to focus on notions of invariance that arise from an  
equivalence relation on Q[0,16]^32. I.e.,

EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS AN E INVARIANT MAXIMAL  
SQUARE

where E is an equivalence relation on Q[0,16]^32.

We can view Q[0,16] as the system M(0,16;32) = (Q[0,16],<,{1,...,16}).  
I.e., a linearly ordered set together with a 1-place predicate. As  
such, we have the fundamental equivalence relation

x,y are M(0,16;32) equivalent if and only if

i. x,y in Q[0,16]^32.
ii. for all 1 <= i,j <= 32, x_i < x_j iff y_i < y_j.
iii. for all 1 <= i <= 32, x_i in {1,2,...,16} iff y_i in {1,2,...,16}.

The above construction is a special case of the fundamental  
equivalence relation that we naturally associate to any relational  
system consisting of a domain together with multivariate relations on  
the domain.

We say that S contained in Q[0,16]^32 is M(0,16;32) invariant if and  
only if for all M(0,16;32) equivalent x,y, x in S iff y in S.

So far, we have presented two natural equivalence relations on  
Q[0,16]^32, and their corresponding notions of invariance. These are  
order equivalence, and M(0,16;32) equivalence. So we can naturally  
consider

EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS AN ORDER INVARIANT  
MAXIMAL SQUARE.
EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS AN M(0,16;32) INVARIANT  
MAXIMAL SQUARE.

Both of these statements are demonstrably false.

EQUIVALENCE CLASS PROBLEM (prototype). Which equivalence relations can  
be used for the above statement?

There are uncountably many equivalence relations on Q[0,16]^32. It is  
natural to focus on those equivalence relations on Q[0,16]^32 which  
are themselves M(0,16;32) invariant as a subset of Q[0,16]^64.

EQUIVALENCE CLASS PROBLEM (ECP) ON Q[0,16]^32. For which M(0,16;32)  
invariant equivalence relations E on Q[0,16]^32 is it the case that  
every order invariant subset of Q[0,16]^32 has an E invariant maximal  
square?

Note that ECP on Q[0,16]^32 involves only finitely many equivalence  
relations E.

QUESTION: Is the ECP on Q[0,16]^32 obviously completely natural?

***PARTIAL RESULTS ON THE EQUIVALENCE CLASS PROBLEM ON Q[0,16]^32***

THEOREM 1. Among the finitely many instances of the ECP for  
Q[0,16]^32, one of them is provable in SRP but not in ZFC. Thus a  
complete solution to the ECP on Q[0,16]^32 cannot be given in ZFC.

CONJECTURE: A complete solution to the ECP on Q[0,16]^32 can be given  
in SRP.

SRP+ = ZFC + (for all k)(there is an ordinal with the k-SRP). 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.

Note that Theorem 1 and the Conjecture combined tell a natural story  
without mentioning any particular M(0,16;32) invariant equivalence  
relation on Q[0,16]^32.

CONJECTURE*. The above Conjecture will be proved within a few years.

If the equivalence relations extend order equivalence on  
{1,...,16}^32, then we have a complete solution:

THEOREM 2. A complete solution to the ECP on Q[0,16]^32 for  
equivalence relations extending order equivalence on {1,...,16}^32 can  
be given in SRP, but not in ZFC.

THEOREM 3. It is provable in SRP that there is a largest equivalence  
relation extending order equivalence on {1,...,16}^32 for which ECP on  
Q[0,16]^32 is true.

We do not know if Theorem 3 can be proved in ZFC.

THEOREM 4. The following is provable in SRP, but not in ZFC. The  
largest equivalence relation extending order equivalence on  
{1,...,16}^32 for which ECP on Q[0,16]^32 is true is the following  
equivalence relation on Q[0,16]^32. x E y if and only if x,y are order  
equivalent and for all 1 <= i <= 32, if x_i not= y_i then every x_j >=  
x_i is in {1,...,16} and every y_j  >= y_i is in {1,...,16}.

QUESTION: Is Theorem 4 a completely natural partial result on the  
completely natural ECP on Q[0,16]^32?

***DEFINITIVE RESULT ON THE RESTRICTED SHIFT PROBLEM ON Q[0,16]^32***

Let T:Q[0,16]^32 into Q^32. We say that S contained in Q[0,16]^32 is  
completely T invariant if and only if for all x,T(x) in Q[0,16]^32, x  
in S iff T(x) in S.

We now consider restricted shift functions from Q[0,16]^32 into Q^32.  
These are T:Q[0,16]^32 into Q^32 where T(x) is obtained by adding 1 to  
none, some, or all of the coordinates of x.

Another way of looking at a restricted shift function is as given by a  
mapping H:Q[0,16]^32 into {0,1}^32. The associated restricted shift  
function T is given by T(x) = x + H(x).

It is natural to use mappings H:Q[0,16]^32 into {0,1}^32 which are  
M(0,16;32) invariant in the sense that for all M(0,16;32) invariant  
x,y in Q[0,16]^32, H(x) = H(y).

We call these T the M(0,16;32) induced restricted shift functions.

RESTRICTED SHIFT PROBLEM (RSP) ON Q[0,16]^32. For which M(0,16;32)  
invariant equivalence relations E on Q[0,16]^32 is it the case that  
every order invariant subset of Q[0,16]^32 has a completely T  
invariant maximal square?

THEOREM 5. A complete solution to the RSP on Q[0,16]^32 can be given  
in SRP, but not in ZFC.

There is a natural special case of RSP on Q[0,16]^32.

EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS A Z+UP INVARIANT  
MAXIMAL SQUARE.

Here Z+up:Q[0,16]^32 into Q^32 is defined by Z+up(x) = the result of  
adding 1 to all coordinates greater than all coordinates not in Z+.

THEOREM 6. The above statement is provable in SRP but not in ZFC.

***AMBIENT SPACES Q[0,n]^k***

The same results apply except that we need n >= 16 and k >= 32 in  
order for our methods to show that independence from ZFC kick in.

The single most natural specific statement is:

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

All of the statements thus far are Pi01 in virtue of their logical  
form, using Goedel completeness of first order predicate calculus.

***AMBIENT SPACES Q^k***

The same results apply here as well, except that we don't know of any  
independence from ZFC.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 487th 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

Harvey Friedman


More information about the FOM mailing list