1

Consider the function $f: \mathbb{R} \to \mathbb{R}^{\geq 0}$ defined by $f(x) = x^2$ for all $x \in \mathbb{R}$. $f$ is surjective, because for all $x \in \mathbb{R}^{\geq 0}$ we have $f(\sqrt{x}) = x$, as every non-negative real number has a square root. However, $f$ is not injective, because we have $f(1) = f(-1) = 1$ where $1 \neq -1$.

I then observed that $f$ had multiple right inverses (a right inverse of a function $f: X \to Y$ is a function $g: Y \to X$ such that $f \circ g = id_Y$, which is the identity function on $Y$), such as:

  • Define $g: \mathbb{R}^{\geq 0}$ by $g(x) = \sqrt{x}$. $g$ is a right inverse, because $(f \circ g)(x) = f(g(x)) = f(\sqrt{x}) = (\sqrt{x})^2 = x$.
  • Define $g: \mathbb{R}^{\geq 0}$ by $g(x) = -\sqrt{x}$. $g$ is a right inverse, because $(f \circ g)(x) = f(g(x)) = f(-\sqrt{x}) = (-\sqrt{x})^2 = x$.

In general, I have been able to find multiple right inverses for all the surjective but not injective functions I have tested. I want to prove or disprove that all functions $f: X \to Y$ where $f$ is surjective and not injective, have multiple right inverses.

My current idea is that because $f$ is not injective, there exists some $y \in \mathbb{R}$ where $f(x_0) = f(x_1) = y$ for $x_0, x_1 \in \mathbb{R}^{\geq 0}$ where $x_0 \neq x_1$. Thus, we can have two right inverses, one of which takes $y$ to $x_0$, and the other of which takes $y$ to $x_1$.

However, I don't think this is formal enough. Can someone provide a formal proof of the assertion above?

i_will_solve_the_riemann_hyp
  • 11

2 Answers2

2

Theorem. Let $f\colon X\to Y$ be a function.

  1. Assuming that $X$ has at least two elements, if $f$ is injective but not surjective, then $f$ has more than one left inverse.
  2. Assuming the Axiom of Choice, if $f$ is surjective but not injective, then $f$ has more than one right inverse.

Proof. For 1, let $x_1,x_2\in X$, $x_1\neq x_2$. Let $h_1,h_2\colon Y\to X$ be defined by $$h_i(y) = \left\{\begin{array}{ll} x &\text{if }y\in f(X), f(x)=y,\\ x_i&\text{otherwise}. \end{array}\right.$$ Note that $h_i$ is well defined, since $f$ is one-to-one; hence if $y\in f(X)$, then there exists a unique $x$ such that $f(x)=y$.

To see that $h_1\neq h_2$, let $y\in Y\setminus f(X)$; such a $y$ exists since $f$ is assumed to not be surjective. Then $h_1(y)=x_1\neq x_2=h_2(y)$. Thus, $h_1\neq h_2$.

To verify that the $h_i$ are both left inverses of $f$, let $x\in X$. Then $f(x)\in f(X)$, so $h_i\circ f(x) = h_i(f(x)) = x$ for $i=1,2$. Thus, $f$ has more than one left inverse.

(We need $|X|\gt 1$, as otherwise there is only one function $g\colon Y\to X$, which is of course a right inverse of $f$, whether $f$ is surjective or not).

For 2, assume the Axiom of Choice. Since $f$ is not one-to-one, there exists a $y_0\in Y$ and $x_1\neq x_2$ in $X$ such that $f(x_1)=f(x_2)=y_0$. For each $y\in Y\setminus\{y_0\}$, using the Axiom of Choice select $x_y\in X$ such that $f(x_y)=y$. Define $g_1,g_2\colon Y\to X$ by $$ g_i(y) =\left\{\begin{array}{ll} x_i &\text{if }y=y_0,\\ x_y&\text{otherwise.} \end{array}\right.$$ To verify that $g_1\neq g_2$ note that $g_1(y_0)=x_1\neq x_2=g_2(y_0)$. To verify that $g_i$ is a right inverse of $f$, note that for $y\in Y$, if $y\neq y_0$ then by construction $f(x_y)=y$, so $f\circ g_i(y) = f(x_y) = y$. And $f\circ g_i(y_0) = f(x_i) = y_0$. Thus, $g_1$ and $g_2$ are right inverses of $f$, so $f$ has at least two right inverses. $\Box$

(Sometimes I joke that the dual of the Axiom of Choice is "the domain is nonempty", because while "every surjection has a right inversse" requires one to assume the Axiom of Choice, the dual statement "every injection has a left inverse" requires one to assume the domain is nonempty; here we see that "the domain has at least two elements" plays the dual role to the Axiom of Choice when switching from "surjective" to "injective"...)

Arturo Magidin
  • 398,050
1

The existence of right inverses for surjective functions requires the axiom of choice.

Once you have a right inverse $g:Y\to X$ for $f,$ if $f$ is not injective i.e. if there exists some $y \in Y$ such that $f(x_0) = f(x_1) = y$ for distinct $x_0,x_1 \in X,$ you can define another right inverse $h$ by: $h(t)=g(t)$ if $t\ne y$ and $h(y)=x_0,$ assuming wlog $g(y)\ne x_0.$

Anne Bauval
  • 34,650