[FOM] 493:Invariant Maximality/conjectures 2
Friedman, Harvey
friedman at math.ohio-state.edu
Sat Mar 31 01:10:29 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
**********************************
The four Templates from #493: Invariant Maximality/conjectures all
involved infinitely many instances:
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.
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.
CONJECTURE. All instances of Templates 1-4 are provable or refutable
in SRP. The instances of Templates 1-4 are linearly ordered by
provable implication over ACA'.
We know using the examples of Z+up and upper Z+ equivalence adapted to
Q[0,1] that each of Templates 1-4 have instances that are neither
provable nor refutable in ZFC. Also, we know in this way that no
finite fragment of SRP suffices in the above Conjecture. Some
instances that we know about have k as low as 16 and use as few as 16
parameters in the elementary presentations.
Perhaps my intuition is quite wrong about these Templates, and that
algorithmic undecidability kicks in. In that case, obviously both
Conjectures above are false.
So it is natural to weaken the Conjecture:
CONJECTURE (16,16). All instances of Templates 1-4 with k = 16, using
<= 16 parameters, are provable or refutable in SRP. The instances of
Templates 1-4 with k = 16, using <= 16 parameters, are linearly
ordered by provable implication over ACA'.
QUESTION. For which pairs k,n, is it the case that all instances of
Templates 1-4, with dimension k and <= n parameters, are provable or
refutable in ZFC? In SRP?
QUESTION. For which pairs k,n, is it the case that the instances of
Templates 1-4, with dimension k and at most n parameters, are linearly
ordered under provable implication over ACA'?
The structures (Q[0,1],<) and (Q,<) are quite impoverished. What
happens if we use richer structures? In general, the Templates will be
richer, and harder to analyze. However, we can always restrict the
dimension and the number of parameters allowed, to perhaps compensate
for the richer structure.
**********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 493rd 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
492: Invariant Maximality/conjectures
Harvey Friedman
More information about the FOM
mailing list