[FOM] 443: Kernels and Large Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
Wed Oct 20 22:29:16 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED.
Assuming this work remains stable, I am expecting to put up sketches
early in 2011. I have other urgent matters presently.
KERNELS AND LARGE CARDINALS 1
by
Harvey M. Friedman
October 20, 2010
0, Preface.
1. Digraph, kernel, downward.
2. A-set, A-digraph, diagonal image, upper shift.
3. The infinite upper shift kernel theorem.
4. (A,R)-set, (A,R)-set*, (A,R)-digraph, local (A,R)-function.
5. The infinite system kernel theorem.
6. Norm, n-kernel, n-diagonal image.
7. The finite upper shift kernel theorem.
8. n-local (A,R)-function.
9. The finite system kernel theorem.
10. The future.
0. PREFACE.
In http://www.cs.nyu.edu/pipermail/fom/2010-October/015089.html, we
presented the Infinite Upper Shift Kernel Theorem, and pointed to a
sketch of its proof from large cardinals (the SRP hierarchy) in http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
, section 1 #70.
The Infinite Upper Shift Kernel Theorem states the existence of a
subset of Q such that certain naturally associated digraphs have a
kernel containing its image under a specific function (the upper shift).
We now present the Infinite System Kernel Theorem. Here we state the
existence of a system (A,R), A contained in Q, R contained in A^2,
such that certain naturally associated digraphs have a kernel
containing its image under a nontrivial function whose truncations are
nice relative to (A,R).
The resulting sentence is equivalent to Con(HUGE).
In http://www.cs.nyu.edu/pipermail/fom/2010-October/015089.html, we
also presented the Finite Upper Shift Kernel Theorem, which can be
viewed as a straightforward version of the Infinite Upper Shift Kernel
Theorem, putting in upper bounds on the norms of the rationals
involved. It is explicitly Pi01, and also equivalent to Con(SRP).
We present a somewhat simplified version of the Finite Upper Shift
Kernel Theorem. We also present the Finite System Kernel Theorem, as a
straightforward version of the Infinite System Kernel Theorem. It is
explicitly Pi01, and also equivalent to Con(HUGE).
We also sharpen the System Kernel Theorems to reach past I3 = rank
into itself.
Note that all finite forms are explicitly Pi01. The estimates used
appear safe, and will probably be sharpened when the results fully
stabilize.
We can also use the lexicographic ordering for downward. This will
push the strength up a little bit, and also seems to somewhat simplify
the reversals.
1. DIGRAPH, KERNEL, DOWNWARD.
A directed graph, or digraph, is a pair (V,E), where V is a nonempty
set of vertices, and E contained in V^2 is a set of edges. We say that
x connects to y if and only if (x,y) in E.
A kernel in (V,E) is a S contained in V such that
i. No element of S connects to any element of S.
ii. Every element of V\S connects to some element of S.
This the standard definition of kernel in digraphs, and the study of
kernels in digraphs is a very active subject in pure/applied
combinatorics. There is the dual notion of dominator in digraphs, and
some of the work falls under that name.
The study of kernels in digraphs was inspired by the following theorem
of John von Neumann.
THEOREM 1.1. Von Neumann 1944 (book with Morgenstern). Every finite
dag has a unique kernel.
Here a dag is a directed acyclic graph; i.e., a digraph with no cycles.
There is a well known generalization.
THEOREM 1.2. Every digraph with no infinite walk has a unique kernel.
Theorem 1.2 is subject to Reverse Mathematics. For countable digraphs
the existence of a kernel and the existence of a unique kernel are
both equivalent to ATR_0 over RCA_0.
It appears that Digraph Kernels are providing a crucial link between
strong uses of infinity and an active research area of mathematics
relating to combinatorics, computer science, and optimization.
However, I do not want to overstate the case here. The bulk of
interest is in kernels in finite digraphs, and the Infinite Kernel
Theorems presented here involve infinite digraphs. The Finite Kernel
Theorems, however, involve only finite digraphs. We are hopeful that
through the Finite Kernel Theorems, we shall be able to strengthen the
connection with ongoing research in Digraph Kernels.
The great power of Digraph Kernels is that they allow us to
appropriate encapsulate transfinite recursion, transfinite induction,
and bounded separation, with one simple concept. Large cardinals are
"generated" by imposing richness properties on the kernels.
We let Q be the set of all rational numbers with the usual ordering.
We will focus on digraphs (A^k,E) where A is contained in Q. We say
that (A^k,E) is downward if and only if x E y implies max(x) > max(y).
Note that if A is well ordered, then (V,E) has no infinite walk, and
hence has a unique kernel.
2. A-SET, A-DIGRAPH, DIAGONAL IMAGE, UPPER SHIFT.
We fix A contained in Q. The A-sets in A^k form a Boolean algebra of
subsets of A^k defined using variables x_1,...,x_k ranging over A. It
is the Boolean algebra generated by the conditions x_i < x_j, 1 <= i,j
<= k.
The A-digraphs on A^k are the digraphs (A^k,E), where E is an A-set in
A^2k.
The A-sets and the A-digraphs are the A-sets in A^k and the A-digraphs
on A^k, for k >= 1.
Let S contained in Q^k and f:Q into Q be partial. The diagonal image
of S by f is the set
{(f(x_1),...,f(x_k)): (x_1,...,x_k) in S}.
The upper shift is the function ush:Q into Q given by
ush(q) = q+1 if q >= 0; q otherwise.
3. THE INFINITE UPPER SHIFT KERNEL THEOREM.
PROPOSITION 3.1. Infinite Upper Shift Kernel Theorem. There exists 0
in A contained in Q such that every downward A-digraph has a kernel
containing its diagonal image by the upper shift.
THEOREM 3.2. Proposition 3.1 is provably equivalent to Con(SRP) over
ACA_0. ACA_0 + Con(SRP) proves that A and the kernels can be taken to
be recursive in the Turing jump of 0.
Here SRP = ZFC + {there exists lambda with the k-SRP}_k. Lambda has
the k-SRP if and only if lambda is a cardinal such that every f:
[lambda]^k into 2 is constant on some [E]^k, E a stationary subset of
lambda. Here [E]^k is the set of all unordered k-tuples from E.
4. (A,R)-SET, (A,R)*-SET, (A,R)-DIGRAPH, LOCAL (A,R)-FUNCTION.
A Q-system is a pair (A,R), where A is a subset of Q and R is a subset
of A^2.
The (A,R)-sets in A^k form a Boolean algebra of subsets of A^k defined
using variables x_1,...,x_k ranging over A. It is the Boolean algebra
generated by the conditions z < w, R(z,w), where z,w are among the
variables x_1,...,x_k.
If we also allow z,w to be specific elements of A, then we obtain the
(in general) larger Boolean algebra of (A,R)*-sets. We can think of
(A,R)* as the structure (A,R) expanded with constants for each element
of A.
The (A,R)-digraphs on A^k are the digraphs (A^k,E), where E is an
(A,R)-set in A^k.
A downward (A,R)-digraph is an (A,R)-digraph where x E y implies
max(x) > max(y).
The (A,R)-sets, (A,R)*-sets, (A,R)-digraphs are the (A,R)-sets in A^k,
(A,R)*-sets in A^k, (A,R)-digraphs on A^k, respectively, for some k >=
1.
The local (A,R)-functions are the functions f:A into A such that the
graph of each truncation f|<x, x in A, is an (A,R)*-set.
A function is said to be nontrivial if and only if it is not an
identity function.
5. THE INFINITE SYSTEM KERNEL THEOREM.
PROPOSITION 5.1. Infinite System Kernel Theorem. There exists a Q-
system (A,R) such that every downward (A,R)-digraph has a kernel
containing its diagonal image by a nontrivial local (A,R)-function.
THEOREM 5.2. Proposition 5.1 is provably equivalent to Con(HUGE) over
ACA_0. ACA_0 + Con(HUGE) proves that A,R, the kernels, and the local
functions can be taken to be recursive in the Turing jump of 0.
Here HUGE = ZFC + {there exists a k-huge cardinal}_k.
We can go further.
PROPOSITION 5.3. Extended Infinite System Kernel Theorem. There exists
a Q-system (A,R) such that every downward (A,R)-digraph has a kernel
containing its diagonal image under a local (A,R)-function that is
nontrivial below some fixed point.
THEOREM 5.4. Proposition 5.3 implies Con(I3) and is implied by
Con(I2), over ACA_0. ACA_0 + Con(I2) proves that A,R, the kernels, and
the local functions can be taken to be recursive in the Turing jump of
0.
6. NORM, n-KERNEL, n-DIAGONAL IMAGE.
The norm of x in Q^k is the sum of the magnitudes of all of the
numerators and denominators of the reduced forms of its coordinates.
I.e, the norm of (-2,2/6,0) is 8.
The norm of a subset of Q^k is the maximum norm of its elements. The
empty set and infinite subsets of Q^k do not have norms.
Let (A^k,E) be a digraph, where A is contained in Q. We say that S is
an n-kernel if and only if
i. Every element of S has norm at most 8n^2.
ii. No element of S is connected to any element of S.
iii. Every x in V\S of norm p <= n is connected to an element of S of
norm at most 8p^2.
Let S contained in Q^k and f:Q into Q be partial. The n-diagonal image
of S by f is the set of all elements of the diagonal image of S by f
of norm at most n.
7. THE FINITE UPPER SHIFT KERNEL THEOREM.
PROPOSITION 7.1. Finite Upper Shift Kernel Theorem. There exists 0 in
A contained in Q of norm at most 8n^2 such that every downward A-
digraph has an n-kernel containing its n-diagonal image under the
upper shift.
THEOREM 7.2. Proposition 7.1 is provably equivalent to Con(SRP) over
EFA.
Note that the Finite Upper Shift Kernel Theorem is explicitly Pi01.
8. n-LOCAL (A,R) FUNCTION.
Let (A,R) be a Q-system. The norm of an (A,R)*-set is the least n such
that the set can be expressed using parameters of norm at most n.
An n-local function is a function f from elements of A of norm at most
n into elements of A of norm at most 8n^2, where for all x in A of
norm p <= n, f|<x is an (A,R)*-set of norm at most 8p^2.
9. THE FINITE SYSTEM KERNEL THEOREM.
PROPOSITION 9.1. Finite System Kernel Theorem. There exists a Q-system
(A,R), A of norm at most 8n^2, such that every downward (A,R)-digraph
has a kernel containing its n-diagonal image under an n-local (A,R)-
function that maps 0 to 1.
PROPOSITION 9.2. Extended Finite System Kernel Theorem. There exists a
Q-system (A,R), A of norm at most 8n^2, such that every downward (A,R)-
digraph has a kernel containing its n-diagonal image under an n-local
(A,R)-function that maps 0 to 1 and 2 to 2.
THEOREM 9.3. Proposition 9.1 is provably equivalent to Con(HUGE) over
EFA.
THEOREM 9.4. Proposition 9.2 implies Con(I3) and is implied by
Con(I2), over EFA.
Note that the Finite System Kernel Theorem and the Extended Finite
System Kernel Theorem are explicitly Pi01.
10. THE FUTURE.
I am expecting an interesting general theory of NORMIFICATION, whereby
certain infinite statements are uniformly normed, resulting in Pi01
statements. The idea is to justify that the Pi01 statements are just
as mathematical as the original infinite statements from which they
came. The present normifications - perhaps modified - should be
special cases of general normification.
I should be able to go further into the large cardinal axioms that
violate the axiom of choice. However, a new idea is needed since the
obvious way to do this will get the axiom of choice, and hence
inconsistency.
I am expecting that the above approach based on kernels of digraphs
should be crafted into a tool that allows for a uniform correspondence
with the entire large cardinal hierarchy, from PA through j:V into V.
As a first step towards this, we already know how to make the SRP
statement relate to the HUGE statement:
There exists a Q-system (A,R) such that every downward (A,R)-digraph
has a kernel containing its diagonal image under a function whose
fixed points have a strict sup in A.
If we are just concerned with SRP, then we prefer the Infinite Upper
Shift Kernel Theorem.
We expect to be able to Template the Infinite Upper Shift Kernel
Theorem using partial rational piecewise linear functions from Q into
Q, as discussed in http://www.cs.nyu.edu/pipermail/fom/2010-October/015089.html
. We expect to be able to template the Infinite System Kernel Theorem
and the Extended Infinite System Kernel Theorem also.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 443rd 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 athttp://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
410: Kernel Function Theory 1 4/8/10 7:39PM
411: Free Generation Theory 1 4/13/10 2:55PM
412: Local Basis Construction Theory 1 4/17/10 11:23PM
413: Local Basis Construction Theory 2 4/20/10 1:51PM
414: Integer Decomposition Theory 4/23/10 12:45PM
415: Integer Decomposition Theory 2 4/24/10 3:49PM
416: Integer Decomposition Theory 3 4/26/10 7:04PM
417: Integer Decomposition Theory 4 4/28/10 6:25PM
418: Integer Decomposition Theory 5 4/29/10 4:08PM
419: Integer Decomposition Theory 6 5/4/10 10:39PM
420: Reduction Function Theory 1 5/17/10 2:53AM
421: Reduction Function Theory 2 5/19/10 12:00PM
422: Well Behaved Reduction Functions 1 5/23/10 4:12PM
423: Well Behaved Reduction Functions 2 5/27/10 3:01PM
424: Well Behaved Reduction Functions 3 5/29/10 8:06PM
425: Well Behaved Reduction Functions 4 5/31/10 5:05PM
426: Well Behaved Reduction Functions 5 6/2/10 12:43PM
427: Finite Games and Incompleteness 1 6/10/10 4:08PM
428: Typo Correction in #427 6/11/10 12:11AM
429: Finite Games and Incompleteness 2 6/16/10 7:26PM
430: Finite Games and Incompleteness 3 6/18/10 6:14PM
431: Finite Incompleteness/Combinatorially Simplest 6/20/10 11:22PM
432: Finite Games and Incompleteness 4 6/26/10 8:39PM
433: Finite Games and Incompleteness 5 6/27/10 3:33PM
434: Digraph Kernel Structure Theory 1 7/4/10 3:17PM
435: Kernel Structure Theory 1 7/5/10 5:55PM
436: Kernel Structure Theory 2 7/9/10 5:21PM
437: Twin Prime Polynomial 7/15/10 2:01PM
438: Twin Prime Polynomial/error 9/17/10 1:22PM
439: Twin Prime Polynomial/corrected 9/19/10 2:16PM
440: Finite Phase Transitions 9/26/10 1:28PM
441: Equational Representations 9/27/10 4:59PM
442: Kernel Structure Theory Restated 10/11/10 9:01PM
Harvey Friedman
More information about the FOM
mailing list