I'm trying to make the below proof as rigorous as possible, but I am not completely certain on how to phrase several steps and their justifications. The statement is:
Let $f: X \to Y$ be a map of sets. A function $g: Y \to X$ is called a left (resp. right) inverse of $f$ if $g \circ f = \mathrm{id}_X$ (resp. $f \circ g = \mathrm{id}_Y$).
- Show that $f$ admits a right inverse if and only if $f$ is surjective (onto). Show that, in general, a right inverse is not unique.
- Show that $f$ admits a left inverse if and only if $f$ is injective (one-to-one). Show that, in general, a left inverse is not unique.
The prompt doesn't require that $X,Y $be nonempty, so I felt the need to first rule out these "edge cases."
We first rule out the edge cases. Notice that if one of $X$ or $Y$ is empty, then the other must be empty for this result to hold. Indeed, if $X = \emptyset$, then $f: X \to Y$ is only defined if $Y = \emptyset$. Similarly, if $Y = \emptyset$, then a function $g: Y \to X$ is defined only if $X = \emptyset$. So if $X = Y = \emptyset$, then $f: X \to Y$, the empty function, is vacuously bijective and is, in fact, its own inverse. We proceed under the assumption that $X,Y \neq \emptyset$.
I'm not sure if this above explanation is fully rigorous. Here's now my attempt at the forward direction for part (a).
Suppose that $f$ admits a right inverse $g: Y \to X$. Given $y \in Y$, there exists a unique $x \in X$ such that $g(y) = x$. But then
$$f(g(y)) = (f \circ g)(y) = \mathrm{id}_Y (y) = y = f(x),$$
so $f$ is surjective.
I'm fairly confident in this forward direction, but less so in the backward direction.
Conversely, suppose that $f$ is surjective. Define the function $g: Y \to X$ sending $y \longmapsto x$ for some preimage $x \in f^{-1} (y)$. In the case where the preimage of $y$ in $x$ is non-unique, we apply the axiom of the choice to pick a single $x$. Given $y \in Y$ with corresponding $x = g(y)$, we have
\begin{align*}
(f \circ g)(y) = f(g(y)) = f(x) = y,
\end{align*}
so $f \circ g = \mathrm{id}_Y$, and $f$ admits a right inverse.
My key point of confusion is whether it makes sense to "define" $x$ as $g(y)$. The more rigorous approach seems to be to argue that $f \circ g = \mathrm{id}_Y$ by definition, or perhaps there's a better argument.
For lack of uniqueness, here's what I came up with. I'll be defining $\mathbb{Z}/2 = \{0,1\}$ with addition given by $(a,b) \mapsto$ $a + b$ if $a + b < 2$ and $a + b – 2$ otherwise.
I claim that a right inverse is not
in general unique. Consider the reduction map
$$
\begin{array}{rccl}
f \colon & \mathbb{Z} & \longrightarrow & \mathbb{Z}/2 \\
& a & \longmapsto & a \text{ mod $2$}.
\end{array}
$$
Notice that $f$ is surjective, but $1,3 \in f^{-1} (1)$, so we can define right inverses $g_1: Y \to X$ sending
$$
y \longmapsto \begin{cases}
1, \; \text{ if $y = 1$} \\
0, \; \text{ if $y = 0$}
\end{cases}
$$
and $g_2: Y \to X$ sending
$$
y \longmapsto \begin{cases}
3, \; \text{ if $y = 3$} \\
0, \; \text{ if $y = 0$}.
\end{cases}
$$
Given $y \in \mathbb{Z}/2$, we then have
\begin{align*}
(f \circ g_1)(y) = f(g_1 (y)) = \begin{cases}
f(1), \; \text{ if $y = 1$} \\ f(0), \; \text{ if $y = 0$}
\end{cases} \hspace{-2.5mm} = \begin{cases}
1, \; \text{ if $y = 1$} \\
0, \; \text{ if $y = 0$}
\end{cases}
\end{align*}
so $f \circ g = \mathrm{id}_Y$. Similarly, for any $y \in \mathbb{Z}/2$, we have
\begin{align*}
(f \circ g_2)(y) = f(g_2 (y)) = \begin{cases}
f(3), \; \text{ if $y = 1$} \\ f(0), \; \text{ if $y = 0$}
\end{cases} \hspace{-2.5mm} = \begin{cases}
1, \; \text{ if $y = 1$} \\
0, \; \text{ if $y = 0$} \end{cases},
\end{align*}
so $f \circ g_2 = \mathrm{id}_Y$, so $g_1 \neq g_2$ are both right inverses of $f$.
I believe the above is correct unless there is a more 'general' approach than a simple counterexample.
Now, for part (b), beginning with the forward direction.
Suppose that $f$ admits a left inverse $g: Y \to X$. Given $a,b \in X$ for which $f(a) = f(b)$, we have
\begin{align*}
a = \mathrm{id}_X (a) = (g \circ f)(a) = g(f(a)) = g(f(b)) = (g \circ f)(b) = \mathrm{id}_X (b) = b,
\end{align*}
so $f$ is injective.
Again, I feel fairly confident about the forward direction, but less so about the backward direction.
Suppose that $f: X \to Y$ is injective. Fix $x_0 \in X$, and define the map $g: Y \to X$ by
$$
y \longmapsto \begin{cases}
x, \; & \text{ if $y = f(x)$ for some $x \in X$} \\
x_0, \; & \text{ if $y \not \in f(X)$}
\end{cases}
$$
This map is well-defined because if $y \in f(X)$, its preimage in $X$ is unique because $f$ is injective. Then, for any $x \in X$ for which $f(x) = y$ for a unique $y \in Y$, we have
\begin{align*}
(g \circ f)(x) = g(f(x)) = g(y) = y,
\end{align*}
so $g \circ f = \mathrm{id}_X$, as desired.
Again, I'm not sure if it's fully rigorous to define $f(x) = y$, or if I should argue that $x$ is the unique element of $X$ mapping to $y$ or, simply, that $g \circ f = \mathrm{Id}_X$ by definition.
Here is the final step that a left inverse isn't unique.
I claim that a left inverse is not, in general, unique. Let $X = \{1,2\}$ and $Y = \{3,4,5\}$, and define the map $f: X \to Y$ by $1 \longmapsto 3$, $2 \longmapsto 4$. Then we can define the following two inverses:
\begin{align*}
& g_1: Y \to X, \; 3 \longmapsto 1, 4 \longmapsto 2, 5 \longmapsto 1 \\
& g_1: Y \to X, \; 3 \longmapsto 1, 4 \longmapsto 2, 5 \longmapsto 2.
\end{align*}
How do these look? My main concerns, as I noted, are (1) the edge cases; (2) the proof that I constructed a proper left inverse; (3) the proof that I constructed a proper right inverse; and (4) the way to notate the left inverse $g: Y \to A$, because the definition, though it is well-defined, sounds as though it isn't well-defined (i.e., the "for some $x \in X$").
Best Answer
Your assertions about empty sets are incorrect.
Recall that a function from a set $X$ to a set $Y$ is a subset $f\subseteq X\times Y$ such that
The function is injective if and only if for all $x,x’\in X$ and $y\in Y$, if $(x,y),(x’,y)\in f$, then $x=x’$.
The function is surjective if and only if for all $y\in Y$ there exists $x\in X$ such that $(x,y)\in f$.
If $X$ is empty, and $Y$ is any set, empty or not, the empty set $\varnothing\subseteq \varnothing\times Y = X\times Y$ satisfies the definition of being a function from $X=\varnothing$ to $Y$, hence is a function. Moreover, it satisfies the definition of being injective, hence is injective: there is always a function from the empty set to any set, and it is always injective.
However, that function only has a left inverse when the codomain is empty. So the statement you are trying to prove about injective functions is not quite true as written: you must exclude $X=\varnothing$ in order for it to be true.
That said, I applaud that you recognized the need to deal with the possibility of empty sets. Many people forget about that (for example, whoever wrote this problem up did!)
Your proof of (a) is correct; but you need to take into account the case where $X=\varnothing$. In this case, you can conclude from surjectivity that $Y=\varnothing$, and from the existence of a right inverse that $Y=\varnothing$.
As to “defining” the right inverse... In the nonempty sets dcadse, the “better way” of specifying the right inverse is to explicitly use the Axiom of Choice. For example, one formulation of the Axiom of Choice is that given any nonempty family of nonempty sets $\{A_i\}_{i\in I}$, there exists a function $g\colon I\to \cup A_i$ such that $g(i)\in A_i$ for each $i$. So you could take the family $\{A_y\}_{y\in Y}$, with $A_y=f^{-1}(\{y\})$, and just verify that a function $g\colon Y\to \cup A_y$ that you obtain from the Axiom of Choice is a right inverse for $f$. This is going to be the best you can do, at least for arbitrary sets.
Your example of non-uniqueness suffices; though in general you can show that the function has multiple right inverses if and only if it is not injective, that is not required.
For (b), the forward direction is fine (since we have assumed $X\neq\varnothing$. I would say the backward direction is fine, though I would note that $x_0$ exists because we are assuming that $X$ is not empty. Again, your example of nonuniqueness is fine. One can prove that the left inverse is unique if and only if $f$ is bijective, but you are not required to do so.