[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