Absolute Value of Integer is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

For every $n \in \N$, let $n$ code the integer $k_n$.

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

$\map a n = \size {k_n}$

Then, $a$ is primitive recursive.


Proof

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

$\map a n = \map {\operatorname{quot}} {n + 1, 2}$

By:

it follows that $a$ is primitive recursive.


By definition of code number for integer, either:

$n = 2 k_n - 1$, with $k_n > 0$

or:

$n = - 2 k_n$, with $k_n \le 0$

In the first case, with $k_n > 0$, we have:

$k_n = \size {k_n}$

Then:

\(\ds \map a n\) \(=\) \(\ds \map a {2 k_n - 1}\)
\(\ds \) \(=\) \(\ds \map {\operatorname{quot} } {\paren {2 \size {k_n} - 1} + 1, 2}\)
\(\ds \) \(=\) \(\ds \map {\operatorname{quot} } {2 \size {k_n}, 2}\)
\(\ds \) \(=\) \(\ds \size {k_n}\) Definition of Quotient


In the second case, with $k_n \le 0$, we have:

$k_n = - \size {k_n}$

Then:

\(\ds \map a n\) \(=\) \(\ds \map a {- 2 k_n}\)
\(\ds \) \(=\) \(\ds \map {\operatorname{quot} } {\paren {- 2 \paren {- \size {k_n} } } + 1, 2}\)
\(\ds \) \(=\) \(\ds \map {\operatorname{quot} } {2 \size {k_n} + 1, 2}\)
\(\ds \) \(=\) \(\ds \size {k_n}\) Definition of Quotient

$\blacksquare$

Retrieved from "https://proofwiki.org/w/index.php?title=Absolute_Value_of_Integer_is_Primitive_Recursive&oldid=676640"