Standard model and formulas in logic

Question

If $\phi(v)$ is a formula defining the prime numbers in the standard model, then are there nonstandard elements satisfying $\phi(v)$? What if $\phi(v)$ is a formula for powers of $2$?

Also, what if $\phi(v)$ is a formula so that $v$ is prime and $v+2$ is prime?

So, for the first question, a formula I am assuming could be:

$\{(x,y)| x\cdot y = z \text{ and } x =1 \text{ or } y = 1 \text{ and } z \text{ is not a multiple of } kx \text{ or } ky\}$, so this shows the nonstandard element of $\phi(v)$.

For a formula for powers of $2$: $\{(x,y)|2^x = y\}$.

And for the third one, I dont see how to formulate.

Answer 1

Details depend on whether we are taalking about the non-negative integers or the positive integers. We use the non-negatives.

It is not difficult to write down a formula $\operatorname{Prime}(x)$ that "says" that $x$ is prime. We have to say that $x$ is not $0$ or $1$, and that for all $s$ and $t$, if $st=x$ then $s=x$ or $t=x$. The part about $x$ not $0$ or $1$ can be dealt with by $\lnot x\cdot x=x$, or in other ways.

It is a theorem that for all $u$ there is a prime $\gt u$. So in any non-standard model, there will be "primes" that are not the usual ones. One can construct such objects semi-explicitly in an ultrapower of $\mathbb{N}$.

The "$2^y$" is more complicated, since the usual first-order Peano Arithmetic does not have an exponentiation operation. One can get around it by producing a formula that uses only the allowed function symbols and "represents" the function $2^y$. The details are a little complicated, but classical. Since it is a theorem that for any integer $w$, there is a power of $2$ that is greater than $w$, any non-standard model will have "infinitely large" elements that behave arithmetically like powers of $2$. More simply, we can define a formula $\operatorname{Pow2}(x)$ that says that the only prime that divides $x$ is $2$.

It is not hard to produce a formula $\operatorname{Twins}(u,v)$ that says that $u$ and $v$ are prime and $u$ and $v$ differ by $2$. Since we do not know whether in fact there are infinitely many pairs of twin primes, we cannot come to any conclusion about the existence of "infinitely large" such objects in a nonstandard model.

Answer 2

That there will be non-standard numbers satisfying the first two formulae follows from the

Overspill Lemma (variant): Let $M \models \mathrm{PA}$ be non-standard, and let $I \subsetneq M$ be an initial segment of $M$ which is closed under the successor function. If $\phi ( x , \bar{z} )$ is a formula and $\bar{a} \in M$ are such that for all $x \in I$ there is a $y \in I$ such that $$M \models y \geq x \wedge \phi ( y , \bar{a} ),$$ then for each $c > i$ there is a $b \in M$ with $I < b < c$ and $$M \models ( b , \bar{a} ).$$

In particular, if $M \models \mathrm{PA}$ is nonstandard, then the standard numbers $\mathbb{N} \subsetneq M$ can be taken as such a set $I$. The proof of this result rests on the fact that since $M \models \mathrm{Induction}$ such sets $I$ are not definable.