# Is my proof of Cantor-Bernstein-Schröder theorem correct?

Please check if my proof contains any error!

Cantor-Bernstein-Schröder theorem:

Suppose $f:A \to B$ and $g:B \to A$ are injections. Then there exists a bijection $h$ between $A$ and $B$.

Proof:

First, let $A_0=A\setminus g[B]$ and $B_0=B\setminus f[A]$. We define recursively $B_{n+1}=f[A_n]$ and $A_{n+1}=g[B_n]$ for all $n \in \mathbb N$. Second, let $A'=A\setminus\bigcup_{n\in\mathbb N}A_n$ and $B'=B\setminus\bigcup_{n\in\mathbb N}B_n$. Finally, our sequences look like:

$$A_0 \rightarrow B_1 \rightarrow A_2 \rightarrow B_3 \rightarrow A_4 \rightarrow \cdots$$

$$B_0 \rightarrow A_1 \rightarrow B_2 \rightarrow A_3 \rightarrow B_4 \rightarrow \cdots$$

Note that for all $n\in\mathbb N$, $f\upharpoonright A_n$ is a bijection from $A_n$ to $B_{n+1}$, and $g\upharpoonright B_n$ is a bijection from $B_n$ to $A_{n+1}$.

1. $\{A_n \mid n \in \mathbb N\} \cup \{A'\}$ and $\{B_n \mid n \in \mathbb N\} \cup \{B'\}$ are partitions of $A$ and $B$ respectively

Let $T=\{n \in \mathbb N \mid A_n \cap A_m =\varnothing \text{ and } B_n \cap B_m =\varnothing \text{ for all } m \neq n\}$. It suffices to prove $T=\mathbb N$.

$A_{n+1}=g[B_n] \subseteq g[B]$ and $A_0=A\setminus g[B]$ $\implies A_0 \cap A_{n+1} =\varnothing \space \forall n \in \mathbb N$, or equivalently $A_0 \cap A_m =\varnothing \space \forall m \neq 0$. Similarly, $B_0 \cap B_m =\varnothing \space \forall m \neq 0$. Thus $0 \in T$.

Assume $k\in T$, then $A_k \cap A_m =\varnothing$ and $B_k \cap B_m =\varnothing$ for all $m \neq k$. Thus $B_k \cap B_{m-1} =\varnothing \space \forall m-1 \neq k \implies g[B_k] \cap g[B_{m-1}] =\varnothing \space \forall m \neq k+1$ [Since $g$ is injective] $\implies A_{k+1} \cap A_m = \varnothing \space \forall m \neq k+1$. Similarly, $B_{k+1} \cap B_m = \varnothing \space \forall m \neq k+1$. Thus $k+1 \in T$.

By principle of induction, $T=\mathbb N$.

1. $f:A' \to B'$ is bijective

If $a\in A'$, then $f(a) \in f(A\setminus\bigcup_{n\in\mathbb N}A_n)=f(A)\setminus\bigcup_{n\in\mathbb N}f(A_n)$ [Since $f$ is injective] $=(B\setminus B_0)\setminus \bigcup_{n\in\mathbb N}B_{n+1}=B\setminus (B_0 \cup \bigcup_{n\in\mathbb N}B_{n+1})=B\setminus \bigcup_{n\in\mathbb N}B_n=B'$.

If $b \in B'$, then $b \in B\setminus \bigcup_{n\in\mathbb N}B_n=B\setminus (B_0 \cup \bigcup_{n\in\mathbb N}B_{n+1})=B\setminus ((B\setminus f(A)) \cup \bigcup_{n\in\mathbb N}B_{n+1})$. Thus $b\in B$ and $b \notin B\setminus f(A) \implies b \in f(A) \implies$ there exits $f^{-1}(b) \implies f^{-1}(b) \notin A_n$ for all $n \in \mathbb N$ [if not, there exists $n\in \mathbb N$ such that $f^{-1}(b)\in A_n \implies f(f^{-1}(b))\in f(A_n) \implies$ $b \in B_{n+1}$. This contradicts the fact that $b \in B'$] $\implies f^{-1}(b) \in A'$.

1. We generate the desired function $h$ as follows

$$h:A\to B:a\mapsto\begin{cases} f(a)&\text{if }a\in A'\cup\bigcup_{n\in \mathbb N}A_{2n} \\ g^{-1}(a)&\text{if }a\in \bigcup_{n\in \mathbb N}A_{2n+1} \end{cases}$$ $$\tag*{\blacksquare}$$

• There is a much shorter and simpler proof of this theorem. You can find it in Introduction To Topology And Modern Analysis,, by Simmons, or in a couple of answers of mine on this topic on this site.... It is also called the Schroeder-Bernstein or Cantor-Bernstein theorem – DanielWainfleet May 1 '18 at 4:28
• Thank you @DanielWainfleet! I've read your answers and they are amazing. I'm just curious about other proofs so that I can have a broader view of this theorem :) – Le Anh Dung May 1 '18 at 13:38

I want to expand upon a comment about shorter proofs. Here I present a more elementary proof-outline of the theorem. First a lemma, which is an instance of the Knaster-Tarski fixed point theorem.

Lemma. Let $X$ and $Y$ be sets. Fix $f:X\to Y$. Fix $g:Y\to X$. Define $F:\mathscr{P}\left(X\right)\to\mathscr{P}\left(X\right)$ by $$F\left(S\right)=X\setminus g\left(Y\setminus f\left(S\right)\right)$$ for every $S\in\mathscr{P}\left(X\right)$. Define $\mathcal{S}:=\left\{S\in\mathscr{P}\left(X\right):S\subseteq F\left(S\right)\right\}$. Define $T:=\bigcup\mathcal{S}$.

(i) For all $S_0,S_1\in\mathscr{P}\left(X\right)$, if $S_0\subseteq S_1$, then $F\left(S_0\right)\subseteq F\left(S_1\right)$.

(ii) For each $S\in\mathcal{S}$, $S\subseteq T$ and $S\subseteq F\left(S\right)\subseteq F\left(T\right)$.

(iii) $T\subseteq F\left(T\right)$ and $F\left(T\right)\subseteq F\left(F\left(T\right)\right)$.

(iv) $F\left(T\right)=T$.

Theorem. Let $X$ and $Y$ be sets. Let $f$ be an injection from $X$ to $Y$. Let $g$ be an injection from $Y$ to $X$. Let $T$ be a subset of $X$ such that $T=X\setminus g\left(Y\setminus f\left(T\right)\right)$---which exists by the above lemma.

(i) For each $y\in Y$, if $y\in Y\setminus f\left(T\right)$, then $g\left(y\right)\in X\setminus T$.

(ii) For each $x_1\in T$ and for each $x_2\in X\setminus T$, $f\left(x_1\right)\in f\left(T\right)$ and $g^{-1}\left(x_2\right)\in Y\setminus f\left(T\right)$.

(iii) $\left(f\upharpoonright T\right)\cup(g^{-1}\upharpoonright X\setminus T)$ is a bijection from $X$ to $Y$.

Notice (iii) is our desired conclusion. Also one does not need to use the natural numbers $\mathbb{N}$ to prove the theorem. If you are mainly interested in a verification of your proof, then it would immensely help to present an argument as to why your $h$ function is a bijection. It seems like you presented two lemmas, but never went about proving the meat of the theorem. I.e. that your constructed $h$ is indeed a bijection.

Edit: In the theorem (i) proves surjectivity, and (ii) proves injectivity.

Wikipedia: Schröder–Bernstein theorem

• I got your proof. Could you be more specific about two lemmas that I have not proved? I think your confusion would be solved if I wrote $$h:A\to B:a\mapsto\begin{cases} f(a)&\text{if }a\in A_{2n}\text{ for some }n\in\mathbb N\\ g^{-1}(a)&\text{if }a\in A_{2n+1}\text{ for some }n\in\mathbb N\\ f(a)&\text{if }a\in A'\; \end{cases}$$ – Le Anh Dung May 1 '18 at 14:31