[FOM] 452: Rational Graphs and Large Cardinals II
Harvey Friedman
friedman at math.ohio-state.edu
Sun Jan 9 01:35:41 EST 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS SELF CONTAINED.
This is a comprehensive statement of the state of the art, with new
aspects covered. Substantial breakthroughs appear throughout.
RATIONAL GRAPHS AND LARGE CARDINALS
by
Harvey M. Friedman
January 4, 2010
1. FIXED POINTS.
2. DERIVED SEQUENCES.
3. DIGRAPHS AND KERNELS.
4. GRAPHS, CLIQUES, AND GREED.
5. HUGE CARDINALS.
6. TEMPLATES.
1. FIXED POINTS.
The fixed point approach leads directly to Concrete Mathematical
Incompleteness with a minimum of definitions. However, in this form,
it doesn't have any clear connection with existing mathematics. The
closely related approaches in sections 3 and 4 do have clear
connections with existing research in combinatorics.
We use Q for the set of all rationals. 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 E contained in Q^k is order invariant if and only if for
all order equivalent x,y in Q^k, x in E if and only if y in E.
We focus on relations R contained in Q^2k, viewed as a binary relation
on Q^k.
For A contained in Q^k, we define the image
RA = {y: (therexists x in A)(R(x,y))}.
We use the upper image
R<A = {y: (therexists x in A)(max(x) < max(y) and R(x,y))}.
Here < appears as a subscript.
We take the subspaces of Q^k to be the sets D^k, where 0 in D
contained in Q.
For A contained in Q^k, we define A# to be the subspace of Q^k
generated by A. I.e., A# is the least subspace of Q^k containing A.
The upper shift of x in Q^k results from adding 1 to all nonnegative
coordinates. The upper shift of A contained in Q^k is the set of upper
shifts of its elements.
We say that lambda has the k-SRP if and only if lambda is a limit
ordinal, where every partition of the unordered k-tuples from lambda
into two pieces has a homogenous set that is stationary in lambda.
(Here SRP stands for "stationary Ramsey property").
SRP+ = ZFC + (for all k)(there exists lambda with the k-SRP). SRP =
ZFC + {there exists lambda with the k-SRP}_k.
UPPER SHIFT FIXED POINT THEOREM. Every order invariant R contained in
Q^2k has an A = A#\R<A contained in Q^k containing its upper shift.
We say that R is strictly dominating if and only if R(x,y) implies
max(x) < max(y). The following is variant is easily seen to be
equivalent.
UPPER SHIFT FIXED POINT THEOREM. Every strictly dominating order
invariant R contained in Q^2k has an A = A#\RA contained in Q^k
containing its upper shift.
THEOREM 1.1. USFPT (both forms) is provable in SRP+. WKL_0 proves that
USFPT (both forms) is equivalent to Con(SRP). It is provable in RCA_0
that if USFPT holds then the A can be chosen to be recursive in 0'.
2. DERIVED SEQUENCES.
We now give an explicitly Pi01 statement equivalent to Con(SRP). It is
closely related to the Upper Shift Fixed Point Theorem.
The setting will be the [-n,n]^k, where k,n are positive integers. We
use discrete intervals only.
We use U. for disjoint union. If two sets are not disjoint, then their
disjoint union is undefined.
Let R contained in [-n,n]^2k and A contained in [-n,n]^k. We define RA
= {y: (therexists x in A)(R(x,y))}, and R<A = {y: (therexists x in A)
(max(x) < max(y) and R(x,y))}.
THEOREM 2.1. For all R contained in [-n,n]^2k there exists a unique A
such that A U. R<A = [-n,n]^k.
Let A be contained in [-n,n]^k. An R-derived sequence for A is a
sequence [-n,n] = D_1 containing ... containing D_m such that for all
1 <= i < m,
D_i+1^k is contained in (A intersect D_i^k) U. R<(A intersect D_i^k).
There are two obvious variants:
D_i+1^k is contained in A U. R<(A intersect D_i^k).
D_i+1^k is contained in (A intersect D_i^k) U. R<A.
The same results below hold for all three variants.
Let t >= 1. The t-upper shift of x in [-n,n]^k is obtained by adding t
to every nonnegative coordinate of x.
The t-upper shift of A contained in [-n,n]^k is the set of t-upper
shifts of elements of A.
The restricted t-upper shift of A consists of the elements of the t-
upper shift of A whose coordinates are at most some coordinate of some
element of A.
We use order invariant E contained in [-n,n]^k, in the sense that for
any order equivalent x,y in [-n,n]^k, x in E iff y in E.
DERIVED SEQUENCE THEOREM. Let t > (8kmp)! > 1. For every order
invariant R contained in [-pt,pt]^2k, some A containing its restricted
t-upper shift has an R-derived sequence of length m ending with
{0,t,...,pt}.
Note that the Derived Sequence Theorem is explicitly Pi01. The (8knp)!
is convenient overkill.
THEOREM 2.2. The Derived Sequence Theorem is provable in SRP+. It is
provably equivalent to Con(SRP) over EFA. These results hold even for
p = k and m = 2.
3. DIGRAPHS AND KERNELS.
A digraph G is a pair (V,E), where V is a set of vertices, and E is a
set of edges. The edges in G are ordered pairs from V. Thus loops are
allowed.
A walk in G is a finite or infinite sequence of vertices where there
is an edge from every term to the next term (if it exists).
A dag (directed acyclic graph) is a digraph in which every walk
consists of distinct vertices.
A kernel in G 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.
The original fundamental theorem on digraph kernels is as follows.
THEOREM 3.1. Every finite dag has a unique kernel. (Von Neumannn and
Morgenstern).
Kernels in digraphs continues to be an active field of combinatorics.
Kernels in (undirected) graphs is yet more active, and the focus is
mainly on finite graphs and digraphs.
Theorem 3.1 has the following expected generalization. Note that a
finite digraph is a dag if and only if it has no infinite walk.
THEOREM 3.2. Every digraph with no infinite walk has a unique kernel.
In the countable case, this is equivalent to ATR_0 over RCA_0. In
fact, the existence part alone is equivalent to ATR_0 over RCA_0.
We use Q for the set of all rational numbers.
A rational digraph is a digraph whose vertex set is contained in some
Q^k, k >= 1. A downward rational digraph is a rational digraph such
that if (x,y) is an edge then max(x) > max(y).
Let A be contained in 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.
We say that (A^k,E) is on k-tuples. Note that for a given A, there are
only finitely many A-digraphs on k-tuples.
THEOREM 3.3. (Q,Q^2) is a Q-digraph with no kernel.
A rational digraph is downward if and only if for any edge (x,y),
max(x) > max(y).
THEOREM 3.4. There is a downward Q-digraph with no kernel. There is a
recursive non well ordered A contained in Q such that every downward A-
digraph has a kernel.
We want to understand the structure of kernels in Q-graphs. Since Q-
graphs may not have kernels, we want to understand the structure of
kernels in A-graphs, A contained in Q.
The upper shift of x in Q^k is the result of adding 1 to each
nonnegative coordinate of x.
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.
We now give two closely related variants of UUSKT. All three versions
have their advantages and disadvantages.
The restriction of a digraph (V,E) to D contained in V is the digraph
(D,E intersect D^2).
RESTRICTED UPPER SHIFT KERNEL THEOREM. Every downward Q-digraph has a
restriction to some A^k, 0 in A contained in Q, with a kernel
containing its upper shift.
We take the subspaces of Q^k to be the A^k, 0 in A contained in Q. For
S contained in Q^k, we define S# to be the least subspace of Q^k
containing S.
A local kernel in the digraph (Q^k,E) is an S contained in Q^k such that
i. There is no edge from any x in S to any y in S.
ii. For all x in S#\S, there is an edge from x to some y in S.
LOCAL UPPER SHIFT KERNEL THEOREM. Every downward Q-digraph has a local
kernel containing its upper shift.
There is an easy proof of the equivalence of these three forms that
can be carried out in RCA_0.
The integral upper shift of x in Q^k is the result of adding 1 to the
nonnegative integer coordinates that are greater than the non integer
coordinates.
UNIFORM INTEGRAL UPPER SHIFT KERNEL THEOREM. There exists 0 in A
contained in Q, where every downward A-digraph has a kernel containing
its upper shift.
RESTRICTED INTEGRAL UPPER SHIFT KERNEL THEOREM. Every downward Q-
digraph has a restriction to some A^k, 0 in A contained in Q, with a
kernel containing its upper shift.
LOCAL INTEGRAL UPPER SHIFT KERNEL THEOREM. Every downard Q-digraph has
a local kernel containing its upper shift.
By the same easy argument, we see that the above three theorems are
provably equivalent in RCA_0.
THEOREM 3.5. SRP+ proves all six theorems. In fact, they are each
provably equivalent to Con(SRP) over WKL_0. For each of the six, it is
provable in RCA_0 that if it holds then A and the kernels can be
chosen to be recursive in 0'.
An important difference between the Upper Shift Theorems and the
Integral Upper Shift Theorems is that for the former, there is a fixed
dimension k where we get equivalence with Con(SRP). For the latter,
there is no such k, and instead we get a hierarchy through SRP.
4. GRAPHS, CLIQUES, AND GREED.
In this section, we present corresponding results involving graphs,
cliques, and greedy cliques. There are some differences, and a number
of open questions.
A graph is a pair G = (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. Thus
graphs are undirected, with no multiple edges and no loops.
We say that x,y are adjacent in G if and only if {x,y} is an edge in
G. We say that x,y are nonadjacent in G if and only if x,y are not
adjacent in G. Note that every x is nonadjacent to x in G.
A clique in G is a set of vertices, where any two distinct elements
are adjacent.
A maximal clique in G is a clique S, where every vertex is nonadjacent
to some vertex in S.
Note that this is equivalent to the condition: every vertex outside S
is nonadjacent to some vertex in S.
A rational graph is a graph whose vertex set is a subset of some Q^k.
A greedy clique in a rational graph G is a clique S in G, where every
x in V is nonadjacent to some y in S with max(y) <= max(x).
Note that this is equivalent to the condition: every x in V\S is
nonadjacent to some y in S with max(y) <= max(x).
A finite graph is a graph whose vertex set is finite. A well ordered
rational graph is a rational graph where the set of all coordinates of
vertices is a well ordered subset of Q.
THEOREM 4.1. Every graph has a maximal clique. Every finite rational
graph has a greedy clique. Every well ordered rational graph has a
greedy clique.
Let A be contained in 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.
THEOREM 4.2. (Q,emptyset) is a Q-graph with no greedy clique. There is
a recursive non well ordered A contained in Q such that every A-graph
has a greedy clique, and every downward A-graph has a kernel.
We want to understand the structure of maximal and greedy cliques in Q-
graphs. Since Q-graphs may not have greedy cliques, we want to
understand the structure of greedy cliques in A-graphs, A contained
in Q. In this way, we are also lead to studying the structure of
maximal cliques in A-graphs, A contained in Q.
QUESTION. Does every Q-graph have a maximal clique, which contains its
upper shift?
At present, we do not know the answer to this question. However, we do
have the following.
PROPOSITION 4.3. Every Q-graph has a maximal clique, which contains
its integral upper shift.
THEOREM 4.4. Proposition 4.3 is provable in WKL_0 + Con(SRP).
We do not know if Proposition 4.3 can be proved in ZFC.
UNIFORM UPPER SHIFT MAXIMAL CLIQUE THEOREM. There exists 0 in A
contained in Q, such that every A-graph has a maximal clique, which
contains its upper shift.
UNIFORM UPPER SHIFT GREEDY CLIQUE THEOREM. There exists 0 in A
contained in Q, such that every A-graph has a greedy clique, which
contains its upper shift.
UNIFORM INTEGRAL UPPER SHIFT MAXIMAL CLIQUE THEOREM. There exists 0 in
A contained in Q, such that every A-graph has a maximal clique, which
contains its integral upper shift.
UNIFORM INTEGRAL UPPER SHIFT GREEDY CLIQUE THEOREM. There exists 0 in
A contained in Q, such that every A-graph has a greedy clique, which
contains its integral upper shift.
We also have the restricted and local forms.
RESTRICTED UPPER SHIFT MAXIMAL CLIQUE THEOREM. Every Q-graph has a
restriction to some A^k, 0 in A contained in Q, with a maximal clique,
that contains its upper shift.
RESTRICTED UPPER SHIFT GREEDY CLIQUE THEOREM. Every Q-graph has a
restriction to some A^k, 0 in A contained in Q, with a greedy clique,
that contains its upper shift.
RESTRICTED INTEGRAL UPPER SHIFT MAXIMAL CLIQUE THEOREM. Every Q-graph
has a restriction to some A^k, 0 in A contained in Q, with a maximal
clique, that contains its integral upper shift.
RESTRICTED INTEGRAL UPPER SHIFT GREEDY CLIQUE THEOREM. Every Q-graph
has a restriction to some A^k, 0 in A contained in Q, with a greedy
clique containing its integral upper shift.
A local maximal clique in the graph (Q^k,E) is a clique S contained in
Q^k such that every x in S# is nonadjacent to some y in S.
A local greedy clique in the graph (Q^k,E) is a clique S contained in
Q^k such that every x in S# is adjacent to some y in S with max(y) <=
max(x).
LOCAL UPPER SHIFT MAXIMAL CLIQUE THEOREM. Every Q-graph has a local
maximal clique, that contains its upper shift.
LOCAL UPPER SHIFT GREEDY CLIQUE THEOREM. Every Q-graph has a local
greedy clique, that contains its upper shift.
LOCAL INTEGRAL UPPER SHIFT MAXIMAL CLIQUE THEOREM. Every Q-graph has a
local maximal clique, that contains its integral upper shift.
LOCAL INTEGRAL UPPER SHIFT GREEDY CLIQUE THEOREM. Every Q-graph has a
local greedy clique, that contains its integral upper shift.
We have thus presented three groups of four theorems, for a total of
12 theorems. As in section 1, there are easy equivalence proofs of
1,5,9; of 2,6,10; of 3,7,11; and of 4,8,12.
THEOREM 4.5. SRP+ proves all twelve theorems above. The six theorems
involving greedy cliques are provably equivalent to Con(SRP) over
WKL_0. For each of the twelve, it is provable in RCA_0 that if it
holds then A and the cliques can be chosen to be recursive in 0'.
The only proofs we know of the six theorems involving maximal cliques
use SRP+ (or Con(SRP)). We don't know if they can be proved in ZFC, or
even in RCA_0.
As in section 3, for the three Upper Shift Greedy Clique Theroems,
there is a fixed dimension k where we get equivalence with Con(SRP).
For the three Integral Upper Shift Greedy Clique Theorems, there is no
such k, and instead we get a hierarchy through SRP.
5. HUGE CARDINALS.
Let f:A^2 into A, A contained in Q. The f-relations are the subsets of
the A^k, k >= 1, which are Boolean combinations of inequalities
expressed using variables x_1,...,x_k over A, <, and f. The f-
relations are the same as the quantifier free definable subsets of
A^k in (A,<,f) in the sense of model theory.
The f-graphs are the graphs (A^k,E), where E contained in A^k is an f-
relation.
Let S be contained in Q^k. Write fld(S) for the set of all coordinates
of elements of S.
A self embedding of S is a partial function f:Q into Q such that for
all x_1,...,x_k in fld(S),
(x_1,...,x_k) in S iff (f(x_1),...,f(x_k)) in S.
A nontrivial self embedding of S is a self embedding of S that is not
an identity function.
EXOTIC KERNEL EMBEDDING THEOREM. There exists f:A^2 into A, A
contained in Q, such that every downward f-digraph has a kernel with
the nontrivial self embedding f(x,ceiling(x+1)).
THEOREM 5.1. The Exotic Kernel Embedding Theorem is provable in HUGE+
but not in HUGE. It is provably equivalent, over WKL_0, to Con(HUGE).
It is provable in RCA_0 that if it holds then f and the kernels can be
chosen to be recursive in 0'.
Here HUGE+ = ZFC + (for all n)(there exists an n-huge cardinal). HUGE
= ZFC + {there exists an n-huge cardinal}_n.
6. TEMPLATES.
Recall the from section 1:
UPPER SHIFT FIXED POINT THEOREM. Every order invariant R contained in
Q^2k has an A = A#\R<A contained in Q^k containing its upper shift.
This asserts that for all suitable R there exists A contained in Q^k
such that a particular Boolean equation holds between A,A#,R<A,ush[A],
where ush[A] is the upper shift of A.
TEMPLATE A. Let alpha be a Boolean equation in four variables. For all
order invariant R contained in Q^2k, there exists A contained in Q^k
such that alpha(A,A#,R<A,ush[A]) holds.
There are 2^16 instances of this Template. We expect to be able to
give a complete determination of the truth values of every instance,
within SRP+.
It is natural to add RA as follows.
TEMPLATE B. Let alpha be a Boolean equation in five variables. For all
order invariant R contained in Q^2k, there exists A contained in Q^k
such that alpha(A,A#,RA,R<A,ush[A]) holds.
This also should be capable of complete analysis within SRP+.
In an orthogonal direction, ush[A] is the straightforward lifting of
the upper shift function ush:Q into Q given by
ush(q) = q+1 if q >= 0 0; q otherwise
to vectors and sets of vectors.
TEMPLATE C. Let F be a partial piecewise linear function from Q into Q
with rational coefficients. Every order invariant R contained in Q^2k
has an A = A#\R<A contained in Q^k containing F[A].
TEMPLATE D. Let F_1,...,F_r be partial piecewise linear function from
Q into Q with rational coefficients. Every order invariant R contained
in Q^2k has an A = A#\R<A contained in Q^k containing each F_i(A).
These Templates have infinitely many instances, but should be amenable
to complete analysis within SRP+.
Note that Templates A,B are orthogonal to Templates C,D. They can be
combined into yet more ambitious Templates in the obvious way. We
conjecture that these more ambitious Templates are amenable to
complete analysis within SRP+.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 452nd 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
Harvey Friedman
More information about the FOM
mailing list