Welcome to our community

Be a part of something great, join today!

Cantor-Bernstein Theorem proof

Usagi

Member
Jun 26, 2012
46
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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

MHB Oldtimer
Staff member
Feb 7, 2012
2,703
You may find that the diagram and explanation given here helps you to visualise the structure of the proof.