[FOM] 412: Local Basis Construction Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Fri Apr 16 21:11:59 EDT 2010
THIS RESEARCH IS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
************************
The most thematic idea in these recent postings is that of a "basis
construction". In our context of N^k, the basis is unique, and the
usual constructions take infinitely many steps, and are deterministic.
There are no symmetry properties of the construction that would
distinguish it from any other construction in N^k.
However, we also consider more general basis constructions, that are
nondeterministic, and may only last for finitely many steps before
reaching an obstruction. These constructions can, in fact, always be
carried out without running into obstructions.
But here we present some simple symmetry properties that CANNOT be
maintained for infinitely many steps, but CAN be maintained for any
given finite number of steps. HOWEVER, this fact requires the use of
axioms far beyond ZFC. We need SRP+, and SRP does not suffice.
Although the local bases for R contained in N^k x N^k may not have
these strong symmetry properties, we CAN find a countable R* contained
in N*^k x N*^k, finitely isomorphic to R, with a local basis that does
have these strong symmetry properties. We don't emphasize this at this
time because the assertion asserts the existence of a countably
infinite set. But it does give a consequence of being able to maintain
the construction for any given finite number of steps. This is also
closely related to other statements involving the existence of
countably infinite sets - see section 9.
There is a reasonable thematic goal: to determine all such simple
symmetry properties that can always be realized for any given finite
number of steps in these basis constructions. We know a lot about
this, but nowhere near what we should, and will report on this later.
The kind of bases we consider are analogous to the myriad cases of
bases in mathematics, but are stronger. They are an adaptation of what
are called KERNELS IN DIGRAPHS. This is explained in detail in section
1.
***************************
LOCAL BASIS CONSTRUCTION THEORY 1
by
Harvey M. Friedman
April 16, 2010
1. BASES AND KERNELS
2. LOCAL BASES.
3. LOCAL BASIS CONSTRUCTIONS.
4. POLYNOMIALS AND LOWER YIELDS.
5. INFINITARY LOCAL BASIS CONSTRUCTION THEOREMS.
6. FINITARY LOCAL BASIS CONSTRUCTION THEOREMS.
7. ORDER INVARIANT LOCAL BASIS CONSTRUCTION THEOREMS.
8. UPPER SHIFT LOCAL BASIS THEOREM ON Q^k.
1. BASES AND KERNELS.
We use N for the set of all nonnegative integers. We fix R contained
in N^k x N^k.
For our purposes, we think of the relation
x R y and max(x) > max(y)
as asserting that "y is a reduction of x".
NOTE: We emphasize that we are NOT requiring that R, or the above
reduction relation, be transitive.
Note that we cannot keep reducing forever, because we are lowering the
max.
A basis for R is a set A contained in N^k such that
i. Every element of N^k is either in A or has a reduction in A.
ii. No element of A has a reduction in A.
In the special case where R is transitive, it is clear that the set of
elements of N^k that have no reduction forms the unique basis for R.
THEOREM 1.1. Every R contained in N^k x N^k has a unique basis.
We think of Theorem 1.1 as an adaptation of the famous Kernel Theorem
of von Neumann for our purposes. As the reader may not be aware of
kernel digraph theory, we provide this background here.
Kernels in digraphs represent a very active area of research in pure
and applied graph theory, game theory, computer science, and social
science. It has its origins with von Neumann in his book with
Morgenstern on Game Theory and Economic Behavior, 1944.
Kernels form a kind of "basis" for a digraph.
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 (graph theorists) say that S is a kernel in G if and only if
i. S is a set of vertices of G.
ii. There is no edge (x,y), x,y in S.
iii. For all x in V\S, there is an edge (x,y), y in S.
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. S is a set of vertices of G.
ii. There is no edge (x,y), x,y in S.
iii. For all x in V\S, there is an edge (y,x), y in S.
However, there are more references to kernels in digraphs than to
dominators in digraphs, so we will use kernels rather than dominators.
THEOREM 1.2. Finite Kernel Theorem. Every finite dag has a unique
kerrnel.
Theorem 1.2 is due 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.3. Infinite Kernel Theorem. If G is a digraph where all
walks are finite, then G has a unique kernel.
Obviously, if all walks are finite then there are no cycles.
THEOREM 1.4. The Infinite Kernel Theorem, for countable digraphs, is
provably equivalent to ATR_0 over RCA_0. The uniqueness (at most one)
part is provable in RCA_0, and the existence part is also provably
equivalent to ATR_0 over RCA_0.
It is obvious that Theorem 1.1 follows immediately from Theorem 1.3.
2. LOCAL BASES.
Let R contained in N^k x N^k and E contained in N.
A basis for R|E is a set A contained in E^k such that
i. Every element of E^k is either in A or has a reduction in A.
ii. No element of A has a reduction in A.
THEOREM 2.1. For all R contained in N^k x N^k and E contained in N,
there is a unique basis for R|E.
The various bases for the R|E, E contained in N, are called the local
bases of R.
We write fld(A), A contained in N^k, for the set of all coordinates of
elements of A.
THEOREM 2.2. Let W_k consist of the subsets A of N^k with field N,
such that for some R contained in N^k x N^k, every infinite local
basis for R is order isomorphic to A. Then W_k is finite, and every
element is elementary recursive (and better). In fact, the union of
the W_k's has an elementary enumeration, but not without repetition.
But the W_k are not really understandable.
THEOREM 2.3. There is no algorithm for computing the number of
elements of W_k as a function of k. There is a fixed k such that ZFC
cannot determine the number of elements of W_k. Moreover, no
consistent consequence of our large cardinal axioms is sufficient.
These results hold even if we use "isomorphic" rather than "order
isomorphic".
NOTE: THE COUNT FUNCTION OF k ABOVE IS A PARTICULARLY NATURAL AND
INTERESTING (DOUBLE EXPONENTIALLY BOUNDED) NONRECURSIVE FUNCTION FROM
N INTO N.
Note that Theorem 2.3 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 2.3, and
whether the smallest k depends on whether we are using ZFC, large
cardinals, or weak fragments of ZFC.
NOTE: Theorem 2.3 corrects some earlier versions.
3. LOCAL BASIS CONSTRUCTIONS.
Fix R contained in N^k x N^k. We now introduce a particular kind of
natural construction that builds a local basis for R. That is, if the
construction is successfully continued for infinitely many steps, it
will yield a local basis for R.
We start with nonempty E contained in N.
We now build A_1 contained in N^k as follows. For each x in E^k, put
x* in A_1, where x* = x or x* is a reduction of x. Now check to make
sure that A_1 is free. If so, then we can continue the construction.
If not, then the construction is blocked.
Suppose A_1,...,A_i have been built, i >= 1. We build A_i+1 contained
in N^k, as follows. For each x in (E union fld(A_1) union ... union
fld(A_i))^k, put x in A_i+1, or put a reduction of x in A_i+1. Check
to make sure that A_1 union ... union A_i+1 is free.
Suppose this construction can be carried out for infinitely many
steps. Let A be the union of the A's. Then obviously A is a basis for
R|fld(A), and E is contained in fld(A). In particular, A is a local
basis for R.
Suppose that we carry out the construction to A_1,...,A_p, p >= 1,
where we check that A_1 union ... union A_p is free - and then quit of
our own free will. Then we say that the construction has length p.
We use E for the initial set. We can think of the first stage in the
construction as a function from E^k into N^k given by the * operation
above.
TEMPLATE. Every R contained in N^k x N^k has a local basis
construction of any given finite length where the first stage in the
construction has nice symmetry properties.
We aim for a complete understanding of all instances of this Template.
We know that certain simple symmetry properties arise from applying
piecewise polynomials with coefficients from N. This does motivate the
simple symmetry properties chosen. Unfortunately, it appears that
piecewise polynomials with coefficients from N give us some symmetry
properties that make the Template false.
We are developing the right kind of complete description of all
symmetry properties that make the Template true. It will be a very
sensible combinatorial description, closely connected with classical
Ramsey theory from 1930. Any proof of the correctness of this or any
other combinatorial description must climb up the SRP hierarchy. Also,
there are robustness properties for the symmetry properties that make
the Template true, and the verification of these robustness properties
also must climb up the SRP hierarchy.
4. POLYNOMIALS AND LOWER YIELDS.
Let f:N^k into N^k. The lower yield of E contained in N consists of
the set of all coordinates of values of f on E^k that are less than
min(E).
More generally, the lower yield of E' contained in E is the set of all
coordinates of values of f on E'^k that are less than min(E').
THEOREM 4.1. Let f:N^k into N^k be a piecewise polynomial with
coefficients from N. Then f is well behaved on any set E of
sufficiently large double factorials, in the following special sense.
The lower yield of any two equinumerous subsets of E, or subsets of E
with at least k elements, are the same.
Note that this is false for f:N into N given by
f(x) = x-1 if x > 0; 0 otherwise.
We can give another form as follows.
THEOREM 4.2. Let f:N^k into N^k be a piecewise polynomial with
coefficients from N, and E be an infinite subset of N. There exists an
infinite subset E' of E such that the lower yield of any two
equinumerous subsets of E, or subsets of E with at least k elements,
are the same.
5. INFINITARY LOCAL BASIS CONSTRUCTION THEOREMS.
PROPOSITION 5.1. Every R contained in N^k x N^k has a length 3 (length
k, length p) local basis construction with infinite E, where the lower
yield of any two k element subsets of E are the same.
Here is the sharpest statement of this kind.
PROPOSITION 5.2. Every R contained in N^k x N^k has a length 3 (length
k, length p) local basis construction with infinite E, where the lower
yield of any two equinumerous subsets of E, or subsets of E with at
least k elements, are the same.
THEOREM 5.3. Propositions 5.1, 5.2 (all six forms) are provable in SRP
+ but not in any consequence of SRP consistent with RCA_0.
Propositions 5.1, 5.2 (all three forms) are provably equivalent to
Con(SRP) over ACA'.
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. 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 LOCAL BASIS CONSTRUCTION THEOREMS.
Here are the semifinite versions.
PROPOSITION 6.1. Every R contained in N^k x N^k has a length 3 (length
k, length p) local basis construction, where the lower yield of any
two k element subsets of the k+1 element E are the same.
PROPOSITION 6.2. Every R contained in N^k x N^k has a length 3 (length
k, length p) local basis construction, where the lower yield of any
two equinumerous subsets of the k element E are the same.
There are two paths to an explicitly Pi01 form of Propositions 6.1,
6.2. One is to replace N with a large initial segment of N, which we
do now. The other path is followed in section 6, using the order
invariance of R.
In the context of R contained in {0,...,t}^k x {0,...,t}^k we assume
that all local basis constructions live in {0,...,t} or {0,...,t}^k.
PROPOSITION 6.3. For all t >> k, every R contained in {0,...,t}^k x
{0,...,t}^k has a length 3 (length k, length p) local basis
construction, where the lower yield of any two k element subsets of
the k+1 element E are the same. It is sufficient for t to be greater
than the length 8k exponential stack of 2's (8kp if we use p).
PROPOSITION 6.4. For all t >> k, every R contained in {0,...,t}^k x
{0,...,t}^k has a length 3 (length k, length p) local basis
construction, where the lower yield of any two equinumerous subsets of
the k element E are the same. It is sufficient for t to be greater
than the length 8k exponential stack of 2's (8kp if we use p).
Obviously Propositions 6.3 - 6.4 are explicitly Pi01.
THEOREM 6.5. Propositions 6.1 - 6.4 are provable in SRP+, but none
from any consequence of SRP consistent with SEFA. Propositions 6.1 -
6.4 are provably equivalent to Con(SRP) over SEFA.
Here SEFA is super exponential function arithmetic.
7. ORDER INVARIANT LOCAL BASIS CONSTRUCTION THEOREMS.
We say that x,y in N^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 S contained in N^k
is order invariant if and only if S is the union of equivalence
classes under order equivalence. We aay that R contained in N^k x N^k
is order invariant if and only if R is order invariant as a subset of
N^2k.
PROPOSITION 7.1. Every order invariant R contained in N^k x N^k has a
length 3 (length k, length p) local basis construction, where the
lower yield of any two k element subsets of the k+1 element E are the
same. Furthermore, we can find E living below (8k)! ((8kp)! if we use
p).
PROPOSITION 7.2. Every order R contained in N^k x N^k has a length 3
(length k, length p) local basis construction, where the lower yield
of any two equinumerous subsets of the k element E are the same.
Furthermore, we can find E living below (8k)! ((8kp)! if we use p).
PROPOSITION 7.3. For all r > (8k)!!, every order invariant R contained
in N^k x N^k has a length 3 (length k) local basis construction,
starting with {r,r^2,...,r^k+1}, where {r,r^2,...,r^k} and
{r^2,r^3,...,r^k+1} have the same lower yield.
Obviously, Propositions 7.1 - 7.3 are explicitly Pi01.
THEOREM 7.4. Propositions 7.1 - 7.3 are provable in SRP+, but none
from any consequence of SRP consistent with EFA. Propositions 7.1 -
7.3 are provably equivalent to Con(SRP) over EFA.
8. LOCAL UPPER SHIFT KERNEL THEOREM ON Q^k.
If we are willing to consider statements that assert the existence of
a countably infinite set, then major new possibilities for necessary
uses of large cardinals arise.
We extend order equivalence to Q^k in the obvious way.
Let G be a digraph on Q^k. We say x is isolated in G if and only if x
is in Q^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 8.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. I.e., a local kernel is a kernel of
some R|E^k, E contained in Q.
THEOREM 8.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 8.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 8.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 8.4. Proposition 8.3 is provable in SRP+ but not from any
consequence of SRP consistent with RCA_0. Proposition 8.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.
We are looking forward to a major structure theory for local kernels
of order invariant digraphs on Q^k, where necessary uses of large
cardinals abound.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 412th 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
Harvey Friedman
More information about the FOM
mailing list