Munkres Introduction to Topology: Section 7 Problem 6


Part A

Given sets $A$ and $B$, with $B \ \subset \ A$, we wish to prove that if there is an injection $f : A \ \rightarrow \ B$, then $A$ and $B$ have the same cardinality, meaning that there is a bijection between them. Munkres gives us a lot of help in figuring out exactly how to do this. We define $A_1 \ = \ A$ and $B_1 \ = \ B$. We then define recursive formulas for $n \ > \ 1$, which is given by $A_n \ = \ f(A_{n \ - \ 1})$ and $B_n \ = \ f(B_{n \ - \ 1})$. We assert that a bijection $h : A \ \rightarrow \ B$ is defined by:
$$h(x) \ = \ \begin{cases} f(x) & \text{if} \ x \ \in \ A_n \ - \ B_n \ \text{for some} \ n \\ x & \text{otherwise} \end{cases}$$

We then prove that this function is $1$-to-$1$ and onto. Let us pick two elements of $A$, $a$ and $b$. Let us assert that $f(a) \ \neq \ f(b)$. Clearly, if both $a$ and $b$ are in $A_n \ - \ B_n$ for some $n$, then $h(a) \ = \ f(a)$ and $h(b) \ = \ f(b)$. Since $f$ is injective, it follows that $f(a) \ \neq \ f(b)$ and thus $h(a) \ \neq \ h(b)$. The same is true if both unique $a$ and $b$ are mapped under $h(x) \ = \ x$, as this function is also injective. Now, consider the case where $a \ \in \ A_n \ - \ B_n$ and $b$ is not. We must prove that $f(a) \ \neq \ b$. It is true that in the case of an injective function, we have $f(A \ - \ B) \ = \ f(A) \ - \ f(B)$. It follows that $f(a) \ \in \ f(A_n) \ - \ f(B_n) \ = \ A_{n + 1} \ - \ B_{n + 1}$. But by definition, $b \ \not\in \ A_{k} \ - \ B_{k}$ for any $k$, so it can't be in $A_{n + 1} \ - \ B_{n + 1}$. Thus we have proved that $f(a) \ \neq \ b$, or else we arrive at a contradiction.

Next, we have to prove that $h$ is surjective. Let's pick some $x \ \in \ B$. Let's also assume that $x \ \not\in \ A_k \ - \ B_k$ for any $k$. Well, in this case, it follows that $h^{-1}(x) \ = \ x$, so for $x \ \in \ B$, we know that $x \ \in \ A$ is a point that maps to it.

Now, let's consider each set $A_k \ - \ B_k$, for all $k$. By the recursive definition, we have:
$$f(A_k \ - \ B_k) \ = \ f(A_k) \ - \ f(B_k) \ = \ A_{k + 1} \ - \ B_{k \ + \ 1}$$ This implies that $A \ - \ B \ \rightarrow \ A_2 \ - \ B_2$, then $A_2 \ - \ B_2 \ \rightarrow \ A_3 \ - \ B_3$, and so on, for all positive integers. Thus, for some $x \ \in A_n \ - \ B_n$, it is true that $x \ \in \ f(A_{n - 1} \ - \ B_{n \ - \ 1})$, meaning that $x \ \in \ B$ must be the image of some point $y \ \in \ A_{n \ - \ 1} \ - \ B_{n \ - \ 1} \ \subset \ A$. With both cases accounted for, we have proved that for any $x \ \in \ B$, there exists some point $y \ \in \ A$ such that $f(y) \ = \ x$. Thus, $h$ is surjective and injective, making it a bijection.


Part B

Theorem 1 (Schroeder-Bernstein). Given sets $A$ and $C$, if there exist injections $f : A \ \rightarrow \ C$ and $g : C \ \rightarrow \ A$, then $A$ and $C$ have the same cardinality.
Let us consider the image of $C$ under $g$, which we denote by $g(C)$. Since $g$ is injective, it follows that the function given by $g : C \ \rightarrow \ g(C)$ is a bijection. We wish to prove that there exists some injective map from $A$ to $g(C)$. Consider the composite function $g \ \circ \ f$, where $g$ is the range-restricted bijection from $C$ to $g(C)$. The composite of two injections is also an injection, thus we have an injection from $A$ to $g(C) \ \subset \ A$. By Part A, it follows that $A$ and $g(C)$ have the same cardinality. This implies that there is a bijection $h : g(C) \ \rightarrow \ A$. It follows that $(h \ \circ \ g) : C \ \rightarrow \ A$ is a bijection, which implies that $A$ and $C$ have the same cardinality.