Set of Natural Numbers is Primitive Recursive
Jump to navigation
Jump to search
Theorem
The set of natural numbers $\N$ is primitive recursive.
Proof
The characteristic function $\chi_\N: \N \to \N$ is defined as:
- $\forall n \in \N: \chi_\N \left({n}\right) = 1$.
So:
- $\chi_\N \left({n}\right) = f^1_1 \left({n}\right)$
The constant function $f^1_1$ is primitive recursive.
Hence the result.
$\blacksquare$