[FOM] 465: Patterns in Order Invariant Graphs

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

INTRODUCTORY REMARKS. The last comprehensive statement of the Pi01  
independent statements is http://www.cs.nyu.edu/pipermail/fom/2011-May/015464.html 
  This features MAXIMAL CLIQUES, and the MAXIMAL CLIQUE SPLIT THEOREM  
is implicitly Pi01. That posting is STILL OPERATIVE - but with caution  
to the reader in the preliminary remarks there.

In http://www.cs.nyu.edu/pipermail/fom/2011-May/015522.html, we  
introduced a sea change in the independent statements. They are  
explicitly Pi02, implicitly Pi01 (on the basis of well known decision  
procedures), and with the addition of obvious crude estimates, are  
explicitly Pi01. Because of this level of breakthrough claim, I made  
the more than usual qualification that we need a manuscript with  
complete proofs. I went out on a limb.

In this posting, we continue with breakthrough claims and conjectures  
- and this time, I am going EVEN FURTHER OUT ON A LIMB in terms of the  
layers of ideas that need to be extremely carefully checked to justify  
these claims. I.e., yet more very substantial layers.

The breakthrough idea here is that we focus only on existential  
properties of order invariant graphs. This not only supports a  
simplification (no more "nonzero"), but also suggests a marvelously  
compelling set of extremely concrete problems that should all be  
solvable with and only with small large cardinals. These problems are  
explicitly Pi02, implicitly Pi01 (on the basis of well known decision  
procedures), and now with the addition of only one obvious crude  
estimate on the single existential quantifier, are explicitly Pi01.

This reduction to essentially the simplest possible context, with just  
order and doubling on the rational numbers, would then be preliminary  
to wholesale embedding into the very fabric of mathematical culture.

If this house comes tumbling down, it will at least demonstrate by  
example, the QUALITY of developments that we are seeking - and now  
expecting.

PATTERNS IN ORDER INVARIANT GRAPHS
by
Harvey M. Friedman
June 4, 2011

1. Graphs, Order Invariance, Splits.
2. Patterns in Order Invariant Graphs.
3. Templates.

1. GRAPHS, ORDER INVARIANCE, DOUBLES.

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 for the set of all rational numbers.

We say that 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.

We say that S containedin Q^k is order invariant if and only if for  
all x,y in Q^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 if and only if E  
containedin Q^2k is order invariant.

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

The double of x in Q^k is obtained by doubling every coordinate.

The upper double of x in Q^k is obtained by doubling every positive  
coordinate.

2. PATTERNS IN ORDER INVARIANT GRAPHS.

ORDER INVARIANT PATTERN THEOREM. In every order invariant graph on  
Q^k, some vertex not adjacent to (1,...,k) is equal or adjacent to its  
upper double.

Note that using the well known decision procedures for the ordered  
groups of rationals, this statement is Pi01.

THEOREM 2.1. The Order Invariant Pattern Theorem is provable in SMAH+  
but not in any consistent fragment of SMAH that proves EFA. The Order  
Invariant Pattern Theorem is provably equivalent to Con(SMAH) over EFA.

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 PATTERN THEOREM. In every order invariant  
graph on Q^k, some vertex of norm at most 8k, not adjacent to  
(1,...,k), is equal or adjacent to its upper double.

Note that the Estimated Order Invariant Pattern Theorem is explicitly  
Pi01.

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

3. TEMPLATES.

We use the letter E for subsets of Q^2k. We write ud(x) for the upper  
double of x (from section 1).

We use variables x_1,x_2,... for elements of Q^k. The R,ud terms are  
inductively defined by

i. Each element of Q^k is an R,ud term.
ii. Each variable is an R,ud term.
iii. If t is an R,ud term then ud(t) is an R,ud term

The atomic R,ud formulas are of the form

s < t
(s,t) in E

where s,t are R,ud terms.

The R,ud conditions are inductively defined by

i. Every atomic R,ud formula is an R,ud condition.
ii. If A,B are R,ud conditions, then so are notA, A and B, A or B, A  
implies B, A iff B.

Obviously, every R,ud condition phi has a well defined meaning once we  
specify an order invariant graph G = (Q^k,E), and elements of Q^k for  
the variables that appear in phi.

TEMPLATE. Let phi be an R,ud formula with at most the variable x. In  
every order invariant graph on Q^k, there exists vertex x such that  
phi(x).

Obviously, there are very interesting weaker and very interesting  
stronger Templates to be considered. Note that this Template includes  
the Order Invariant Pattern Theorem as a special case.

CONJECTURE. Every instance of the Template can be proved using small  
large cardinals.

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

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

Harvey Friedman