[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