0
$\begingroup$

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))$$

$\endgroup$
  • 2
    $\begingroup$ The color names in the title confuse me. $\endgroup$ – Git Gud Aug 19 '13 at 17:32
  • $\begingroup$ Try proving each direction of the if and only if statements separately. $\endgroup$ – Dan Rust Aug 19 '13 at 17:32
  • $\begingroup$ What are the colors?? $\endgroup$ – Ataraxia Aug 19 '13 at 17:33
  • 3
    $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Aug 19 '13 at 17:40
  • 1
    $\begingroup$ @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. $\endgroup$ – Cameron Buie Aug 19 '13 at 19:30
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.