9
$\begingroup$

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.

$\endgroup$
0

5 Answers 5

6
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ May 22, 2014 at 17:21
  • 1
    $\begingroup$ @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. $\endgroup$ May 22, 2014 at 17:24
  • $\begingroup$ @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. $\endgroup$ May 22, 2014 at 17:26
  • $\begingroup$ 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}$. $\endgroup$ May 22, 2014 at 17:36
  • $\begingroup$ 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. $\endgroup$ May 22, 2014 at 17:38
5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ May 22, 2014 at 17:02
  • 1
    $\begingroup$ 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. $\endgroup$ May 22, 2014 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$ May 22, 2014 at 17:24
  • $\begingroup$ 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. $\endgroup$ May 22, 2014 at 17:32
  • $\begingroup$ Hum, the incompleteness theorem is treated in a later chapter of Kunen's Foundations, so I will watch for this as I read on. $\endgroup$ May 22, 2014 at 17:44
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to Math.SE! From the fact that $p$ is an infinite prime, it does not follow that $p+1$ has infinitely large prime divisors. For example, you can't rule out that $p$ is a Mersenne prime, in which case $p+1$ has exactly one prime divisor, 2, a very finite number.. $\endgroup$
    – Z. A. K.
    Oct 26, 2020 at 22:14
  • 1
    $\begingroup$ Thanks for the correction - I hadn't even thought of the possibility of a finite prime dividing $p + 1$ infinitely many times! $\endgroup$ Oct 27, 2020 at 19:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .