G
In this last (and short!) chapter related to the first incompleteness theorem, we meet ‘Tarski’s Theorem’. And so we arrive at what might be thought of as the Master Argument for incompleteness — for appropriate theories, provability-in-T is expressible in T but truth isn’t, so provability isn’t truth.
Onwards to the second theorem next week!
[Link now removed]
We get today to Chapter 13, called ‘The Diagonalization Lemma, and Rosser’s Theorem’. Not that we actually prove Rosser’s theorem in detail, as this is fiddly. But I do establish the Lemma, show how it can be used to derive the syntactic version of the first theorem again, and I indicate the key construction for getting to Rosser’s theorem.
(Looking back at Chapter 12, though, I see that the section which actually proves the first theorem there had become rather oddly arranged: I’ve rearranged a bit, separating out the theorem from a couple of corollaries worth remarking. So I’ve included a revised Chapter 12 too.)
[Link now removed]
And, at last ….
Cue drumroll …
‘The First Incompleteness Theorem, syntactic version’
This is the version of the theorem that Gödel highlights in his epochal 1931 paper, and which people usually have in mind when they talk of ‘the’ incompleteness theorem. We have to do a little more work than for the semantic version, but again — once we have grasped the trick of constructing a Gödel sentence, and understood the idea of capturing/representing/defining primitive recursive relations in a formal theory, the proof is delightfully simple. Which is not to diminish Gödel’s achievement in the slightest: on the contrary, it was very important to him that the ideas involved are straightforward to handle once you grasp them.
[Link now removed]
And at last, we get to a proof of ‘The First Incompleteness Theorem, semantic version’, uisng pretty much Gödel’s materials. And given our background work over previous chapters, it is very easy. Grasp the trick in constructing the described Gödel sentence, and everything then falls speedily and simply into place. Enjoy!
[Link now removed]
A good time to join the party, if you haven’t yet been following along with this chapter-by-chapter posting of a new version of Gödel Without (Too Many) Tears.
Along with revised versions of early chapters (thanks to all those who sent comments and corrections, a few here, and more by e-mail), here is Chapter 10, on ‘The Arithmetization of Syntax’. So this is where we get to today:
And then, over the next four chapters, we (at last) get to prove the first incompleteness theorem, in pretty much Gödel’s way. We also introduce the Diagonalization Lemma, prove Rosser’s Theorem and Tarski’s Theorem. A busy but fun week!
[Link now removed]
Today’s chapter is about ‘Expressing and capturing the primitive recursive functions’. We prove (in reasonable detail) that although the language of basic arithmetic $latex L_A$ only has the successor, addition and multiplication functions built in, we can in fact form a $latex L_A$ wff to express any primitive recursive function we pick. And then we prove (or rather, wave our arms at a proof) that even the weak Robinson Arithmetic can reprsent or ‘capture’ every primitive recursive function.
Even cutting lots of corners, this chapter is inevitably a bit fiddly. But one nice idea we meet is the use of a coding device for handling finite sequences of numbers. I try to make clear (a) how having such a device will enable us to express/capture primitive recursive functions, while (b) distinguishing the neat general coding idea from Gödel’s particular implementation of the device using his beta function.
[Link now removed]
I’ll be briefer than usual, though today’s attached episode is longer than usual. After a short Interlude (where we’ve been, where we are going), there’s a quite substantial chapter ‘Primitive Recursive Functions’. And there’s a nice diagonal argument to enjoy!
[Link now removed]
Next, we have the shortest chapter so far, on Quantifier Complexity, which introduces the notions of $latex \Delta_o, \Sigma_1$ and $latex \Pi_1$ wffs.
But there is an intriguing little result in this chapter. If the consistent theory T which includes Robinson Arithmetic Q proves a given $latex \Pi_1$ sentence, that sentence must be true. You don’t have to believe the theory T is true to accept its $latex \Pi_1$ consequences are true. For example, suppose T is the wildly infinitary apparatus that Wiles uses to prove Fermat’s Last Theorem, which is equivalent to a $latex \Pi_1$ sentence. Then you don’t have to believe that infinitary apparatus is actually correct (whatever exactly that means); all you need to believe to accept Fermat’s Last Theorem (assuming Wiles’s corrected derivation from T is correctly done) is that T is consistent. I still find that rather remarkable.
[Link now removed]
We get back to proving the First Incompleteness Theorem next week. In this week’s five chapters, we are reading into the record some necessary arithmetical background.
Everything in today’s chapter will very probably be quite familiar; but we do need to say just a little in GWT (a very little) about ‘First-order Peano Arithmetic’, the benchmark formalized theory of arithmetic. The most interesting claims (for a student who has not met them before, unlikely for a reader of this blog!) are those in the final section about non-standard models — but that brisk section is optional!
[Link now removed]
Where have we got to in this slow introduction to the incompleteness theorems? Theorem 8 from Chapter 4 tells us that if a consistent, effectively axiomatized, theory is “sufficiently strong”, then it must be negation incomplete. And we announced that even the very weak arithmetic called Robinson Arithmetic is sufficiently strong (in which case, stronger consistent, effectively axiomatized, theories must also meet the condition, and so must be incomplete). But we didn’t say anything at all about what this weak theory of arithmetic looks like! Today’s Chapter 5 explains.
So here are revised versions of Chapters 1 to 4 together with the new Chapter 5 on ‘Two weak arithmetics’. (Many thanks to those who have commented on the earlier chapters here or by email: there are quite a few small improvements as a result.)