# Cantor-Bernstein-Schröder Theorem

## Contents

## 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 Equivalence of Definitions of Dominate (Set Theory), 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 $S$ dominates $T$.

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$.

## Proof 1

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

- $f: S \to T_1$
- $g: T \to S_1$

Let:

- $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$.

For each natural number $k$, let $S_{k+2} \subseteq S$ be the image of $S_k$ under the mapping $g \circ f$.

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

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

Now we can represent $S$ as:

\(\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\) | $\quad$ $(1)$ | $\quad$ |

where $S \setminus S_1$ denotes set difference.

Similarly, we can represent $S_1$ as:

\(\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\) | $\quad$ $(2)$ | $\quad$ |

Now let:

\(\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\) | $\quad$ | $\quad$ | |||||||||

\(\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\) | $\quad$ | $\quad$ | |||||||||

\(\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\) | $\quad$ | $\quad$ |

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

\(\displaystyle S\) | \(=\) | \(\displaystyle D \cup M \cup N\) | $\quad$ $(3)$ | $\quad$ | |||||||||

\(\displaystyle S_1\) | \(=\) | \(\displaystyle D \cup M \cup N_1\) | $\quad$ $(4)$ | $\quad$ |

Now:

\(\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)\) | $\quad$ | $\quad$ | |||||||||

\(\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)\) | $\quad$ | $\quad$ |

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 Law of Excluded Middle there are two choices:

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

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

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 Law of Excluded Middle there are two further choices:

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

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

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 one of the following happens:

- 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:

- $s \in S_A \implies f \left ({s}\right) \in T_A$;
- $\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): \quad S_A$, $S_B$ and $S_C$ are mutually disjoint
- $(2): \quad T_A$, $T_B$ and $T_C$ are mutually disjoint
- $(3): \quad 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.

Let $\alpha$ and $\beta$ denote the mappings induced on $\mathcal P \left({S}\right)$ and $\mathcal P \left({T}\right)$ by $f$ and $g$, respectively.

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

- $z = \complement_S \circ \beta \circ \complement_T \circ \alpha$

### $z$ is an increasing mapping

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

We have:

\(\displaystyle \alpha \left({A}\right)\) | \(\subseteq\) | \(\displaystyle \alpha \left({B}\right)\) | $\quad$ Image of Subset under Relation is Subset of Image: Corollary 2 | $\quad$ | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \left({\complement_T \circ \alpha}\right) \left({A}\right)\) | \(\supseteq\) | \(\displaystyle \left({\complement_T \circ \alpha}\right) \left({B}\right)\) | $\quad$ Set Complement inverts Subsets | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \left({\beta \circ \complement_T \circ \alpha}\right) \left({A}\right)\) | \(\supseteq\) | \(\displaystyle \left({\beta \circ \complement_T \circ \alpha}\right) \left({B}\right)\) | $\quad$ Image of Subset under Relation is Subset of Image: Corollary 2 | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \left({\complement_S \circ \beta \circ \complement_T \circ \alpha}\right) \left({A}\right)\) | \(\subseteq\) | \(\displaystyle \left({\complement_S \circ \beta \circ \complement_T \circ \alpha}\right) \left({B}\right)\) | $\quad$ Set Complement inverts Subsets | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle z \left({A}\right)\) | \(\subseteq\) | \(\displaystyle z \left({B}\right)\) | $\quad$ Definition of $z$ | $\quad$ |

$\Box$

By the Knaster-Tarski Lemma: Power Set, there is a $\mathbb G \in \mathcal P \left({S}\right)$ such that:

- $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 \complement_S \left({\mathbb G}\right)\) | \(=\) | \(\displaystyle \left({\complement_S \circ z}\right) \left({\mathbb G}\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({\complement_S \circ \complement_S \circ \beta \circ \complement_T \circ \alpha}\right) \left({\mathbb G}\right)\) | $\quad$ Definition of $z$ | $\quad$ | |||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle g \left[{\left({\complement_T \circ \alpha}\right] \left({\mathbb G}\right)}\right)\) | $\quad$ as $\complement_S \circ \complement_S = I_{\mathcal P \left({S}\right)}$ | $\quad$ |

At this stage, a diagram can be helpful:

Let $h: S \to T$ be the mapping 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}$

From the above, we have that:

- $\complement_S \left({\mathbb G}\right) \subseteq g \left[{T}\right]$

Therefore, as $g$ is an injection, it follows that the preimage $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$

## Proof 4

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\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle a_1\) | \(=\) | \(\displaystyle f \left({a_0}\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle a_2\) | \(=\) | \(\displaystyle g \left({a_1}\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\vdots\) | \(\displaystyle \) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle a_{2n-1}\) | \(=\) | \(\displaystyle f \left({a_{2 n - 2} }\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle a_{2n}\) | \(=\) | \(\displaystyle g \left({a_{2 n - 1} }\right)\) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\vdots\) | \(\displaystyle \) | $\quad$ | $\quad$ |

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)\) | $\quad$ if such an element exists in $T$ | $\quad$ | |||||||||

\(\displaystyle a_{-2}\) | \(=\) | \(\displaystyle f^{-1} \left({a_{-1} }\right)\) | $\quad$ if such an element exists in $S$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\vdots\) | \(\displaystyle \) | $\quad$ | $\quad$ | |||||||||

\(\displaystyle a_{-2 n + 1}\) | \(=\) | \(\displaystyle g^{-1} \left({a_{-2 n + 2} }\right)\) | $\quad$ if such an element exists in $T$ | $\quad$ | |||||||||

\(\displaystyle a_{2 n}\) | \(=\) | \(\displaystyle f^{-1} \left({a_{-2 n + 1} }\right)\) | $\quad$ if such an element exists in $S$ | $\quad$ | |||||||||

\(\displaystyle \) | \(\vdots\) | \(\displaystyle \) | $\quad$ | $\quad$ |

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:

and

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\) | $\quad$ | $\quad$ | |||||||||

\(\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\) | $\quad$ | $\quad$ |

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$

## Proof 5

By Injection to Image is Bijection:

- $g: T \to g \left({T}\right)$ is a bijection.

Thus $T$ is equivalent to $g \left({T}\right)$.

By Composite of Injections is Injection $g \circ f: S \to g \left({T}\right) \subset S$ is also an injection (to a subset of the domain).

Then by Cantor-Bernstein-Schröder Theorem: Lemma:

- There is a bijection $h: S \to g \left({T}\right)$.

Thus $S$ is equivalent to $g \left({T}\right)$.

We already know that $T$ is equivalent to $g \left({T}\right)$.

Thus by Set Equivalence is Equivalence Relation, $S$ is equivalent to $T$.

By the definition of set equivalence:

- There is a bijection $\phi: S \to T$.

$\blacksquare$

## Proof 6

Let $\mathcal P \left({A}\right)$ be the power set of $A$.

Define a mapping $E: \mathcal P \left({A}\right) \to \mathcal P \left({A}\right)$ thus:

- $E \left({S}\right) = A \setminus g \left({B \setminus f \left({S}\right)}\right)$

### $E$ is increasing

Let $S, T \in \mathcal P \left({A}\right)$ such that $S \subseteq T$.

Then:

\(\displaystyle f \left({S}\right)\) | \(\subseteq\) | \(\displaystyle f \left({T}\right)\) | $\quad$ Image of Subset is Subset of Image | $\quad$ | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle B \setminus f \left({T}\right)\) | \(\subseteq\) | \(\displaystyle B \setminus f \left({S}\right)\) | $\quad$ Set Difference with Subset is Superset of Set Difference | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle g \left({B \setminus f \left({T}\right)}\right)\) | \(\subseteq\) | \(\displaystyle g \left({B \setminus f \left({S}\right)}\right)\) | $\quad$ Image of Subset is Subset of Image | $\quad$ | ||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle A \setminus g \left({B \setminus f \left({S}\right)}\right)\) | \(\subseteq\) | \(\displaystyle A \setminus g \left({B \setminus f \left({T}\right)}\right)\) | $\quad$ Set Difference with Subset is Superset of Set Difference | $\quad$ |

That is, $E \left({S}\right) \subseteq E \left({T}\right)$.

$\Box$

By the Knaster-Tarski Lemma, $E$ has a fixed point $X$.

By the definition of fixed point:

- $E \left({X}\right) = X$

Thus by the definition of $E$:

- $A \setminus g \left({B \setminus f \left({X}\right)}\right) = X$

Therefore:

- $(1): \quad A \setminus \left({A \setminus g \left({B \setminus f \left({X}\right)}\right)}\right) = A \setminus X$

Since $g$ is a mapping into $A$:

- $g \left({B \setminus f \left({X}\right)}\right) \subseteq A$

Thus by Relative Complement of Relative Complement:

- $A \setminus \left({A \setminus g \left({B \setminus f \left({X}\right)}\right)}\right) = g \left({B \setminus f \left({X}\right)}\right)$

Thus by $(1)$:

- $g \left({B \setminus f \left({X}\right)}\right) = A \setminus X$

Let $f' = f \restriction_{X \times f \left({X}\right)}$ be the restriction of $f$ to $X \times f \left({X}\right)$.

Similarly, let $g' = g \restriction_{\left({B \setminus f \left({X}\right)}\right) \times \left({A \setminus X}\right)} = g \restriction_{\left({B \setminus f \left({X}\right)}\right) \times g \left({B \setminus f \left({X}\right)}\right)}$.

By Injection to Image is Bijection, $f'$ and $g'$ are both bijections.

Define a relation $h: A \to B$ by $h = f' \cup {g'}^{-1}$.

We will show that $h$ is a bijection from $A$ onto $B$.

The domain of $f'$ is $X$, which is disjoint from the codomain, $A \setminus X$, of $g'$.

The domain of $g'$ is $B \setminus f \left({X}\right)$, which is disjoint from the codomain, $f \left({X}\right)$, of $f'$.

Let $h = f' \cup {g'}^{-1}$.

By the corollary to Union of Bijections with Disjoint Domains and Codomains is Bijection:

- $h$ is a bijection from $X \cup \left({A \setminus X}\right)$ onto $f \left({X}\right) \cup \left({B \setminus f \left({X}\right)}\right)$.

By Union with Relative Complement, $h$ is a bijection from $A$ onto $B$.

Since $f' \subseteq f$ and $g' \subseteq g$, each element of $h$ is an element of $f$ or of $g^{-1}$.

That is, if $y = h \left({x}\right)$ then either $y = f \left({x}\right)$ or $x = g \left({y}\right)$.

$\blacksquare$

## Law of the Excluded Middle

This theorem depends on the Law of the Excluded Middle.

This is one of the axioms of logic that was determined by Aristotle, and forms part of the backbone of classical (Aristotelian) logic.

However, the intuitionist school rejects the Law of the Excluded Middle as a valid logical axiom. This in turn invalidates this theorem from an intuitionistic perspective.

## 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**

## 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

- 1968: A.N. Kolmogorov and S.V. Fomin:
*Introductory Real Analysis*: $\S 2.6$: Theorem $7$ - 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 10.03$ - 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 8$: Theorem $8.2$: Corollary - 2005: René L. Schilling:
*Measures, Integrals and Martingales*... (previous) ... (next): $2.7$ - 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): Appendix $\text{A}$: Set Theory: Cardinality