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:
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$