Cancellable Finite Semigroup is Group

From ProofWiki
Jump to: navigation, search

Theorem

Let $\struct {S, \circ}$ be a non-empty finite semigroup in which all elements are cancellable.

Then $\struct {S, \circ}$ is a group.


Proof

As $\struct {S, \circ}$ is a semigroup, it is already closed and associative.

It remains to be shown that it has an identity and that every element of $S$ has an inverse in $S$.


First we show that $\struct {S, \circ}$ has an identity.

Choose $a \in S$.

Let the mapping $\lambda_a: S \to S$ be the left regular representation of $\struct {S, \circ}$ with respect to $a$.


By hypothesis:

all elements of $S$ are cancellable
$S$ is finite.

By Regular Representation wrt Cancellable Element on Finite Semigroup is Bijection, $\lambda_a$ is a bijection.

Hence $a \circ e = a$ for some $e \in S$.


Let $x \in S$.

Then because of cancellability:

\(\displaystyle a \circ e \circ x\) \(=\) \(\displaystyle a \circ x\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle e \circ x\) \(=\) \(\displaystyle x\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x \circ e \circ x\) \(=\) \(\displaystyle x \circ x\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle x \circ e\) \(=\) \(\displaystyle x\)


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: \map {\lambda_a} y = 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, $\struct {S, \circ}$ is a group.

$\blacksquare$


Also see


Sources