Non-Empty Set of Natural Numbers with no Greatest Element is Denumerable
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
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $3$: The Natural Numbers: $\S 8$ Definition by finite recursion: Exercise $8.1$