# There is no smallest infinitely large prime

I'm reading Kunen's Foundations of Mathematics and trying to solve Exercise II.16.19, which constructs an elementary extension of the reals as an ordered field, and asks the reader to prove various properties. I'm stuck on proving that there is no smallest infinitely large prime.

Here's the setup (abbreviated). $\mathcal{L}$ is the lexicon $\{0, 1, +, \cdot, -, i, <, Z\}$. $i$ here indicates "multiplicative inverse", and $Z$ is the unary predicate "is an integer". Let $\mathfrak{R}$ be the structure with universe $\mathbb{R}$, where the symbols in $\mathcal{L}$ are interpreted in the obvious way. Then let $\mathfrak{B} \succneqq \mathfrak{R}$ be a proper elementary extension of $\mathfrak{R}$, whose existence is guaranteed by the upward Löwenheim-Skolem-Tarski theorem, and $B \supsetneqq \mathbb{R}$ its universe. We note in particular that $\mathfrak{B}$ is an ordered field so usual arithmetic notation makes sense. We say an element $b \in B$ is infinitely large if $|b| > r$ for every $r \in \mathbb{R}$.

An element $p$ of a structure over $\mathcal{L}$ is prime iff we have $p \ge 2$, $Z(p)$, and there do not exist $x,y$ such that $Z(x)$, $Z(y)$, $1<x<p$, and $p=x\cdot y$. (I have tweaked Kunen's definition slightly to rule out negative primes, which are not considered in this problem.) Of course, in $\mathfrak{R}$, this is the usual notion of a prime number.

I have proved that infinitely large primes exist in $\mathfrak{B}$ and that the set of infinitely large primes in $B$ is unbounded above. Now I wish to:

Show that there is no smallest infinitely large prime in $\mathfrak{B}$. That is, for any infinitely large prime $p$, there is an infinitely large prime $q$ with $q < p$.

I am a bit stuck. The main tool available to us that $\mathfrak{B}$ is an elementary extension of $\mathfrak{R}$, which means that if $\varphi$ is any first-order formula of $\mathcal{L}$, we have $\mathfrak{R} \vDash \varphi(r)$ for every $r \in \mathbb{R}$ iff $\mathfrak{B} \vDash \varphi(r)$ for every $r \in \mathbb{R}$ (and likewise for formulas $\varphi(r_1, \dots, r_n)$ with several free variables). In particular, every sentence of $\mathcal{L}$ (with no free variables) that holds in $\mathfrak{R}$ also holds in $\mathfrak{B}$.

I thought of trying to produce the prime $q$ by using the fact that, in $\mathcal{R}$, for every integer $n$ there is a prime between $n$ and $n!$. But I don't know how to express the factorial function in a first-order way. (I thought of using some larger function, like $n^n$, but that doesn't seem any better.)

A crazy idea I had is to use some weak version of the Goldbach conjecture. For instance, Vinogradov's theorem proves that, in $\mathfrak{R}$, every sufficiently large odd number is the sum of three primes, and apparently Borozdin showed that $3^{3^{15}}$ is large enough. In particular, every prime larger than $3^{3^{15}}$ is the sum of three primes. This is easily expressed as a first-order sentence of $\mathcal{L}$ so it must also be true in $\mathfrak{B}$. Thus every infinitely large prime $p$ in $\mathfrak{B}$ is a sum of three primes, all of which are less than $p$, and at least one of those three must be infinitely large. But this can't possibly be the "right" solution!

Any hints would be welcome.

-

Hint: Suppose toward a contradiction that $p$ is the smallest infinite prime. There is a prime between zero and $p$. Moreover, if there is a prime between $n$ and $p$, then there is a prime between $n+1$ and $p$. Therefore...

-
Therefore, for every finite $n$, there is a prime between $n$ and $p$. But I already know this: there are infinitely many finite primes, so there is a (finite) prime between $n$ and $p$. I don't see how to use this to construct an infinitely large prime. What am I missing? – Nate Eldredge May 22 '14 at 17:21
@NateEldredge Therefore, for every positive integer $n$, there is a prime between $n$ and $p$. You can use first-order induction on the nonstandard positive integers in your nonstandard model. – Trevor Wilson May 22 '14 at 17:24
@NateEldredge Indeed, it is the fact that the set of primes is unbounded in the finite integers (and also definable) that allows this proof to work; no further number theory is necessary. – Trevor Wilson May 22 '14 at 17:26
Oh, I get it now. Assume $p$ is the smallest infinite prime. The statement "if there is a prime between $n$ and $p$, there is a prime between $n+1$ and $p$" is true for all integers $n$. If $n$ is finite then it is true because there are infinitely many finite primes. And if $n$ is infinite then it is vacuously true because by assumption there are no infinite primes smaller than $p$. But the principle of induction can be written as a first-order sentence and it's true in $\mathfrak{R}$, so it's also true in $\mathfrak{B}$. – Nate Eldredge May 22 '14 at 17:36
That's right. This argument is an instance of overspill (en.wikipedia.org/wiki/Overspill.) EDIT: technically, first-order induction is a first-order schema rather than a first-order sentence. Anyway, we only need one instance of this schema there. – Trevor Wilson May 22 '14 at 17:38

Hint: Use the fact that if $x\gt 1$, there is always a prime between $x$ and $2x$. (You will want to show that for any infinite $y$ there is an infinite $w$ such that $2w\le y$.)

Remarks: The "fact" is usually called Bertrand's Postulate, and has been a theorem since about $1850$.

Every recursive function is definable, so one could travel through the $n!$ route you suggested.

-
Aha. I wondered if something like this might be true, but I'm weak on number theory and didn't know Bertrand's postulate off the top of my head. Of course, to make it easy we could write some cruder sentence like "for every real $x>2$ there is a prime between $\frac{1}{4}x$ and $x$." I wonder if there is something even more elementary? – Nate Eldredge May 22 '14 at 17:02
I have added a less elementary observation: all recursive functions are definable, so you can use bounds like the ones you suggested. But the Bertrand bound is syntactically simple. – André Nicolas May 22 '14 at 17:06
What's a good reference for the fact that every recursive function is definable? I didn't see it in a quick skim through Kunen. – Nate Eldredge May 22 '14 at 17:24
It is done in every book that proves the Incompleteness Theorem/Undecidability of arithmetic. Usually one proves far more, representability in a quite weak arithmetic. A book I have used is Shoenfield/s Mathematical Logic, but it is done there at too high a level. – André Nicolas May 22 '14 at 17:32
Hum, the incompleteness theorem is treated in a later chapter of Kunen's Foundations, so I will watch for this as I read on. – Nate Eldredge May 22 '14 at 17:44