Set of Doubletons of Natural Numbers is Countable
Jump to navigation
Jump to search
Theorem
Let $S$ be the set defined as:
- $S = \set {\set {n_1, n_2}: n_1, n_2 \in \N, n_1 \ne n_2}$
where $\N$ denotes the set of natural numbers.
Then $S$ is countably infinite.
Proof
We can write the elements of $S \times T$ in the form of an infinite table:
- $\begin{array} {*{4}c}
\tuple {1, 0} & & & \\ \tuple {2, 0} & \tuple {2, 1} & & \\ \tuple {3, 0} & \tuple {3, 1} & \tuple {3, 2} & \\ \vdots & \vdots & \vdots & \ddots \\
\end{array}$
This table clearly contains all the elements of $S$.
Let $\set {n_1, n_2} \in S$ be written such that $n_1 > n_2$.
Then $\set {n_1, n_2}$ will be found in row $n_1$ and column $n_2 + 1$ of the table.
The index of the $n$th row is the $n$th triangular number.
Let $f: S \to \N$ be defined as:
- $\forall \set {n_1, n_2} \in S: \map f {\set {n_1, n_2} } = \dfrac {n_1 \paren {n_1 + 1} } 2 + n_2$
It is seen that $f$ is an injection.
With a little more work it can be shown to be a bijection as well, but that condition is not necessary.
The result follows.
$\blacksquare$
Sources
- 2010: Raymond M. Smullyan and Melvin Fitting: Set Theory and the Continuum Problem (revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 2$ Countable or uncountable?