[FOM] 500: Embedded Maximal Cliques 3
Harvey Friedman
hmflogic at gmail.com
Thu Sep 20 22:15:38 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
except for introductory remarks at
http://www.cs.nyu.edu/pipermail/fom/2012-September/016692.html
and preliminary sections 1,2 at
http://www.cs.nyu.edu/pipermail/fom/2012-September/016695.html
WE FIRST REPEAT THE ABSTRACT AND GIVE A TABLE OF CONTENTS FOR THE
CONVENIENCE OF THE READER. SECTIONS 9,10,11 ARE IN THE NEXT POSTING.
Abstract. Every order invariant graph on Q≥0^k has an f embedded
maximal clique, where f is +1 on {0,...,n}. 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 within the usual ZFC axioms for mathematics. We give a
proof of the second statement (and more general statements) that goes
well beyond ZFC, and establish that ZFC does not suffice (assuming ZFC
is consistent). As a consequence of the Gödel completeness theorem,
both statements are Π01. We develop transparent finite forms that are
explicitly Π01. 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.
2. Order invariant and order theoretic.
3. OIG(J,f).
4. OIG(J,f1,...,fn).
5. OIG characterizations
6. Total embeddings.
7. n-invariance.
8. General conjectures.
9. Finite forms.
10. Extremely strong statement.
11. Computational aspects.
*****************************************
We have to weaken some of the general results concerning order
theoretic functions and OIG(J,f). For this reason, we restart the
series of postings at section 3.
EMBEDDED MAXIMAL CLIQUES continued
*3. OIG(J,f).*
In this section, we investigate the statement OIG(J,f) =
every order invariant graph on every J^k has an
f embedded maximal clique.
for order theoretic f ∈ PF(J). A major goal is to determine the status
of OIG(J,f) for all order theoretic f. We have been able to deal with
some particularly simple order theoretic f. The finite case is
completed in section 5.
The first result concerns the special role of "strictly increasing"
for arbitrary f ∈ PF(J).
THEOREM 3.1. (RCA_0). OIG(J,f) implies f is strictly increasing.
THEOREM 3.2. (ATR_0). OIG(Q≥0,f), where f is +1 on {0,...,n}.
THEOREM 3.3. (Z). OIG(Q≥0,f), where f is +1 on {0,...,n} extended by
the identity on Q>n+2.
PROPOSITION 3.4. OIG(Q≥0,f), where f is +1 on {0,...,n} extended by
the identity on Q>n+1.
THEOREM 3.5. (EFA). Proposition 3.4 is provable in SRP+, and (assuming
ZFC is consistent) not provable in ZFC. Proposition 3.4 is provably
equivalent to Con(SRP) over WKL_0. Proposition 3.4 is not provable
from any consistent consequence of SRP that proves WKL_0.
THEOREM 3.6. (EFA). There are fixed k,n, and graph G on Q>=0^k such
that phi(k,n,G,f) = "G has an f embedded maximal clique", where f is
as in Proposition 3.4, is not provable in ZFC (assuming that ZFC is
consistent). No finite fragment of SRP suffices to prove every
phi(k,n,G,f), f from Proposition 3.4 (assuming SRP is consistent).
We now greatly extend Theorems 3.2, 3.3 and Proposition 3.4.
THEOREM 3.7. (ATR0). OIG(J,f), where f in PF(J\{sup(J)}) is strictly
increasing and finite. (RCA0). There exists strictly increasing and
finite f in PF(Q[0,1]) such that not OIG(J,f).
THEOREM 3.8. (Z). OIG(J,f^J-), where f in PF(J\{sup(J)|) is strictly
increasing and finite.
PROPOSITION 3.9. OIG(J,f^J), where f in PF(J\{sup(J)}) is strictly
increasing and finite.
We now bring in continuity and bicontinuity.
THEOREM 3.10. (Z). OIG(J,f), where f in PF(J\{inf(J),sup(J)}) is
strictly increasing, order theoretic, and continuous.
THEOREM 3.11. (Z). OIG(J,f), where f in PF(J) is infinite, strictly
increasing, order theoretic, and bicontinuous.
PROPOSITION 3.12. OIG(J,f), where f in PF(J) is strictly increasing,
order theoretic, and with a single point of non bicontinuity.
THEOREM 3.13. Theorems 3.5, 3.6 hold for Propositions 3.9, 3.12.
THEOREM 3.14. Every instance of OIG(J,f) is provably equivalent to a
Π01 sentence over WKL_0. This is true even for any specific order
invariant graph.
*4. OIG(J,f1,...,fm).*
In this section, we investigate the statement OIG(J,f1,...,fm) =
every order invariant graph on every J^k has an
f1,...,fm embedded maximal clique
for order theoretic f ∈ PF(J). A major goal is to determine the status
of OIG(J,f1,...,fm) for all order theoretic f1,...,fm. We have been
able to deal with some particularly simple order theoretic f1,...,fm.
The finite case is completed in section 5.
THEOREM 4.1. (ATR_0). OIG(Q≥0,f1,...,fm), where fi is +1 on {0,...,i}.
THEOREM 4.2. (Z). OIG(Q≥0,f1,...,fm), where fi is +1 on {0,...,i}
extended by the identity on Q>i+2.
PROPOSITION 4.3. OIG(Q≥0,f1,...,fm), where fi is +1 on {0,...,i}
extended by the identity on Q>i+1.
THEOREM 4.4. (ATR_0). OIG(J,f1,...,fm), where f1,...,fm ∈
PF(J\{sup(J)}) are strictly increasing and finite.
THEOREM 4.5. (Z). OIG(J,f1^J-,...,fm^J-), where f1,...,fm ∈
PF(J\{sup(J)}) are strictly increasing and finite.
PROPOSITION 4.6. OIG(J,f1^J,...,fm^J), where f1,...,fm ∈
PF(J\{sup(J)}) are strictly increasing and finite.
THEOREM 4.7. (RCA_0). Let J be nontrivial. There exists f,g ∈ PF(J),
which are strictly increasing, bicontinuous, order theoretic, and
¬OIG(J,f,g).
THEOREM 4.8. (Z). OIG(J,f1,...,fm), where f1,...,fm ∈
PF(J\{inf(J),sup(J)}) are strictly increasing, order theoretic,
continuous, and dom(f1) ⊆ ... ⊆ dom(fm).
THEOREM 4.9. (Z). OIG(J,f1,...,fm), where f1,...,fm ∈ PF(J) are
infinite, strictly increasing, bicontinuous, order theoretic, and
dom(f1) ⊆ ... ⊆ dom(fm).
PROPOSITION 4.10. OIG(J,f1,...,fm), where f1,...,fm ∈ PF(J) are
strictly increasing, order theoretic, each with a single point of non
bicontinuity, and dom(f1) ⊆ ... ⊆ dom(fm).
THEOREM 4.11. Theorem 4.8 is not provable in WZ. Theorems 3.4, 3.5
hold for Propositions 4.3, 4.6, 4.9.
THEOREM 4.12. Every instance of OIG(J,f1,...,fm) is provably
equivalent to a Π01 sentence over WKL_0. This is true even for any
specific order invariant graph.
*5. OIG characterizations.*
THEOREM 5.1. (ATR0). Let f in PF(J) be finite. OIG(J,f) if and only if
i. f is strictly increasing.
ii. if |dom(f)| >= 2 then some p in J lies outside every nontrivial
interval [x,f(x)] union [f(x),x].
THEOREM 5.2. (ATR0). Let f1,...,fm in PF(J) be finite.
OIG(J,f1,...,fm) if and only if
i. f is strictly increasing.
ii. for all i, if |dom(fi)| >= 2 then some p in J lies outside every
nontrivial interval [x,fi(x)] union [fi(x),x].
Here are three characterizations that follow immediately from section 3.
THEOREM 5.3. (Z). Let f in PF(J\{inf(J),sup(J)}) be order theoretic
and continuous. OIG(J,f) if and only if f is strictly increasing.
THEOREM 5.4. (Z). Let f in PF(J) be infinite, order theoretic, and
bicontinuous. OIG(J,f) if and only if f is strictly increasing.
PROPOSITION 5.5. Let f in PF(J) be order theoretic, with a single
point of non bicontinuity. OIG(J,f) if and only if f is strictly
increasing.
THEOREM 5.6. Theorems 3.5, 3.6 hold for Proposition 5.5.
*6. Total embeddings.*
THEOREM 6.1. (RCA_0). If f ∈ TF(J) is order theoretic, then OIG(J,f)
if and only if f is the identity.
THEOREM 6.2. (ATR_0). Let f1,...,fm ∈ PF(J) be strictly increasing and
finite, where rng(f1) ∪ ... ∪ rng(fm) does not contain any endpoint of
J. There exist respective extensions g1,...,gm ∈ TF(J) of f1,...,fm
such that OIG(J,g1,...,gm).
THEOREM 6.3. (ATR_0). Let f1,...,fm ∈ PF(J) be finite, where fld(f1) ∪
... ∪ fld(fm) does not contain any endpoint of J. There exist
respective bijective extensions g1,...,gm ∈ TF(J) of f1,...,fm such
that OIG(J,g1,...,gm).
THEOREM 6.4. (Z). Let f1,...,fm ∈ PF(J) be strictly increasing and
finite, where rng(f1) ∪ ... ∪ rng(fm) does not contain any endpoint of
J. There exist respective extensions g1,...,gm ∈ TF(J) of
f1^J-,...,fm^J- such that OIG(J,g1,...,gm).
THEOREM 6.5. (Z). Let f1,...,fm ∈ PF(J) be strictly increasing and
finite, where fld(f1) ∪ ... ∪ fld(fm) does not contain any endpoint of
J. There exist respective bijective extensions g1,...,gm ∈ TF(J) of
f1^J-,...,fm^J- such that OIG(J,g1,...,gm).
PROPOSITION 6.6. Let f1,...,fm ∈ PF(J) be strictly increasing and
finite, where rng(f1) ∪ ... ∪ rng(fm) does not contain any endpoint of
J. There exist respective extensions g1,...,gm ∈ TF(J) of
f1^J,...,fm^J such that OIG(J,g1,...,gm).
THEOREM 6.7. Theorems 6.4, 6.5 cannot be proved in WZ. Theorems 3.5,
3.6 hold for Proposition 6.6. These results also hold if we set
J,f1,...,fm as in Theorem 4.1.
We say that f ∈ PF(J) is "real piecewise linear" if and only if f is
the restriction of a piecewise linear function from reals into reals
to J. Here not only are we allowed to use the group structure of ℜ,
but also constants from ℜ.
THEOREM 6.8. (Z). In Theorems 6.2 - 6.5, we can require that the total
embeddings be real piecewise linear. This is false for Proposition
6.6.
*7. n-invariance.*
We have already used f embedded S ⊆ Q≥0^k for some specific order
theoretic f ∈ PF(Q≥0) in Theorems 3,2, 3.3, and Proposition 3.4.
These f embeddings are one dimensional. We now introduce the higher
dimensional notion of n-invariant S ⊆ Q≥0^k.
We first introduce the following notation. LSH[n] ∈ PF(Q≥0) is +1 on
{0,...,n} extended by the identity on Q>n+1. LSH is read "lower
shift".
We say that x,y ∈ Q≥0k are n-equivalent if and only if
i. the p > n appear in the same positions in x,y.
ii. the remaining coordinates of x,y lie in {0,...,n}
iii. x,y are order equivalent.
THEOREM 7.1. (RCA_0). n-equivalence is the least equivalence relation
on Q≥0^k containing the graphs of LSH[0],...,LSH[n-1].
We say that S ⊆ Q≥0^k is n-invariant if and only if for all
n-equivalent x,y ∈ Q>=0^k, x ∈ S → y ∈ S.
THEOREM 7.2. (RCA_0). S ⊆ Q≥0^k is n-invariant if and only if S is
LSH[0],...,LSH[n-1] embedded.
Thus we can now restate Proposition 4.3 as follows.
PROPOSITION 7.3. Every order invariant graph on Q≥0^k has an
n-invariant maximal clique.
THEOREM 7.4. Theorems 3.5, 3.6 hold for Proposition 7.3.
Note that n-invariance on Q≥0^k is a very special case of the general
notion of invariance. Here is a very general formulation. Let R be a
binary relation anywhere, and S ⊆ A^k. We say that S is R invariant if
and only if for all x,y ∈ A^k, if R(x,y) and x ∈ S, then y ∈ S.
Thus S ⊆ Q≥0^k is n-invariant if and only if S is R invariant, where R
is n-equivalence on Q≥0^k.
*8. General conjectures.*
CONJECTURE 8.1. Let J be a rational interval and f1,...,fn ∈ PF be
order theoretic. Then OIG(J,f1,...,fn) is provable or refutable in
SRP.
THEOREM 8.2. (RCA_0). Conjecture 9.1 fails if we replace SRP by any
consistent consequence of SRP that proves WKL_0.
We observe that if OIG(J,f1,...,fn) is provable or refutable in SRP,
then it is provable or refutable in WKL_0 + Con(SRP), and even in
WKL_0 + the consistency of some finite fragment of SRP.
We can also fix the order invariant graph. For this purpose, it is
more natural to consider a wider family of graphs.
An order theoretic graph is a graph whose vertex set V is an order
theoretic subset of some Q^k, and whose edge set is an order theoretic
subset of V^2. Obviously every order invariant graph on any J^k is an
order theoretic graph.
CONJECTURE 8.3. Let G be an order theoretic graph and f1,...,fn ∈
PF(V(G)) be order theoretic. Then "G has an f1,...,fn embedded maximal
clique" is provable or refutable in SRP.
THEOREM 8.4. (RCA_0). Conjecture 8.3 fails if we replace SRP by any
consistent consequence of SRP that proves WKL_0.
We can go further and bring in invariance notions, and not just embeddings.
CONJECTURE 8.5. Let J be a rational interval and R1,...,Rn ⊆ J^2k be
order theoretic. Then OIG(J,R1,...,Rn) is provable or refutable in
SRP.
CONJECTURE 8.6. Let G be an order theoretic graph and R1,...,Rn ⊆ J^2k
be order theoretic. Then "G has an R1,...,Rn embedded maximal clique"
is provable or refutable in SRP.
The following is proved using Gödel's completeness theorem.
THEOREM 8.7. Each instance α of these conjecturess can be effectively
converted to a Π01 sentence α* such that WKL_0 proves α ↔ α*.
TO BE CONTINUED.
*******************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 500th 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
498: Embedded Maximal Cliques 1 9/18/12 12:43AM
499. Embedded Maximal Cliques 2 9/19/12 2:50AM
Harvey Friedman
More information about the FOM
mailing list