[FOM] 398: New Free Reduction Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Wed Mar 10 05:26:39 EST 2010
I can do without the upper shift, order invariance, and also replace Q
by N. There is still a context where I need these - see section 4.
So we start over, fully self contained (except for importation of
material from previous posting in section 4).
NEW FREE REDUCTION THEORY 1
by
Harvey Friedman
March 10, 2010
1. VALLEYS.
2. INFINITE REDUCTIONS.
3. FINITE REDUCTIONS.
4. INJECTIVE REDUCTIONS.
5. ORDER INVARIANCE.
1. VALLEYS.
We use N for the set of all nonnegative integers. We define the cubes
in N^k as the sets E^k, where E is contained in N. The length of the
cube E^k is the number of elements of E.
Let f:N^k into N^k. We say that n is a valley of f if and only if n is
a coordinate of some f(x), 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 are the even elements of N.
We say that n is a valley of f over E if and only if n is a coordinate
of some f(x), x in E^k, where min(x) > n.
THEOREM 1.1. The following is false. Every f:N^k into N^k has finitely
many valleys over some infinite set.
THEOREM 1.2. The following is false. For all r >= 1, every f:N^k into
N^k has at most k^k+1 valleys over some r element set.
THEOREM 1.3. For all r >= 1, every f:N^k into N^k has at most rk^k+1
valleys on some r element set.
2. INFINITE REDUCTIONS.
We use N for the set of all nonnegative integers.
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 or N^2k.
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 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.
THEOREM 2.1. Every relation on N^k has a free reduction with domain
N^k. Its range is unique.
THEOREM 2.2. The following is false. Every relation on N^k has a free
reduction with finitely many valleys over N.
Let f:N^k into N^k be partial. We say that E contained in N is stable
if and only if f[E^k] contained in E^k contained in dom(f).
THEOREM 2.3. The following is false. Every relation on N^k has a free
reduction with finitely many valleys over some infinite stable set.
A feature of a stable set is that you can keep generating integers
from its elements, using (the coordinate functions of) f, and you will
always stay within the domain of f. (Of course, a stable set has an
additional property: that you never leave the set as you generate.)
From this point of view, the weakest relevant condition on E is that
E^k contained in dom(f). We call such E the 0-cores of f.
THEOREM 2.4. Every relation on N^k has a free reduction with finitely
many valleys over some infinite 0-core.
More generally, the r+1-cores, r >= 0, are the E such that E union
f[E^k] is an r-core.
It is easy to verify that subsets of r-cores are r-cores, and that any
r-core is an r'-core if 0 <= r' < r.
Another way of looking at r-cores is that if we generate integers for
r steps, starting form elements of the set, then we stay within the
domain (taking k-tuples).
Consider the core of the Earth. It immediately affects (generates)
material including it and a bit farther out. This is turn immediately
affects (generates) material including it and yet farther out. We can
iterate this process several times, but always stay within the Earth
(the domain). At some point, we run into the atmosphere, which is not
part of the Earth (the domain). So the core of the Earth is like, say,
a 6-core for geologic operations. Perhaps this suggests a causation
model.
PROPOSITION 2.5. Every relation on N^k has a free reduction with
finitely many valleys over some infinite k-core.
PROPOSITION 2.6. For all k,n >= 1, every relation on N^k has a free
reduction with finitely many valleys over some infinite n-core.
PROPOSITION 2.7. Every relation on N^k has a free reduction with
finitely many valleys over some infinite 2-core.
THEOREM 2.8. Propositions 1.5 - 1.7 are provable in SRP+ but not in
any consequence of SRP consistent with RCA_0. They are provably
equivalent, over ACA, to Con(SRP).
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.
3. FINITE REDUCTIONS.
We first need to quantify the number of valleys.
PROPOSITION 3.1. For all k,n >= 1, every relation on N^k has a free
reduction with at most k^k+1 valleys over some infinite n-core.
PROPOSITION 3.2. For all k,n,r >= 1, every relation on N^k has a free
finite reduction with at most k^k+1 valleys on some n-core with r
elements.
We now consider relations on [0,t]^k. It is understood that reductions
must have domain included in [0,t]^k.
PROPOSITION 3.3. For all t >> k,n,r >= 1, every relation on [0,t]^k
has a free reduction with at most k^k+1 valleys on some n-core with r
elements. In fact, it suffices to assume that t is greater than an
exponential stack of 2's of length 8(k+n+r). This is a very crude but
safe estimate.
Obviously Proposition 3.3 is explicitly Pi01.
THEOREM 3.4. Propositions 3.1 - 3.3 are provable in SRP+ but not in
any consequence of SRP consistent with RCA_0. They are provably
equivalent, over ACA, to Con(SRP).
4. INJECTIVE REDUCTIONS.
If we want to work with free reductions f:E^k into E^k, then we need
to use order invariance, the rationals, and most naturally, the upper
shift.
PROPOSITION 4.1. In every order invariant relation on Q^k, some set
containing its upper shift freely reduces its cube.
See Free Reduction Theory 1 http://www.cs.nyu.edu/pipermail/fom/2010-March/014422.html
section 1, for details.
5. ORDER INVARIANCE.
We can add order invariance to the hypotheses of Propositions 2.5,
2.6, 2.7, 3.1, 3.2, 3.3. This does not change their metamathematical
status. Proposition 3.2 becomes explicitly Pi01 without having to use
an estimate as in Proposition 3.3.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 398th 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
Harvey Friedman
More information about the FOM
mailing list