There Exists a Non-Recursively Enumerable Set ( {n in mathbb{N}: varphi(n)} ) Such That the Formula ( varphi(n) ) Is Short and Can Be Easily Translated into a First-Order Formula Which Uses Only + and ( cdot )

We prove that the set ( T=Bigl{ninmathbb{N}: exists p,qinmathbb{N};Bigl((2n=(p+q)(p+q+1)+2q);wedge ) ( forall (x_0,ldots,x_p)inmathbb{N}^{p+1};exists (y_0,ldots,y_p)in{0,ldots,q}^{p+1} ) ( bigl((forall kin{0,ldots,p};(1=x_k Rightarrow 1=y_k));wedge ) ( (forall i,j,kin{0,ldots,p};(x_i+x_j=x_k Rightarrow y_i+y_j=y_k));wedge ) ( (forall i,j,kin{0,ldots,p};(x_icdot x_j=x_k Rightarrow y_icdot y_j=y_k))bigr)Bigr)Bigr} ) is not recursively enumerable. By using Gödel’s ( beta ) function, we prove that the formula that defines the set T can be easily translated into a first-order formula which uses only + and ( cdot ). The same properties has the set ( Bigl{ninmathbb{N} : exists p,qinmathbb{N};Bigl((2n=(p+q)(p+q+1)+2q);wedge ) ( forall (x_0,ldots,x_p)inmathbb{N}^{p+1};exists (y_0,ldots,y_p)in{0,ldots,q}^{p+1} ) ( bigl((forall j,kin{0,ldots,p};(x_j+1=x_k Rightarrow y_j+1=y_k));wedge ) ( (forall i,j,kin{0,ldots,p};(x_icdot x_j=x_k Rightarrow y_icdot y_j=y_k))bigr)Bigr)Bigr} ).