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, 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 is defined by where N denotes the positive integers. We start by assuming there are integers u and v for which f(u) = f(v). Thus, and so . 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