Subset of Natural Numbers is Cofinal iff Infinite

From ProofWiki
Jump to: navigation, search

Theorem

Consider the ordered set $\left({\N, \le}\right)$, where $\le$ is the usual ordering on the natural numbers.

Let $S \subseteq \N$.


Then $S$ is cofinal if and only if it is infinite.


Proof

From Rule of Transposition, we may replace the only if statement by its contrapositive.

Therefore, the following suffices:


Implication

Suppose $S$ is infinite.

Let $n \in \N$ be an arbitrary natural number.

We have that $\N_n = \left\{{m \in \N: m \le n}\right\}$ is a finite set.

By Subset of Finite Set is Finite, it is not the case that $S \subseteq \N_n$.

Hence, as $\le$ is a total ordering, there exists a $s \in S$ such that $n \le s$.

Hence, as $n$ was arbitrary, $S$ is cofinal.

$\Box$


Contrapositive Implication

Suppose now that $S$ is finite.

As $\le$ is a total ordering, $S$ has a maximal element.

Let this maximal element of $S$ be $N$.

Then as $N + 1 \not \le N$, from transitivity of $\le$ and maximality of $N$:

$\forall s \in S: N + 1 \not \le s$

Hence $S$ is not cofinal.

$\blacksquare$