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.
 A: 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...
A: 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. 
A: I think appealing to overspill or induction in particular is overkill here; being an elementary extension is all we need.
First prove that a $\mathfrak B$-natural $n$ that is not infinitely large is in fact a standard element of $\mathbb N$. By assumption there is a standard real $r$ such that $n<r$, and then we also have $ n < m $ where $m$ is some standard natural larger than $r$. But the fact that every natural less than $m$ is one of $0,1,2,\ldots,m-1$ is a finite first-order sentence, and since it is true in $\mathfrak R$ it is also true in the elementary extension $\mathfrak B$. So $n$ is one of those particular standard naturals.
Next, in $\mathfrak R$ it is true that for every prime $p$ that doesn't equal $1+1$, there is a largest prime less than $p$. This is a first-order property and therefore true in $\mathfrak B$ too.
Therefore, if $p$ is any infinitely large prime, it has an immediate predecessor prime $q$.
All we now need to know is that $q$ itself is infinitely large. However, if $q$ is not infinitely large, then it's standard. And then since it is true in $\mathfrak R$ that the only prime that has $q$ as its immediate predecessor is such-and-such, this is also true in $\mathfrak B$, and $p$ must equal such-and-such. Which contradicts the assumption that $p$ was infinitely large.
A: Just to add another hint:
Show the existence of (or construct) a function $\Pi: \mathbb{N}\to\mathbb{N}$ that maps each natural number $n$ to the n-th prime.
Now assume $\Pi(h)$, where $h$ is an infinite number, to be the smallest infinite prime. What does this say about $\Pi(h-1)$?
A: Assume, for contradiction, there is a smallest infinitely large positive prime, $p$. Consider $p + 1$. Clearly $p$ does not divide it, so by the fundamental theorem of arithmetic (which we know holds in  because it is an elementary extension of ℜ), $p + 1$ has an infinitely large prime divisor that is not $p$. Therefore there is no smallest infinitely large positive prime.
EDIT: This doesn't actually work. As Z. A. K. points out below, an infinitely large integer doesn't necessarily have an infinitely large prime divisor.
