After proving that unique solvability of equations turns a semigroup into a group, we now study a very useful finite version of that idea. In a finite semigroup, cancellation laws are strong enough to force unique solvability of equations. The reason is that an injective map from a finite set to itself must also be onto. Thus cancellation gives one-to-one left and right multiplication maps, finiteness gives onto maps, and the equation criterion then gives a group. In this lesson, students will prove that every finite cancellative semigroup is a group. :::definition[Cancellative Semigroup] Let $(S,\circ)$ be a semigroup. Then $(S,\circ)$ is called $cancellative$ if both cancellation laws hold in $S$, that is, for all $a,b,c\in S$: (i) $a\circ b=a\circ c \implies b=c$. (ii) $b\circ a=c\circ a \implies b=c$. ::: Cancellation alone does not always produce a group in infinite semigroups. For example, $(\mathbb{N},+)$ is cancellative and associative, but it is not a group when $\mathbb{N}=\{1,2,3,\ldots\}$. The missing ingredient is finiteness. In a finite set, one-to-one maps are automatically onto. This finite-set fact is the bridge from cancellation to unique solvability of equations. :::theorem Let $(S,\circ)$ be a finite semigroup. If both cancellation laws hold in $S$, then $(S,\circ)$ is a group. ::: :::proof Given that $(S,\circ)$ is a finite semigroup and both cancellation laws hold in $S$. To prove that $(S,\circ)$ is a group. Let $a\in S$. Define $L_a:S\to S$ by $$\begin{equation*} L_a(x)=a\circ x \quad \forall\, x\in S. \end{equation*}$$ If $L_a(x_1)=L_a(x_2)$, then $$\begin{align*} L_a(x_1)=L_a(x_2) &\implies a\circ x_1=a\circ x_2\\ &\implies x_1=x_2 \quad [\because\, \text{left cancellation law}]. \end{align*}$$ Therefore $L_a$ is one-one. Since $S$ is finite, every one-one map from $S$ to $S$ is onto. Therefore $L_a$ is onto. Thus for each $b\in S$, there exists $x\in S$ such that $$\begin{equation*} a\circ x=b. \end{equation*}$$ Also, since $L_a$ is one-one, this solution is unique. Therefore the equation $a\circ x=b$ has a unique solution in $S$ for all $a,b\in S$. Now define $R_a:S\to S$ by $$\begin{equation*} R_a(y)=y\circ a \quad \forall\, y\in S. \end{equation*}$$ If $R_a(y_1)=R_a(y_2)$, then $$\begin{align*} R_a(y_1)=R_a(y_2) &\implies y_1\circ a=y_2\circ a\\ &\implies y_1=y_2 \quad [\because\, \text{right cancellation law}]. \end{align*}$$ Therefore $R_a$ is one-one. Since $S$ is finite, $R_a$ is onto. Thus for each $b\in S$, there exists $y\in S$ such that $$\begin{equation*} y\circ a=b. \end{equation*}$$ Also, since $R_a$ is one-one, this solution is unique. Therefore the equation $y\circ a=b$ has a unique solution in $S$ for all $a,b\in S$. Hence, by the semigroup equation criterion, $(S,\circ)$ is a group. $\square$ ::: The proof is a good example of how algebra and finite set theory work together. Algebra gives cancellation, so the maps $L_a$ and $R_a$ are one-one. Finiteness changes one-one into onto. Onto means that the equations $a\circ x=b$ and $y\circ a=b$ have solutions for every $b$. One-one means those solutions are unique. The previous theorem then supplies the identity element and inverses. :::example Let $S=\{0,1,2,3,4\}$ with addition modulo $5$. Then $(S,+)$ is a finite semigroup. It is cancellative because $$\begin{equation*} a+b\equiv a+c \pmod{5} \end{equation*}$$ implies $$\begin{equation*} b\equiv c \pmod{5}. \end{equation*}$$ Thus the cancellation laws hold. Since $S$ is finite, the theorem implies that $(S,+)$ is a group. ::: :::example The semigroup $(\mathbb{N},+)$ is cancellative but not a group when $\mathbb{N}=\{1,2,3,\ldots\}$. Indeed, $$\begin{equation*} a+b=a+c \implies b=c \end{equation*}$$ and $$\begin{equation*} b+a=c+a \implies b=c. \end{equation*}$$ However, $(\mathbb{N},+)$ has no identity element inside $\mathbb{N}$. This example shows why finiteness is necessary in the theorem. ::: :::solved-problem Let $(S,\circ)$ be a finite semigroup. Suppose that for every $a\in S$, the map $L_a:S\to S$ defined by $L_a(x)=a\circ x$ is one-one, and the map $R_a:S\to S$ defined by $R_a(x)=x\circ a$ is one-one. Prove that $(S,\circ)$ is a group. ::: :::solution Let $(S,\circ)$ be a finite semigroup. Given that for every $a\in S$, both maps $L_a$ and $R_a$ are one-one. To prove that $(S,\circ)$ is a group. Since $S$ is finite, every one-one map from $S$ to $S$ is onto. Thus $L_a$ is onto for every $a\in S$. Therefore for every $a,b\in S$, there exists $x\in S$ such that $$\begin{equation*} L_a(x)=b. \end{equation*}$$ Hence, $$\begin{equation*} a\circ x=b. \end{equation*}$$ Since $L_a$ is one-one, this solution is unique. Similarly, $R_a$ is onto for every $a\in S$. Therefore for every $a,b\in S$, there exists $y\in S$ such that $$\begin{equation*} R_a(y)=b. \end{equation*}$$ Hence, $$\begin{equation*} y\circ a=b. \end{equation*}$$ Since $R_a$ is one-one, this solution is unique. Therefore the equations $a\circ x=b$ and $y\circ a=b$ have unique solutions in $S$ for all $a,b\in S$. Hence, by the semigroup equation criterion, $(S,\circ)$ is a group. $\square$ ::: :::remark The finite hypothesis cannot be removed. The map $L_a:\mathbb{N}\to\mathbb{N}$ defined by $L_a(x)=a+x$ is one-one, but it is not onto when $a\geq1$ because small positive integers are not reached. Thus injectivity alone does not give solutions to all equations in an infinite semigroup. This is exactly why $(\mathbb{N},+)$ remains cancellative but not a group. ::: Cancellation says that left and right multiplication maps do not collapse two different inputs into one output. In a finite set, that injective behavior forces every output to be reached. We observe this by comparing addition modulo $n$ and multiplication modulo $n$. Addition modulo $n$ gives permutation maps, while multiplication modulo $n$ may collapse values and break cancellation. :::scientific-preview[Left Multiplication Image Explorer] @libraries: plotly ::: Use the calculator to test left and right cancellation for addition or multiplication modulo $n$ on the set $\{0,1,\ldots,n-1\}$. For addition modulo $n$, cancellation always holds. For multiplication modulo $n$, cancellation may fail. This experiment illustrates why finite cancellative semigroups become groups, while finite semigroups without cancellation may not. :::calculator[Cancellation Table Test] ::: :::exercise [1] Define a cancellative semigroup. [2] Prove that a finite cancellative semigroup is a group. [3] Explain why the map $L_a(x)=a\circ x$ is one-one under left cancellation. [4] Give an infinite cancellative semigroup that is not a group. [5] Determine whether addition modulo $n$ on $\{0,1,\ldots,n-1\}$ gives a finite cancellative semigroup. ::: :::answer [1] A semigroup is cancellative if both left and right cancellation laws hold. [2] Left and right multiplication maps are one-one. Since the set is finite, they are onto. Hence both equations have unique solutions, so the semigroup is a group. [3] If $L_a(x_1)=L_a(x_2)$, then $a\circ x_1=a\circ x_2$, and left cancellation gives $x_1=x_2$. [4] $(\mathbb{N},+)$ is cancellative but not a group when $\mathbb{N}=\{1,2,3,\ldots\}$. [5] Yes. Addition modulo $n$ is associative and cancellative on the finite set. ::: :::faq Q: Why does finiteness matter in this theorem? A: In a finite set, every one-one self-map is onto. Q: Does cancellation alone make a semigroup a group? A: Not in general. The semigroup must be finite for this theorem. Q: What maps are used in the proof? A: The left multiplication map $L_a(x)=a\circ x$ and the right multiplication map $R_a(x)=x\circ a$. Q: Why does onto imply solvability of equations? A: If $L_a$ is onto, then for every $b$ there exists $x$ such that $L_a(x)=b$, meaning $a\circ x=b$. ::: :::call-to-action[Idempotents in Finite Semigroups] subtitle: Continue to idempotents in finite semigroups and see why every finite semigroup contains an idempotent element. button: Next Lesson | /abstract-algebra/introduction-to-groups/semigroup-conditions-for-groups/idempotents-in-finite-semigroups button-ghost: Previous Lesson | /abstract-algebra/introduction-to-groups/semigroup-conditions-for-groups/semigroup-equation-criterion-for-groups :::