[FOM] 442: Kernel Structure Theory Restated
Harvey Friedman
friedman at math.ohio-state.edu
Sun Oct 10 20:44:12 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
For a proof sketch of the Infinite Upper Shift Kernel Theorem, see http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
section 1 #70.
THE UPPER SHIFT KERNEL THEOREMS
by
Harvey M. Friedman
Ohio State University
October 9, 2010
1. INFINITE UPPER SHIFT KERNEL THEOREM.
2. FINITE UPPER SHIFT KERNEL THEOREM.
3. TEMPLATES.
1. INFINITE UPPER SHIFT KERNEL THEOREM.
A digraph is a pair G = (V,E), where V is a nonempty set of vertices
and E containedin V^2 is a set of edges.
A kernel in (V,E) is commonly defined in graph theory sas a set S
containedin 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.
We now fix A containedin Q. There is a fundamental class of digraphs
associated with A, which we call the A-digraphs. An A,k-digraph is a
digraph (A^k,E), where E is an order invariant subset of A^2k in the
following sense. For all x,y in A^2k of the same order type, x in E
iff y in E.
Note that for each A containedin Q, there are finitely many A,k-graphs.
The A-digraphs are the A,k-digraphs, for some k >= 1.
The downward A-digraphs (A,k-digraphs) are the A-digraphs (A,k-
digraphs) such that for all edges (x,y), max(x) > max(y).
The upper shift ush:Q into Q is defined by ush(q) = q+1 if q >= 0; q
otherwise. This lifts to ush:Q^k into Q^k by acting coordinatewise. We
can now use ush for forward images of subsets of Q^k.
SRP stands for "stationary Ramsey property". We say that lambda has
the k-SRP if and only if lambda is an infinite cardinal, and every f:
[lambda]^k into 2 is constant on some [S]^k, where S is a stationary
subset of lambda. Here [S]^k is the set of all unordered k tuples from
S. Let SRP = ZFC + {there exists a cardinal lambda with the k-SRP}_k.
INFINITE UPPER SHIFT KERNEL THEOREM. There exists 0 in A containedin Q
such that every downward A-digraph has a kernel containing its upper
shift.
For a proof of the Infinite Upper Shift Kernel Theorem in ACA_0 +
Con(SRP), see http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
manuscript #70. We expect to use ideas from the BRT book, http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
, section 3, to show that the Infinite Upper Shift Kernel Theorem is
provably equivalent to Con(SRP) over ACA_0.
Note that we are talking about Con(SRP), rather than 1-Con(SRP).
Also, the A containedin Q in the Infinite Upper Shift Kernel THeorem
can be taken to be recursive in the Turing jump 0'. Also, the sequence
of kernels for the A-digraphs can be taken to be recursive in the
Turing jump 0'.
INFINITE UPPER SHIFT KERNEL THEOREM(k). There exists 0 in A
containedin Q such that every downward A,k-digraph has a kernel
containing its upper shift.
There is a small k such that the Infinite Upper Shift Kernel
Theorem(k) also has the same metamathematical properties. I.e., is
also provably equivalent, over ACA_0, to Con(SRP). Thus we do NOT get
a hierarchy on the dimension k.
It remains to give a small k. I have been postponing this kind of
investigation for some time, waiting for the independent statements to
stabilize.
2. FINITE UPPER SHIFT KERNEL THEOREM.
There are general principles that allow us to look at the form of the
Infinite Upper Shift Kernel Theorem(k) and see that it must be
provably equivalent to a Pi01 sentence over ACA_0. This is more
awkward for the Infinite Upper Shift Kernel Theorem.
However, we also want to find a simple explicitly Pi01 form of the
Infinite Upper Shift Kernel Theorem or the Infinite Upper Shift Kernel
Theorem(k).
We have settled on a quantitative approach. We are also considering
non quantitative approaches, but they haven't yet jelled into
something suitably simple.
We use convenient norms on Q^k. Let |q|, q in Q, be the least integer
n such that q can be written as a ratio of two integers of magnitude
at most n. Let |x|, x in Q^k, be max(|x_1|,...,|x_k|).
The n-upper shift of B containedin Q^k consists of the upper shifts of
the elements of B of norm at most n.
Let (B,E), B containedin Q^k, be a digraph. An n-kernel in (B,E) is a
set S containedin B such that
i. No element of S connects to any element of S.
ii. Every x in V\S of norm at most n connects to some element of S of
norm at most |x|^k + k.
FINITE UPPER SHIFT KERNEL THEOREM. For each n > k > 1, there exists
finite 0 in A containedin Q such that every downward A,k-digraph has
an n-kernel containing its n-upper shift. Furthermore, we can require
that every element of A have norm at most n^k+1.
Note that the Finite Upper Shift Kernel Theorem is explicitly Pi01.
The Finite Upper Shift Kernel Theorem is proved from the Infinite
Upper Shift Kernel Theorem by starting with 0 in A containedin Q from
the Infinite Upper Shift Kernel Theorem, choosing the provided
kernels, and building a tower of simultaneous approximations for A and
the kernels. Since the conditions in question are purely order
theoretic, we can move the elements of A around to conform to the norm
||.
For any fixed k > 1, we can use a compactness argument to go from the
Finite Upper Shift Kernel Theorem, to the Infinite Upper Shift Kernel
Theorem(k).
In this way, we see that the Finite Upper Shift Kernel Theorem is also
equivalent to Con(SRP) over ACA_0. We expect to be able to replace
ACA_0 here by EFA = exponential function arithmetic.
3. TEMPLATES.
Recall that the upper shift, ush, was first defined as a function
ush:Q into Q, and then extended to ush:Q^k into Q^k for use in forward
images of subsets of Q^k. This is the most obvious component to
Template. Ush is a special case of a rational partial piecewise linear
function from Q into Q.
TEMPLATE. Let f_1,...,f_n:Q into Q be rational partial piecewise
linear functions. There exists 0 in A containedin Q such that every
downward A-digraph has a kernel containing its images under f_1,...,f_n.
CONJECTURE. Every instance of the above Template is provable or
refutable in SRP+ = ZFC + "for all k there exists lambda such that
lambda has the k-SRP".
This should be within our present technology.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 442nd 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
Harvey Friedman
More information about the FOM
mailing list