Signum Function is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\operatorname{sgn}: \N \to \N$ be defined as the signum function.

Then:

$\operatorname{sgn}$ is primitive recursive.
$\overline {\operatorname{sgn}}$ is primitive recursive.


Proof

We have that the characteristic function $\chi_{\N^*}$ of $\N^*$, where $\N^* = \N \setminus \left\{{0}\right\}$, is primitive recursive.

We also have by definition that $\operatorname{sgn} \left({n}\right) = \chi_{\N^*} \left({n}\right)$.

Thus $\operatorname{sgn}$ is primitive recursive.


Now $\N - \N^* = \left\{{0}\right\}$ from Relative Complement of Relative Complement.

We also have by definition that $\overline {\operatorname{sgn}} \left({n}\right) = \chi_{\left\{{0}\right\}} \left({n}\right)$.

Thus $\overline {\operatorname{sgn}}$ is primitive recursive from Complement of Primitive Recursive Set.

$\blacksquare$