Diophantine predicate

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$.