[FOM] 465: Patterns in Order Invariant Graphs
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jun 4 17:51:29 EDT 2011
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
More information about the FOM
mailing list