# divisible by all standard prime numbers

This question is about prime numbers in nonstandard models of Peano Arithmetic. Every such model looks like N+AxZ, where A is a dense linear order without end points. There are many nonstandard numbers that are divisible by all standard prime numbers (there is exactly one standard number with this property). Question: does every copy of Z contain a number with this property?

• See also François's answer here mathoverflow.net/a/30084/1946, which provides a $\mathbb{Z}$ chain consisting entirely of composite numbers, using the same idea that Andreas had. – Joel David Hamkins Apr 2 '15 at 12:13
• @Joel : Andreas, or Emil? (Did Andreas delete a post near this question?) – The Masked Avenger Apr 2 '15 at 17:09
• Andreas had posted an answer to the effect that there must be $\mathbb{Z}$ chains consisting of composites, but this doesn't by itself answer Jaap's question, and so he deleted it. – Joel David Hamkins Apr 2 '15 at 17:35

Proposition: Let $f$ be a recursive function. If $M\models\mathrm{PA}$, then every interval $[a,b]$ in $M$ of nonstandard length contains an $x$ such that $$x\equiv f(p)\pmod p$$ for all standard primes $p$.

Proof: Let $\phi(u,v)$ be a $\Sigma_1$ formula representing $f$. The formula $$\psi(w)=\exists x\in[a,b]\,\forall u<w\,\forall v\,(\mathrm{Prime}(u)\land\phi(u,v)\to x\equiv v\pmod u)$$ holds for all standard $w$, hence it holds for some nonstandard $w$ by overspill. QED

Corollary: If $M\models\mathrm{PA}$, then any interval $[a,b]$ in $M$ of nonstandard length contains

1. an $x$ divisible by all standard primes;

2. a copy of $\mathbb Z$ not containing any element divisible by all standard primes.

Proof: Use $f(p)=0$ for 1, and e.g. $f(p_n)=n$ for 2. QED

In fact, we do not need anything as strong as PA for the argument to work. Recall that $E_1$ is the class of all bounded existential formulas.

Proposition: The previous two results hold for $IE_1$ in place of PA.

Rather than giving a direct proof, let me mention that this is an immediate consequence of the following more general result:

Theorem (Wilmers ): If $M$ is a nonstandard model of $IE_1$, then the Presburger reduct $(M,+,<)$ is recursively saturated.

On the other hand, the situation is different for theories on the weaker side of the Tennenbaum barrier.

Theorem: There is a nonstandard model $M\models\mathit{IOpen}$ such that every copy of $\mathbb Z$ in $M$ contains an element divisible by all standard primes.

In fact, it is easy to see that this holds in the Shepherdson model, consisting of Puiseux polynomials $$a_nx^{n/m}+a_{n-1}x^{(n-1)/m}+\dots+a_0,$$ where $a_i\in\mathbb R$, $a_0\in\mathbb Z$: namely, every such polynomial with $a_0=0$ is divisible by all standard integers.

Reference:

 George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90. JSTOR

Here is a construction of a $\mathbb{Z}$-chain none of whose elements are divisible by every standard prime:

Let $p_1,p_2,\ldots$ be the sequence of positive (standard) primes. It follows from the Chinese Remainder Theorem that for each standard positive $N$ there is a standard $a$ satisfying the following equations: \begin{align*} a&\equiv 1\mod p_1\\ a+1&\equiv 1\mod p_2\\ a-1&\equiv 1\mod p_3\\ &\ldots\\ a+N&\equiv 1\mod p_{2N}\\ a-N&\equiv 1\mod p_{2N+1} \end{align*}

Therefore by compactness there is a single non-standard $a$ (in some nonstandard model of PA) satisfying the above equations for every standard $N$. Therefore no element of the chain $a+\mathbb{Z}$ is divisible by every standard prime.