Cancellable Finite Semigroup is Group
Theorem
Let $\left({S, \circ}\right)$ be a finite semigroup in which all elements are cancellable.
Then $\left({S, \circ}\right)$ is a group.
Proof
As $S$ is a semigroup, it is already closed and associative.
We just need to show that it has an identity and that every element has an inverse.
First we show that $S$ has an identity.
Choose $a \in S$. Let the mapping $\lambda_a$ be the left regular representation of $\left({S, \circ}\right)$ with respect to $a$.
Because all elements are cancellable, in particular, so is $a$, so $\lambda_a$ is injective.
As $S$ is finite, $\lambda_a$ is also surjective.
Hence $a \circ e = a$ for some $e \in S$.
Let $x \in S$.
Then because of cancellability:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle a \circ e \circ x\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle a \circ x\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle e \circ x\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle x\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ e \circ x\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle x \circ x\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle x \circ e\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle x\) | \(\displaystyle \) | \(\displaystyle \) |
Thus $e$ is the identity.
The existence of inverses comes from the surjectivity of $\lambda_a$.
As $\lambda_a$ is surjective, $\exists y \in S: \lambda_a \left({y}\right) = e$.
That is, $a \circ y = e$.
So we see that $y$ acts as a right inverse for $a$.
This is the case for any $a \in S$: all of them have some right inverse.
So, from Right Inverse for All is Left Inverse, each of these elements is also a left inverse, and therefore an inverse.
Thus $S$ is closed, associative, has an identity and every element has an inverse.
So, by definition, $\left({S, \circ}\right)$ is a group.
$\blacksquare$
Comment
in the process of being refactored, or:
has been identified as a candidate for refactoring. In particular:
Extract this into an "also see"
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Note that the same does not apply to infinite semigroups.
Consider the semigroup $\left({\N, +}\right)$.
- It is closed: the sum of two natural numbers is another natural number.
- Natural number addition is associative, so it is definitely a semigroup
- $b + a = c + a \implies b = c$, so all elements of $\left({\N, +}\right)$ are cancellable.
But $\left({\N, +}\right)$ is not a group, as (apart from $0$) no element has an inverse.
Sources
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 26 \delta$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $6.3$
