Exercise 5.1.11

Proof. Suppose that $X$ is a Dedekind infinite set. Then there is a $Y\subset X$ such that there is a bijective $f:X\to Y$. Since $Y\subset X$ there is an $x\in X$ such that $x\notin Y$. So first define $x_0=x$ and then for $n\in 𝑵$ define $x_{n+1}=f(x_n)$.

We claim that $x_n\ne x_m$ for any $n,m\in 𝑵$ where $n\ne m$, from which it clearly follows that

is a countable set. So consider any $n,m\in 𝑵$ where $n\ne m$ Without loss of generality we can assume that $n<m$. Suppose that $x_n=x_m$. We now show by induction that $x_{n-k}=x_{m-k}$ for all $n\ge k\ge 0$. If $k=0$ then we clearly have

Now suppose that $x_{n-k}=x_{m-k}$. We then have

Since $f$ is injective this implies that $x_{n-(k+1)}=x_{m-(k+1)}$ so that inductive proof is complete. So since this holds for $k=n$ we have that

Noting that $m-n-1\ge 0$ since $m\ge n+1$. But $x_0=x\notin Y$ and $f(x_{m-n-1})\in Y$ since $f:X\to Y$ so that we have a contradiction. So it must be that $x_n\ne x_m$. Hence $Z$ is countable. Since also clearly $Z\subseteq X$ the proof is complete. □