[FOM] 407: Kernel Tower Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Wed Mar 31 10:09:27 EDT 2010
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
_
More information about the FOM
mailing list