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.
Sure about the less-than-or equal-to at the end of those expressions? Surely it should be less-than? See talk page.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
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.
