# Naive Set Theory: Functions

## Inverses and Identities

Imagine the most boring function you possibly can. This function should be as useless and insipid a function could ever aspire to be. Have one in mind? Well, it's called an identity. 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$. Truly an idea to behold, isn't it? The function does absolutely nothing - it just returns the input unchanged. Yet, while this function does not provide the most breathtaking mathematical vista, figuring out whether functions combine to *form* an identity is pretty darn interesting.

Consider our more malleable trusty function $f : A \rightarrow B$, which maps elements from $A$ to elements in $B$. But what about going the other way from $B$ to $A$? What if we want to "undo" the mapping? For an element $f(a) \in B$, can we recover the $a \in A$ from whence it came?

The answer is yes, and the way to do it is with a function called an inverse. 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 is like placing items in a safe, then an inverse is like figuring out how to get them back out. Sometimes the code is easy, but other times it's pretty tough to crack!

And here's the twist - if a function has both a left inverse and a right inverse, then the two inverses are the *same* function. Formally, for a bijective function $f : A \rightarrow B$, there exists a function called the **inverse** of $f$, denoted $f^{-1} : B \rightarrow A$, such that $f^{-1}(f(a)) = a$.

This definition of an inverse function is made in terms of bijections rather than left and right inverses. It's left as a (solved!) exercise to show that there is indeed an equivalent definition in terms of left and right inverses.

## 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.