Binary Operations Proof

Date: 02/26/2009 at 22:31:35
From: David
Subject: Binary operations

Let s be a finite set with an associative binary operation * (it is 
not given that the operation has an identity).  Prove that there is 
an element such that a * a = a.

I know how to show this for a case but how do you prove it in 
general?  I have tried setting up a table to show examples of where s
is associative and each element * each element is itself.

Date: 02/27/2009 at 06:23:07
From: Doctor Jacques
Subject: Re: Binary operations

Hi David,

As the operation is associative, we may write "powers" of an element, 
i.e., expressions like a^n (where n is a strictly positive integer), 
without ambiguity.  Furthermore, the usual "law of exponents" holds:

  a^(m+n) = (a^m)(a^n)

although simplification is not allowed; if

  a^(m+k) = a^(n+k)

where k is a positive integer, we are not allowed to conclude that 
a^m = a^n.

Pick any element "a" in S and consider the infinite sequence of 
elements of S:

  a, a^2, a^3, ...

As S is a finite set, there is at least one element b that appears 
infinitely often in the sequence.  The means that there are at least 
two positive integers m and n, with m < n,  such that:

  b = a^m = a^n      [1]

Note that [1] implies that:

  a^(m+k) = a^(n+k)   [2]

for all k >= 0.

Can you continue from here?  Don't forget that we must have k >= 0 in 
[2], since simplification is not allowed.

Please feel free to write back if you require further assistance.


- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/