[FOM] 178:Diophantine Shift Sequences
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jun 14 18:34:30 EDT 2003
We introduce the notion of a Diophantine uniform sequence of
integers. We show that the existence of arbitrarily long finite
Diophantine uniform sequences is independent of Peano Arithmetic (PA).
All numbers and intervals are with the integers.
We say that a polynomial has a zero in a set A if and only if the
polynomial is 0 at a vector whose coordinates lie in A.
A Diophantine shift sequence is a strictly increasing finite sequence
x of positive integers such that
for all 1 <= i <= lth(x) = n, every polynomial P in at most xi
variables with coefficients from [-xi,xi] has a zero from
{xi+1,...,xn-1} union [xn-1,xn] if and only if it has a zero from
{xi+2,...,xn} union [xn,infinity).
A limited Diophantine shift sequence is a strictly increasing finite
sequence x of positive integers, such that
for all 1 <= i <= lth(x) = n, every polynomial P in at most xi
variables with coefficients from [-xi,xi] has a zero from
{xi+1,...,xn-2} union [xn-2,xn-1] if and only if it has a zero from
{xi+2,...,xn-1} union [xn-1,xn].
THEOREM 1. There are Diophantine shift sequences of every finite length.
THEOREM 2. There are limited Diophantine 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 Diophantine 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.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 178th 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
Harvey Friedman
More information about the FOM
mailing list