1
$\begingroup$

Hofstadter in his book Gödel, Escher, Bach is describing Godel's contradiction of sufficiently powerful versus complete. In the chapter 13 BlooP, FlooP, and GlooP he writes,

Now although completeness will turn out to be a chimera, TNT is at least complete with respect to primitive recursive predicates. In other words, any statement of number theory whose truth or falsity can be decided by a computer within a predictable length of time is also decidable inside TNT. (p418)

Hofstadter uses the previously introduced systems called TNT and BlooP as the base of his argument. He continues,

So the question really is, Can upper bounds always be given for the length of calculations [his definition of primitive recursive predicates]--or, is there an inherent kind of jumbliness to the natural number system, which sometimes prevents calculation lengths from being predictable in advance? The striking thing is the latter is the case, and we are about to see why. [...] In our demonstration, we will use the celebrated diagonal method by George Cantor, the founder of set theory. (p418)

Hofstadter's proof begins with a set of functions understood to be primitive recursive functions called Blueprograms {#N}[N]. To my understanding this is an array with index {#N}, accepting the value [N] as an argument.

Then to form the proof (within the section titled "The Diagonal Method") Hofstadter adds +1 to it, and finally assigns this value to a new function called Bluediag[N]:

Bluediag[N] = 1 + Blueprogram {#N}[N]

He concludes that simply by adding +1 to the set Blueprograms the new set (or superset) called Bluediag lies outside the realm of primitive recursive functions. (p420) Thus demonstrating it is likely impossible to test for primitive recursive functions.

This may all be well and good. If true--to my mind--its due to the paradoxical or loopy nature of recursion, and not to Cantor's diagonal method for real numbers. My modest understanding of the orders of infinity says that adding +1 to infinity does not change the size of infinity. This is the Hilbert Hotel non-intuitive Paradox says infinity + infinity = infinity.

See also Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers?

  • 0
    These middle chapters have many referential details back to TNT, MU. Its hard to summarize such a complex argument. Its so un-chunky.2011-11-11

5 Answers 5

6

Perhaps a further example will serve to confuse you even more.

Consider Euclid's classical argument for the infinitude of primes. Suppose $p_1,\ldots,p_n$ is a finite list of all primes. Then $P = p_1 p_2 \cdots p_n + 1$ must have a prime factor different from $p_1,\ldots,p_n$, since by design, none of these can be factors of $P$.

Euclid's argument is also a sort of "diagonal argument", since $P$ is constructed to be "different" than the given list of primes; though $P$ is not a prime itself, so this is actually a "generalization" of the diagonal argument.

When people say "diagonal argument", they don't mean Cantor's particular proof of $\mathbb{Q} < \mathbb{R}$, but rather some idea, some proof technique, which is only loosely defined. And yet, the concept is useful, and the experienced mathematician will be quite content when told that a certain statement "can be proved by diagonalization"; if she really wanted and had the time, she could probably reconstruct the argument.

Oftentimes, the set to which an element is proven not to belong, this set is indeed countable. But Cantor's argument was generalized by Cantor himself to show that $S < 2^S$, for any $S$ (modern technicalities ignored). The power of the method lies in its general applicability.

I vividly recall taking a course on the theory of computation. One section was devoted to "reducibility and diagonalization". The section gave some example of these very important concepts and techniques. Perhaps something of that sort will help you make up your own mind whether mathematicians are justified when they draw attention to the similarity between Cantor's original argument and ones like Hofstadter mentions.

  • 0
    However, I am _really_ naive. I have separated what I still don't know about recursion from what the author is saying. More importantly I'm aware of how he has been delivering his arguments throughout the whole of his book with very limited systems such as --p--q---- and MIU. Adding awareness of the bijection fact, and this is where the question comes from. I hope that helps you understand my remarks. Peace.2011-11-15
5

Hofstadter is referring to diagonalisation in general, as also used by Gödel. He doesn't mean the specific diagonalisation argument that Cantor used to prove the uncountability of the real numbers.

  • 0
    Will you elaborate on your answer? Hilbert's Hotel suggests a simple system using natural numbers is fully capable of accounting for every possible index. Why does *any* diagonal argument apply in a discussion of a simple programmatic system?2011-11-09
2

I just reread the section again, and you are correct that it is not a literal diagonalization, but rather mimics the approach of the Cantor diagonalization, in that it establishes that one item which should be in a list of items cannot be, and thus the list can never be complete. According to this Wikipedia entry on the diagonal lemma, this idea is called "diagonal" due to this resemblance to Cantor's argument. Presumably Hofstadter is using diagonal in this sense.

  • 0
    My concern is not the diagonal argument per se. Its the changing from natural to real number argument in the context of the authors more than considerable work to avoid reals in his fictitious systems (I'm sure I mentioned here he doesn't include division in TNT) up to this point. After your comment, I've reread several passages and realize the author seems to imply the catalog is finite, yet he never mentions it explicitly. (I could quote passages on p418 if anyone cares). Regardless, without speaking of cardinality or the purpose of Cantor's proofs on infinity, I still find it suspect.2011-11-15
2

The argument he gives is the standard proof that there are functions that are not primitive recursive. The same argument is given in here, and in textbooks. So no, he's not cheating.

You should read the section "What does a diagonal argument prove?" on p-$422$. You start with a list, and then show that there must be an element that isn't in the list. In Cantor's argument, this is used as a proof by contradiction: the supposition that you could create a countable list of all real numbers must have been false. In the present case, the list was all primitive recursive functions, and what the argument shows is simply that there are functions which are not primitive recursive. In Cantor's argument, the element produced by the diagonal argument is an element that was meant to have been on the list, but can't be on the list, hence the contradiction. In the present case, all we're trying to show is that there are functions that aren't on the list.

  • 3
    Well, the fact that the proof is a textbook standard and has been accepted for some time might cause one to suspect that Hofstadter is doing something reasonable and that it is _you_ that is missing something. The proof uses the same idea as Cantor's original argument: we have a list, each member of which can be construed as an infinite sequence, which is exhaustive, but we construct an item not on the list by altering the $n$'th component of the $n$'th item on the list. It looks (to me) like the exact same thing.2011-11-12
0

To 'see the diagonal', form an image in your mind of a two-dimensional matrix, indexed by the natural numbers on both dimensions (hence infinite on both dimensions). Let the matrix entry (i, j) be the pair [$B_i$, #j], where $B_i$ is (the interpretable source-coded of) the primitive-recursive program 'Blueprogram[i]', and #j is (the textual value of) the number j. If you pick an arbitrary entry (i, j), you can interpret $B_i$ operating on argument #j and get back a value.

Then Hofstadter invites you to consider this program:

Bluediag(N) = { Let p = entry($B_N$, N); let y = [result of interpreting p]; return y + 1; }

The 'diagonalization' is the fact that N is being used as the value of both i and j to get the entry (i, j).