Naive Set Theory: Functions
Inverses and Identities
Motivation: Undoing a Function
Consider some function $f : A \rightarrow B$, which maps elements from $A$ to elements in $B.$ We might ask about whether we can derive a function function that "undoes" this mapping. In other words, for an element $f(a) \in B$, can we recover the $a \in A$ from whence it came? To test this question, we need to formalize the concept of an identity function and then that of an inverse.
Identity Functions
The identity for a set $C$ is a function $I_C : C \rightarrow C$ such that $I_C(c) = c$ for all $c \in C.$ Identity functions are not terribly interesting on their own, but they allow us to define the inverse of a function. Namely, if the composition of two functions forms an identity function, then that means that one function has "undone" the mapping of the other.
Inverses
A function that "undoes" another by producing for a given element of the image set of a function the element in the domain that produced it is called an inverse. Formally, a function $g : B \rightarrow A$ is a left inverse of $f$ if $g \circ f = I_A$. Likewise, a function $h : B \rightarrow A$ is a right inverse of $f$ if $f \circ h = I_B$. If a function has both a left inverse and a right inverse, then the two inverses are in fact the same function, which is simply called the inverse. Formally, a function $f^{-1} : B \rightarrow A$ is the inverse of a function $f : A \rightarrow B$ if $f \circ f^{-1} = I_B$ and $f^{-1} \circ f = I_A.$ This means that $f(f^{-1}(b)) = b$ and $f^{-1}(f(a)) = a$ for all $a \in A$ and $B \in B.$ Functions that have inverses are said to be invertible.
Condition for the Existence of Inverses
There is a strong condition that allows us to determine whether a function has an inverse. Namely, a function has an inverse if and only if it is a bijection. The proof of this fact is left as a (solved) exercise. It is useful to note that injective functions that are not bijective may be trivially converted into bijections, and thus made invertible, by shrinking the codomain to be identical to the image set.
Problems
Let $f : A \rightarrow B$ be a function. Show that $f$ has a left inverse if and only if $f$ is bijective.
If $f$ has a left inverse, then there exists a function $g : B \rightarrow A$ such that $g \circ f = I_A$. By definition of identity, for each $a \in A$, $(g \circ f)(a) = a$, and by definition of composite function, $(g \circ f)(a) = g(f(a))$. Therefore $g(f(a)) = a$. For each $f(a) \in B$, assume that there is another element $a' \in A$ such that $f(a') = f(a)$. Then $g(f(a)) = a$ and $g(f(a')) = a'$. But $g(f(a))=g(f(a'))$, so $a = a'$. Thus, $f(a')=f(a) \implies a=a'$. Therefore $f$ is injective.
Let $f : A \rightarrow B$ be an injection. By assigning $c$ to be some fixed element in $A$, we construct a function $g : B \rightarrow A$ whose rule is defined as follows:
$g(b) = \left\{ \begin{matrix} a & \text{ where } b = f(a) \text{ for some } a \in A \\ c & \text{otherwise} \end{matrix} \right.$
The fact that $f$ is injective ensures the uniqueness of the element $a$ given the input element $f(a)$. Next consider the composite function $g \circ f$. For all $a \in A$, $g(f(a)) = a$, and therefore $g \circ f = I_A$. Therefore $g$ is a left inverse of $f$.
Let $f : A \rightarrow B$ be a function. Show that $f$ has a right inverse if and only if it is surjective.
If $f$ has a right inverse, then there exists a function $g : B \rightarrow A$ such that $f \circ g = I_B$. By definition of identity, for each $b \in B$, $(f \circ g)(b) = b$, and by definition of composite function, $(f \circ g)(b) = f(g(b))$. Therefore $f(g(b)) = b$. Because for each $b \in B$ there is a corresponding $a = g(b) \in A$ such that $f(a) = b$, it follows that $f$ is surjective.
Let $f : A \rightarrow B$ be a surjection. Then for each $b \in B$ there is at least one $a \in A$ such that $f(a) = b$. We construct a function $g : B \rightarrow A$ whose rule is defined as follows:
$g(b) = a_b \text{ where } a_b \text { is a fixed element in } A_b, \text{ where } A_b = \{ a \in A : f(a) = b\}$.
The fact that $f$ is surjective ensures that for each $b \in B$ the set $A_b$ is nonempty. Next consider the composite function $f \circ g$. For all $b \in B$, $f(g(b)) = b$, which means that $f \circ g = I_B$. Therefore $g$ is a right inverse of $f$.
Show that a function $f : A \rightarrow B$ is bijective if and only if it has a left inverse and a right inverse.
If $f$ is bijective, it is both injective and surjective. Because $f$ is injective, it has a left inverse, and because $f$ is surjective, it has a right inverse.
If $f$ has a left inverse, then it is injective. Likewise, if $f$ also has a right inverse, then $f$ is also surjective. Because $f$ is both injective and surjective, it follows that $f$ is bijective.
Give an example of a function that has a left inverse but no right inverse.
Let $f : \{1,2\} \rightarrow \{a,b,c\}$ be a function whose rule is $\{(1, a), (2, b)\}$. Clearly $f$ is injective, so $f$ has a left inverse, however $f$ is not surjective, as no element in its domain maps to the element $c$ in the codomain. Therefore $f$ does not have a right inverse.
Give an example a function that has a right inverse but no left inverse.
Let $f : \{1,2,3\} \rightarrow \{a,b\}$ be a function whose rule is $\{(1, a), (2, b), (3,b)\}$. Clearly $f$ is surjective, so $f$ has a right inverse. However, $f$ is not injective, as both the elements $2$ and $3$ map to the elemtn $b$ in the codomain. Therefore $f$ does not have a left inverse.
Prove that if a function $f : A \rightarrow B$ has a left inverse $g$ and a right inverse $h$, then $g = h = f^{-1}$.
Since $h$ is a right inverse of $f$, $f(h(b)) = b$. Likewise, because $g$ is a left inverse of $f$, $g(f(h(b))) = g(b)$. For each $a \in A$, $g(f(a)) = a$. Let $a = h(b)$. Then $g(b) = g(f(h(b))) = g(f(a)) = a = h(b)$. Since $f$ has both a left and a right inverse, it is bijective. The bijectivity of $f$ ensures that for each $b \in B$ there is exactly one $a \in A$ such that $a = g(b) = h(b)$. By definition of inverse, $g = h = f^{-1}$.
Show that for every nonempty set $A$, the identity $I_A$ is bijective.
We must show that $I_A$ is both injective and surjective.
Assume $I_A(a) = I_A(b)$. Because $I_A(a) = a$ and $I_A(b) = b$, it follows that $a = b$, so $I_A$ is injective. Likewise, for every $a \in A$, $I_A(a) = a$, thus $I_A$ is also surjective. Therefore $I_A$ is bijective.