Arithmetical representations of recursively enumerable sets with a~small number of quantifiers

Yu. V. Matiyasevich

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part V, Tome 32 (1972), pp. 77-84

Résumé

It is shown that every recursively enumerable set $M$ of positive integers can be represented in each of the following forms: \begin{align} a\in M\Leftrightarrow\exists_p\exists_s\{i=1}^\pi\exists_v[A_i(a,p,s,v)>0],\notag\\ a\in M\Leftrightarrow\exists_s\{i=1}^\pi\exists_p\exists_v[B_i(a,p,s,v)>0],\notag\\ a\in M\Leftrightarrow\exists_t\forall y_{\leq t} \exists_v\exists_w[C(a,t,y,v,w)=0].\notag \end{align} Here $\pi$ is a particular integer, $A_i$, $B_i$, $C$ are polynomials with integer coefficients, $a$, $p$, $s$, $t$, $v$, $w$, $y$ ware variables for positive integers.