[FOM] 408: Kernel Tower Theory 2
Harvey Friedman
friedman at math.ohio-state.edu
Thu Apr 1 12:25:56 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
***********************************
We simplify the definition of progressive in http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
.
We eliminate the use of subexponential in http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
, through the use of "controlled progressive". (Actually, the
definition of subexponential had too small an estimate, which can be
fixed by replacing 2^i with (8kp!)^i, but now this is moot).
We need change section 7, http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
. This is fixed, and arguably improved, below, through the use of
isolated vertices.
******************
Kernel Tower Theory 2
by
Harvey M. Friedman
April 1, 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.
No change from http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
2. GRAPHS ON N^k.
No change from http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
3. LOCAL KERNELS AND KERNEL TOWERS.
No change from http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
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 all 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 the least positive integer n in fld(T1), the greatest integer in
fld(T2) below n is less than the greatest integer in fld(T3) below n.
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).
Let T be a tower in N^k of length p. We say that T is controlled
progressive if and only if for the i-th positive integer n in fld(T1),
1 <= i <= p, there are from 1 to (8ikp)! integers in fld(T_p) below n
that are greater than all integers in fld(T_p-1) below n.
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.
Replace "subexponential progressive" in Proposition 5.3 of http://www.cs.nyu.edu/pipermail/fom/2010-March/014507.html
with "controlled progressive".
6. FINITARY KERNEL TOWER THEOREMS.
Replace "subexponential progressive" in Propositions 6.1, 6.3 by
"controlled progressive".
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 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 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.
**********************
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
Harvey Friedman
More information about the FOM
mailing list