0
$\begingroup$

Let A be a non-empty set and $f : A → A$ be a function.

Prove that f has a left inverse in $F_{A}$ if and only if f is injective (one-to-one).

$\leftarrow$ assume f is injective then $\forall x\in A \space \space \space \space \space \space \space \space \space f(x) \in A $ such that if $f(x)=f(y) $ then $ x=y$

something something $g(f(x)) = x \space \space \space \space \forall x\in A$

$\rightarrow$ assume f has a left inverse in $F_{A}$ then $\forall x\in A$

$g(f(x)) = x$ something says that x must be one to one?

Im really confused by this question First of all f must be a bijection if it is one to one from $ A \to A $ is it not?

Can someone help me out with this proof?

$\endgroup$
  • 1
    $\begingroup$ Are any functions $f : \{0\} \to \{1, 2\}$ one-to-one? Are they bijections too? Could you write down any left inverses for any of these one-to-one functions? $\endgroup$ – pjs36 Jan 16 '17 at 4:33
  • $\begingroup$ What is $F_A{}$? $\endgroup$ – Eric Wofsey Jan 16 '17 at 4:34
  • $\begingroup$ it has a left inverse not a bijection not one to one. $\endgroup$ – Faust Jan 16 '17 at 4:34
  • $\begingroup$ $F_{A}$ is the set of functions that map A to A $\endgroup$ – Faust Jan 16 '17 at 4:35
  • $\begingroup$ Possible duplicate of Left inverse iff injective; right inverse iff surjective $\endgroup$ – Javier Apr 8 at 13:57
2
$\begingroup$

Suppose $f$ has a left inverse $g$.
Suppose $f(x)=f(y)$ for some $x,y\in A$.
Then $gf(x)=gf(y)$.
Since $gf=i_A$, we have $x=y$ and hence $f$ is injective.

Suppose $f$ is injective. Let $a_0$ be a fixed element in $A$.
Define $g:A\rightarrow A$ by the rules:
For $x\in A$
(i) If there is an element $y\in A$ such that $f(y)=x$, then $g(x)=y$.
(ii) If no such element $y$ exists in $A$, then $g(x)=a_0$.

For case (i), the element $y$ is unique as if $g(x)=y_1$ and $g(x)=y_2$, then $f(y_1)=x=f(y_2)$ which implies $y_1=y_2$.
For case (ii), $g(x)=a_0$ is also unique by the way we define it.
So $g$ is a function from $A$ to $A$.

For $a\in A$, $gf(a)=a$ as $f(a)=x\in A$ implies $g(x)=a$ by (i).
Hence $g$ is a left inverse of $f$.

$\endgroup$
  • $\begingroup$ ii) was the hard side. $\endgroup$ – Faust Jan 16 '17 at 4:45
  • $\begingroup$ $\forall y \in A g(f(y))=x $ so g compose f is the same as $ I (y) \forall y \in A$ $\endgroup$ – Faust Jan 16 '17 at 4:47
  • $\begingroup$ @Faust7 for all $y\in A$, $gf(y)=y$, so $gf=i_A$, the identity function from $A$ to $A$. $\endgroup$ – Alan Wang Jan 16 '17 at 4:51
  • $\begingroup$ Yes that was what i was trying to say but couldn't :( Thank you very much your explanation was flawless. $\endgroup$ – Faust Jan 16 '17 at 4:51
1
$\begingroup$

First of all, a one-to-one set function $f: A \to A$ certainly need not be a bijection; consider the multiplication by two map $\times 2: \mathbb{Z} \to \mathbb{Z}$. This is injective, but no odd numbers are in the image.

Now for your main question, assume $f$ is injective. Then define a left inverse $g$ by setting $g(x) = f^{-1}(x)$ wherever $f^{-1}(x)$ is defined. Because $f$ is injective, there is only one possible value for $f^{-1}(x)$, whenever it exists. Thus, $g$ is a left inverse of $f$ (because $g(f(x)) = x$ by definition). In the other direction, suppose that $g$ is a left inverse to $f$, i.e. for all $x \in A$, $g(f(x)) = x$. Now suppose that $f(x) = f(y)$. Applying $g$ to both sides, we see that $g(f(x)) = g(f(y))$, and since $g$ is a left inverse, this gives $x = y$. Thus $f$ is injective.

$\endgroup$
0
$\begingroup$

Each of the two answers in this article have flaws in their proofs that every injective function has a left inverse, so here we set the record straight.

The accepted answer doesn't account for the fact that $A$ might be empty (this is really hair splitting). The answer by Reuben Stern only constructs a left inverse when the function $f$ is a bijection.

If $f: A \to A$ is injective, the converse relation $f^{-1}$ will define a bijective function

$$ f^{-1}: f(A) \to A$$

satisfying $f^{-1} \circ f = id_A$.

If $f(A) = A$ then $f^{-1} \in F_A$ and we are done.

If $f$ is not surjective let $a_0 \in A \setminus f (A)$ and define the function $g: A \to A$ by

$g(a) = \left\{\begin{array}{lr} f^{-1}(a)\, \;\;\;\text{ |} & \text{for } a \in f(A)\\ a_0 \quad \quad \,\,\;\; \text{ |} & \text{for } a \in A \setminus f (A) \end{array}\right\}$

It is easily checked that $g \circ f = id_A$.

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