Proof. We prove that if \(A\) and \(B\) are disjoint countably infinite sets, then \(A \cup B\) is also countably infinite by showing that there is a bijection between the natural numbers and \(A \cup B\). Since \(A\) and \(B\) are countably infinite, there are bijections between them and the natural numbers. Let those bijections be \(f : A \to \mathbb {N}\) and \(g : B \to \mathbb {N}\), respectively. Now we define a new function \(h : A \cup B \to \mathbb {N}\) by

To show that \(h\) is an injection, we show that \(h(x) = h(y)\) implies that \(x = y\). So suppose \(x\) and \(y\) are elements of \(A \cup B\) such that \(h(x) = h(y)\). Notice that \(h\) produces an even number for elements of \(A\) and an odd number for elements of \(B\), so if \(h(x) = h(y)\), \(x\) and \(y\) are both elements of the same set. Suppose both are elements of \(A\). Then \(h(x) = 2 f(x)\) and \(h(y) = 2 f(y)\), so we have \(2 f(x) = 2 f(y)\), or \(f(x) = f(y)\). Now since \(f\) is a bijection, this implies \(x = y\). Similarly, if \(x\) and \(y\) are both elements of \(B\), \(2 g(x) - 1 = 2 g(y) - 1\), and again \(g(x) = g(y)\) and so \(x = y\).

To show that \(h\) is a surjection, we show that for any natural number \(n\), there is some \(x \in A \cup B\) such that \(h(x) = n\). So let \(n\) be a natural number, and consider two cases, namely \(n\) is even and \(n\) is odd.

If \(n\) is even, we need an \(x \in A\) such that \(2 f(x) = n\), or \(f(x) = \tfrac {n}{2}\). Since \(n\) is even and a natural number, \(\tfrac {n}{2}\) is a natural number. Since \(f\) is a bijection it is also a surjection, and thus there is some \(x \in A\) for which \(f(x) = \tfrac {n}{2}\), and so in turn \(h(x) = n\).

On the other hand, if \(n\) is odd, then we seek an \(x \in B\) such that \(2 g(x) - 1 = n\). Algebra gives us

Now since \(n\) is odd, \(n+1\) is even, and therefore \(\tfrac {n+1}{2}\) is a natural number. Now since \(g\) is a surjection, there is indeed an \(x \in B\) such that \(g(x) = \tfrac {n+1}{2}\) and thus \(h(x) = n\).

We have now shown that \(h\) as defined by (1) is a bijection from \(A \cup B\) to \(\mathbb {N}\), which in turn means that \(A \cup B\) is countably infinite. We have therefore proven that if \(A\) and \(B\) are disjoint countably infinite sets, then \(A \cup B\) is also countably infinite. □

Proof. We assume that \(A\) and \(B\) are countably infinite sets, and will show that \(A \times B\) is countably infinite. Since \(A\) and \(B\) are countable, they have the form \(A = \{A_1,A_2,A_3,\ldots \}\) and \(B = \{B_1,B_2,B_3,\ldots \}\). We can then imagine writing the Cartesian product as a table whose rows correspond to elements of \(B\) and columns to elements of \(A\), like so:

We then match every pair in the product with a natural number by traversing the table along lower-left-to-upper-right diagonals, starting in the upper left corner: \((A_1,B_1)\) forms the first diagonal, \((A_1,B_2)\) and \((A_2,B_1)\) the second, and so forth. We assign natural numbers to pairs in the order we reach those pairs in this traversal. Notice that this matching is a bijection. It is an injection because if two pairs match the same natural number, then they must appear in the same place in the traversal, i.e., they must be equal. The matching is also a surjection because any pair lies on some diagonal, and since every diagonal is finite the traversal will eventually reach that diagonal and pair and match the pair to a natural number.

We have now established a bijection between \(A \times B\) and the natural numbers, and thereby shown that if \(A\) and \(B\) are countably infinite sets then \(A \times B\) is countably infinite. □