[FOM] 411: Free Generation Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Tue Apr 13 01:01:28 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
***********************************
We now prefer to work only with everywhere defined functions from N^k
into N^k, and talk about free generation. The strongest notion is that
the entire range is free. The approximate forms are that the p spans
of finite and infinite sets of nonnegative integers are free.
We have been shifting back and forth from graph theoretic to ordinary
notation. Now we like ordinary notation, but we state the connections.
We believe that we are still continuing to make the Pi01 sentences
steadily more quotable, vivid, natural, and ready to connect to
various topics in math.
Soon we will take what we have learned and apply it to get improved
Pi01 statements corresponding to measurables to I3/I2.
Free Generation Theory 1
by
Harvey M. Friedman
April 13, 2010
1. FREE GENERATION THEOREM.
2. LOCAL FREE GENERATION THEOREM.
3. FREE SPANS, LOWER PARTS, AND ADJACENT SETS.
4. INFINITARY FREE GENERATION THEOREMS.
5. FINITARY FREE GENERATION THEOREMS.
6. ORDER INVARIANT FREE GENERATION THEOREMS.
7. LOCAL UPPER SHIFT KERNEL THEOREM ON Q^k.
1. FREE GENERATION THEOREMS.
We use N for the set of all nonnegative integers. We consider
relations R contained in N^k x N^k. A choice function for R is a
function f:N^k into N^k such that for all x in N^k, x R f(x).
We say that R is reflexively regressive if and only if
i. For all x in N^k, x R x,
ii. For all distinct x,y in N^k, if x R y then max(x) > max(y).
RECOMMENDED ABBREVIATION: rr for reflexively regressive. Here we will
continue to write it out.
Obviously, the identity function on N^k is a choice function for every
reflexively regressive R contained in N^k x N^k.
We say that A is R free if and only if no two distinct elements of A
are related by R.
THEOREM 1.1. Free Generation Theorem. Every reflexively regressive R
contained in N^k x N^k has a choice function whose range is R free.
This R free range depends only on R and not on the choice function.
This R free range is the unique kernel of the graph with vertex set
N^k whose edge set is the irreflexive part of R.
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
paths are finite, then G has a unique kernel.
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 useful to have a simple condition on graphs on N^k that implies
that all paths are finite, so that we obtain a unique kernel. (There
is a large literature on sufficient conditions for their being a
kernel, or unique kernel, in a digraph).
We say that G is a regressive digraph on N^k if and only if G is a
digraph with vertex set N^k, where for all edges (x,y), max(x) > max(y).
THEOREM 1.5. Every regressive digraph on N^k has a unique kernel.
2. LOCAL FREE GENERATION THEOREM.
Let R contained in N^k x N^k be reflexively regressive. A local choice
function for R is a function f:E^k into E^k such that for all x in
E^k, x R f(x). We say that E is the field of f.
THEOREM 2.1. Local Free Generation Theorem. Let E contained in N. The
following are equivalent.
i. Every reflexively regressive R contained in N^k x N^k has a local
choice function with field E whose range is R free.
ii. E is well ordered.
For A contained in N^k, we define the field of A to be the set of all
coordinates of elements of A.
A local kernel of R is the unique kernel of some G|E^k. Here G|E^k is
the subgraph of G induced by E^k.
THEOREM 2.2. There is a unique finite set W_k of subsets of N^k with
field N such that
i. Every reflexively regressive R contained in N^k x N^k with an
infinite local kernel has a local kernel order isomorphic to an
element of W_k.
ii. No proper subset of W_k has property i.
The elements of W_k are elementary recursive (and better). In fact,
the union of the W_k's has an elementary recursive enumeration, but
not without repetitions.
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.
3. FREE SPANS, LOWER PARTS, AND ADJACENT SETS.
Let f:N^k into N^k and E be contained in N. We define the i-span of f
on E by induction on i >= 1 as follows.
The 1-span of f on E is the set of all values of f at arguments from
E. The i+1-span of f on E is the set of all values of f at coordinates
of elements of the i-span of f.
NOTE: From some points of view, it is more natural to use the
cumulative i-span, whereby the i+1-span of f on E would be the set of
all values of f at coordinates of elements of the j-spans of f, 1 <= j
<= i. The use of the cumulative i-span would not affect our results.
The lower part of the i-span of f on E is the set of all elements of
the i-span of f on E whose max is less than min(E).
We say that A,B contained in N are adjacent if and only if
i. B is the result of deleting the first element from A and appending
a new integer higher than max(A); or
ii. B is the result of deleting the first element from the infinite
set A.
THEOREM 3.1. Infinitary Affine Generation Theorem. Let T:N^k into N^k
be affine and n >> k,p. The p-spans of T on {n,n^2,...} and
{n^2,n^3,...} have the same lower part.
THEOREM 3.2. Finitary Affine Generation Theorem. Let T:N^k into N^k be
affine and n >> k,p,r. The p-spans of T on {n,n^2,...,n^r} and
{n^2,n^3,...,n^r+1} have the same lower part.
THEOREM 3.3. Infinitary Piecewise Linear Generation Theorem. Let T:N^k
into N^k be piecewise linear with nonnegative coefficients, and n >>
k,p. The p-spans of T on {n,n^2,...} and {n^2,n^3,...} have the same
lower part.
THEOREM 3.4. Finitary Piecewise Linear Generation Theorem. Let T:N^k
into N^k be piecewise linear with nonnegative coefficients, and n >>
k,p,r. The p-spans of T on {n,n^2,...,n^r} and {n^2,n^3,...,n^r+1}
have the same lower part.
4. INFINITARY FREE GENERATION THEOREMS.
PROPOSITION 4.1. Every reflexively regressive R contained in N^k x N^k
has a choice function whose 3-spans on some two infinite adjacent sets
are R free and have the same lower part.
PROPOSITION 4.2. Every reflexively regressive R contained in N^k x N^k
has a choice function whose p-spans on some two infinite adjacent sets
are R free and have the same lower part.
Note that these Propositions assert that we can find a choice function
which
i. Behaves somewhat like the unique choice function whose range is R
free.
ii. Behaves somewhat like an affine function or a piecewise linear
function with nonnegative coefficients.
THEOREM 4.3. Propositions 4.1, 4.2 are provable in SRP+ but not in any
consequence of SRP consistent with RCA_0. Propositions 4.1, 4.2 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".
5. FINITARY FREE GENERATION THEOREMS.
Let R be contained in N^k x N^k. We can consider finite choice
functions f. Here we have x R f(x) for all x in dom(f). In order for
the p span of f to exist, we require that all relevant values of f
exist. Obviously, R will have finite choice functions whose p span
exists.
PROPOSITION 5.1. Every reflexively regressive R contained in N^k x N^k
has a finite choice function whose 3-spans on some two k element
adjacent sets are R free and have the same lower part.
PROPOSITION 5.2. Every reflexively regressive R contained in N^k x N^k
has a finite choice function whose p-spans on some two r element
adjacent sets are R free and have the same lower part.
Propositions 5.1, 5.2 are semifinite in the sense that although we
have an infinitary input, we get a finitary output.
There are two paths to an explicitly Pi01 form of Propositions 5.1,
5.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.
In the context of R contained in {0,...,t}^k x {0,...,t}^k we assume
that all sets and functions live in {0,...,t} or {0,...,t}^k.
PROPOSITION 5.3. For all t >> k, every reflexively regressive R
contained in {0,...,t}^k x {0,...,t}^k has a choice function whose 3-
spans on some two k element adjacent sets are R free and have the same
lower part. It is sufficient for t to be greater than the length 8k
exponential stack of 2's.
PROPOSITION 5.4. For all t >> k,p,r every reflexively regressive R
contained in {0,...,t}^k x {0,...,t}^k has a choice function whose p-
spans on some two r element adjacent sets are R free have the same
lower part. It is sufficient for t to be greater than the length 8kpr
exponential stack of 2's.
Obviously Propositions 5.3, 5.4 are explicitly Pi01.
THEOREM 5.5. Propositions 5.1 - 5.4 are provable in SMAH+, but none
from any consequence of SRP consistent with SEFA. Propositions 5.1 -
5.4 are provably equivalent to Con(SRP) over SEFA.
Here SEFA is super exponential function arithmetic.
6. ORDER INVARIANT FREE GENERATION 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 a subset of N^k is order invariant if and only if it is
the union of equivalence classes of N^k under order equivalence.
We say 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 6.1. Every order invariant reflexively regressive R
contained in N^k x N^k has a finite choice function whose 3-spans on
some two k element adjacent sets are R free and have the same lower
part. Furthermore, we can require that the sets are {n,n^2,...,n^k},
{n^2,...,n^k+1], n < (8k)!, and the function maps {0,...,n^k+1} into
{0,...,n^k+1}.
PROPOSITION 6.2. Every order invariant reflexively regressive R
contained in N^k x N^k has a finite choice function whose p-spans on
some two r element adjacent sets are R free and have the same lower
part. Furthermore, we can require that the sets are {n,n^2,...,n^k},
{n^2,...,n^k+1], n < (8kpr)!, and the function maps {0,...,n^k+1} into
{0,...,n^k+1}.
Obviously Propositions 6.1, 6.2 are explicitly Pi01.
PROPOSITION 6.1. Every order invariant reflexively regressive R
contained in N^k x N^k has a finite choice function whose 3-spans on
some two k element adjacent sets are R free and have the same lower
part. Furthermore, we can require that the function and the sets live
below (8k)!.
PROPOSITION 6.2. Every order invariant reflexively regressive R
contained in N^k x N^k has a finite choice function whose p-spans on
some two r element adjacent sets are R free and have the same lower
part. Furthermore, we can require that the function and the sets live
below (8kpr)!.
THEOREM 6.3. Propositions 6.1, 6.2 are provable in SMAH+, but none
from any consequence of SRP consistent with EFA. Propositions 6.1, 6.2
are provably equivalent to Con(SRP) over EFA.
Here EFA is exponential function arithmetic.
7. LOCAL UPPER SHIFT KERNEL THEOREM ON Q^k.
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 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 6.
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. I.e., a local kernel is a kernel of
some R|E^k, E contained in Q.
THEOREM 7.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 7.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 7.4. Proposition 7.3 is provable in SRP+ but not from any
consequence 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 411th 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
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
Harvey Friedman
More information about the FOM
mailing list