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?

  • 2
    $\begingroup$ You already have an associative binary operation with an identity, and you are told that the cancellation law applies. You need to show that this implies that every element has an inverse - you will need to use the fact you are given that the set is finite, which you have not used in your proof. $\endgroup$ – Mark Bennet Sep 30 '13 at 16:42
  • 2
    $\begingroup$ Note - the non-negative integers under addition are an infinite set which has an associative binary operation, identity (zero) and cancellation, but only the identity has an inverse. $\endgroup$ – Mark Bennet Sep 30 '13 at 16:45

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.

  • $\begingroup$ Thank you. Seeing it this way was very helpful as well $\endgroup$ – Ruth Gutierrez Sep 30 '13 at 17:39
  • $\begingroup$ @RuthGutierrez, you're welcome. $\endgroup$ – Andreas Caranti Sep 30 '13 at 17:41
  • $\begingroup$ @AndreasCaranti I don't quite understand the proof for identity. I thought it should be z = ax? why is it z = xa? $\endgroup$ – user10024395 Sep 5 '14 at 10:19

No, you seem to be assuming things like the inverse would exist in your proof, which is the only thing you really need to prove (the other 3 conditions in the definition of a group are given to you).

So choose $a\in G$, and consider the set $$ \{a, a^2, a^3, \ldots \} \subset G $$ Since $G$ is finite, this set is finite, and so there exist $a^i, a^j$ such that $i>j$ and $$ a^i = a^j $$ Now consider $f = a^{i-j}$, then $$ fa^j = a^i = a^j = ea^j \Rightarrow f = e $$ Hence, if $b = a^{i-j-1}$, then $$ ab = e = ba $$ and hence $b = a^{-1} \in G$

  • 1
    $\begingroup$ So just showing that the identity and inverse exist in G then this shows that G is a group? $\endgroup$ – Ruth Gutierrez Sep 30 '13 at 16:49
  • 1
    $\begingroup$ You are already given an identity, and you are already given closure (because it is a binary operation), and associativity. The only thing left is the inverses. $\endgroup$ – Prahlad Vaidyanathan Sep 30 '13 at 16:50
  • 1
    $\begingroup$ Oh ok which showed that a^-1 exists in G. $\endgroup$ – Ruth Gutierrez Sep 30 '13 at 17:06
  • 1
    $\begingroup$ thank you this was very helpful $\endgroup$ – Ruth Gutierrez Sep 30 '13 at 17:38
  • 1
    $\begingroup$ I noticed you find an identity $e_x$ for a given $x\in G$. I would like to ask why is this identity a "general" identity, that is, why is $e_xg=ge_x=g$ true for all $g\in G$? $\endgroup$ – rgm Apr 18 '17 at 11:49

You know that cancellation holds in $G$, it's a hypothesis, so you have not to prove it. And, most important, you can't use inverses of elements without first proving they exist, which is exactly what you have to do.

Consider an element $a\in G$ and the map $f_a\colon G\to G$ defined by $$ f(x)=ax $$ This map is injective. Why?

This map is also surjective, because of an important hypothesis you have. Which one?

Now, what can you say about the element $x$ such that $f_{a}(x)=e$? It is…

Next, consider the map $g_{a}\colon G\to G$ defined by $g_{a}(x)=xa$. Repeat the reasoning to conclude.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.