Signum Function on Integers is Primitive Recursive

Theorem

Let $\sgn_\Z : \Z \to \set {-1, 0, 1}$ denote the signum function on the integers.

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

$\map s n = m$

where:

$n$ codes the integer $k$

$m$ codes the integer $\map {\sgn_\Z} k$

Then $s$ is a primitive recursive function.

Proof

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

$\map s n = \begin{cases}

1 & : k > 0 \\ 2 & : k < 0 \\ 0 & : \text{otherwise} \end{cases}$

By:

• Set of Strictly Positive Integers is Primitive Recursive
• Set of Strictly Negative Integers is Primitive Recursive

we have that:

$k > 0 \iff n \in P$

$k < 0 \iff n \in N$

are primitive recursive relations.

Thus, by:

• Constant Function is Primitive Recursive
• Definition by Cases is Primitive Recursive/Corollary

the function $s$ defined above is primitive recursive.

First, suppose $k > 0$.

Then, we have:

$\map {\sgn_\Z} k = 1$

As $1 > 0$, by definition, $m$ codes $1$ if and only if:

$m = 2 \paren 1 - 1 = 1$

But $\map s n = 1$ in this case.

Next, suppose $k < 0$.

Then, we have:

$\map {\sgn_\Z} k = -1$

As $-1 \le 0$, by definition, $m$ codes $-1$ if and only if:

$m = -2 \paren {-1} = 2$

But $\map s n = 2$ in this case.

Lastly, suppose $k = 0$.

Then, we have:

$\map {\sgn_\Z} k = 0$

As $0 \le 0$, by definition, $m$ codes $0$ if and only if:

$m = -2 \paren 0 = 0$

But $\map s n = 0$ in this case.

In every case, $s$ satisfies the requirements.

$\blacksquare$