You are here
Home ›Diophantine set
Primary tabs
Diophantine set
A set is said to be Diophantine if
-
there is a polynomial over in variables, , such that iff there is some , such that .
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 example, itself is Diophantine, for the polynomial works. Another trivial example: the set of all positive integers divisible by is Diophantine, for the polynomial works.
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:
-
the set , where and are Diophantine
-
the set , where and are Diophantine
-
the set
-
the set of composite numbers
-
the set of prime numbers
-
the set of powers of a positive integer
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.
References
- 1 M Davis, Computability and Unsolvability. Dover Publications, Inc. New York, 1982
Mathematics Subject Classification
03D99 None of the above, but in MSC2010 section 03Dxx03D80 Applications of computability and recursion theory
- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by unlord
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759
new image: AbstrExample3.jpg by m759
new image: four-diamond_figure.jpg by m759
May 16
new problem: Curve fitting using the Exchange Algorithm. by jeremyboden


