# Diophantine set

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Diophantine_set
> Markdown URL: https://mediated.wiki/source/Diophantine_set.md
> Source: https://en.wikipedia.org/wiki/Diophantine_set
> Source revision: 1322434576
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Solution of some Diophantine equation

In [mathematics](/source/Mathematics), a [Diophantine equation](/source/Diophantine_equation) is an equation of the form *P*(*x*1, ..., *x**j*, *y*1, ..., *y**k*) = 0 (usually abbreviated *P*(*x*, *y*) = 0) where *P*(*x*, *y*) is a [polynomial](/source/Polynomial) with integer [coefficients](/source/Coefficient), where *x*1, ..., *x**j* indicate parameters and *y*1, ..., *y**k* indicate unknowns.

A **Diophantine set** is a [subset](/source/Set_(mathematics)) *S* of N j {\displaystyle \mathbb {N} ^{j}} , the set of all *j*-tuples of natural numbers, so that for some [Diophantine equation](/source/Diophantine_equation) *P*(*x*, *y*) = 0,

- x ¯ ∈ S ⟺ ( ∃ y ¯ ∈ N k ) ( P ( x ¯ , y ¯ ) = 0 ) . {\displaystyle {\bar {x}}\in S\iff (\exists {\bar {y}}\in \mathbb {N} ^{k})(P({\bar {x}},{\bar {y}})=0).}

That is, a parameter value is in the Diophantine set *S* [if and only if](/source/If_and_only_if) the associated Diophantine equation is [satisfiable](/source/Satisfiability) under that parameter value. The use of natural numbers both in *S* and the existential quantification merely reflects the usual applications in [computability theory](/source/Computability_theory) and [model theory](/source/Model_theory). It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers.[1] Also it is sufficient to assume *P* is a polynomial over Q {\displaystyle \mathbb {Q} } and multiply *P* by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem.[2]

The [MRDP theorem](/source/MRDP_theorem) (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is [computably enumerable](/source/Recursively_enumerable_set).[4][5] A set of integers *S* is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of *S* and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to [number theory](/source/Number_theory), can be taken rather in [logical](/source/Mathematical_logic) or computability-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work.

Matiyasevich's completion of the MRDP theorem settled [Hilbert's tenth problem](/source/Hilbert's_tenth_problem). [Hilbert's](/source/David_Hilbert) tenth problem[6] was to find a general [algorithm](/source/Algorithm) that can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision [algorithm](/source/Algorithm) with a [total computable predicate](/source/Recursive_set) allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.

## Examples

In the following examples, the natural numbers refer to the set of positive integers.

The equation

- x = ( y 1 + 1 ) ( y 2 + 1 ) {\displaystyle x=(y_{1}+1)(y_{2}+1)}

is an example of a Diophantine equation with a parameter *x* and unknowns *y*1 and *y*2. The equation has a solution in *y*1 and *y*2 precisely when *x* can be expressed as a product of two integers greater than 1, in other words *x* is a [composite number](/source/Composite_number). Namely, this equation provides a **Diophantine definition** of the set

- {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

consisting of the composite numbers.

Other examples of Diophantine definitions are as follows:

- The equation x = y 1 2 + y 2 2 {\displaystyle x=y_{1}^{2}+y_{2}^{2}} with parameter *x* and unknowns *y*1, *y*2 only has solutions in N {\displaystyle \mathbb {N} } when *x* is a sum of two [perfect squares](/source/Square_number). The Diophantine set of the equation is {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}.

- The equation y 1 2 − x y 2 2 = 1 {\displaystyle y_{1}^{2}-xy_{2}^{2}=1} with parameter *x* and unknowns *y*1, *y*2. This is a [Pell equation](/source/Pell_equation), meaning it only has solutions in N {\displaystyle \mathbb {N} } when *x* is not a perfect square. The Diophantine set is {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}.

- The equation x 1 + y = x 2 {\displaystyle x_{1}+y=x_{2}} is a Diophantine equation with two parameters *x*1, *x*2 and an unknown *y*, which defines the set of pairs (*x*1, *x*2) such that *x*1 < *x*2.

## Matiyasevich's theorem

Matiyasevich's theorem, also called the [Matiyasevich](/source/Yuri_Matiyasevich)–[Robinson](/source/Julia_Robinson)–[Davis](/source/Martin_Davis_(mathematician))–[Putnam](/source/Hilary_Putnam) or MRDP theorem, says:

- Every [computably enumerable set](/source/Recursively_enumerable_set) is Diophantine, and the converse.

A set *S* of integers is **[computably enumerable](/source/Recursively_enumerable)** if there is an algorithm such that: For each integer input *n*, if *n* is a member of *S*, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of *S*. A set *S* of integers is **Diophantine** precisely if there is some [polynomial](/source/Polynomial) with integer coefficients *f*(*n*, *x*1, ..., *x**k*) such that an integer *n* is in *S* if and only if there exist some integers *x*1, ..., *x**k* with *f*(*n*, *x*1, ..., *x**k*) = 0.

It is easy to see that every Diophantine set is computably enumerable: consider a Diophantine equation *f*(*n*, *x*1, ..., *x**k*) = 0. Now we make an algorithm that tries all possible values for *n*, *x*1, ..., *x**k* (in, say, some simple order consistent with the increasing order of the sum of their absolute values), and prints *n* every time *f*(*n*, *x*1, ..., *x**k*) = 0. This algorithm will run forever and will list exactly the *n* for which *f*(*n*, *x*1, ..., *x**k*) = 0 has a solution in *x*1, ..., *x**k*.

[Yuri Matiyasevich](/source/Yuri_Matiyasevich) utilized a method involving [Fibonacci numbers](/source/Fibonacci_number), which [grow exponentially](/source/Exponential_growth), in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by [Julia Robinson](/source/Julia_Robinson), [Martin Davis](/source/Martin_Davis_(mathematician)) and [Hilary Putnam](/source/Hilary_Putnam) – hence, MRDP – had shown that this suffices to show that every [computably enumerable set](/source/Recursively_enumerable_set) is Diophantine.

## Application to Hilbert's tenth problem

[Hilbert's tenth problem](/source/Hilbert's_tenth_problem) asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's result with the fact that most [recursively enumerable languages](/source/Recursively_enumerable_language) are not [decidable](/source/Recursive_language) implies that a solution to Hilbert's tenth problem is impossible.

### Refinements

Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977)[7] or 11 integer variables ([Sun Zhiwei](/source/Sun_Zhiwei), 1992).[8]

## Further applications

Matiyasevich's theorem has since been used to prove that many problems from [calculus](/source/Calculus) and [differential equations](/source/Differential_equation) are unsolvable.

One can also derive the following stronger form of [Gödel's first incompleteness theorem](/source/G%C3%B6del's_first_incompleteness_theorem) from Matiyasevich's result:

- *Corresponding to any given consistent axiomatization of number theory,[9] one can explicitly construct a Diophantine equation that has no solutions, but such that this fact cannot be proved within the given axiomatization.*

According to the [incompleteness theorems](/source/Incompleteness_theorem), a powerful-enough consistent axiomatic theory is incomplete, meaning the truth of some of its propositions cannot be established within its formalism. The statement above says that this incompleteness must include the solvability of a diophantine equation, assuming that the theory in question is a number theory.

## Notes

1. **[^](#cite_ref-1)** ["Diophantine set"](http://encyclopediaofmath.org/index.php?title=Diophantine_set&oldid=46710). *[Encyclopedia of Mathematics](/source/Encyclopedia_of_Mathematics)*. Retrieved 11 March 2022.

1. **[^](#cite_ref-FOOTNOTEPheidasZahidi2008_2-0)** [Pheidas & Zahidi 2008](#CITEREFPheidasZahidi2008).

1. **[^](#cite_ref-FOOTNOTEMatiyasevich1970_3-0)** [Matiyasevich 1970](#CITEREFMatiyasevich1970).

1. **[^](#cite_ref-4)** The theorem was established in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem.[3] However, the proof given by Matiyasevich relied extensively on previous work on the problem and the mathematical community has moved to calling the equivalence result the MRDP theorem or the Matiyasevich–Robinson–Davis–Putnam theorem, a name that credits all the mathematicians that made significant contributions to this theorem

1. **[^](#cite_ref-FOOTNOTESmith2024_5-0)** [Smith 2024](#CITEREFSmith2024).

1. **[^](#cite_ref-6)** [David Hilbert](/source/David_Hilbert) posed the problem in his celebrated list, from his 1900 address to the [International Congress of Mathematicians](/source/International_Congress_of_Mathematicians).

1. **[^](#cite_ref-FOOTNOTEMatiyasevich1993_7-0)** [Matiyasevich 1993](#CITEREFMatiyasevich1993).

1. **[^](#cite_ref-FOOTNOTESun_Zhi-Wei1992_8-0)** [Sun Zhi-Wei 1992](#CITEREFSun_Zhi-Wei1992).

1. **[^](#cite_ref-9)** More precisely, given a [Σ 1 0 {\displaystyle \Sigma _{1}^{0}} -formula](/source/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_formulas) representing the set of [Gödel numbers](/source/G%C3%B6del_number) of [sentences](/source/Sentence_(mathematical_logic)) that recursively axiomatize a [consistent](/source/Consistency) [theory](/source/Theory_(mathematical_logic)) extending [Robinson arithmetic](/source/Robinson_arithmetic).

## References

- [Davis, Martin](/source/Martin_Davis_(mathematician)) (1973). "Hilbert's Tenth Problem is Unsolvable". *[American Mathematical Monthly](/source/American_Mathematical_Monthly)*. **80** (3): 233–269. [doi](/source/Doi_(identifier)):[10.2307/2318447](https://doi.org/10.2307%2F2318447). [ISSN](/source/ISSN_(identifier)) [0002-9890](https://search.worldcat.org/issn/0002-9890). [JSTOR](/source/JSTOR_(identifier)) [2318447](https://www.jstor.org/stable/2318447). [Zbl](/source/Zbl_(identifier)) [0277.02008](https://zbmath.org/?format=complete&q=an:0277.02008).

- [Matiyasevich, Yuri V.](/source/Yuri_Matiyasevich) (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. *[Doklady Akademii Nauk SSSR](/source/Doklady_Akademii_Nauk_SSSR)* (in Russian). **191**: 279–282. [MR](/source/MR_(identifier)) [0258744](https://mathscinet.ams.org/mathscinet-getitem?mr=0258744). English translation in *Soviet Mathematics* **11** (2), pp. 354–357.

- [Matiyasevich, Yuri V.](/source/Yuri_Matiyasevich) (1993) [1977]. *Hilbert's 10th Problem*. MIT Press Series in the Foundations of Computing. Foreword by Martin Davis and Hilary Putnam. Cambridge, MA: MIT Press. [ISBN](/source/ISBN_(identifier)) [0-262-13295-8](https://en.wikipedia.org/wiki/Special:BookSources/0-262-13295-8). [Zbl](/source/Zbl_(identifier)) [0790.03008](https://zbmath.org/?format=complete&q=an:0790.03008). original Russian edition; English translation

- Pheidas, Thanases; Zahidi, Karim (2008). ["Decision problems in algebra and analogues of Hilbert's tenth problem"](https://scholar.archive.org/work/u2qccxcwindxlmlm4dh7syojlq). *Model theory with applications to algebra and analysis. Vol. 2*. London Mathematical Society Lecture Note Series. Vol. 350. Cambridge University Press. pp. 207–235. [doi](/source/Doi_(identifier)):[10.1017/CBO9780511735219.007](https://doi.org/10.1017%2FCBO9780511735219.007). [ISBN](/source/ISBN_(identifier)) [978-0-521-70908-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-521-70908-8). [MR](/source/MR_(identifier)) [2436143](https://mathscinet.ams.org/mathscinet-getitem?mr=2436143).

- Shlapentokh, Alexandra (2007). *Hilbert's tenth problem. Diophantine classes and extensions to global fields*. New Mathematical Monographs. Vol. 7. Cambridge: [Cambridge University Press](/source/Cambridge_University_Press). [ISBN](/source/ISBN_(identifier)) [978-0-521-83360-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-521-83360-8). [Zbl](/source/Zbl_(identifier)) [1196.11166](https://zbmath.org/?format=complete&q=an:1196.11166).

- Smith, Peter (2024-09-12). [The MRDP Theorem](https://www.logicmatters.net/resources/pdfs/MRDP.pdf) (PDF) (Report). University of Cambridge. Retrieved 2025-09-25.

- [Sun Zhi-Wei](/source/Sun_Zhiwei) (1992). ["Reduction of unknowns in Diophantine representations"](http://math.nju.edu.cn/~zwsun/12d.pdf) (PDF). *Science China Mathematics*. **35** (3): 257–269. [Zbl](/source/Zbl_(identifier)) [0773.11077](https://zbmath.org/?format=complete&q=an:0773.11077). [Archived](https://web.archive.org/web/20110707025032/http://math.nju.edu.cn/~zwsun/12d.pdf) (PDF) from the original on 2011-07-07.

## External links

- [Matiyasevich theorem](http://www.scholarpedia.org/article/Matiyasevich_theorem) article on [Scholarpedia](/source/Scholarpedia).

---
Adapted from the Wikipedia article [Diophantine set](https://en.wikipedia.org/wiki/Diophantine_set) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Diophantine_set?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.