Cantor-Bernstein-Schröder Theorem/Proof 4

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$

Proof

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

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

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

Using $f$ and $g$, $S$ and $T$ are divided into disjoint subsets such that there exists a bijection between the subsets of $S$ and those of $T$, as follows.

Let $a \in S$.

Then we define the elements of $S$:

$\ldots, a_{-2n}, \ldots, a_{-2}, a_0, a_2, \ldots, a_{2n}, \ldots$

and the elements of $T$:

$\ldots, a_{-2n+1}, \ldots, a_{-1}, a_1, \ldots, a_{2n-1}, \ldots$

recursively as follows:

Let:

\(\displaystyle a_0\)

\(=\)

\(\displaystyle a\)

\(\displaystyle a_1\)

\(=\)

\(\displaystyle f \left({a_0}\right)\)

\(\displaystyle a_2\)

\(=\)

\(\displaystyle g \left({a_1}\right)\)

\(\displaystyle \)

\(\vdots\)

\(\displaystyle \)

\(\displaystyle a_{2n-1}\)

\(=\)

\(\displaystyle f \left({a_{2 n - 2} }\right)\)

\(\displaystyle a_{2n}\)

\(=\)

\(\displaystyle g \left({a_{2 n - 1} }\right)\)

\(\displaystyle \)

\(\vdots\)

\(\displaystyle \)

This construction is valid for all $n \ge 1$, but note that some of the $a_n$'s may coincide with others.

We set up a similar construction for negative integers:

\(\displaystyle a_{-1}\)

\(=\)

\(\displaystyle g^{-1} \left({a_0}\right)\)

if such an element exists in $T$

\(\displaystyle a_{-2}\)

\(=\)

\(\displaystyle f^{-1} \left({a_{-1} }\right)\)

if such an element exists in $S$

\(\displaystyle \)

\(\vdots\)

\(\displaystyle \)

\(\displaystyle a_{-2 n + 1}\)

\(=\)

\(\displaystyle g^{-1} \left({a_{-2 n + 2} }\right)\)

if such an element exists in $T$

\(\displaystyle a_{2 n}\)

\(=\)

\(\displaystyle f^{-1} \left({a_{-2 n + 1} }\right)\)

if such an element exists in $S$

\(\displaystyle \)

\(\vdots\)

\(\displaystyle \)

As $f$ and $g$ are injections, it follows that if $f^{-1} \left({x}\right)$ and $g^{-1} \left({y}\right)$ exist for any $x \in T$, $y \in S$, then those elements are unique.

Let:

the elements of $S$ with an even index be denoted $\left[{a}\right]_S$

and

the elements of $T$ with an odd index be denoted $\left[{a}\right]_T$

that is:

\(\displaystyle \left[{a}\right]_S\)

\(=\)

\(\displaystyle \left\{ {\ldots, a_{-2 n}, \ldots, a_{-2}, a_0, a_2, \ldots, a_{2 n}, \ldots}\right\} \subseteq S\)

\(\displaystyle \left[{a}\right]_T\)

\(=\)

\(\displaystyle \left\{ {\ldots, a_{-2 n + 1}, \ldots, a_{-1}, a_1, \ldots, a_{2 n - 1}, \ldots}\right\} \subseteq T\)

We are given that $f$ and $g$ are injections.

So by the definition of $\left[{a}\right]_S$, for any two $a, b \in S$, $\left[{a}\right]_S$ and $\left[{b}\right]_S$ are either disjoint or equal.

The same applies to $\left[{a}\right]_T$ and $\left[{b}\right]_T$ for any $a, b \in T$.

It follows that:

$\mathcal A_S = \left\{{\left[{a}\right]_S: a \in S}\right\}$ is a partition of $S$

and

$\mathcal A_T = \left\{{\left[{a}\right]_T: a \in S}\right\}$ is a partition of $T$.

So:

every element of $S$ belongs to exactly one element of $\mathcal A_S$

and:

every element of $T$ belongs to exactly one element of $\mathcal A_T$.

So let $a \in S$ and $b \in T$ such that $f \left({a}\right) = b$.

It follows that a bijection can be constructed from $\mathcal A_S$ to $\mathcal A_T$.

Now there are two different kinds of $\left[{a}\right]_S$ sets:

$(1):$ It is possible that no repetition occurs in the sequence $\left \langle {a_{2n}}\right \rangle$.

As a consequence, no repetition occurs in the sequence $\left \langle {a_{2n-1}}\right \rangle$ either.

By the method of construction it can be seen that $\left[{a}\right]_S$ and $\left[{a}\right]_T$ are both countably infinite.

So a bijection can be constructed between $\left[{a}\right]_S$ and $\left[{a}\right]_T$.

$(2):$ There may be a repetition in $\left[{a}\right]_S$.

Suppose such a repetition is $a_{2m} = a_{2n}$ for some $m \ne n$.

Then $a_{2m+1} = a_{2n+1}$ and $a_{2m+2} = a_{2n+2}$ and so on.

In general $a_{2m+k} = a_{2n+k}$ for all $k \in \N$.

But because $f$ and $g$ are injections it follows that $a_{2m-1} = a_{2n-1}$ and $a_{2m-2} = a_{2n-2}$ and so on, where they exist.

So in general $a_{2m-k} = a_{2n-k}$ for all $k \in \N$, where they exist.

Given $m$, we can choose $n$ so that the elements $a_{2m}, a_{2m+2}, \ldots, a_{2n-2}$ are distinct.

Then $a_{2m+1}, a_{2m+3}, \ldots, a_{2n-1}$ are likewise distinct elements of $T$.

Thus we can set up a bijection:

$a_{2m} \mapsto a_{2m+1}, a_{2m+2} \mapsto a_{2m+3}, \ldots, a_{2n-2} \mapsto a_{2n-1}$

between the elements of $\left[{a}\right]_S$ and $\left[{a}\right]_T$.

It follows that a bijection can be constructed between any two elements of the partitions of $S$ and $T$.

These maps then automatically yield a bijection from $S$ to $T$.

Hence the result.

$\blacksquare$

Source of Name

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

Sources

• 1964: Steven A. Gaal: Point Set Topology ... (previous) ... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability