Countable Unions

Combining Countable Sets

A countable set can be listed using natural-number labels. The next question is what happens when we have a sequence of countable sets: can all their elements be collected into one countable set? The answer is yes in the usual setting of real analysis. The basic idea is to arrange the lists in rows, use pairs of natural numbers to index all the entries, and then discard any repetitions.

The rows may overlap, and some may be empty or finite. These possibilities do not prevent a countable union. They do mean that a proof should not assume that every element appears in only one row, or that every row has infinitely many distinct elements.

The union collects the elements, not the sets themselves. For example, if \(A_1=\{a,b\}\) and \(A_2=\{b,c\}\), then \(A_1\cup A_2=\{a,b,c\}\): the shared element \(b\) occurs just once in the union. In an infinite family, elements can likewise occur in several rows.

The Countable Union Theorem

Suppose first that each nonempty set \(A_n\) comes with a surjective enumeration \(e_n:\mathbb N\to A_n\). If \(A_n\) is countably infinite, its bijection with \(\mathbb N\) is such an enumeration. If \(A_n\) is finite and nonempty, its finite list can be repeated to give a surjection from \(\mathbb N\). Empty sets need no enumeration.

Proof. Write \(U=\bigcup_{n=1}^{\infty}A_n\). If \(U=\varnothing\), then \(U\) is finite and therefore countable. Suppose instead that \(U\ne\varnothing\). By the theorem from “Countable Sets” that \(\mathbb N\times\mathbb N\) is countable, fix a bijection \(q:\mathbb N\to\mathbb N\times\mathbb N\).

For each \(x\in U\), define a set of indices

This set is nonempty. Since \(x\in U\), there is an \(n\) such that \(x\in A_n\). The set \(A_n\) is nonempty, and the surjectivity of \(e_n\) gives a \(k\in\mathbb N\) with \(e_n(k)=x\). The pair \((n,k)\) equals \(q(j)\) for some \(j\), because \(q\) is onto. That \(j\) belongs to \(J_x\).

Every nonempty subset of \(\mathbb N\) has a least element. Define \(i:U\to\mathbb N\) by letting \(i(x)\) be the least element of \(J_x\). We show that \(i\) is injective. Suppose \(i(x)=i(y)=j\). Since \(q\) is a function, there is one pair \((n,k)=q(j)\). The definition of \(J_x\) gives \(e_n(k)=x\), and the definition of \(J_y\) gives \(e_n(k)=y\). Therefore \(x=y\). Thus \(i\) is injective. By the Injection Criterion for Countability, \(U\) is countable. \(\square\)

The proof first allows entries to appear repeatedly in the combined arrangement: an element may occur in several sets, or several times in an enumeration. It then assigns that element its least index in the arrangement. This “first occurrence” rule produces distinct natural-number labels, which is exactly what the injection criterion requires.

There is a small set-theoretic point behind the theorem’s hypothesis. If we are told only that every \(A_n\) is countable, choosing one enumeration for every set in an infinite sequence is an instance of countable choice. In the usual real-analysis setting this choice is accepted. The theorem above states the proof precisely when the enumerations are given; in applications, they are often constructed explicitly.

Rows, Pairs, and Repeated Elements

The proof of the theorem uses the pairs \((n,k)\) to keep track of two choices: the row number \(n\), and the position \(k\) within that row. The earlier theorem that \(\mathbb N\times\mathbb N\) is countable tells us that these pairs can all be placed in a single sequence. The first-occurrence rule then turns this sequence of possible entries into distinct labels for the elements of the union.

The indexing in the theorem is important. A sequence of sets means that each set has a natural-number index. The sets themselves may be finite, countably infinite, empty, or repeated. If only finitely many sets are being united, the result follows, by induction on the number of sets, from the theorem on the union of two finite sets when all of those sets are finite, or from the countable union theorem by appending empty sets when they are countable.

A Useful Consequence and a Common Pitfall

Proof. For each nonempty finite \(A_n\), choose a listing of its finitely many elements and repeat the last element forever to obtain a surjection \(e_n:\mathbb N\to A_n\). Choosing a listing for every \(n\) is again an instance of countable choice, as in the theorem; if the listings are given in advance, no choice is needed. If \(A_n=\varnothing\), no enumeration is needed. The Countable Union Theorem now applies and shows that \(\bigcup_{n=1}^{\infty}A_n\) is countable. \(\square\)

This result is useful because an infinite set can be built up from finite pieces. The integers in the preceding example are obtained as the union of the finite sets \(\{-n,\ldots,n\}\). The conclusion does not say that the union is finite; it says that its elements can be assigned distinct labels from \(\mathbb N\).

A common pitfall is to argue that a union is countable merely because every one of its members belongs to some countable set, without accounting for the infinitely many sets. The theorem supplies the missing organization: pair each set index with a position in that set’s enumeration, use the countability of \(\mathbb N\times\mathbb N\), and handle repetitions. Another pitfall is assuming that a row-by-row listing must finish a row before moving on. An infinite row has no last entry, so the diagonal or paired indexing method is what ensures progress through all rows.