[FOM] 400: New Free Reduction Theory 3
Harvey Friedman
friedman at math.ohio-state.edu
Sun Mar 14 11:55:09 EDT 2010
This differs from New Free Reduction Theory 2 http://www.cs.nyu.edu/pipermail/fom/2010-March/014446.html
only in some strategic changes in terminology. There has been no
significant advance at the SRP level since then. However, I intend to
post on the large large cardinals shortly.
NEW FREE REDUCTION THEORY 3
by
Harvey Friedman
March 14, 2010
1. VALLEY COUNTING THEOREMS. (no change)
2. FREE REDUCTION THEOREMS. (terminology changes)
3. FREE REDUCTION VALLEY THEOREMS - infinite.
4. FREE REDUCTION VALLEY THEOREMS - finite.
5. ORDER INVARIANCE.
1. VALLEY COUNTING THEOREMS.
We use N for the set of all nonnegative integers. We focus on the
spaces N^k. For our purposes, the natural subspaces of N^k are the
sets E^k, where E is contained in N^k. These subsapaces are called the
cubes (in N^k). The length of a cube E^k is the cardinality of E.
Let f:N^k into N^k be partial and A be contained in the domain of f.
We say that n is a valley of f over A if and only if n is a coordinate
of some f(x), x in A, where min(x) > n.
EXAMPLE. Let f:N^2 into N^2 be given by f(n,m) = (m,2|n-m|). The
valleys of f over N^k are the even elements of N.
THEOREM 1.1. The following is false, even for k = 1. Every f:N^k into
N^k has finitely many valleys over some infinite cube.
THEOREM 1.2. The following is false, even for k = 1. For all r >= 1,
every f:N^k into N^k has at most k^k+1 valleys over some length r cube.
THEOREM 1.3. Valley Counting Theorem - infinite. For all k,r >= 1,
every f:N^k into N^k has at most rk^k+1 valleys over some length r cube.
THEOREM 1.4. Valley Counting Theorem - finite. For all t >> k,r >= 1,
every f:{0,...,t}^k into {0,...,t}^k has at most rk^k+1 valleys over
some length r cube.
THEOREM 1.5. Theorems 1.3, 1.4 are provable in ACA' but not in ACA_0.
They are provably equivalent to 1-Con(PA) over RCA_0. Theorem 1.4 is
not provable in PA = Peano Arithmetic. Theorem 1.4 is provably
equivalent to 1-Con(PA) over SEFA = super exponential function
arithmetic.
Here ACA' = ACA_0 + "for all n,x, the n-th Turing jump of x exists".
2. FREE REDUCTION THEOREMS.
We use N for the set of all nonnegative integers. By relation, we
always mean binary relation.
Fix a relation R on N^k and a partial function f:N^k into N^k. We view
R as a subset of N^k x N^k.
We write x R y for (x,y) in R. We write dom(f) for the domain of f.
We say that y is a strict R reduction of x if and only if max(x) >
max(y) and x R y. We say that y is an R reduction of x if and only if
y = x lies in N^k, or y is a strict R reduction of x.
We say that f:C into D is an R reduction if and only if
i. C,D are cubes in N^k.
ii. For all x in C, f(x) is an R reduction of x.
We say that f is a free R reduction if and only if f is an R
reduction, where no value of f is a strict R reduction of any value of
f.
THEOREM 2.1. Free Reduction Theorem. For every cube C in N^k, every
relation on N^k has a free reduction f:C into C. Furthermore, its
range is uniquely determined by the cube and the relation.
A continuation of a free R reduction f:C into D is a free R reduction
g:D into E that extends f.
A continuable free R reduction is a free R reduction with a
continuation.
3. FREE REDUCTION VALLEY THEOREMS - infinite.
We now combine Valley Theory and Free Reduction Theory in an obvious
way.
PROPOSITION 3.1. Every relation on N^k has an free reduction with
finitely many valleys over some infinite subcube of its domain.
We can prove Proposition 3.1 by going well beyond the usual ZFC
axioms. However, we do not yet know if Proposition 3.1 can be proved
in ZFC.
PROPOSITION 3.2. Every relation on N^k has a continuable free
reduction with finitely many valleys over some infinite subcube of its
domain.
We know that the sharper Proposition 3.2 is independent of ZFC.
PROPOSITION 3.3. Every relation on N^k has a p times continuable free
reduction with finitely many valleys over some infinite subcube of its
domain.
The "limit" of these Propositions is as follows.
THEOREM 3.4. The following are false. Every relation on N^k has an
infinitely many times continuable free reduction with finitely many
valleys over some infinite subcube of its domain. Every relation on
N^k has an injective free reduction with finitely many valleys over an
infinite subcube of its domain.
THEOREM 3.5. Proposition 3.1 is provable in SRP+, and also in ACA' +
Con(SRP). Propositions 3.2, 3.3 are provable in SRP+ but not from any
consequence of SRP consistent with RCA_0. They are each 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 and x contained in omega, the n-th
Turing jump of x exists".
4. FREE REDUCTION VALLEY THEOREMS - finite.
We now work with relations on {1,...,t}^k. Here the reductions are
required to have domain and codomain to be subcubes of {1,...,t}^k.
PROPOSITION 4.1. For all t >> k,r >= 1, every relation on {1,...,t}^k
has a free reduction with at most k^k+1 valleys over a length r
subcube of its domain. Furthermore, it suffices that t is bigger than
an exponential stack of 2's of length 8kr (this is a very crude but
safe upper bound).
PROPOSITION 4.2. For all t >> k,r >= 1, every relation on {1,...,t}^k
has a continuable free reduction with at most k^k+1 valleys over a
length r subcube of its domain. Furthermore, it suffices that t is
bigger than an exponential stack of 2's of length 8kr (this is a very
crude but safe upper bound).
PROPOSITION 4.3. For all t >> k,r,p >= 1, every relation on
{1,...,t}^k has a p times continuable free reduction with at most k^k
+1 valleys over a length r cube that starts a sequence of k cubes,
each mapped into the next. In fact, we can require that these cubes
nest under inclusion and lie in the domain. Furthermore, it suffices
that t is bigger than an exponential stack of 2's of length 8rkp (this
is a very crude but safe upper bound).
Note that Propositions 4.1 - 4.3 are explicitly Pi01.
THEOREM 4.4. The following is false. For all t >> k,r >= 1, every
relation on {1,...,t}^k has an injective free reduction with at most
k^k+1 valleys over a length r subcube of its domain.
THEOREM 4.5. Proposition 4.1 is provable in SRP+, and also in SEFA +
Con(SRP). Propositions 4.2, 4.3 are provable in SRP+ but not from any
consequence of SRP consistent with SEFA. They are each provably
equivalent to Con(SRP) over SEFA.
Here SEFA = super exponential function arithmetic.
5. ORDER INVARIANCE.
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 contained in N^k
is order invariant if and only if A is the union of equivalence
classes of N^k under order equivalence. We say that R is an order
invariant relation on N^k if and only if R is an order invariant
subset of N^2k.
We say that A contained in {1,...,t}^k is order invariant if and only
if A is the union of equivalence classes of {1,...,t}^k under order
equivalence. We say that R is an order invariant relation on
{1,...,t}^k if and only if R is an order invariant subset of
{1,...,t}^2k.
Note that for each fixed k, there are only finitely many order
invariant subsets of N^k, and they have nice canonical presentations
as finite sets of elements from N^k, each of whose set of coordinates
forms an initial segment of N.
What effect on these results does the restriction to these very
concrete order invariant relations have?
The answer is NONE. In fact, the estimates given in section 4 can be
sharply reduced to a double or triple exponential.
In fact, we can go further. In section 3, we can demand that the
domains be N^k, and take the infinite subcube as the set of k tuples
from a geometric progression, with explicitly given base (yet another
at most double exponential). We can also demand that the free
reduction be extremely computable. A fully explicit representation of
the free reduction may be possible in intelligible terms following
topics like generating functions from core math. In fact, the whole
development has an Hilbertian flavor - but with a bizarre twist. ZFC
is nowhere near strong enough. Certain large cardinals are sufficient.
Once we bring in order invariance, we have the earlier infinitary
formulation from http://www.cs.nyu.edu/pipermail/fom/2010-March/014422.html
- using order invariance on Q^k, where Q is the rationals. Recall
that in the previous formulations, we use the closely related concept
of one set freely reducing another set - rather than a function being
a reduction.
PROPOSITION. In every order invariant relation on Q^k, some set
containing its upper shift, freely reduces its own cube.
We also games and related developments from the earlier postings.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 400th 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 1
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:30PMs
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/14/10 11:51AM
Harvey Friedman
More information about the FOM
mailing list