[FOM] 188:Applications of Hilbert's 10th

Sun Jul 6 04:43:21 EDT 2003

Before we get to the content of this posting, let me correct a typo 
in my posting Re: Correction: [FOM] Logically Full Structures and 
Theories, 11:31AM, 7/5/03:

I wrote:

>CONJECTURE. The DC axioms are complete. I.e., every consistent sentence has a
>model definable in every DC ring.

This should read:

CONJECTURE. The DC axioms are logically full. I.e., every consistent 
sentence has a model definable in every DC ring.

##########################################

SOME APPLICATIONS OF HILBERT'S TENTH PROBLEM
Harvey M. Friedman
July 5, 2003

1. SURJECTIVITY OF FULLY INTEGRAL POLYNOMIALS.

Here a "fully integral polynomial" is a polynomial function whose 
domain is some Z^n and whose range is included in Z. Obviously, its 
coefficients must be integers.

THEOREM 1.1. The set of all fully integral polynomials which are onto 
Z is not recursive. In fact, it is complete Pi-0-2.

2. ONE VARIABLE CALCULUS.

We consider only functions f:R into R, where R is the set of all real numbers.

We say that a set E of such functions is a ring if and only if

i) the constantly 1 function and the identity function lies in E;
ii) for all f,g in E, f+g and f-g are in E.

Note that we do NOT throw in all constant functions.

The K be the least ring of functions such that for all f in K, the 
function sin(f(x)) lies in K.

Thus in K, arbitrary iterations of the sine function are supported. 
Below, S is much more restrictive.

Let S be the least ring of functions such that for all integers n >= 1,

i) the function sin(x^n) lies in S;
ii) the function sin(x sin(x^n)) lies in S.

THEOREM 2.1. (Known). The set of (expressions for) functions in K 
which have a zero is r.e. hard. The set of (expressions for) 
functions in K which have a nonnegative value is r.e. hard. The set 
of (expressions for) functions in K which have a positive value is 
complete r.e.

See Y. Matiyasevich, Hilbert's tenth Problem, MIT Press, 1993, 
168-174, and the discussion on 179, where a number of people are 
credited for the this and other results, sometimes relying on 
Hilbert's tenth Problem before it was solved by Matiyasevich, 
Robinson, Putnam, Davis.

THEOREM 2.2. (New?). The set of (expressions for) functions in S 
which have a zero is r.e. hard. The set of (expressions for) 
functions in S which have a nonnegative value is r.e. hard. The set 
of (expressions for) functions in S which have a positive value is 
complete r.e.

Note that all equations and inequalities in Theorems 2.1 and 2.2 are 
being solved in the reals.

3. SUPREMUMS OF FULLY INTEGRAL RATIONAL FUNCTIONS.

THEOREM 3.1. The supremums of ratios of fully integral polynomials 
(that exist) are exactly the real numbers whose left cut is 
recursively enumerable.

There is no simple way to define the concept of r.e. set of natural 
numbers from the left r.e. reals we get in Theorem 3.1.

However, a real number has an arithmetical left (right) cut if and 
only if its base 2 expansion is arithmetical. Obviously arithmeticity 
of real numbers is quite robust. So it is nice to extend Theorem 3.1 
to the arithmetical reals.

THEOREM 3.2. The set of all arithmetical real numbers forms the least 
nonempty set K of real numbers such that all supremums of ratios of 
polynomials in several integer variables with coefficients from K lie 
in K.

*********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 188th 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

Harvey Friedman