Subset of Natural Numbers is either Finite or Denumerable

Theorem

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

Then $S$ is either finite or denumerable.

Proof

Let $\omega$ denote the set of natural numbers as defined by the von Neumann construction.

By the Well-Ordering Principle, $\omega$ is well-ordered by the $\le$ relation.

Thus from the Well-Ordering Principle, $S$ has a smallest element.

Let this smallest element of $S$ be denoted $s_0$.

Also from the Well-Ordering Principle, every subset of $S$ also has a smallest element.

This theorem requires a proof. In particular: establish a sequence where $s_k$ is the smallest element of $S_k$ where $S_k = S_{k - 1} \setminus \set {s_{k - 1} }$, and then build a mapping $f$ such that $\map f {s_k} \to \set {s_0, s_1, \ldots, s_{k - 1} }$ and show it's progressing, or something, but it's tedious. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $3$: The Natural Numbers: $\S 7$ Denumerable classes: Exercise $7.1$