[FOM] 410: Kernel Function Theory 1

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

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

The punch line has been simplified to "regular pair of vectors". These  
are pairs of vectors (n_1 < ... < n_k), (n_2 < ... < n_k+1) whose  
values under a given function have a nice order theoretic property.  
Thus we use a single function - a Kernel Function - rather than a tower.

This notion of regular pair for a function f is very simple, and there  
are many interesting examples from very elementary mathematics. E.g.,  
with linear functions from N^k into N^k, and piecewise linear  
functions from N^k into N^k with nonnegative coefficients. We can also  
use polynomials from N^k into N^k, and piecewise polynomials from N^k  
into N^k with nonnegative coefficients.

Here is one of the independent statements:

EVERY REGRESSIVE DIGRAPH ON N^k HAS A KERNEL FUNCTION f:E^k into N^k  
MAPPING THE CUBE OF SOME REGULAR PAIR TO A CUBE WHICH IS MAPPED TO E^k.

Regular pairs are present all through elementary mathematics. E.g., if  
T:N^k into N^k is affine and r is sufficiently large, then  
(r,r^2,...,r^k) and (r^2,...,r^k+1) is a regular pair for T. If P:N^k  
into N^k is a polynomial and r is sufficiently large, then (r!, 
(2r)!,...,(kr)!) and ((2r)!,...,(kr+r)!) is a regular pair for P.

We believe that the tension present in kernel functions is also  
present all through basic mathematics - in different forms yet to be  
identified. A kernel of a digraph is a kind of basis for the digraph.  
Good places to look may be the usual kind of, and modified forms of,  
bases for vector spaces, groups, semigroups, rings, fields, Banach  
spaces, ideals in polynomial rings, etc.

We can replace N with {0,...,t}, t sufficiently large, and with an  
iterated exponential estimate for t. If the digraph is order  
invariant, then we have

FOR ALL r > (8k)!, EVERY REGRESSIVE ORDER INVARIANT DIGRAPH ON  
{0,...,r^k+1}^k HAS A KERNEL FUNCTION F:{0,...,r^k+1}^k MAPPING THE  
CUBE OF THE REGULAR PAIR (r,r^2,...,r^k), (r^2,...,r^k+1) TO A CUBE  
WHICH IS MAPPED TO {0,...,r^k+1}^k.

The associated large cardinals are the SRP hierarchy.

Kernel Function Theory 1
by
Harvey M. Friedman
April 8, 2010

1. KERNEL THEOREMS.
2. LOCAL KERNELS.
3. KERNEL FUNCTIONS.
4. MIN REGULAR PAIRS.
5. INFINITARY KERNEL FUNCTION THEOREMS.
6. FINITARY KERNEL FUNCTION THEOREMS.
7. ORDER INVARIANT KERNEL FUNCTION THEOREMS.
8. LOCAL KERNEL THEOREM ON Q^k.

1. KERNEL THEOREMS.

Kernels in digraphs represent a very active area of research in pure  
and applied graph theory, game theory, computer science, and social  
science. It has its origins with von Neumann in his book with  
Morgenstern on Game Theory and Economic Behavior, 1944.

Kernels form a kind of "basis" for a digraph.

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 (graph theorists) say that S is a kernel in G if and only if

i. S is a set of vertices of G.
ii. There is no edge (x,y), x,y in S.
iii. For all x in V\S, there is an edge (x,y), y in S.

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. S is a set of vertices of G.
ii. There is no edge (x,y), x,y in S.
iii. For all x in V\S, there is an edge (y,x), y in S.

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 due 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. The uniqueness (at most one)  
part is provable in RCA_0, and the existence part is also provably  
equivalent to ATR_0 over RCA_0.

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 with vertex set N^k, where for all edges (x,y), max(x) > max(y).

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

2. LOCAL KERNELS.

N^k has a natural subspace structure. The subspaces are subsets of the  
form E^k. We call these subspaces, cubes. The length of a cube E^k is  
the number of elements of E.

For S contained in N^k, we define the cube of S to be the least cube  
(subspace) in (of) N^k containing S. It is denoted by S#.

The cube of a list of vectors is the least cube in N^k containing all  
vectors in the list.

It is clear that S# = fld(S)^k, where fld(S) is the set of all  
coordinates of elements of S.

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

i. For all x,y in S, (x,y) is not an edge.
ii. For all x in N^k\S, there is an edge (x,y), y in S.

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

i. There is no edge (x,y), x,y in S.
ii. For all x in S#\S, there is an edge (x,y), y in S.

Thus we have simply replaced the whole space N^k by the subspace S#.

THEOREM 2.1. There is a finite set W_k of infinite subsets of N^k with  
field N such that
i. Every regressive digraph on N^k with an infinite local kernel has a  
local kernel isomorphic to a unique element of W_k.
ii. No proper subset of W_k has property i.
The elements of W_k are elementary recursive (and better). In fact,  
the union of the W_k's has an elementary recursive enumeration, but  
not without repetitions.

But the W_k are not really understandable.

THEOREM 2.2. There is no algorithm for computing the number of  
elements of W_k as a function of k. There is a fixed k such that ZFC  
cannot determine the number of elements of W_k. Moreover, no  
consistent consequence of our large cardinal axioms is sufficient.

NOTE: THE FUNCTION OF k ABOVE IS A PARTICULARLY NATURAL AND  
INTERESTING NONRECURSIVE FUNCTION FROM N INTO N TO DATE.

Note that Theorem 2.2 does NOT give us these kinds of incompleteness:

i. Specific sentences that are independent.
ii. Tasks (computing sizes) that can be done with large cardinals but  
not in ZFC.

An interesting question is how small k can be made in Theorem 2.2, and  
whether the smallest k depends on whether we are using ZFC, large  
cardinals, or weak fragments of ZFC.

3. KERNEL FUNCTIONS.

Let G = (V,E) be a digraph. Let f:V into V. We say that f is a kernel  
function if and only if

i. For all x in V, f(x) = x or (x,f(x)) is an edge.
ii. For all x,y in rng(f), (x,y) is not an edge.

THEOREM 3.1. G has a kernel if and only if G has a kernel function.  
The range of any kernel function is a kernel. If G has no infinite  
path, then G has a kernel function, and all kernel functions have the  
same range - the unique kernel of G.

We think of a kernel function as a "demonstration" that its range is a  
kernel.

It is important for us to extend the definition of kernel function to  
f:S into V, where S is a subset of V. I.e., f:S into V is a kernel  
function (for G) if and only if

i. For all x in S, f(x) = x or (x,f(x)) is an edge.
ii. For all x,y in rng(f), not (x,y) is not an edge.

Of course, from a kernel function f:D into V we do not get a kernel  
for G, or even a kernel for the induced subdigraph G|D. However, the  
range of kernel functions f:D into D must be kernels for G|D.

We will be concerned with kernel functions for regressive digraphs G  
on N^k whose domain is a cube.

4. REGULAR PAIRS.

Let f:A^k into N^k, A contained in N. A regular pair for f is a pair  
of vectors of the form

(n_1 < ... < n_k), (n_2 < ... < n_k+1)

such that every coordinate of f(n_2,...,n_k+1) less than n_2 is the  
corresponding coordinate of f(n_1,...,n_k).

This definition is definitely subject to Templating. We will not  
discuss the very important Templates here, but take this up later.

THEOREM 4.1. Suppose T:N^k into N^k is linear, or piecewise linear  
with nonnegative coefficients. For sufficiently large r,  
(r^1,...,r^k), (r^2,...,r^k+1) is a regular pair for T.

THEOREM 4.2. Suppose P:N^k into N^k is a polynomial, or piecewise  
polynomial with nonnegative coefficients. For sufficiently large r,  
(r!,(2r)!,...,(rk)!, ((2r)!,...,(rk+r)!) is a regular pair for P.

In fact, there is a robust notion of "ultimately regular pair" that  
comes out of examining linear functions and polynomials. This can be  
used in sections 5,6,7.

5. INFINITARY KERNEL FUNCTION THEOREM.

PROPOSITION 5.1. Every regressive digraph on N^k has a finite kernel  
function f:E^k into N^k mapping the cube of some regular pair to a  
cube that is mapped to E^k.

THEOREM 5.2. Proposition 5.1 is provable in SRP+ but not in any  
consequence of SRP consistent with RCA_0. Proposition 5.1 is provably  
equivalent to Con(SRP) over ACA'.

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 FUNCTION THEOREMS.

We now use digraphs on {0,...,t}^k. It is understood that kernel  
functions must have domain and range contained in {0,...,t}^k.

PROPOSITION 6.1. For all t >> k, every regressive digraph on  
{0,...,t}^k has a kernel function f:E^k into N^k mapping the cube of  
some regular pair to a cube that is mapped to E^k. Furthermore, it  
suffices that t be greater than the exponential stack of 2's of height  
k.

Note that Proposition 6.1 is explicitly Pi01.

THEOREM 6.2. Proposition 6.1 is provable in SRP+ but not in any  
consequence of SRP consistent with SEFA. Proposition 6.1 is provably  
equivalent to Con(SRP) over SEFA.

SEFA is super exponential function arithmetic.

7. ORDER INVARIANT KERNEL FUNCTION THEOREMS.

We say that x,y in N^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 a subset of N^k is order invariant if and only if it is  
the union of equivalence classes of N^k under order equivalence.

We say that R contained in N^k x N^k is order invariant if and only if  
R is order invariant as a subset of N^2k.

PROPOSITION 7.1. Every regressive order invariant digraph on N^k has a  
finite kernel function f:{0,...,(8k)!^k+1}^k into N^k mapping the cube  
of the regular pair {(8k)!,(8k)!^2,...,(8k)!^k}, {(8k)!^2,...,(8k)!^k 
+1) to a cube that is mapped to {0,...,(8k)!^k+1}^k.

THEOREM 7.2. Proposition 7.1 is provable in SMAH+, but none from any  
consequence of SRP consistent with SEFA. Proposition 7.1 is provably  
equivalent to Con(SRP) over SEFA.

8. LOCAL KERNEL THEOREM ON Q^k.

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 x is isolated in G if and only if x
is in N^k, and there are no edges (x,y), (y,x).

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 6.

THEOREM 8.1. The following is false in dimension 2 and higher. Every
order invariant digraph on Q^k with an isolated vertex 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 8.2. Every regressive order invariant digraph on Q^k in which  
x is isolated, has an infinite local kernel containing x.

We can strengthen Theorem 8.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 8.3. Every regressive order invariant digraph on Q^k in  
which x is isolated, has a local kernel containing its upper shift and  
x.

THEOREM 8.4. Proposition 8.3 is provable in SRP+ but not from any
consequence of SRP consistent with RCA_0. Proposition 8.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 410th 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
407: Kernel Tower Theory 1  3/31/10  12:02PM
408: Kernel tower Theory 2  4/1/10  6:46PM
409: Kernel Tower Theory 3  4/5/10  4:04PM

Harvey Friedman