Section 7: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

We say that two sets $A$ and $B$ have the same cardinality if there is a bijection of $A$ with $B$ .

(a) Show that if $B\subset A$ and if there is an injection $f:A\rightarrow B,$ then $A$ and $B$ have the same cardinality. [Hint: Define $A_{1}=A$ , $B_{1}=B$ , and for $n>1$ , $A_{n}=f(A_{n-1})$ and $B_{n}=f(B_{n-1})$ . (Recursive definition again!) Note that $A_{1}\supset B_{1}$ $\supset A_{2}\supset B_{2}$ $\supset A_{3}\supset\cdots$ . Define a bijection $h:A\rightarrow B$ by the rule $h(x)=\begin{cases} f(x) & \mbox{if }x\in A_{n}-B_{n}\mbox{ for some }n,\\ x & \mbox{otherwise.]} \end{cases}$

(b) Theorem (Schroeder-Bernstein theorem). If there are injections $f:A\rightarrow C$ and $g:C\rightarrow A$ , then $A$ and $C$ have the same cardinality.

(a) The hint is actually almost the proof.

$B_{1}=B\subset A=A_{1}$ . Hence, $A_{2}=f(A_{1})\subset B=B_{1}$ and $B_{2}=f(B_{1})\subset f(A_{1})=A_{2}$ . Further, for $n\ge2$ , if $B_{n}=f(B_{n-1})\subset A_{n}=f(A_{n-1})$ $\subset B_{n-1}$ , then $B_{n+1}=f(B_{n})\subset f(A_{n})=A_{n+1}$ and $A_{n+1}=f(A_{n})\subset f(B_{n-1})=B_{n}$ . So, by induction, we get the sequence of subsets.
We show that $h$ is well-defined. For all $x\in A$ , $h(x)\in B$ , as if $x\in A-B=A_{1}-B_{1}$ then $h(x)=f(x)\in B$ , otherwise $x\in B$ , and $h(x)=x$ or $h(x)=f(x)$ , in either case $h(x)\in B$ .
We show that $h$ is bijective. Let $C_{n}=A_{n}-B_{n}$ and $X=A-\cup_{n\in\mathbb{Z}_{+}}C_{n}$ . Then all $C_{n}$ ’s and $X$ are pairwise disjoint (for $m>n$ , $C_{m}\subset A_{m}\subset B_{n}$ and $B_{n}\cap C_{n}=\emptyset$ ). The restriction of $h$ on $C_{n}$ is a bijection $h_{n}:C_{n}\rightarrow C_{n+1}$ because $f|A_{n}:A_{n}\rightarrow A_{n+1}$ and $f|B_{n}:B_{n}\rightarrow B_{n+1}$ are bijections. The restriction of $h$ on $X$ is the identity function. Since the image sets of all functions $h_{n}$ and $h|_{X}$ are pairwise disjoint, and $h(A)=X\cup\cup_{n\in\mathbb{Z}_{+}}C_{n+1}$ $=A-C_{1}=B$ , we conclude that $h$ is injective and surjective, i.e. bijective.

(b) $h:C\rightarrow f(A)\subset C$ defined by $h(c)=(f\circ g)(c)\in f(A)$ is an injection, therefore, by (a), $C$ has the same cardinality as $f(A)$ , and there is a bijection $m:f(A)\rightarrow C$ . Also, $l:A\rightarrow f(A)$ defined by $l(a)=f(a)$ is a bijection. Overall, the composite of $l$ and $m$ is a bijection of $A$ with $C$ , so that $C$ and $A$ have the same cardinality.

Subpages

Section 7: Problem 6 Solution

Section 7: Problem 6 Solution