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:
- $\operatorname{Domain}(g)=A$
- $\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 \begin{align*}g(f(x))=g(f(z))\end{align*}
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.