Finite and Infinite Sets and Alphabets

A finite set is one that has n members, for some natural number n; this definition seems to do just fine. But what about infinite sets? How can they be defined? This is not an easy question. One possible answer, given to us by the late, great mathematician Dedekind, is to say that an infinite set is one that can be ``paired off" with a proper subset of itself. For example, consider N. A proper subset of this set is the set E of even natural numbers {0, 2, 4, 6,...}. The natural numbers, N, can be paired off with E:

$$0 \: \: 0, 1 \: \: 2, 2 \: \: 4, 3 \: \: 6, \ldots$$

Though this is a promising way to characterize infinite sets, it is nonetheless somewhat controversial, and we will not affirm it. We will instead say simply that infinite sets are those sets that are not finite. However, the general notion that the ``size" of set can be based on the notion of pairing off is one that we will affirm -- but we will make this notion a bit more precise. We will formalize the concept of pairing off through the term equinumerous; two sets A and B will be said to be equinumerous provided that there is a bijective function (or, as we can say, a bijection) $f : A \longrightarrow B$. A set that is equinumerous with N is said to be countably infinite; a set that is either countably infinite or finite is said to be countable.

We now prove a theorem related to countability that will prove useful later on. This theorem pertains to alphabets, which are simply sets of symbols. For example, {0, 1} is an alphabet, as is {a, b, c, $\ldots$, z}, which is an alphabet speakers and readers of English will be rather familiar with. The length of the alphabet {0, 1} is 2; the length of the second example just given is of course 26.

Theorem 2.1   Let $\Sigma$ be a finite alphabet $\{a_1, a_2, \ldots, a_n\}$. Then $\Sigma^\ast$, the (infinite) set of all strings that can be generated by concatenating a finite number of symbols from $\Sigma$, is countably infinite.

Proof. The elements of $\Sigma^\ast$ can be listed in lexicographic order, in which first the strings of length 1 are listed, then the strings of length 2, and so on. Within the sub-listing of strings of length m, we proceed in ``dictionary" fashion, taking advantage of the fact that in $\Sigma$ a_i precedes a_j iff i < j. Here is how the list looks (where e is the empty string):

$$e, a_1, \ldots, a_n, a_1 a_1, a_1 a_2, \ldots, a_2 a_1, a_2 a_2, \ldots, a_n a_n, a_1 a_1 a_1, \ldots$$

This list defines a bijective function f from N to $\Sigma^\ast$:

$$f(0) = e, f(1) = a_1, f(2) = a_2, \ldots$$

QED

What if the alphabet in question is not finite, but countably infinite? Is the set of all strings over such an alphabet itself countably infinite? We now show in graphical fashion that the answer is ``Yes." That is, we show:

Theorem 2.2   Let $\Sigma$ be a countably infinite alphabet. Then $\Sigma^\ast$ is countably infinite.

Proof. To start, note that it can be established that the set of strings of length 1 over $\Sigma$ is countably infinite, that the set of strings of length 2 over $\Sigma$ is countably infinte, and, generalizing, that the set of strings of length n over $\Sigma$ is countably infinite. (These lemmas are left to the reader as exercises.) Suppose that these results are represented in the form of the appropriate lists, that is, a list of strings of length 1, a list of strings of length 2, of length 3, $\ldots$ of length n. Arrange these lists as rows in an array:

$$\begin{array}{c\vert ccccc} \mbox{length 1} & u^1_1 & u^1_2 ... ...\\ \vdots & \vdots & \vdots & \vdots & \vdots &\\ \end{array}$$

We can weave through this array in a ``triangular" pattern that produces a list which ``hits" every element of $\Sigma^\ast$. Here is the start of this list:

$$u^1_1, u^2_1, u^1_2, u^3_1, u^2_2, u^1_3, u^4_1, u^3_2, u^2_3, u^1_4, \ldots$$

At this point you may wonder: Are all infinite sets countably infinite? Cantor proved that the answer is ``No." Here is his famous proof.

Theorem 2.3 (Cantor's Theorem)   The power set of the positive integers -- 2^Z+ -- is not countably infinite.

Proof. Notice that all countably infinite sets can be listed in a sequence that starts with the first element of the set, then passes to the second, and then the third, and so on; we can thus say that such a set is enumerable. Now, suppose, for contradiction, that the set in question is enumerable. Then there is an infinite list enumerating all of P^*:

$$L \, = \, S_1, S_2, S_3, \ldots$$

Now define the set

$$\bar{D}(L) \, = \, \{n \in Z^+ \, : \, n \not\in S_n \}$$

Since $\bar{D}(L)$ is a set of positive integers, it turns up somewhere in the list L; so let it be S_m, for some positive integer m. That is, $\bar{D}(L) \, = \, S_m$. But then the particular positive integer m is in $\bar{D}(L)$ if and only if m is not in S_m (by the definition of $\bar{D}(L)$. Now, since $\bar{D}(L) \, = \, S_m$, it follows that

$$m \in \bar{D}(L) \: \mbox{iff} \: m \not\in \bar{D}(L).$$

This is a contradiction. QED.