4
$\begingroup$

This question already has an answer here:

I am trying to prove this (it looks true to me) :

Let $A,B $ be two sets. If there is a surjection $A\to B $ and a surjection $B\to A$ then $A $ and $B $ are in bijection.

I showed that is it equivalent to the following statement :

If there is an injection $A\to B $ and an injection $B\to A$ then $A $ and $B $ are in bijection.

But I am stuck, I don't see how to prove either.

$\endgroup$

marked as duplicate by Winther, José Carlos Santos, Asaf Karagila set-theory Oct 4 '17 at 21:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Ho w did you show the equivalence to the statement involving injections? $\endgroup$ – Andrés E. Caicedo Oct 4 '17 at 17:07
  • 1
    $\begingroup$ If we have a surjection $f:A\to B $ then, for each $b \in B $ we can (via the axiom of choice) choose an element $a\in f^{-1}(b) $. Then we have an injection $g:B\to A $ by defining $g (a)=b $ (we do that for every $b $). $\endgroup$ – Friedrich Oct 4 '17 at 17:11
1
$\begingroup$

The assertion that if there are injections $A \leftrightarrows B$ then there is a bijection $A \to B$ is the Cantor–Schröder–Bernstein and has a reasonably involved proof—involved enough that I doubt you'd reasonably be expected to prove it yourself.

Every surjection $f : A \to B$ has a right inverse $r : B \to A$, i.e. a function such that $f(r(b))=b$ for all $b \in B$, and this right inverse is injective. You have (in the comments to your question) correctly constructed such a right inverse and identified that it is injective, and so the result follows from the Cantor–Schröder–Bernstein theorem... that is, if you're allowed to assume it.

$\endgroup$
  • $\begingroup$ Thank you! I didn't knew it was a famous theorem. $\endgroup$ – Friedrich Oct 4 '17 at 17:16
  • 1
    $\begingroup$ It should be noted that the existence of the right inverse is equivalent to the axiom of choice, while the Cantor–Schröder–Bernstein theorem can be proved without it. $\endgroup$ – Professor Vector Oct 4 '17 at 17:20
  • $\begingroup$ Clive Newstead-- I don't only do what I'm expected to do :) $\endgroup$ – Friedrich Oct 4 '17 at 17:26

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