Finite Semigroup Equal Elements for Different Powers

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

$\forall x \in S: \exists m, n \in \N: m \ne n: x^m = x^n$


Proof

List the positive powers $x, x^2, x^3, \ldots$ of any element $x$ of a finite semigroup $\left({S, \circ}\right)$.

Since all are elements of $S$, and the semigroup has a finite number of elements, it follows from the Pigeonhole Principle this list must contain repetitions.

So there must be at least one instance where $x^m = x^n$ for some $m, n \in \N$.

$\blacksquare$