Power of Idempotent Element
Theorem
Let $\struct {S, \circ}$ be an algebraic structure.
Let $s \in S$ be an idempotent element with respect to $\circ$.
Then:
- $\forall n \in \Z_{> 0}: s^n = s$
where $s^n$ is defined as:
- $s^n = \begin{cases} s & : n = 1 \\
s^{n - 1} \circ s & : n > 1 \end{cases}$
Proof
The proof proceeds by induction.
For all $n \in \Z_{> 0}$, let $\map P n$ be the proposition:
- $s^n = s$
$\map P 1$ is the case:
- $s^1 = s$
which holds by definition.
Thus $\map P 1$ is seen to hold.
Basis for the Induction
$\map P 2$ is the case:
\(\ds s^2\) | \(=\) | \(\ds s^1 \circ s\) | Definition of $s^n$ | |||||||||||
\(\ds \) | \(=\) | \(\ds s \circ s\) | Definition of $s^1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds s\) | Definition of Idempotent Element |
Thus $\map P 2$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- $s^k = s$
from which it is to be shown that:
- $s^{k + 1} = s$
Induction Step
This is the induction step:
\(\ds s^{k + 1}\) | \(=\) | \(\ds s^k \circ s\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds s \circ s\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds s\) | Basis for the Induction |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \Z_{> 0}: s^n = s$