Subset of Naturals is Finite iff Bounded

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then $X$ is finite iff 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 iff $X$ is bounded above.

That is, iff:

$\exists p \in \N: \forall x \in X: x \le p$


Necessary Condition

Let $X$ be finite.

Then $X = \left\{{x_1, x_2, \ldots, x_n}\right\}$ 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 = \left\{{0, 1, \ldots, p}\right\}$ of $\N$.

It follows from Subset of Finite Set is Finite that $X$ is finite.

$\blacksquare$


Sources