# Top-down and Bottom-up proofs of a lemma used to prove Cantor-Bernstein-Schröder theorem and their connection

Lemma:

Suppose that $Z \subseteq Y \subseteq X$ and that $f:X \to Z$ is bijective, then there exists a bijection $g : X \to Y$.

Here I present two proofs in detail for the lemma in which the first proof one is top-down and the second is bottom-up. Furthermore, I prove that the set $A$ in top-down proof actually equals to set $A$ in bottom-up approach. Especially, the key part in top-down approach is to prove $f(A)=A \cap Y$, so I present two different ways to prove $f(A)=A \cap Y$ in which one of them is very intuitive while the other is not. I give the proofs that are as detailed as possible for clarity.

Please check if my complete proofs contain any error!

Top-down proof:

Without loss of generality, we assume $Y \subsetneq X$.

Let $$\mathcal{F}=\{ V\subseteq X | (X-Y) \subseteq V \text{ and } f(V) \subseteq V \}$$ $$A=\bigcap_{V\in \mathcal{F}}V$$

From the definition of $A$, we have that $A \in \mathcal{F}$ and that $\forall V\in \mathcal{F}, A \subseteq V$, or equivalently $A$ is the minimal element of $\mathcal{F}$.

1. We prove $A \neq \varnothing$

$X-Y \subseteq X$ and $f(X)=Z \subseteq X \implies X \in \mathcal{F} \implies \mathcal{F} \neq \varnothing.$ As a result, $f(A) \subseteq A$ and $(X-Y) \subseteq A$.

$\mathcal{F} \neq \varnothing$ and $\forall V \in \mathcal{F}, (X-Y) \subseteq V \implies (X-Y) \subseteq \bigcap_{V\in \mathcal{F}}V \implies (X-Y) \subseteq A \implies$ $A \neq \varnothing.$

1. We prove $f(A)=A \cap Y$

a. Indirect approach (seemingly not intuitive at all).

Let $$B=f(A) \cup (X-Y)$$

$f(A) \subseteq A$ and $(X-Y) \subseteq A \implies B \subseteq A$.

First, $B=f(A) \cup (X-Y) \implies (X-Y) \subseteq B$.

$f(A) \subseteq A \implies f(f(A)) \subseteq f(A)$; $(X-Y) \subseteq A \implies f(X-Y) \subseteq f(A)$.

Second, $f(B)=f(f(A) \cup (X-Y))=f(f(A)) \cup f(X-Y) \subseteq f(A) \subseteq B.$

Finally, $(X-Y) \subseteq B$ and $f(B) \subseteq B \implies B \in \mathcal{F},$ but $B \subseteq A$. From the minimality of $A$, $B=A$.

$A \cap Y=B \cap Y= (f(A) \cup (X-Y)) \cap Y=(f(A) \cap Y) \cup ((X-Y) \cap Y)=f(A) \cup \varnothing = f(A)$.

b. Direct approach.

$f(A) \subseteq A$ and $f(A) \subseteq Z \subseteq Y \implies f(A) \subseteq (A \cap Y)$.

Assume $(A\cap Y) \not\subseteq f(A) \implies \exists p\in (A\cap Y)$ such that $p \notin f(A) \implies p \in Y$.

Let $$B=A-\{p\}$$.

First, $p \in Y \wedge (X-Y) \subseteq A \implies X-Y \subseteq A-\{p\} \implies (X-Y) \subseteq B$.

Second, $f(B)=f(A-\{p\})=f(A)-f(\{p\})$ [Since $f$ is injective] $\subseteq f(A) \subseteq f(A)-\{p\}$ [Since $p \notin f(A)$] $\subseteq A-\{p\}$ [Since $f(A) \subseteq A$]$=B$.

To sum up, we have $(X-Y) \subseteq B$ and $f(B)\subseteq B$, then $B \in \mathcal{F}$, but $B \subsetneq A$. This contradicts to the minimality of $A \implies (A \cap Y) \subseteq f(A)$.

$f(A) \subseteq (A \cap Y)$ and $A \cap Y \subseteq f(A) \implies A \cap Y=f(A)$.

1. $f(A) \cup (X-A)=Y$ and $f(A) \cap (X-A)=\varnothing$

$X-Y \subseteq A \implies X-A \subseteq X-(X-Y)=Y$.

$f(A) \cup (X-A)=(A \cap Y)\cup (X-A)=(A\cup (X-A)\cap (Y\cup (X-A))=X\cap (Y\cup (X-A))=Y\cup (X-A) \subseteq Y \cup Y=Y \implies f(A) \cup (X-A)=Y$.

$f(A) \cap (X-A)=(A \cap Y) \cap (X-A)=Y \cap (A \cap (X-A))=Y \cap \varnothing=\varnothing.$

We generate $g$ as follows:

$$g(x) = \begin{cases} \ f(x) & \text {if x \in A} \\ x & \text {if x \in X \setminus A} \\ \end{cases}$$

Bottom-up proof:

Let $$A=A_0\cup A_1\cup A_2\cup\cdots$$ where $A_0=X-Y$ and $A_{n+1}=f(A_n).$

It is clear that $A_0=X-Y \notin Y$, while $A_{n+1}=f(A_n) \in Y \space \forall n \in \mathbb{N}$. Thus$A_0 \cap (A_1\cup A_2\cup A_3\cup\cdots)=\varnothing.$

$f(A)=f(A_0\cup A_1\cup A_2\cup\cdots)=f(A_0)\cup f(A_1)\cup f(A_2)\cup\cdots=A_1\cup A_2\cup A_3\cup\cdots=A-A_0=A-(X-Y)=(A \cap Y)\cup (A-X)=(A \cap Y)\cup \varnothing =A \cap Y$. Thus $f(A)=A \cap Y$.

$A=A_0\cup A_1\cup A_2\cup\cdots \implies A=(X-Y)\cup f(A) \implies X-Y \subseteq A \implies X-A \subseteq X-(X-Y)=Y$.

Now we prove $f(A) \cup (X-A)=Y$ and $f(A) \cap (X-A)=\varnothing$.

$f(A) \cup (X-A)=(A \cap Y)\cup (X-A)=(A\cup (X-A)\cap (Y\cup (X-A))=X\cap (Y\cup (X-A))=Y\cup (X-A) \subseteq Y \cup Y=Y \implies f(A) \cup (X-A)=Y$.

$f(A) \cap (X-A)=(A \cap Y) \cap (X-A)=Y \cap (A \cap (X-A))=Y \cap \varnothing=\varnothing.$

We generate $g$ as follows:

$$g(x) = \begin{cases} \ f(x) & \text {if x \in A} \\ x & \text {if x \in X \setminus A} \\ \end{cases}$$

Now I show that the set $A$ in top-down proof equals to set $A$ in bottom-up approach.

Let $$A=A_0\cup A_1\cup A_2\cup\cdots$$ where $A_0=X-Y$ and $A_{n+1}=f(A_n)$.

1. $A \in \mathcal{F}$

$f(A)=f(A_0\cup A_1\cup A_2\cup\cdots)=f(A_0)\cup f(A_1)\cup f(A_2)\cup\cdots=A_1\cup A_2\cup A_3\cup\cdots \implies f(A) \subseteq A$.

$A=A_0\cup A_1\cup A_2\cup\cdots \implies A=A_0 \cup f(A)=(X-Y)\cup f(A) \implies (X-Y)\subseteq A$.

$f(A) \subseteq A$ and $(X-Y)\subseteq A \implies A \in \mathcal{F}$.

1. $A$ is the minimal element of $\mathcal{F}$

$A_0 =X-Y \implies A_0 \cap Y=\varnothing$.

$A_{n+1}=f(A_n) \implies A_{n+1} \subseteq Y \space \forall n \in \mathbb{N} \implies A_0 \cap A_n =\varnothing \space \forall n>0 \implies f^m(A_0) \cap f^m(A_n)=\varnothing \space \forall m \in \mathbb{N} \text{ and } n>0 \implies A_m \cap A_{m+n} =\varnothing \space \forall m \in \mathbb{N} \text{ and } n>0 \implies A_m \cap A_n =\varnothing \space \forall m \neq n$.

Assume $x \in A$, then $\exists ! n \in \mathbb{N}$ such that $x \in A_n$. Let $B=A \setminus \{x\}$. It suffices to prove $B \notin \mathcal{F}$. We have two cases in total.

1. $x\in A_0$

$x \in A_0 \implies x \in X-Y \implies X-Y \not \subseteq A \setminus \{x\} \implies X-Y \not \subseteq B \implies B \notin \mathcal{F}.$

1. $x\in A_{n+1}$

$A_n \subseteq A \implies A_n \subseteq B \implies f(A_n) \subseteq f(B) \implies A_{n+1} \subseteq f(B) \implies x \in f(B)$.

$x \in f(B)$ and $x \notin B \implies f(B) \not \subseteq B \implies B \notin \mathcal{F}.$

To sum up, we have proved that $A$ is an element of $\mathcal{F}$ and that if we remove any $x$ from $A$, the set $A \setminus \{x\}$ no more belongs to $\mathcal{F}$. Thus $A$ is the minimal element of $\mathcal{F}$.

• Here you should emphasize more what you are asking (it is not obvious at first sight that you want a complete check). It would perhaps be better to split it into two questions, given the length. – Arnaud Mortier Aug 11 '18 at 13:16
• Hi @ArnaudMortier, I have edited to show that I would like a complete check because, at the end, I also prove the connection between these two approaches :) – LE Anh Dung Aug 11 '18 at 14:25