Infinite Set of Natural Numbers is Countably Infinite

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ be the set of natural numbers.

Let $S$ be an infinite subset of $\N$.


Then $S$ is countably infinite.

That is, there is a bijection $f: \N \to S$.


Proof

By Infinite Set has Countably Infinite Subset, we have an injection $g: \N \to S$

But by Cantor-Bernstein-Schröder Theorem/Lemma this produces a bijection $f: \N \to S$

$\blacksquare$

Sources