# How to prove identity element in a set that is finite, associative, and left-right cancellable?

Let $G$ be a finite set and $*$ a binary operation on $G$ such that:

• The operation $*$ is associative.
• For all $x$, $y$, and $z$ in $G$, if $x*y=x*z$ then $y=z$ and if $y*x=z*x$ then $y=z$.

I must show that this set has an identity element $e$ in $G$ such that for all $x$ in $G$, $e*x=x$. I'm not sure how to start at all. I was thinking of showing that for some arbitrary element in $G$, there exists e such that $e*a=a$ and then proving it for the rest of the elements.

• Hint: Let $y\in G$ and consider the set $\{y,y^2,\cdots\}$. Since $G$ is finite, we must have $y^m=y^n$ for some $m <n$. Now try to prove using left cancellation that $y^{n-m}$ is the identity. – Uncountable Feb 3 '16 at 18:37
• I see where you're going here. However, does that mean I'm assuming that the operation is multiplication? How can I show that y^(n-m)*y^(m) = y^n? – mil10 Feb 3 '16 at 18:58
• $y^n$ is just short-hand notation for $y*\cdots *y$ (with $n$ $y$'s). – Uncountable Feb 3 '16 at 19:00
• Gotcha. That helped so much! Thank you. Once proving that the identity exists for element y, do I have to prove that any x in G can be written as y*a for some a in G, or does it suffice to say that since y was an arbitrary element, the property must be true for all other x in G? – mil10 Feb 3 '16 at 19:04
• When we show that $y^{n-m}$ has the property that $y^{n-m}x=x$ for all $x\in G$, then we have shown that the $e$ that was requested indeed exists (namely $e=y^{n-m}$ will work); there is no "dependence" on $y$ here anymore, since it "acts as an identity" for any element of $G$. The only thing we used is that $G$ is non-empty. – Uncountable Feb 3 '16 at 19:07

Let $G=\{x_1,x_2,\dotsc,x_n\}$ Pick a $a\in G$, then multiplication by $a$ induces a permutation $\sigma$ on the elements of $G$. Such a permutation has a finite order $k$ so $a^k*x_i=x_i$. In other words, $a^k$ acts like a multiplicative identity.