Commutativity of Powers in Semigroup

From ProofWiki

Jump to: navigation, search

Theorem

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

Let $a, b \in S$ both be cancellable elements of $S$.

Then:

$\forall m, n \in \N^*: a^m \circ b^n = b^n \circ a^m \iff a \circ b = b \circ a$

Let $a, b \in S: a \circ b = b \circ a$.

Because $\left({S, \circ}\right)$ is a semigroup, $\circ$ is associative on $S$.

Let $T$ be the set of all $n \in \N^*$ such that:

$a^n \circ b = b \circ a^n$

We have:

$a \circ b = b \circ a \implies a^1 \circ b = b \circ a^1$.

So $1 \in T$.

Now suppose $n \in T$. Then we have:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle a^{n + 1} \circ b$	$=$	$\displaystyle \left({a^n \circ a}\right) \circ b$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle a^n \circ \left({a \circ b}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	(as $\circ$ is associative)
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle a^n \circ \left({b \circ a}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	(as $b$ commutes with $a$ under $\circ$)
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left({a^n \circ b}\right) \circ a$	$\displaystyle $	$\displaystyle $	$\displaystyle $	(as $\odot$ is associative)
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left({b \circ a^n}\right) \circ a$	$\displaystyle $	$\displaystyle $	$\displaystyle $	(as $n \in T$)
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle b \circ \left({a^n \circ a}\right)$	$\displaystyle $	$\displaystyle $	$\displaystyle $	(as $\ast$ is associative)
$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle $	$=$	$\displaystyle b \circ a^{n + 1}$	$\displaystyle $	$\displaystyle $	$\displaystyle $

So $n + 1 \in T$.

Thus by the Principle of Finite Induction, $T = \N^*$. Thus:

$\forall m \in \N^*: a^m \circ b = b \circ a^m$

Thus, from the preceding: $\forall m, n \in \N^*: a^m$ and $b^n$ also commute with each other.

For the above relationships and equalities to hold, it follows that $a$ and $b$ must commute.

The result follows.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a^{n + 1} \circ b\)	\(=\)	\(\displaystyle \left({a^n \circ a}\right) \circ b\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a^n \circ \left({a \circ b}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(as $\circ$ is associative)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a^n \circ \left({b \circ a}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(as $b$ commutes with $a$ under $\circ$)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({a^n \circ b}\right) \circ a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(as $\odot$ is associative)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({b \circ a^n}\right) \circ a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(as $n \in T$)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \circ \left({a^n \circ a}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(as $\ast$ is associative)
\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b \circ a^{n + 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)