Schroeder-Bernstein Theorem:Let and be sets. If there exists an injection , and an injection , then . That is, the two sets have the same cardinality.
The Mathematician’s Tango
Suppose you’re scheduling a weekly tango in a universe with infinitely many mathematicians. In this tango, each male mathematician will be paired up with a female mathematician as dancing partners.
Now we take a two big hats with infinitely many numbers and we tell the men to pick a number from one and the women to pick a number from the other to assign them each a dancing partner. But since there are infinitely many numbers in both hats, it may happen that not all the numbers in each hat are chosen. Say, Georg picks “14” and is assigned Emily, but Emily picks “984” and is assigned Tim.
What are we to do? Now neither Georg nor Tim know if Emily should be their dancing partner, but we need unique partners!
This is what we do: we take all the men that weren’t drawn by any of the women call them , and we assign to them the women that they drew as their unique dancing partner, call them . (unique because nobody drew them)
But wait! Now what about the men drawn by the women in ? (call them ) well since they’re no longer in a situation like Georg, (note they all were before we reassigned), we can just uniquely give them the woman whose number they drew, call this set .
And so if we keep doing this, letting be ‘s original drawing of men, we will eventually remedy every man in a situation like Georg, by giving him his original draw.
Thus we have two types of situations, the ones like Georg’s, which are the men in the ‘s and the ones where the man drew the woman and the woman drew the same man. In this case, just match the woman to her original draw, which is unique.
There you have it, a bijection. Every male now has a unique female dancing partner, and every female now has a unique dancing partner!
The Formal Proof of the Tango
If the analogy doesn’t sit well with you yet, read it over a few times before reading the formal proof. If it still doesn’t sit well, draw pictures of the two sets, represented by dots, and then draw the arrows back and forth between the sets in the way described until you see the idea.
Here’s the formal proof, written succinctly since the idea is in the analogy:
Let . Let . Let . Inductively, let .
Then, we denote . (note these are all the men in Georg’s situation).
Now, we would like to note two things:
(note that are all the men in the situation that the man drew the woman and the woman drew the same man.)
The proof of (1) is simple, and is seen by just applying to . To prove (2), show that if , then is in the image of , but is not in the image of , using (1). Then show the converse: if , it is not in .
With these two fact established, we have enough information to form our bijection. (2) tells us that we can assign to the elements of , their inverse image under . In the collection , we assign to them their original image under . (look at the analogy here).
Our desired bijection is thus given by if , and if .
This concludes the proof of Schroeder-Bernstein. I hope the analogy assisted the understanding of the formal proof, which is usually quite muddled by symbols. As a last remark, note that the theorem still works for uncountable cardinalities, but the analogy I’ve given is for a countable number of mathematicians. This analogy was given only for simplicity.