# 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 *R ^{m}* is called Diophantine over

*R*if there exists a polynomial

*p(T*i,...,

_{1}, ...T_{m}, X*X*with coefficients in

_{k})*R*such that for any element

*(t*we have that

_{1},...,t_{m}) e R^{m}

In this case we call *p(T _{1}, ...,T_{m}, X_{1},..., X_{k}*) 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 Z^{m }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 Z^{m} 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, X*i,..., *X _{k}).* 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, X*

_{1},...,

*X*0 has solutions in Z

_{K}) =^{k}. 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 Z^{k} in the following fashion. Using a recursive listing of Z^{k+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.