Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

ing the length of calculation of B luediag [N]. This is an "infinite conspira-

cy", related to the Tortoise's notion of "infinite coincidences", and also to

w-incompleteness. But we shall not trace out the relations in detail.

Cantor's Original Diagonal Argument

Why is this called a diagonal argument? The terminology comes from

Cantor's original diagonal argument, upon which many other arguments

(such as ours) have subsequently been based. To explain Cantor's original

argument will take us a little off course, but it is worthwhile to do so.

Cantor, too, was concerned with showing that some item is not in a certain

list. Specifically, what Cantor wanted to show was that if a "directory" of

real numbers were made, it would inevitably leave some real numbers

out-so that actually, the notion of a complete directory of real numbers is a

contradiction in terms.

It must be understood that this pertains not just to directories of finite

size, but also to directories of infinite size. It is a much deeper result than the

statement "the number of reals is infinite, so of course they cannot be listed

in a finite directory". The essence of Cantor's result is that there are (at

least) two distinct types of infinity: one kind of infinity describes how many

entries there can be in an infinite directory or table, and another describes

how many real numbers there are (i.e., how many points there are on a line,

or line segment)-and this latter is "bigger", in the sense that the real

numbers cannot be squeezed into a table whose length is described by the

former kind of infinity. So let us see how Cantor's argument involves the

notion of diagonal, in a literal sense.

Let us consider just real numbers between 0 and 1. Assume, for the

sake of argument, that an infinite list could be given, in which each positive

integer N is matched up with a real number r(N) between 0 and 1, and in

which each real number between 0 and 1 occurs somewhere down the line.

Since real numbers are given by infinite decimals, we can imagine that the

beginning of the table might look as follows:

r( 1): .1 4 1 5 9 2 6 5 3

r(2): .3 3 3 3 3 3 3 3 3

r(3): .7 8 2 8 1 8 2 8

r(4): .4 1 4 2 1 3 5 6 2

r(5): .5 0 0 0 0 0 0 0 0

The digits that run down the diagonal are in boldface: 1,3,8,2,0, ... Now

those diagonal digits are going to be used in making a special real number

d, which is between 0 and 1 but which, we will see, is not in the list. To

make d, you take the diagonal digits in order, and change each one of them

to some other digit. When you prefix this sequence of digits by a decimal

point, you have d. There are of course many ways of changing a digit to

some other digit, and correspondingly many different d's. Suppose, for

BlooP and AooP and GlooP 421