A set is said to be Diophantine if
So can be thought of as a set such that, there is a Diophantine equation and a non-negative integer , so that when each element in is “combined” with some -tuple, makes up a solution to a Diophantine equation . In other words, if is a projection function given by where and , then is a Diophantine set iff , where is the zero set of some Diophantine equation . Equivalently, a set is Diophantine if there is a , such that
For a less trivial example, let us show that the set of all triples such that is Diophantine. For the inequality , let . Then the sentence is equivalent to . Similarly, for the inequality , we have the same polynomial . Putting the two inequality together amounts to setting . Thus, the sentence , where and is the same as the inequality .
Some other Diophantine sets are:
Remark. Associated with the concept of a Diophantine set is that of a Diophantine function: a function is said to be Diophantine if its graph is a Diophantine set. Some well-know Diophantine functions are the exponential functions and the factorial function , where are positive integers.
It turns out that a function is Diophantine iff it is recursive. From this, it is possible to prove that Hilbert’s 10th problem is unsolvable.
The idea behind using Diophantine sets to prove the unsolvability of Hilbert’s 10th problem comes from Yuri Matiyaseviĉ, and hence the theorem is known as Matiyaseviĉ’s theorem.
- 1 M Davis, Computability and Unsolvability. Dover Publications, Inc. New York, 1982
|Date of creation||2013-03-22 18:02:50|
|Last modified on||2013-03-22 18:02:50|
|Last modified by||CWoo (3771)|