[FOM] 437: Kernel Structure Theory 3

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

######################################################################

I wrote 436: Kernel Structure Theory 2 http://www.cs.nyu.edu/pipermail/fom/2010-July/014884.html 
  on July 9, 2010, about a month ago. I then took time off to do some  
writing.

I am now coming back to this - at least briefly. I still have some  
further writing obligations, however.

I already see that there are two mistakes in section 4, in the  
definition of upper shift tower. (From the correct starting definition  
in section 5, one can see what the mistakes were).

I wrote

> An upper shift tower is a finite sequence A_1,...,A_n contained in Q^k
> such that for all 1 <= i < n, for all x in A_i, the result of adding 1
> to all coordinates of x, lies in A_i+1.

I should have written

An upper shift tower is a finite sequence A_1,...,A_n contained in Q^k
such that for all 1 <= i < n, A_i union ush(A_i) is contained in A_i+1.

The point is that I meant to say that an upper shift tower is at least  
a tower, and I should have added 1 to all nonnegative coordinates of x.

Accordingly, I will give a self contained restatement, and also add a  
new section 6, which starts a unification of Kernel Structure Theory  
with Boolean Relation Theory.

I also make some small changes in notation from http://www.cs.nyu.edu/pipermail/fom/2010-July/014884.html

The main urgency with regard to Kernel Structure Theory and the just  
developing Order Invariant Image Theory (section 6) is to give a small  
value of the dimension k which is sufficient for the unprovability  
results.

THIS POSTING IS ENTIRELY SELF CONTAINED.

KERNEL STRUCTURE THEORY 3
by
Harvey M. Friedman
August 8, 2010

1. DIGRAPHS, KERNELS, DOWNWARD, ORDER INVARIANCE.
2. KERNEL CLOSURE THEOREM.
3. KERNEL CLOSURE TEMPLATES.
4. KERNEL TOWER THEOREMS.
5. KERNEL TOWER TEMPLATES.
6. TOWARD BOOLEAN RELATION THEORY.

1. DIGRAPHS, KERNELS, DOWNWARD, ORDER INVARIANCE.

A digraph is a pair G = (V,R), where R is contained in V x V. The
vertices of G are the elements of V, and the edges of G are the
elements of R. We say that G is a digraph on V.

We say that E is independent in G if and only if E is a subset of V,
where there is no edge from any element of E to any element of E.

We say that E is a kernel in G if and only if E is independent in G,
and for all x in V\E, there is an edge from x to some element of E.

A kernel of A in G is a kernel of the induced subdigraph G|A.

Let Q be the set of all rational numbers. We say that a digraph on Q^k
is downward if and only if for all edges (x,y), max(x) > max(y).

We say that x,y in Q^k are order equivalent if and only if for all
1 <= i,j <= k, x_i < x_j iff y_i < y_j.

We say that A contained in Q^k is order invariant if and only if for
all order equivalent x,y in Q^k, x in A iff y in A.

A digraph on Q^k is order invariant if and only if its edge set is
order invariant as a subset of Q^2k.

2. KERNEL CLOSURE THEOREM.

Let f:Q into Q and A be a subset of Q^k. We say that A is f closed if
and only if for all (x_1,...,x_k) in A, (f(x_1),...,f(x_k)) is in A.

The upper shift ush:Q into Q is given by ush(x) = x+1 if x >= 0; x
otherwise.

PROPOSITION 2.1. Kernel Closure Theorem. In every downward order
invariant digraph on Q^k, some (E union {0})^k has an upper shift
closed kernel.

THEOREM 2.2. Proposition 3.1 is provable in SRP+ but not from any
consequence of SRP that is consistent with RCA_0. Proposition 2.1 is
provably equivalent, over WKL_0, to Con(SRP). These results hold if we
fix k to be any particular sufficiently large integer in Theorem 2.1.
(We guess that k >= 4 suffices, but we need to take a serious look).

Here 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. The
k-SRP asserts that every partition of the unordered k-tuples from
lambda into two pieces has a homogeneous set that is a stationary
subset of lambda.

3. KERNEL CLOSURE TEMPLATES.

What can we use in the Kernel Closure Theorem other than the upper
shift?

We look for a particularly illuminating form of an answer to this
question. Note that the upper shift is a function that can be
presented in a rather concrete way. In particular, the upper shift is
rational semilinear - a well known and well studied category of objects.

Specifically, we say that A contained in Q^k is rational semilinear if
and only if it is in the Boolean algebra generated by the open
rational half planes

q_1 x_1 + ... + q_k x_k + q_k+1 > 0

where q_1,...,q_k+1 are rationals. This is the same as being a finite
union of finite intersections of rational half planes

q_1 x_1 + ... + q_k x_k + q_k+1 > 0
q_1 x_1 + ... + q_k x_k + q_k+1 >= 0.

We say that a function is rational semilinear if and only if its graph
is rational semilinear.

TEMPLATE A. Let f:Q into Q be rational semilinear. In every downward
order invariant digraph on Q^k, some (E union {0})^k has an f closed
kernel.

Note that there are a countably infinite number of instances of
Template A - one for each rational semilinear function from Q into Q.

Template A is analyzable in SRP+ in the following sense.

THEOREM 3.1. Every instance of Template A is provable or refutable in
SRP+. In fact, every instance of Template A is provable in WKL_0 +
Con(SRP) or refutable in RCA_0. It is not the case that every instance
of Template A is provable or refutable in SRP - unless SRP proves its
own inconsistency. This can't happen, according to SRP+.

We now consider a more difficult challenge. Let f:Q^k into Q^k and A
be a subset of Q^k. We say that A is f closed if and only if for all x
in A, f(x) is in A.

TEMPLATE B. Let f:Q^k into Q^k be rational semilinear. In every
downward order invariant digraph on Q^k, some (E union {0})^k has an f
closed kernel.

Obviously every instance of Template A is provably equivalent to an
instance of Template B by lifting rational semilinear f:Q into Q to
the corresponding rational semilinear g:Q^k into Q^k by acting
coordinatewise.

We can also template the domain set in Templates A,B - i.e, template
the construction (E union {0})^k.

It is highly preferable to treat the domain set and the kernel set
uniformly. The natural way to do this is to use P contained in Q^3k in
the following way.

Let A be contained in Q^k. We say that A is P closed if and only if
P[A^2] is contained in A.

But before taking the full plunge, we can just template on the kernel
side - and also use P contained in Q^2k. Thus we are led to these two
preliminary Templates which are modifications of Template B.

TEMPLATE C. Let P contained in Q^2k be rational semilinear. In every
downward order invariant digraph on Q^k, some (E union {0})^k has a P
closed kernel.

TEMPLATE D. Let P contained in Q^3k be rational semilinear. In every
downward order invariant digraph on Q^k, some (E union {0})^k has a P
closed kernel.

Now we come to the Templating of both the domain set and the kernel set.

TEMPLATE E. Let P,J contained in Q^3k be rational semilinear. In every
downward order invariant digraph on Q^k, some nonempty P closed set
has a J closed kernel.

 From the Kernel Closure Theorem (Theorem 2.1), we know that the
following instances of Template E are provable in SRP+ but not in SRP
(assuming SRP is consistent). Let k be sufficiently large (probably
k = 4 will do, although I need to look at this closely).

P_k(x,y,z) if and only if x,y,z in Q^k and every coordinate of z is a
coordinate of x, a coordinate of y, or 0.

J_k(x,y,z) if and only if x,y,z in Q^k and z is obtained by starting
with x or y, and then adding 1 to all nonnegative coordinates.

4. KERNEL TOWER THEOREMS.

For A contained in Q^k, define ush(A) = {ush(x): x in A}. Define  
fld(A) to be the set of all coordinates of elements of A.

A sharp tower is a finite sequence A_1,...,A_n contained in Q^k such
that for all 1 <= i < n, (fld(A_i) union {0})^k is contained in A_i+1.

An upper shift tower is a finite sequence A_1,...,A_n contained in Q^k
such that for all 1 <= i < n, A_i union ush(A_i) is contained in A_i+1.

PROPOSITION 4.1. In all downward order invariant digraphs on Q^k,
there is a sharp tower of finite sets of length r with an upper shift
tower of kernels.

Note that Proposition 4.1 is explicitly Pi02. It can be seen that for
Proposition 4.1, there are a priori upper bounds for the finite sets
that put this in explicitly Pi01 form. However, we can also
incorporate a bound directly.

PROPOSITION 4.2. In all downward order invariant digraphs on Q^k,
there is a sharp tower of finite sets of length r, involving only
numerators and denominators of magnitude at most (8kr)!!, with an
upper shift tower of kernels.

Note that Proposition 4.2 is explicitly Pi01.

THEOREM 4.3. Propositions 4.1, 4.2 are provable in SRP+ but not from
any consequence of SRP that is consistent with EFA. Propositions 4.1,
4.2 are provably equivalent, over EFA, to Con(SRP). These results hold
if we fix k to be any particular sufficiently large integer in
Propositions 4.1, 4.2. (We guess that k >= 4 suffices, but we need to
take a serious look).

EFA is exponential function arithmetic.

5. KERNEL TOWER TEMPLATES.

A P closed tower is a finite sequence A_1,...,A_n contained in Q^k
such that for all 1 <= i < n, A_i union P[A_i^2) is contained in A_i+1.

TEMPLATE F. P,J contained in Q^3k be rational semilinear with
coefficients from {0,1}. In every downward order invariant graph on
Q^k, some P closed tower of nonempty finite sets of length r has a J
closed tower of kernels.

TEMPLATE G. P,J contained in Q^3k be rational semilinear with
coefficients from {0,1}. In every downward order invariant graph on
Q^k, some P closed tower of nonempty sets of length r, involving only
numerators and denominators of magnitude at most (8kr)!!, has a J
closed tower of kernels.

Note that Propositions 4.1 and 4.2 are instances of Templates F,G,
respectively;. Hence Templates F,G cannot be analyzed in SRP+,
provided SRP is consistent.

6. TOWARD BOOLEAN RELATION THEORY.

Here we start a reconciliation with Boolean Relation Theory.

 From the point of view of BRT, the kernel construction has no special  
significance.

We use three ways of forward imaging A contained in Q^k.

a. A#. This is (fld(A union {0})^k.

b. ush(A). This is the upper shift of A, used previously.

c. RA = {z in Q^k: there exists x,y in Q^k such that R(x,y}}.

We have the usual notion of R contained in Q^2k being order invariant,  
that we have used previously. We say that R contained in Q^2k is  
strictly dominating if and only if R(x,y) implies max(x) < max(y).

TEMPLATE H. Let BOOL(T,U,V,W) be one of the 2^16 Boolean relations  
between four subsets of Q^k. For all strictly dominating order  
invariant R contained in Q^2k, there exists A contained in Q^k such  
that BOOL(A,A#,ush(A),RA) holds.

We know that the following instance of Template 6.1 is provably  
equivalent, in WKL_0, to Con(SRP):

For all order invariant R contained in Q^2k, there exists A contained  
in Q^k such that ush(A) is contained in A = A#\RA.

CONJECTURE. Every instance of Template H is provable or refutable in  
SRP+. In fact, every instance of Template H is provable in WKL_0 +  
Con(SRP) or refutable in RCA_0.

We have started to build the classification for Template H, and except  
that this should take at most 3 months full time effort. I don't have  
that kind of time at the moment.

We expect, that if we were to define A# = fld(A union {q})^k, where q  
is any rational other than 0, then all instances of Template H would  
be provable or refutable in ACA.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 437th 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  8:42PM

Harvey Friedman