[FOM] 463: Pi01 independence/comprehensive
Harvey Friedman
friedman at math.ohio-state.edu
Fri May 20 21:39:49 EDT 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
OBSOLETES ALL EARLIER POSTINGS ON MAXIMAL CLIQUES
*****************************************
The last comprehensive statement of the Pi01 independent statements is http://www.cs.nyu.edu/pipermail/fom/2011-May/015381.html
Since then, there have been improvements in notation, and various
simplifications in the finite constructions and finite games. These
have continued.
In particular, there is a MAJOR SIMPLIFICATION in the Sequential
Constructions in section 5, giving very much IMPROVED explicitly Pi01
sentences.
The Finite Sequential Construction does require the use of an obvious
norm on rational [-1,1]^k. The Finite Games (main version) does not
use the norm. Therefore it is important to keep both formulations. We
can think of these as a Solitaire Game and a Two Person Game,
respectively.
#I want remind you that I am committed to having a manuscript for
publication by the end of the calendar year. That that will be the
moment of truth whether the complicated proofs are correct.#
**********************************************
MAXIMAL CLIQUES AND LARGE CARDINALS
by
Harvey M. Friedman
May 20, 2011
1. Graphs, Cliques, and Order Invariance.
2. Maximal Clique Split Theorem.
3. Maximal Clique Embedding Theorems.
4. Greedy Cliques and Huge Cardinals.
5. Sequential Constructions.
6. Maximal Clique Embedding/Injection and Predicate Calculus.
7. Finite Games.
8. Templates.
9. Variants.
1. Graphs, Cliques, and Order Invariance.
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.
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
THEOREM 1.2. The following is provable in RCA_0. Every countable graph
has a maximal clique.
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.
Here is a background theorem to orient the reader.
THEOREM 1.3. Let A be a subset of Q and k >= 1. There are finitely
many order invariant subsets of A^k. The order invariant subsets of A
are the empty set and A. The following are equivalent.
i. Some singleton from A^k is an order invariant subset of A^k.
ii. A has at most k elements.
Here is how order invariant subsets of A fit into the framework of
model theory.
THEOREM 1.4. Let A be a subset of Q. The order invariant subsets of
A^k are the subsets of A^k that are definable in the structure (A,<)
without parameters.
Of particular interest for us is the case A = Q intersect [-1,1]. We
refer to this A as rational [-1,1]. We refer to A^k as rational
[-1,1]^k.
2. Maximal Clique Split Theorem.
Let S contained in Q^k. The split of S is obtained by dividing the
coordinates of vectors in S by 2. Thus the split of {(1,-4/3),(-1,0)}
is {(1/2,-2/3),(-1/2,0)}.
THEOREM 2.1. The following is refutable in RCA_0. Every order
invariant graph on rational [-1,1]^k has a maximal clique containing
its split.
So we need to fix the split.
The upper split of S is the result of dividing the positive
coordinates of vectors in S by 2. Thus the upper split of {(1,-4/3),
(-1,0)} is {(1/2,-4/3),(-1,0)}.
THEOREM 2.2. The following is refutable in RCA_0. Every order
invariant graph on rational [-1,1]^k has a maximal clique containing
its upper split.
Examination shows that the problem is 0. Here is the fix:
The strict upper split of S is the result of dividing the positive
coordinates of vectors in S by 2, and then removing all vectors with
coordinate 0. Thus the strict upper split of {(1,-4/3),(-1,0)} is
{(1/2,-4/3)}.
MAXIMAL CLIQUE SPLIT THEOREM. Every order invariant graph on rational
[-1,1]^k has a maximal clique containing its strict upper split.
THEOREM 2.3. The Maximal Clique Split Theorem is provably equivalent
to Con(SMAH) over WKL_0. The Maximal Clique Split Theorem is provable
in SMAH+ but not in any consistent fragment of SMAH that logically
implies RCA_0.
THe Maximal Clique Split Theorem and the variants in Theorems 2.1,
2.2, 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
rational [0,1]^k has a maximal clique with a nontrivial embedding.
MAXIMAL CLIQUE EMBEDDING THEOREM 2. Every order invariant graph on
rational [0,1]k has a maximal clique with a nontrivial embedding whose
range forms an interval.
MAXIMAL CLIQUE EMBEDDING THEOREM 3. Every order invariant graph on
rational [0,1]^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
rational [0,1]^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
rational [0,1]^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 7.
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 vertex
in 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.
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.1. 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 A^k 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.2. 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.
We first associate an obvious nondeterministic infinite sequential
construction based on The Greedy Clique Split Theorem.
Fix an order invariant graph G on rational [-1,1]^k.
Let us start with any vectors x_1,x_2,... in rational [-1,1]^k. In the
G,x_1,x_2,... construction, each term x_i is replaced by some y such
that (x,y) is not an edge in G.
INFINITE CONSTRUCTION THEOREM. Let G be an order invariant graph on
rational [-1,1]^k, and x_1,x_2,... lie in rational [-1,1]^k. The
G,x_1,x_2,... construction can be carried out so that the resulting
vectors form a clique in G.
INFINITE SPLIT CONSTRUCTION THEOREM. Let G be an order invariant graph
on rational [-1,1]^k, and x_1,x_2,... lie in rational [-1,1]^k. The
G,x_1,x_2,... construction can be carried out so that the resulting
vectors, together with their strict upper shifts, form a clique in G.
THEOREM 5.1. The Infinite Construction Theorem is provable in RCA_0.
The Infinite Split Construction Theorem 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.
We now consider the G,x_1,...,x_n construction, where x_1,...,x_n lie
in rational [-1,1]^k.
FINITE SPLIT CONSTRUCTION THEOREM. Let G be an order invariant graph
on rational [=1,1]^k, and x_1,...,x_n lie in rational [-1,1]^k. The
G,x_1,...,x_n construction can be carried out so that the resulting
vectors, together with their strict upper shifts, form a clique in G.
THEOREM 5.2. The Finite Split Construction Theorem is provable in RCA_0.
In the normed G,x_1,...,x_n construction, every x_i replaced by some
y, where (x,y) is not an edge in G, and the norm of y is at most 8k
times the norm of x_i.
NORMED FINITE SPLIT CONSTRUCTION THEOREM. Let G be an order invariant
graph on rational [=1,1]^k, and x_1,...,x_n lie in rational [-1,1]^k.
The normed G,x_1,...,x_n construction can be carried out so that the
resulting vectors, together with their strict upper splits, form a
clique in G.
THEOREM 5.3. The Normed Finite Split Construction Theorem 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.
Note that The Normed Finite Split Construction Theorem is explicitly
Pi01.
6. Maximal Clique Embedding/Injection and Predicate Calculus.
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 WKL_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.
7. 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 such that (v,w)
is not an edge in G.
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 such that (v,w) is not an
edge in G.
Now let G be an order invariant graph on rational [-1,1]^k, and 1 <=
alpha <= infinity. We let G[alpha]* be the same as the game G[alpha],
except that Bob is considered to be the winner if and only if Bob's
moves, together with their strict upper splits, form a clique in G.
INFINITE SPLIT GAME THEOREM. For every order invariant graph G on
rational [-1,1]^k, Bob wins the game G[infinity]*.
FINITE SPLIT GAME THEOREM. For every order invariant graph G on
rational [-1,1]^k, and n >= 1, Bob wins the game G[n]*.
Note that the FInite Split Game Theorem is implicitly (as opposed to
explicitly) Pi01 by the following argument. For any given G,n, the
existence of a winning strategy for Bob is equivalent to a first order
sentence in Presburger Arithmetic (with 2n quantifiers). Then apply
the usual decision procedure for Presburger Arithmetic.
We let G[n]** be the same as G[n]*, except that for all 1 <= i <= n,
Alice's i-th move is required to use only numerators and denominators
of magnitude at most (8k)^2i-1, and Bob's i-th move is required to use
only numerators and denominators of magnitude at most (8k)^2i.
ESTIMATED UPPER SPLIT GAME THEOREM. For every order invariant graph on
rational [-1,1]^k and n >= 1, Bob wins the game G[n]**.
Note that The Estimated FInite Split Game Theorem is explicitly Pi01.
THEOREM 7.1. The Infinite Split Game 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.
THEOREM 7.2. The Finite Split Game THeorem, and The Estimated Split
Game Theorem 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.
8. 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 Split Theorem is based on a rather specific partial
rational piecewise linear function from Q into Q. This suggests the
following Template.
Let h:Q into Q be partial and S contained in Q^k. We say that S is h
closed if and only if for all (x_1,...,x_k) in S intersect dom(h)^k,
(h(x_1),...,h(x_k)) is in S.
FIRST TEMPLATE. Let E be a finite union of rational intervals in Q
with extended rational endpoints. Let h:Q into Q be a partial rational
piecewise linear function. Every order invariant graph on E^k has an h
closed maximal clique.
Note that the Maximal Clique Upper Split Theorem is an instance of the
First Template, where
E = rational [-1,1].
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 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 from
rational [0,1] into itself. In every order invariant graph on rational
[0,1]^k, some maximal clique has an embedding (injection) obeying phi.
Here the first order properties apply to the relational system (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+.
9. Variants.
In sections 5 and 7, we used "the vectors together with their strict
upper splits form a clique in G".
We can instead incorporate the strict upper splits (when they exist)
in the statements themselves. When we do this, we need only say that
"the vectors form a clique in G".
If we follow this plan, we obtain precisely the same results. I.e.,
equivalence with Con(SMAH).
For definiteness, here are the variants spelled out.
Fix an order invariant graph G on rational [-1,1]^k.
We use sus(y) for the strict upper split of y, which may be undefined.
The expression y,sus(y) is taken to be y if sus(y) is undefined.
In the modified normed G,x_1,...,x_n construction, every x_i replaced
by some y,sus(y) where the norm of y is at most 8k times the norm of
x_i.
In the modified game G[n]#, Alice plays x in [-1,1]^k, and Bob must
respond with some y,sus(y), where (x,y) is not an edge in G.
We let G[n]## be the same as G[n]#, except that for all 1 <= i <= n,
Alice's i-th move is required to use only numerators and denominators
of magnitude at most (8k)^2i-1, and Bob's i-th move is required to use
only numerators and denominators of magnitude at most (8k)^2i.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 463rd 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
Harvey Friedman
More information about the FOM
mailing list