Proof that "$f$ injective" and "$f$ possesses a recipracal" are equivalent

Question

Let $f\colon A\rightarrow B$ be a function, where $A$ and $B$ are unempty and finite sets.

Prove that:

$$\text{$f$ is injective}\quad\Longleftrightarrow\quad\text{$\exists f'\colon B\rightarrow A$ such that $f' \circ f=\operatorname{id}_A$}$$

---

I was loosely trying to prove this with erroneous reasoning because we know the following property, without any conclusion regarding to reverse implication:

$g\circ f$ is injective $\quad\Longrightarrow\quad$ $f$ is injective

What I need is only to prove existence of this $f'$. (It means that only the first side of the implications, concerning the existence.)

Though, I thought about a second proof, an alternative for a straight forward proof, which is the following:

---

Let $f\colon A\rightarrow B$ be injective.

Thus, we have the direct conclusion $\operatorname{Card}(f(A))=\operatorname{Card}A$, so that we can, without restriction, define any $f'\colon B\rightarrow f(A)$ such that we would have $f'\circ f=\operatorname{id}_{A}$, where we'd have $f'\circ f\colon A\rightarrow f(A)$. $\blacksquare$

---

Please show me:

• what properties must $f'$ possess -if particularly any?

• how I can prove this by using function's properties,

• if my second reasoning is right or wrong.

Thank you in advance

Answer 1

I found my answer today, thanks to hints you gave me before.

My complete proof is as follows:

---

$(\Rightarrow )$ First Side Implication:

Assume $f:A\rightarrow B$ injective.

1. Then we have: $Card(f(A)) = Card(A)$, e.g. $f(A)\subseteq B$.

And as $f$ is not surjective, then we strictly have $f(A) \ne B$. (Note that if $f$ were surjective too, then $f$ would become bijective and the conclusion would be trivial with ${ f }^{ \prime }={ f }^{ -1 }$).

Thus we have the strict inclusion as follows: $A = f(A)\subset B$

2. As we have -by injectivity- that for any $({ \alpha }_{ 1 },{ \alpha }_{ 2 })\in { A }^{ 2 }$ arbitrarily chosen, $f({ \alpha }_{ 1 })=f({ \alpha }_{ 2 })\Rightarrow { \alpha }_{ 1 }={ \alpha }_{ 2 }$.

Thus, we can, without any restriction, define a function $\varphi :B\rightarrow f(A)$ such that: $\varphi \circ f(\alpha )={ id }_{ A }$ for any $\alpha \in f(A)$. We would then have, in conformity with injection's definition:

$$\begin{cases} \varphi \circ f({ \alpha }_{ 1 })={ \alpha }_{ 1 }={ id }_{ A } \\ \varphi \circ f({ \alpha }_{ 2 })={ \alpha }_{ 2 }={ id }_{ A } \end{cases}\Rightarrow \varphi \circ f={ id }_{ A }$$

• So, we have a restricted function $\varphi$ with existence established and well constructed. But, as we have the strict inclusion with $A = f(A)\subset B$, then $B\setminus f(A)\neq \emptyset $.

So, we can obviously extend the definition of $\varphi$ by adding: $\forall \beta \in B\setminus f(A),\varphi (\beta )=\emptyset $

By this way, we proved not only that such a function exists, but we also constructed it: $\varphi = f^{ \prime }$

$(\Leftarrow )$ Reverse Implication:

Same reasoning would fit in this situation because if there exists such a function, then it couldn't be a surjection at all. We would prove it by contradiction over cardinals of $A$ and $B$: if $Card(A) \ge Card(B)$ then the identity function would -somehow- by hypothesis map at least one element of $A$ to another element.

As surjectivity-case is excluded, consequently we have the strict inclusion, and bijectivity-case is also disproved. (NOTE:the equality of $Card(A)$ and $Card(B)$ might though only be a particular case, but here, we even haven't that)

Consequently, we would conclude by saying that if such a function exists, it is injective. $\blacksquare $

Answer 2

Note that the question asks that $\ f' : B\to A$. The function you defined is $f' : B \to f(A)$. Since $f(A)\subset B$, your answer can not be the right answer! Plus, you did not actually define any function. You just stated that we can define a function $f'$ such that $f'\circ f = id$... without defining it.

Hint : Since $A$ is finite, $f(A)$ is finite. Suppose $x\in A$. What should the function $f'$ do to $f(x)$ so that $f'\circ f = id$ ? Once you figured that out, ask yourself why such a function $f'$ is well defined. In particular, does every $y\in B$ has an image ? If not, what can you do about it?

Answer 3

You are being asked to show that there is a function $f':B \rightarrow A$ such that $f'$ is a left inverse to $f$ i.e. $f' \circ f$ maps each $a \in A$ to itself.

The most direct way to show that $f'$ exists is to construct it. If $b$ is in the image of $f$ i.e. $b=f(a)$ for some $a \in A$ then you could define $f'(b) = a$, so that $(f' \circ f)(a) = f'(f(a)) = f'(b) = a$. This leaves you with two sub-problems:

(i) How can you be sure that this $f'$ is well defined ?

(ii) To complete the definition of $f'$, what value should you assign to $f'(c)$ where c is not in the image of A ?