Countable Unions of Countable Sets

Combining Countable Listings

A countable family of countable sets can be gathered into a single countable set. The useful construction is to list each set along a row of an array, then scan the array along successive diagonals. This scan reaches every cell after finitely many steps, even though each row and the collection of rows may be infinite. Since different cells can contain the same element, we also need a precise way to keep repetitions from causing a problem.

We use \(\mathbb{N}=\{1,2,\ldots\}\). A set is countable if it is finite or can be put in bijection with \(\mathbb{N}\). We consider sets \(A_n\), one for each \(n\in\mathbb{N}\). A listing of a nonempty countable set \(A_n\) will mean a sequence whose terms belong to \(A_n\) and which contains every element of \(A_n\) at least once. For an infinite countable set this can be a bijective listing; for a nonempty finite set, repeat its elements so that the sequence continues indefinitely.

The assumption about selecting listings matters. In the usual set theory with the axiom of choice, one may choose a listing for each of the countably many nonempty sets. More specifically, the choice needed here is countable choice: choosing one suitable listing for each set in a countable family. If the listings are already specified, no additional choice is needed in the construction below. If the union is empty, it is countable immediately, so for the rest of the proof suppose the union is nonempty and choose \(u\in\bigcup_{n\in\mathbb{N}}A_n\).

Write the selected listing of a nonempty \(A_n\) as \(a_{n,1},a_{n,2},a_{n,3},\ldots\). If \(A_n\) is empty, put \(a_{n,m}=u\) for every \(m\in\mathbb{N}\). Thus every array entry belongs to the union, and every element of every nonempty \(A_n\) occurs in its row. The entries in a row for an empty set are only placeholders; they do not assert that \(u\in A_n\).

The Diagonal Scan and Its Proof

View \(a_{n,m}\) as the entry in row \(n\), column \(m\). Scan first the cells with \(n+m=2\), then those with \(n+m=3\), then \(n+m=4\), and so on. Within each diagonal, scan in increasing order of the row number \(n\). The beginning of the cell order is \((1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\ldots\).

Every cell is reached: the cell \((n,m)\) lies on the diagonal with sum \(n+m\), and there are only finitely many cells on all diagonals up to that one. To turn this scan into a sequence, let \(g(k)\) be the entry in the \(k\)-th cell scanned. Thus \(g:\mathbb{N}\to\bigcup_n A_n\) is defined at every positive integer.

Proof. Let \(x\in\bigcup_{n\in\mathbb{N}}A_n\). By the definition of union, \(x\in A_n\) for some \(n\). That set is nonempty, and its listing contains \(x\), so \(a_{n,m}=x\) for some \(m\in\mathbb{N}\). The cell \((n,m)\) occurs in the diagonal scan, so for its scan index \(k\) we have \(g(k)=a_{n,m}=x\). Hence every element of the union occurs in the sequence. \(\square\)

The scan sequence may repeat values, so it need not itself be a one-to-one listing. For each \(x\) in the union, however, there is a least \(k\in\mathbb{N}\) such that \(g(k)=x\), because every nonempty subset of \(\mathbb{N}\) has a least element. Sending \(x\) to this first index gives an injection from the union into \(\mathbb{N}\): if two elements have the same first index, both equal the value of \(g\) at that index. By the countability criterion that a set admitting an injection into \(\mathbb{N}\) is countable, the union is countable. Equivalently, scan \(g\) and retain a value only at its first occurrence. This produces a list of the union with no repetitions; the list is finite if only finitely many distinct values occur and otherwise is indexed in order by an infinite subset of \(\mathbb{N}\).

Worked Diagonal Scans

Why the Scan Order Matters

A tempting alternative is to finish the first row, then move to the second row, and continue in that order. That does not give a scan of an infinite array: an infinite first row is never finished, so the procedure never reaches the second row. The diagonal order avoids this problem because every cell has a finite diagonal number \(n+m\), and only finitely many cells precede it.

Common pitfall. A second mistake is to claim that the diagonal sequence itself is a one-to-one enumeration. In the identical-row example, the scan begins \(1,2,1,3,2,1,\ldots\), so \(1\) and \(2\) both appear more than once. The correction is to retain each value only at its first occurrence. This does not remove any element from the union: every element occurs somewhere by the claim, and its first occurrence is retained. It does remove all repetitions, because any later occurrence has an earlier index with the same value.

There are two different sources of repetition. A single row may repeat elements when it lists a finite set indefinitely. Also, different sets may overlap, so the same element may occur in different rows. First-occurrence suppression handles both at once; the proof only uses that each union element appears at least once in the scanned sequence.

The result is useful whenever a construction produces a countable list of countable pieces and a single list of all their elements is needed. The crucial ingredients are a listing for each row and an order of cells that reaches every row-column pair. The argument does not require the sets to be disjoint, infinite, or nonempty individually. If there are only finitely many nonempty sets, the same construction applies after the empty sets are included as rows; suppressing repetitions then yields a finite list when the union is finite.