[proofplan]
We prove [countability](/pages/1215) in two ways. First, we construct an injection from $\mathbb{N} \times \mathbb{N}$ into $\mathbb{N}$ by encoding a pair as the exponents of the primes $2$ and $3$, then invoke the equivalent characterisation of countability by injection into $\mathbb{N}$. Second, we record the standard diagonal enumeration, which lists pairs by increasing value of $x+y$ and checks that every pair appears exactly once.
[/proofplan]
[step:Encode each pair by powers of the primes $2$ and $3$]
Define the map
\begin{align*}
f: \mathbb{N} \times \mathbb{N} &\to \mathbb{N} \\
(x,y) &\mapsto 2^x3^y.
\end{align*}
We prove that $f$ is injective. Let $(x_1,y_1),(x_2,y_2) \in \mathbb{N} \times \mathbb{N}$ and suppose
\begin{align*}
f(x_1,y_1)=f(x_2,y_2).
\end{align*}
Then
\begin{align*}
2^{x_1}3^{y_1}=2^{x_2}3^{y_2}.
\end{align*}
Since $2$ and $3$ are prime numbers, the [Fundamental Theorem of Arithmetic](/theorems/730) implies that the exponent of $2$ and the exponent of $3$ in the prime factorisation are uniquely determined. Hence $x_1=x_2$ and $y_1=y_2$, so $(x_1,y_1)=(x_2,y_2)$. Therefore $f$ is injective.
[guided]
The goal is to turn a pair of natural numbers into a single natural number without losing information. Define
\begin{align*}
f: \mathbb{N} \times \mathbb{N} &\to \mathbb{N} \\
(x,y) &\mapsto 2^x3^y.
\end{align*}
The choice of $2$ and $3$ matters because they are distinct prime numbers, so the exponents in a prime factorisation can be recovered uniquely.
To prove injectivity, take two pairs $(x_1,y_1),(x_2,y_2) \in \mathbb{N} \times \mathbb{N}$ and assume that they have the same image under $f$:
\begin{align*}
f(x_1,y_1)=f(x_2,y_2).
\end{align*}
By the definition of $f$, this means
\begin{align*}
2^{x_1}3^{y_1}=2^{x_2}3^{y_2}.
\end{align*}
The Fundamental Theorem of Arithmetic applies because both sides are natural numbers written as products of prime powers. It says that the prime factorisation of a natural number is unique, so the exponent attached to the prime $2$ must be the same on both sides, and the exponent attached to the prime $3$ must be the same on both sides. Therefore
\begin{align*}
x_1=x_2,
\qquad
y_1=y_2.
\end{align*}
Thus $(x_1,y_1)=(x_2,y_2)$. This proves that $f$ is injective.
[/guided]
[/step]
[step:Apply the injection characterisation of countability]
The set $\mathbb{N} \times \mathbb{N}$ admits the injection $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ constructed above. By the [Equivalent Characterisations of Countability](/theorems/753), any set admitting an injection into $\mathbb{N}$ is countable. Hence $\mathbb{N} \times \mathbb{N}$ is countable.
[/step]
[step:Enumerate the pairs along finite anti-diagonals]
Define a [sequence](/pages/1149)
\begin{align*}
a: \mathbb{N} &\to \mathbb{N} \times \mathbb{N} \\
n &\mapsto a_n
\end{align*}
as follows. Set $a_1=(1,1)$. If $a_{n-1}=(p,q)$ for $n \geq 2$, define
\begin{align*}
a_n =
\begin{cases}
(p-1,q+1), & \text{if } p \neq 1,\\
(p+q,1), & \text{if } p=1.
\end{cases}
\end{align*}
This lists the pairs on each finite anti-diagonal
\begin{align*}
D_s := \{(x,y) \in \mathbb{N} \times \mathbb{N} : x+y=s\},
\qquad s \in \mathbb{N},\ s \geq 2,
\end{align*}
in the order
\begin{align*}
(s-1,1),\ (s-2,2),\ \dots,\ (1,s-1).
\end{align*}
[guided]
The diagonal enumeration groups pairs according to the sum of their coordinates. For each natural number $s \geq 2$, define the finite anti-diagonal
\begin{align*}
D_s := \{(x,y) \in \mathbb{N} \times \mathbb{N} : x+y=s\}.
\end{align*}
Since $x,y \geq 1$, the elements of $D_s$ are exactly
\begin{align*}
(s-1,1),\ (s-2,2),\ \dots,\ (1,s-1).
\end{align*}
Thus $D_s$ has exactly $s-1$ elements.
We define a sequence
\begin{align*}
a: \mathbb{N} &\to \mathbb{N} \times \mathbb{N} \\
n &\mapsto a_n
\end{align*}
by starting with $a_1=(1,1)$ and then moving one step down the current anti-diagonal until the first coordinate reaches $1$. Formally, if $a_{n-1}=(p,q)$ for $n \geq 2$, set
\begin{align*}
a_n =
\begin{cases}
(p-1,q+1), & \text{if } p \neq 1,\\
(p+q,1), & \text{if } p=1.
\end{cases}
\end{align*}
When $p \neq 1$, the new pair satisfies
\begin{align*}
(p-1)+(q+1)=p+q,
\end{align*}
so it stays on the same anti-diagonal. When $p=1$, the current anti-diagonal has ended, and the next pair is
\begin{align*}
(p+q,1)=(q+1,1),
\end{align*}
which is the first element of the next anti-diagonal because its coordinate sum is $q+2=(p+q)+1$. Therefore the recursion lists the anti-diagonals $D_2,D_3,D_4,\dots$ in order, and within each $D_s$ it lists the pairs from $(s-1,1)$ down to $(1,s-1)$.
[/guided]
[/step]
[step:Show that the diagonal enumeration reaches every pair exactly once]
Let $(x,y) \in \mathbb{N} \times \mathbb{N}$, and define $s:=x+y$. Then $(x,y) \in D_s$. The anti-diagonals before $D_s$ contain
\begin{align*}
\sum_{r=2}^{s-1} (r-1)=\sum_{k=1}^{s-2} k=\frac{(s-2)(s-1)}{2}
\end{align*}
pairs. Within $D_s$, the pair $(x,y)$ appears in position $y$, since the order is
\begin{align*}
(s-1,1),\ (s-2,2),\ \dots,\ (1,s-1).
\end{align*}
Hence
\begin{align*}
a_{\frac{(s-2)(s-1)}{2}+y}=(x,y),
\end{align*}
so $a$ is surjective.
The anti-diagonals $D_s$ are pairwise disjoint because a pair $(x,y)$ has a unique coordinate sum $x+y$. Within each $D_s$, the displayed list has no repetitions because the second coordinate runs through $1,2,\dots,s-1$ exactly once. Therefore $a$ is injective. Thus $a:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ is a bijection.
[guided]
Fix an arbitrary pair $(x,y) \in \mathbb{N} \times \mathbb{N}$. Define
\begin{align*}
s:=x+y.
\end{align*}
Then $s \geq 2$ and $(x,y)$ lies on the anti-diagonal
\begin{align*}
D_s=\{(u,v) \in \mathbb{N} \times \mathbb{N}:u+v=s\}.
\end{align*}
Before the sequence reaches $D_s$, it has already listed $D_2,D_3,\dots,D_{s-1}$. Since $D_r$ has $r-1$ elements, the total number of earlier pairs is
\begin{align*}
\sum_{r=2}^{s-1}(r-1)=\sum_{k=1}^{s-2}k=\frac{(s-2)(s-1)}{2}.
\end{align*}
Inside $D_s$, the order is
\begin{align*}
(s-1,1),\ (s-2,2),\ \dots,\ (1,s-1).
\end{align*}
The pair $(x,y)$ has second coordinate $y$, so it is the $y$-th pair listed within $D_s$. Therefore
\begin{align*}
a_{\frac{(s-2)(s-1)}{2}+y}=(x,y).
\end{align*}
Because $(x,y)$ was arbitrary, every element of $\mathbb{N}\times\mathbb{N}$ appears in the sequence, so $a$ is surjective.
It remains to check that no pair appears twice. If two pairs lie on different anti-diagonals, then their coordinate sums are different, so they cannot be equal. If two entries lie on the same anti-diagonal $D_s$, then the enumeration of $D_s$ uses the list
\begin{align*}
(s-1,1),\ (s-2,2),\ \dots,\ (1,s-1),
\end{align*}
where the second coordinate takes each value in $\{1,\dots,s-1\}$ exactly once. Hence no pair repeats within a single anti-diagonal. Combining the two observations, no pair repeats anywhere in the sequence. Thus $a$ is injective, and therefore $a:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ is a bijection.
[/guided]
[/step]
[step:Conclude that the Cartesian product is countable]
The injection $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ already proves countability by the Equivalent Characterisations of Countability. Equivalently, the diagonal construction gives a bijection $a:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$, which is also one of the equivalent characterisations of countability. Therefore $\mathbb{N}\times\mathbb{N}$ is countable.
[/step]
