[FOM] 409: Kernel Tower Theory 3
Harvey Friedman
friedman at math.ohio-state.edu
Mon Apr 5 14:57:10 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
***********************************
There has been a breakthrough in connection with the punch lines.
The punch line for the infinitary kernel towers - namely progressive -
is already very satisfactory. It does involve the first three terms of
infinitary kernel towers, but in a vivid way.
Progressivity of finitary kernel towers CAN be obtained in ZFC.
HOWEVER, we know that it can be proved in Zermelo set theory, but not
in bounded Zermelo set theory. Still a rather strong incompleteness
for an explicitly Pi01 sentence - but less than the drama of large
cardinals.
We now have a number of satisfactory punch lines for the finitary
kernel towers that transcend ZFC.
The two new ones presented here are particularly satisfactory. They
are the upper shift property, and the increasing property. They
involve only the first two terms of kernel towers.
The increasing property does not depend on a shift, and leads
immediately to the general definition of
ORDER THEORETIC CLOSURE PROPERTY OF A PAIR OF SUBSETS OF N^k.
These take the form: if certain vectors built out of increasing
nonnegative integers are in the first term or in the second term, then
another vector built out of the same integers is in the first term or
in the second term.
So, e.g., we consider the Template
*) Every positive regressive graph on N^k has a finitary kernel tower
of any given finite length and front size, whose first two terms have
a specific order theoretic closure property.
We claim a determination of the truth values of all instances of *)
with a specific order theoretic property in a specific dimension k.
Such a determination can be done using the SRP hierarchy of large
cardinals, but not without.
Furthermore, we can prove general robustness features of this
classification that do not involve any specific order theoretic
property. But only if we use large cardinals, and not without.
We won't forgot the previously posted punch lines concerning
embeddings of kernel towers with critical point in fld(T1), and
subtowers of kernel towers with first integer removed in fld(T1).
******************
Kernel Tower Theory 3
by
Harvey M. Friedman
April 4, 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.
8. ORDER THEORETIC CLOSURE CONDITIONS.
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. There is no edge (x,y), x,y in A.
iii. For all x in V\A, there is an edge (x,y), y 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. There is no edge (x,y), x,y in A.
iii. For all x in V\A, there is an edge (y,x), y 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.
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 may be too many edges. 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.
N^k has a natural subspace structure. The subspaces are subsets of the
form E^k. For A contained in N^k, the subsapace generated by A is the
least subspace of N^k that contains A, and is denoted by A#.
It is clear that A# = fld(A)^k, where fld(A) is the set of all
coordinates of elements of 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. There is no edge (x,y), x,y in A.
ii. For all x in N^k\A, there is an edge (x,y), y in A.
We say that A is a local kernel for G if and only if
i. There is no edge (x,y), x,y in A.
ii. For all x in A#\A, there is an edge (x,y), y in A.
Thus we have simply replaced the whole space N^k by the subspace A#.
Note that by an induction argument, if two local kernels for G
generate the same subspace, then they are equal.
THEOREM 3.1. There is a unique finite set S_k of infinite subsets of
N^k with field N such that
i. Every positive regressive digraph on N^k has a local kernel order
isomorphic to a unique element of S_k.
ii. No proper subset of S_k has property i.
Furthermore, the elements of S_k are elementary recursive (and
better). In fact, the union of the S_k's has an elementary recursive
enumeration, but not without repetitions.
But the S_k are not really understandable.
THEOREM 3.2. There is no algorithm for computing the number of
elements of S_k as a function of k. There is a fixed k such that ZFC
cannot determine the number of elements of S_k. Moreover, no
consistent consequence of our large cardinal axioms is sufficient.
NOTE: THE FUNCTION OF k ABOVE IS A CANDIDATE FOR THE MOST NATURAL AND
INTERESTING NONRECURSIVE FUNCTION FROM N INTO N TO DATE.
Note that Theorem 3.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 3.2, and
whether the smallest k depends on whether we are using ZFC, large
cardinals, or weak fragments of ZFC.
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. There is no edge (x,y), x,y in A.
ii. For all x in A#\A, there is an edge (x,y), y 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 natural to strengthen this
definition to
i. There is no edge (x,y), x,y in B.
ii. For all x in A#\A, there is an edge (x,y), y in B.
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 Ti.
Let G be a digraph on N^k. A kernel tower in G is a tower T of subsets
of N^k, where
i. There is no edge (x,y), where x,y are in some T_i.
ii. For all 1 <= i < lth(T) and x in T_i#\T_i, there is an edge (x,y),
y 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 three of many 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 T be a tower in N^k. We say that T is progressive if and only if
for all positive n in fld(T_1), the greatest integer in fld(T_2) below
n is smaller than the greater integer in fld(T_3) below n.
We say that T has the upper shift property if and only if the
following holds. If x is in T_2 and x* is the result of replacing all
of the positive coordinates of x that are greater than all of the
coordinates of x in fld(T_2)\fld(T_1) by their respective shifts in
fld(T_1), then x* is in T_2. NOTE: x* exists if and only if
max(fld(T1)) is not a coordinate of x.
We say that T has the increasing property if and only if the following
holds.
For all x < y_1 < ... < y_k, if (y_1,...,y_k) is in T_1 and
(x,y_1,...,y_k-1) is in T_2, then (x,y_2,...,y_k) is in T_2.
I.e., given some strictly increasing numbers, if certain k-tuples are
in T1 and certain k-tuples are in T2, then certain k-tuples are in T_1
and certain k-tuples are in T_2.
5. INFINITARY KERNEL TOWER THEOREMS.
Now we can 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 (any given finite
length).
PROPOSITION 5.2. Every positive regressive digraph on N^k has an
infinitary kernel tower of length 4 (any given finite length) with the
upper shift property.
PROPOSITION 5.3. Every positive regressive digraph on N^k has an
infinitary kernel tower of length 4 (any given finite length) with the
increasing property.
PROPOSITION 5.4. Every positive regressive digraph on N^k has an
infinitary progressive kernel tower of length 4 (any given finite
length) with the upper shift and increasing properties.
THEOREM 5.5. Proposition 5.1 (both forms) is provable in SMAH+, but
not from any consequence of SMAH consistent with RCA_0. Proposition
5.1 (both forms) is provably equivalent to Con(SMAH) over ACA'.
Propositions 5.2 - 5.4 (all six forms) are provable in SRP+, but not
from any consequence of SRP consistent with RCA_0. Propositions 5.2 -
5.4 (all six forms) are provably equivalent to Con(SRP) over ACA'.
THEOREM 5.6. If we use length 2 in Propositions 5.1 - 5.4, then the
statements are provable in ZFC. If we use infinite length in
Propositions 5.1 - 5.4, then the statements are refutable in RCA_0.
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.
The front size of a kernel tower is the number of positive elements of
the field of the first term.
PROPOSITION 6.1. For all t >> k, every positive regressive digraph
on {0,...,t}^k has a kernel tower of length 4 and front size k with
the upper shift property (increasing property). It suffices to assume
that t is greater than an exponential stack of 2's of height 8k.
PROPOSITION 6.2. For all t >> k,r, every positive regressive digraph
on {0,...,t}^k has a kernel towers of length 4 and front size r with
the upper shift property (increasing property). 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,p, every positive regressive digraph
on {0,...,t}^k has a kernel towers of length p and front size k with
the upper shift property (increasing property). It suffices to assume
that t is greater than an exponential stack of 2's of height 8kp.
PROPOSITION 6.4. For all t >> k,p,r, every positive regressive digraph
on {0,...,t}^k has a kernel towers of length p and front size r with
the upper shift property (increasing property). It suffices to assume
that t is greater than an exponential stack of 2's of height 8kpr.
THEOREM 6.5. Propositions 6.1 - 6.4 (all 8 forms) is provable in SRP+,
but not from any
consequence of SRP consistent with RCA_0. Propositions 6.1 - 6.4 are
provably
equivalent to Con(SRP) over SEFA.
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 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 1.
THEOREM 7.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 7.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 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 regressive order invariant digraph on Q^k in
which x is isolated, has a local kernel containing its upper shift and
x.
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.
8. ORDER THEORETIC CLOSURE CONDITIONS.
Recall the definition of the increasing property. We have used the
following property of two sets A contained in B contained in N^k.
For all x < y_1 < ... < y_k, if (y_1,...,y_k) is in A and
(x,y_1,...,y_k-1) is in B, then (x,y_2,...,y_k) is in B.
I.e., given some strictly increasing numbers, if certain k-tuples are
in A and certain k-tuples are in B, then certain k-tuples are in A and
certain k-tuples are in B.
We write this formally as follows.
For all nonnegative integers x_1 < ... < x_p, if y_1,...,y_q in A and
z_1,...,z_r in B then u_1,...,u_s in A and v_1,...,v_t in B.
Here Let p >= 1, q,r,s,t >= 0, and the y's, z's, u's, v's are k-tuples
from the p distinct variates x_1,...,x_p.
In increasing property asserts that the first two terms of a kernel
tower has a single order theoretic closure property. We can subject a
kernel tower to a finite set of order theoretic closure properties.
TEMPLATE INF. Let alpha be a finite set of order theoretic closure
properties in N^k. Every positive regressive digraph on N^k has an
infinitary kernel tower of any given finite length whose first two
terms obey alpha.
TEMPLATE FIN. Let alpha be a finite set of order theoretic closure
properties in N^k. For all t >> k,p,r every positive regressive
digraph on {0,...,t}^k has a kernel tower of length p and front size r
whose first two terms obey alpha. It suffices to assume that t is
greater than an exponential stack of 2's of height 8kpr.
THEOREM 8.1. Each instance of INF or FIN is either provable in SRP, or
refutable in RCA_0. This result does not hold for any consequence of
SRP that is consistent with RCA_0. In fact, we can replace SRP by
RCA_0 + the consistency of each fragment of SRP (as a scheme).
This is a large amount of robustness in the classification.
PROPOSITION 8.2. The two Templates yield the same truth values.
Note that in each instance of INF, k is fixed, and we are quantifying
over all finite lengths.
PROPOSITION 8.3. In INF, if we quantify over length 4 only, then we
get the same truth values.
PROPOSITION 8.4. In FIN, if we fix p = 4, then we get the same truth
values.
There are other robustness results.
THEOREM 8.5. Propositions 8.2 - 8.4 are provable in SRP+ but not in
any consequence of SRP consistent with RCA_0. In fact, RCA_0 +
Con(SRP) suffices.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 408th 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
Harvey Friedman
More information about the FOM
mailing list