Powers of Commuting Elements of Semigroup Commute

From ProofWiki
Jump to: navigation, search


Let $\struct {S, \circ}$ be a semigroup.

For $a \in S$, let $\circ^n a = a^n$ denote the $n$th power of $a$.

Let $a, b \in S$ such that $a$ commutes with $b$:

$a \circ b = b \circ a$


$\forall m, n \in \N_{>0}: \paren {\circ^m a} \circ \paren {\circ^n b} = \paren {\circ^n b} \circ \paren {\circ^m a}$

That is:

$\forall m, n \in \N_{>0}: a^m \circ b^n = b^n \circ a^m$


The proof proceeds by the Principle of Mathematical Induction:

Let $\map P n$ be the proposition:

$\paren {\circ^n a} \circ b = b \circ \paren {\circ^n a}$

Basis of the Induction

\(\displaystyle a \circ b\) \(=\) \(\displaystyle b \circ a\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {\circ^1 a} \circ b\) \(=\) \(\displaystyle b \circ \paren {\circ^1 a}\) $\quad$ Definition of $\circ^1$ $\quad$

demonstrating that $\map P 1$ holds.

This is the basis for the induction.

Induction Hypothesis

Suppose that $\map P k$ holds:

$\paren {\circ^k a} \circ b = b \circ \paren {\circ^k a}$

This is the induction hypothesis.

It remains to be shown that:

$\map P k \implies \map P {k + 1}$

That is, that:

$\paren {\circ^{k + 1} a} \circ b = b \circ \paren {\circ^{k + 1} a}$

Induction Step

This is the induction step:


\(\displaystyle \paren {\circ^{k + 1} a} \circ b\) \(=\) \(\displaystyle \paren {\paren {\circ^k a} \circ a} \circ b\) $\quad$ Definition of $\circ^n a$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\circ^k a} \circ \paren {a \circ b}\) $\quad$ $\circ$ is associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\circ^k a} \circ \paren {b \circ a}\) $\quad$ $b$ commutes with $a$ under $\circ$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\paren {\circ^k a} \circ b} \circ a\) $\quad$ $\circ$ is associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \paren {b \circ \paren {\circ^k a} } \circ a\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle b \circ \paren {\paren {\circ^k a} \circ a}\) $\quad$ $\circ$ is associative $\quad$
\(\displaystyle \) \(=\) \(\displaystyle b \circ \paren {\circ^{k + 1} a}\) $\quad$ Definition of $\circ^n a$ $\quad$

So $\map P {k + 1}$ is true.


$\forall m \in \N_{>0}: \paren {\circ^m a} \circ b = b \circ \paren {\circ^m a}$


By repeating the argument above, replacing $a$ with $b$ and $b$ with $\circ^m a$, we have:

\(\displaystyle b \circ \paren {\circ^m a}\) \(=\) \(\displaystyle \paren {\circ^m a} \circ b\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {\circ^n b} \circ \paren {\circ^m a}\) \(=\) \(\displaystyle \paren {\circ^m a} \circ \paren {\circ^n b}\) $\quad$ $\quad$

Hence the result:

$\forall m, n \in \N_{>0}: \paren {\circ^m a} \circ \paren {\circ^n b} = \paren {\circ^n b} \circ \paren {\circ^m a}$

That is:

$\forall m, n \in \N_{>0}: a^m \circ b^n = b^n \circ a^m$