2 Sets and functions 2.9 Invertibility 2.11 Permutations

2.10 Conditions for invertibility

Here is the connexion between function properties and invertibility.

Theorem 2.10.1.

Let $f:X\to Y$ be a function between nonempty sets.

1.

$f$ has a left inverse if and only if it is injective.
2.

$f$ has a right inverse if and only if it is surjective.
3.

$f$ has a two sided inverse if and only if it is bijective.

Proof.

1.
- •
  
  ONLY IF. Let $g$ be a left inverse to $f$ , so $g\circ f=\operatorname{id}_{X}$ . Suppose $f(a)=f(b)$ . Then applying $g$ to both sides, $g(f(a))=g(f(b))$ , so $a=b$ .
- •
  
  IF. Let $f$ be injective. Choose any $x_{0}$ in the domain of $f$ . Define $g:Y\to X$ as follows. Each $y$ in $Y$ is either in the image of $f$ or not. If $y$ is in the image of $f$ , it equals $f(x)$ for a unique $x$ in $X$ (uniqueness is because of the injectivity of $f$ ), so define $g(y)=x$ . If $y$ is not in the image of $f$ , define $g(y)=x_{0}$ . Clearly $g\circ f=\operatorname{id}_{X}$ .
2.
- •
  
  IF. Suppose $f$ has a right inverse $g$ , so $f\circ g=\operatorname{id}_{Y}$ . If $y\in Y$ then $f(g(y))=\operatorname{id}_{Y}(y)=y$ , so $y\in\operatorname{im}(f)$ . Every element of $Y$ is therefore in the image of $f$ , so $f$ is onto.
- •
  
  ONLY IF. Suppose $f$ is surjective. Let $y\in Y$ . Then $y$ is in the image of $f$ , so we can choose an element $g(y)\in X$ such that $f(g(y))=y$ . This defines a function $g:Y\to X$ which is evidently a right inverse to $f$ .
3.

If $f$ has a left inverse and a right inverse, it is injective (by part 1 of this theorem) and surjective (by part 2), so is a bijection. Conversely if $f$ is a bijection it has a left inverse $g:Y\to X$ and a right inverse $h:Y\to X$ by part 1 and part 2 again. We will now show $g=h$ , so that $g$ is a two sided inverse to $f$ .

$\displaystyle g$ $\displaystyle=g\circ\operatorname{id}_{Y}$ Proposition 2.7.1

$\displaystyle=g\circ(f\circ h)$ $\displaystyle\text{as }f\circ h=\operatorname{id}_{Y}$

$\displaystyle=(g\circ f)\circ h$ associativity

$\displaystyle=\operatorname{id}_{X}\circ h$ $\displaystyle\text{as }g\circ f=\operatorname{id}_{X}$

$\displaystyle=h$

so $g=h$ is a two sided inverse of $f$ . ∎

Figure 2.11: A diagram illustrating the construction, in part 1 of the theorem, of the left inverse to an injective function

f:X\to Y

where

X=\{x,y,z\}

Y=\{a,b,c,d,e\}

, and

f(x)=c,f(y)=b,f(z)=a

. Left-to-right arrows show where

f

sends elements of

X

and right-to-left arrows show where

g

sends elements of

Y

. The elements

d

and

e

Y

which are not in the image of

f

are all sent to the element

x

X

Figure 2.11 illustrates the construction in part 1 of the theorem. Arrows from left to right show where $f$ sends each element of $X$ . Arrows from right to left show where the left inverse $g$ we have constructed sends each element of $Y$ .

Definition 2.10.1.

If $f:X\to Y$ is invertible, we write $f^{-1}$ for the two sided inverse of $f$ .

It makes sense to talk about the two sided inverse to $f$ because there really is only one: if $g$ and $h$ are two sided inverses of $f$ then certainly $g$ is a left inverse and $h$ is a right inverse, so the argument in the proof of part 3 of the theorem above shows $g=h$ .

2.10.1 Inverse of a composition

Theorem 2.10.2.

If $f:X\to Y$ and $g:Y\to Z$ are invertible then so is $g\circ f$ , and $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ .

Proof.

$f^{-1}\circ g^{-1}$ is a left inverse to $g\circ f$ , because

$\displaystyle(f^{-1}\circ g^{-1})\circ(g\circ f)$	$\displaystyle=f^{-1}\circ(g^{-1}\circ g)\circ f$	associativity
	$\displaystyle=f^{-1}\circ\operatorname{id}_{Y}\circ f$
	$\displaystyle=f^{-1}\circ f$
	$\displaystyle=\operatorname{id}_{X}.$

A similar calculation shows that it is a right inverse as well. ∎

It is important to get this the right way round. The inverse of $g\circ f$ is not normally $g^{-1}\circ f^{-1}$ , indeed this composition may not even make sense. The correct result is easy to remember when you think about getting dressed. Each morning you put on your socks, then you put on your shoes: if $k$ is the put-on-socks function and $h$ is the put-on-shoes function then you apply the function $h\circ k$ to your feet. The inverse of this is taking off your shoes, then taking off your socks: $k^{-1}\circ h^{-1}$ . Not the other way round — it’s not even (normally) possible to take off your socks, then take off your shoes, just as it is not normally possible to form the composition $g^{-1}\circ f^{-1}$ in the context of the theorem above.³³ 3 The shoes and socks illustration comes from Gilbert Strang’s famous 18.06 linear algebra course.

A similar result applies when you compose more than two invertible functions: if $f_{1},f_{2},\ldots,f_{n}$ are invertible and if the composition

f_{1}\circ\cdots\circ f_{n}

makes sense, it is also invertible and its inverse is

f_{n}^{-1}\circ\cdots\circ f_{1}^{-1}.

$\displaystyle g$	$\displaystyle=g\circ\operatorname{id}_{Y}$	Proposition 2.7.1
	$\displaystyle=g\circ(f\circ h)$	$\displaystyle\text{as }f\circ h=\operatorname{id}_{Y}$
	$\displaystyle=(g\circ f)\circ h$	associativity
	$\displaystyle=\operatorname{id}_{X}\circ h$	$\displaystyle\text{as }g\circ f=\operatorname{id}_{X}$
	$\displaystyle=h$