Non-Empty Set of Natural Numbers with no Greatest Element is Denumerable

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be a non-empty set of natural numbers.

Let $A$ have no greatest element.


Then $A$ is a countably infinite set.


Proof

Aiming for a contradiction, suppose $A$ is finite.

From Subset of Naturals is Finite iff Bounded, it follows that $A$ is bounded.

Hence $A$ has a greatest element.

This contradicts the fact that $A$ has no greatest element.

Hence by Proof by Contradiction it follows that $A$ is not finite.

From Subset of Natural Numbers is either Finite or Denumerable, $A$ is a countably infinite set.

$\blacksquare$


Sources