# 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

1. 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$.

2. 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$.

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

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

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

6. 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}$.

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