Countable Sets

From Finite Cardinality to Countable Sets

The previous tutorial measured finite sets by matching them with standard finite sets \([n]\). We now extend the idea of comparing sets by bijections to infinite sets. The basic infinite reference set will be the natural numbers \(\mathbb N=\{1,2,3,\ldots\}\). A set matched bijectively with \(\mathbb N\) can be listed in a sequence: its first element, its second element, and so on.

There is a small convention to settle. Some authors use “countable” to mean “countably infinite,” while others include finite sets as countable. Here we use the inclusive convention. This makes finite sets part of the same general category, while the phrase “countably infinite” identifies sets that can be matched bijectively with all of \(\mathbb N\).

A bijection \(f:\mathbb N\to A\) is an enumeration of \(A\): the terms \(f(1),f(2),f(3),\ldots\) are all distinct and include every element of \(A\). In contrast, an injection into \(\mathbb N\) only assigns distinct natural-number labels to the elements of \(A\). It need not use every natural number. We will show that, for countability, having such labels is enough.

An Injection Criterion for Countability

To establish the criterion, first consider a subset \(S\) of \(\mathbb N\). If \(S\) is infinite, its elements can be listed in increasing order by repeatedly choosing the least element not yet chosen. The least-element property of the natural numbers ensures each choice is possible. The resulting list must include every element of \(S\): if \(m\in S\) were never chosen, then every chosen element would be less than \(m\), even though there are only finitely many natural numbers less than \(m\).

Proof. Define \(s_1\) to be the least element of \(S\). Once \(s_1,\ldots,s_k\) have been chosen, define \(s_{k+1}\) to be the least element of \(S\setminus\{s_1,\ldots,s_k\}\). This set is nonempty: if it were empty, \(S\) would equal the finite set \(\{s_1,\ldots,s_k\}\), contradicting that \(S\) is infinite. Thus the construction continues for every positive integer \(k\).

The terms are distinct, since each new term is chosen outside the set of earlier terms. They are strictly increasing, since \(s_{k+1}\) is the least element remaining after \(s_1,\ldots,s_k\) have been selected. Define \(e:\mathbb N\to S\) by \(e(k)=s_k\). Distinct terms show that \(e\) is injective.

It remains to show that \(e\) is surjective. Let \(m\in S\). Suppose, for contradiction, that \(m\) is never selected. At every stage \(k\), \(m\) remains among the available elements. Since \(s_k\) is the least available element, \(s_k\leq m\); and because \(m\) is never selected, \(s_k\ne m\), so \(s_k<m\). In particular, all the terms \(s_1,\ldots,s_m\) would be distinct natural numbers less than \(m\). There are only \(m-1\) such numbers, which is impossible. Therefore \(m=s_k\) for some \(k\), and \(e\) is surjective. Hence \(e\) is a bijection from \(\mathbb N\) to \(S\). \(\square\)

Proof. First suppose \(A\) is countable. If \(A\) is finite, its distinct listing gives an injection into \(\mathbb N\): send the first listed element to \(1\), the second to \(2\), and so on. If \(A\) is countably infinite, a bijection from \(\mathbb N\) to \(A\) has an inverse, which is an injection from \(A\) into \(\mathbb N\). Thus either way there is such an injection.

Conversely, suppose \(f:A\to\mathbb N\) is injective, and let \(S=f[A]\), the range of \(f\). Then \(S\subseteq\mathbb N\). The function \(f\), regarded as a map from \(A\) onto \(S\), is a bijection: it is injective by assumption and surjective onto its range by definition. Therefore \(f^{-1}:S\to A\) is also a bijection. If \(S\) is finite, a distinct listing \(s_1,\ldots,s_k\) of \(S\) pulls back through \(f^{-1}\) to the distinct listing \(f^{-1}(s_1),\ldots,f^{-1}(s_k)\) of \(A\), which includes every element of \(A\) because \(f^{-1}\) is onto \(A\). So \(A\) is finite. If \(S\) is infinite, the theorem just proved gives a bijection \(e:\mathbb N\to S\), and \(f^{-1}\circ e:\mathbb N\to A\) is a bijection. In this case \(A\) is countably infinite. Both cases show that \(A\) is countable. \(\square\)

This theorem is useful because it replaces the task of constructing a complete listing with the often simpler task of assigning distinct natural-number labels. For an infinite set, an injection into \(\mathbb N\) may leave some labels unused; the proof shows that this still gives a bijection with \(\mathbb N\).

Listing Integers and Pairs

The integers \(\mathbb Z\) are not a subset of the positive natural numbers, but they can still be assigned distinct natural-number labels. One possible ordering begins \(0,1,-1,2,-2,3,-3,\ldots\). The alternating signs prevent the negative integers from being left out.

A less immediate example is the set \(\mathbb N\times\mathbb N\) of ordered pairs of natural numbers. It may seem that an infinite grid has too many entries to list. The key is to list pairs along diagonals of constant sum. Each diagonal contains only finitely many pairs.

Proof. For each integer \(r\geq2\), list the pairs whose coordinates sum to \(r\), in this order: \((1,r-1),(2,r-2),\ldots,(r-1,1)\). Concatenate these finite lists in order of increasing \(r\). The beginning of the resulting list is \((1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\ldots\).

Every listed pair occurs exactly once. Indeed, a pair \((a,b)\) belongs to the list for the unique sum \(r=a+b\), and within that list it occurs at the unique position determined by its first coordinate \(a\). Thus no pair is repeated. Conversely, every \((a,b)\in\mathbb N\times\mathbb N\) has a sum \(r=a+b\geq2\), so it appears on that diagonal. Hence the concatenated list contains every pair exactly once. Assigning the first pair to \(1\), the second to \(2\), and so forth gives a bijection from \(\mathbb N\) to \(\mathbb N\times\mathbb N\). \(\square\)

The diagonal method works because each diagonal is finite, and the diagonals can be arranged in a sequence. Merely arranging entries row by row would not work: after finishing the first row one would never reach the second, because each row has infinitely many entries. The diagonal ordering makes progress through both coordinates.

The Rational Numbers Are Countable

The rational numbers \(\mathbb Q\) can be represented by fractions, but many fractions represent the same rational number: for example, \(1/2=2/4\). To use pairs as labels without duplication, represent each rational number in its reduced form \(p/r\), where \(p\in\mathbb Z\), \(r\in\mathbb N\), and \(p\) and \(r\) have no common factor greater than \(1\). This representation is unique when the denominator is required to be positive.

What Countability Tells Us

Countability does not mean that a set is small in the sense of being finite. The even natural numbers, the integers, and the rational numbers are all infinite, yet each can be placed in bijection with \(\mathbb N\). For these sets, the important feature is not that their elements are arranged in an obvious order, but that a complete sequence can be constructed.

A common pitfall is to assume that an infinite set cannot be counted because its listing never ends. A countable enumeration does continue indefinitely; what matters is that each element occurs at a particular finite position. Conversely, an attempted list that misses even one element is not an enumeration. The injection criterion is often the more efficient tool: it proves countability by assigning distinct natural-number labels, without requiring those labels to be used in order.