[FOM] 179:Polynomial Shift Sequences/Correction

[Harvey Friedman]

I had the right idea, but it cannot be done quite the way that I said 
in posting #178. Here is a corrected version, which also is simpler.

My apologies to the FOM email list.

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

We introduce the notion of a Polynomial Shift Sequence of integers. 
We show that the existence of arbitrarily long finite Polynomial 
Shift Sequences is independent of Peano Arithmetic (PA).

Let P:Z^n into Z^n be a polynomial. We let #(P) be the least r such 
that all coefficients of P have magnitude <= r and the degree of P is 
<= r.

A Polynomial Shift Sequence is a strictly increasing finite sequence 
x of positive integers such that

for all 1 <= i <= lth(x) = n, every polynomial P:Z^n into Z^n with 
#(P) <= x_i, that achieves a value in {x_i+1,...,x_n-1}^n, achieves a 
value in {x_i+2,...,x_n}^n.

A Limited Polynomial Shift Sequence is a strictly increasing finite 
sequence x of positive integers, such that

for all 1 <= i <= lth(x) = n, every polynomial P:[-xn,xn]^n into Z^n 
with #(P) <= x_i, that achieves a value in {x_i+1,...,x_n-2}^n, 
achieves a value in {x_i+2,...,x_n-1}^n.

THEOREM 1. There are Polynomial Shift Sequences of every finite length.

THEOREM 2. There are Limited Polynomial Shift Sequences of every finite length.

THEOREM 3. Theorems 1,2 are provable in ACA but not in ACA0 or PA. 
Theorem 2 is provably equivalent, in EFA (exponential function 
arithmetic), to the 1-consistency of PA. Let f(n) be the least last 
term of a Limited Polynomial Shift Sequence of length n. Then f is 
epsilon0-recursive, but eventually dominates every 
<epsilon0-recursive function.

THEOREM 4. Theorem 1 is provably equivalent, in EFA, to the 
2-consistency of PA.

There are many good ways to introduce a parameter k, so that the 
statement "there are k-sequences of every finite length" corresponds 
to, roughly, Sigmak induction. Here one simple way of going about 
this.

Let k >= 1. A Polynomial k-Sequence is a strictly increasing finite 
sequence x of positive integers such that

for all 1 <= i <= lth(x)-k, every polynomial P:Z^k into Z^k with #(P) 
<= x_i, that achieves a value in {x_1,...,x_n}^k, achieves a value in 
{x_1,...,x_i+k}^k.

A Limited Polynomial k-Sequence is a strictly increasing finite 
sequence x of positive integers such that

for all 1 <= i <= lth(x)-k, every polynomial P:[-x_n,x_n]^k into Z^k 
with #(P) <= x_i, that achieves a value in {x_1,...,x_n}^k, achieves 
a value in {x_1,...,x_i+k}^k.

THEOREM 5. For all k,n >= 1, there is a Polynomial k-Sequence of length n.

THEOREM 6. For all k,n .= 1, there is a Limited Polynomial k-Sequence 
of length n.

THEOREM 7. Theorems 5,6 are provable in ACA but not in ACA0 or PA. 
Theorem 6 is provably equivalent, in EFA (exponential function 
arithmetic), to the 1-consistency of PA. For any fixed k >= 1, 
Theorems 5,6 are provable in PA, but the quantifier complexity of 
induction required goes up according to k.

THEOREM 8. Theorem 5 is provably equivalent, in EFA, to the 
2-consistency of PA.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 179th 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-149 can be found at 
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html  in the FOM 
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM

Harvey Friedman


_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom