well defined functions

February 17, 2010

Motivated by the interesting article you can find here, I explain how a function is usually defined based on relations. I think, dividing the “functional property” of a function into two properties (left-total, right-unique), makes it easy to explain to an undergraduate what we mean when we say a function is well defined.

A function f is a relation {f = (A,B,R)} (a relation is a tripel f = (A,B,R), consisting of sets A, B and R, with {R \subset A \times B}) satisfying the following two properties:
(i) {\forall a \in A \, \exists \, b \in B: (a,b) \in R}
(ii) {\forall a \in A \, \forall \, b_1, b_2 \in B \text{ with } (a,b_1) \in R \wedge (a,b_2) \in R \Rightarrow b_1 = b_2}

For (i) we say: R is a left-total relation. (Every element of A is related at least with one element of B.)
For (ii) we say: R is right-unique relation. (Every element of A is related at most with one element of B.)

Alltogether we get: {\forall a \in A \; \exists! \, b \in B: (a,b) \in R}

Because of the right-uniqueness we can use the following notation: {b = f(a)} instead of {(a,b) \in R} \text{ or } {aRb}.

To get basic intuition for working with relations and functions it can be helpful to draw some pictures that look like the two below: On the left we draw our domain A and on the right our codomain B. The dots represent the elements of the sets. Whenever b = f(a) for {a \in A, b \in B} we connect the two dots representing a and b with an arrow.
Property (i) forbids the situation on the left (because there are some elements in the set A where no arrow is coming from and going to some element in B) while property (ii) forbids a situation like the one on the right (because there is an element of A which is “mapped” to more than one element of B).

By the way, a function f is injective(one-to-one) iff the inverse relation {f^{-1}} (which in general is no function) is right-unique because injective is equivalent to left-unique. Analogous, a function f is surjective(onto) iff the inverse relation {f^{-1}} is left-total because surjective is equivalent to right-total. A good way to get an understanding what one-to-one and onto mean, is to work out by yourself how the “forbidden pictures” look like (e.g. if some function is not onto or not one-to-one).

Now, what does it mean if we ask if a function f is well defined? First of all it could be better(but longer) to ask instead: “Is this relation f a well defined function, does it satisfy property (i) and (ii)” ? (we assume that the presented declaration is at least a relation)
For example, in an elementary topology or analysis course we show that the sets we call “open ball” are open in a metric space. Of course it is fine to call these sets “open balls”, but for pedagogical reasons, i recommend to introduce these sets first without giving them any name, proofing that they are open and to label them “open balls” at the end.
It is the same with “well defined functions”. Imagine an undergraduate who is confronted with some definition that is not stated unambiguously in some sense but should define a function. If someone asks him if the construction is a well defined function, the student will probably get confused.
But i am sure it will be straight forward for him to check if conditions (i) and (ii) are satisfied.

The following easy counterexample shows what a gunction (a term I stole from the article above, heh) – a not well defined function – can look like. I will use the notation that usually is used to define functions to show how easy it is to overlook bad definitions.

{f: \mathbb{R} \rightarrow \mathbb{R}, f(x) = \sqrt{x}}.
This declaration does not represent a (well defined) function. It satisfies none of the properties (i) and (ii). It is not left-total because there is no quareroot for negative x and it is not right-unique because there are two squareroots for positive x. If we restrict the domain to the positive reals f it becomes left-total but still is not right-total. Also if we only restrict the codomain to the positive reals we still dont get a function. We have to restrict both the domain and codomain to the positive reals. First then the function becomes well-defined.

A last note: most times we have to check condition (ii), for example when working with equivalence classes.


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?