[FOM] 425: Well Behaved Reduction Functions 4

Harvey Friedman friedman at math.ohio-state.edu
Mon May 31 16:37:17 EDT 2010


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

**********************************************************************

As an alternative to the well behavedness condition in http://www.cs.nyu.edu/pipermail/fom/2010-May/014779.html 
  we use "p times extendable". This has the advantage of avoiding the  
use of p-composites. We do go back to "lower shift invariance".

In the interest of focusing on the main point, we now require that  
reduction functions be finite.

E.g.,

PROPOSITION 3.1. Every R contained in N^k x N^k has a p-extendable  
reduction function that is lower shift invariant over some r element  
set.

We also give two equivalent definition of Reduction Functions - one  
involving Kernels in Digraphs, the other involving Strategies in Games.

WELL BEHAVED REDUCTION FUNCTIONS 4
by
Harvey M. Friedman
May 31, 2010

1. REDUCTION FUNCTIONS AND EXTENDABILITY.
2. LOWER SHIFT INVARIANCE.
3. REDUCTION FUNCTION THEOREMS.
4. ORDER INVARIANT REDUCTION FUNCTION THEOREMS.
5. REDUCTION FUNCTIONS AND KERNELS.
6. REDUCTION FUNCTIONS AND GAMES.

1. REDUCTION FUNCTIONS AND EXTENDABILITY.

Let N be the set of all nonnegative integers.

Let R be a subset of 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, where A is a finite subset of 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.

THEOREM 1.1. Let R  be contained in N^k x N^k, and A be a finite  
subset of N^k. There is a reduction function from A into A. Any  
reduction function from A into A is idempotent. Any two reduction  
functions from A into A have the same fixed points. The reduction  
functions f:A into A are exactly the functions f:A into A such that  
for all x in A, f(x) is a strict R reduction of x that is a fixed  
point of f, if this exists; x otherwise.

Let f,g:N^k into N^k be partial. We say that g is a strong extension  
of f if and only if

i. g is an extension of f.
ii. dom(g) includes all k tuples of coordinates of arguments of f.
iii. The largest coordinate of the arguments of f,g are the same.

We say that f is a p-extendable reduction function for R if and only  
if there is a sequence of p+1 reduction functions for R starting with  
f, forming a tower of strong extensions.

2. LOWER SHIFT INVARIANCE.

Let E be a finite subset of N. The E shift sends each element of E to  
the next largest element of E. Its domain is E\{max(E)}.

The E shift extends to E^k by acting coordinatewise. Its domain is (E\ 
{max(E)}^k.

Let f:N^k into N^k be partial. We say that f is shift invariant over E  
if and only if for all x,y in E^k, if y is the E shift of x, then f(x)  
= f(y).

We say that f is lower shift invariant over E if and only if for all  
x,y, if y is the E shift of x, and f_i(x) < min(x), then f_i(x) =  
f_i(y). Here f_i is the i-th coordinate function of f.

Note that if f is lower shift invariant over E and E has at least two  
element, then dom(f) includes E^k.

3. REDUCTION FUNCTION THEOREMS.

We write [t] = {0,...,t}.

We write 2^[t] for the exponential stack of t 2's. I.e., 2^[0] = 1,  
2^[s+1] = 2^2^[s].

We say that partial f:N^k into N^k is <= t if and only if dom(f) is  
contained in [t]^k.

PROPOSITION 3.1. Every R contained in N^k x N^k has a p-extendable  
reduction function which is lower shift invariant over some r element  
set.

PROPOSITION 3.3. Every R contained in N^k x N^k has a p-extendable  
reduction function <= 2^[8kpr] which is lower shift invariant over  
some r element set.

Obviously, in Proposition 3.3, only the part of R that is <= 2^[8kpr]  
is relevant. Thus we have the following explicitly Pi01 form.

PROPOSITION 3.4. Let t >= 2^[8kpr]. Every R contained in [t]^k x [t]^k  
has a p-extendable reduction function <= t which is lower shift  
invariant over some r element set.

THEOREM 3.6. Propositions 3.1 - 3.4 are provable in SRP+ but not from  
any consequence of SRP that is consistent with RCA_0. Propositions 3.1  
- 3.4 are provably equivalent, over RCA_0, to Con(SRP). For 3.4, we  
can use SEFA instead of RCA_0.

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. SEFA is super exponential function arithmetic.

4. ORDER INVARIANT REDUCTION FUNCTION THEOREMS.

Order invariance of R allows us to lower the upper bound needed, and  
to be explicit about the r element set. We prefer to use just one  
variable for this most explicit form.

PROPOSITION 4.1. Every order invariant R contained in N^k x N^k has a  
k-extendable reduction function <= (8k)!! which is lower shift  
invariant over {(7k)!!,(7k)!!^2,...,(7k)!!^k}.

THEOREM 4.2. Proposition 4.1 is provable in SRP+ but not from any  
consequence of SRP that is consistent with EFA. Proposition 4.1 are  
provably equivalent to Con(SRP) over EFA.

Here EFA is exponential function arithmetic.

5. REDUCTION FUNCTIONS AND KERNELS.

Let R be contained in N^k x N^k. Let G[R] be the digraph with vertex  
set N^k, where (x,y) is an edge if and only if y is a strict R  
reduction of x.

Then f is a reduction function for R if and only if

i. f:A into A, A a finite subset of N^k.
ii. For all x in A but not in the kernel of G|A, f(x) is in the kernel  
of G|A and (x,f(x)) is an edge of G|A.
iii. For all x in the kernel of G|A, f(x) = x.

6. REDUCTION FUNCTIONS AND GAMES.

Let R be contained in N^k x N^k and A be a finite subset of N^k. Write  
GAME(R,A) for the two person game where players I,II alternately play  
elements of A, where, after player I's first move, each player must  
play a strict R reduction of the previous move in the game (i.e., the  
last previous move of their opponent). If a player cannot meet this  
this requirement, then that player loses and their opponent wins. Note  
that every play of the game ends with a loss.

Then f is a reduction function for R if and only if

i. f:A into A, A a finite subset of N^k.
ii. For all x in A, if x is a loss in GAME(R,A) then f(x) is a winning  
response to x in GAME(R,A).
iii. For all x in A, if x is a win in GAME(R,A) then f(x) = x.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 425th 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  5/4/10   10:39PM
420: Reduction Function Theory 1  5/17/10   2:53AM
421: Reduction Function Theory 2  5/19/10   12:00PM
422: Well Behaved Reduction Functions 1  5/23/10  4:12PM
423: Well Behaved Reduction Functions 2  5/27/10  3:01PM
424: Well Behaved Reduction Functions 3  5/29/10  8:06PM

Harvey Friedman 


More information about the FOM mailing list