Let $G$ be a non-empty finite set with an associative binary operation so that cancellation law holds, i.e. $ab=ac$ or $ba=ca$ implies $b=c$, for any choices of $a,b,c$ in $G$. Assume that there is an identity element $e$ in $G$. Show that $G$ is a group.
Proof: To show $G$ is a group, conditions must hold. Suppose that $ab=ac$, then $b=eb=(a^{-1}a)b
=a^{-1}(ab)=a^{-1}(ac)
=(a^{-1}a)c=ec=c$. So left cancellation holds in $G$.
2) Suppose $ba=ca$, then $b=be=b(aa^{-1})
=(ba)a^{-1}=(ca)a^{-1}
=c(aa^{-1})=ce=c$. So right cancellation holds in $G$.
3) If $a$ exists in $G$ then $aa^{-1}=a^{-1}a=e$, where $a$ is an inverse of $a^{-1}$. Since inverses are unique, $(a^{-1})^{-1}=a$.
4) Let $x$ be the inverse of $ab$. Then $(ab)x=e$. By associativity we have $a(bx)=aa^{-1}$. Through left cancellation we have
$bx=a^{-1}bx=ea^{-1}=b(b^{-1}a^{-1})$ and $x=b^{-1}a^{-1}$.
Thus $(ab)^{-1}=b^{-1}a^{-1}$. So all conditions hold, $G$ is a group.
Is this proof correct? I know to show $G$ is a group these conditions have to be met. This is all I have to show right?
Best Answer
Another proof makes use of the pigeonhole principle. Fix $a \in G$, and consider the map $$ f : G \to G, \qquad x \mapsto a x. $$ Since $G$ is cancellative, the map is injective, hence surjective because $G$ is finite, so that there is $b \in G$ such that $e = f(b) = a b$.
Similarly, there is $c \in G$ such that $c a = e$.
Thus $$c = c e = c (a b) = (c a) b = e b = b,$$ and $b = c$ is the required inverse of $a$.
You need not assume that there is an identity, but can prove that one exists.
First show, with the arguments above, that any element $z$ of $G$ can be written in the form $z = x a$, for some $x \in G$. Then show that there is $s \in G$ such that $a s = a$. Now $$z s = x a s = x a = z, \quad\text{for all $z \in G$,}$$ so $s$ is a right identity. Similarly there is a left identity $t$ such that $$t z = z,\quad \text{for all $z \in G$,}$$ and finally $$t = t s = s$$ is the identity.