[FOM] 420: Reduction Function Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Mon May 17 02:53:59 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
**********************************************************************
Now things seem considerably more direct and simple than before.
Reduction functions have strong ties to kernels in digraphs. But the
present formulation is more direct than passing through digraph theory.
TEMPLATE. Every R contained in N^k x N^k has a reduction function
which is well behaved over some k generating infinite set.
PROPOSITION. Every R contained in N^k x N^k has a reduction function
which is lower shift invariant over some k generating infinite (k
element) set.
REDUCTION FUNCTION THEORY 1
by
Harvey M. Friedman
May 17, 2010
1. REDUCTION FUNCTIONS.
2. GENERATING SETS.
3. LOWER SHIFT INVARIANCE.
4. INFINITE FREE REDUCTION THEOREM.
5. FINITE FREE REDUCTION THEOREM.
6. ORDER INVARIANT BASIS THEOREMS.
7. EXPONENTIAL PRESBURGER SETS.
8. WELL BEHAVEDNESS.
1. REDUCTION FUNCTIONS.
Let N be the set of all nonnegative integers.
We consider R contained in N^k x N^k.
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 is a strict R
reduction of x or y = x.
We say that f is a reduction function for R if and only if
i. f:A into A, A contained in N^k.
ii. For all x in A, f(x) is an R reduction of x.
iii. No value of f is a strict R reduction of any value of f.
We think of
y is a strict R reduction of x
as asserting that
y "strictly simplifies to x".
We think of
y is an R reduction of x
as asserting that
y "simplifies to x".
Let f:A into A be a reduction function for R. Then
each x in A is simplified by f to a "core", f(x), that is not going to
strictly simplify to any other "core".
NOTE: In this motivating language, simplification and strict
simplification are not transitive.
THEOREM 1.1. Let R,A be given. There is a reduction function from A
into A. Its range is the same as its fixed points. Any two reduction
functions from A into A have the same range (or fixed points). The
reduction functions f:A into A are exactly the functions f:A into A
that are defined by: f(x) is a strict R reduction of x that is a fixed
point of f, if this exists; x otherwise.
2. GENERATING SETS.
Let f:A into A, A contained in N^k. Let E be contained in N. We use
any E contained in N to generate vectors as follows. Gamma(f,E,0) =
E^k. Gamma(f,E,p+1) is the least set D^k containing Gamma(f,E,p) union
f[Gamma(f,E,p)].
We say that E is a p generating set for f if and only if Gamma(f,E,p)
is contained in A.
Note the essential use of the subsets D^k of N^k. We can view these as
the "subspaces" of N^k. This is highly suggestive for possible moves
to more general mathematical contexts.
3. LOWER SHIFT INVARIANCE.
For E contained in N, we define the E shift as the map that sends x in
E to the next largest element of E. Obviously, the E shift is
undefined at the largest element of E. If E is infinite then the E
shift maps E into E.
The E shift lifts naturally to E^k, by acting on coordinates.
We say that f:A into A is shift invariant over E contained in N if and
only if for all x,y in A, if the E shift of x is y then f(x) = f(y).
This notion is too strong for our purposes. We are interested in a
weakening of this notion that works well with many familiar
mathematical functions.
We say that f:A into A is lower shift invariant over E contained in N
if and only if for all x,y in A and 1 <= i <= k, if the E shift of x
is y and f_i(x) < min(x), then f_i(x) = f_i(y). Here f_i is the i-th
coordinate function of f.
There are some standard mathematical contexts where lower shift
invariance arises.
THEOREM 3.1. Every polynomial P:Z^k into Z^k with nonnegative integer
coefficients is lower shift invariant over a tail of the double
factorials.
Note that, e.g., x-1 is not lower shift invariant over even a two
element subset of N.
4. INFINITE FREE REDUCTION THEOREM.
PROPOSITION 4.1. Every R contained in N^k x N^k has a reduction
function which is lower shift invariant over some infinite k
generating set.
THEOREM 4.2. Proposition 4.1 is provable in SRP+ but not from any
consequence of SRP that is consistent with ACA'. Proposition 4.1 is
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. The
k-SRP asserts that every partition of the unordered k-tuples from
lambda into two pieces has a homogeneous set that is a stationary
subset of lambda. ACA' is ACA_0 + "for all n in N and x contained in
N, the n-th Turing jump of x exists". Another way of formulating ACA'
is ACA_0 + "arithmetic recursion on omega".
5. FINITE FREE REDUCTION THEOREM.
We begin with the semi finite form of Proposition 4.1.
PROPOSITION 5.1. Every R contained in N^k x N^k has a finite reduction
function which is lower shift invariant over some finite k generating
set.
There are two ways of giving a finite form of Proposition 5.1. One is
to use a large initial segment of N, which is the approach of this
section. The other is to use order invariance, which is the approach
of the next section.
PROPOSITION 5.2. Every R contained in [t]^k x [t]^k has a reduction
function on [t]^k which is lower shift invariant over some k element k
generating set, where t is the stack of 2's of height 8k.
Note that Proposition 5.2 is explicitly Pi01.
THEOREM 5.3. Propositions 5.1, 5.2 is provable in SRP+ but not from
any consequence of SRP that is consistent with ACA'. Proposition 5.1
is provably equivalent, over ACA', to Con(SRP). Proposition 5.2 is
provably equivalent, over SEFA, to Con(SRP).
Here SEFA = super exponential function arithmetic.
6. ORDER INVARIANT FREE REDUCTION THEOREMS.
PROPOSITION 6.1. Every order invariant R contained in N^k x N^k has a
reduction function which is lower shift invariant over some infinite k
generating set.
PROPOSITION 6.2. Every order invariant R contained in N^k x N^k has a
finite reduction function which is lower shift invariant over some k
element k generating set.
PROPOSITION 6.3. Every order invariant R contained in N^k x N^k has a
reduction function on [(8k)!]^k which is lower shift invariant over
some k element k generating set.
We can even be explicit about the generating set.
PROPOSITION 6.4. Every order invariant R contained in N^k x N^k has a
reduction function which is lower shift invariant over some k
generating infinite geometric progression.
PROPOSITION 6.5. Every order invariant R contained in N^k x N^k has a
finite reduction function which is lower shift invariant over the k
generating set {2^(8k)!,...,2^((8k)!+k)}.
Note that Proposition 6.2 is explicitly Pi02, and Propositions 6.3,
6.5 are explicitly Pi01.
THEOREM 6.6. Propositions 6.1 - 6.5 are provable in SRP+ but not from
any consequence of SRP that is consistent with ACA'. Propositions 6.1,
6.4 is provably equivalent, over RCA_0, to Con(SRP). Propositions 6.2,
6.3, 6.5 are provably equivalent, over EFA, to Con(SRP).
Here EFA = exponential function arithmetic.
7. EXPOENENTIAL PRESBURGER SETS.
Presburger arithmetic is the first order theory of the structure (N,
+). Exponential Presburger arithmetic is the first order theory of the
structure (N,+,2^). I.e., we add base 2 exponentiation to Presburger
arithmetic. THere remains a decision procedure. See, e.g.,
F. Point, On the Expansion (N;+;2^x) of Presburger Arithmetic,
Appendix B, Book Drafts, http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html
Recall
PROPOSITION 4.1. Every R contained in N^k x N^k has a reduction
function which is lower shift invariant over some infinite k
generating set.
THEOREM 7.1. For all k >= 1, every order invariant R contained in N^k
x N^k has an exponential Presburger reduction function which is lower
shift invariant over some infinite k generating tail of the powers of
2. This sentence is provably equivalent to Con(SRP) over SEFA.
From the decision procedure for exponential Presburger arithmetic
(see F. Point above), this yields a Pi02 sentence. By placing a
suitable bound on the complexity of the exponential Presburger
function, this yields a Pi01 sentence.
8. WELL BEHAVEDNESS.
Instead of using lower shift invariance, we can use a variety of well
behavedness conditions, resulting in a variety of levels of Pi01
independent statements ranging from PA through SRP. There is even a
notion of "ultimately well behaved". This is an elaborate theory, and
will be fully developed in due course now that - perhaps - we have
finally settled on reduction functions as the clearest way to deliver
the message.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 420th 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 1graham
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:30PM
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
402: New Free Reduction Theory 5 3/19/10 12:59PM
403: Set Equation Tower Theory 1 3/22/10 2:45PM
404: Set Equation Tower Theory 2 3/24/10 11:18PM
405: Some Countable Model Theory 1 3/24/10 11:20PM
406: Set Equation Tower Theory 3 3/25/10 6:24PM
407: Kernel Tower Theory 1 3/31/10 12:02PM
408: Kernel tower Theory 2 4/1/10 6:46PM
409: Kernel Tower Theory 3 4/5/10 4:04PM
410: Kernel Function Theory 1 4/8/10 7:39PM
411: Free Generation Theory 1 4/13/10 2:55PM
412: Local Basis Construction Theory 1 4/17/10 11:23PM
413: Local Basis Construction Theory 2 4/20/10 1:51PM
414: Integer Decomposition Theory 4/23/10 12:45PM
415: Integer Decomposition Theory 2 4/24/10 3:49PM
416: Integer Decomposition Theory 3 4/26/10 7:04PM
417: Integer Decomposition Theory 4 4/28/10 6:25PM
418: Integer Decomposition Theory 5 4/29/10 4:08PM
419: Integer Decomposition Theory 6
Harvey Friedman
More information about the FOM
mailing list