[FOM] 494:Inv Max Templates/Z+up, upper Z+ equiv
Friedman, Harvey
friedman at math.ohio-state.edu
Thu Apr 5 12:50:07 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
**********************************
THIS POSTING IS SELF CONTAINED
for 1, mostly, and for 2,3,4,5
*********************************
FOM OPINIONS REQUESTED
on naturalness of items 1-4
and issues raised in 5
********************************
1. Restatement of the Invariant Maximality Templates in http://www.cs.nyu.edu/pipermail/fom/2012-March/016383.html
and http://www.cs.nyu.edu/pipermail/fom/2012-March/016386.html
2. New way to talk about Z+up.
3. New way to talk about upper Z+ equivalence.
4. Using Maximal Cliques in Graphs.
1. RESTATEMENT OF TEMPLATES.
In http://www.cs.nyu.edu/pipermail/fom/2012-March/016383.html and http://www.cs.nyu.edu/pipermail/fom/2012-March/016386.html
I forgot to change the statement of Template 3 in accordance with
the other Templates. There is nothing wrong with what I wrote, but it
is not the way I meant to write it.
So here are the four Invariant Maximality Templates (IMT) involving
infinitely many instances:
IMT 1. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q[0,1],<) elementary. EVERY
ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A T INVARIANT MAXIMAL SQUARE.
IMT 2. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q[0,1],<) elementary. EVERY
ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A COMPLETELY T INVARIANT
MAXIMAL SQUARE.
IMT 3. Let E be a (Q[0,1],<) elementary equivalence relation on
Q[0,1]^2k. EVERY ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS AN E
INVARIANT MAXIMAL SQUARE.
IMT 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.
These Templates all have infinitely many instances. We can introduce
the number of parameters in the elementary presentations (IMTP), and
these will have finitely many instances:
IMTP 1. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q[0,1],<) elementary with
<= r parameters. EVERY ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A T
INVARIANT MAXIMAL SQUARE.
IMTP 2. Let T:Q[0,1]^2k into Q[0,1]^2k be (Q[0,1],<) elementary with
<= r parameters. EVERY ORDER INVARIANT SUBSET OF Q[0,1]^2k HAS A
COMPLETELY T INVARIANT MAXIMAL SQUARE.
IMTP 3. Let E be a (Q[0,1],<) elementary equivalence relation on
Q[0,1]^2k with <= r parameters. EVERY ORDER INVARIANT SUBSET OF
Q[0,1]^2k HAS AN E INVARIANT MAXIMAL SQUARE.
IMTP 4. Let E_1,E_2 be (Q,<) elementary equivalence relations on Q^2k
with <= r parameters each. EVERY E_1 INVARIANT SUBSET OF Q^2k HAS AN
E_2 INVARIANT MAXIMAL SQUARE.
Here Q[0,1] = Q intersect [0,1]. Also (Q[0,1],<) elementary means
"definable by a Boolean combination of inequalities alpha < beta,
where alpha, beta are variables or constants from Q[0,1]". Analogously
for (Q,<).
CONJECTURE. All instances of IMT 1-4 are provable or refutable in SRP.
The instances of IMT 1-4 are quasi 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.
We know that some instances of IMTP 1-4 with k = r = 16 are neither
provable nor refutable in ZFC.
QUESTION. For which triples k,n,r is it the case that all instances of
IMTP 1-4 are provable or refutable in ZFC? In SRP?
QUESTION. For which triples k,n,r is it the case that the instances of
IMTP 1-4 are quasi 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 even harder to analyze. However, we can always restrict
the dimension and the number of parameters allowed, to perhaps
compensate for the richer structure.
2. NEW WAY TO TALK ABOUT Z+up.
Recall Z+up:Q* into Q*, where Z+up(x) is the result of adding 1 to all
coordinates that are greater than all coordinates not in Z+. Here Z+
is the set of all positive integers, and Q* is the set of all finite
sequences of rationals.
We propose to redefine Z+up as follows. Let Q*<= be the set of
increasing (<=) finite sequences from Q.
Z+up:Q*<= into Q*<= is given by: Z+up(x) is the result of adding 1 to
the longest tail of positive integer coordinates of x.
This is readily visualized and very natural.
*Every order invariant subset of Q[0,n]^2k has completely Z+up
invariant square.*
under the new definition of Z+up.
All the results remain the same. I.e., it is equivalent to Con(SRP)
over ACA'.
3. NEW WAY TO TALK ABOUT UPPER Z+ EQUIVALENCE.
Recall that x,y in Q* are upper Z+ equivalent if and only if x,y are
order equivalent, and for all 1 <= i <= lth(x), every x_j >= x_i is in
Z+ and every y_j >= y_i is in Z+.
We propose to redefine upper Z+ equivalence as follows. x,y are upper Z
+ equivalent if and only if x,y are strictly increasing sequences of
rationals of the same length, where every coordinate not in their
longest common initial subsequence is a positive integer.
Note that this new upper Z+ equivalence is still an equivalence
relation. It's field is Q*<.
This is also readily visualized and very natural.
*Every order invariant subset of Q[0,n]^2k has an upper Z+ invariant
maximal square.*
under the new definition of upper Z+ equivalence.
All the results remain the same. I.e., it is equivalent to Con(SRP)
over ACA'.
4. USING MAXIMAL CLIQUES IN GRAPHS
Recall that I asked the FOM and others about comparing
a. Maximal CLiques in Graphs
b. Maximal Squares in Binary Relations
There was a split, with most liking b) better. As you know, I went
with b). Here the Invariance is applied to the Maximal Square.
Let's revisit this issue.
Here are the graph theoretic formulations:
*Every order invariant graph on Q[0,n]^k has a completely Z+up
invariant maximal clique.*
*Every order invariant graph on Q[0,n]^k has an upper Z+ invariant
maximal clique.*
under the new definitions of Z+up and upper Z+ equivalence.
The notion of graph used here is simply an irreflexive symmetric
relation on a set. After this definition, one can refer to "vertices
and edges".
5. TENTATIVE OPINION.
My tentative opinion is that the new definitions of Z+up and upper Z+
equivalence are quite valuable, in that they are significantly easier
to fully digest and visualize. That the reversals are going to be
harder, particularly in the case of the new upper Z+ equivalence. The
number 16 = k = n may have to be raised in the claims about ZFC, but
not too much.
As for Maximal Cliques in Squares versus Maximal Squares in Binary
Relations.
I still am not so sure which is better.
In a gesture towards those who do not want to bring in graph theoretic
terminology, one can avoid talking about "vertices" and "edges", and
simply say that a graph is a pair (V,E), where V is a set and E is an
irreflexive symmetric relation on V. Then relate this to "vertices"
and "edges".
So here is my present plan. Write
EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k (GRAPH ON Q[0,n]^k) HAS A
COMPLETELY Z+up INVARIANT MAXIMAL SQUARE (MAXIMAL CLIQUE).
EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k (GRAPH ON Q[0,n]^k) HAS AN
UPPER Z+ INVARIANT MAXIMAL SQUARE (MAXIMAL CLIQUE).
using the new definitions. Then strengthen the new definitions to the
old definitions, using an asterisk. Thus, state
EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k (GRAPH ON Q[0,n]^k) HAS A
COMPLETELY Z+up INVARIANT* MAXIMAL SQUARE (MAXIMAL CLIQUE).
EVERY ORDER INVARIANT SUBSET OF Q[0,n]^2k (GRAPH ON Q[0,n]^k) HAS AN
UPPER Z+ INVARIANT* MAXIMAL SQUARE (MAXIMAL CLIQUE).
iii. Prove that all four are provably equivalent to Con(SRP) over ACA'.
iv. Technically, the most convenient is the Maximal Cliques in Graphs
with the old definitions of Z+up and upper Z+ equivalence.
What do YOU think?
**********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 494th 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 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
Harvey Friedman
More information about the FOM
mailing list