David Madore's WebLog: Gödel was here

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #0856 [older| permalink|newer] / ↓Entrée #0856 [précédente| permalien|suivante] ↓


Gödel was here

I've just learned of this mathematical result which I guess I could nominate as the most elegant theorem of all times (though probably the most useless ever). Actually, I had already read the statement in Douglas Hofstadter's Gödel, Escher, Bach a long time ago, but I hadn't paid much attention to it then; and now (in the course of thinking carefully about Gödel's incompleteness theorem, Löb's theorem, iterated Gödelization and self-consistency statements) I figured out how to prove it, and the proof is simply wonderful. I can't remember at the time whose name is associated to it (it is not Gödel), but here goes the theorem:

Theorem: This statement is a theorem.

That's all. Statement T merely states that T is a theorem (say, of first-order Peano arithmetic); and T is, in fact, true (and is a theorem: for once, we don't have to distinguish T being true and T being a theorem, because the two are exactly identical, by definition of T!). This sound provokingly much like the famous riddle:

Q: What is the ultimate question in the Universe, and what is its answer?

A: The ultimate question is that which you have just asked and its answer is that which I have just given.

So maybe we can try proving statement T by saying something like this is the proof of statement T — but any mathematician will see that this is a fraud (error 42: attempting to apply a fixed point operator on proofs!). Yet the proof that works is not entirely different either, but it is more intricate, a cleverly crafted jewel.

I won't give that proof here, though. I believe any mathematician who correctly understands Gödel's theorem (not just in the handwaving way it is sometimes — and to much damage — explained to laymen) should be able to have the pleasure of figuring the proof by himself, and anyone who does not understand Gödel's theorem sufficiently well would miss the point entirely. But maybe I'll write a little survey on the incompleteness theorem(s) sometime soon, which would try to go through all the subtleties and intricacies of how it works (e.g., do we need the set of axioms to be Σ1, or does arithmetically definable suffice? why?) and what happens when we try to push it to its limits (iterating Gödelization and reflexions to transfinite heights as Solomon Feferman has done in the most brilliant way); in which case I would also, as a matter of course, give a proof of the above-mentioned theorem. Just so people can't accuse me of lacking the appropriate rigor, here is the (“Quine-unfolding”) mathematically precise way of stating T:

Fix a usual Gödel numbering scheme (of the language of first-order arithmetic). Let P(n) be the predicate such that, for any predicate Q(n) with Gödel number ⌜Q⌝, P(⌜Q⌝) asserts the existence of a proof, in the first-order theory of Peano's axioms, of “Q(⌜Q⌝)” (that is, of the statement obtained by substituting Q's Gödel number, ⌜Q⌝, in place of the free variable). Then we have P(⌜P⌝) [and the proof works in first-order Peano arithmetic].

As an extra bonus, we can do everything in intuitionist logic (that the proof of the above statement can be given in intuitionist logic is trivial, since in the end we exhibit a proof; but actually we can replace the statement by the stronger statement that this statement is provable in intuitionist logic and the statement is again true — and indeed provable in intuitionist logic).

↑Entry #0856 [older| permalink|newer] / ↑Entrée #0856 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]