Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

🔗

Section 10.6 Inverse functions

🔗
We now have enough machinery to start working on inverse functions. Consider what an inverse function needs to do. If we start with a∈A and apply a function f:A→B then we obtain some element b∈B. We want our inverse to “undo” this and take b back to a. We’ll start by defining functions that are nearly inverses and give a few examples.
🔗
But before we do that, we note that some of the material below is a bit technical. The reader who is interested in these details should continue on. The reader who wishes to just get to the main results should instead skip ahead to Definition 10.6.6 and Theorem 10.6.8
🔗

Definition 10.6.1.

🔗
🔗
Recall Definition 10.4.12, and let f:A→B and g:B→A be functions.
  • 🔗
    If g∘f=iA then we say that g is a left-inverse of f.
  • 🔗
    Similarly, if f∘g=iB then we say that g is a right-inverse of f.
🔗
🔗
So notice that if we start at some point a∈A and apply f to get b∈B, then a left-inverse g tells us how to get back from b to a:
g(b)=g(f(a))=a
🔗
On the other hand, if are trying to get to a particular point b∈B in the codomain using f, then the right-inverse tells you a possible starting point a∈A:
g(b)=a so that f(a)=f(g(b))=b
🔗

Example 10.6.2.

🔗
🔗
Let A={1,2} and B={4,5,6} and define
f:A→Bf(1)=4,f(2)=5g:B→Ag(4)=1,g(5)=2,g(6)=2
🔗
as depicted below.
🔗
🔗
Then notice that g∘f:A→A satisfies
g(f(1))=g(4)=1 and g(f(2))=g(5)=2.
🔗
That is g∘f=iA and so is a left-inverse of f. At the same time, f∘g:B→B satisfies
f(g(4))=f(1)=4f(g(5))=f(2)=5butf(g(6))=f(2)=5
🔗
and so g is not a right-inverse of f.
🔗
By swapping the roles of f,g in the above we can construct a function that is a right-inverse but not a left-inverse. Consider the functions defined in the image below.
🔗
🔗
Then we see that
g(f(1))=g(4)=1g(f(2))=g(5)=2butg(f(3))=g(5)=2
🔗
and so g is not a left-inverse of f. And then
f(g(4))=f(1)=4andf(g(5))=f(2)=5
🔗
making g a right-inverse of f.
🔗
Notice in the above example, that the function that has a left-inverse is injective, while the function with the right-inverse is surjective. This is not a coincidence as the following two lemmas prove.
We prove each implication in turn.
  • Assume that f has a left-inverse, g. Now let a1,a2∈A so that f(a1)=f(a2). Then g(f(a1))=g(f(a2)), but since g is the left-inverse of f, we know that g(f(a1))=a1 and g(f(a2))=a2. Thus a1=a2 and so f is injective.
  • Now let f be injective. We construct a left-inverse of f in two steps. First pick any α∈A. Then consider the preimage of a given point b∈B. That preimage, f−1({b}), is empty or not.
    • If f−1({b})=∅, then define g(b)=α
    • Now assume that f−1({b})≠∅. Since f is injective, the preimage f−1({b}) contains exactly 1 element. To see why, consider a,c both in the preimage. We must have f(c)=f(a)=b (since they are both in the preimage of b), but since f is an injection, we must have c=a. So define g(b)=a the unique element in the preimage.
    To summarise
    g(b)={αif preimage emptyaotherwise take unique a in the preimage.
    Now let a∈A, under f it maps to some b∈B with b=f(a). Hence (as argued above) a is the unique element in the preimage of b, and so g(f(a))=g(b)=a. Thus g is a left-inverse of f.
We prove each implication in turn.
  • Assume that f has a right-inverse, g. Now let b∈B and set a=g(b). Then f(a)=f(g(b))=b and so f is surjective.
  • Now let f be surjective and let b∈B. For the sake of this proof, let us denote the preimage of b as
    Ab={a∈A∣f(a)=b}.
    Since f is surjective, we know that Ab≠∅ for every b∈B. So now define g(b) to be any 140  element of Ab.
    Now let b∈B, then under g it maps to some a∈A so that (by construction) f(a)=b. Hence f(g(b))=f(a)=b and thus g is a right-inverse as required.
🔗
These lemmas tell us that a function has both a left inverse and right inverse if and only if it is bijective. We can go further those one-sided inverses are actually the same function.
Let f,g,h be as stated. Then we know that
g∘f=iA and f∘h=iB
Now starting with g we can write:
g=g∘iB=g∘(f∘h)=(g∘f)∘h=iA∘h=h
and thus g=h as required.
The last part of the lemma follows by combining the previous two lemmas.
🔗
So this lemma tells us conditions under which a function will have both a left- and right-inverse, and that those one-sided inverses are actually the same function. A function that is a left- and right-inverse is a (usual) inverse.
🔗

Definition 10.6.6.

🔗
Let f:A→B and g:B→A be functions. If g∘f=iA and f∘g=iB then we say that g is an inverse of f.
🔗
Note that we will prove that the inverse is unique, and so we will be able to say that g is the inverse of f and denote it f−1.
🔗
Also note that if a function is an inverse then it is also a left- and right-inverse.
This proof is very similar to the proof of Lemma 10.6.5. Let g:B→A and h:B→A both be inverses to the function f. Then
g=g∘iB=g∘(f∘h)=(g∘f)∘h=iA∘h=h
and so g=h. Thus the inverse is unique.
🔗
We can now state our main theorem about inverse functions.
We combine some of the lemmas above to prove this result.
  • Assume that f has an inverse. Then that inverse is both a left-inverse and a right-inverse. Lemma 10.6.5 then implies that f is both injective and surjective, and so is bijective.
    Now assume that f is bijective. Then Lemma 10.6.5 tells us there exists a function g that is a left-inverse and right-inverse for f. Then, by definition g is an inverse for f.
  • The uniqueness of the inverse is proven by Lemma 10.6.7.
🔗
Theorem 10.6.8 tells us under what circumstances a function has an inverse. However, it does not tell us if that inverse has a nice expression. If the original function is nice enough, then we may be able to state the inverse nicely. Here are a couple of such examples.
🔗

Example 10.6.9.

🔗
🔗
The function f:R→R defined by f(x)=7x−3 is bijective and so has an inverse function. We proved this in Result 10.4.2 and Result 10.4.2. The inverse is f−1:R→R and we can work out a formula for it by solving y=f(x) for x in terms of y. Notice that we did exactly that when we proved that f was surjective. In particular, we found that
f−1:R→Rdefined byf−1(y)=y+37.
🔗
🔗
To verify that this is correct it suffices to show that f−1∘f is the identity function:
f−1∘f(x)=f−1(7x−3)=(7x−3)+3y=x
🔗
as required.
🔗

Example 10.6.10. Möbius continued.

🔗
🔗
In Result 10.4.14 above we saw that a Möbius transformation h:R−{dc}→R−{ac} defined by
h(x)=ax−bcx−d
🔗
is bijective. The above result tells us that it has an inverse function. We can verify that the inverse is h−1:R−{ac}→R−{dc} defined by
h−1(y)=dy−bcy−a.
🔗
(which we computed while proving the result). We simply need to show that h−1∘h is the identity:
h−1(h(x))=h−1(ax−bcx−d)=dax−bcx−d−bcax−bcx−d−a=d(ax−b)−b(cx−d)c(ax−b)−a(cx−d)=(ad−bc)xad−bc=x
🔗
as required.
That one can do this is not as obvious as it might seem. In particular, if B is infinite we need the Axiom of Choice in order to make this selection. The interested reader should search engine their way to more information on this. Now in the event that our function f is injective, then Ab contains exactly one element and we don’t need the Axiom of Choice to construct our function. Thankfully we apply this result when our function is bijective — phew.
<Prev^TopNext>