[FOM] 464: Order Invariant Upper Split Theorem

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THE USUAL QUALIFICATIONS APPLY THAT THE PAPER HAS TO BE WRITTEN AND  
CHECKED CAREFULLY

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

THIS POSTING IS ENTIRELY SELF CONTAINED (AFTER THE INTRODUCTORY REMARKS)

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

INTRODUCTORY REMARKS. The last comprehensive statement of the Pi01  
independent statements is http://www.cs.nyu.edu/pipermail/fom/2011-May/015464.html

This posting represents a sea change breakthrough in the Finite Form,  
and includes explicitly Pi01 forms.

There are layers of new ideas, which pass through all of the new ideas  
needed to handle the Maximal Clique Split Theorem from http://www.cs.nyu.edu/pipermail/fom/2011-May/015464.html 
:

MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on rational  
[-1,1]^k has a "rich" maximal clique.

MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on rational  
[-1,1]^k has a maximal clique containing its strict upper split.

These is still my best infinite theorem that is independent of ZFC. In  
fact, it is provably equivalent to Con(SMAH).

However, it appears that as a Corollary of the new stuff in the  
present posting, we will be able to obtain the same results for:

MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on Q^k has a  
"rich" maximal clique.

MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on Q^k has a  
maximal clique containing its strict upper split.

But the main event is that we remove CLIQUES entirely from the  
statement, and use only individual VERTICES. This is a profound sea  
change. Now the statements are not tied to specifically combinatorial  
considerations, and instead are poised to penetrate algebra, geometry,  
analysis, and virtually any mathematical context.

Now this does not mean that it is going to be that easy to obtain such  
a penetration. But it is completely inevitable. It is completely  
untenable to contemplate any kind of major barrier to doing so.

Now given the MULTIPLE LAYERING of new ideas needed to establish the  
claims in this postings, the probability that everything will work as  
claimed is SOMEWHAT LESS THAN NORMAL for my numbered postings.

However, given that I have a number of backup results with less drama,  
in this general direction, and given the profound sea change this  
represents, I thought it appropriate, on balance, to make this posting  
now.

I am committed to having a complete manuscript that will convince me  
by October 1, 2011, and if all goes well, a manuscript suitable for  
publication by the end of 2011.

ORDER INVARIANT SPLIT THEOREM
by
Harvey M. Friedman
May 30, 2011

1. Graphs, Order Invariance, Splits.
2. Order Invariant Split Theorem.

1. GRAPHS, ORDER INVARIANCE, SPLITS.

A graph is a pair G = (V,E), where V is a nonempty set of vertices,  
and E is an irreflexive symmetric relation.

We say that x,y are adjacent if and only if x E y.

We use Q,R for the set of all rationals, and the set of all reals,  
respectively.

We say that x in R^k is without 0 if and only if 0 is not a coordinate  
of x.

We say that x,y in R^k are order equivalent if and only if for all 1  
<= i,j <= k, x_i < x_j iff y_i < y_j.

We say that S containedin Q^k (R^k) is order invariant if and only if  
for all x,y in Q^k (R^k), if x,y are order equivalent then x in S iff  
y in S.

We say that G is an order invariant graph on Q^k (R^k) if and only if  
E containedin Q^2k (R^2k) is order invariant.

Note that there are at most 2^(k^k) order invariant S containedin Q^k  
(R^k), and so there are at most 2^((2k)^(2k)) order invariant graphs  
on Q^k (R^k).

The split of x in R^k is obtained by dividing every coordinate of x by  
2.

The upper split of x in R^k is obtained by dividing every positive  
coordinate of x by 2.

2. ORDER INVARIANT SPLIT THEOREM.

RATIONAL ORDER INVARIANT UPEPR SPLIT THEOREM. In every order invariant  
graph on Q^k, every vertex without 0 is not adjacent to its upper  
split, or adjacent to some vertex not adjacent to its upper split.

REAL ORDER INVARIANT UPPER SPLIT THEOREM. In every order invariant  
graph on R^k, every vertex without 0 is not adjacent to its upper  
split, or adjacent to some vertex not adjacent to its upper split.

Note that using the well known decision procedures for the ordered  
groups of rationals and reals (the same decision procedure), all four  
of these statements are Pi01.

THEOREM 2.1. The two above are provable in SMAH+ but not in any  
consistent fragment of SMAH that proves RCA_0. The two above are  
provably equivalent to Con(SMAH) over RCA_0.

Here SMAH+ is ZFC + "for all k there exists a strongly k-Mahlo  
cardinal". SMAH = ZFC + {there exists a strongly k-Mahlo cardinal}_k.

The norm of x in Q^k is the smallest positive integer n such that  
every coordinate of x can be written as a ratio of integers of  
magnitude at most n. Consider the following:

ESTIMATED ORDER INVARIANT UPPER SPLIT THEOREM. In every order  
invariant graph on Q^k, every vertex without 0, of norm at most k, is  
not adjacent to its upper split, or adjacent to some vertex of norm at  
most 8k, not adjacent to its upper split.

Note that the Estimated Order Invariant Upper Split Theorem is  
explicitly Pi01.

THEOREM 2.2. The Estimated Order Invariant Upper Split Theorem is  
provable in SMAH+ but not in any consistent fragment of SMAH that  
proves RCA_0. The Estimated Order Invariant Upper Split Theorem is  
provably equivalent to Con(SMAH) over RCA_0.

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

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

Harvey Friedman