Oops! A blunder in GWT

David Makinson has emailed to point out a foul-up in Episode 2, §9, of Gödel Without Tears. (Actually, he very kindly called it an “anomaly”. This suggests one of those irregular conjugations: “I made a little slip, what you wrote involves an anomaly, he or she made a terrible blunder”.)

Since I picked up the email on a train to London I had a few hours to worry about whether the same foul-up occurs in my Gödel book (in the corresponding §7.1). Phew. It doesn’t. It was indeed something too unthinkingly said as an aside in lectures, and afterwards plonked down in the notes. Which is a relief.

I’ll rewrite the relevant passage in Gödel Without Tears a.s.a.p. But here’s the basic story. Theorem 5 says: A consistent, sufficiently strong, axiomatized formal theory cannot be negation complete. Here, ‘sufficient strength’ you will recall is a matter of being able to capture or represent decidable properties of numbers, and ‘axiomatized’ of course means ‘decidably axiomatized’.

Now neither this theorem  nor the proof I gave of it  actually  delivers us a formally undecidable sentence. So it is weaker than a full Gödelian result. But I said more:

So suppose we start off with a consistent ‘sufficiently strong’ theory T couched in some language which just talks about arithmetic matters: then this theory T is incomplete, and will have arithmetical formally undecidable sentences. But now imagine that we extend T ’s language (perhaps it now talks about sets of numbers as well as about numbers), and we give it richer axioms, to arrive at an expanded consistent theory U. U will still be sufficiently strong if T is, and so Theorem 5 will still apply if it is properly axiomatized. Note, however, that as far as Theorem 5 is concerned, it could be that U repairs the gaps in T and proves every truth statable in T’s language, while the incompleteness has now ‘moved outwards’, so to speak, to claims involving U’s new vocabulary.

If that were right, it would be another way Theorem 5 is weaker than Gödel, for he shows that some incompleteness will always remain even in the theory’s arithmetical core. But it isn’t right. Sigh. Here’s David’s counter, only slightly edited:

Let T* be the set of all theorems of U in the language of T. Since T is included in T* which is included in U, we know that T* is sufficiently strong but consistent. And suppose for reductio that T* is negation complete in the language of T; we get a contradiction.

If T* is negation complete then T* must be decidable [by the same kind of argument used in proving Theorem 3]. Thus, given any sentence A in the language of T, just grind out theorems of U until you get either A or its negation (which you must, since T* is included in U and by supposition is negation complete in its language). But if T* is decidable, then it may serve as the axiom set for itself as a axiomatized formal theory. Thus T* is a consistent, sufficiently strong, axiomatized formal theory and so by Theorem 5 is not negation complete after all, giving us a contradiction.

Indeed. Oh dear, I’ve been leading the youth astray again …

This entry was posted in Gödel's theorems. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *