Theorem 4.8.3 shows that `$\le$', as applied to infinite cardinal numbers, has some familiar properties, that is, some properties of `$\le$' in more familiar settings, like the integers. Another property that we rely on when dealing with $\Z$ or $\Q$ or $\R$ is anti-symmetry: if $x\le y$ and $y\le x$ then $x=y$. It is far from obvious that the ordering of the infinite cardinals obeys this rule, but it does.
Theorem 4.9.1 (Schröder-Bernstein Theorem) If $\overline{A}\le \overline{B}$ and $\overline{B}\le \overline A$, then $\overline A=\overline B$.
Proof. We may assume that $A$ and $B$ are disjoint sets. Suppose $f\colon A\to B$ and $g\colon B\to A$ are both injections; we need to find a bijection $h\colon A\to B$. Observe that if $a$ is in $A$, there is at most one $b_1$ in $B$ such that $g(b_1)=a$. There is, in turn, at most one $a_1$ in $A$ such that $f(a_1)=b_1$. Continuing in this way, we can find a string of "ancestors'' of $a$: $$ a=a_0,b_1,a_1, b_2,a_2, b_3, a_3, … $$ such that $g(b_{n})=a_{n-1}$ and $f(a_{n})=b_n$. Call this the lineage of $a$. Of course, any $b\in B$ also has a lineage. Note that the lineage of $a\in A$ consists of just itself if $a$ is not in the image of $g$; likewise, an element $b\in B$ might have no ancestors other than itself.
The lineage may take three forms: it may be infinite; it may end at some term $a_k$ or $b_k$, if $a_k$ is not in the image of $g$ or $b_k$ is not in the image of $f$; or it may "wrap around'' to the beginning, if $a_k=a$ for some $k>0$. If a lineage ends with a term $a_k$, $k\ge 0$, we say it ends in $A$. Let $A_A$ and $B_A$ be the subsets of $A$ and $B$, respectively, consisting of those elements whose lineage ends in $A$.
Claim 1 If $f(a)=b$, then $a\in A_A$ iff $b\in B_A$. To see this, observe that the lineage of $b$ is $$ b,a, b_1,a_1, b_2,a_2, b_3, a_3, … $$ i.e., to get the lineage of $b$, just add it to the lineage of $a$. Now it is clear that if the lineage of $a$ ends in $A$, so does the lineage of $b$. Suppose that the lineage of $b$ ends in $A$. The lineage of $b$ must then include $a$, and so the lineage of $a$ ends in $A$ also.
Now define $\hat f\colon A_A \to B_A$ by $\hat f(a) = f(a)$ (i.e., $\hat f(a)$ is $f$ restricted to $A_A$, and with a different codomain.).
Claim 2 $\hat f$ is a bijection. Since $f$ is an injection, it follows easily that $\hat f$ is an injection. To show $\hat f$ is surjective, suppose $b\in B_A$. Since the lineage of $b$ ends in $A$, $b$ must be in the image of $f$. So there is an $a\in A$ such that $f(a)=b$. Since $b\in B_A$, by claim 1, $a\in A_A$. Therefore, $\hat f(a)=b$ for some $a$ in $A_A$, and $\hat f$ is surjective.
We outline a parallel construction and leave the details for the exercises. ${A_A}^c$ (the complement of $A_A$ in $A$) and ${B_A}^c$ consist of those elements whose lineage does not end in $A$.
Claim $1'$ If $g(b)=a$, then $b\in {B_A}^c$ iff $a\in {A_A}^c$ (exercise 4).
Claim $1'$ allows us to define $\hat g\colon {B_A}^c \to {A_A}^c$, where $\hat g(b)=g(b)$ for any $b\in {B_A}^c$.
Claim $2'$ $\hat g$ is a bijection (exercise 5).
The theorem follows from claims 2 and $2'$: define $h\colon A\to B$ by the formula, $$ h(a)=\cases { \hat f(a); & if $a\in A_A$, \cr \hat g^{-1}(a); & if $a\in {A_A}^c$.\cr} $$ It is straightforward to verify that $h$ is a bijection (exercise 6). $\qed$
It is sometimes tempting to react to a result like this with, "Of course! How could it be otherwise?'' This may be due in part to the use of the familiar symbol `$\le$'—but of course, just using the symbol hardly guarantees that it acts like `$\le$' in more familiar contexts. Even paying attention to the new meaning, this theorem may seem "obvious.'' Perhaps the best way to see that it might not be so obvious is to look at a special case, one in which the injections $f$ and $g$ are easy to find, but there does not seem to be any "obvious'' bijection. See exercise 8.
Example 4.9.2 Suppose $D=\{\,(x,y): x^2+y^2\le 1\,\}$ is the unit disc in the plane and $S$ is the square $\{\,(x,y):-1\le x,y\le 1\,\}$. Since $D\subseteq S$, $\overline D\le \overline S$. The map $f\big((x,y)\big)=(x/2,y/2)$ is an injection $S\to D$, so $\overline S\le \overline D$. By the Schröder-Bernstein Theorem, $\overline S=\overline D$. (So it is possible, after all, to fit a square peg in a round hole!) $\square$
Felix Bernstein. Bernstein (1878–1956) studied under Cantor in Halle, and under Hilbert and Klein in Göttingen. It was in 1895 or 1896, while an undergraduate, that he proved the equivalence theorem for sets. Cantor had been working on the problem, but left for a holiday. In his absence, Bernstein was proof-reading one of Cantor's books; the idea for his proof of the equivalence theorem came to him one morning while he was shaving. Cantor later worked for several years to refine the proof to his satisfaction, but always gave full credit for the theorem to Bernstein.
After taking his undergraduate degree, Bernstein went to Pisa to study art. He was persuaded by two professors there to return to mathematics, after they heard Cantor lecture on the equivalence theorem. Bernstein remained interested in the arts, especially sculpture and painting, for the rest of his life.
Bernstein received his Ph.D. at Göttingen in 1901, and after some time in Halle became associate professor of mathematical statistics at Göttingen.
Bernstein was a versatile mathematician, working in both pure and applied mathematics. He was one of the first mathematicians to apply set theory to other branches of mathematics. By the 1920s, he had become interested in mathematical genetics, and made important contributions in population genetics. Most notable was his successful explanation of the inheritance of blood type, based on a set of three alleles.
In the 1930s, Bernstein emigrated to the United States, and became a citizen in 1940. He taught at Columbia, NYU and Syracuse until 1948, when he returned to Göttingen.
The information here is from the article on Bernstein, by Henry Nathan, in Biographical Dictionary of Mathematicians, New York: Charles Scribner's Sons, 1991.
Exercises 4.9
Ex 4.9.1 Why is the Schröder-Bernstein Theorem easy if $A$ and $B$ are finite sets?
Ex 4.9.2 Suppose $f\colon A\to B$ is an injection and $g\colon A\to B$ is a surjection. Show there is a bijection $h\colon A\to B$.
Ex 4.9.3 At the beginning of the proof of the Schröder-Bernstein Theorem we said, "We may assume that $A$ and $B$ are disjoint sets.'' Why? In other words, what do we do if $A$ and $B$ are not disjoint?
Ex 4.9.4 Prove Claim $1'$ of theorem 4.9.1.
Ex 4.9.5 Prove Claim $2'$ of theorem 4.9.1.
Ex 4.9.6 Prove that the function $h$ defined at the end of the proof of the Schröder-Bernstein Theorem is a bijection.
Ex 4.9.7 Use the Schröder-Bernstein Theorem to conclude that $\overline {{[0,1]}}=c$. (See exercise 3 of section 4.7.)
Ex 4.9.8 Find simple injections from $[0,1]$ to $\R$ and from $\R$ to $[0,1]$. Then find an explicit bijection from $[0,1]$ to $\R$.
Ex 4.9.9 Note that if $A$ has $m$ elements and $B$ has $n$ elements, then $A\times B$ has $mn$ elements. We use this to define the product of two cardinals by the formula $\overline A\cdot \overline B= \overline {A\times B}$. Show that this definition is independent of the sets $A$ and $B$, i.e., if $A\approx A'$ and $B\approx {B'}$, then $A\times B\approx A'\times B'$.
Ex 4.9.10 Show that $\aleph_0\cdot \aleph_0=\aleph_0$. (Hint: exercise 6 of section 4.7.) (See exercise 9.)
Ex 4.9.11 Show that if $\overline A\le \overline B$ then $\overline A\cdot \overline C\le \overline B\cdot \overline C$. (See exercise 9.)
Ex 4.9.12 Prove that if $\overline{A}< \overline{B}\le\overline{C}$ then $\overline{A}< \overline{C}$.