[FOM] 199:Radical Polynomial Behavior Theorems
Harvey Friedman
friedman at math.ohio-state.edu
Mon Dec 22 13:22:54 EST 2003
A radical polynomial in k variables x1,...,xk is a finite sum of radical
monomials with real coefficients. A radical monomial is a finite product of
nonnegative rational powers of variables. 1 is the trivial radical monomial.
We prove a Radical Polynomial Behavior Theorem to the effect that for any
function f:Z+^k< into Z+ there is a radical polynomial P:[0,infinity)^k<
into R+ such that f and P exhibit the same behavior when restricted to some
common infinite A^k<. An obvious finite form also holds. This obvious finite
form is, however,
*independent of Peano Arithmetic.*
This may raise the known incompleteness of PA to a new thematic level.
Let Z be the set of all positive integers, Q be the set of all rational
numbers, and R be the set of all real numbers. For A containedin R, let A+
be the set of all positive elements of A. Let A^k< be the set of all
strictly increasing k-tuples from A.
Let f,g:A^k< into R. We say that f,g have the same behavior if and only if
for all x1 < ... < xk from A, y1 < ... < yk from A, and 1 <= i <= k, we have
f(x1,...,xk) < xi iff g(x1,...,xk) < xi.
f(x1,...,xk) < f(y1,...,yk) iff g(x1,...,xk) < g(y1,...,yk).
I.e., we preserve the truth values of all unnested atomic relations.
THEOREM 1. For all f:Z+^k< into Z+ there exists a radical polynomial P:R+^k<
into R+ and infinite A containedin Z+ such that f,P restricted to A^k< have
the same behavior. In fact, we may require that P have rational
coefficients.
THEOREM 2. For all k,p in Z+ there exists n in Z+ such that the following
holds. For all f:{1,...,n}^k< into Z+ there exists a radical polynomial
P:R+^k< into R+ and p element A containedin {1,...,n} such that f,P
restricted to A^k< have the same behavior.
Using the decision procedure for real closed fields, Theorem 2 is in Pi-0-3
form.
THEOREM 3. Theorem 1 is provably equivalent, over RCA0, to "the jump
operator can be iterated any finite number of times starting with any set".
Theorems 2 is provably equivalent, over EFA, to the 1-consistency of Peano
Arithmetic.
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 198th 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
178:Diophantine Shift Sequences 6/14/03 6:34PM
179:Polynomial Shift Sequences/Correction 6/15/03 2:24PM
180:Provable Functions of PA 6/16/03 12:42AM
181:Strict Reverse Mathematics 2:06/19/03 2:06AM
182:Ideas in Proof Checking 1 6/21/03 10:50PM
183:Ideas in Proof Checking 2 6/22/03 5:48PM
184:Ideas in Proof Checking 3 6/23/03 5:58PM
185:Ideas in Proof Checking 4 6/25/03 3:25AM
186:Grand Unification 1 7/2/03 10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03 4:43AM
189:Some Model theoretic Pi-0-1 statements 9/25/03 11:04AM
190:Diagrammatic BRT 10/6/03 8:36PM
191:Boolean Roots 10/7/03 11:03 AM
192:Order Invariant Statement 10/27/03 10:05AM
193:Piecewise Linear Statement 11/2/03 4:42PM
194:PL Statement/clarification 11/2/03 8:10PM
195:The axiom of choice 11/3/03 1:11PM
196:Quantifier complexity in set theory 11/6/03 3:18AM
197:PL and primes 11/12/03 7:46AM
198:Strong Thematic Propositions 12/18/03 10:54AM
Harvey Friedman
More information about the FOM
mailing list