Cantor-Bernstein-Schroeder Theorem

Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:

$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Alternatively, from Dominates is Equivalent to Subset, this can be expressed as:

$\forall S, T: T \preccurlyeq S \land S \preccurlyeq T \implies S \sim T$

where $T \preccurlyeq S$ denotes the fact that $T$ dominates $S$.

That is:

If $\exists f: S \to T$ and $\exists g: T \to S$ where $f$ and $g$ are both injections, then there exists a bijection from $S$ to $T$.

Also known as

• The Cantor-Bernstein Theorem
• The Cantor-Schroeder-Bernstein Theorem or Cantor-Schröder-Bernstein Theorem
• The Schroeder-Bernstein Theorem or Schröder-Bernstein Theorem

Proof 1

From the facts that $T \sim S_1$ and $S \sim T_1$, we can set up the two bijections:

• $f \left({S}\right) = T_1 \subseteq T$
• $g \left({T}\right) = S_1 \subseteq S$

Thus:

$S_2 = g \left({f \left({S}\right)}\right) = g \left({T_1}\right) \subseteq S_1$

and:

$T_2 = f \left({g \left({T}\right)}\right) = f \left({S_1}\right) \subseteq T_1$

So $S_2 \subseteq S_1$, and $S_2 \sim S$, while $T_2 \subseteq T_1$, and $T_2 \sim T$.

Let $S_3 \subseteq S$ be the image of $S_1$ under the mapping $g \circ f$,

and let $S_4 \subseteq S$ be the image of $S_2$ under the mapping $g \circ f$.

We can generalise this to:

Let $S_{k+2} \subseteq S$ be the image of $S_k$ under the mapping $g \circ f$, where $k \in \N$.

Then $S \supseteq S_1 \supseteq S_2 \supseteq \ldots \supseteq S_k \supseteq S_{k+1} \ldots$.

Set $\displaystyle D = \bigcap_{k=1}^\infty {S_k}$.

Now we can represent $S$ as:

\(\displaystyle \)

\(\displaystyle S\)

\(=\)

\(\displaystyle \left({S \setminus S_1}\right) \cup \left({S_1 \setminus S_2}\right) \cup \ldots \cup \left({S_k \setminus S_{k+1} }\right) \cup \ldots \cup D\)

\(\displaystyle \)

$(1)$

where $S \setminus S_1$ denotes set difference.

Similarly, we can represent $S_1$ as:

\(\displaystyle \)

\(\displaystyle S_1\)

\(=\)

\(\displaystyle \left({S_1 \setminus S_2}\right) \cup \left({S_2 \setminus S_3}\right) \cup \ldots \cup \left({S_k \setminus S_{k+1} }\right) \cup \ldots \cup D\)

\(\displaystyle \)

$(2)$

Now let:

	\(\displaystyle \)	\(\displaystyle M\)	\(=\)	\(\displaystyle \left({S_1 \setminus S_2}\right) \cup \left({S_3 \setminus S_4}\right) \cup \left({S_5 \setminus S_6}\right) \cup \ldots\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle N\)	\(=\)	\(\displaystyle \left({S \setminus S_1}\right) \cup \left({S_2 \setminus S_3}\right) \cup \left({S_4 \setminus S_5}\right) \cup \ldots\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle N_1\)	\(=\)	\(\displaystyle \left({S_2 \setminus S_3}\right) \cup \left({S_4 \setminus S_5}\right) \cup \left({S_6 \setminus S_7}\right) \cup \ldots\)	\(\displaystyle \)

... and rewrite $(1)$ and $(2)$ as:

	\(\displaystyle \)	\(\displaystyle S\)	\(=\)	\(\displaystyle D \cup M \cup N\)	\(\displaystyle \)	$(3)$
	\(\displaystyle \)	\(\displaystyle S_1\)	\(=\)	\(\displaystyle D \cup M \cup N_1\)	\(\displaystyle \)	$(4)$

Now:

	\(\displaystyle \)	\(\displaystyle g \circ f \left({S \setminus S_1}\right) = \left({S_2 \setminus S_3}\right)\)	\(\implies\)	\(\displaystyle \left({S \setminus S_1}\right) \sim \left({S_2 \setminus S_3}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle g \circ f \left({S_2 \setminus S_3}\right) = \left({S_4 \setminus S_5}\right)\)	\(\implies\)	\(\displaystyle \left({S_2 \setminus S_3}\right) \sim \left({S_4 \setminus S_5}\right)\)	\(\displaystyle \)

and so on.

So $N \sim N_1$.

It follows from $(3)$ and $(4)$ that a bijection can be set up between $S$ and $S_1$.

But $S_1 \sim T$.

Therefore $S \sim T$.

$\blacksquare$

Proof 2

Suppose $S \preccurlyeq T$ and $T \preccurlyeq S$.

By definition, we have that there exist injections $f: S \to T$ and $g: T \to S$.

We are going to try to build a sequence $t_1, s_1, t_2, s_2, t_3 \ldots$ as follows.

Consider any $t_1 \in T$.

By the Law of the Excluded Middle there are two choices:

	\(\displaystyle \)	\(\displaystyle \exists s_1 \in S: f \left({s_1}\right)\)	\(=\)	\(\displaystyle t_1\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \neg \exists s_1 \in S: f \left({s_1}\right)\)	\(=\)	\(\displaystyle t_1\)	\(\displaystyle \)

Suppose $\exists s_1 \in S: f \left({s_1}\right) = t_1$.

Because $f$ is injective, such an $s_1$ is unique.

So we can choose $s_1 = f^{-1} \left({t_1}\right)$.

Again, by the Law of the Excluded Middle there are two further choices:

	\(\displaystyle \)	\(\displaystyle \exists t_2 \in T: g \left({t_2}\right)\)	\(=\)	\(\displaystyle s_1\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \neg \exists t_2 \in T: g \left({t_2}\right)\)	\(=\)	\(\displaystyle s_1\)	\(\displaystyle \)

Suppose $\exists t_2 \in T: g \left({t_2}\right) = s_1$.

Because $f$ is injective, such an $t_2$ is unique.

Similarly, we choose $s_2 = f^{-1} \left({t_2}\right)$, if it exists.

This process goes on until:

• We reach some $s_n \in S$ such that $\neg \exists t \in T: g \left({t}\right) = s_n$. This may be possible because $g$ may not be a surjection.

• We reach some $t_n \in T$ such that $\neg \exists s \in S: f \left({s}\right) = t_n$.This may be possible because $f$ may not be a surjection.

• The process goes on for ever.

For each $t \in T$, then, there is a well-defined process which turns out in one of the above three ways.

We partition $T$ up into three subsets that are mutually disjoint:

• Let $T_A = \{$ all $t \in T$ such that the process ends with some $s_n\}$
• Let $T_B = \{$ all $t \in T$ such that the process ends with some $t_n\}$
• Let $T_C = \{$ all $t \in T$ such that the process goes on for ever$\}$.

We can do exactly the same thing with the elements of $S$:

• Let $S_A = \{$ all $s \in S$ such that the process ends with some $s_n\}$
• Let $S_B = \{$ all $s \in S$ such that the process ends with some $t_n\}$
• Let $S_C = \{$ all $s \in S$ such that the process goes on for ever$\}$.

What we need to do is show that $S \sim T$.

We do this by showing that $S_A \sim T_A$, $S_B \sim T_B$ and $S_C \sim T_C$.

• The restriction of $f$ to $S_A$ is a bijection from $S_A$ to $T_A$.

To do this we need to show that:

1. $s \in S_A \implies f \left ({s}\right) \in T_A$;
2. $\forall t \in T_A: \exists s \in S_A: f \left ({s}\right) = t$.

Let $s \in S_A$. Then the process applied to $s$ ends in $S$.

Now consider the process applied to $f \left ({s}\right)$. Its first step leads us back to $s$. Then it continues the process, applied to $s$, and ends up in $S$. Thus $f \left ({s}\right) \in T_A$.

Thus $s \in S_A \implies f \left ({s}\right) \in T_A$.

Now suppose $t \in T_A$. Then the process applied to $t$ ends in $S$.

In particular, it must have a first stage, otherwise it would end in $T$ with $t$ itself.

Hence $t = f \left ({s}\right)$ for some $s$.

But the process applied to this $s$ is the same as the continuation of the process applied to $t$, and therefore it ends in $S$.

Thus $s \in S_A$ as required.

Hence the restriction of $f$ to $S_A$ is a bijection from $S_A$ to $T_A$.

We can use the same argument to show that $g: T_B \to S_B$ is also a bijection. Hence $g^{-1}: S_B \to T_B$ is a bijection.

Finally, suppose $t \in T_C$.

Because $f$ is an injection, $t = f \left({s}\right)$ for some $s$, and the process applied to $t$ must start.

And this $s$ must belong to $S_C$, because the process starting from $s$ is the same as the process starting from $t$ after the first step. This never ends, as $t \in T_C$.

Now we can define a bijection $h: S \to T$ as follows:

$\displaystyle h \left({x}\right) = \begin{cases} f \left({x}\right): x \in S_A \\ f \left({x}\right): x \in S_C \\ g^{-1} \left({x}\right): x \in S_B \\ \end{cases}$

The fact that $h$ is a bijection follows from the facts that:

1. $S_A$, $S_B$ and $S_C$ are mutually disjoint;
2. $T_A$, $T_B$ and $T_C$ are mutually disjoint;
3. $f$, $f$ and $g^{-1}$ are the bijections which respectively do the mappings between them.

$\blacksquare$

Proof 3

Let $S, T$ be sets, and let $\mathcal P \left({S}\right), \mathcal P \left({T}\right)$ be their power sets.

Let $f: S \to T$ and $g: T \to S$ be injections that we know to exist between $S$ and $T$.

Consider the relative complements of elements of $\mathcal P \left({S}\right)$ and $\mathcal P \left({T}\right)$ as mappings:

• $\complement_S: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right): \forall X \in \mathcal P \left({S}\right): \complement_S \left({X}\right) = S \setminus X$
• $\complement_T: \mathcal P \left({T}\right) \to \mathcal P \left({T}\right): \forall Y \in \mathcal P \left({T}\right): \complement_T \left({Y}\right) = T \setminus Y$

which follow directly from the definition of relative complement.

Consider the mapping $z: \mathcal P \left({S}\right) \to \mathcal P \left({S}\right)$ defined by:

$z = \complement_S \circ \left({g \circ \complement_T \circ f}\right)$

Consider $A \subseteq B \subseteq S$, so $A, B \in \mathcal P \left({S}\right)$.

We have:

	\(\displaystyle \)	\(\displaystyle A \subseteq B\)	\(\implies\)	\(\displaystyle f \left({A}\right) \subseteq f \left({B}\right)\)	\(\displaystyle \)	from Subset of Image
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \complement_T \left({f \left({B}\right)}\right) \subseteq \complement_T \left({f \left({A}\right)}\right)\)	\(\displaystyle \)	from Complements Invert Subsets
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle f \left({\complement_T \left({f \left({B}\right)}\right)}\right) \subseteq g \left({\complement_T \left({f \left({A}\right)}\right)}\right)\)	\(\displaystyle \)	from Subset of Image
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \complement_S \left({g \left({\complement_T \left({f \left({A}\right)}\right)}\right)}\right) \subseteq \complement_S \left({g \left({\complement_T \left({f \left({B}\right)}\right)}\right)}\right)\)	\(\displaystyle \)	from Complements Invert Subsets
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle z \left({A}\right) \subseteq z \left({B}\right)\)	\(\displaystyle \)	by definition of $z$

Now consider the collection:

$\mathbb F = \left\{{X \in \mathcal P \left({S}\right): X \subseteq z \left({X}\right)}\right\}$

As Empty Set Subset of All, we note that $\varnothing \in \mathbb F$, so $\mathbb F \ne \varnothing$.

Now consider the union of all the sets in $\mathbb F$:

$\displaystyle \mathbb G = \bigcup \left\{{X: X \in \mathbb F}\right\}$

Don't lose sight of the fact that:

$\mathbb F \subseteq \mathcal P \left({S}\right)$;

$\mathbb G \subseteq S$.

From Subset of Union: General Result, we have that $X \in \mathbb F \implies X \subseteq \mathbb G$.

Thus:

$X \subseteq z \left({X}\right) \subseteq z \left({\mathbb G}\right)$

From Union Smallest: General Result, it follows that:

$\mathbb G \subseteq z \left({\mathbb G}\right)$

and so from above:

$z \left({\mathbb G}\right) \subseteq z \left({z \left({\mathbb G}\right)}\right)$

So $z \left({\mathbb G}\right) \in \mathbb F$ and so $z \left({\mathbb G}\right) \subseteq \mathbb G$.

So from:

$z \left({\mathbb G}\right) \subseteq \mathbb G$

and:

$\mathbb G \subseteq z \left({\mathbb G}\right)$

we have from Equality of Sets:

$z \left({\mathbb G}\right) = \mathbb G$

From Relative Complement of Relative Complement we have that $\complement_S \circ \complement_S$ is the identity mapping on $\mathcal P \left({S}\right)$.

Thus we obtain:

	\(\displaystyle \)	\(\displaystyle \complement_S \left({\mathbb G}\right)\)	\(=\)	\(\displaystyle \left({\complement_S \circ z}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\complement_S \circ \complement_S \circ g \circ \complement_T \circ f}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)	by definition of $z$
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({g \circ \complement_T \circ f}\right) \left({\mathbb G}\right)\)	\(\displaystyle \)	as $\complement_S \circ \complement_S = I_{\mathcal P \left({S}\right)}$

At this stage a diagram can be helpful:

Now consider the sets $S$ and $T$ in light of the fact that the relative complement forms a partition.

We have that:

• $\left\{{\mathbb G, \complement_S \left({\mathbb G}\right)}\right\}$ forms a partition of $S$;
• $\left\{{f \left({\mathbb G}\right), \complement_T \left({f \left({\mathbb G}\right)}\right)}\right\}$ forms a partition of $T$.

Thus we see that we can set up the mapping $h: S \to T$ defined as:

$\forall x \in S: h \left({x}\right) = \begin{cases} f \left({x}\right) & : x \in \mathbb G \\ g^{-1} \left({x}\right) & : x \in \complement_S \left({\mathbb G}\right) \end{cases}$

As $g$ is an injection, it follows that $g^{-1} \left({x}\right)$ is a singleton.

So $h$ is a bijection by dint of the injective nature of both $f$ and $g^{-1}$.

$\blacksquare$

Comments

• This theorem states in set theoretical concepts the "intuitively obvious" fact that if $a \le b$ and $b \le a$ then $a = b$.

Care needs to be taken to make well sure of this, because when considering infinite sets, intuition is frequently misleading.

• In order to prove equivalence, a bijection needs to be demonstrated. It can be significantly simpler to demonstrate an injection than a surjection, so proving that there is an injection from $S$ to $T$ and also one from $T$ to $S$ may be a lot less work than proving that there is both an injection and a surjection from $S$ to $T$.

Source of Name

This entry was named for Georg Cantor, Felix Bernstein and Ernst Schröder.

Cantor first attempted to prove this theorem in his 1897 paper. Ernst Schröder had also stated this theorem some time earlier, but his proof, as well as Cantor's, was flawed. It was Felix Bernstein who finally supplied a correct proof in his 1898 PhD thesis.

Sources

• A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 2.6$: Theorem $7$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 8$: Theorem $8.2$