Set of Doubletons of Natural Numbers is Countable

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?