Subset of Countably Infinite Set is Countable

From ProofWiki
Jump to navigation Jump to search

Theorem

Every subset of a countably infinite set is countable.


Proof

Let $S = \set {a_0, a_1, a_2, \ldots}$ be countably infinite.

Let $T \subseteq S = \set {a_{n_0}, a_{n_1}, a_{n_2}, \ldots}$, where $a_{n_0}, a_{n_1}, a_{n_2}, \ldots$ are the elements of $S$ also in $T$.

If the set of numbers $\set {n_0, n_1, n_2, \ldots}$ has a largest number, then $T$ is finite.

Otherwise, consider the bijection $i \leftrightarrow n_i$.

This leads to the bijection $i \leftrightarrow a_{n_i}$

This latter bijection is the required one-to-one correspondence between the elements of $T$ and those of $\N$, showing that $T$ is indeed countable.




Also see


Sources