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!


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

  • $\begingroup$ Great answer! Thank you so much for pointing our such sloppy points! $\endgroup$ – Le Anh Dung Sep 15 '18 at 1:14

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.