Homomorphism of Powers/Naturally Ordered Semigroup

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({T_1, \odot}\right)$ and $\left({T_2, \oplus}\right)$ be semigroups.

Let $\phi: \left({T_1, \odot}\right) \to \left({T_2, \oplus}\right)$ be a (semigroup) homomorphism.


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

For a given $a \in T_1$, let $\odot^n \left({a}\right)$ be the $n$th power of $a$ in $T_1$.

For a given $a \in T_2$, let $\oplus^n \left({a}\right)$ be the $n$th power of $a$ in $T_2$.

Then:

$\forall a \in T_1: \forall n \in \left({S^*, \circ, \preceq}\right): \phi \left({\odot^n \left({a}\right)}\right) = \oplus^n \left({\phi \left({a}\right)}\right)$

where $S^* = S \setminus \left\{ {0}\right\}$.


Proof

The proof proceeds by the Principle of Mathematical Induction for a Naturally Ordered Semigroup.


Let $A := \left\{ {n \in S^*: \forall a \in T_1: \phi \left({\odot^n \left({a}\right)}\right) = \oplus^n \left({\phi \left({a}\right)}\right)}\right\}$

That is, $A$ is defined as the set of all $n$ such that:

$\forall a \in T_1 \phi \left({\odot^n \left({a}\right)}\right) = \oplus^n \left({\phi \left({a}\right)}\right)$


Basis for the Induction

We have that:

\(\displaystyle \phi \left({\odot^1 \left({a}\right)}\right)\) \(=\) \(\displaystyle \phi \left({a}\right)\) Definition of Power of Element
\(\displaystyle \) \(=\) \(\displaystyle \oplus^1 \left({\phi \left({a}\right)}\right)\) Definition of Power of Element

So $1 \in A$.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $k \in A$ where $k \ge 1$, then it logically follows that $k \circ 1 \in A$.


So this is our induction hypothesis:

$\forall a \in T_1: \phi \left({\odot^k \left({a}\right)}\right) = \oplus^k \left({\phi \left({a}\right)}\right)$


Then we need to show:

$\forall a \in T_1: \phi \left({\odot^{k \circ 1} \left({a}\right)}\right) = \oplus^{k \circ 1} \left({\phi \left({a}\right)}\right)$


Induction Step

This is our induction step:

\(\displaystyle \phi \left({\odot^{k \circ 1} \left({a}\right)}\right)\) \(=\) \(\displaystyle \phi \left({\left({\odot^k \left({a}\right)}\right) \odot a}\right)\) Definition of Power of Element
\(\displaystyle \) \(=\) \(\displaystyle \left({\phi \left({\odot^k \left({a}\right)}\right)}\right) \oplus \left({\phi \left({a}\right)}\right)\) Definition of Homomorphism
\(\displaystyle \) \(=\) \(\displaystyle \left({\oplus^k \left({\phi \left({a}\right)}\right)}\right) \oplus \left({\phi \left({a}\right)}\right)\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \oplus^{k \circ 1} \left({\phi \left({a}\right)}\right)\) Definition of Power of Element

So $k \in A \implies k \circ 1 \in A$ and the result follows by the Principle of Mathematical Induction:

$\forall n \in \left({S^*, \circ, \preceq}\right): \phi \left({\odot^n \left({a}\right)}\right) = \oplus^n \left({\phi \left({a}\right)}\right)$

$\blacksquare$


Sources