2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – DanielWainfleet May 1 '18 at 4:28
  • $\begingroup$ 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 :) $\endgroup$ – Le Anh Dung May 1 '18 at 13:38
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – Le Anh Dung May 1 '18 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.