Functions whose Inverses are Functions

Recall that we defined inverses for any relation:

Definition. If R is a relation from A to B, then R^{-1} is a relation from B to A, defined by (b,a)\in R^{-1} iff (a,b)\in R.

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 x and y") actually does result in a function.

Recall that g:A\rightarrow B means that two conditions hold:

  1. \operatorname{Domain}(g)=A
  2. \left((a,b)\in g\text{ and }(a,c)\in g\right)\Rightarrow b=c.

Exercise 1. Suppose f:X\rightarrow Y. By substituting f^{-1} for g, X for A, and Y for B, write what it means for f^{-1}:Y\rightarrow X.

Exercise 2. Use the definition of f^{-1} to rewrite your conditions solely in terms of f (with no f^{-1} anywhere).

Definition.  Let f:X\rightarrow Y. We call f onto or surjective if \forall y\in Y, \exists x\in X: y=f(x). We call f one-to-one or injective if for any x,z\in X, we have that f(x)=f(z) guarantees x=z.

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 f:X\rightarrow Y. Then f^{-1}:Y\rightarrow X iff f is both one-to-one and onto.

Theorem.  Suppose f:X\rightarrow Y is one-to-one and g:\operatorname{Range}(f)\rightarrow Z is one-to-one. Then g\circ f:X\rightarrow Z is one-to-one.

Proof. Note that the condition that g be defined on the range of f is necessary in order to compose the two functions as functions.

Let x,z\in X. Suppose g\circ f(x)=g\circ f(z). Applying the fact that the composition of functions is a function, we have


Since g is one-to-one, we have f(x)=f(z). Since f is one-to-one, we have x=z. Since x,z were arbitrary, we've shown g\circ f is one-to-one. \Box.

Theorem. Suppose f:X\rightarrow Y is onto and g:Y\rightarrow Z is onto. Then g\circ f is onto.

Proof. This is an exercise for you.