[FOM] 457: Maximal Cliques and Large Cardinals

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

There appears to have been major breakthroughs on many fronts since http://www.cs.nyu.edu/pipermail/fom/2011-January/015268.html

The new results concerning Maximal Cliques have pretty much  
stabilized, although there are some serious open issues.

Most of the claims here concerning Maximal Cliques are very delicate -  
particularly the reversals. I am committed to a manuscript for  
publication by the end of the calendar year.

So you should view the claims as somewhat tentative, but I feel that I  
have enough control to make this hedged announcement.

MAXIMAL CLIQUES AND LARGE CARDINALS
by
Harvey M. Friedman

1. Graphs, Cliques, and Order Invariance.
2. Maximal Clique Upper Split Theorem.
3. Maximal Clique Embedding Theorems.
4. Greedy Cliques and Huge Cardinals.
5. Sequential Constructions.
6. Finite Games.
7. Templates.

1. Graphs, Cliques, and Order Invaraince.

A graph is a pair G = (V,E), where V is a set of vertices, and E  
contained in V^2 is irreflexive and symmetric. We say that G is a  
graph on V, and E is the edge relation of G. We say that x,y are  
connected in G if and only if x E y.

We say that S is a clique in G if and only if S is a set of vertices  
of G, where any two distinct elements of S are connected in G.

We say that S is a maximal clique in G if and only if S is a clique in  
G which is not a proper subset of any clique in G.

We now fix k >= 1 and A contained in Q. We work entirely within the  
spaces A^k and A^2k.

We say that x,y in A^2k are order equivalent if and only if for all 1  
<= i,j <= 2k, x_i < x_j iff y_i < y_j.

We say that E contained in A^2k is order invariant if and only if for  
all order equivalent x,y in A^2k, x in E iff y in E.

We say that G is an order invariant graph on A^k if and only if G is a  
graph on A^k whose edge relation is an order invariant subset of A^2k.

THEOREM 1.1. Every graph has a maximal clique.

Proof: This is well known and follows easily from Zorn's Lemma. We can  
also well order the vertex set and perform a transfinite recursion. QED

We say that x_1,...,x_n is a clique in (V,E) if and only if  
{x_1,...,x_n} is a clique in (V,E).

THEOREM 1.2. The following is provable in RCA_0. Every countable graph  
has a maximal clique.

Proof: Let (V,E) be a graph, where V is countable. We say that x is a  
neighbor of y if and only if x E y.

Let x_1,x_2,... be an enumeration of V. We recursively define
y_i = x_i if {y_1,...,y_i-1,x_i} is a clique in (V,E); x_i-1 otherwise.

Obviously {y_1,y_2,...} is a maximal clique in (V,E). QED

2. Maximal Clique Upper Split Theorem.

Let S contained in Q^k. The split of S is the result of dividing the  
coordinates of vectors in S by 2. Thus the split of (1,4),(-1,3)} is  
{(1/2,2),(-1/2,3/2)}.

The upper split of S is the result of dividing the nonnegative  
coordinates of vectors in S by 2. Thus the upper split of {(1,4), 
(-1,3)} is {(0,2),(-1,3/2)}.

THEOREM 2.1. The following two statements refutable in RCA_0. Every  
order invariant graph on [-1,1]^k intersect Q^k has a maximal clique  
containing its split. Every order invariant graph on [-1,1]^k  
intersect Q^k has a maximal clique containing its upper split.

The nonzero part of S contained in Q^k is the set of vectors in S all  
of whose coordinates are nonzero.

THEOREM 2.2. The following is refutable in RCA_0. Every order  
invariant graph on [-1,1]^k intersect Q^k has a maximal clique  
containing the nonzero part of its split.

MAXIMAL CLIQUE UPPER SPLIT THEOREM. Every order invariant graph on  
[-1,1]^k intersect Q^k has a maximal clique containing the nonzero  
part of its upper split.

THEOREM 0.14E.3. MCUST is provably equivalent to Con(SMAH) over WKL_0.  
MCUST is provable in SMAH+ but not in any consistent fragment of SMAH  
that logically implies RCA_0.

MCUST and the above variants can all be naturally viewed as instances  
of a fundamental template. This is discussed in section 7.

3. Maximal Clique Embedding Theorems.

Here we focus on general structural properties of maximal cliques.

Let S contained in A^k. We say that h is an embedding of S if and only  
if h:A into A, and for all q_1,...,q_k in A,

(q_1,...,q_k) in S iff (h(q_1),...,h(q_k)) in S.

Let S be contained in A^k. We say that h is an injection of S if and  
only if h:A into A, and for all q_1,...,q_k in A,

(q_1,...,q_k) in S iff (h(q_1),...,h(q_k)) in S.

In partial embeddings and partial injections, we allow h:A into A to  
be partially defined, and use q_1,...,q_k in dom(h) instead of  
q_1,...,q_k in A.

The modifier "nontrivial" requires that the function not be an  
identity function.

The fixed point set of any function is the set of its fixed points.

MAXIMAL CLIQUE EMBEDDING THEOREM 1. Every order invariant graph on  
[0,1]^k intersect Q^k has a maximal clique with a nontrivial embedding.

MAXIMAL CLIQUE EMBEDDING THEOREM 2. Every order invariant graph on  
[0,1]k intersect Q^k has a maximal clique with a nontrivial embedding  
whose range forms an interval.

MAXIMAL CLIQUE EMBEDDING THEOREM 3. Every order invariant graph on  
[0,1]^k intersect Q^k has a maximal clique with a nontrivial embedding  
whose fixed points forms an interval.

MAXIMAL CLIQUE EMBEDDING THEOREM 4. Every order invariant graph on  
[0,1]^k intersect Q^k has a maximal clique with a nontrivial embedding  
whose range and whose fixed points each form an interval.

MAXIMAL CLIQUE EMBEDDING THEOREM 5. Every order invariant graph on  
[0,1]^k intersect Q^k has a maximal clique with a nontrivial embedding  
whose range and whose fixed points each form intervals with rational  
endpoints.

MAXIMAL CLIQUE INJECTION THEOREMS 1- 5. These are obtained by  
replacing "embedding" with "injection".

THEOREM 3.1. MCET1,2 and MCIT1,2 are provable in ACA. MCET4 is  
provably equivalent to Con(SMAH) over WKL_0. It is provable in SMAH+  
but not in any consistant fragment of SMAH that logically implies  
RCA_0. MCIT5 is provably equivalent to Con(SRP) over WKL_0. It is  
provable in SRP+ but not in any consistant fragment of SRP that  
logically implies RCA_0.

Recall from section 0.4 that WKL_0 is Weak Konig's Lemma. Recall the  
definitions of SMAH+, SMAH, SRP+, and SRP from previous FOM postings.

We do not know the status of MCET3 and MCIT3.

MCET1-5 and MCIT1-5 are instances of natural Templates. See section  
0.14J.

4. Greedy Cliques and Huge Cardinals.
Let G be a graph on A^k, A contained in Q. It is easy to see that S is  
a maximal clique in G if and only if

S is the set of all vertices that are connected to every other element  
of S.

  We say that S is a greedy clique in G if and only if

S is the set of all vertices that are connected to every element of S  
with smaller max.

We say that S is a locally maximal clique in G if and only if

for all x in A^k, S|<=x is a maximal clique in G|<=x.

Here S|<=x and G|<=x are S and G restricted to vectors whose max is at  
most the max of x.

We now present three backgkround theorems.

THEOREM 4.1. Let G be a graph on A^k, A contained in Q. The greedy  
cliques in G are the same as the locally maximal cliques in G, all of  
which are maximal cliques in G.

THEOREM 4.2. For all A contained in Q, the following are equivalent.

i. Every graph on A has a greedy clique.

ii. Every graph on every Ak has a unique greedy clique.

iii. A is well ordered.

Furthermore, iii implies i, and iii implies ii are provably equivalent  
to ATR_0 over RCA_0.

THEOREM 4.3. There is a non well ordered recursive A contained in Q  
such that every order invariant graph on every A^k has a greedy  
clique. The greedy clique will not, in general, be unique. The  
possible order types of such A can be completely analyzed according to

[Fr73] H. Friedman, Countable Models of Set Theories, Lecture Notes in  
Mathematics, Vol. 337, Springer-Verlag, (1973), pp. 539-573.

The upper shift of S contained in Q^k is obtained by adding 1 to all  
nonnegative coordinates of vectors in S.

GREEDY CLIQUE UPPER SHIFT THEOREM. For some 0 in A contained in Q,  
every order invariant graph on A^k has a greedy clique containing its  
upper shift.

THEOREM 4.4. The Greedy Clique Upper Shift Theorem is provably  
equivalent, over WKL_0, to Con(SRP). It is provable in SRP+ but not in  
any consistent fragment of SRP that logically implies RCA_0.

Let f:A^2 into A, A contained in Q. The f-sets are analogous to the  
semialgebraic sets in semialgebraic geometry with rational  
coeffeicients.

An f-set is a subset of some Ak which is in the Boolean algebra  
generated by inequalities in f, without constants.

In the language of model theory, the f-sets are the quantifier free  
definable without parameters in (A,<,f).

The f-graphs are the graphs on the A^k whose edge relation is an f-set  
of dimension 2k.

EXOTIC GREEDY CLIQUE EMBEDDING THEOREM. For some f:A^2 into A, N  
contained in A contained in Q, every f-graph has a greedy clique with  
the nontrivial embedding f(x,ceiling(x+1)).

Here the ceiling of x is the least integer >= x.

THEOREM 4.5. The Exotic Maximal Clique Embedding Theorem is provably  
equivalent, over WKL_0, to Con(HUGE). It is provable in HUGE+ but not  
in any consistent fragment of HUGE that logically implies RCA_0.

Here HUGE+ = ZFC + (forall n)(there exists an elementary embedding  
j:V(alpha) into V(beta) with critical point kappa, where alpha = j^(n) 
(kappa)). HUGE = ZFC + {there exists an elementary embedding  
j:V(alpha) into V(beta) with critical point kappa, where alpha = j^(n) 
(kappa))}_n.

5. Sequential Constructions.

The statement that lends itself best to sequential constructions is  
the following weakening of the Greedy Clique Upper Shift Theorem.

NONUNIFORM GREEDY CLIQUE UPPER SHIFT THEOREM. For any order invariant  
graph on Q^k, the induced subgraph on some A^k, 0 in A contained in Q,  
has a greedy clique containing its upper shift.

THEOREM 5.1. The Nonuniform Greedy Clique Upper Shift Theorem is  
provably equivalent, over WKL0, to Con(SRP). It is provable in SRP+  
but not in any consistent fragment of SRP that logically implies RCA_0.

Fix an order invariant graph G on Q^k. We now present the  
nondeterministic G construction.

At any stage in the construction, we have a finite list of entries,  
each of which is either x+ or x-, where x in Q^k.

The idea is that entries x+ indicate that x is in the prospective  
greedy clique, whereas entry x- indicate that x is not in the  
prospective greedy clique.

Let w_1,...,w_r in Q^k. The birthdate of z in w_1,...,w_r is the least  
i such that every coordinate of z is a coordinate of some w_j, j <= i.  
If there is no such i, then the birthdate is infinity.

We start the G construction by setting x_1+/- to be (0,...,0)+ or  
(0,...,0)-.

Suppose x_1+/-,...,x_i+/- in Q^k, i >= 1, have been constructed.

case 1. x_i+/- is x_i+. Set x_i+1+/- = x_i+1+, where x_i+1 is a vector  
not among x_1,...,x_i whose birthdate in x_1,...,x_i is as small as  
possible.

case 2. x_i+/- is x_i-. Set x_i+1+/- = y+, where y in Q^k, max(y) <  
max(x_i+1). and y,x_i+1 are not connected in G.

INFINITE GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k, there is a G construction x_1+/-,x_2+/-,... such that  
the positive entries together with their upper shifts form a G clique.

FINITE GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k and n ³ 1, there is a G construction x_1+/-,...,x_n+/-  
such that the positive entries together with their upper shifts form a  
G clique.

ESTIMATED GREEDY CLIQUE CONSTRUCTION THEOREM. For any order invariant  
graph G on Q^k and n >= 1, there is a G construction x_1+/-,...,x_n+/-  
such that the positive entries together with their upper shifts form a  
G clique, where the numerators and denominators in x_1,...,x_n are of  
magnitude at most (8kn)!!.

Here we use a very crude but safe estimate. We expect to give more  
refined estaimates in the future.

Note that FGCCT is explicitly Pi02, whereas EGCCT is explicitly Pi01.

THEOREM 5.2. IGCCT is provably equivalent, over EFA, to Con(SRP). It  
is provable in SRP+ but not in any consistent fragment of SRP that  
logically implies RCA_0.
THEOREM 5.3. FGCCT, EGCCT are provably equivalent, over EFA, to  
Con(SRP). They are provable in SRP+ but not in any consistent fragment  
of SRP that logically implies EFA.

We now make an observation about MCET1-5, MCIT1-5 from section 3.

Each of these ten statements can be readily seen to be provably  
equivalent to Pi01 sentences over WKLz-0. Specifically, it is clear  
that the MCET1-5, MCIT1-5 take the following form.

for all order invariant relations R on a

dense linear ordering with endpoints,

a particular sentence in predicate calculus,

constructed explicitly from R by hand,

has a countable model.

Then by the completeness theorem for predicate calculus, this  
assertion takes the form

for all order invariant relations R on a

dense linear ordering with endpoints,

a particular sentence in predicate calculus,

constructed explicitly from R by hand,

is formally consistent.

Note that this is in explicitly Pi01 form.

Actually, only a convenient and mathematically familiar fragment of  
predicate calculus is needed for the natural formalization - the  
A...AE...E fragment. Furthermore, through the obvious introduction of  
function symbols and constants (and removing relation symbols), all  
mention of predicate calculus can be removed, leaving only universal  
quantifiers followed by formulas with the logical connectives.

This is a particularly mathematically transparent form. It readily  
applies to a number of standard mathematical situations such as  
finitely presented groups.

For example, the nontriviality of any given finitely presented group  
is equivalent to a Pi01 sentence, as a consequence of these general  
considerations. Of course, in this particular case, we can directly  
use the usual group manipulations to obtain a Pi01 form.

These considerations also apply to the Greedy Clique Upper Shift  
Theorem and the Exotic Greedy Clique Embedding Theorem. For the  
former, we can work in the space (Q,<,+1), and obtain a non  
Archimedean form using predicate calculus. But then we can cut back to  
the Archimedean part, so that 0 in A contained in Q.

Similarly, for the Exotic Greedy Clique Embedding Theorem, we use  
constants for each element of N, obtaining a non Archimedean form  
using predicate calculus. But then we can cut back to the Archimedean  
part so that N contained in A contained in Q.

6. Finite Games.

Let G be any graph. and 1 <= alpha <= infinity. We can associate a  
game G[alpha] to G as follows.

There are two players, Alice and Bob. They alternately move, with  
Alice playing the first move. They each make a total of alpha moves.

Every move by either player is a vertex of G. Alice can play any  
vertex v on any move. Bob must respond with a vertex w which is not  
connected to v.

To comnplete the definition of G[n], we say that Bob wins the game if  
and only if the set of all of his moves forms a G clique.

It is easy to see that Bob wins G[alpha] by the following easy  
argument. Bob first chooses a maximal clique S for G. When Alice plays  
a vertex v, Bob looks up whether v in S. If v in S then Bob copies v.  
If v not in S then Bob plays some w in S which is not connected to v.

Now let G be a graph on [-1,1]^k intersect Q^k, and 1 <= alpha <=  
infinity. We let G[alpha]* be the following modified game. Alice and  
Bob alternately move, with Alice playing the first move. They each  
make a total of alpha moves.

Bob wins if and only if the set of all of his moves, together with the  
upper splits of his moves that have no zero coordinates, forms a G  
clique.

INFINITE UPPER SPLIT GAME THEOREM. For every order invariant graph G  
on [-1,1]^k intersect Q^k, Bob wins the game G[infinity]*.

FINITE UPPER SPLIT GAME THEOREM. For every order invariant graph G on  
[-1,1]^k intersect Q^k and n >= 1, Bob wins the game G[n]*.

We let G[n]** be the same as G[n]*, except that for all 1 <= i <= n,  
Alice's i-th move uses only numerators and denominators of magnitude  
at most (8ki)!!, and Bob's i-th move uses only numerators and  
denominators of magnitude at most (16ki)!!.

ESTIMATED UPPER SPLIT GAME THEOREM. For every order invariant graph G  
on [-1,1]^k intersect Q^k and n >= 1, Bob wins the game G[n]**.

Here we use a very crude but safe estimate. We expect to give more  
refined estaimates in the future.
THEOREM 6.1. IUSGT is provably equivalent, over WKL_0, to Con(SRP). It  
is provable in SRP+ but not in any consistent fragment of SRP that  
logically implies RCA_0.

THEOREM 6.2. FUSGT, EUSGT are provably equivalent, over EFA, to  
Con(SRP). Both are provable in SRP+ but not in any consistent  
fragement of SRP that logically implies EFA.

Note that FUSGT can be seen to be immediately equivalent to an  
effectively given set of sentences in the structure (Q,Z,+1,<). Using  
the well known decision procedure for this structure, we see that  
FUSGT is provably equivalent to a Pi01 sentence over EFA.

Also note that EUSGT is explicitly Pi01.

7. Templates.

The Maximal Clique Upper Split Theorem and the Maximal Clique  
Embedding Theorems suggest

a structure theory for maximal cliques in

order invariant graphs on the rationals.

and the more specialized

structure theory of embeddings

of maximal cliques in

order invariant graphs on the rationals.

The Maximal Clique Upper Split Theorem is based on a rather specific  
partial rational piecewise linear function from Q into Q. This  
suggests the following Template.

For parital h:Q into Q and S contained in Q^k, we take the image of S  
under h to be

{(h(x_1),...,h(x_k)): (x_1,...,x_k) in S}.

FIRST TEMPLATE. Let h:Q into Q be a partial rational piecewise linear  
function. Every order invariant graph on [-1,1]^k intersect Q^k has a  
maximal clique containing its image under h.

Note that the Maximal Clique Upper Split Theorem is an instance of the  
First Template, where

h(q) = q if q < 0; undefined if q = 0; q/2 if q > 0.

CONJECTURE. Every instance of the First Template is provable or  
refutable in SRP+, or perhaps in SMAH+.

We say that h:Q into Q moves q if and only if h(q) ≠ q. This implies  
that q in dom(h).

FIRST TEMPLATE SUFFICIENCY THEOREM. The First Template holds for all h  
with strictly positive first derivative, which moves no negative  
rationals.

THEOREM 7.1. The First Template Sufficiency Theorem is provably  
equivalent, over WKL_0, to Con(SMAH). It is provable in SMAH+ but not  
in any consistent fragment of SMAH that logically implies RCA_0.

We now consider the Maximal Clique Embedding/Injection Theorems 1,2.  
These come under the following Template.

SECOND TEMPLATE. Let phi be a first order property of functions f: 
[0,1] intersect Q into [0,1] intersect Q. In every order invariant  
graph on [0,1]^k intersect Q^k, some maximal clique has an embedding  
(injection) obeying phi.

Here the first order properties apply to the relational system ([0,1]  
intersect Q,<,f).

Note that MCET4-5, MCIT4,5 are instances of the Second Template.

CONJECTURE. Every instance of the Second Template is provable or  
refutable in SRP+.

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

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