[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