1.
Show that \(\N^2\) is countable by constructing an explicit bijection from \(\N\) to \(\N^2\text{.}\)
Solution.
For \(r\geq0\text{,}\) let \(T_r=r(r+1)/2\) be the \(r\)-th triangular number. Given \(k\in\N\text{,}\) set
\begin{equation*}
r=r(k)=\left\lceil\frac{\sqrt{8k+1}-1}{2}\right\rceil
\quad\text{and}\quad
j=j(k)=k-T_{r-1}.
\end{equation*}
Then \(T_{r-1}<k\leq T_r\text{,}\) so \(1\leq j\leq r\text{.}\) Define \(F:\N\to\N^2\) by
\begin{equation*}
F(k)=(r-j+1,j).
\end{equation*}
The map \(F\) counts the lattice points one diagonal at a time:
\begin{equation*}
(1,1),(2,1),(1,2),(3,1),(2,2),(1,3),\ldots.
\end{equation*}
To verify that \(F\) is bijective, define \(G:\N^2\to\N\) by
\begin{equation*}
G(m,n)=T_{m+n-2}+n.
\end{equation*}
If \(F(k)=(m,n)\text{,}\) then \(m+n-1=r\) and \(n=j\text{,}\) so \(G(F(k))=T_{r-1}+j=k\text{.}\) Conversely, given \((m,n)\in\N^2\text{,}\) set \(r=m+n-1\) and \(k=G(m,n)\text{.}\) Since \(1\leq n\leq r\text{,}\) \(T_{r-1}<k\leq T_r\text{,}\) and therefore \(F(k)=(r-n+1,n)=(m,n)\text{.}\) Thus \(F\) and \(G\) are inverses, so \(F\) is a bijection and \(\N^2\) is countably infinite.
