Red Inverse, Blue Inverse, Left Inverse, Right Inverse

Question

1.) Prove that $f$ has a left inverse if and only if $f$ is injective.

2.) Prove that $f$ has a right inverse if and only if $f$ is surjective.

My first attempt for 1.):

$$f\text{ is injective.}$$ $$\iff$$ $$f(a)=f(b)\implies a=b$$ $$\iff$$ $$g(f(a))=g(f(b))$$

Try proving each direction of the if and only if statements separately. — Dan Rust, Aug 19 '13 at 17:32
@Ataraxia: It’s apparently a play on the first four lines of the children’s book One Fish, Two Fish, Red Fish, Blue Fish, by Dr. Seuss. (I prefer Cordwainer Smith’s ‘Think Blue, Count Two’, myself.) — Brian M. Scott, Aug 19 '13 at 17:40
Part 2) is answered in http://math.stackexchange.com/questions/440832/right-inverse-for-surjective-function?rq=1 — Avi Steiner, Aug 19 '13 at 17:43
@Loie: Dr. Seuss is not globally renowned. Please refrain from belittling people who are just trying to understand your post in order to help you better. — Cameron Buie, Aug 19 '13 at 19:30

score 1 · Answer 1 · answered Aug 19 '13 at 17:42

A left inverse is a transformation such that $A^LA=I$. A transformation is injective if and only if

$$A\vec{v}=A\vec{x}\to\vec{v}=\vec{x}$$

By counterexample, suppose that $A$ is not injective:

$$(\exists\vec{v})\,(\exists\vec{x})\,A\vec{v}=A\vec{x}\land\vec{v}\ne\vec{x}$$

$$A^LA\vec{v}=A^LA\vec{x}\implies{I}\vec{v}=I\vec{x}$$

This does not hold true in all cases if $A$ is not injective, so $A$ must be injective.

score 1 · Answer 2 · answered Aug 19 '13 at 18:04

The last line of your attempted proof comes out of nowhere: it makes no sense to make claims about a $g$ that you’ve not defined. You’d do better to separate the two halves of the argument. I’ll do the first one to give you a model of organization and leave the second to you.

Suppose that $f:X\to Y$ has a left inverse $g$. If $x_0,x_1\in X$ and $f(x_0)=f(x_1)$, then we can apply $g$ to $f(x_0)$ and $f(x_1)$ to find that $x_0=g\big(f(x_0)\big)=g\big(f(x_1)\big)=x_1$; since $x_0$ and $x_1$ were arbitrary elements of the domain of $X$, $f$ is injective.
Now suppose that $f:X\to Y$ is injective. Here it’s easiest to think of $f$ as a subset of $X\times Y$. Let $g=\{\langle y,x\rangle:\langle x,y\rangle\in f\}$. If $\langle y,x_0\rangle,\langle y,x_1\rangle\in g$, then $\langle x_0,y\rangle,\langle x_1,y\rangle\in f$ (or in more familiar notation, $f(x_0)=f(x_1)=y$), and since $f$ is injective, we must have $x_0=x_1$; this shows that $g$ is a function from some subset of $Y$ (namely, the range of $f$) to $X$. Now let $x\in X$ be arbitrary, and let $y=f(x)$; then $\langle x,y\rangle\in f$, so $\langle y,x\rangle\in g$, i.e., $g(y)=x$. Thus, $(g\circ f)(x)=x$, and since $x\in X$ was arbitrary, $g\circ f=\mathrm{id}_X$, and $g$ is a left inverse for $f$.

It’s also possible to prove the second direction without thinking of a function as a set of ordered pairs; it’s just a bit more informal.

Let $R=\{f(x):x\in X\}$, the range of $f$. For each $y\in R$ there is by definition an $x\in X$ such that $f(x)=y$. Suppose that $x_0,x_1\in X$ and $f(x_0)=f(x_1)=y$; then $x_0=x_1$ by the injectivity of $f$, so in fact there is a unique $x\in X$ such that $f(x)=y$; let $g(y)$ be this $x$. This defines a function $g:R\to X$, and it’s clear that for each $x\in X$ we have $g\big(f(x)\big)=x$, i.e., that $g$ is a left inverse for $f$.

Red Inverse, Blue Inverse, Left Inverse, Right Inverse

2 Answers2