[FOM] 498: Embedded Maximal Cliques 1
Harvey Friedman
hmflogic at gmail.com
Tue Sep 18 12:43:25 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
There have been significant breakthroughs on various fronts in Concrete
Mathematical Incompleteness at the Pi01 level.
The crucial milestone that remained
http://www.cs.nyu.edu/pipermail/fom/2012-May/016458.html was the
simplification of the natural but somewhat awkward notion of invariance
used in the fully satisfactory template
EVERY ORDER INVARIANT GRAPH ON EVERY Q>=0^k HAS AN "INVARIANT" MAXIMAL
CLIQUE.
In http://www.cs.nyu.edu/pipermail/fom/2012-May/016458.html we used various
finite intervals in the rationals, but now prefer to use the single
interval Q>=0 of nonnegative rationals.
A main breakthrough has been the use of the particularly well known kind of
invariance represented by the usual notion of (partial) embedding, familiar
to algebraists, logicians, and others. As is usual, embeddings are one
dimensional (partial) functions. Note the title "Embedded Maximal Cliques",
replacing the former "Invariant Maximal Cliques".
We will present this higher state of the art in multiple installments. This
first installment will discuss only the specific infinitary statements
involving particularly simple kinds of partial embeddings.
*******************************************
*EMBEDDED MAXIMAL CLIQUES*
by
Harvey M. Friedman
September 17, 2012
Abstract. For k,n >= 1, every order invariant graph on Q>=0^k has an f
embedded maximal clique, where f is +1 on {0,...,n}. For k,n >= 1, every
order invariant graph on Q>=0^k has an f embedded maximal clique, where f
is +1 on {0,...,n} extended by the identity on Q>n+1. We give a proof of
the first statement well within the usual ZFC axioms for mathematics. We
give a proof of the second statement using axioms that go well beyond ZFC.
We prove that ZFC does not suffice (assuming ZFC is consistent). As a
consequence of the Goedel completeness theorem, both statements are Pi01.
We develop transparent finite forms that are explicitly Pi01. These predict
that certain computer searches will result in actual certificates. Computer
investigations are discussed which may indicate how these predictions can
be argued to provide confirmation of the consistency, or pragmatic
consistency, of ZFC and some of its far reaching extensions.
*1. Graphs, cliques, embeddings.*
A graph G is a pair (V,E), where V is a set and E is a subset of V^2 that
is irreflexive and symmetric. V is the set of vertices, and E is the
adjacency relation. We say that G is a graph on V.
A clique is a subset of V, where any two distinct elements are adjacent. A
maximal clique is a clique which is not a proper subset of a clique.
Note that S is a maximal clique if and only if S is a clique, where (for
all v in V)(there exists w in S)(v,w are not adjacent).
We have the following well known theorem.
THEOREM 1.1. Every graph has a maximal clique. This is provably equivalent
to the axiom of choice over ZF.
We will only be concerned with countable graphs.
THEOREM 1.2. RCA0 proves that every countable graph has a maximal clique.
The statement "in every countable graph, every clique is contained in a
maximal clique" is equivalent to ACA0 over RCA0.
The field of f is fld(f) = dom(f) union rng(f).
We use PF(A) for the set of all partial functions from A into A. I.e.,
functions whose field is a subset of A.
We say that a function is finite if and only if it has finite domain.
Let S be a subset of A^k. We say that S is f embedded if and only if
i. f is in PF(A).
ii. for all x1,...,xk in dom(f), (x1,...,xk) in S iff (f(x1),...,f(xk))
in S.
More generally, we say that S is f1,...,fn embedded if and only if for all
1 <= i <= n, S is fi embedded.
In sections 3,4, and elsewhere, we use far reaching extensions of the usual
ZFC axioms for mathematics by large cardinal hypotheses.
SMAH+ = ZFC + (for all k)(there exists lambda)(lambda is strongly k-Mahlo
cardinal). SMAH = ZFC + (there exists a strongly k-Mahlo cardinal)_k.
SRP+ = ZFC + (for all k)(there exists lambda)(lambda has the k-SRP). SRP =
ZFC + {there exists lambda with the k-SRP}_k. lambda has the k-SRP if and
only if lambda is a limit ordinal, where every partition of the unordered
k-tuples from lambda into two pieces has a stationary homogeneous set.
Z = Zermelo set theory. WZ is Z with bounded separation.
ACA' = RCA0 + for all x,n, the n-th Turing jump of x exists.
Here SRP is read "stationary Ramsey property".
We shall see that the the consistency alone of such far reaching extensions
of ZFC is sufficient to prove Embedded Maximal Clique theorems.
*2. Order invariant graphs.*
We say that x,y in Q^k are order equivalent if and only if for all 1 <= i,j
<= k, xi < xj iff yi < yj.
Let V be a subset of Q^k. We say that A contained in V is order invariant
if and only if for all order equivalent x,y in V, x in A iff y in A.
A graph on V^k is said to be order invariant if and only if the edge set E
contained in V^2k is order invariant.
We use Q for the set of all rational numbers, and Q>p, Q>=p, p in Q, for
the set of all rationals >p, >=p, respectively.
More generally, the rational intervals are intervals J of rationals where
inf(J), sup(J) are in Q union {infinity,-infinity}.
Let f in PF(J) be finite. We write f^J for f extended by the identity on J
intersect (max(fld(f)),infinity). I.e., f^J is f extended by the identity
higher up. Note that if f is strictly increasing then f^J is strictly
increasing.
Whenever we write J it is understood that J is a rational interval.
*3. OIG(J,f). *
Let f be in PF(J). We investigate the statement OIG(J,f) =
every order invariant graph on every J^k has an f embedded maximal clique.
Our understanding of OIG(J,f) is far from complete, and we restrict
attention to very simple f in PF(J).
First a very general result.
THEOREM 3.1. If OIG(J,f) then f is strictly increasing.
We begin by discussing two very specific simple cases of OIG(J,f) that are
stated in the Abstract.
THEOREM 3.2. OIG(Q>=0,f), where f is +1 on {0,...,n}.
PROPOSITION 3.3. OIG(Q>=0,f), where f is +1 on {0,...,n} extended by the
identity on Q>n+1.
THEOREM 3.4. (EFA). Theorem 3.1 is provable in RCA0. Theorem 3.2 is
provable in ATR0. Proposition 3.3 is provable in SRP+, and (assuming ZFC is
consistent) is not provable in ZFC. Proposition 3.3 is provably equivalent
to Con(SRP) over WKL0. Proposition 3.3 is not provable from any consistent
consequence of SRP that proves WKL0.
THEOREM 3.5. (EFA). There are fixed k,n such that Proposition 3.3 for
graphs on (Q>=0)^k is not provable in ZFC (assuming that ZFC is
consistent). No finite fragment of SRP suffices to prove every instance of
Proposition 3.3 for fixed k,n (assuming SRP is consistent).
It is too early to tell how small k,n can be for Proposition 3.3 to go
beyond ZFC. A good target would be, say, k = n = 8.
We now generalize these two special cases.
THEOREM 3.6. OIG(J,f), where f in PF(J\{sup(J)}) is strictly increasing and
finite.
PROPOSITION 3.7. OIG(J,f^J), where f in PF(J\{sup(J)}) is strictly
increasing and finite.
THEOREM 3.8. RCA0 refutes Theorem 3.6 for PF(J), J = Q intersect
[0,1]. Theorems
3.4, 3.5 hold for Theorem 3.2, Proposition 3.3 replaced by Theorems 3.6,
Propositions 3.7.
*4. OIG(J,f1,...,fm).*
Let J be a rational interval and f1,...,fm be in PF(J). We investigate the
statement OIG(J,f1,...,fm) =
every order invariant graph on every J^k has an f1,...,fm embedded maximal
clique.
The results of section 3 all extend to this multiple form.
THEOREM 4.1. OIG(Q>=0,f1,...,fm), where fi is +1 on {0,...,i}.
PROPOSITION 4.2. OIG(Q>=0,f1,...,fm), where fi is +1 on {0,...,i} extended
by the identity on Q>i+1.
THEOREM 4.3. OIG(J,f1,...,fm), where f1,...,fm in PF(J\sup(J)) are strictly
increasing and finite.
PROPOSITION 4.4. OIG(J,f1^J,...,fm^J), where f1,...,fm in PF(J\sup(J)) are
strictly increasing and finite.
THEOREM 4.5. Theorems 3.4, 3.5 hold for Theorem 3.2, Proposition 3.3
replaced by Theorem 4.1, Proposition 4.2, or replaced by Theorem 4.3,
Proposition 4.4.
TO BE CONTINUED.
*******************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 498th 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
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
489: Invariant Maximality Programs 3/24/12 2:31PM
490: Invariant Maximality Program 2 3/24/12 3:19PM
491: Formal Simplicity 3/25/12 11:50PM
492: Invariant Maximality/conjectures 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv 4/5/12 4:17PM
495: Invariant Finite Choice 4/5/12 4:18PM
496: Invariant Finite Choice/restatement 4/8/12 2:18AM
497: Invariant Maximality Restated 5/2/12 2:49AM
Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120918/f9093f6e/attachment-0001.html>
More information about the FOM
mailing list