# Infinite Set of Natural Numbers is Countably Infinite

## 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$