[FOM] 426: Well Behaved Reduction Functions 5

Tue Jun 1 22:39:30 EDT 2010

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

########################################################################

This is a continuation of

424: Well Behaved Reduction Functions 3 http://www.cs.nyu.edu/pipermail/fom/2010-May/014779.html
425: Well Behaved Reduction Functions 4 http://www.cs.nyu.edu/pipermail/fom/2010-May/014790.html

There is a particularly satisfactory theory of well behavedness at  
very restricted sets of vectors. Here we briefly state one situation -  
that of what we call *forward pairs* (see below).

Here we only present the resulting Propositions. In a later posting we  
will discuss the associated theory of well behavedness, where we will  
establish the robustness of the notion (at forward pairs), and state  
and prove that the Propositions below are best possible (at forward  
pairs). Forward chains will also be treated - where the number of  
vectors is any finite integer >= 2.

We say that x,y in N^k is a forward pair if and only if they are of  
the form (z_1,...,z_k), (z_2,...,z_k+1), where z_1 < ... < z_k+1.

Pure polynomials P in partial f:N^k into N^k are given by expressions  
in the coordinate functions f_1,...,f_k and variables, and are N  
valued. (Logicians call these terms). Degree refers to the number of  
occurrences of functions.

The set of all such P is often referred to as the clone generated by  
(the coordinate functions of) f - although this is usually done only  
for functions f:A into A. E.g., see http://en.wikipedia.org/wiki/Clone_(algebra) 
   http://www.math.u-szeged.hu/tagok/szendrei/clone.htm  http://www.algebra.uni-linz.ac.at/Slides/slides-olomouc9.pdf

Polynomials in f allow the use of constants, and cannot be used here.

DEFINITION. Let f:N^k into N^k be partial. We say that f is p well  
behaved at a forward pair x,y in N^k if and only if for all pure k-ary  
polynomials P in f of degree <= p, (x,P(x)) and (y,P(y)) have the same  
order type, and P(x) < x_1 implies P(x) = P(y).

The above implies that P(x), P(y) are defined.

OBSERVATION. Every affine T:N^k into N is p well behaved at some  
forward pair.

This definition allows us to make very simple Propositions as follows.  
As in 425: Well Behaved Reduction Functions 4 http://www.cs.nyu.edu/pipermail/fom/2010-May/014790.html 
  we require that reduction functions be finite.

PROPOSITION 1. Every R contained in N^k x N^k has a reduction function  
which is p well behaved at some forward pair.

PROPOSITION 2. Every R contained in N^k x N^k has a reduction function  
<= 2^[8kp] which is p well behaved at some forward pair.

PROPOSITION 3. Let t >= 2^[8kpr]. Every R contained in [t]^k x [t]^k  
has a reduction function <= t which is p well behaved at some forward  
pair.

PROPOSITION 4. Every order invariant R contained in N^k x N^k has a  
reduction function <= (8k)!! which is k well behaved at  
{(7k)!!,...,k(7k)!!}, {2(7k)!!,..,(k+1)((7k)!!)).

These Propositions are provably equivalent to Con(SRP) over RCA_0  
(SEFA suffices for Proposition 3, and EFA suffices for Proposition 4).

As in http://www.cs.nyu.edu/pipermail/fom/2010-May/014790.html  
Reduction Functions correspond to strategies in associated games. We  
call these

*the restricted lower strategies for R*

Then we can restate Propositions 1-4 as follows. We think of R  
contained in N^k x N^k as a game, and so we insert the word "game"  
below.

PROPOSITION 1'. Every game R contained in N^k x N^k has a restricted  
lower strategy which is p well behaved at some forward pair.

PROPOSITION 2'. Every game R contained in N^k x N^k has a restricted  
lower strategy <= 2^[8kp] which is p well behaved at some forward pair.

PROPOSITION 3'. Let t >= 2^[8kpr]. Every game R contained in [t]^k x  
[t]^k has a restricted lower strategy <= t which is p well behaved at  
some forward pair.

PROPOSITION 4'. Every order invariant game R contained in N^k x N^k  
has a restricted lower strategy <= (8k)!! which is k well behaved at  
((7k)!!,...,k(7k)!!), (2(7k)!!,..,(k+1)((7k)!!)).

These Propositions are provably equivalent to Con(SRP) over RCA_0  
(SEFA suffices for Proposition 3', and EFA suffices for Proposition 4').

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 426th 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 athttp://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
425: Well Behaved Reduction Functions 4  5/31/10  5:05PM

Harvey Friedman