Cantor's Zigzag

In these notes, I discuss Cantor's famous "zigzag" argument.

Theorem. \(\mathbb{N} \cong \mathbb{N} \times \mathbb{N}\).

Proof. Consider the following figure.

Given an element \((x, y) \in \mathbb{N} \times \mathbb{N}\), we may conceive of this element as an integral coordinate on a discrete grid with the origin as point \((0,0)\). The sum \(x+y\) is invariant along each diagonal extending from a point on the "x" axis to a point on the "y" axis and indicates the index of the respective diagonal, where the diagonal at index \(0\) is the degenerate diagonal consisting only of the origin point \((0,0)\). Diagonal \(i\) contains exactly \(i+1\) points. Thus, the point \((x,y)\) is preceded by exactly \(k=x+y\) diagonals, which contain a total of \(\sum_{i=1}^k i = \frac{k(k+1)}{2}\) points. The point \((x,0)\) therefore occurs at index \(\frac{k(k+1)}{2}\) along the "zigzag" (since we begin at index \(0\)) and the point \((x,y)\) therefore is offset from \((x,0)\) by \(y\) indices. Thus, we may define a function \(f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) as follows:

\[f(x, y) = \frac{(x+y)(x+y+1)}{2} + y.\]

Note that this is well-defined, since \(k(k+1)\) is even for any natural number \(k\).

We can exhibit an explicit inverse \(f^{-1} : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) as follows. First, writing \(n = f(x,y)\) and \(k=x+y\), we obtain

\[n = \frac{k(k+1)}{2} + y\]

and thus

\[y = n - \frac{k(k+1)}{2}\]

and

\[x = k - y.\]

Since \(k = x + y\), it follows that \(y \le k\). Since \(n = \frac{k(k+1)}{2} + y\), it follows that \(n \ge \frac{k(k+1)}{2}\). We may thus establish an upper and lower bound for \(n\):

• Lower bound: \(n \ge \frac{k(k+1)}{2}\);
• Upper bound: \(n = \frac{k(k+1)}{2} + y \le \frac{k(k+1)}{2} + k = \frac{k(k+3)}{2}\).

If we multiply this lower bound by \(8\) and add \(1\), we obtain

\[8n + 1 \ge 8 \cdot \frac{k(k+1)}{2} + 1 = 4k^2 + 4k + 1 = (2k+1)^2.\]

Since each expression is non-negative, taking the principal square root yields

\[\sqrt{8n + 1} \ge 2k + 1\]

and hence

\[\frac{\sqrt{8n+1} - 1}{2} \ge k.\]

Likewise, we then multiply this upper bound by \(8\) and add \(1\):

\[8n + 1 \le 8 \cdot \frac{k(k+3)}{2} + 1 = 4k^2 + 12k + 1.\]

It then follows that

\[8n + 1 \le 4k^2 + 12k + 1 \lt 4k^2 + 12k + 9 = (2k + 3)^2.\]

Since each expression is non-negative, taking the principal square root of each side of this inequality yields

\[\sqrt{8n + 1} \lt 2k + 3.\]

It then follows that \(\sqrt{8n + 1} - 1 \lt 2k + 2\) and hence

\[\frac{\sqrt{8n + 1} - 1}{2} \lt k + 1.\]

We have thus shown that

\[k \le \frac{\sqrt{8n + 1} - 1}{2} \lt k + 1,\]

which, by definition, means that

\[k = \left\lfloor \frac{\sqrt{8n+1} - 1}{2} \right\rfloor.\]

We therefore define

\[f^{-1}(n) = \left(k - \left(n - \frac{k(k+1)}{2} \right), n - \frac{k(k+1)}{2} \right).\]

Next, we confirm that \(f(f^{-1}(n)) = n\). Note the following:

\begin{align*}f(f^{-1}(n)) &= \frac{\left[\left(k - \left(n - \frac{k(k+1)}{2} \right)\right) + \left(n - \frac{k(k+1)}{2}\right) \right]\left[\left(k - \left(n - \frac{k(k+1)}{2} \right)\right) + \left(n - \frac{k(k+1)}{2} + 1\right) \right]}{2} + \left(n - \frac{k(k+1)}{2}\right) \\&= \frac{k(k+1)}{2} + \left(n - \frac{k(k+1)}{2}\right) \\&= n.\end{align*}

Finally, we confirm that \(f^{-1}(f(x,y)) = (x,y)\). As previously established,

\[x + y \le \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \lt x+y+1,\]

and hence

\[\left \lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right \rfloor = x + y.\]

Therefore:

\begin{align*}f^{-1}(f(x,y)) &= \left(\left\lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right\rfloor - \left(f(x,y) - \frac{\left\lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right\rfloor \cdot \left(\left\lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right\rfloor + 1\right)}{2}\right), f(x,y) - \frac{\left\lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right\rfloor \cdot \left(\left\lfloor \frac{\sqrt{8 \cdot f(x,y) + 1} - 1}{2} \right\rfloor + 1\right)}{2}\right) \\&= \left(x + y - \left(f(x,y) - \frac{(x + y) \cdot \left(x + y + 1\right)}{2}\right), f(x,y) - \frac{(x + y) \cdot \left(x + y + 1\right)}{2}\right) \\&= \left(x + y - \left(\frac{(x+y)(x+y+1)}{2} + y - \frac{(x + y) \cdot \left(x + y + 1\right)}{2}\right), \frac{(x+y)(x+y+1)}{2} + y - \frac{(x + y) \cdot \left(x + y + 1\right)}{2}\right) \\&= (x,y).\end{align*}

The functions \(f\) and \(f^{-1}\) are therefore mutually inverse and thus bijective. \(\square\)

It follows immediately that, if \(A\) is a countably infinite set, then \(A \cong A \times A\) since \(A \cong \mathbb{N} \cong \mathbb{N} \times \mathbb{N} \cong \mathbb{A} \times {A}\).

As a corollary, we have the following generalization.

Corollary. \(\mathbb{N}^k \cong \mathbb{N}\) for all \(k \ge 1\).

Proof. We proceed by induction on \(k\).

• Base case \((k=1)\). It is trivially the case that \(\mathbb{N}^1 = \mathbb{N} \cong \mathbb{N}\).
• Inductive step. Suppose \(\mathbb{N}^k \cong \mathbb{N}\) for some \(k \in \mathbb{N}\). Then, by definition, there exists a bijection \(f : \mathbb{N}^k \rightarrow \mathbb{N}\). We then define a function \(g : \mathbb{N}^k \times \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}\) as follows: \(g(m, n) = (f(m), n)\). This is a bijection with inverse \(g^{-1}(m, n) = (f^{-1}(m), n)\). It follows that \(\mathbb{N}^k \times \mathbb{N} \cong \mathbb{N} \times \mathbb{N}\). Since \(\mathbb{N}^{k+1} \cong \mathbb{N}^k \times \mathbb{N}\) and \(\mathbb{N} \times \mathbb{N} \cong \mathbb{N}\), it follows that \(\mathbb{N}^{k+1} \cong \mathbb{N}\). \(\square\)

It follows immediately that, if \(A\) is a countably infinite set, then \(A \cong A^k\) for all \(k \ge 1\) since \(A \cong \mathbb{N} \cong \mathbb{N}^k \cong A^k\).

The theorem also has another important corollary.

Corollary. For any disjoint countably infinite family of sets \((A_i)_{i \in \mathbb{N}}\) such that \(A_i\) is countably infinite for every \(i \in \mathbb{N}\), \(\bigcup_{i \in \mathbb{N}}A_i \cong \mathbb{N}\).

Proof. Since for all \(i \in \mathbb{N}\) the set \(A_i\) is countably infinite, by definition, there exists a bijection \(a_i : \mathbb{N} \rightarrow A_i\). We use the notation \(a_{ij} = a_i(j)\) for \(j \in \mathbb{N}\). We then define a function \(f : \mathbb{N} \times \mathbb{N} \rightarrow \bigcup_{i \in \mathbb{N}}A_i\) as follows:

\[f(i, j) = a_{ij}.\]

Injectivity. Suppose that \(f(i, j) = f(i', j')\). Then \(a_{ij} = a_{i'j'}\), \(a_{ij} \in A_i\) and \(a_{i'j'} \in A_{i'}\). Since the family is disjoint, it follows that \(A_i = A_{i'}\) and hence \(i = i'\). Then, \(a_i(j) = a_i(j')\), and, since \(a_i\) is injective, it follows that \(j = j'\). Thus \((i,j) = (i',j')\) and \(f\) is injective.

Surjectivity. Suppose \(a \in \bigcup_{i \in \mathbb{N}}A_i\). Then, by definition of union, and since the family is disjoint, there exists a unique index \(i\) such that \(a \in A_i\). Since the function \(a_i : \mathbb{N} \rightarrow A_i\) is surjective, there exists an index \(j \in \mathbb{N}\) such that \(a_i(j) = a\). Thus, \(f(i,j) = a_{ij} = a\) and \(f\) is surjective.

Since \(f\) is both injective and surjective, it is bijective. Thus \(\bigcup_{i \in \mathbb{N}}A_i \cong \mathbb{N}\). \(\square\)