[FOM] 402: New Free Reduction Theory 5
Harvey Friedman
friedman at math.ohio-state.edu
Fri Mar 19 01:39:48 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
***********************************
This corrects and simplifies New Free Reduction Theory 3 http://www.cs.nyu.edu/pipermail/fom/2010-March/014446.html
Also, to highlight the great simplicity of the SRP statement, we
minimize definitions and background material. Background material can
of course be added after headlines. The definitions are so simple that
background material is not needed for headlines.
We postpone a detailed discussion of the use of ORDER INVARIANCE.
NEW FREE REDUCTION THEORY 5
by
Harvey Friedman
March 18, 2010
1. FREE REDUCTION VALLEY THEOREMS - infinite, single relation.
2. FREE REDUCTION VALLEY THEOREMS - finite, single relation.
3. FREE REDUCTION VALLEY THEOREMS - infinite, two relations.
4. FREE REDUCTION VALLEY THEOREMS - finite, two relations.
1. FREE REDUCTION VALLEY THEOREMS - infinite, binary.
We use N for the set of all nonnegative integers.
Let f:N^k into N^k be partial. We say that f is infinite if and only
if f has an infinite domain.
We say that n is a valley of f if and only if n is a coordinate of
some f(y), where min(y) > n.
Let R be a binary relation on N^k. We say that y is a strict R
reduction of x iff x R y and max(x) > max(y). We say that y is an R
reduction of x iff y = x in N^k, or y is a strict reduction of x.
We say that f is a free R reduction if and only if
i. f:A^k into B^k, where A,B are subsets of N.
ii. For all x in A^k, f(x) is an R reduction of x.
iii. No value of f is a strict reduction of any value of f.
A continuable free R reduction is a free R reduction with an extension
to a free R reduction, where the domain of the latter is the codomain
of the former.
A twice continuable free R reduction is a free R reduction with an
extension to a continuable free R reduction, where the domain of the
latter is the codomain of the former.
These definitions extend to "f is p times continuable", p >= 0, in the
obvious way.
PROPOSITION 1.1. Free Reduction Valley Theorem 0 (binary). Every
binary relation on N^k has an infinite free reduction with finitely
many valleys.
PROPOSITION 1.2. Free Reduction Valley Theorem 1 (binary). Every
binary relation on N^k has an infinite continuable free reduction with
finitely many regressive values.
PROPOSITION 1.3. Free Reduction Valley Theorem 2 (binary). Every
binary relation on N^k has an infinite twice continuable free
reduction with finitely many regressive values.
PROPOSITION 1.4. Free Reduction Valley Theorem p (binary). Every
binary relation on N^k has an infinite p times continuable free
reduction with finitely many regressive values.
PROPOSITION 1.5. Free Reduction Valley Theorem <infinity (binary). For
all k,p >= 1, every binary relation on N^k has an infinite p times
continuable free reduction with finitely many regressive values.
THEOREM 1.6. The following is false. Every binary relation on N^k has
an infinite injective free reduction with finitely many regressive
values.
THEOREM 1.7. Propositions 1.1 - 1.5 are provable in SRP+, and also in
ACA' + Con(SRP). Propositions 1.3 - 1.5 are each provable in SRP+ but
not from any consequence of SRP consistent with RCA_0. Propositions
1.3 - 1.5 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".
2. FREE REDUCTION VALLEY THEOREMS - finite, binary.
We now work with binary relations on {1,...,t}^k. Here the domains and
codomains of reductions are required to be of the form A^k for some
subset A of {1,...t}.
The length of f:A^k into B^k is the cardinality of A.
PROPOSITION 2.1. For all t >> k,r >= 1, every binary relation on
{1,...,t}^k has a length r free reduction with at most k^k+1 valleys.
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 2.2. For all t >> k,r >= 1, every binary relation on
{1,...,t}^k has a length r continuable free reduction with at most k^k
+1 valleys. 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 2.3. For all t >> k,r >= 1, every binary relation on
{1,...,t}^k has a length r twice continuable free reduction with at
most k^k+1 valleys. 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 2.4 (relative to p). For all t >> k,r >= 1, every binary
relation on {1,...,t}^k has a length r, p times continuable free
reduction with at most k^k+1 valleys. Furthermore, it suffices that t
is bigger than an exponential stack of 2's of length 8krp (this is a
very crude but safe upper bound).
PROPOSITION 2.5. For all t >> k,r,p >= 1, every binary relation on
{1,...,t}^k has a length r, p times continuable free reduction with at
most k^k valleys. Furthermore, it suffices that t is bigger than an
exponential stack of 2's of length 8krp (this is a very crude but safe
upper bound).
THEOREM 2.6. The following is false. For all t >> k,r, every binary
relation on {1,...,t}^k has a length r injective free reduction with
at most k^k+1 valleys.
Note that Propositions 2.1 - 2.5 are explicitly Pi01.
THEOREM 2.7. Propositions 2.1 - 2.5 are provable in SRP+, and also in
SEFA + Con(SRP). Propositions 2.3 - 2.5 are each provable in SRP+ but
not from any consequence of SRP consistent with SEFA. Propositions 2.3
- 2.5 are each provably equivalent to Con(SRP) over SEFA.
Here SEFA = super exponential function arithmetic.
3. FREE REDUCTION VALLEY THEOREMS - infinite, ternary.
Let f,g:N^k into N^k be partial. We say that f,g is infinite if and
only if f,g has an infinite domain.
We say that n is a valley of f,g if and only if n is a coordinate of
some f(y) or g(y), where min(y) > n.
Let R be a ternary relation on N^k. The strict R reductions of x are
the pairs (y,z) such that max(x) > max(y),max(z) and R(x,y,z). The R
reductions of x are (x,x) together with the strict R reductions of x.
We say that f,g is a free R reduction if and only if
i. f,g:A^k into B^k, where A,B are subsets of N.
ii. For all x in A^k, (f(x),g(x)) is an R reduction of x.
iii. No (f(x),g(y)) is a strict reduction of any f(z) or g(z).
A continuable free R reduction f,g:A^k into B^k is a free R reduction
f',g':B^k into C^k, where f' extends f and g' extends g.
This definition extends to "f is p times continuable", p >= 0, in the
obvious way.
PROPOSITION 3.1. Free Reduction Valley Theorem 0 (ternary). Every
ternary relation on N^k has an infinite free reduction with finitely
many valleys.
PROPOSITION 3.2. Free Reduction Valley Theorem 1 (ternary). Every
ternary relation on N^k has an infinite continuable free reduction
with finitely many valleys.
PROPOSITION 3.3. Free Reduction Valley Theorem p (ternary). Every
ternary relation on N^k has an infinite p times continuable free
reduction with finitely many valleys values.
PROPOSITION 3.4. Free Reduction Valley Theorem <infinity (ternary).
For all k,p >= 1, every ternary relation on N^k has an infinite p
times continuable free reduction with finitely many valleys.
THEOREM 3.5. Propositions 3.1 - 3.4 are provable in SRP+, and also in
ACA' + Con(SRP). Propositions 3.2 - 3.4 are provable in SRP+ but not
from any consequence of SRP consistent with RCA_0. Propositions 3.2 -
3.4 are each provably equivalent to Con(SRP) over ACA'.
4. FREE REDUCTION VALLEY THEOREMS - finite, ternary.
We now work with ternary relations on {1,...,t}^k. Here the domains
and codomains of reductions are required to be of the form A^k for
some subset A of {1,...t}.
The length of f,g:A^k into B^k is the cardinality of A.
PROPOSITION 4.1. For all t >> k,r >= 1, every ternary relation on
{1,...,t}^k has a length r free reduction with at most 2k^k+1 valleys.
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 ternary relation on
{1,...,t}^k has a length r continuable free reduction with at most 2k^k
+1 valleys. 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 (relative to p). For all t >> k,r >= 1, every ternary
relation on {1,...,t}^k has a length r, p times continuable free
reduction with at most 2k^k+1 valleys. Furthermore, it suffices that t
is bigger than an exponential stack of 2's of length 8krp (this is a
very crude but safe upper bound).
PROPOSITION 4.4. For all t >> k,r,p >= 1, every ternary relation on
{1,...,t}^k has a length r, p times continuable free reduction with at
most 2k^k valleys. Furthermore, it suffices that t is bigger than an
exponential stack of 2's of length 8krp (this is a very crude but safe
upper bound).
Note that Propositions 4.1 - 4.4 are explicitly Pi01.
THEOREM 4.5. Propositions 4.1 - 4.4 are provable in SRP+, and also in
SEFA + Con(SRP). Propositions 4.2 - 4.4 are provable in SRP+ but not
from any consequence of SRP consistent with SEFA. Propositions 3.2 -
3.4 are each provably equivalent to Con(SRP) over SEFA.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 402nd 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/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
Harvey Friedman
More information about the FOM
mailing list