Set of Prime Numbers is Primitive Recursive
Theorem
The set $\Bbb P$ of prime numbers is primitive recursive.
Proof
A prime number is defined as an element of $\N$ with exactly two positive divisors.
So, we have that $n > 0$ is prime if and only if $\map \tau n = 2$, where $\tau: \N \to \N$ is the divisor count function.
Thus we can define the characteristic function of the set of prime numbers $\Bbb P$ as:
- $\forall n > 0: \map {\chi_\Bbb P} n := \map {\chi_{\operatorname {eq} } } {\map \tau n, 2}$
Now we let $g: \N^2 \to \N$ be the function given by:
- $\map g {n, z} = \begin{cases}
0 & : z = 0 \\ \ds \sum_{y \mathop = 1}^z \map {\operatorname {div} } {n, y} & : z > 0 \end{cases}$
As:
it follows that $g$ is primitive recursive.
Then for $n > 0$:
- $\ds \map g {n, n} = \sum_{y \mathop = 1}^n \map {\operatorname {div} } {n, y} = \map \tau n$
and from Divisor Count Function is Primitive Recursive we have that $g$ is primitive recursive.
Then let $h: \N \to \N$ be the function defined as:
- $\map h n = \map g {n, n}$
which is also primitive recursive.
So we have, for all $n \in \N$:
- $\map {\chi_\Bbb P} n = \map {\chi_{\operatorname {eq} } } {\map h n, 2}$
Hence the result.
$\blacksquare$