# Subset of Countably Infinite Set is Countable

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.

This needs considerable tedious hard slog to complete it.In particular: formal justificationTo 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 `{{Finish}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

## Also see

## Sources

- 1964: Steven A. Gaal:
*Point Set Topology*... (previous) ... (next): Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability - 1968: A.N. Kolmogorov and S.V. Fomin:
*Introductory Real Analysis*... (previous) ... (next): $\S 2.2$: Countable sets: Theorem $1$ - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Mappings: $\S 15 \eta$ - 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.10$