Gödel! #3 An Introduction to Gödel’s Theorems 2.1

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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Trackbacks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: