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:

• the primitive recursive function $\chi_{\operatorname{eq}}$

• the primitive recursive function $\chi_\Bbb P$.

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:

• the primitive recursive function $\exp$;
• the constant $2$.

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.