# 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 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 [1]): 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:

[1] 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.