[FOM] Fwd: 499: Embedded Maximal Cliques 2

[Harvey Friedman]

I have been migrating to gmail, and have seen that
http://www.cs.nyu.edu/pipermail/fom/2012-September/016692.html has a
lot of unintended blank space.

Because of this, I decided to start over with a longer posting (with a
bit more polish) than
http://www.cs.nyu.edu/pipermail/fom/2012-September/016692.html
which I have submitted under the plaintext option in gmail.

For introductory remarks, please see
http://www.cs.nyu.edu/pipermail/fom/2012-September/016692.html

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

*EMBEDDED MAXIMAL CLIQUES*
by
Harvey M. Friedman
September 19, 2012

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.*

A graph G is a pair (V,E), where V is a set and E ⊆ V^2 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
(∀v ∈ V)(∃w ∈ 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. RCA_0 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 ACA_0 over RCA_0.

We use PF(A) for the set of all partial functions from A into A. I.e.,
functions whose domain and range are subsets of A. The field of f is
fld(f) = dom(f) ∪ rng(f).

We say that a function is finite if and only if it has finite domain.

Let S ⊆ Ak. We say that S is f embedded if and only if

i. f ∈ PF(A).
ii. for all x1,...,xk ∈ dom(f), (x1,...,xk) ∈ S ↔ (f(x1),...,f(xk)) ∈ 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 and later, we use far reaching extensions of the usual
ZFC axioms for mathematics by large cardinal hypotheses.

SMAH+ = ZFC + (∀k)(∃λ)(λ is strongly k-Mahlo cardinal). SMAH = ZFC +
(∃λ)(λ is a strongly k-Mahlo cardinal).

SRP+ = ZFC + (∀k)(∃λ)(λ has the k-SRP). SRP = ZFC + {∃λ with the
k-SRP}k. λ has the k-SRP if and only if λ is a limit ordinal, where
every partition of the unordered k-tuples from λ into two pieces has a
stationary homogeneous set.

Here SRP is read "stationary Ramsey property".

Z = Zermelo set theory. WZ is Z with bounded separation.

RCA_0, WKL_0, ATR_0 are standard systems from Reverse Mathematics.

EFA = exponential function arithmetic, also referred to as IΣ0(exp).

We shall see that only the consistency of such far reaching extensions
of ZFC is  used here.

*2. Order invariant and order theoretic.*

We use Q, Z, Z+, N for the set of all rational numbers, integers,
positive integers, nonnegative integers, respectively.

We say that x,y ∈ Q^k are order equivalent if and only if for all 1 ≤
i,j ≤ k, xi < xj ↔ yi < yj.

Let V ⊆ Q^k. We say that A ⊆ V is order invariant if and only if for
all order equivalent x,y ∈ V, x ∈ A ↔ y ∈ A.

We say that G is an order invariant graph on V ⊆ Q^k if and only if G
is a graph on V, where the edge relation E ⊆ V^2 is order invariant.

We say that S ⊆ Q^k is order theoretic if and only if S can be defined
as a Boolean combination of inequalities x < y, where x,y are among
the variables v1,...,vk or constants for elements of Q.

We treat functions in terms of their graphs. Thus f ∈ PF(Q^k) is order
theoretic if and only if its graph (a subset of Q^2k) is order
theoretic.

We say that J is a rational interval if and only if

i. J ⊆ Q.
ii. a < b < c ∧ a,c ∈ J → b ∈ J.
iii. J = ∅, or inf(J), sup(J) ∈ Q ∪ {-∞,∞}.

We say that J is nontrivial if and only if J is nonempty, and inf(J) < sup(J).

The following structure theorems are very basic cases of a much wider
theory called o-minimality.

THEOREM 2.1. Let A ⊆ Q. A is order theoretic if and only if A is the
union of finitely many rational intervals.

We say that f ∈ PF(Q) is rudimentary if and only if dom(f) is a
rational interval, and f is either constant or the identity.

THEOREM 2.2. Let f ∈ PF(Q). f is order theoretic if and only if f is
the union of finitely many rudimentary g ∈ PF(Q).

THEOREM 2.3. Let f ∈ PF(Q) be strictly increasing and order theoretic.
Then f is the identity on the interior of its domain.

For p ∈ Q, we use Q≥p for {x ∈ Q: x ≥ p}, and the analogous notation
Q>p, Q≤p, Q<p. We also use this notation with Q replaced by N.

For p,q ∈ Q ∪ {-∞,∞}, we use Q[p,q], Q[p,q), Q(p.q], Q(p,q) for Q ∩
[p,q], Q ∩ [p,q), Q ∩ (p,q], Q ∩ (p,q), respectively.

Throughout this manuscript, J will always denote a rational interval.

For f ∈ PF(J), we write f^J for f extended by the identity on J ∩
(sup(fld(f)),infinity). I.e., f^J is f extended by the identity
function higher up.

We also define f^J- to be f extended by the identity on J ∩
(sup(fld(f))+1,infinity).

We say that f ∈ PF(Q) is continuous if and only if f is continuous at
every point in its domain. We say that f ∈ PF(Q) is bicontinuous if
and only if f is one-one, and f, f^-1 are both continuous.

*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. This remains open, but we have been able to handle all
continuous order theoretic f. Already for some very special continuous
order theoretic f, it is necessary and sufficient to go well beyond
the usual ZFC axioms for mathematics.

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 such that Proposition 3.4 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.4 for fixed k,n (assuming SRP is
consistent).

We now greatly extend Theorems 3.2, 3.3 and Proposition 3.4.

THEOREM 3.7. (ATR_0). OIG(J,f), where f ∈ PF(J\{sup(J)}) is strictly
increasing and finite. (RCA_0). There exists strictly increasing
finite f ∈ PF(Q[0,1]) such that ¬OIG(J,f).

THEOREM 3.8. (Z). OIG(J,f^J-), where f ∈ PF(J\{sup(J)|) is strictly
increasing and finite.

PROPOSITION 3.9. OIG(J,f^J), where f ∈ 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 ∈ PF(J) is infinite, strictly
increasing, bicontinuous, and order theoretic.

PROPOSITION 3.11. OIG(J,f), where f ∈ PF(J) is infinite, strictly
increasing, continuous, and order theoretic.

THEOREM 3.12. Theorems 3.5, 3.6 hold for Propositions 3.9, 3.11.

In light of Theorem 3.1 and Proposition 3.11, we have a complete
determination of the status of OIG(J,f) where f is infinite continuous
and order theoretic. The finite case will be completed in section 5.

THEOREM 3.13. 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) are
infinite, strictly increasing, bicontinuous, order theoretic, and
dom(f1) ⊆ ... ⊆ dom(fm).

PROPOSITION 4.9. OIG(J,f1,...,fm), where f1,...,fm ∈ PF(J) are
infinite, strictly increasing, continuous, order theoretic, and
dom(f1) ⊆ ... ⊆ dom(fm).

THEOREM 4.10. Theorem 4.8 is not provable in WZ. Theorems 3.4, 3.5
hold for Propositions 4.3, 4.6, 4.9.

THEOREM 4.11. 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.

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.

TO BE CONTINUED.

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

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

Harvey Friedman