Let $B$ be a finite, nonempty set and assume that $f : B \to A$ is a surjection. Prove that there exists a function $h : A \to B$ such that $f \circ h = I_A$ and $h$ is an injection. ($I_A$ is the identity of the set $A$).

This is my start, Since $B$ is finite, there exists a natural number $m$ such that $\mathbb N_m ≈ B$. This means there exists a bijection $k : \mathbb N_m \to B$. Now let $h = k \circ g$, where $g$ is the function...

I'm struggling to come up with a function for $g$ that allows $h$ to be an injection.

  • $\begingroup$ I added typesetting, but was unsure what you meant by $Nm$ and $\approx$. You may want to edit to clarify this. $\endgroup$ – Bungo Apr 18 '16 at 18:06
  • $\begingroup$ I don't know to make N (\doubleN) and use subscripts $\endgroup$ – Dr. Proof Apr 18 '16 at 18:09
  • $\begingroup$ Do you mean $\mathbb N_m$? Type \mathbb N_m to get this. Here is a typesetting tutorial for future reference. $\endgroup$ – Bungo Apr 18 '16 at 18:12
  • $\begingroup$ Huge help I appreciate the tutorial reference. $\endgroup$ – Dr. Proof Apr 18 '16 at 18:34

Actually it is not necessary for $B$ to be non-empty, and if AC is accepted then it is not necessary for $B$ to be finite either.

Since $f$ is surjective for every $a\in A$ the set $f^{-1}(\{a\})$ is not empty.

For every $a\in A$ choose an element $b_a\in B$ with $b_a\in f^{-1}(\{a\})$ (or equivalently with $f(b_a)=a$).

Now prescribe function $h:A\to B$ by $a\mapsto b_a$.

Then function $h$ is injective and $f\circ h$ is the identity on $A$.

If conversely $f\circ h$ is the identity on $A$ and $h(u)=h(v)$ then $u=f\circ h(u)=f\circ h(v)=v$ showing that $h$ is injective.

  • $\begingroup$ This answer completely misses the point of the exercise (induction). $\endgroup$ – Najib Idrissi Apr 18 '16 at 19:12
  • $\begingroup$ @NajibIdrissi I admit there is a good chance that the exercise was focused on induction ($B$ not empty and finite, and the start of the OP). But nowhere that was stated explicitly. It might be helpful for the OP. Let him/her be the judge of that. $\endgroup$ – drhab Apr 19 '16 at 7:16
  • $\begingroup$ It's not stated that you have to use induction because it's an exercise... Not all exercises hold your hand and tell you all the theorems you need to use. The fact that $B$ is finite is not random chance. $\endgroup$ – Najib Idrissi Apr 19 '16 at 7:25
  • $\begingroup$ @NajibIdrissi Efforts to convince me of that are not needed, as I allready made clear in my former comment. But if someone downvotes this for that reason then I disagree. Btw, as you can see the answer is accepted. That's not a justification of course, but it pleases me that apparantly the OP has made some advances in mathematics anyhow. $\endgroup$ – drhab Apr 19 '16 at 7:42
  • $\begingroup$ I downvoted your answer for this, yes. When accepting your answer, the OP may not have even realized that this wasn't the answer their instructor wanted. $\endgroup$ – Najib Idrissi Apr 19 '16 at 7:44

If you enumerate the elements of $B$ as $b_1, \ldots, b_n$, you can let $h(a) = b_m$ where $m$ is the least $i$ such that $f(b_i) = a$.

  • $\begingroup$ So by using the recursive definition f is surjective? $\endgroup$ – Dr. Proof Apr 18 '16 at 19:03
  • $\begingroup$ What do you mean? The problem stated that $f$ is a surjection. $\endgroup$ – Robert Israel Apr 18 '16 at 19:07

It is a basic result in elementary set theory that, if $f\circ h$ is injective, then $h$ is injective. If it is surjective, then $f$ is surjective. And the identity is both…

  • $\begingroup$ This doesn't explain how to construct $h$. $\endgroup$ – Najib Idrissi Apr 18 '16 at 19:13

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.