Prob 6, Sec 7 in Munkres' TOPOLOGY, 2nd ed: The existence of an injection of a superset into the set means the sets have the same cardinality? Let $A$ and $B$ be two sets such that $B \subset A$ and there is an injection $f \colon A \to B$. Then how to show that $A$ and $B$ have the same cardinality? 
Munkres' Hint: 
We define $A_1 \colon= A$, $B_1 \colon= B$, and, for $n > 1$, we define $A_n \colon= f(A_{n-1})$ and $B_n \colon= f(B_{n-1})$. 
Thus, we have 
$$B_1 = B \subset A_1 = A$$
and 
$$A_2 = f(A_1) = f(A) \subset B = B_1,$$
that is, 
$$A_2 \subset B_1 \subset A_1.$$
Now if, for any +ive integer $n \geq 1$, we have 
$$B_{n+1} \subset B_n \subset A_n, $$
then we also have
$$B_{n+2} = f(B_{n+1}) \subset f(B_n) = B_{n+1}$$
and 
$$B_{n+1} = f(B_n) \subset f(A_n) = A_{n+1},  $$
that is, 
$$B_{n+2} \subset B_{n+1} \subset A_{n+1}.$$
Hence using induction we can conclude that
$$A_{n+1} \subset B_n \subset A_n \ \mbox{ for each } \ n \in \mathbb{N}.$$
That is, 
$$A_1 \supset B_1 \supset A_2 \supset B_2 \supset A_3 \supset B_3 \supset \ldots.$$ 
Now let the map $h \colon A \to B$ be defined as follows:
$$ h(x) \colon= 
\begin{cases} 
f(x) \ & \mbox{ if } \ x \in A_n - B_n \ \mbox{ for some } \ n; \\
x \ & \mbox{ otherwise}. 
\end{cases}
$$
Munkres claims that this map $h$ is a bijection. How do we show this? 
Injectivity of $h$: 
Suppose $a, x \in A$ such that $h(a) = h(x)$. We need to show that $a=x$. 
If there exist $m, n \in \mathbb{N}$ such that $a \in A_m - B_m$ and $x \in A_n - B_n$, then we must have 
$$f(a) = h(a) = h(b) = f(b),$$
which implies $a = b$. 
On the other hand, if $a \not\in A_n - B_n$ for any $n \in \mathbb{N}$ and $x \not\in A_n - B_n$ for any $n \in \mathbb{N}$, then we have 
$$a = h(a) = h(b) = b.$$
How to show that $a = b$ in the following situation? 
There exists some $m \in \mathbb{N}$ such that $a \in A_m - B_m$ but 
$x \not\in A_n - B_n$ for any $n \in \mathbb{N}$. 
Surjectivity of $h$: 
Let $b \in B$. 
Then $b \in A$. 
If $b \not\in A_n - B_n$ for any $n \in \mathbb{N}$, then we have 
$b = h(b)$. 
On the other hand, if, for some $k \in \mathbb{N}$, we have $b \in A_k - B_k$, then let $k$ be the smallest such positive integer. 
If $k = 1$, then we have $b \in A - B$, which is a contradiction as $b \in B$, by our hypothesis. So we must have $k > 1$; rather, $k \geq 2$. 
As $b \in A_k - B_k$ and as $A_k \subset B_{k-1}$, so we must have $b \in B_{k-1}$. What next?
 A: Since you asked me to answer here: http://dbfin.com/topology/munkres/chapter-1/section-7-countable-and-uncountable-sets/problem-6-solution/#comment-2390104583.
Step 1. We show the inclusions $A_1\supset B_1\supset A_2\supset B_2\supset\cdots$, you have already shown it in the question.
Step 2. We show that $h$ is well-defined. Indeed, 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)\in \{x,f(x)\}\subset B$, so that $h(x)\in B$.
Step 3. We show that $h$ is bijective. We split all of $A$ into "slices" $C_n=A_n−B_n$ and the rest $X=A−\cup_{n\in\mathbb{Z}_+}C_n$.
(a) All slices and $X$ are pairwise disjoint. $X$ is disjoint from any $C_n$ by definition. Further, for $m>n$, we have $C_m\subset A_m$ (by definition), $A_m\subset B_n$ by Step 1, $B_n\cap C_n=\emptyset$ by definition. Overall, we have $C_m\cap C_n=\emptyset$.
(b) The restriction of $h$ to $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}$ where $B_k\subset A_k$ are bijections.
(c) The restriction of $h$ to X is the identity function.
Since the image sets of the functions $h_n$ and $h|X$ are pairwise disjoint (by (a), (b) and (c)), $A=X\cup_{n\in \mathbb{Z}_+}C_n$ and $h(A)=X\cup_{n\in \mathbb{Z}_+}C_{n+1}=A−C_1=B$, we conclude that $h$ is injective and surjective, i.e. bijective.
A: I understand you didn't finish proving surjectivity of $h$, let me complete it. You want to prove that, that for any $b \in B$ such that $b \in (A_k - B_k)$ for some positive integer $k>1$, there exists some $\alpha \in A \; |\,h(\alpha)=b $. 
Due to $A_k=f(A_{k-1})$, $B_k = f(B_{k-1})$ and $f$ is an injective function,$A_k - B_k = f(A_{k-1}) - f(B_{k-1}) = f(A_{k-1} - B_{k-1})$. Then, $b\in f(A_{k-1} - B_{k-1})$, i.e, there exists some $\alpha\in A_{k-1}\subseteq A$ such that $f(\alpha)=b$ when $\alpha \in (A_{k-1} - B_{k-1})$, and $h(\alpha)=b$. This should complete the surjectivity proof you started.
