4
$\begingroup$

I'm trying to prove $|A| = |B|$, and I have two injective functions $f:A \to B$ and $g:B \to A$. Is this enough proof for a bijection, which would prove $|A| = |B|$? It seems logical that it is, but I can't find a definitive answer on this.

All I found is this yahoo answer:

One useful tool for proving that two sets admit a bijection between them is a theorem which says that if there is an injective function $f: A \to B$ and an injective function $g: B \to A$ then there is a bijective function $h: A \to B$. The theorem doesn't really tell you how to find $h$, but it does prove that $h$ exists. The theorem has a name, but I forget what it is.

But he doesn't name the theorem name and the yahoo answers are often unreliable so I don't dare to base my proof on just this quote.

$\endgroup$
  • 1
    $\begingroup$ It's called en.wikipedia.org/wiki/… an wikipedia lists some proofs ... AB, $\endgroup$ – martini Mar 20 '12 at 13:43
  • $\begingroup$ @Roy T.: Most proofs of Cantor-Bernsein construct a bijection $h$ explicitly from $f$ and $g$. $\endgroup$ – André Nicolas Mar 20 '12 at 13:56
  • $\begingroup$ Thanks Martini and André, this is exactly what I was looking for. $\endgroup$ – Roy T. Mar 20 '12 at 14:00
10
$\begingroup$

Yes this is true, it is called Cantor–Bernstein–Schroeder theorem.

$\endgroup$
  • $\begingroup$ Hey, this is exactly the sort of confirmation I was looking for. Thanks! $\endgroup$ – Roy T. Mar 20 '12 at 14:00

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.