How Do I Prove the Cantor-Bernstein Theorem?

[Usagi]

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.

 

[caffeinemachine]

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.

Define, for each $y\in Y$, a cahin $D_y$ as
$$\ldots,g^{-1}(f^{-1}(y)),f^{-1}(y),y,g(y),f(g(y)),\ldots$$

Note that, then $C_x=D_{f(x)}$.

Similarly $D_y=C_{g(y)}$ ---(1)

Now to tackle the question at hand.

Say, for simplicity $g^{-1}(x_0)$ is an element in $Y$ which is not in $f(X)$.

Then from $(1)$ we know that $D_{g^{-1}(x_0)}=C_{x_0}$.

Write $y=g^{-1}(x_0)$.
So we see that $D_y=C_{x_0}$.
This is precisely what we needed.

Using an induction argument you can prove the above in the general case.

 

[Opalg]

You may find that the diagram and explanation given here helps you to visualise the structure of the proof.