The Schröder–Bernstein theorem

I decided that my first blog post should be about something that gave me the ‘wow’ feeling - and I immediately knew that it has to be the Schröder–Bernstein theorem. The proof of this theorem was skipped in the lecture (as an exercise :P) and I was waiting for the lecture to get over to try the proof. After hours of failed attempts, I thought I might be missing something trivial and decided to google it. I am a fan of elegant proofs and this theorem has been close to my heart ever since. Okay, let's cut the drama and jump straight into the theorem.

Theorem: Let $A,B$ be any sets. If there are injective functions $f: A \rightarrow B$ and $g: B \rightarrow A$ then there exists a bijection $h: A \rightarrow B$.

Before going into the proof, I would like to introduce you to an alternate restatement of this theorem. This is not used in the proof and can be skipped.

Let us first fix the following terminologies.

The Schröder–Bernstein theorem can now be restated as follows:

Theorem (restated): For any sets $A,B$ if $|A| \leq |B|$ and $|B| \leq |A|$ then $|A| = |B|$.

Let us do an easy special case first. Say $A = \{a_1,\ldots,a_n\}$ and $B = \{b_1, \ldots,b_k\}$ be finite sets with injections $f: A \rightarrow B$ and $g: B \rightarrow A$. If $f(A) = B$, we are done as $f$ is a bijection as well. We now argue that if $f(A) \subsetneq B$ then there can not exist any injection from $B$ to $A$which is a contradiction. Since $f$ is an injection, $f(a_i) \neq f(a_j)$ whenever $i \neq j$, meaning $B$ can be written as $B = \{ f(a_1),\ldots,f(a_n),b_{n+1},\ldots, b_k \}$. As $k > n$, by pigeonhole principle there can not exist an injection from $B \rightarrow A$.

The above proof idea does not carry over to the case when $A$ and $B$ are not finite. There are various proofs of this theorem. The proof presented in this post is based on what I read from here (although I have used my own terminologies and visualized this as a graph).

Construct a directed graph $G(V,E)$ as follows:

.

It follows from the injectivity of $f$ and $g$, that both the indegree and outdegree of any vertex in this graph is atmost 1. So chains that have branches (as shown in the following diagrams) can not exist.

Hence the graph $G$ consists of disjoint components each of which is either a cycle or an infinite chain.

An infinite chain can either start with a vertex from set $A$ (that is a blue vertex) or a vertex from set $B$ (a pink vertex). Let us call them blue chains and pink chains respectively. Observe that the first element of each pink chain do not have an incoming edge and these are precisely those elements in $B$ that does not have a pre-image with respect to $f$.

We are now ready to define our bijection $h: A \rightarrow B$. Since all pink elements in cycles and blue chains have an incoming edge, $h$ mimics $f$ for the blue elements in these components.

However on pink chains, $h$ maps each blue element to its parent vertex in the graph $G$.

More formally $h: A \rightarrow B$ is defined as

Let us verify that $h$ is indeed a bijection. First of all, $h$ is a valid function as $h$ is defined on all blue vertices and each blue vertex has out-degree 1. Further, each pink vertex has in-degree exactly equal to 1 implying $h$ is a bijection. That's all - we are done 🙂

Aside: Observe that if $A$ and $B$ were finite sets then all the components are cycles!

Remarks