[FOM] 407: Kernel Tower Theory 1

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

***********************************

This posting represents major breakthroughs on two fronts:

1. First and foremost, the independent Pi01 statements are put rather  
clearly into the context of a fundamental and active part of pure and  
applied graph theory, which goes back to von Neumann and Morgenstern's  
book on Game Theory published in 1944. This is the theory of kernels  
and dominators in digraphs. The area is rather active, with  
applications to computer science, game theory (its origin),  
optimization, and even social science (voting, etcetera). The kernel  
and dominator notions are dual, although there are more references to  
kernels in digraphs than to dominators in digraphs.

NOTE: We use N^k here, with the ordering on N, and the obvious notion  
of subspace - the E^k, E contained in N. We expect to find new  
formulations that are purely, or more purely, graph theoretic.

2. Secondly, we have found some new and more vivid punch lines - i.e.,  
structural properties of our objects - that drive the necessary use of  
large cardinals.

The large cardinals involved in this posting are the strongly Mahlo  
hierarchy and the SRP hierarchy.

We also revisit the previous work on order invariant relations on the  
rationals, using the kernel terminology. Since that work, we have of  
course moved away from order invariant relations.

We will report on large large cardinals later.

This posting is self contained.

Kernel Tower Theory 1
by
Harvey M. Friedman
March 31, 2010

1. CLASSICAL KERNEL THEOREMS.
2. GRAPHS ON N^k.
3. LOCAL KERNELS AND KERNEL TOWERS.
4. PROPERTIES OF TOWERS IN N^k.
5. INFINITARY KERNEL TOWER THEOREMS.
6. FINITARY KERNEL TOWER THEOREMS.
7. LOCAL KERNELS IN Q^k.

1. CLASSICAL KERNEL THEOREMS.

A digraph is a pair G = (V,E), where V is a set and E is a subset of  
V^2. V is the set of vertices, and E is the set of edges.

A directed acyclic graph (dag) is a digraph where all of the vertices  
on any path are distinct.

We say that A is a kernel in G if and only if

i. A is a set of vertices of G.
ii. No edge connects an element of A to an element of A.
iii. If v is a vertex outside A, then there is an edge (v,w) in G,  
where w is in A.

The dual notion of a dominator in the digraph G is also encountered.  
We say that A is a dominator in G if and only if

i. A is a set of vertices of G.
ii. No edge connects an element of A to an element of A.
iii. If v is a vertex outside A, then there is an edge (w,v) in G,  
where w in A.

However, there are more references to kernels in digraphs than to  
dominators in digraphs, so we will use kernels rather than dominators.

THEOREM 1.1. Finite Kernel Theorem. Every finite dag has a unique  
kerrnel.

Theorem 1.1 is credited to von Neumann in his book with Morgenstern on  
Game Theory in 1944.

I do not know any reference for the following infinitary extension of  
the Kernel Theorem. I hesitate to claim credit for this, but I may  
have to.

THEOREM 1.2. Infinite Kernel Theorem. If G is a digraph where all  
paths are finite, then G has a unique kernel.

THEOREM 1.3. The Infinite Kernel Theorem, for countable digraphs, is  
provably equivalent to ATR_0 over RCA_0.

2. GRAPHS ON N^k.

We use N for the set of all nonnegative integers. Sections 3-6 are  
based on digraphs on N^k; i.e., where the vertex set is N^k.

We exploit the coordinate structure of N^k and the ordering on N.  
Although we do not take this approach here, we can view N^k as the set  
of labels for the digraph G, and so the labels are equipped with extra  
structure. More radically, in the future we will explore the  
possibility of doing without this non graph theoretic structure,  
dealing just with ordinary digraphs (no labels).

But in this abstract, we work with digraphs on N^k.

It is useful to have a simple condition on graphs on N^k that implies  
that all paths are finite, so that we obtain a unique kernel. (There  
is a large literature on sufficient conditions for their being a  
kernel, or unique kernel, in a digraph). We say that G is a regressive  
digraph on N^k if and only if G is a digraph on N^k, where for all  
edges (x,y), max(x) > max(y).

THEOREM 2.1. Every regressive digraph on N^k has a unique kernel.

However, the kernel may be finite, or even of cardinality 1. This is  
because there are too many edges. So to avoid trivialities, we say  
that G is a positive digraph on N^k if and only if G is a digraph on  
N^k where for all edges (x,y), min(x) > 0.

THEOREM 2.2. Every positive regressive digraph on N^k has a unique  
kernel, and the kernel is infinite.

Sections 3-6 are concerned with positive regressive digraphs on N^k.

There cannot be any structure theory for the kernels of positive  
regressive digraphs on N^k, in light of the following.

THEOREM 2.3. Let A be contained in N^k. The following are equivalent.
i. A is the kernel of some positive regressive digraph on N^k.
ii. A includes all x in N^k with min(x) = 0.

3. LOCAL KERNELS AND KERNEL TOWERS.

In light of there being no structure theory for kernels of positive  
regressive digraphs on N^k, it is natural to move to what we call  
LOCAL KERNELS.

We view the space N^k as having the natural subspaces E^k contained in  
N^k. For A contained in N^k, we write A# for the subspace generated by  
A; i.e., the least subspace of N^k containing A.

Let G be a digraph on N^k and A contained in N^k. Recall that A is a  
kernel for G if and only if

i. No element of A is connected by an edge to an element of A.
ii. For every v in N^k\A, there is an edge (v,w) in G, where w is in A.

We say that A is a local kernel for G if and only if

i. No element of A is connected by an edge to an element of A.
ii. For every v in A#\A, there is an edge (v,w) in G, where w is in A.

Thus we have "merely" replaced N^k with A#.

Note that if two local kernels for G generate the same subspace, then  
they are equal. It is clear that any structure theory for the local  
kernels of a positive regressive digraph on N^k will involve at least  
kernels generating different subspaces. In fact, the following  
suggests that there is no structure theory for the local kernels of a  
positive regressive digraph on N^k.

THEOREM 3.1. The following is false. In any positive regressive  
digraph on N^k, there are two infinite local kernels, the first  
properly included in the second.

In fact, there is a positive regressive graph on some N^k where local  
kernels are comparable under inclusion if and only if the subspace  
generated by one of them is an initial segment of the subspace  
generated by the other.

So where do we go from here?

We "stagger" the kernels in the following very natural sense. Let G be  
a digraph on N^k. The simplest "staggered kernel" notion is a pair A  
contained in B contained in N^k such that

i. No element of A is connected by an edge to an element of A.
ii. For every v in A#\A, there is an edge (v,w) in G, where w is in B.

Notice that we have "merely" changed the last letter in the definition  
of local kernel, form "A" to "B". Hence the name "staggered".

Actually, once we go this route, it is somewhat more natural to  
strengthen this definition to

i. No element of B is connected by an edge to an element of B.
ii. For every v in A#\A, there is an edge (v,w) in G, where w is in B.

More generally, we define KERNEL TOWERS as follows.

A tower (of sets) is a nonempty finite or infinite sequence of sets,  
where each nonterminal term is a subset of the next term. We count the  
terms of towers T from 1 on. If the i-th term of T exists, then we  
write it as T_i.

Let G be a digraph on N^k. A kernel tower in G is a tower T of subsets  
of N^k, where

i. No vertex in any term of T is connected by an edge to any vertex in  
any term of T.
ii. For all 1 <= i < lth(T) and v in T_i#\T_i, there is an edge (v,w)  
in G, where w is in T_i+1.

THEOREM 3.2. The union of the terms of any infinite length kernel  
tower in any graph on N^k is a local kernel in that graph.

Note that in some sense, kernel towers of length p, where p is large,  
"approximate" a local kernel. The larger p is, the "better" the  
"approximation" to a local kernel.

The punch line is that the kernel towers of finite length in positive  
regressive digraphs on N^k can be proved to have interesting  
structural properties - but only if we use large cardinals going far  
beyond the usual axioms of mathematics.

4. PROPERTIES OF TOWERS IN N^k.

We now introduce the properties of towers that drive the necessary  
uses of large cardinals in the next two sections.

An infinitary tower is a tower where all sets are infinite. The front  
size of a tower is the cardinality of its first term.

For A contained in N^k, we write fld(A) for the set of integers  
appearing as coordinates of elements of A. Obviously, A# = fld(A)^k.

Let S,T be towers in N^k of finite length p >= 1.

We say that T is subexponential if and only if the number of elements  
of fld(T_p) below the i-th element of fld(T_1) is at most 2^i.

We say that T is progressive if and only if for all positive n in  
fld(T_1), the greatest integer in fld(T_i) below n, strictly increases  
as i goes from 1 through p.

For towers S,T of the same length, we say that S contained in T if and  
only if each S_i is contained in T_i. By "the first integer removed"  
we mean the least element of fld(T_p)\fld(S_p). (In the case of  
infinite length S,T, we use the union of the T's and S's here). There  
may not be a first (or any) integer removed (even if the inclusions  
are proper). An interesting condition is that the first integer  
removed lies in fld(T_1).

5. INFINITARY KERNEL TOWER THEOREMS.

Now we can now develop some structure theory for infinitary kernel  
towers.

PROPOSITION 5.1. Every positive regressive digraph on N^k has an  
infinitary progressive kernel tower of length 4.

PROPOSITION 5.2. Every positive regressive digraph on N^k has two  
infinitary kernel towers of length 4, S contained in T, where the  
first integer removed lies in fld(T_1).

PROPOSITION 5.3. Every positive regressive digraph on N^k has two  
infinitary subexponential progressive kernel towers of any given  
finite length, S contained in T, where the first integer removed lies  
in fld(T).

THEOREM 5.4. Propositions 5.1 - 5.3 are provable in ZFC for length 2.  
Proposition 5.1 is provable in SMAH+, but not from any consequence of  
SMAH consistent with RCA_0. Proposition 5.1 is provably equivalent to  
Con(SMAH) over ACA'. Propositions 5.2, 5.3 are provable in SRP+, but  
not from any consequence of SRP consistent with RCA_0. Propositions  
5.2, 5.3 are provably equivalent to Con(SRP) over ACA'.

THEOREM 5.5. If we use length 2 in Propositions 5.1 - 5.3, then the  
statements are provable in ZFC. If we use infinite length in  
Propositions 5.1 - 5.3, then the statements are refutable in RCA_0.  
If, in Proposition 5.2, we merely assert that there is an integer  
removed, then the statement is provable in ZFC.

Here SMAH+ = ZFC + "for all k there exists a strongly k-Mahlo  
cardinal". SMAH = ZFC + {there exists a strongly k-Mahlo cardinal}_k.  
SRP+ = ZFC + "for all k there exists a limit ordinal with the k-SRP".  
SRP = ZFC + {there exists a limit ordinal with the k-SRP}_k. 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 which is a stationary subset of lambda.  
ACA' is ACA_0 + "for all n in N and x contained in N, the n-th Turing  
jump of x exists".

6. FINITARY KERNEL TOWER THEOREMS.

Now we can now develop some structure theory for kernel towers in  
digraphs on {0,...,t}^k. It is understood that all terms of kernel  
towers must be subsets of {0,...,t}^k.

PROPOSITION 6.1. For all t >> k,r, every positive regressive digraph  
on {0,...,t}^k has a subexponential progressive kernel tower of length  
4 and front size r. It suffices to assume that t is greater than an  
exponential stack of 2's of height 8kr.

PROPOSITION 6.2. For all t >> k,r, every positive regressive digraph  
on {0,...,t}^k has two kernel towers of length 4 and front size k, S  
contained in T, where the first integer removed lies in fld(T). It  
suffices to assume that t is greater than an exponential stack of 2's  
of height 8kr.

PROPOSITION 6.3. For all t >> k,r,p, every positive regressive digraph  
on {0,...,t}^k has two subexponential progressive kernel towers of  
length p and front size r, S contained in T, where the first integer  
removed lies in fld(T). It suffices to assume that t is greater than  
an exponential stack of 2's of height 8krp.

THEOREM 6.4. Proposition 6.1 is provable in SMAH+, but not from any  
consequence of SMAH consistent with RCA_0. Proposition 6.1 is provably  
equivalent to Con(SMAH) over SEFA. Propositions 6.2, 6.3 are provable  
in SRP+, but not from any consequence of SRP consistent with RCA_0.  
Propositions 6.2, 6.3 are provably equivalent to Con(SRP) over SEFA.

THEOREM 6.5. If we use length 2 in Propositions 6.1 - 6.3, then the  
statements are provable in ZFC. If, in Proposition 6.1, we remove  
"subexponential", or if we remove "progressive", then the statement is  
provable in ZFC. If, in Propositions 6.1, we replace "front size r"  
with "front size k" or use various standard functions of k, then the  
statement is provable in ZFC. If, in Proposition 6.2, we merely assert  
that there is an integer removed, then the statement is provable in ZFC.

In fact, in Proposition 6.1, as we replace "front size r" with "front  
size f(k)", for various functions f in the < epsilon_0-recursive  
function hierarchy, we climb up from Peano Arithmetic through SMAH. We  
will report on this later.

Here SEFA is super exponential function arithmetic.

7. LOCAL KERNELS IN THE RATIONALS.

Here we work with graphs on Q^k that are order invariant, as defined  
below. This allows us to make interesting statements about the local  
kernels of the graph.

Let x,y in Q^k. Two tuples x,y of rationals are order equivalent if  
and only if for all 1 <= i,j <= k, x_i < x_j iff y_i < y_j. There are  
finitely many equivalence classes of Q^k under order equivalence.

We say that V contained in Q^k is order invariant if and only if V is  
the union of equivalence classes of Q^k under order equivalence.

Let G be a digraph on Q^k. We say that G is limited if and only if  
there exists x in Q^k such that there are no edges (x,y).

We say that G is order invariant if and only if its edge set is order  
invariant, viewed as a subset of Q^2k = Q^k x Q^k.

We say that G is regressive if and only if for all edges (x,y) in G,  
max(x) > max(y).

The kernels of G have been defined in section 1.

THEOREM 7.1. The following is false. Every limited order invariant  
digraph on Q^k has a kernel.

We define local kernels as before. Specifically, for A contained in  
Q^k, we define A# to be the subspace of Q^k generated by A. (The  
subspaces are the E^k contained in Q^k).

THEOREM 7.2. Every limited order invariant digraph on Q^k has an  
infinite local kernel.

We can strengthen Theorem 7.2 greatly. The upper shift of q in Q is q 
+1 if q is nonnegative; q otherwise. The upper shift extends to Q^k  
coordinatewise. The upper shift of a subset of Q^k is the set of upper  
shifts of its elements.

PROPOSITION 7.3. Every limited order invariant digraph on Q^k has a  
nonempty local kernel that is properly contained in its upper shift.

THEOREM 7.4. Proposition 7.3 is provable in SRP+ but not in any  
fragment of SRP consistent with RCA_0. Proposition 7.3 is provably  
equivalent to Con(SRP) over WKL_0.

The upper shift is an example of a piecewise linear (partial) function  
from Q into Q. We intend to study carefully what happens when we use  
any finite sets of such functions, instead of just the upper shift on  
Q as above. We expect that we will be able to completely analyze this  
in SRP+. We already know that SRP does not suffice. In particular, ZFC  
does not suffice.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 407th 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-349 can be found at http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.

350: one dimensional set series  7/23/09  12:11AM
351: Mapping Theorems/Mahlo/Subtle  8/6/09  10:59PM
352: Mapping Theorems/simpler  8/7/09  10:06PM
353: Function Generation 1  8/9/09  12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1  8/9/09  6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2  8/10/09  6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem  8/14/09  9:31AM
357: HIGH SCHOOL Games/Update  8/20/09  10:42AM
358: clearer statements of HIGH SCHOOL Games  8/23/09  2:42AM
359: finite two person HIGH SCHOOL games  8/24/09  1:28PM
360: Finite Linear/Limited Memory Games  8/31/09  5:43PM
361: Finite Promise Games  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1  9/24/09  1:06PM
366: Free Reductions and Large Cardinals/polished  9/28/09  2:19PM
367: Upper Shift Fixed Points and Large Cardinals  10/4/09  2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction  10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09  2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1graham
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09  2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09  2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION  12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10  7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1  2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2  2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3  2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4  2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5  2/22/10
3:50AM
394: Free Reduction Theory 1  3/2/10  7:30PM
395: Free Reduction Theory 2  3/7/10  5:41PM
396: Free Reduction Theory 3  3/7/10  11:30PM
397: Free Reduction Theory 4  3/8/10  9:05AM
398: New Free Reduction Theory 1  3/10/10  5:26AM
399: New Free Reduction Theory 2  3/12/10  9:36AM
400: New Free Reduction Theory 3  3/14/10  11:55AM
401: New Free Reduction Theory 4  3/15/10  4:12PM
402: New Free Reduction Theory 5  3/19/10  12:59PM
403: Set Equation Tower Theory 1  3/22/10  2:45PM
404: Set Equation Tower Theory 2  3/24/10  11:18PM
405: Some Countable Model Theory 1  3/24/10  11:20PM
406: Set Equation Tower Theory 3  3/25/10  6:24PM

Harvey Friedman

_