[FOM] 399: New Free Reduction Theory 2

[Harvey Friedman]

This is an improved and polished presentation of the New Free  
Reduction Theory http://www.cs.nyu.edu/pipermail/fom/2010-March/014443.html 
. We now have a particularly clean division of Valley Counting Theory,  
and Free Reduction Theory. The Valley Counting Theorem has been  
presented to a Fields Medalist analyst, in somewhat different form,  
many years ago, with unequivocal success. Also, more recently, with a  
particularly hard nosed several complex variables expert, also with  
unequivocal success. I.e., they regarded the Valley Counting Theorem  
as of clear mathematical interest, independently of its  
metamathematical status - which is, incidentally, its unprovability  
from Peano Arithmetic, and corresponding growth rates (the epsilon_0  
hierarchy of numerical functions).

Also, the Free Reduction Theorem is a modified form of The  
Complementation Theorem from BRT - see Chapter 1 of my book on my  
website - and as discussed there, is essentially the same as a theorem  
about dags essentially due to Von Neumann (in his book on game theory  
with Morgenstern), which has spawned a substantial field in graph  
theory called Dominators (and its dual notion, Kernels), and has  
strong connections with the Contraction Mapping Theorem.

The Valley Counting Theorems and the Free Reduction Theorems are put  
together in obvious ways to obtain the Free Reduction Valley Theorems,  
which correspond to large cardinals (the SRP hierarchy as in http://www.cs.nyu.edu/pipermail/fom/2010-March/014443.html 
.

NEW FREE REDUCTION THEORY 2
by
Harvey Friedman
March 11, 2010

1. VALLEY COUNTING THEOREMS.
2. FREE REDUCTION THEOREMS.
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 p cube.

THEOREM 1.3. Valley Counting Theorem - infinite. For all k,p >= 1,  
every f:N^k into N^k has at most pk^k+1 valleys over some length p cube.

THEOREM 1.4. Valley Counting Theorem - finite. For all t >> k,p >= 1,  
every f:{0,...,t}^k into {0,...,t}^k has at most pk^k+1 valleys over  
some length p 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 is an R reduction if and only if for all x in dom(f),
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.

We say that a function (from anywhere to anywhere) is infinite if and  
only if its domain is infinite.

THEOREM 2.1. Free Reduction Theorem. Every relation on N^k has a free  
reduction with domain N^k. Its range is unique.

We can strengthen this as follows.

THEOREM 2.2. Free Reduction Theorem - sharp. For all A contained in  
N^k, every relation on N^k has a free reduction f:A into A. Its range  
depends only on A and the relation.

In sections 3,4 we will be working with free reductions f:A into N^k  
where rng(f) is NOT a subset of A.

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 an 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.

We say that f maps A into B if and only if for all x in A, f(x) is in  
B. In particular, A must be a subset of the domain of f.

PROPOSITION 3.2. Every relation on N^k has a free reduction with  
finitely many valleys over an infinite cube that is mapped into a  
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 free reduction with  
finitely many valleys over an infinite 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.

PROPOSITION 3.4. For all n >= 1, every relation on N^k has a free  
reduction with finitely many valleys over an infinite cube that starts  
a sequence of n cubes, each mapped into the next. In fact, we can  
require that these cubes nest under inclusion and lie in the domain.

The "limit" of these Propositions is as follows, which is not  
surprising in light of Theorem 1.1.

THEOREM 3.5. The following is false. Every relation on N^k has a free  
reduction f:E^k into E^k with finitely many valleys over an infinite  
subcube of E^k.

THEOREM 3.6. Proposition 3.1 is 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. 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". s

4. FREE REDUCTION VALLEY THEOREMS - finite.

We now work with relations on {1,...,t}^k. Here a reduction is  
required to have domain contained in {1,...,t}^k.

PROPOSITION 4.1. For all t >> k,p >= 1, every relation on {1,...,t}^k  
has a free reduction with at most k^k+1 valleys over a length p  
subcube of its domain. Furthermore, it suffices that t is bigger than  
an exponential stack of 2's of length 8kp (this is a very crude but  
safe upper bound).

PROPOSITION 4.2. For all t >> k,p >= 1, every relation on {1,...,t}^k  
has a free reduction with at most k^k+1 valleys over a length p cube  
that is mapped into a subcube of its domain. Furthermore, it suffices  
that t is bigger than an exponential stack of 2's of length 8kp (this  
is a very crude but safe upper bound).

PROPOSITION 4.3. For all t >> k,p >= 1, every relation on {1,...,t}^k  
has a free reduction with at most k^k+1 valleys over a length p 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 8kp (this is a very crude but safe upper bound).

PROPOSITION 4.4. For all t >> k,p,n >= 1, every relation on  
{1,...,t}^k has a free reduction with at most k^k+1 valleys over a  
length p cube that starts a sequence of n 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 8kpn (this is a very crude but  
safe upper bound).

Note that Propositions 4.1 - 4.4 are explicitly Pi01.

THEOREM 4.5. The following is false. For all t >> k,p >= 1, every  
relation on {1,...,t}^k has a free reduction f:E^k into E^k with at  
most k^k+1 valleys over a length p subcube of its domain.

THEOREM 4.6. Proposition 4.1 is 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. 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 399th 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

Harvey Friedman