Set of Strictly Positive Integers is Primitive Recursive

Theorem

Let $P \subseteq \N$ be the set of all $n \in \N$ such that:

$n$ codes an integer $k$ such that $k > 0$.

Let $p : \N \to \N$ be defined as:

$\map p n = \map {\operatorname{rem}} {n, 2}$

By:

Suppose $n$ codes an integer $k$ such that $k > 0$.

Then:

$n = 2 k - 1$

Therefore:

$\ds \map p n$

$=$

$\ds \map {\operatorname{rem} } {2 k - 1, 2}$

$\ds $

$=$

$\ds \map {\operatorname{rem} } {2 \paren {k - 1} + 1, 2}$

$\ds $

$=$

$\ds 1$

Definition of Remainder

Suppose $n$ codes an integer $k$ such that $k \le 0$.

Then:

$n = - 2 k$

Therefore:

$\ds \map p n$

$=$

$\ds \map {\operatorname{rem} } {- 2 k, 2}$

$\ds $

$=$

$\ds \map {\operatorname{rem} } {2 \paren {- k}, 2}$

$\ds $

$=$

$\ds 0$

Definition of Remainder

By definition, $p$ is the characteristic function of $P$.

Thus, $P$ is primitive recursive by definition.

$\blacksquare$