next up previous
Next: Proving Functions are Onto Up: NOTES ON BASIC PROOFS Previous: Proving Sets Equal

Proving Functions One-to-One

Often we are required to prove that a function f, tex2html_wrap_inline208 is one-to-one, or an injection. A proof of this depends on how the function is given to us and what properties the function has. For functions that are given by some formula there is a standard way. We use the contrapositive of the definition of one-to-one, namely that if f(u) = f(v) then u = v. For example, suppose that tex2html_wrap_inline214 is defined by tex2html_wrap_inline216 where N denotes the positive integers. We start by assuming there are integers u and v for which f(u) = f(v). Thus, tex2html_wrap_inline224 and so tex2html_wrap_inline226 . Then, (u-v)(u+v) = 0. Since the product is zero then u-v = 0 or u+v = 0. The first condition tells us that u=v. The second condition says that v = -u. However, since u > 0 this would imply v < 0 which is impossible since v is positive. Hence, u =v as required and f is one-to-one. There are other methods used to prove a function is one-to-one. In calculus for example, if f is differentiable then it is sufficent to show that the derivative is positive everywhere or negative everywhere. In linear algebra, if f is a linear transformation it is sufficient to show that the kernal of f contains only the zero vector. If f is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice in the list.

Peter Williams
Wed Aug 21 23:10:39 PDT 1996