[FOM] 468: Maximal Cliques/Incompleteness
Harvey Friedman
friedman at math.ohio-state.edu
Tue Jul 26 14:39:40 EDT 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
1. PRIOR STATEMENTS - RAN INTO TROUBLE.
2. NEW STATEMENTS - MAXIMAL CLIQUE SHIFT THEOREM.
1. PRIOR STATEMENTS - RAN INTO TROUBLE.
I had been putting together a detailed manuscript on these statements:
MAXIMAL CLIQUE SPLIT THEOREM (1). In every order invariant graph on
Q[-1,1]^k, without 0, some maximal clique contains its upper split.
MAXIMAL CLIQUE SPLIT THEOREM (2). In every order invariant graph on
Q[-1,1]^k, some maximal clique contains its upper split without 0.
These are just the earlier statements I have been writing about,
except that now I use improved terminology. Here Q[-1,1] is the
interval [-1,1] in the rationals. For S contained in Q^k, S without 0
is S with the elements that have coordinate 0 removed. The upper split
of S is obtained by dividing all positive coordinates of S by 2. (The
former strict upper split now becomes the upper split without 0).
I ran into a serious problem. We still claim a proof of the above from
large cardinals. However, there is a serious problem with the
reversal. I'm not sure how to get past this problem.
The good news is that I have new statements that are in fact better in
some respects!
2. NEW STATEMENTS - MAXIMAL CLIQUE SHIFT THEOREM.
Details are below.
MAXIMAL CLIQUE SHIFT THEOREM (informal). In every order invariant
graph on Q[0,n]^k, some maximal clique has various symmetry properties.
MAXIMAL CLIQUE SHIFT THEOREM. In every order invariant graph on
Q[0,n]^k, some maximal clique is preserved by the upper {1,...,n-1}
shift.
Note that the above equivalent of Con(SRP) is obviously Pi01 since it
expresses the existence of a countable model of predicate calculus
through simple predicate calculus manipulations.
I do have a proof of the following from Con(SRP), but I don't know if
it is provable in ZFC:
MAXIMAL CLIQUE SHIFT THEOREM (Q). In every order invariant graph on
Q^k, some maximal clique is preserved by the upper N shift.
Also there is a particularly simple Pi01 form of the Maximal Clique
Shift Theorem - which is phrased in terms of Dominators.
I have been developing a good detailed draft, and things seem correct
thus far.
I now have an update from Steve Hedetniemi concerning the level of
activity in dominators on graphs. He is doing a bibliography, and
expects there are now over 3000 papers on domination in graphs. He
also reports that if we include some very closely related topics in
graphs, then the number is considerably higher.
MAXIMAL CLIQUES AND INCOMPLETENESS
by
Harvey M. Friedman
July 25, 2011
1. Graphs, cliques, order invariance, shifts, preservation.
2. Maximal Clique Shift Theorem.
3. Dominators, local dominators.
4. Finite Dominator Shift Theorems.
5. Templates.
1. GRAPHS, CLIQUES, ORDER INVARIANCE, SHIFTS, PRESERVATION.
A (simple) graph is a pair G = (V,E), where V is a set and E is an
irreflexive symmetric binary relation on V - viewed as a subset of V^2.
The vertices of G are the elements of V = V(G). The edges of G are the
elements of E = E(G).
We say that x,y are adjacent (in G) if and only if x E y.
A clique is a subset of V, any two distinct elements of which are
adjacent.
A maximal clique is a clique which is not a proper subset of a clique.
The following is well known.
THEOREM 1.1. Every graph has a maximal clique. This is provable in EFA
for finite graphs, and RCA_0 for countable graphs.
We use Q for the set of all rationals, with its usual ordering. We use
Q* for the set of all nonempty finite sequences from Q.
We write Q[a,b] for the set of rationals in the closed interval [a,b].
We say that x,y in Q^k are order equivalent if and only if for all 1
<= i,j <= k, x_i < x_j iff y_i < y_j.
We say that S is order invariant in V contained in Q^k if and only if
for all order equivalent x,y in V, x in S iff y in S.
Note that for each V contained in Q^k, there are only finitely many
order invariant S in V.
We say that a graph G is order invariant on V contained in Q^k if and
only if V(G) = V, and E(G) is order invariant in V^2. Again, for each
V contained in Q^k, there are only finitely many order invariant
graphs on V.
The shift maps Q* by Q* by adding 1 to all coordinates.
Restricted shifts play a crucial role in this paper. In restricted
shifts, we add 1 only to some coordinates.
Fix A contained in Q. The A shift maps Q* into Q* by adding 1 to all
coordinates from A.
The upper A shift maps Q* into Q* by adding 1 to all coordinates from
A, such that all greater coordinates are from A.
We say that a set S is preserved by a function f if and only if for
all x in dom(f), x in S iff f(x) in S.
2. MAXIMAL CLIQUE SHIFT THEOREM.
We use k,n,m,r,s,t for nonnegative integers, and p,q for rationals.
Cartesian exponents are always positive integers.
MAXIMAL CLIQUE SHIFT THEOREM (informal). In any order invariant graph
on Q[0,n]^k, some maximal clique has various symmetry properties.
MAXIMAL CLIQUE SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some maximal clique is preserved by the upper {1,...,n-1}
shift.
In this paper, we will prove the following result.
THEOREM 2.1. The Maximal Clique Shift Theorem is provable in SRP+ but
not in any consistent fragment of SRP that proves RCA_0. The Maximal
Clique Shift Theorem is provably equivalent to Con(SRP) over ACA_0.
Note that by Theorem 2.1, the Maximal Clique Shift Theorem is provably
equivalent to a Pi01 sentence over ACA_0. Using the well known
representation of P01 sentences by Diophantine equations given by the
solution to Hilbert's Tenth Problem, we obtain the following.
THEOREM 2.2. There is a polynomial P with integer coefficients such
that the following is provable in ACA_0. The Maximal Clique Shift
Theorem holds if and only if P has an integral zero.
We can derive very strong metamathematical conclusions from Theorem
2.2, within ACA_0, concerning the Maximal Clique Shift Theorem, such as
a. The truth value of the Maximal Clique Shift Theorem is the same for
all models of ZFC (or even ACA_0) with standard integers.
b. If the Maximal Clique Shift Theorem fails, then it can be refuted
in ACA_0.
There is no way at present of constructing any kind of remotely
reasonable polynomial P for Theorem 2.2.
Thus the question remains as to whether we can give an intelligible
explicitly Pi01 form of the Maximal Clique Shift Theorem. This is
achieved in section 4 in a clear way, by switching to dominators and
using a standard norm on Q^k.
However, by simple considerations from mathematical logic, it is clear
that the Maximal Clique Shift Theorem is Pi01 *in virtue of its
logical form*.
Specifically, It is a simple exercise to see that for each k,n >= 1,
and order invariant graph G on Q[0,n]^k, the Maximal Clique Shift
Theorem asserts the existence of a countable model of a sentence
sigma(k,n,G) in first order predicate calculus with equality,
effectively constructed from k,n,G. Hence by Goedel's completeness
theorem, the Maximal Clique Shift Theorem is provably equivalent, over
WKL_0, to the formal consistency of sigma(k,n,G). Therefore the
Maximal Clique Shift Theorem is provably equivalent, over WKL_0, to a
Pi01 sentence - in virtue of its logical form.
THEOREM 2.3. There exists k,n such that the Maximal Clique Shift
Theorem for k,n is provable in SRP but not in ZFC. The Maximal Clique
Shift Theorem for the various fixed k,n form an axiomatization of
{Con(k-SRP): k >= 1} over ACA_0.
For Theorem 2.3, we believe that k,n can be taken to be remarkably
small, but we have not gone into this in detail.
3. DOMINATORS, CONTROLLED DOMINATORS.
Let G be a graph. A dominator is an S contained in V(G) such that
every element of V(G)\S is adjacent to an element of S.
We say that S contained in V(G) is independent if and only if no two
elements of S are adjacent.
A maximal independent set is an independent set which is not a proper
subset of an independent set.
An independent dominator is a dominator which is an independent set.
A minimal dominator is a dominator where no proper subset is a
dominator.
THEOREM 3.1. The maximal cliques (maximal independent sets) in G are
the same as the maximal independent sets (maximal cliques) in
(V,V^2\E). The maximal independent sets are the same as the
independent dominators. Every independent dominator is a minimal
dominator. There is a finite graph with a minimal dominator that is
not an independent dominator. These results are provable in EFA for
finite graphs, and RCA_0 for countable graphs.
Thus we have the following variants:
MAXIMAL CLIQUE SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some maximal clique is preserved by the upper {1,...,n-1}
shift.
MAXIMAL INDEPENDENT SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some maximal independent set is preserved by the upper
{1,...,n-1} shift.
INDEPENDENT DOMINATOR SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some independent dominator is preserved by the upper
{1,...,n-1} shift.
MINIMAL DOMINATOR SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some minimal dominator is preserved by the upper {1,...,n-1}
shift.
It is obvious from Theorem 3.1 that the first three of these are
provably equivalent in RCA_0, and thus share the relevant
metamathematical properties. Also, the Minimal Dominator Shift Theorem
is provable in SRP+. We have not attempted to determine the status of
the Minimal Dominator Shift Theorem.
We now make use of a natural norm. For q in Q, let ||q|| be the least
integer r such that q is the ratio of two integers of magnitude at
most r.
For x in Q^k, let ||x|| = ||x_1|| + ... + ||x_k||. For S contained in
Q^k, ||S|| is the max of the ||x||, x in S. If S is infinite, ||S|| =
infinity.
The norm of a subset of Q^k is the max of the norms of its elements
(infinity if the set is infinite).
Let G be a graph on Q^k. We say that S is a controlled dominator if
and only if every x in Q^k\S is adjacent to some y in S of norm at
most 8||x||^2. (There is a lot of flexibility in what estimate we can
use here. We have not gone into this is detail).
We say that S is a dominator of E if and only if every element of E\S
is adjacent to an element of S. Thus S is a dominator if and only if S
is a dominator on V(G).
We say that S is a controlled dominator of E if and only if every x in
E\S is adjacent to some y in S of norm at most 8||x||^2.
4. FINITE DOMINATOR THEOREMS.
FINITE DOMINATOR SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, every finite set of vertices has a finite independent
controlled dominator, which is preserved by the upper {1,...,n-1} shift.
EXPLICIT DOMINATOR SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, the set of vertices of norm at most n has an independent
controlled dominator of norm at most 16n^2, which is preserved by the
upper {1,...,n-1} shift.
The Finite Dominator Shift Theorem is Pi02, and the Explicit Dominator
Shift Theorem is Pi01. They are easily seen to be provably equivalent
in EFA.
THEOREM 4.1. The Finite Dominator Shift Theorem and the Explicit
Dominator Shift Theorem are provable in SRP+ but not in any consistent
fragment of SRP that proves EFA. The Finite Dominator Shift Theorem
and the Explicit Dominator Shift Theorem are provably equivalent to
Con(SRP) over EFA.
5. TEMPLATES.
We work with the
MAXIMAL CLIQUE SHIFT THEOREM. In any order invariant graph on
Q[0,n]^k, some maximal clique is preserved by the {1,...,n-1} shift.
Note that the upper {0,...,n-1} shift on Q[0,n]^k is a relatively
order theoretic function from Q[0,n]^k into Q[0,n]^k. I.e., the graph
of the function is an order invariant subset of Q[0,n]^2k relative to
finitely many parameters from Q[0,n] (in this case, parameters
1,...,n-1). This is equivalent to asserting that the function is
definable in (Q,<) with parameters.
TEMPLATE I. Let k,n >= 1 and h be a relatively order theoretic
function from Q[0,n]^k into Q[0,n]^k. In every order invariant graph
on Q[0,n]^k, some maximal clique is preserved by h.
TEMPLATE II. Let k,n >= 1, and h be a rational piecewise translation
from Q[0,n]^k into Q[0,n]^k. In every order invariant graph on
Q[0,n]^k, some maximal clique is preserved by h.
TEMPLATE III. Let k,n >= 1, and h be a rational piecewise linear
function from Q[0,n]^k into Q[0,n]^k. In every order invariant graph
on Q[0,n]^k, some maximal clique is preserved by h.
Preservation by relatively order theoretic functions form Pi01
sentences in (Q,<,S) with parameters, where S contained in Q[0,n]^k
represents the maximal clique.
Preservation by rational piecewise translations based on the shift
form Pi01 sentences in (Q,+1,<,S) with parameters.
Preservation by rational piecewise linear functions form Pi01
sentences in (Q,+,<,S) with parameters.
TEMPLATE IV. Let k >= 1 and phi be a Pi01 sentence in (Q[0,n],<,S)
with parameters. In every order invariant graph on Q[0,n]^k, some
maximal clique S has phi.
TEMPLATE V. Let k >= 1 and phi be a Pi01 sentence in (Q[0,n],+1,<,S)
with parameters. In every order invariant graph on Q[0,n]^k, some
maximal clique S has phi.
TEMPLATE VI. Let k >= 1 and phi be a Pi01 sentence in (Q[0,n],+,<,S)
with parameters. In every order invariant graph on Q[0,n]^k, some
maximal clique S has phi.
GENERIC ASSERTIONS. Every instance of Template T is provable or
refutable in SRP+. Every instance of Template T is either provable in
ACA_0 + Con(SRP) or refutable in RCA_0. The dichotomy is testable in
polynomial time. We cannot replace SRP+ with SRP.
The last claim in Generic Assertions follows from Theorem 2.3 for all
six Templates.
We conjecture that the Generic Assertions hold for Templates I,II,IV,
and V.
With some care, we can also develop Templates for the Maximal Clique
Shift Theorem with k treated as a variable. Here we can treat shift
operators from Q* into Q* by quantifying over coordinates.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 468th 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
Harvey Friedman
More information about the FOM
mailing list