Cantor pairing function

Example

The Cantor pairing function is the function $\pi \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ with $$\pi(x, y) = \frac{(x + y)(x + y + 1)}{2} + y.$$ It is a bijection. It lists the pairs along the diagonals $x + y = 0, 1, 2, \dots$: $\pi(0, 0) = 0$, $\pi(1, 0) = 1$, $\pi(0, 1) = 2$, $\pi(2, 0) = 3$.

Remarks

So $\mathbb{N} \times \mathbb{N}$ is countably infinite. See product of countable sets is countable. The value $(x + y)(x + y + 1)/2$ is the number of pairs on the earlier diagonals, and $y$ is the position on the diagonal.

Explanations

L1 human

Write the pairs $(x, y)$ in an infinite grid. Walk through the grid along the short diagonals, one after the other, and number the pairs as you go. Each pair gets exactly one number, and each number gets exactly one pair.