Exercise Real Analysis

Question

I'm having trouble to understand the following exercise I would appreciate any help?

Let $A,B,C$ be sets such that $A\subseteq B\subseteq C$ and let $f:C\rightarrow A$ be an injective map. Define the sets $D_0, D_1, ...$ recursively by setting $D_0:=B\backslash A$, and $D_{n+1}:=f[\,D_n\,]$ for all the natural numbers. Prove that the sets are all disjoints to each other. Also show that if $g: A\rightarrow B$ is a function defined by setting $g(x)= f^{-1}(x)$ when $x\in \bigcup_{n=1}^\infty D_n$, and $g(x)=x$ when $x\in A\backslash \bigcup_{n=1}^\infty D_n$ and is a bijection between the two.

For the first part, I've tried to use induction but I have some problems to do the last step. Here is what I have so far.

(1) First we have to show that $D_n\cap D_{n+1}=\varnothing$ for all $n$.

For the base case suppose by contradiction that $D_0\cap D_1 \not= \varnothing$. Then there is some $x\in D_0$ and $x\in D_1$, i.e., $x\in B\backslash A$ and $x\in f[\,B \backslash A \,]$, so we have $x= f(y)$ for $y\in B\backslash A \subseteq C$. But then $f(y)\in A$ by definition of $f$, which contradicts that $x = f(y)\in B\backslash A$.

Now suppose we have already proven the assertion for $n\ge 0$ and we may assume that $D_{n+1} \cap D_{n+2} \not= \varnothing$. Let $x \in D_{n+1} \cap D_{n+2}$. So $x = f(y)$ for $y\in D_{n}$ and $x=f^2(z)$ for $z\in D_n$. Since $f$ is 1:1, we have $y= f(z)$. Then $y=f(z)\in D_{n} \cap D_{n+1}$. But, by inductive hypothesis $D_{n} \cap D_{n+1} = \varnothing$, a contradiction.

(2) Now we have to show $D_n \cap D_{n+1+\ell}=\varnothing$ for all $\ell \in \mathbb{N}$. The base case follows from (1). We may assume that the claim is true for $\ell \ge 0$ and we will show that also hold for $\ell+1$.

By contradiction suppose that $D_n\cap D_{n+1+\ell+1} \not= \varnothing$. Let $x\in D_n\cap D_{n+1+\ell+1}$. So, $x= f^2(z)$ where $z\in D_{n+\ell}$, if we set $y = f(z)$, so $\,y \in D_{n+1+\ell}$.

And there is where I'm stuck. Some hint? I've not try yet the last part of the exercise. Thanks in advance.

Note: I'm not sure if the title is really appropriate. If someone think that is better idea to change it, for me is ok.

Answer 1

One thing to note is that the claims are trivial if $A=B,$ so suppose not.

To simplify your induction, note that for any $n\in\Bbb N,$ we have $D_{n+1}=f[D_n]\subseteq A$ (since $f:C\to A$), but $D_0=B\setminus A,$ so $D_0=B\setminus A$ is disjoint from $D_{n+1},$ being disjoint from $A.$

Now, suppose that there is some least $m\in\Bbb N$ for which there is some $n\in\Bbb N\setminus\{m\}$ such that $D_m\cap D_n\neq\emptyset.$ By the above work, we have that $0<m<n.$ Then $m=j+1$ and $n=k+1$ for some $j,k\in\Bbb N$ with $j<k,$ and there is some $y\in D_{j+1}\cap D_{k+1}.$ By our choice of $m,$ we have that $D_j\cap D_i=\emptyset$ for all $i\in\Bbb N\setminus\{j\}$ (why?), and in particular, $D_j\cap D_k=\emptyset.$ Since $y\in D_{j+1}=f[D_j],$ then $y=f(x_j)$ for some $x_j\in D_j.$ Similarly, $y=f(x_k)$ for some $x_k\in D_k.$ Since $D_j\cap D_k=\emptyset,$ then $x_j\neq x_k,$ from which we readily derive a contradiction. (Why?)

The second part is fairly straightforward. You'll need to use the first part in the proof. Let me know if you get stuck.

Answer 2

I put it here hopefully it won't be a problem.

Let define the function $g: A \rightarrow B$ as follows:

$$ x\mapsto \begin{cases} f^{-1}(x),& \text{if }\,x\in \bigcup_{i=1}^\infty D_i\\ x,& \text{if }\, x\in A\backslash\bigcup_{i=1}^\infty D_i \end{cases} $$

We claim that the function is well-defined and is a bijection. Since each $D_i$ is disjoint to each other then there is not ambiguity. Also we have $\bigcup_{i=1}^\infty D_i \subset f[C]$ and so the inverse function of $f$ exist [since is a bijection if we restrict the target set to its image ].

Suppose $x,x'\in A$ and $x\not= x'$. We will show that $g(x)\not= g(x')$, i.e., g is a $1:1$ map.

If $x,x'\in \bigcup_{i=1}^\infty D_i$, so $x=f(y_{i-1})\in f[D_{i-1}]$ and $x'=f(y_{k-1})\in f[D_{k-1}]$ for $i,k>0$. Clearly $y_{i-1}\not= y_{k-1}$ because $f$ is function. Then $g(f(y_{i-1}))=y_{i-1}$ and $g(f(y_{k-1}))=y_{k-1}$ and for what we said above the result follows. If $x,x'\in A\backslash \bigcup_{i=1}^\infty D_i$ the result is trivial. Just we need to check when $x \in \bigcup_{i=1}^\infty D_i$ and $x'\in A\backslash \bigcup_{i=1}^\infty D_i$. Then $g(x)= y_{i-1}\in D_{i-1}$ [$x= f(y_{i-1})$] and $g(x')=x'$. For the sake of contradiction suppose that $x'=y_{i-1}$. We divide the claim in two parts when $i=1$ and when $i>1$. For the former $x'=y_{i-1}\in B\backslash A$ but $x' \in A$ a contradiction. For the latter, $x'=y_{i-1} \in D_{i-1}\subset \bigcup_{i=1}^\infty D_i$ which is again a contradiction. Therefore $x'\not=y_{i-1}$.

In any case we have $g(x)\not= g(x')$. Hence $g$ is an injective map.

To conclude we have to show that $g$ is a surjective map. Let

$$z\in B= B\backslash A \cup A = B\backslash A \cup \bigg(\bigcup_{n=1}^\infty D_n \cup A \backslash \bigcup_{n=1}^\infty D_n \bigg) $$

we will show that there is some $x\in A$ such that $g(x)= z$. It is not difficult to show that the three sets are disjoints. Then we analyze the entire problem by cases again.

If $z\in B \backslash A$, so $f(z)\in f[D_0]=D_1\subseteq \bigcup_{n=1}^\infty D_n \subseteq A$ and then $g(f(z))= z$ as desired. If $z\in \bigcup_{n=1}^\infty D_n$ then we have $z\in D_i$ for $i>0$, so $f(z)\in D_{i+1} \subseteq \bigcup_{n=1}^\infty D_n \subseteq A$, furthermore $g(f(z))= z$. If $z \in A\backslash \bigcup_{n=1}^\infty D_n$, then $g(z)=z$ and we're done.

Thus the map is surjective and injective, i.e, bijective. Furthermore, $\#A =\#B$.

Corollary: (Bernstein Thm) Let $f: A \rightarrow B$, and $g: B \rightarrow A$ be injectives maps. Then, there exists a bijective map $h: A\rightarrow B$.

Proof: Clearly $f: A \rightarrow f[A]$ is a bijection. We define $\tilde h:= f \circ g$. Now, since $f[A]\subseteq B$ and $\tilde h: B \rightarrow f[A]$ is an injection then there exists a bijective map $h: f[A]\rightarrow B$ as we have shown. Hence the composition with $f$ give us the desired bijection.