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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Apr 2 '15 at 12:13
  • 1
    $\begingroup$ @Joel : Andreas, or Emil? (Did Andreas delete a post near this question?) $\endgroup$ – The Masked Avenger Apr 2 '15 at 17:09
  • $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Apr 2 '15 at 17:35

The answer is no.

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.