Diophantine Subsets of a Ring

As mentioned above, a good place to start our survey is a definition of Diophantine subsets of a ring. This definition is at the center of much of the work that followed the solution of Hilbert’s Tenth Problem (“HTP” in the future) and by itself is a knot of sorts holding together connections to several areas of Mathematics.

Definition 3.1 (Diophantine Sets: A Number-Theoretic Definition) Let R be a commutative ring with identity. (All the rings considered below satisfy these assumptions.) A subset A c Rm is called Diophantine over R if there exists a polynomial p(T1, ...Tm, Xi,..., Xk) with coefficients in R such that for any element (t1,...,tm) e Rm we have that

In this case we call p(T1, ...,Tm, X1,..., Xk) a Diophantine definition of A over R.

What was proved by Martin Davis, Hilary Putnam, Julia Robinson and Yuri Matiyasevich (“DPRM” in the future) is that recursively enumerable subsets of integers (natural numbers) and Diophantine subsets of integers (natural numbers) were the same. Now the connections to different areas of Mathematics emerge immediately because Diophantine sets can also be described as the sets existentially definable in R in the language of rings or as projections of algebraic sets. We define recursive and recursively enumerable sets below.

Definition 3.2 (Recursive and Recursively Enumerable Subsets of Z) Aset A c Zm is called recursive, computable or decidable if there is an algorithm (or a computer program) to determine the membership in the set.

A set A c Zm is called recursively or computably enumerable (r.e. and c.e. respectively in the rest of the paper) if there is an algorithm (or a computer program) to list the set.

The following theorem is a well-known result from Recursion Theory (see for example [43, Sect. 1.9]).

Theorem 3.1 There exist recursively enumerable sets which are not recursive.

Given the DPRM result we immediately obtain the following important corollary. Corollary 3.1 There are undecidable Diophantine subsets of Z.

It is easy to see that the existence of undecidable Diophantine sets implies that no algorithm as requested by Hilbert exists. Indeed, suppose A c Z is an undecidable Diophantine set with a Diophantine definition P(T, Xi,..., Xk). Assume also that we have an algorithm to determine the existence of integer solutions for polynomial equations. Now, let a e Z and observe that a e A if and only if P (a, X1,..., XK) = 0 has solutions in Zk. So if we can answer Hilbert’s question effectively, we can determine the membership in A effectively.

It is also not hard to see that Diophantine sets are recursively enumerable. Given a polynomial p(T, X) we can effectively list all t e Z such that p(t, X) = 0 has a solution x e Zk in the following fashion. Using a recursive listing of Zk+1, we can plug each (k + 1)-tuple into p(T, X) to see if the value is 0. Each time we get a zero we add the first element of the (k + 1)-tuple to the t-list. So the difficult part of the DPRM proof was to show that every r.e. subset of Z is Diophantine.

< Prev   CONTENTS   Source   Next >