Countable sets and Kleene star

In this article I will give examples of countable sets and informally illustrate why they are countable. Also, I will show a less well-known fact, which is that the Kleene star of a countable set is countable.

The set of natural numbers is the infinite set \( \mathbb{N} = \{ 0, 1, 2, 3, \ldots \} \). A set \(S\) is called countable iff there exists an injective function \(f : S → \mathbb{N}\). In other words, it must be possible to map each element in \(S\) to a unique natural number.

Basic sets

Finite sets

Every finite set \(S\) is countable. Simply map each element in \(S\) to a unique number in \( \{0, 1, \ldots, |S| - 1 \} \).

Subsets

If \(T\) is a countable set and \(S\) is a subset of \(T\), then \(S\) is countable. This is because for \(S\), we can use the same injective function that was used to prove that \(T\) is countable.

The integers (\(\mathbb{Z}\))

The set of integers is \( \mathbb{Z} = \{ \ldots, -2, -1, 0, 1, 2, \ldots \} \). The natural numbers are contained in the set of integers, i.e. \( \mathbb{N} ⊂ \mathbb{Z} \). However, even with these additional numbers, the integers are countable. We can interleave the positive integers with the negative integers to yield a sequence that is infinite only on one side. To map every integer to a unique natural number, we map 0 to 0, 1 to 1, −1 to 2, 2 to 3, −2 to 4, 3 to 5, −3 to 6, and so on.

Pairs of natural numbers (\( \mathbb{N} × \mathbb{N} \))

The set of pairs of natural numbers includes elements like (0, 0), (0, 1), (2, 0), (4, 3). While this set may look “doubly infinite”, it is in fact countable. The key observation is that for any natural number \(c\), there are only a finite number of pairs \( (a, b) \) where \( a + b = c \). This is because \(a\) and \(b\) are nonnegative, which restricts the range of choices. In fact, there are exactly \(c + 1\) such pairs. For example, there is one pair whose elements sum to 0, which is (0, 0). There are two pairs whose elements sum to 1, which are (0, 1) and (1, 0). There are three pairs whose elements sum to 2, which are (0, 2), (1, 1), and (2, 0).

To map pairs to natural numbers injectively, do the following: Map the pairs with the sum of 0 to the lowest natural numbers. Namely, map (0, 0) to 0. Next, map the pairs with sum 1, in ascending order of the first element, to the next available natural numbers. So map (0, 1) to 1 and map (1, 0) to 2. Continue like this, mapping the pairs with sum \(k\), in ascending order of the first element, to the next natural numbers. Every pair will be mapped eventually, because every pair has a finite sum.

Corollary: If \(S\) is a countable set, then \(S × S\) is also countable.

Rational numbers (\(\mathbb{Q}\))

Each rational number \(x\) can be expressed as a fraction \(a / b\), where \(a\) and \(b\) are integers and \(b \neq 0\). So there is an injective function that maps rational numbers to pairs of integers. The set of integers is countable, thus the set of pairs of integers is countable, and the set of rational numbers is countable.

Kleene star of sets

A string is a finite sequence of items. We will use the notation \( (a_0, a_1, \ldots, a_{n-1}) \) to denote a string of length \(n\). The Kleene star of a set \(S\) is \(S^*\), which is the set of all strings whose elements are drawn from \(S\).

For example, for the set \(S = \{\text{a}, \text{b}\}\), we have \(S^* = \{ (), (\text{a}), (\text{b}), (\text{a}, \text{a}), (\text{a}, \text{b}), (\text{b}, \text{a}), (\text{b}, \text{b}), (\text{a}, \text{a}, \text{a}), \ldots \}\).

Finite sets

For each finite non-empty set \(S\), the set \(S^*\) is infinite. Letting \(a ∈ S\) be some arbitrary element, \(S^*\) is infinite because it contains arbitrarily long strings of \(a\), among other things: \( (), (a), (a, a), (a, a, a), (a, a, a, a), \ldots \). But \(S^*\) is countable, because for each \(n ∈ \mathbb{N}\), there are only a finite number of strings of length \(n\); in fact, there are \(|S|^n\) of them. So to map each string in \(S^*\) to a unique natural number, simply map each string of length 0 to the lowest natural numbers (starting with 0), then map each string of length 1 to the next lowest natural numbers, then map each string of length 2, and so on.

Countable sets

If \(S\) is a countably infinite set, we can show that \(S^*\) is still countable. But we cannot use the same argument as above for finite sets, because there is an infinite number of strings of each length.

First of all, let’s restrict ourselves the case where \(S\) is \(\mathbb{N}\). (In the general case where \(S\) is an arbitrary countable set, we use the injective function \(f\) to map its elements to natural numbers.)

For each string \((a_0, a_1, \ldots, a_{n-1}) ∈ \mathbb{N}^*\), consider the sum of all the elements plus the length of the string, and call this number as the “class” of the string. The key observation is that for each \(k ∈ \mathbb{N}\), there are a finite number of strings in \(\mathbb{N}^*\) of class \(k\). This is because for a string \(s\) to have class \(k\), the length of \(s\) must be less than or equal to \(k\), and each element in \(s\) must be less than or equal to \(k\). So there are at most \(k^k\) strings of class \(k\).

With this fact, we can construct an injective mapping in the same way as before. We map each string of class 0 to the lowest natural numbers, then we map each string of class 1 to the next lowest natural numbers, then class 2, and so on.