[FOM] 387: Better Polynomial Shift Translation/typos
Harvey Friedman
friedman at math.ohio-state.edu
Sun Jan 3 15:05:50 EST 2010
We have found a better Polynomial Shift Translation Theorem by simply
replacing "positive translation" with "translation". It was idiotic
that I didn't see this earlier.
BUT first let me correct two typos in http://www.cs.nyu.edu/pipermail/fom/2010-January/014282.html
I forgot to erase two occurrences of "If". Here is the correction.
UPPER SHIFT GREEDY CLIQUE SEQUENCES
Let G be a simple graph on Q^k. An Upper Shift Greedy Clique Sequence
for G is a nonempty sequence x[1],...,x[n] from Q^k with the following
properties.
i. x[1] is the 0 tuple in Q^k.
ii. Let 2 <= 2m <= n-1. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1]. Then
a. x[2m] <= y and (y,x[2m]) is not an edge of G.
b. x[2m+1] is the upper shift of x[2m].
iii. {x[2],...,x[n]} is a clique in G.
UPPER SHIFT GREEDY DOWN CLIQUE SEQUENCES
Let G be a digraph on Q^k. An Upper Shift Greedy Down Clique Sequence
for G is a nonempty sequence x[1],...,x[n] from Q^k with the following
properties.
i. x[1] is the 0 vector in Q^k.
ii. Let 2 <= 2m <= n-1. Let y be the m-th subsequence of length k of
the concatenation of x[1],...,x[2m-1]. Then
a. x[2m] = y, or (x[2m] < y and (y,x[2m]) is not an edge of G).
b. x[2m+1] is the upper shift of x[2m].
iii. {x[2],...,x[n]} is a down clique in G.
EXTREME UPPER SHIFT GREEDY DOWN CLIQUE SEQUENCES
***no change***
ALSO, the word "open" is quite stupid. Replace "open" with "terminal".
I.e., terminal thread.
NOW for the restatement of the polynomials.
Let n_1,...,n_k be in Z and 1 <= i <= k. The translates of
(n_1,...,n_k) in the i-th coordinate are obtained by adding an integer
to the i-th coordinate.
POLYNOMIAL SHIFT TRANSLATION THEOREM. For all polynomials P:Z^k into
Z^k, there exist distinct positive integers n_1,...,n_k+1 such that,
in each coordinate, the number of translates of (n_1,...,n_k) achieved
by P is at most the number of translates of (n_2,...,n_k+1) achieved
by P.
QUADRATIC SHIFT TRANSLATION THEOREM. For all quadratics P:Z^k into
Z^k, there exist distinct positive integers n_1,...,n_k+1 such that,
in each coordinate, the number of translates of (n_1,...,n_k) achieved
by P is at most the number of translates of (n_2,...,n_k+1) achieved
by P.
THEOREM. Both of the above theorems are provable in ACA' but not
in Peano Arithmetic. They each 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 387th 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
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
Harvey Friedman
More information about the FOM
mailing list