Bottom-up proof of a lemma used to prove Bernstein-Schröder theorem

96 Views Asked by At

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


My attempts:

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


Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

1

There are 1 best solutions below

1
On BEST ANSWER

$A_0=X-Y \notin Y$, while $A_{n+1}=f(A_n) \in Y \space \forall n \in \mathbb{N}$

It should be

$A_0=X-Y \not\subseteq Y$, while $A_{n+1}=f(A_n) \subseteq Y \space \forall n \in \mathbb{N}$


Apart from this it looks good. Also, be consistent, if you use $-$ for set difference use it always, don't change it in the last line.


Also instead of

$$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$$ You can write$$\mbox{By definition we have }X-Y \subseteq A \implies X-A \subseteq X-(X-Y)=Y$$