Subset of Naturals is Finite iff Bounded
Theorem
Let $X$ be a subset of the natural numbers $\N$.
Then $X$ is finite if and only if it is bounded.
Proof
A subset of the natural numbers is also a subset of the real numbers $\R$.
By definition, a bounded subset of $\R$ is bounded below in $\R$ and bounded above in $\R$.
By the Well-Ordering Principle, $X$ is bounded below
Thus $X$ is bounded if and only if $X$ is bounded above.
That is, if and only if:
- $\exists p \in \N: \forall x \in X: x \le p$
Necessary Condition
Let $X$ be finite.
Then $X = \set {x_1, x_2, \ldots, x_n}$ for some $n \in \N$.
Let $p = x_1 + x_2 + \ldots + x_n$.
Thus $x \in X \implies x \le p$.
Thus $X$ is bounded above by $p$.
So by definition $X$ is bounded.
$\Box$
Sufficient Condition
Let $X \subseteq \N$ be bounded.
Then for some $p \in \N$, it is contained in the initial segment $\N_p = \set {0, 1, \ldots, p}$ of $\N$.
It follows from Subset of Finite Set is Finite that $X$ is finite.
$\blacksquare$
Sources
- 1989: Elon Lages Lima: AnĂ¡lise Real 1: Chapter $1, \S 2$