Recall that we defined inverses for any relation:
Definition. If is a relation from to , then is a relation from to , defined by iff .
Thus (in our formalism) every function has an inverse. The inverse of a function so defined, however, may not be a function itself! (Remember that most operations we do to sets or to relations will not preserve functionhood.) So let's discover when taking the inverse (``swapping and ") actually does result in a function.
Recall that means that two conditions hold:
Exercise 1. Suppose . By substituting for , for , and for , write what it means for .
Exercise 2. Use the definition of to rewrite your conditions solely in terms of (with no anywhere).
Definition. Let . We call onto or surjective if . We call one-to-one or injective if for any , we have that guarantees .
Definition. A function which is both one-to-one and onto is called a one-to-one correspondence or a bijection.
The following theorem is important, but its proof is just the combination of Exercises 1 and 2.
Theorem. Let . Then iff is both one-to-one and onto.
Theorem. Suppose is one-to-one and is one-to-one. Then is one-to-one.
Proof. Note that the condition that be defined on the range of is necessary in order to compose the two functions as functions.
Let . Suppose . Applying the fact that the composition of functions is a function, we have
Since is one-to-one, we have . Since is one-to-one, we have . Since were arbitrary, we've shown is one-to-one. .
Theorem. Suppose is onto and is onto. Then is onto.
Proof. This is an exercise for you.