Prime Enumeration Function is Primitive Recursive
Theorem
Let the function $p: \N \to \N$ be the prime enumeration function, defined as:
- $p \left({n}\right) = \begin{cases} 1 & : n = 0 \\ \mbox{the } n \mbox{th prime number} & : n > 0 \end{cases}$
Then $p$ is primitive recursive.
Proof
We can define $p$ recursively by:
- $p \left({n + 1}\right) = \text{the smallest } y \in \N \text { such that } y \text { is prime and } p \left({n}\right) \le y$
Hence we can express it as:
- $p \left({n + 1}\right) = \mu y \left({\chi_\Bbb P \left({y}\right) = 1 \land p \left({n}\right) \le y}\right)$
where:
- $\chi_\Bbb P \left({y}\right)$ is the characteristic function of the set of prime numbers $\Bbb P$
- $\mu y \left({\mathcal R}\right)$ means the smallest $y \in \N$ such that the relation $\mathcal R$ holds.
Now consider the relation $\mathcal S$ given by:
- $\mathcal S \left({m, y}\right) \iff \chi_\Bbb P \left({y}\right) = 1$.
We have a reason for making $\mathcal S$ a binary relation, even though $m$ is not actually invoked in its definition.
Then we have:
- $\chi_\mathcal S \left({m, y}\right) = \chi_{\operatorname{eq}} \left({\chi_\Bbb P \left({y}\right), 1}\right)$.
So $\chi_\mathcal S$ is primitive recursive as it is obtained by substitution from:
Then we have that $<$ is primitive recursive.
So we define the relation $\mathcal R$ by:
- $\mathcal R \left({m, y}\right) \iff \mathcal S \left({m, y}\right) \land m < y \iff \chi_\Bbb P \left({y}\right) = 1 \land m < y$.
This is primitive recursive from the above and Set Operations on Primitive Recursive Relations.
Now let us define the function $g: \N^2 \to \N$ as:
- $g \left({m, z}\right) = \mu y \le z \left({\chi_\Bbb P \left({y}\right) = 1 \land m < y}\right)$
which is primitive recursive by Bounded Minimization is Primitive Recursive.
We note that $g \left({p \left({n}\right), z}\right) = p \left({n + 1}\right)$ as long as $p \left({n + 1}\right) \le z$.
Next, let $h: \N \to \N$ be defined as $h \left({n}\right) = \exp \left({2, \exp \left({2, n}\right)}\right)$.
Then $h$ is primitive recursive since it is obtained by substitution from:
From Upper Bounds for Prime Numbers, we have $p \left({n+1}\right) \le 2^{2^n} = h \left({n}\right)$.
It follows that:
- $p \left({n+1}\right) = g \left({p \left({n}\right), h \left({n}\right)}\right)$
where $g$ and $h$ are both primitive recursive.
So using the definition of $p$ as given above, we have:
- $p \left({0}\right) = 1$
- $p \left({n+1}\right) = g \left({p \left({n}\right), h \left({n}\right)}\right)$.
So $p$ is defined by primitive recursion from the constant $1$ and the primitive recursive functions $g$ and $h$.
$\blacksquare$
Note
Note that we use the extravagantly large upper bound $2^{2^n}$ for the prime number $p \left({n+1}\right)$ because it is convenient in this context. Smaller ones would of course do the same job.