Archive for the ‘demystifying proofs’ Category

Twice to the left is back to the origin

February 14, 2010

Lemma 1: Let A be a magma. If there is a left identity e_l in A and a right identity e_r in A it follows that e_l = e_r.

Is there an identity in A, it is uniquely determined.

Proof: e_l = e_l e_r = e_r. The first identity holds because e_l is a left identity, the right because e_r is a right identity. It follows specially: If e is an identity, it is uniquely determined: Let e' be another identity, then it is e' = ee' = e because e is particularly a left identity and e' a right identity.

Lemma 2: Let A be a semigroup. If e is a neutral element and every element a \in A has a left inverse it follows that every element a \in A has a right inverse.

Proof: Let a \in A. By condition it exists a' \in A: a'a = e. Again by condition it exists a'' \in A: a''a' = e. It follows

aa' = eaa' = (a''a')aa' = a''(a'a)a' = a''ea' = a''a' = e

So we did not only show that there exists a right inverse, but also that left and right inverse are equal.

Exercise: Show that an inverse of an element a in a semigroup A is uniquely determined.

Interesting sidenote: While the proof of Lemma 2 only needs that e has the property of an left identity the proof of the exercise needs both properties of e: that it is left and right identity. That said I should mention that in the definition of an inverse or a left inverse we expect e to be a two-sided identity.

The proofs of both lemmas are straight forward. The first proof is much easier. The idea of it is to take the universal statement \forall a \in A: e_l a = a and substitute the special e_r for a. Analogous with the other side. So how do we find the proof by ourselves? In this case it is simple:
There is simply no other way. The conditions only bring two universal statements and two special elements into play. We just have to substitute the special elements.

Contrary, the proof of Lemma 2, seems to fall from heaven. In the first place, it is not at all clear, that the left inverse a' is the searched right inverse. Then, in the proof we insert arbitrarily an identity e (by the way we have 3 places to do so) and everything works fine.
I claim that the fundamental point is associativity. It allows us to use the symmetry between left- and right inverse: a' is left inverse to a and on the other side right inverse to a''.
Let us assume we dont know the proof. We want to show that there exists an element b such that ab = e and let us assume we dont know that the b we are searching for equals a'. What could we do? How do we find the “right” b (assuming such one exists)?
Well, first we always look at the conditions. They tell us that there exists an a' such that a'a = e. Now we got a new player and can substitute him. The problem is: Even if we substitute the “right” b (= a') we cannot immediately deduce that (ab = )aa' = e. We only know that a'a = e. Commutativity is not assumed. We can only continue to play on around:

a' also has an left inverse, lets call it a''. We get ab = e = a''a'. What did we gain? On the right side “a” doesnt even show up anymore. Let us put everything into one line:

ab = e = a''a' = a'a \quad\quad\quad (\ast)

Still no idea. Let us meditate a bit over this line. Shortly before we fall asleep the right equal sign begins to fade away and the two a'`s become one. Mentioning that we still didnt use associativity, we see that a''a'a = a''(a'a) = (a''a')a \Rightarrow a''e = ea \Rightarrow a'' = a.
The left inverse of the left inverse equals our original element. We went twice to the left and returned to the origin. Substituing back a for a'' in (\ast) we’ve got e = aa' = a'a
I propose the following experiment: Find some first year undergraduate and let her/him try to proof Lemma 1 and Lemma 2 by her/himself. Do she/he finds the proofs and how? Even people who dont study maths and are told the basic definitions will find the proof of Lemma 1. I would be curious about the ways people handle Lemma 2.

Looking back at my way of finding the proof or better to say the essence of Lemma 2, it seems to me like nonsense – we just found the proof by playing around. How would you reveal the proof, what hints would you give to an undergraduate student so that she/he will find the proof?

Advertisements