Proof of The Set of Pairs of Natural Numbers is Countable

Let $(T_{k})_{k\in\mathbb{N}}$ be the sequence of triangular numbers and define

Below, claim numbers for addition on $\mathbb{N}$ refer to Arithmetic of Addition on the Natural Numbers and claim numbers for the order on $\mathbb{N}$ to Properties of the Order on the Natural Numbers.

Step 1: $h$ is injective. Let $(m,n),(m',n')\in\mathbb{N}\times\mathbb{N}$ with $h(m,n)=h(m',n')$, and put $k=m+n$ and $k'=m'+n'$. By claim 6 of the order lemma, $m<m+n=k$ and likewise $m'<k'$.

Suppose $k<k'$. By claim 7 of the order lemma there is $j\in\mathbb{N}$ with $k'=k+j$, and $1\le j$ by claim 4, so $k+1\le k+j=k'$ by claim 6. If $k+1=k'$ then $T_{k+1}=T_{k'}$, and if $k+1<k'$ then $T_{k+1}<T_{k'}$ by claim 3 of Triangular Numbers; in either case $T_{k+1}\le T_{k'}$. Using $T_{k+1}=T_{k}+k+1$ (claim 2 of that lemma) and claim 6 of the order lemma repeatedly,

Here the second inequality is claim 6 applied to $T_{k}+k$ and the summand $1+m'$, after rearranging $T_{k}+k+1+m'$ as $(T_{k}+k)+(1+m')$ by associativity and commutativity (claims 3 and 4 of the addition lemma); the third uses $m<k$: writing $k=m+i$ with $i\in\mathbb{N}$ (claim 7) and rearranging by claim 3, $T_{k}+k=(T_{k}+m)+i>T_{k}+m$ by claim 6. This contradicts $h(m,n)=h(m',n')$, so $k<k'$ is impossible; exchanging the roles of the two pairs shows $k'<k$ is impossible as well. By trichotomy (claim 3 of the order lemma), $k=k'$.

Consequently $T_{k}+m=T_{k}+m'$, so $m=m'$ by commutativity and cancellation (claims 4 and 5 of the addition lemma). Then $m+n=k=k'=m+n'$ gives $n=n'$ in the same way. Hence $h(m,n)=h(m',n')$ implies $(m,n)=(m',n')$.

Step 2: conclusion. $\mathbb{N}$ is countable by claim 1 of Basic Properties of Countable Sets. Applying claim 5 of that lemma to the injective map $h:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ shows that $\mathbb{N}\times\mathbb{N}$ is countable.