[FOM] 518: Polynomial Independence

[Harvey Friedman]

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