Exercise 5.1.8

Proof. For a set $X$ suppose that $f:X\to X$ is injective. Also suppose that $\mathrm{ran}(f)$ is a proper subset of $X$.

Now suppose that $X$ is finite so that there is an $n\in 𝑵$ such that there is a bijective $g:n\to X$. We also note that clearly $g^{-1}:X\to n$ is also a bijection. Now define a function $h:n\to n$ by

for any $k\in n$. Since $g$, $f$, and $g^{-1}$ are all injective it follows from Exercise 2.3.5 that $h$ is also injective.

We now claim that $\mathrm{ran}(h)$ is proper subset of $n$. First we note that for any $m\in n$ we have

since $g$ is a function. Now, since $\mathrm{ran}(f)\subset X$ there is an $x\in X$ such that $x\notin \mathrm{ran}(f)$. So let $k=g^{-1}(x)$ so that $g(k)=x$. Now suppose that there is an $m\in n$ such that $h(m)=k$. Then per the above we have

which is impossible since $x\notin \mathrm{ran}(f)$. So it must be that there is no such $m$ so that $k\notin \mathrm{ran}(h)$ Hence since $k\in n$ it follows that $\mathrm{ran}(g)\subset n$.

Now clearly $h$ is a surjective mapping from $n$ to $\mathrm{ran}(h)$. But since $h$ is also injective it is thus a bijection from $n$ to $\mathrm{ran}(n)$. However, according to Lemma 4.2.2 there is no bijective mapping from $n$ to $\mathrm{ran}(n)$ since $\mathrm{ran}(h)\subset n$. We have thus arrived at a contradiction so that, if the hypotheses hold, then $X$ cannot be finite. Hence by definition $X$ is infinite. □