[FOM] 464: Order Invariant Upper Split Theorem
Harvey Friedman
friedman at math.ohio-state.edu
Mon May 30 00:53:25 EDT 2011
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
More information about the FOM
mailing list