Gödel Without Tears, slowly, 13

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.)

The post Gödel Without Tears, slowly, 13 appeared first on Logic Matters.