# A finite, cancellative semigroup is a group [duplicate]

Let $G$ be a finite, nonempty set with an operation $*$ such that

1. $G$ is closed under $*$ and $*$ is associative
2. Given $a,b,c \in G$ with $a*b=a*c$, then $b=c$.
3. Given $a,b,c \in G$ with $b*a=c*a$, then $b=c$.

I want to prove that $G$ is a group, but I don't know how to show that there exists an identity $e\in G$ such that $e*x=x$ and $x*e=x$ $\forall x \in G$. I also don't know how to show that $\forall$ x $\in G$ there exists a $y \in G$ such that $y*x=e$ and $x*y=e$. How do I do this?

## marked as duplicate by BCLC, user99914, Sil, José Carlos Santos, Adrian KeisterAug 17 '18 at 0:10

• I suspect that (3) should be: Given $a,b,c\in G$ with $b*a=c*a$, then $b=c$. – Brian M. Scott Sep 26 '12 at 20:00
• If we take your 3 literally, then $G$ has exactly one element and hence is - with the only possible operation - isomorphic to the trivial group. If we simply drop condition 3, then $G=\mathbb N$ and $*=+$ is a non-group model of your axioms. – Hagen von Eitzen Sep 26 '12 at 20:01
• Sorry I was in a rush, I fixed it now. – user39794 Sep 26 '12 at 20:03
• Note that finiteness is critical, otherwise take the positive integers under addition. – Will Jagy Sep 26 '12 at 20:09
• This is about a different question that I think you asked, about a group of $5$ elements. It can be done with no machinery, though it is unreasonably special. Suppose $xy\ne yx$. By properties of inverse, neither is $e$. Let $z$ be any group element other than these three. Look at $e$, $xy$, $yx$, $z$, $(xy)z$, $(yx)z$. Easily they must be all distinct. This contradicts order equal $5$. – André Nicolas Oct 3 '12 at 18:27

We write $xy$ for $x*y$.

Let $a$ be an element of $G$, and consider the function $f:G \to G$, $f(g)=ag$. This is injective by (2), and so (since $G$ is finite) it must also be surjective. Thus there exists an element $e$ of $G$ such that $f(e)=a$, i.e. $a=ae$.

We want to show that $e$ is in fact a two-sided identity for $G$. So let $b$ be an arbitrary element of $G$, and consider $ab=(ae)b=a(eb)$. Thus by (2), $b=eb$ for all $b$, i.e. $e$ is a left identity. To show $e$ is also a right identity, consider $bb=b(eb)=(be)b$, and apply (3) to conclude that $b=be$.

Now we need to show the existence of inverses. As above, for every $a$ in $G$ the function $g \mapsto ag$ is surjective, so there is an element, $a_R$ say, such that $aa_R=e$. Similarly, there is an element $a_L$ such that $a_La=e$. Since $a_L=a_Le=a_L(aa_R)=(a_La)a_R=ea_R=a_R$, we have that $a_L=a_R$ is a two-sided inverse for $a$.

• @Chris_Eagle how do you know it must be surjective? – user39794 Sep 26 '12 at 20:27
• A map of a finite set to itself is is either bijective or it is neither in- nor surjective. – Hagen von Eitzen Sep 26 '12 at 20:30
• By the way, it is sufficient to show that just a left inverse and a left identity exists. – peoplepower Sep 26 '12 at 21:20
• @peoplepower: That result is rather trickier to prove than this one, though, so it seemed silly to rely on it. – Chris Eagle Sep 27 '12 at 6:40
• @ChrisEagle: True. The second inverse trick is hard to see when you don't know it. – peoplepower Sep 27 '12 at 12:00

Your three axioms do not describe a group but rather a semigroup with cancellation law. An example of such a beast is the set $\mathbb N$ with addition. It is not a group.

However, you additionally require finiteness. To show that $(G,*)$ is now a group, consider the following: Select $a\in G$ and define $a^n$ recursively: $a^1=a$, $a^{n+1}=a^n*a$. Finiteness implies that $a^n=a^m$ for some $n\ne m$ . Wlog. $n>m$, say $n=m+k$ with $k>0$. Then $a^{k+1}*a^{m}=a^{n+1}=a^n*a=a^m*a=a^{m+1}=a*a^{m}$, hence $a^{k+1}=a$. Let $e=a^{k}$. Then $e*a=a*e=a^{k+1}=a$. Let $x\in G$. Since the $x* y$, $y\in G$ are pairwise distinct, there is one $y$ with $x* y = a$. It follows that $$(e*x)*y = e*(x*y) = e*a = a = x*y,$$ hence $e*x=x$. Since the $z*x$, $z\in G$ are pairwise distinct, there is one $z$ with $z*x = a$. It follows that $$z*(x*e)=(z*x)*e=a*e=a=z*x,$$ hence $x*e=x$. Thus $e$ is left and right neutral.

Then, again by the $x* y$ being distinct, we find $y\in G$ such that $x*y=e$. But then also $(y*x)*y=y*(x*y)=y*e=y=e*y$ implies $y*x=e$, i.e. the $y$ found is left and right inverse of $x$.

• You missed the finiteness assumption. – Chris Eagle Sep 26 '12 at 20:09
• Yes I did - and thenlost time ;) – Hagen von Eitzen Sep 26 '12 at 20:32
• . How does "Since the $x* y$, $y\in G$ are pairwise distinct, there is one $y$ with $x* y = a$" follow? how can u say they are pair-wise disjoint – Shobhit Aug 27 '17 at 20:29
• Brilliant! I just knew there had to be a way to do this without the concepts of 'injective' or 'surjective'. – BCLC Aug 16 '18 at 11:00

The finiteness of $G$ will let us use the pigeonhole principle to say for some $a\in G$ that there is some $e_a\in G$ such that $a*e_a=a$. Using the associativity of $*$, then $(b*a)*e_a=b*(a*e_a)=b*a$, and by pigeonhole principle, every $c\in G$ has form $b*a$ for some $b\in G$ so that $e_a$ is a right identity element.

Now, take any $b,c\in G$ and note that $b*c=(b*e_a)*c=b*(e_a*c)$, so by cancellativity, $c=e_a*c$ for any $c\in G$. Thus, $e_a$ is a left identity element, as well.

Cancellativity tells us that $e_a$ is (in fact) the unique identity element of $G$. A final (similar) application of pigeonhole principle and cancellativity tells us that for any $b\in G$, there is a unique $c\in G$ such that $c*b=e_a=b*c$.

Beginning: fix an element $a.$ Taking all $x,$ the set of right products $ax$ will be the entire set (they are distinct and the set is finite, we count), so there is some $x,$ call it $x_a$ such that $a x_a = a.$ Next, there is some $y_a$ such that $y_a a = a.$ There is more work after this.

Given $g \in G$, by finiteness of $G$ and condition $2$, left multiplication $l_g : G \to G$ by $g$ is a permutation of $G$. Then, by associativity of $*$, the map $g \mapsto l_g$ is a magma homomorphism. By condition $3$, this map is an injection. Thus, the magma $G$ can be embedded into $S_{|G|}$. Since any nonempty subset of any finite group, which is closed under multiplication is a subgroup, $G$ is a subgroup of $S_{|G|}$.

This proof also shows that we can weaken the right cancellation hypothesis with: If $g$, $h \in G$ satisfy $gx = hx$ for all $x \in G$, then $g = h$.