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 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 and each member is guaranteed to appear a finite number of entries into this list. The finite case is fairly obvious if (where denotes the empty set containing no elements) then trivially all elements of will appear on any list (say, the empty list containing no entries). If is larger, but still finite, we can imagine just going through each of the elements and listing them one by one. For example, is an enumeration of the finite set . Similarly, also enumerates , 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 must appear a finite number of entries into the list. So, for example, the following lists each enumerate (where denotes the infinite set containing all natural numbers):
Notice that in each case (assuming our patterns hold) we can determine exactly how many entries into the list a given number will appear. In 1. is in the position. In 2. appears entries down the list if is even, and entries down if is odd. In the third example appears 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 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:
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 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 is enumerable iff either is empty or else there is a surjective (onto) function (so that is the range of ). We say that such a function enumerates .
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 (finite or infinite) is also enumerable. However:
Theorem 2.1 There are infinite sets that are not enumerable.
Proof: Consider the set of infinite binary strings (ie: the set containing strings like ). Obviously is infinite. Suppose, for the purposes of contradiction (also known as reductio) that some enumerating function does exist. Then, for example, will look something like:
The exact values of 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, , such that does not appear in the enumeration generated by . We will do this by generating character-by-character. To determine the character in simple look at the character of and swap it. Thus, given our example enumeration above, the first 5 characters of would be which we get by just this method (for convenience, the character of each has been underlined). Now all we have to do is notice that will differ from each of the ‘s at precisely the position. As such, does not appear in the enumeration generated by . Thus, is not an enumeration of which contradicts our hypothesis that is enumerable.
This gives us some interesting corollaries depending on how you want to interpret the set :
For example, a binary string can be thought of as representing a real binary decimal number (ie: would represent and would represent . Thus we know that the real numbers in the interval are not enumerable (and so neither is the set of all real numbers ).
Another way to think of is that it is the set of sets of natural numbers. To see this, interpret a given string to be the set , where a number iff and iff . So for example, if then . Thus, the set of sets of natural numbers (denoted ) is also not enumerable.
In later chapters we will learn the notion of a characteristic function which is a function which takes a numerical property and maps if holds and if holds. (This may seem backwards, since typically denotes and denotes , however we will see the reasons for this in due course.) If we consider an element to describe a characteristic function by , 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.