Exercise 5.1.10

Proof. Suppose that $X$ is a set with a countable subset $Y$. Then by Exercise 5.1.9 $Y$ is Dedekind infinite so that there is a $Z\subset Y\subseteq X$ such that there is a bijective $f:Y\to Z$. So define the following $g:X\to X$ by

for any $x\in X$. Now since $Z\subset Y$ there is a $y\in Y$ such that $y\notin Z$, noting that since $Y\subseteq X$, $y\in X$.

First we claim that $y\notin \mathrm{ran}(g)$. So suppose that it is so that there is an $x\in X$ such that $g(x)=y$. If $x\in Y$ then by definition $g(x)=f(x)=y$, but this is a contradiction since $f:Y\to Z$ but $y\notin Z$. On the other hand if $x\notin Y$ then we have $g(x)=x=y$, which is also a contradiction since $y=x\in Y$. Since a contradiction follows in either case it must be that there is no such $x$ so that $y\notin \mathrm{ran}(g)$. Hence $\mathrm{ran}(g)\subset X$.

Clearly $g$ is a surjective map from $X$ to $\mathrm{ran}(g)$ so we now show that it is injective. So consider any $x_1,x_2\in X$ where $x_1\ne x_2$.

Case: $x_1\in Y$ and $x_2\in Y$. Then

since $f$ is injective.

Case: $x_1\notin Y$ and $x_2\notin Y$. Then

Case: $x_1\in Y$ and $x_2\notin Y$. Then $g(x_1)=f(x_1)\in Z$ but $g(x_2)=x_2\notin Y$ so that $x_2\notin Z$ either since $Z\subset Y$. Hence $f(x_1)\ne x_2$ so that

Thus in all cases $g(x_1)\ne g(x_2)$ so that $g$ is injective since $x_1$ and $x_2$ were arbitrary.

Therefore we have shown that $g$ is a bijective map from $X$ to $\mathrm{ran}(g)\subset X$ so that $X$ is Dedekind infinite by definition. □