Tao Analysis I - 3.6.3

Exercise 3.6.3

Let $n$ be a natural number, and let $f:\{i \leq i \leq n\} \to \mathbb{N}$ be a function. Show that there exists a natural number $M$ such that $f(i) \leq M$ for all $1 \leq i \leq n$. (Hint: induct on $n$. You may also want to peel at Lemma 5.1.14.). Thus finite subsets of the natural numbers are bounded. Use this to give an alternate proof of Theorem 3.6.12 that does not use Lemma 3.6.9.

Let's remind ourselves of Theorem 3.6.12:

The set of natural numbers $\mathbb{N}$ is infinite.

Solution Part 1

We will use induction on $n$. Consider the statement $P(n)$,

$$P(n): \text{ there exists an } M \in \mathbb{N} \text{ such that for all } i \in \{1 \ldots n\} \text{ we have } f(i) \leq M$$

Consider the base case $P(0)$, which states there exists a natural number $M$ such that $f(i) \leq M$ for $i \in \emptyset$. This is vacuously true.

To avoid any doubt, let's consider $P(1)$ as a base case. It states there exists a natural number $M$ such that $f(i) \leq M$ for $i \in \{1\}$. Since $f$ maps to $\mathbb{N}$, $f(i)$ is a (finite) natural number. We can choose $M=f(1)$, thus identifying an $M$ which satisfies the statement, making $P(1)$ true.

Now let's assume $P(n)$ is true as the inductive hypothesis. We need to show $P(n++)$ is true. Consider $f(n++)$. Again, since $f$ maps to $\mathbb{N}$, we have $f(n++)$ as a finite natural number. We can select $X=f(n++)$ so that $f(n++) \leq X$. By the inductive hypothesis, we know there exists a natural number $Y$ such that $f(i) \leq Y$ for $1 \leq i \leq n$. We can choose the larger of the two, $M=\max(X,Y)$, so that $f(i) \leq M$ for $1 \leq i \leq (n++)$. Thus $P(n++)$ is true.

By induction we have shown there exists a natural number $M$ such that $f(i) \leq M$ for all $1 \leq i \leq n$. That is, finite subsets of the natural numbers, here $\{f(i)\}$, are bounded. $\square$

Solution Part 2

Let's write out what we have just shown: If a subset of the natural numbers $\mathbb{N}$ is finite, then it is bounded.

The contrapositive is: If a subset of the natural numbers is not bounded, then it is not finite.

Consider the set of natural numbers $\mathbb{N}$, which is a subset of $\mathbb{N}$. Let's assume it is finite. That means it must be bounded, as we have shown above. Let's say $M$ is the largest element in that set. This $M$ is a natural number, and by the Peano axioms, has a successor $M+1$ which is also a natural number in $\mathbb{N}$. Therefore $M$ can not be the largest element of the set. We have shown that $\mathbb{N}$ is not bounded. By the above contrapositive statement, it is therefore not finite. $\square$