Recursive Mapping with Identity

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left({S, \circ, \preceq}\right)$ be a naturally ordered semigroup.

Let $\left({T, *}\right)$ be an algebraic structure which has an identity $e$, and let $a \in T$.

Then there is one and only one mapping $g_a: \left({S, \circ, \preceq}\right) \to \left({T, *}\right)$ such that:

$ \forall n \in S: g_a \left({n}\right) = \begin{cases} e & : n = 0 \\ g_a \left({r * a}\right) & : n = r \circ 1 \end{cases} $

where $f_a$ is the restriction of $g_a$ to $S^*$.

Let $\left({T, *}\right)$ have an identity $e$.

Let $s: T \to T$ be the mapping defined as:

$\forall x \in T: s \left({x}\right) = x * a$

The result follows by a direct application of the Principle of Recursive Definition to $s$, $0 \in S$ and $e \in T$:

$ g_a \left({n}\right) = \begin{cases} e & : n = 0 \\ g_a \left({x * a}\right) & : n = x \circ 1 \end{cases} $

Thus we have $g_a \left({1}\right) = g_a \left({0}\right) * a = e * a = a$.

Because $f_a$ as defined in Recursive Mapping is unique, the restriction of $g_a$ to $S^*$ is $f_a$.

$\blacksquare$