Exercise 5.1.9

Proof. Since $X$ and $Y$ are equipotent there is a bijective $f:X\to Y$ so that $f^{-1}$ is also bijective. Also since $Y$ is Dedekind infinite there is a $Z\subset Y$ such that there is a bijective $g:Y\to Z$ so that $g^{-1}$ is also bijective. So since $Z\subset Y$ there is a $y\in Y$ such that $y\notin Z$. So let $S=X-\left\{f^{-1}(y)\right\}$. Clearly since $f^{-1}(y)\in X$ it follows that $S\subset X$ since $f^{-1}(y)\notin S$. Now define $h:X\to S$ by

for $x\in X$. Since $f$ is a function this implies that

Now suppose for a moment that there is an $x\in X$ such that $h(x)=f^{-1}(y)$. Then

which is impossible since $y\notin Z$ but $\mathrm{ran}(g)\subseteq Z$. Hence there is no such $x$ so that $h$ really is a map from $X$ to $S$ (as opposed to $X$ to $X$).

Now, since $f^{-1}$, $g$, and $f$ are all injective it follows from Exercise 2.3.5 that $h$ is injective as well. Then consider any $s\in S$ and let $x=f^{-1}(g^{-1}(f(s)))$, noting that $g^{-1}(f(s))$ exists since $s\ne f^{-1}(y)$. Then we have

so that $h$ is surjective since $s$ was arbitrary. Hence $h$ is a bijective map from $X$ to $S$, and since $S\subset X$ this means that $X$ is Dedekind infinite. □

Proof. Let $N=𝑵-\left\{0\right\}$ so that clearly $N$ is proper subset of $𝑵$. Then we define the map $f:𝑵\to N$ by

for $n\in 𝑵$. Consider any $n,m\in 𝑵$ where $n\ne m$. Then clearly

so that $f$ is injective. Now consider any $n\in N$ so that clearly $f(n-1)=(n-1)+1=n$, noting that since $n\ne 0$ we have $n\ge 1$ so that $n-1\ge 0$. Hence $n-1\in 𝑵$. This shows that $f$ is surjective. Hence $f$ is a bijection from $𝑵$ onto a proper subset $N$ so that by definition $𝑵$ is Dedekind infinite. □

Proof. Suppose that $X$ is a countable set. Then by definition $X$ is equipotent to $𝑵$. Hence since $𝑵$ is Dedekind infinite (Lemma 2) it follows that $X$ is as well by Lemma 1. □