Primality is not existential over true arithmetic

Question

Let $\Phi=\operatorname{Th}(\mathbb{N},+,*,0,1)$ be the theory of true arithmetic and $$\operatorname{prime}(x):=x\neq1\land\forall z(\exists k(x=k*z) \rightarrow (z=1\lor z=x))$$ be a formula for primality. How can I show that $\operatorname{prime}(x)$ is not equivalent to an existential formula modulo $\Phi$? It seems like I have to find two nonstandard models $\mathcal{N}\subset\mathcal{M}$ of $\Phi$ and $n\in N$, which is prime in $\mathcal{N}$ but not in $\mathcal{M}$.

Edit: The motivation for this question came from looking for examples of complete theories that are not model complete. I know that model completeness is equivalent to every formula being equivalent to an existential formula and I wanted to show that this fails for some specific 'interesting' formula.

But as my example doesnt work due to the MRDP Theorem, apparently the problem boils down to finding some formula $\varphi(x)$ which defines some non recursively enumerable set, right?

Answer 1

I don't think what you want to prove is true.

Matiyasevich's theorem states that every recursively enumerable set can be defined by an existential formula over $(\mathbb N,0,1,{+},{\times})$ -- and the set of primes is certainly recursively enumerable.

Answer 2

If you want to find formulas that are not equivalent to existential formulas, you can do this using Post's theorem, which says in particular that there are $m$-complete sets at each level $\Pi^0_n$ and $\Sigma^0_n$ of the arithmetical hierarchy, and so in particular the arithmetical hierarchy does not collapse.

A particular example of a $\Pi^0_1$ complete set is the complement of the halting problem. This set is cannot be definable by an existential formula because then the halting problem would be both r.e. and co-r.e., and so it would be computable. Thus the formula that defines the complement of the halting problem cannot be equivalent to an existential formula. There are examples at higher levels of the arithmetical hierarchy as well.