Set of Even Numbers is Primitive Recursive

Theorem

Let $E \subseteq \N$ be the set of all even natural numbers.

Then $E$ is primitive recursive.

Proof

If $n \in E$ then $n$ is of the form $n = 2 k$ where $k \in \N$.

We have that:

• if the characteristic function $\chi_E \left({n}\right) = 1$ then $\chi_E \left({n + 1}\right) = 0$.
• if the characteristic function $\chi_E \left({n}\right) = 0$ then $\chi_E \left({n + 1}\right) = 1$.

So $\chi_E$ can be defined by:

$\chi_E \left({n}\right) = \begin{cases}

1 & : n = 0 \\ \overline{\operatorname{sgn}} \left({\chi_E \left({n-1}\right)}\right) & : n > 0 \end{cases}$

So $\chi_E$ is obtained by primitive recursion from the constant $1$ and the primitive recursive function $\overline{\operatorname{sgn}}$.

Hence the result.

$\blacksquare$