Prime numbers on a non-standard model

Question

I can't imagine how this is possible:

Let $\mathcal{M}$ be a nonstandard model of arithmetic. Show that:

• There is an element $a\in M$ such that for all prime numbers $p$, we have that $\mathcal{M} \vDash S^p0|a$.
• There is an element $a\in M$, $a>1$ such that for no prime number $p$, we have that $\mathcal{M} \vDash S^p0|a$.

Thank you so much! :)

Answer 1

Let $\varphi$ be the sentence that says that for every $x\gt 0$ there is a $y\gt 0$ such that $t$ divides $y$ for every $t$ in the interval $0\lt t\le x$.

This sentence is not difficult to write down in the usual language of first-order arithmetic, and is true in the natural numbers.

Now let $M$ be a non-standard model of "true arithmetic," and let $m\in M$ be larger than every standard integer. Then since $\varphi$ is true in $M$, there is an $a$ such that $t$ divides $a$ for every $t$ in the interval $0\lt t\le m$. In particular, every standard prime divides $a$. (Since $\varphi$ is a theorem of first-order Peano arithmetic, the same argument works for models of that theory.)

For the second part, instead of the $a$ of the previous argument, use $a+1$.

Answer 2

Your notation for the first claim suggest you mean "every prime" to be every standard prime. Then it can happen, since there are numbers $a$ in the model greater than all standard numbers and thus greater than all standard primes, and every such number has a factorial $a!$. No number in any model is divisible by every prime in the model, since PA proves every number has some prime greater than it.

Also, no model has a number not divisible by any prime in the model; but every nonstandard model has numbers not divisible by any standard prime, since you can take the number $a$ above and take any prime greater than that.

Answer 3

I can't imagine how this is possible

The point of this kind of problem is that functions like $N!$ for the first problem and $N!+1$ for the second extend to the whole nonstandard model, and share the same first-order properties (such as being divisible or not by all the primes up to $N$) but their values at infinite $N$ have interesting properties when viewed externally.