2.3 Enumerable sets

Another useful notion we will be using time and again is that of effective enumerability. As with effective decidability and effective computability, we will first explain what it means to be enumerable in principle, before moving on to the effectively so. Straight from the book:

A set $\Sigma$ is enumerable if its members can – at least in principle – be listed off in some order (a zero-th, first, second) with every member appearing on the list; repetitions are allowed, and the list may be infinite.

What this means is that you can give a (possibly infinite) list that will contain every single member of $\Sigma$ and each member is guaranteed to appear a finite number of entries into this list. The finite case is fairly obvious if $\Sigma=\emptyset$ (where $\emptyset$ denotes the empty set containing no elements) then trivially all elements of $\Sigma$ will appear on any list (say, the empty list containing no entries). If $\Sigma$ is larger, but still finite, we can imagine just going through each of the elements and listing them one by one. For example, $0, 1, 2, 3, 4, 5$ is an enumeration of the finite set $\{0,1,2,3,4,5\}$. Similarly, $0, 1, 5, 3, 4, 3, 0, 1, 2$ also enumerates $\Sigma$, although with redundancies and not in a natural order.

The tricky case is infinite lists. The condition you need to pay special attention to in this instance is that each element of $\Sigma$ must appear a finite number of entries into the list. So, for example, the following lists each enumerate $\Sigma=\mathbb N$ (where $\mathbb N$ denotes the infinite set containing all natural numbers):

1. $0, 1, 2, 3, 4, 5,\ldots$
2. $1, 0, 3, 2, 5, 4,\ldots$
3. $0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,\ldots$

Notice that in each case (assuming our patterns hold) we can determine exactly how many entries into the list a given number $n$ will appear. In 1. $n$ is in the $n^\text{th}$ position. In 2. $n$ appears $n+1$ entries down the list if $n$ is even, and $n-1$ entries down if $n$ is odd. In the third example $n$ appears $\Sigma_{i=0}^n i$ entries into the list. Note that to make the math easier, we start our counting at zero: thus, the left-most element listed is the “zero-th”, the next is the first, the next is the second and so on. Now 2. and 3. are contrived examples but the point they make is that each $n$ appears a finite number of entries into the list, and we can tell exactly how far into the list it is. Contrast that with the following non-examples:

1. $0, 2, 4, 6, ... , 1, 3, 5, 7,\ldots$
2. $100, 99, 98, 97,\ldots$
3. $1, 9, 0, 26, 82, 0, 13,\ldots$

In 1., all the odd numbers seem to appear an infinite number of places into the list. This clearly violates precisely what we’re looking at. In 2. there’s still an obvious pattern, but any number greater than 100 doesn’t seem to appear at all. Finally, in 3. there’s no clear pattern to how the numbers are being listed. It is entirely possible that this is the beginning of some valid enumeration, but without more information it’s impossible to tell. So despite the fact that $\Sigma$ is enumerable, none of these three lists are valid ways to do so.

So hopefully that gives you a bit of an intuitive notion of the idea of enumerability. For the more formally-inclined, here is how this is defined mathematically:

The set $\Sigma$ is enumerable iff either $\Sigma$ is empty or else there is a surjective (onto) function $f:\mathbb N\rightarrow\Sigma$ (so that $\Sigma$ is the range of $f$). We say that such a function enumerates $\Sigma$.

The text proves that these two definitions are equivalent, but it’s fairly straightforward, so if you’re having trouble seeing it, I suggest sitting down and working out why these two versions of enumerability come out to the same thing. It should be similarly obvious that any subset of $\mathbb N$ (finite or infinite) is also enumerable. However:

Theorem 2.1 There are infinite sets that are not enumerable.

Proof: Consider the set $\mathbb B$ of infinite binary strings (ie: the set containing strings like $011001011001..."$). Obviously $\mathbb B$ is infinite. Suppose, for the purposes of contradiction (also known as reductio) that some enumerating function $f:\mathbb N\rightarrow \mathbb B$ does exist. Then, for example, $f$ will look something like: $0\mapsto s_0:\underline{0}110010010\ldots\\1\mapsto s_1:1\underline{1}01001010\ldots\\2\mapsto s_2:10\underline{1}1101100\ldots\\3\mapsto s_3:000\underline{0}000000\ldots\\4\mapsto s_4:1110\underline{1}11000\ldots\\\ldots$

The exact values of $s_i$ aren’t important (as we will see) so this example will abstract to the general case. What we are going to do now is construct a new string, $t$, such that $t$ does not appear in the enumeration generated by $f$. We will do this by generating $t$ character-by-character. To determine the $n^\text{th}$ character in $t$ simple look at the $n^\text{th}$ character of $s_n$ and swap it. Thus, given our example enumeration above, the first 5 characters of $t$ would be $01010\ldots"$ which we get by just this method (for convenience, the $n^\text{th}$ character of each $s_n$ has been underlined). Now all we have to do is notice that $t$ will differ from each of the $s_i$‘s at precisely the $i^{th}$ position. As such, $t$ does not appear in the enumeration generated by $f$. Thus, $f$ is not an enumeration of $\mathbb B$ which contradicts our hypothesis that $\mathbb B$ is enumerable.

QED

This gives us some interesting corollaries depending on how you want to interpret the set $\mathbb B$:

For example, a binary string $b\in\mathbb B$ can be thought of as representing a real binary decimal number $0\leq b\leq 1$ (ie: $0010110111..."$ would represent $0.0010110111...$ and $0000000000..."$ would represent $0$. Thus we know that the real numbers in the interval $[0,1]$ are not enumerable  (and so neither is the set of all real numbers $\mathbb R$).

Another way to think of $\mathbb B$ is that it is the set of sets of natural numbers. To see this, interpret a given string $b=b_0b_1b_2\ldots"$ to be the set $b^\prime=\{n|b_n=1\}$, where a number $n\in b^\prime$ iff $b_n=1$ and $n\not\in b^\prime$ iff $b_n=0$. So for example, if $b=10101000111..."$ then $b^\prime=\{0,2,4,8,9,10,\ldots\}$. Thus, the set of sets of natural numbers (denoted $\mathcal P\mathbb N$) is also not enumerable.

In later chapters we will learn the notion of a characteristic function which is a function $f:\mathbb N\rightarrow\{0,1\}$ which takes a numerical property $P$ and maps $n\mapsto 0$ if $P n$ holds and $n\mapsto 1$ if $\neg Pn$ holds. (This may seem backwards, since $0$ typically denotes $\texttt{False}$ and $1$ denotes $\texttt{True}$, however we will see the reasons for this in due course.) If we consider an element $b=b_0b_1b_2\ldots"\in\mathbb B$ to describe a characteristic function $b^\prime$ by $n\mapsto b_n$, then we can observe that the set of all characteristic functions is similarly non-enumerable.

Next time we will finish up chapter 2 by discussing the limitations of what can be effectively enumerated by a computer program.