[FOM] 488:Invariant Maximality Program
Harvey Friedman
friedman at math.ohio-state.edu
Thu Mar 22 21:05:10 EDT 2012
On Mar 20, 2012, at 10:22 PM, Harvey Friedman wrote:
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
*****************************************
Here we present the Invariant Maximality Program of obvious
fundamental importance. This is a programmatic breakthrough.
We show how it inexorably leads to large cardinals.
But first we put http://www.cs.nyu.edu/pipermail/fom/2012-March/016337.html
into this numbered posting:
In http://www.cs.nyu.edu/pipermail/fom/2012-March/016336.html I wrote:
> 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?
I meant
RESTRICTED SHIFT PROBLEM (RSP) ON Q[0,16]^32. For which M(0,16;32)
induced restricted shift functions T, is it the case that every order
invariant subset of Q[0,16]^32 has a completely T invariant maximal
square? END
We also now make a remark about FUNDAMENTAL NATURALNESS.
There is a reasonably clear notion of fundamentally natural
mathematics that is independent of, and transcends, the current state
of mathematics.
This is evident as we reflect on how trivial the sum total of
mathematics that has been done must be when comparing it with the
mathematics of the future.
To add context to these statements, I make a further observation.
There is very little in the way of a coherent programmatic statement
as to what mathematics is about or is trying to accomplish, of general
intellectual interest. In the absence of such coherent programmatic
statements of general intellectual interest, it would be absurd to tie
fundamental naturalness to existing mathematics.
INVARIANT MAXIMALITY PROGRAM
by
Harvey M. Friedman
March 22, 2012
The present development of the Invariant Maximality Program lives
entirely in the rationals, Q, with its usual linear order.
The elementary subsets of Q^k are very familiar. These are the subsets
of the Q^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.
Of particular importance are the elementary equivalence relations on
the Q^k.
PROBLEM. Classify the elementary equivalence relations on the Q^k.
Let E be an equivalence relation on Q^k. We say that S contained in
Q^k is E invariant if and only if for all E equivalent x,y in Q^k, x
in S iff y in S. This is equivalent to saying that S is a union of
equivalence classes of E.
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 E_1 and 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?
First some observations about this Template.
If we fix the dimension k, and also the set of parameters used for the
two elementary objects involved, then there are only finitely many
instances of the Template.
THEOREM 1. There is an instance of Template A which is independent of
ZFC. Thus a complete analysis of Template A cannot be given in ZFC. In
fact, ZFC cannot handle an instance with k = 16, where E_1 uses
parameter 16, and E_2 uses parameters 1,...,16. There are only
finitely many such instances.
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.
***ALTERNATIVE TEMPLATE***
THEOREM 2. Let E be an elementary equivalence relation on Q^k. The
following are equivalent.
i. E has finitely many equivalence classes.
ii. There are finitely many E invariant subsets of Q^k
iii. Every E invariant subset of Q^k is elementary.
Furthermore, there is a decision procedure for determining whether a
given presentation of an elementary equivalence relation on Q^k has
finitely many equivalence classes.
In light of Theorem 2, it is natural to consider the generally "finer"
Template:
TEMPLATE B. Let K be an elementary subset of Q^2k and E be an
elementary equivalence relation on Q^2k. DOES K HAVE AN E INVARIANT
MAXIMAL SQUARE?
THEOREM 3. There is an instance of Template B which is independent of
ZFC. Thus a complete analysis of Template B cannot be given in ZFC. In
fact, ZFC cannot handle an instance with k = 16, where K has parameter
16, and E has parameters 1,...,16. There are only finitely many such
instances.
CONJECTURE. SRP is sufficient to give a complete analysis of Template B.
NOTE: Every instance of Template B is equivalent to the satisfiability
of a sentence in predicate calculus, over RCA_0. Thus every instance
of Template B is Pi01 in virtue of its logical form.
***OTHER STRUCTURES***
Obviously, we can replace the structure M = (Q,<) by any relational
structure M. Then elementary means quantifier free definable, and
purely elementary means quantifier free definable without parameters.
We naturally have the following three generalized templates.
TEMPLATE C. Let M be a relational structure. Let E_1 and E_2 be M
elementary equivalence relations on D^2k. DOES EVERY E_1 INVARIANT
SUBSET OF D^2k HAVE AN E_2 INVARIANT MAXIMAL SQUARE?
TEMPLATE D. Let M be a relational structure. Let K be an elementary
subset of D^2k and E be an elementary equivalence relation on D^2k.
DOES K HAVE AN E INVARIANT MAXIMAL SQUARE?
You can choose your favorite structure M, and investigate Template B.
If you are a logician, you might also want to use "definable" instead
of "quantifier free".
I have only looked at Template B with special K.
You can choose your favorite structure M, and investigate Templates
C,D. 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,<).
***SOME EXPECTATIONS***
I expect a complete analysis of Template A for k = 2 within Z_3. The
case k = 1 should be within RCA_0.
There is hope of giving a complete analysis of Template B where the
second equivalence relation extends order equivalence on all
parameters used for K and E.
There will be a complete analysis of Templates A,B in SRP sometime
this century.
There will be a complete analysis of Templates C,D using standard
large cardinals, for an assortment of basic structures M, sometime
this century.
**********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 488th 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
Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120322/b98afef0/attachment.html>
More information about the FOM
mailing list