I follow on here from the initial article on cardinality. In that article, we have seen that \(\mathbb N\) contains an infinite countable subset whose complement is also infinite. Namely the subsets of even and odd integers.

Let’s now consider the set \(\mathbb N \times \mathbb N\). \(\mathbb N \times \mathbb N\) contains a countable infinite number of copies of \(\mathbb N\), as for all \(i \in \mathbb N\), \(\{i\} \times \mathbb N \subset \mathbb N \times \mathbb N\). Surprisingly, it is however possible to define a bijection between \(\mathbb N \times \mathbb N\) and \(\mathbb N\).

\(\mathbb N \times \mathbb N\) is equinumerous to \(\mathbb N\)

Consider the map \[\begin{array}{l|rcl}
\varphi : & \mathbb N \times \mathbb N & \longrightarrow & \mathbb N\\
& (n,m) & \longmapsto & 2^{n-1} (2m-1) \end{array}\] \(\varphi\) is one-to-one. Suppose that \(2^{n_1-1} (2m_1-1) = 2^{n_2-1} (2m_2-1)\). If \(n_1=1\), we must also have \(n_2=1\) as \(2 m_1 – 1\) is odd. That implies \((n_1,m_1)=(n_2,m_2)\). Let’s now suppose \(n_1 >1\). According to Euclid’s lemma, \(2^{n_1-1}\) divides \(2^{n_2-1}\) as \(2^{n_1-1}\) is even and \(2m_2 – 1\) odd. By symmetry \(2^{n_2-1}\) also divides \(2^{n_1-1}\). Finally, \(2^{n_1 – 1} = 2^{n_2 – 1}\), \(n_1 = n_2\) and consequently \(m_1 = m_2\).

\(\varphi\) is also onto. \(1\) is the image of \((1,1)\) under \(\varphi\). Let’s consider \(r > 1\) integer. According to the unique factorization theorem, \[r=p_1^{r_1} p_2^{r_2} \cdots p_s^{r_s}\] where \(p_1 < \dots < p_s\) is an increasing sequence of primes and \(r_1, \dots, r_s\) positive integers. If \(p_1 = 2\), we get \(r = 2^{(r_1 + 1)-1}(2 \cdot 1 - 1)\) or \(r = 2^{(r_1 + 1)-1}(2 m - 1)\) with \(2m - 1 = p_2^{r_2} \cdots p_s^{r_s}\) depending on whether \(s =1\) or \(s >1\). And if \(p_1 > 2\) we can write \(r = 2^{1 – 1} (2m-1)\) with \(2m-1 = p_1^{r_1} p_2^{r_2} \cdots p_s^{r_s}\) as \(p_1^{r_1} p_2^{r_2} \cdots p_s^{r_s}\) is odd. We have proven that any \(r \in \mathbb N\) has a pre-image under \(\varphi\).

It is possible to define a bijection between \(\mathbb N\) and \(\mathbb N \times \mathbb N\) in a more intuitive way by “counting” the elements of \(\mathbb N \times \mathbb N\) along diagonals as suggested in the image of the article.

To follow on, it’s time to introduce the Schröder–Bernstein theorem which states that for two sets \(E, F\), if there exist a one-to-one map from \(E\) to \(F\) and a one-to-one map from \(F\) to \(E\), there exists a bijection from \(E\) to \(F\).

Based on Schröder–Bernstein theorem, we can move to next paragraph.

\(\mathbb Q\) is equinumerous to \(\mathbb N\)

On one hand, the map
\[\begin{array}{l|rcl}
\varphi_1 : & \mathbb N & \longrightarrow & \mathbb Q\\
& n & \longmapsto & n \end{array}\] is obviously one-to-one.

On the other hand the map \[\begin{array}{l|rcll}
\varphi_2 : & \mathbb Q & \longrightarrow & \mathbb N\\
& 0 & \longmapsto & 0 &\\
& \frac{p}{q} & \longmapsto & 2^p(2q-1) & \mathrm{gcd}(p,q)=1, p >0\\
& \frac{p}{q} & \longmapsto & 2^{-p}(2q-1)+1 & \mathrm{gcd}(p,q)=1, p <0 \end{array}\] is also one-to-one. We can therefore conclude according to Schröder–Bernstein theorem that \(\mathbb Q\) is equinumerous to \(\mathbb N\). This can seem surprising as \(\mathbb Q\) is also dense in \(\mathbb R\), which means that for any \(x < y\) in \(\mathbb R\), one can find \(q \in \mathbb Q\) with \(x < q < y\). While this is clearly not true for \(\mathbb N\).