example, that we subtract 1 from the diagonal digits (with the convention that 1
taken from 0 is 9). Then our number d will be:.0 2 7 9Now, because of the way we constructed it,
Hence,d's 1st digit is not the same as the 1st digit of r(l);
d's 2nd digit is not the same as the 2nd digit of r(2);
d's 3rd digit is not the same as the 3rd digit of r(3);... and so on.
d is different from r(l);
d is different from r(2);
d is different from r(3);
... and so on.In other words, d is not in the list'What Does a Diagonal Argument Prove?Now comes the crucial difference between Cantor's proof and our proof-
it is in the matter of what assumption to go back and undo. In Cantor's
argument, the shaky assumption was that such a table could be drawn up.
Therefore, the conclusion warranted by the construction of d is that no
exhaustive table of reals can be drawn up after all-which amounts to
saying that the set of integers is just not big enough to index the set of reals.
On the other hand, in our proof, we know that the directory of Blue BlooP
programs can be drawn up-the set of integers is big enough to index the
set of Blue BlooP programs. So, we have to go back and retract some
shakier idea which we used. And that idea is that Bluediag [N] is calculable
by some program in BlooP. This is a subtle difference in the application of
the diagonal method.
It may become clearer if we apply it to the alleged "List of All Great
Mathematicians" in the Dialogue-a more concrete example. The diagonal
itself is "Dboups". If we perform the desired diagonal-subtraction, we will
get "Cantor". Now two conclusions are possible. If you have an unshakable
belief that the list is complete, then you must conclude that Cantor is not a
Great Mathematician, for his name differs from all those on the list. On the
other hand, if you have an unshakable belief that Cantor is a Great
Mathematician, then you must conclude that the List of All Great
Mathematicians is incomplete, for Cantor's name is not on the list! (Woe to
those who have unshakable beliefs on both sides!) The former case corre-
sponds to our proof that Bluediag [N] is not primitive recursive; the latter
case corresponds to Cantor's proof that the list of rea Is is incomplete.(^422) BlooP and F100P and GlooP