The set $\omega \times \omega$ is equinumerous with $\omega$.

Question

Proposition: The set $\omega \times \omega$ is equinumerous with $\omega$, i.e. the set $\omega \times \omega$ is countable.

"Intuitive Proof"

$$\mathbb{N}^2=\{ (n,m): n,m \in \mathbb{N} \}$$

$$1 \mapsto a_{11}$$ $$2 \mapsto a_{12}$$ $$3 \mapsto a_{21}$$ $$4 \mapsto a_{31}$$ $$5 \mapsto a_{22}$$ $$6 \mapsto a_{13}$$ $$7 \mapsto a_{14}$$ $$8 \mapsto a_{23}$$ $$ \cdots \cdots \\ \cdots \cdots \\ \cdots \cdots$$

Could you explain me the intuitive proof?

Answer 1

How to order the set of ordered pairs of positive integers, from

• George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007), page 8 :

As a preliminary to enumerating them, we organize them into a rectangular array. We then traverse the array in Cantor’s zig-zag manner [indicated in a similar figure].

This gives us the list :

$(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1),\ldots$.

If we call the function involved [in the enumeration] $G$, then we have

$G(1) = (1, 1), G(2) = (1, 2), G(3) = (2, 1)$, and so on.

The pattern is: First comes the pair the sum of whose entries is $2$, then come the pairs the sum of whose entries is $3$, then come the pairs the sum of whose entries is $4$, and so on. Within each block of pairs whose entries have the same sum, pairs appear in order of increasing first entry.

It is actually possible to derive mathematical formulas for the encoding functions $J$ that go with the decoding functions $G$.

Let us take first $J$. We want $J(m,n)$ to be the number $p$ such that $G(p) = (m,n)$, which is to say the place $p$ where the pair $(m,n)$ comes in the enumeration corresponding to $G$.

[Thus we have :]

$J(m, n) = (m^2 + 2mn + n^2 − m − 3n + 2)/2$.

For instance, the pair $(3,2)$ should come in the place

$(3^2 + 2 · 3 · 2 + 2^2 − 3 − 3 · 2 + 2)/2 = (9 + 12 + 4 − 3 − 6 + 2)/2 = 18/2 = 9$

as indeed it can be seen (looking back at the enumeration as displayed above) that it does: $G(9) = (3,2)$.

Thus, the "intuitive proof" is a description of the function needed to "perform" the bijection.