Subset of Naturals is Finite iff Bounded

From ProofWiki
Jump to navigation Jump to search


Let $X$ be a subset of the natural numbers $\N$.

Then $X$ is finite if and only if it is bounded.


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.


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.