Exercise 26d.

Let $S$ be a semigroup with a finite number of elements. Suppose that the two cancellation laws hold in $S$ ; that is, if either $ab = ac$ or $ba = ca$ , then $b = c$ . Show that $S$ is a group.

Proof (faulty, read below)

Note: This proof is wrong, but I'm leaving it for educational purposes. Feel free to find the mistake. Link to correct solution and more comments below in the Additional thoughts section.

Once again, we need to prove that the group axioms are true for $S$ .

Closure: $S$ is a semigroup, so by definition closure holds in $S$ .
Associativity: Same as closure.
Existence of the identity element: Let's assume $S \neq \varnothing$ , this means $\exists a \in S$ . Consider now the following set $A=\{a^n \colon a \in S, n \in \mathbb N\}$ We know the following two things: $\varnothing \neq A \subseteq S$ . That $A$ is not empty we know because $a^1 \in A$ . And we know $A$ is a subset of $S$ since we have, by induction and closure of the semigroup, $a^{n} \in S \ \forall n \in \mathbb N$ . Now, by Dirichlet's (aka pigeonhole) principle, since $A$ is finite, and $\mathbb N$ is infinite, there must exist $n, m \in \mathbb N \colon n < m$ for which we have $a^n = a^m \tag 1$ Expanding the semigroup products on both sides of this equality: $\begin{align} \underbrace {(a \dots a)}_{m-1 \ as}\underbrace{(a \dots a)}_{n-m+1 \ as} = \underbrace {(a \dots a)}_{m-1 \ as} a &\implies a^{n-m+1} = a \tag 2\\ & \iff a^{n-m}a = a \\ & \iff aa^{n-m} = a \end {align}$ Above we used the associativity of the semigroup, and the left cancellation law. So, we found an element $e=a^{n-m}$ that leaves $a$ invariant, i.e. we proved that every element has its own identity. To prove that this really is the identity element, it will suffice to prove that they are all the same element. More precisely, we want to show $a^ka^{n-m} = a^k \ \forall k \in \mathbb N$ , and we can do this by induction. For $k=1$ we know it's true. Now we assume it's true for $k$ . Then for $k+1$ we have $a^{k+1}a^{n-m}=a^kaa^{n-m}=a^ka^{n-m}=a^k$ , the last equality being true by the inductive hypothesis. Thus we've shown that all the elements have the one and the same identity element, hence $S$ has the identity element.
Existence of an inverse for all elements of $S$ : Continuing the reasoning from above, consider the following $e=a^{n-m}=aa^{n-m-1}=a^{n-m-1}a$ the above equalities being true by associativity. But this tells us that for an arbitrary $a \in S$ its inverse is $a^{n-m-1}$ . It just remains to consider what if $n-m = 1$ since then the inverse would be $a^0$ and we don't know whether this element is in $S$ . For this case, we would have $e=a^{n-m}=a^1=a$ , in particular $ae=a=e$ , thus in this case as well $a$ is invertible.

We proved everything that needed to be proved, the proof is complete.

$\square$

Additional thoughts

If you just want the correct and arguably better solution of this exercise, here you go:A finite, cancellative semigroup is a group. As in for the mentioned mistake, I believe that we showed that only the set $A\subseteq S$ has the identity element, but we didn't do so for the whole semigroup $S$ . Only after typing up this proof I realized this mistake, so I decided to leave it as an example of a faulty proof, for educational purposes. Here is also a link to the question about this proof I asked on MSE that helped me understand some previous insufficiencies of the proof (check the discussion in the comments).