2
$\begingroup$

Let $f:A\to B$

Prove the map $f$ is injective iff it has a left inverse.

Starting with $f$ is injective

Let $A$ not be $ \varnothing$

$f(A) = \{b \in B \ | \ b = f(a) \text{ for some } a \in A\}$

If there is a map $g: B \to A$ defined by $g(B) = \{a \in A \ | \ a = g(b)\text{ for some } b \in B\}$ where $b = f(a)$

The composite function $g \circ f(a): a \to f(a) \to a$ returns the identity on $A$ and is thus a left inverse.

$g$ does not exist in this definition if $g(b_i) \neq a_i$ for some $i$ denoting an element of $A,B$, which makes it the nullset

Or

$g(b_i) = a_i = a_{i+x}$ two or more elements of $A$ share an element of $B$ in the mapping of $f: A \to B$ It cannot be true because $a_i \neq a_{i+x}$ implies $f(a_i) \neq f(a_{i+x})$

$\endgroup$
10
  • 8
    $\begingroup$ The statement is actually incorrect. $f\colon\varnothing\to\{\star\}$ is injective, but has no left inverse. You need to assume $A\neq\varnothing$. $\endgroup$
    – Arturo Magidin
    Sep 8, 2021 at 20:27
  • 2
    $\begingroup$ You seem to be assuming your sets are finite. You should not. The assertion that if $f$ is injective then $|A|\leq|f(A)|$ is immediate by the definition of cardinality. "Since the domain is less than or equal to the codomain" is incoherent. Sets are not "less" or "more" than other sets. "Each element of $A$ maps to exactly $1$ or more elements in $f(A)$". Just one: because $f$ is a function; it has nothing to do with cardinalities or sizes. You need the right inverse to be defined in all of $B$, not just $f(A)$. Your explanation is insufficient, IMHO. And you only tried one direction. $\endgroup$
    – Arturo Magidin
    Sep 8, 2021 at 20:30
  • $\begingroup$ That is, you only tried to show that if $f$ is injective then it has a left inverse (but haven't quite managed it). You did not even try to show that if $f$ has a left inverse, then it is injective. Yet the statement you are trying to establish says "iff", which is (in my opinion pernicious, but often used) short of "if and only if". You tried the "only if" direction, but haven't even gotten started on the "if" direction. $\endgroup$
    – Arturo Magidin
    Sep 8, 2021 at 20:32
  • $\begingroup$ @ArturoMagidin I edited my answer, is this more of what you're looking for? $\endgroup$
    – Ronald Villiers
    Sep 8, 2021 at 21:24
  • $\begingroup$ So... What's the question? $\endgroup$
    – David
    Sep 8, 2021 at 21:26

2 Answers 2

Reset to default
2
$\begingroup$

Let $f$ be injective. We construct a left-inverse for $f:A\to B$.

Let $a\in A\neq\emptyset$ be an arbitrary element.

Now take $g: B\to A$, $b\mapsto \begin{cases} f^{-1}(b),\text{if $b\in\mathrm{Im}f$}\\ a,\text{else}\end{cases}$.

Where $f^{-1}(b)$ notes the single element of $f^{-1}(\{b\})$, as justified further below.

This function is well-defined, as every element $b\in B$ has an image in $A$, and the image is unique, so $b$ does not get mapped onto several different elements in $A$. Here the assumption that $f$ is injective comes in, as this implies that every element in the image of $f$ has exactly one preimage. So $f^{-1}(b)$ (which is the set (not to confuse with a function) of all elements in $A$ with $f(a)=b$).

Now we have $g(f(a))=a$ for every $a\in A$, as $f(a)$ clearly is an element in $\mathrm{Im}f$ (image of $f$).

So $g$ is a left-inverse of $f$.

For the converse:

Let $g$ be a leftinverse of $f$. We have to show that $f$ is injective.

So let $f(a)=f(a')$. We have to show that $a=a'$.

We have $g(f(a))=a$, as $g$ is a leftinverse. Also we get $g(f(a'))=a'$ for the same reason.

But $a=g(f(a))\stackrel{f(a)=f(a')}{=}g(f(a')=a'$. So $f$ is indeed injective.

$\endgroup$
3
  • $\begingroup$ It seems like begging the question if you say you are "constructing a left inverse for $f$", and use the notation $f^{-1}$ in the definition, given that by definition "$f^{-1}$" is supposed to represent the two-sided inverse of $f$ (when it exists). Worse when you then say that $f^{-1}(b)$ is "the set", because then $g$ takes values in $A\cup P(A)$, not $A$. You should either first define the symbol, or better yet define $g$ by saying that $b$, in the case when $b\in \mathrm{Im}(f)$, is mapped to $a$ where $f(a)=b$. The fact that $f$ is injective yields that this is well-defined. $\endgroup$
    – Arturo Magidin
    Sep 8, 2021 at 20:49
  • $\begingroup$ If you are trying to use the induced function on subsets, note that the induced function from $P(B)$ to $P(A)$ takes subsets of $B$ as arguments, not elements. So if you want to define $g(b)$ as the unique preimage of $b$, then the proper notation would be that it is the unique element of $f^{-1}(\{b\})$, not $f^{-1}(b)$. $\endgroup$
    – Arturo Magidin
    Sep 8, 2021 at 20:51
  • $\begingroup$ I agree, that the notation might lead to confusion. I wanted to avoid naming the left inverse $f^{-1}$. I am aware that the proper notation would be $f^{-1}(\{b\})$. I have pointed that out, that this is supposed to be a set, as I feel like writing the set as an argument is an overkill, and normally one abuses notation in the case of a singleton. Nevertheless I agree with your critique, as this answer is supposed to be as understandable as possible for a beginner, and I will change the notation. $\endgroup$
    – Cornman
    Sep 8, 2021 at 20:54
2
$\begingroup$

Say $f$ is injective. Then for any $a, b$ in the domain of $f$, we have $f(a) = f(b) \implies a = b$. Thus, "the element that maps onto $x$" is uniquely defined for any $x$ in the codomain of $f$. Call this element $f^{-1}(x)$ - we see clearly that $f^{-1}(f(x)) = x$, so we have a well-defined left-inverse.

Say $f$ has a left-inverse $f^{-1}$. Let $f(a) = f(b)$. Applying $f^{-1}$ to both sides, we get $a = b$ (we know the left-inverse must be injective, or else $f$ would not be well-defined). Thus $f$ is injective.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .