Difference between revisions of "Diophantine predicate"
From Encyclopedia of Mathematics
(Importing text file) |
m (label) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | Any predicate | + | {{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]]) | ||
| − | + | $$P(a_1,\ldots,a_n,z_1,\ldots,z_k)=0\label{*}\tag{*}$$ | |
| − | is solvable with respect to | + | 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 | + | 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
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