[FOM] 457: Maximal Cliques and Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
Thu May 5 03:40:31 EDT 2011
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
More information about the FOM
mailing list