- #1
Usagi
- 45
- 0
I am self studying real analysis and I am doing an exercise which is proving the Cantor-Bernstein Theorem.
**Question:**
Assume there exists a 1-1 function $f:X \rightarrow Y$ and another 1-1 function $g:Y \rightarrow X$. Follow the steps to show that there exists a 1-1, onto function $h:X \rightarrow Y$ and hence $X \sim Y$.
*a)* The range of $f$ is defined by $f(X) = \{y \in Y : y = f(x) \ \text{for some} \ x \in X\}$. Let $y \in f(X)$. Explain why there exists a unique $x \in X$ such that $f(x) = y$. Now define $f^{-1}(y) = x$, and show that $f^{-1}$ is a 1-1 function from $f(X)$ onto $X$. In a similar way, we can also define the 1-1, onto function $g^{-1}: g(Y) \rightarrow Y$.
*b)* Let $x \in X$ be arbitrary. Let the chain $C_x$ be the set consisting of all elements of the form:
$$\cdots, f^{-1}(g^{-1}(x)), g^{-1}(x), x, f(x), g(f(x)), f(g(f(x))), \cdots $$
Explain why the number of elements to the left of $x$ in the above chain may be zero, finite, or infinite.
*c)* Show that any two chains are either identical or completely disjoint.
*d)* Note that the terms in the chain above alternate between elements of $X$ and elements of $Y$, i.e.,
$$\cdots, \underbrace{f^{-1}(g^{-1}(x))}_{\in X}, \underbrace{g^{-1}(x)}_{\in Y}, \underbrace{x}_{\in X}, \underbrace{f(x)}_{\in Y}, \underbrace{g(f(x))}_{\in X}, \underbrace{f(g(f(x)))}_{\in Y}, \cdots \ \ \ \ \ \ \ \ \ \ (1)$$
Given a chain $C_x$, focus on $C_x \cap Y$, which is just the part of the chain that belongs to $Y$. Define the set $A$ to be the union of all chains $C_x$ satisfying $C_x \cap Y \subseteq f(X)$. Let $B$ be the set of the union of the remaining chains not in $A$. Show that any chain contained in $B$ must be of the form:
$$y, g(y), f(g(y)), g(f(g(y))), \cdots $$
where $y$ is an element of $Y$ that is not in $f(X)$.----------
**Queries:**
OK, I can do parts *a)* to *c)*, it is part *d)* which is confusing me right now. Here is my attempt so far.
Let $C_{x_0}$ be a chain in $B$, then clearly $C_{x_0} \cap Y \not \subseteq f(X)$, which means there must exist some $y \in Y$ with $y \in C_{x_0}$ such that $y \not \in f(X)$. Referring to expression $(1)$, clearly elements like $f(x_0)$, $f(g(f(x_0)))$, $\cdots$ must be an element of $f(X)$ by definition. So it must be a term of the form like $g^{-1}(x_0)$ which is not an element of $f(X)$. ----------
Now I am not exactly sure how to complete the remainder of the question, that is, the chains in $B$ must be of the form given in the question.
**Question:**
Assume there exists a 1-1 function $f:X \rightarrow Y$ and another 1-1 function $g:Y \rightarrow X$. Follow the steps to show that there exists a 1-1, onto function $h:X \rightarrow Y$ and hence $X \sim Y$.
*a)* The range of $f$ is defined by $f(X) = \{y \in Y : y = f(x) \ \text{for some} \ x \in X\}$. Let $y \in f(X)$. Explain why there exists a unique $x \in X$ such that $f(x) = y$. Now define $f^{-1}(y) = x$, and show that $f^{-1}$ is a 1-1 function from $f(X)$ onto $X$. In a similar way, we can also define the 1-1, onto function $g^{-1}: g(Y) \rightarrow Y$.
*b)* Let $x \in X$ be arbitrary. Let the chain $C_x$ be the set consisting of all elements of the form:
$$\cdots, f^{-1}(g^{-1}(x)), g^{-1}(x), x, f(x), g(f(x)), f(g(f(x))), \cdots $$
Explain why the number of elements to the left of $x$ in the above chain may be zero, finite, or infinite.
*c)* Show that any two chains are either identical or completely disjoint.
*d)* Note that the terms in the chain above alternate between elements of $X$ and elements of $Y$, i.e.,
$$\cdots, \underbrace{f^{-1}(g^{-1}(x))}_{\in X}, \underbrace{g^{-1}(x)}_{\in Y}, \underbrace{x}_{\in X}, \underbrace{f(x)}_{\in Y}, \underbrace{g(f(x))}_{\in X}, \underbrace{f(g(f(x)))}_{\in Y}, \cdots \ \ \ \ \ \ \ \ \ \ (1)$$
Given a chain $C_x$, focus on $C_x \cap Y$, which is just the part of the chain that belongs to $Y$. Define the set $A$ to be the union of all chains $C_x$ satisfying $C_x \cap Y \subseteq f(X)$. Let $B$ be the set of the union of the remaining chains not in $A$. Show that any chain contained in $B$ must be of the form:
$$y, g(y), f(g(y)), g(f(g(y))), \cdots $$
where $y$ is an element of $Y$ that is not in $f(X)$.----------
**Queries:**
OK, I can do parts *a)* to *c)*, it is part *d)* which is confusing me right now. Here is my attempt so far.
Let $C_{x_0}$ be a chain in $B$, then clearly $C_{x_0} \cap Y \not \subseteq f(X)$, which means there must exist some $y \in Y$ with $y \in C_{x_0}$ such that $y \not \in f(X)$. Referring to expression $(1)$, clearly elements like $f(x_0)$, $f(g(f(x_0)))$, $\cdots$ must be an element of $f(X)$ by definition. So it must be a term of the form like $g^{-1}(x_0)$ which is not an element of $f(X)$. ----------
Now I am not exactly sure how to complete the remainder of the question, that is, the chains in $B$ must be of the form given in the question.