Prove that a finite set with cancellation laws is a group

[Happiness]

If G is a finite set closed under an associative operation such that ax = ay forces x = y and ua = wa forces u = w, for every a, x, y, u, w $\in$ G, prove that G is a group.

What I attempted:
If we can prove that for every x $\in$ G, x$^{-1}$ is also $\in$ G, then by the closure of the operation, the identity element is also $\in$ G, and we are done.

To show that x$^{-1}$ is $\in$ G, we need to show that for any x, y $\in$ G,
ax$^{-1}$ = ay$^{-1}$ forces x$^{-1}$ = y$^{-1}$ and
x$^{-1}$a = y$^{-1}$a forces x$^{-1}$ = y$^{-1}$

 

[andrewkirk]

I think we'd have to start by trying to prove that $G$ contains an identity element, ie that $\exists e\in G$ such that $\forall a\in G,\ \ ae=ea=a$. Without that, the symbol string $x^{-1}$ has no meaning.

 

[andrewkirk]

I don't think that the claim for which a proof is requested is true. Consider the group $\mathbb{Z}$ of integers under the operation of addition. That obeys the above two forcing properties - as do all groups.

Now consider the subset $\mathbb{N}$ of positive integers. It is closed under addition and inherits the associativity and forcing properties from the group $\mathbb{Z}$. Yet it has no identity element and no inverses.

Perhaps there is something missing from the problem description?

Ah no. Hang on. I just noticed the set is finite (and $\mathbb{N}$ is not). I suspect the key will lie in that! We need to find a way to use the finiteness.

 

[andrewkirk]

OK I've worked it out. It's a beautiful proof - as many proofs in group theory are. The challenge is how to give just enough hints to get you going, without taking all the fun out of doing it yourself.

First let's establish a couple of concepts. For $a\in G$ we say $b\in G$ is:

• a 'left identity' of $a$ if $ba=a$
• a 'right identity' of $a$ if $ab=a$

We will first prove that every element has a unique left identity, so that we can unambiguously denote 'the' left identity of $a$ by $l(a)$. Then prove that all left identities are the same, ie $\forall a,b\in G: l(a)=l(b)$.

In the proof we repeatedly use the finiteness property, together with the forcing properties and associativity. Let $n$ be the number of elements in $G$.

Consider the coset $Ga$ for an arbitrary $a\in G$. It must have exactly $n$ distinct elements because of the forcing property (why?). Hence one of those elements, say $ba$, must be $a$ (note how we have to use the finiteness property here). So $b$ must be a left identity of $a$.
$a$ can't have two left identities (why?) so $b=l(a)$.

Next we want to prove that all left identities are the same.
Two steps can accomplish this.
First prove that $l(ab)=l(a)$.
Then use the fact that $aG=G$ (which you first have to prove: use finiteness and forcing) to get the result.

So now we know there is a unique left identity in $G$, which we'll call $L$.

A similar argument shows there's a unique right identity $R$.

Next prove that $L=R$.
So we have an identity element, which we'll call $I$.

The last bit, to prove the existence of inverses is easier. Do left inverses first. For element $a\in G$ again consider what we know about $Ga$ and whether it must contain $I$, and why (finiteness and forcing again). You soon conclude that every element has a unique left inverse.

Do the same for right inverses and we conclude that every element has unique left and right inverses.
To prove they are the same we just need to put $a$, it's left and right inverse together in a formula and use the associativity property.

Good luck.

 

[Happiness]

OK I've worked it out. It's a beautiful proof - as many proofs in group theory are. The challenge is how to give just enough hints to get you going, without taking all the fun out of doing it yourself.

First let's establish a couple of concepts. For $a\in G$ we say $b\in G$ is:

• a 'left identity' of $a$ if $ba=a$
• a 'right identity' of $a$ if $ab=a$

We will first prove that every element has a unique left identity, so that we can unambiguously denote 'the' left identity of $a$ by $l(a)$. Then prove that all left identities are the same, ie $\forall a,b\in G: l(a)=l(b)$.

In the proof we repeatedly use the finiteness property, together with the forcing properties and associativity. Let $n$ be the number of elements in $G$.

Consider the coset $Ga$ for an arbitrary $a\in G$. It must have exactly $n$ distinct elements because of the forcing property (why?). Hence one of those elements, say $ba$, must be $a$ (note how we have to use the finiteness property here). So $b$ must be a left identity of $a$.
$a$ can't have two left identities (why?) so $b=l(a)$.

Next we want to prove that all left identities are the same.
Two steps can accomplish this.
First prove that $l(ab)=l(a)$.
Then use the fact that $aG=G$ (which you first have to prove: use finiteness and forcing) to get the result.

So now we know there is a unique left identity in $G$, which we'll call $L$.

A similar argument shows there's a unique right identity $R$.

Next prove that $L=R$.
So we have an identity element, which we'll call $I$.

The last bit, to prove the existence of inverses is easier. Do left inverses first. For element $a\in G$ again consider what we know about $Ga$ and whether it must contain $I$, and why (finiteness and forcing again). You soon conclude that every element has a unique left inverse.

Do the same for right inverses and we conclude that every element has unique left and right inverses.
To prove they are the same we just need to put $a$, it's left and right inverse together in a formula and use the associativity property.

Good luck.

Thanks a lot! Very enlightening!

How did you get the inspiration for the proof or for most proofs? Is it by luck or by hard work?

 

[HallsofIvy]

Consider the set if even integers with the operation of multiplication. It certainly has "cancelation" and multiplication is associative. But in that case, what is the identity? What is the inverse of "2"?

 

[micromass]

Consider the set if even integers with the operation of multiplication. It certainly has "cancelation" and multiplication is associative. But in that case, what is the identity? What is the inverse of "2"?

Not a finite set.

 

[HallsofIvy]

Not a finite set.

Thanks, I hadn't even realized the initial post said finite set. No wonder I didn't understand it!

 

[andrewkirk]

How did you get the inspiration for the proof

Often, the idea for a proof of a claim comes from an intuitive feel that either the claim must be right, or that it cannot be right. If the former, one delves into why one feels that it must be right, looking for some sort of logic that underlies that feeling. If it can be found, one tries to turn it into a proof.

When one feels it cannot be right, one can set about looking for a counterexample, as both HallsOfIvy and myself did. If the claim is actually correct, the counterexample will fail, for some specific reason. In this case they turned out to fail because they were infinite sets. That's a huge clue that the finiteness property must be crucial. So one then starts thinking about that property and what difference it makes. Usually it will be an interaction between that property and the other properties (associativity, cancellation) that leads the way.

In this case there's a fairly natural way to proceed. We need to get identities before inverses, as inverses are defined in terms of identities. The least general equivalent of a full-blown identity element is a left or right identity of a specific element $a$, as defined above. So we start by trying to find those. Then we build our way up towards a full-blown identity.

To find a left-identity of $a$, we need an element that when it multiplies $a$ from the left, gives $a$. So we can think of all $n$ such multiplications and what would happen if none of them give $a$. We will then get two the same and the cancellation law will then require that two distinct elements must be the same - a contradiction. We can only argue this way because the set is finite and hence has no bijection to a proper subset of itself. If $G$ is infinite and has cancellation, it is possible for $Ga$ to be a proper subset of $G$, as the above failed counterexamples show.

 

[disregardthat]

An alternative proof of this, is to consider any element $a$ in your set. Let the set have size $n$. Then $a,a^2, ..., a^{n+1}$ cannot all be different. So $a^m = a^r$ for some nonequal integers $1 \leq m,r \leq n+1$ . Assume without loss of generality that $m$ is the largest. Then put $e = a^{m-r}$. For any other element $b$, consider $eb$. Then $a^reb = a^mb=a^rb$, so by cancellation $eb = b$. Similarly $be = b$. Thus $e$ is an identity element, and must therefore be unique. To prove that any element has an inverse, start with an element $b$. As for $a$, we may find integers $s > t$ with $b^s =b^t$, and by the same argument $b^{s-t} = e$. But then $b^{s-t-1}b = bb^{s-t-1} = b^{s-t} = e$, where by convention we define $b^0 = e$. So $b^{s-t-1}$ is an inverse of $b$.