Set of Even Numbers is Primitive Recursive
Jump to navigation
Jump to search
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$