[FOM] 518: Polynomial Independence
Harvey Friedman
hmflogic at gmail.com
Wed Aug 7 06:04:27 EDT 2013
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
By way of background, see my previous Adjacent Ramsey Theorem:
http://www.math.osu.edu/~friedman.8/manuscripts.html #66
http://sendailogic.math.tohoku.ac.jp/CTFM/slides/Pelupessy.pdf
Our last PA independence posting is at
http://www.cs.nyu.edu/pipermail/fom/2012-October/016753.html, which
opened up a new general theory of statements at the PA level,
incorporating the Adjacent Ramsey Theorem. It also contains a very
simple statements about surjective polynomials with integer
coefficients independent of PA (equivalent to the 2-consistency of PA)
- Here we present a stronger statement about polynomials without
assuming surjectivity, that is independent of PA.
POLYNOMIAL PREIMAGE THEOREM A. For all polynomials P:N^k into N^k
there exist n_1 < ... < n_k+1 such that P-1(n_1,...,n_k)) is contained
in P-1(n_2,...,n_k+1) - N^k.
POLYNOMIAL PREIMAGE THEOREM B. For all polynomials P:N^k into Z^k
there exist nonnegative n_1 < ... < n_k+1 such that P-1(n_1,...,n_k)
is contained in P-1(n_2,...,n_k+1) - N^k.
Here A - B = {x - y: x in A and y in B}.
THEOREM 1. PPT is provable in ACA' but not in PA. PPT implies
2-Con(PA) over EFA.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 518th 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-449 can be found
in the FOM archives at
http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
489: Invariant Maximality Programs 3/24/12 2:31PM
490: Invariant Maximality Program 2 3/24/12 3:19PM
491: Formal Simplicity 3/25/12 11:50PM
492: Invariant Maximality/conjectures 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv 4/5/12 4:17PM
495: Invariant Finite Choice 4/5/12 4:18PM
496: Invariant Finite Choice/restatement 4/8/12 2:18AM
497: Invariant Maximality Restated 5/2/12 2:49AM
498: Embedded Maximal Cliques 1 9/18/12 12:43AM
499. Embedded Maximal Cliques 2 9/19/12 2:50AM
500: Embedded Maximal Cliques 3 9/20/12 10:15PM
501: Embedded Maximal Cliques 4 9/23/12 2:16AM
502: Embedded Maximal Cliques 5 9/26/12 1:21AM
503: Proper Classes of Graphs 10/13/12 12:17PM
504. Embedded Maximal Cliques 6 10/14/12 12:49PM
505: Function Transfer Theory 10/21/12 2:15AM
506: Finite Embedded Weakly Maximal Cliques 10/23/12 12:53AM
507: Finite Embedded Dominators 11/6/12 6:40AM
508: Unique Undefinable Elements 12/22/12 8:08PM
509: A Divine Consistency Proof for Mathematics 12/26/12 2:15AM
510: Unique Undefinable Elements Again 1/9/13 5:07PM
511: A Supernatural Consistency Proof for Mathematics 1/10/13 9:19PM
512: Countable Elementary Extensions 1/11/13 7:31PM
513: Five Supernatural Consistency Proofs for Mathematics 1/14/13 1:13AM
514: Countable Elementary Extensions/again 1/14/13 2:19AM
515: Eight Supernatural Consistency Proofs For Mathematics 1/19/13 2:40PM
516: Embedded Maximal Cliques/restatement 5/21/13 1:31PM
517: New Concrete Mathematical Incompleteness 8/2/13 9:57PM
Harvey M. Friedman
More information about the FOM
mailing list