[FOM] 470: Invariant Maximal Square Theorem

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

I have decided to use MAXIMAL SQUARES instead of MAXIMAL CLIQUES.  
Thank you for your feedback concerning #469 http://www.cs.nyu.edu/pipermail/fom/2011-November/015959.html

At this point, the major issue is to make the second invariance  
condition, UPPER INVARIANCE, as simple as possible.

The previous presentation is already reasonable, but here we do better.

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

Q is the set of rationals. Q^k is the set of all k-tuples from Q.  
Q[0,p], p in Q, is Q intersect [0,p].

x,y in Q^k are Order Equivalent if and only if for all 1 <= i,j <= k,  
x_i < x_j iff y_i < y_j.

x,y in Q^k are Upper Related if and only if y results from adding 1 to  
all x_i such that every x_j >= x_i is a positive integer.

E contained in Q[0,p]^k is Order Invariant (Upper Invariant) if and  
only if for all Order Equivalent (Upper Related) x,y in Q[0,p]^k, x in  
E iff y in E.

A maximal square in E is an S^2 contained in E that is not properly  
included in any S^2 contained in E.

ORDER INVARIANT MAXIMAL SQUARE THEOREM (VERY FALSE!) For all k >= 1  
and p in Q, every Order Invariant subset of Q[0,p]^2k has an Order  
Invariant maximal square.

UPPER INVARIANT MAXIMAL SQUARE THEOREM. UIMST. For all k >= 1 and p in  
Q, every Order Invariant subset of Q[0,p]^2k has an Upper Invariant  
maximal square.

THEOREM. UIMST is provable from certain large cardinals, but not in  
ZFC. UIMST is provably equivalent to Con(SRP) over ACA'.

Here SRP is ZFC + {there exists an ordinal with the k-SRP}_k.

As an exercise in undergraduate mathematical logic, one sees via  
Goedel's Completeness Theorem that UIMST is provably equivalent to a  
Pi01 statement over WKL_0.

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

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

Harvey Friedman