An Injective Tango! (Schroeder-Bernstein Theorem)

Now there’s a simple theorem in set theory whose proof has always appeared a bit cloudy to me, since I’ve never been able to find it written in a straightforward manner. This theorem is the Schroeder-Bernstein Theorem, whose statement is utterly intuitive:
Schroeder-Bernstein Theorem:
Let A and B be sets. If there exists an injection f: A \to B, and an injection g: B \to A , then |A|=|B| . That is, the two sets have the same cardinality.

 

To see just how intuitive this is, let the two sets in question be finite. In this case it’s clear that the sets are in bijection, for if not, we could not have the two given injections! Test this yourself with a couple of examples.

 

The case in which the sets are infinite is not so simple. In fact, the proof of the theorem is difficult because of these infinite sets. For example, if A = \mathbb{N}, andB = \mathbb{Q^+}, f: n \mapsto \frac{n}{2}g: \frac{p}{q} \mapsto 2^p3^q. Well clearly here there are elements on each side of the set that are not in the image of either injection.

 

So what are we to do? How do we prove that \mathbb{N} is in bijection with the positive rational numbers? One proof of the S-B Theorem feels to me like a sort of dance between the two sets, a tango if you will. Accordingly, I’ve written a little analogy that will precede the proof, using minimal symbols, to elucidate the general idea before transcribing the proof into symbols.

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 C_0 , and we assign to them the women that they drew as their unique dancing partner, call them B_0 . (unique because nobody drew them)

But wait! Now what about the men drawn by the women in B_0 ? (call them C_1 ) 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 B_1 .

And so if we keep doing this, letting C_n be B_{n-1}‘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 C_n ‘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 C_0 = A \setminus g(B) . Let h = g \circ f . Let C_1 = h(C_0). Inductively, let C_{n+1} = h(C_n).

Then, we denote C =C_0 \cup \left( \bigcup \limits_{ n \in \mathbb{N}} C_n \right) . (note these are all the men in Georg’s situation).

Now, we would like to note two things:

  1. C = C_0 \cup h(C)
  2. A \setminus C = g(B \setminus f(C))

(note that A \setminus C 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 h to C . To prove (2), show that if x \in A \setminus C , then x is in the image of g , but is not in the image of f(C) , using (1). Then show the converse: if x \in g(B \setminus f(C) , it is not in C .

With these two fact established, we have enough information to form our bijection. (2) tells us that we can assign to the elements of A \setminus C , their inverse image under g . In the collection C , we assign to them their original image under f . (look at the analogy here).

Our desired bijection \phi : A \to B is thus given by \phi(x) = f(x) if x \in C , and \phi(x) = g^{-1}(x) if x \in A \setminus C .


 

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.

Cheers,

J.T.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s