[FOM] 380: More Polynomial Shift Theorems
Harvey Friedman
friedman at math.ohio-state.edu
Mon Dec 28 07:06:26 EST 2009
This supersedes http://www.cs.nyu.edu/pipermail/fom/2009-December/014269.html
This abstract is at the level of PA. The new development is that it
only involves polynomials - even just quadratics - with integer
coefficients.
I will restate below some shift theorems from http://www.cs.nyu.edu/pipermail/fom/2008-January/012582.html
These were used to get independence results involving polynomials with
integer coefficients, in http://www.cs.nyu.edu/pipermail/fom/2008-January/012611.html
However, the new way I do this now is more natural and convincing.
We will give three of the many forms of my combinatorial shift theorem.
THEOREM 1. For all f:N^k into N, there exist distinct x_1,...,x_k+1
such that f(x_2,...,x_k+1) - f(x_1,...,x_k) lies in 2N.
THEOREM 2. For all f:N^k into N, there exist distinct x_1,...,x_k+2
such that f(x_1,...,x_k) <= f(x_2,...,x_k+1) <= f(x_3,...,x_k+2).
THEOREM 3. For all f,g:N^k into N, there exist distinct x_1,...,x_k+1
such that f(x_1,...,x_k) <= f(x_2,...,x_k+1) and g(x_1,...,x_k) <=
g(x_2,...,x_k+1).
THEOREM 4. Theorems 1-3 are each provably equivalent to "epsilon_0 is
well ordered" over RCA_0. Theorem 1 for recursive f's is provably
equivalent to the 2-consistency of PA, over EFA. Theorems 1-3 for
primitive recursive (or elementary recursive or poly time in bit
representations or linear time/log space in bit representations) is
provably equivalent to the 1-consistency of PA, over EFA. Theorems 1-3
for polynomials is provable in EFA (exponential function arithmetic).
Theorem 1 for 2Z and Theorem 3 for just f, are provable in RCA_0.
We now come to the new idea.
The number of times f achieves the value x is the same as the
cardinality of the pre image of x under f, and is among
0,1,2,...,infinity.
POLYNOMIAL SHIFT THEOREM 1. For all polynomials P:Z^k into Z^k, there
exist distinct positive integers n_1,...,n_k+1 such that the number of
times P achieves (n_2,...,n_k+1) exceeds the the number of times P
achieves (n_1,...,n_k) by a nonnegative even integer.
POLYNOMIAL SHIFT THEOREM 2. For all polynomials P:Z^k into Z^k, there
exist distinct positive integers n_1,...,n_k+2 such that the number of
times P achieves (n_1,...,n_k) is at most the number of times P
achieves (n_2,...,n_k+1) is at most the number of times P achieves
(n_3,...,n_k+2).
POLYNOMIAL SHIFT THEOREM 3. For all polynomials P,Q:Z^k into Z^k,
there exist distinct positive integers n_1,...,n_k+1 such that the
number of times P (Q) achieves (n_1,...,n_k) is at most the number of
times P (Q) achieves (n_2,...,n_k+1).
QUADRATIC SHIFT THEOREMS 1-3. Same as the Polynomial Shift Theorems
1-3, but for quadratic polynomials only.
THEOREM 5. All six of the above theorems are provable in ACA' but not
in Peano Arithmetic. They imply 2-Con(PA) over EFA.
Here ACA' is ACA_0 + "for all x,n, the n-th jump of x exists".
I think that they are equivalent to 3-Con(PA) over EFA.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 380th 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 1
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
Harvey Friedman
More information about the FOM
mailing list