[FOM] 451: Rational Graphs and Large Cardinals I
Harvey Friedman
friedman at math.ohio-state.edu
Sat Dec 18 22:53:27 EST 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS SELF CONTAINED.
We review the closely related maximal set constructions being used.
These now include maximal cliques, greedy cliques, and kernels.
We use the greedy clique notion as the basis for the Sequential Clique
Construction - which provides explicitly Pi01 independence results.
We outline major new projects for consolidation - this appears in
sections 7,8.
Finally, we discuss using functions, other than the Upper Shift,
throughout - in section 9.
In a later posting, we expect to polish up the Pi01 independent
statements at the level of HUGE.
*****************************************
RATIONAL GRAPHS AND LARGE CARDINALS
by
Harvey M. Friedman
December 18, 2010
1. Graphs and Cliques.
2. A-graphs and the Upper Shift.
3. Upper Shift Clique Theorems.
4. Digraphs, Kernels, and A-digraphs.
5. Upper Shift Kernel Theorem.
6. Sequential Clique Construction Theorems.
7. Clique Conditions.
8. Set Conditions.
9. Piecewise Linear.
1. GRAPHS AND CLIQUES.
A graph is a pair (V,E), where V is a set of vertices, and E is a set
of edges, where each edge is a subset of V of cardinality 2. We say
that x,y are adjacent if and only if {x,y} is an edge.
We say that the graph G restricts to the graph H if and only if H is
an induced subgraph of G. I.e., every vertex of H is a vertex of G,
and any two vertices of H are adjacent in H if and only they are
adjacent in G.
A clique in a graph is a set of vertices, where any two distinct
elements are adjacent.
A maximal clique is a clique, where for every vertex x outside the
clique there is a vertex y inside the clique such that x,y are not
adjacent.
A rational graph is a graph whose vertex set is a subset of some Q^k.
Here Q is the set of all rational numbers.
A greedy clique is a clique, where for every vertex x outside the
clique there is a vertex y insider the clique such that x,y are not
adjacent and max(y) <= max(x).
THEOREM 1.1. Every graph has a maximal clique. Every finite rational
graph has a greedy clique. Some rational graphs have no greedy clique.
2. A-GRAPHS AND THE UPPER SHIFT.
Let A be a subset of Q. The A-graphs are the graphs (A^k,E), where E
is order invariant. I.e., if (x,y) and (x',y') are order equivalent as
elements of A^2k, then {x,y} in E if and only if {x',y'} in E.
Note that for a given A, there are only finitely many A-graphs with
vertex dimension k.
The upper shift of x in Q^k is obtained by adding 1 to its nonnegative
coordinates. The upper shift of S contained in Q^k is the set of upper
shifts of its elements.
3. UPPER SHIFT CLIQUE THEOREMS.
UPPER SHIFT MAXIMAL CLIQUE THEOREM. Every Q-graph restricts to some A-
graph, 0 in A, with a maximal clique containing its upper shift.
UPPER SHIFT GREEDY CLIQUE THEOREM. Every Q-graph restricts to some A-
graph, 0 in A, with a greedy clique containing its upper shift.
UNIFORM UPPER SHIFT MAXIMAL CLIQUE THEOREM. There exists 0 in A
contained in Q, where every A-graph has a maximal clique containing
its upper shift.
UNIFORM UPPER SHIFT GREEDY CLIQUE THEOREM. There exists 0 in A
contained in Q, where every A-graph has a greedy clique containing its
upper shift.
Since every A-graph is the restriction of a Q-graph, the Uniform Upper
Shift Maximal (Greedy) Clique Theorem immediately implies the Upper
Shift Maximal (Greedy) Clique Theorem.
We do know that it is necessary and sufficient to use large cardinals
in order to prove the Upper Shift Greedy Clique Theorem and the
Uniform Upper Shift Greedy Clique Theorem.
Specifically, let SRP+ = ZFC + "for all k, there is a limit ordinal
with the k-SRP". SRP = ZFC + {there is a limit ordinal with the k-
SRP}_k. The k-SRP asserts that every 2 coloring of the unordered k-
tuples has a stationary monochromatic set.
THEOREM 3.1. SRP+ proves all four Theorems above. The two Greedy
Theorems are provably equivalent to Con(SRP) over WKL_0.
The only proof we know of the Upper Shift Maximal Clique Theorem also
proves the Upper Shift Greedy Clique Theorem, and therefore uses large
cardinals. We don't know if it can be proved in ZFC, or even in RCA_0.
The same remark applies to the Uniform Theorems.
4. DIGRAPHS, KERNELS, AND A-DIGRAPHS.
A digraph is a pair (V,E), where V is a set of vertices, and E is a
set of edges, where each edge is an ordered pair from V.
We say that the digraph G restricts to the digraph H if and only if H
is an induced subgraph of G. I.e., if x,y are vertices of H, then
(x,y) is an edge of H if and only if (x,y) is an edge of G.
A kernel in a digraph (V,E) is an S contained in V such that
i. There is no edge from any x in S to any y in S.
ii. For all x in V\S there is an edge from x to some y in S.
A rational digraph is a digraph whose vertices are rationals. A
downward rational digraph is a rational digraph such that if (x,y) is
an edge then max(x) > max(y).
A rational digraph is downward if and only if for any edge (x,y),
max(x) > max(y).
Let A be a subset of Q. The A-digraphs are the digraphs (A^k,E), where
E is order invariant. I.e., if x,y are order equivalent as elements of
A^2k, then x in E if and only if y in E.
Note that for a given A, there are only finitely many A-digraphs with
vertex dimension k.
5. UPPER SHIFT KERNEL THEOREMS.
UPPER SHIFT KERNEL THEOREM. Every downward Q-digraph restricts to some
A-digraph, 0 in A, with a kernel containing its upper shift.
UNIFORM UPPER SHIFT KERNEL THEOREM. There exists 0 in A contained in
Q, where every downward A-digraph has a kernel containing its upper
shift.
THEOREM 5.1. SRP+ proves The Upper Shift Kernel Theorem. It is
provably equivalent to Con(SRP) over WKL_0.
6. SEQUENTIAL CLIQUE CONSTRUCTION THEOREMS.
The Sequential Clique Construction Theorem is a sequential
construction form of the Upper Shift Greedy Clique Theorem.
Let x_1,...,x_p be in Q^k. We write #(x_1,...,x_p) for the least set
V^k such that x_1,...,x_p are in V^k.
Let (Q^k,E) be a Q-graph. Let x_1,...,x_p be a clique, where p >= 0.
We say that x_1,...,x_p decides y in Q^k if and only if
i. y is among x_1,...,x_p; or
ii. there is some x_i with max(x_i) <= max(y) such that x_i,y are not
adjacent.
Note that if i) holds then y is in any clique extending x_1,...,x_p,
and if ii) holds then y is not in any clique extending x_1,...,x_p.
We say that x_1,...,x_p is ready for y in Q^k if and only if there
exists i such that
i. x_1,...,x_p decides every element of #(x_1,...,x_i).
ii. y is in #(x_1,...,x_i+1).
iii. x_1,...,x_p does not decide y.
An infinite E construction is an infinite E clique
x_1,ush(x_1),x_2,ush(x_2),... such that
i. x_1 decides the origin.
ii. For all i >= 2, x_1,ush(x_1),...,x_i decides some y that
x_1,ush(x_1),...,x_i-1,ush(x_i-1) is ready for.
A finite E construction is a finite E clique
x_1,ush(x_1),...,x_p,ush(x_p) such that
i. x_1 decides the origin.
ii. For all 2 <= i <= p, x_1,ush(x_1),...,x_i decides some y that
x_1,ush(x_1),...,x_i-1,ush(x_i-1) is ready for.
INFINITE SEQUENTIAL UPPER SHIFT GREEDY CLIQUE THEOREM. For all Q-
graphs (Q^k,E), there is an infinite E construction.
FINITE SEQUENTIAL UPPER SHIFT GREEDY CLIQUE THEOREM. For all Q-graphs
(Q^k,E), there is an E construction of any given finite length.
Note that FSUSGCT is explicitly Pi02. However, by a small fragment of
the decision procedure for Presburger arithmetic, FSUSGCT is Pi01. In
fact, we can bound the heights of the rationals involved. The height
of a rational is the max of the absolute values of its denominator and
numerator when put in reduced form.
FINITE SEQUENTIAL UPPER SHIFT GREEDY CLIQUE THEOREM. For all Q-graphs
(Q^k,E) and positive integers n, there is an E construction of length
n using only rationals of height at most (8kn)!.
THEOREM 6.1. ISUSGCT is provably equivalent to Con(SRP) over WKL_0.
FSUSGCT is provably equivalent to Con(SRP) over EFA.
7. CLIQUE CONDITIONS.
We have been using cliques that are maximal, and cliques that are
greedy. These are conditions on cliques. They are both AE conditions
on cliques:
(forall x in A^k)(therexists y in A^k)(x not in S implies (y in S and
not (x connected to y)).
(forall x in A^k)(therexists y in A^k)(x not in S implies (y in S and
max(y) <= max(x) and not (x connected to y)).
We can consider all conditions that take the following form:
*) (forall x in A^k)(therexists y in A^k)(phi(x,y))
where phi(x,y) is a propositional combination of formulas of the form
i. x = y.
ii. max(x) < max(y).
iii. max(y) < max(x).
iv. x in S.
v. y in S.
vi. x,y are connected.
We expect to be able to completely analyze the following templates:
TEMPLATE. Let phi(x,y) be as above, and let clique* be the
corresponding notion of clique according to *). Every Q-relation
restricts to some A-relation, 0 in Q, with a clique* containing its
upper shift.
TEMPLATE. Let phi(x,y) be as above, and let clique* be the
corresponding notion of clique according to *). There exists 0 in A
contained in Q, where every A-relation has a clique* containing its
upper shift.
Obviously, the Upper Shift Maximal Clique Theorem, the Upper Shift
Greedy Clique Theorem, the Uniform Upper Shift Maximal Clique Theorem,
and the Uniform Upper Shift Greedy Clique Theorem, are specific
instances of these two Templates.
These Templates obviously have only finitely many instances, and we
expect to be able to determine the metamathematical status of each
instance.
8. SET CONDITIONS.
The notion of clique itself is a condition with two universal
quantifiers. So we can create richer Templates without assuming that S
is a clique.
For these richer Templates, it is best to use digraphs. We can
consider conjunctions
(forall x,y in A^k)(phi(x,y)) and (forall x in A^k)(therexists y in
A^k)(psi(x,y))
where phi(x,y), psi(x,y) are propositional formulas as before, using
"(s,t) is an edge", s,t among x,y, for clause vi).
More ambitiously, we can consider
(forall x,y in A^k)(therexists z in A^k)(rho(x,y,z))
where rho is a quantifier free formula in variables x,y,z, using
membership in S, comparing max of variables, and the edge set E as a
binary relation.
Analyzing these Templates will be considerably more difficult that
those in section 7, but I think this is a workable multiyear project.
9. PIECEWISE LINEAR.
We have lifted the upper shift ush:Q into Q given by
ush(q) = q+1 if q >= 0; q otherwise
to higher dimensions. We can consider all statements here and
templates as well, with ush replaced by any given finite list of
partial piecewise linear functions from Q into Q with rational
coefficients.
We seek to determine the status of each such replacement. We expect
that this is also amenable to complete analysis. We also expect that
the large cardinals involved will be the same.
For the statements in sections 3,5,6, we expect that this is a
workable project.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 450th 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
Harvey Friedman
More information about the FOM
mailing list