Exercise 3.6.3 (Finite sets of N are bounded)

Proof.

By induction on $n$:
For $n=1$ : $M=f(1)$ so $f(1)\le M$ is satisfied.

Assume the statement holds for some $n=k\ge 1$. Let $f:\{1,\dots ,k+1\}\to \mathbb{N}$. Restrict $f$ to $\{1,\dots ,k\}$.

Then via the induction hypothesis there is $M_k\in \mathbb{N}$ with $f(i)\le M_k$ for all $1\le i\le k$.

Define

Then $M\in \mathbb{N}$ and for every $1\le i\le k+1$ we have $f(i)\le M$ (if $i\le k$ this follows from $f(i)\le M_k\le M$, and if $i=k+1$ it follows from $f(k+1)\le M$). Thus the statement holds for $n=k+1$.

By induction the statement holds for every $n\in \mathbb{N}$. Consequently, any finite subset $\{f(1),\dots ,f(n)\}\subset \mathbb{N}$ has a largest element $M$ and is bounded. □