Namespaces
Variants
Actions

Difference between revisions of "Diophantine predicate"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (label)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
Any predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326401.png" /> defined on the set of (ordered) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326402.png" />-tuples of integers (or non-negative integers or positive integers) for which there exists a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326403.png" /> with integer coefficients such that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326404.png" />-tuple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326405.png" /> satisfies the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326406.png" /> if and only if the Diophantine equation (cf. [[Diophantine equations|Diophantine equations]])
+
{{TEX|done}}
 +
Any predicate $\mathcal P$ defined on the set of (ordered) $n$-tuples of integers (or non-negative integers or positive integers) for which there exists a polynomial $P(a_1,\ldots,a_n,z_1,\ldots,z_k)$ with integer coefficients such that the $n$-tuple $\langle a_1,\ldots,a_n\rangle$ satisfies the predicate $\mathcal P$ if and only if the Diophantine equation (cf. [[Diophantine equations|Diophantine equations]])
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326407.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$P(a_1,\ldots,a_n,z_1,\ldots,z_k)=0\label{*}\tag{*}$$
  
is solvable with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326408.png" />. The truth domain of a Diophantine predicate is a [[Diophantine set|Diophantine set]]. The class of Diophantine predicates coincides with the class of recursively enumerable predicates (cf. [[Diophantine equations, solvability problem of|Diophantine equations, solvability problem of]]).
+
is solvable with respect to $z_1,\ldots,z_k$. The truth domain of a Diophantine predicate is a [[Diophantine set|Diophantine set]]. The class of Diophantine predicates coincides with the class of recursively enumerable predicates (cf. [[Diophantine equations, solvability problem of|Diophantine equations, solvability problem of]]).
  
  
  
 
====Comments====
 
====Comments====
The truth domain of a Diophantine predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d0326409.png" /> is the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d03264010.png" />-tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d03264011.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d03264012.png" />, i.e., for which (*) is solvable with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d032/d032640/d03264013.png" />.
+
The truth domain of a Diophantine predicate $\mathcal P$ is the set of all $n$-tuples $\langle\alpha_1,\ldots,\alpha_n\rangle$ satisfying $\mathcal P$, i.e., for which \eqref{*} is solvable with respect to $z_1,\ldots,z_n$.

Latest revision as of 16:59, 14 February 2020

Any predicate $\mathcal P$ defined on the set of (ordered) $n$-tuples of integers (or non-negative integers or positive integers) for which there exists a polynomial $P(a_1,\ldots,a_n,z_1,\ldots,z_k)$ with integer coefficients such that the $n$-tuple $\langle a_1,\ldots,a_n\rangle$ satisfies the predicate $\mathcal P$ if and only if the Diophantine equation (cf. Diophantine equations)

$$P(a_1,\ldots,a_n,z_1,\ldots,z_k)=0\label{*}\tag{*}$$

is solvable with respect to $z_1,\ldots,z_k$. The truth domain of a Diophantine predicate is a Diophantine set. The class of Diophantine predicates coincides with the class of recursively enumerable predicates (cf. Diophantine equations, solvability problem of).


Comments

The truth domain of a Diophantine predicate $\mathcal P$ is the set of all $n$-tuples $\langle\alpha_1,\ldots,\alpha_n\rangle$ satisfying $\mathcal P$, i.e., for which \eqref{*} is solvable with respect to $z_1,\ldots,z_n$.

How to Cite This Entry:
Diophantine predicate. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Diophantine_predicate&oldid=16355
This article was adapted from an original article by Yu.V. Matiyasevich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article