Gödel, 2nd edition again

OK, here for download [from August, no longer available] are the opening 22 chapters (164 pages) of a draft of the 2nd edition of my Gödel book). This covers up to and including the first, Gödelian, proof of the First Incompleteness Theorem, and therefore corresponds to the opening  17 chapters (152 pages) of the original edition.

The rewriting isn’t working out as I had originally imagined. I’d thought it would be a matter of minor local tinkering with the original text, but then adding some chapters late in the book. But in fact, as I came to going carefully through the early chapters again, I felt they could do with quite a lot of work to make them more reader-friendly (and make the book more appropriate for the introductory series it is published in). So in fact there will now probably be very little space for new material in the second edition, despite an increased page budget as I expand the earlier material: but I hope the early chapters in particular will be notably more accessible.

This partial draft will be the last one I make publicly available here (though I am very open to requests from those who are keen to have the chance to comment on later chapters when they become available). That’s partly for the obvious copyright reasons: the press won’t be too happy if I give away yet more. But also I don’t envisage so many changes in the rest of the book (except locally in particular sections), whereas here there has been a lot of rewriting and rearrangement, and so there are no doubt a lot of new typos and thinkos that I’d really welcome being alerted to at this stage. So please please send me any comments, even if it is just a note of a trivial typo (you might well be the only person to spot it!).

If you want to focus on new material, then check out in particular the new arrangement in Chs 2, 3, 6; the treatment of induction in Ch. 9; revisions of material in Chs 11, 12; the significantly different Chs 15–17; the division of the treatment of the arithmetization of syntax into Chs 19, 20.

Given the publication schedule, I’d ideally like any comments sooner rather than later (though given I’m producing camera ready copy, I can keep on editing until quite late in the process). Thanks in advance!

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

6 Responses to Gödel, 2nd edition again

  1. Rowsity Moid says:

    I’m wondering whether it’s a good idea to have “suitably programmed computer” as part of the definition of “effectively computable” (p 15) and “effectively decidable” (p 19), especially when the clause is introduced by “that” which, strictly speaking, implies that it’s a further restriction: that not any algorithm will do; it has to be an algorithm “that a suitably programmed computer could use”.

    The formulation at the bottom of p 14 has the same problem (without the “that” part), but there, at least, it’s easily fixed: simply move the text beginning with “Such algorithmic procedures can be executed by a computing machine” out of the indented block, so that it’s clearly a comment on the definition rather than part of it. (Or put the text in parentheses.)

    Including computers in the definitions also raises the question of what “computer” means. Effective computability should not be tied to any particular formal model, but if “computer” is meant to refer to the sorts of devices we already know about and call “computers” (just idealised to remove limitations of storage, etc), then that is a particular formal model (although perhaps a disjunctive one); and if it doesn’t mean that, it needs definition in turn. Yet all the definitional work that should matter has already been done in explaining what an algorithm is.

    I also think there’s an opportunity in this part of the book to clarify (perhaps just by how things are worded, rather than by adding more text) what the Church-Turing thesis is meant to be about. Is it just a way to say all formal models will turn out to be equivalent — something needed only because we haven’t yet thought of all possible formal models? Or is it about everything we might intuitively regard as “computable” in some more general, or at least less specified, sense?

  2. Rowsity Moid says:

    One comment on chapter 18: Perhaps it’s because it’s so late at night, but I struggle to make sense of the part of iv that’s on p 133. In iv, a number was the class of all classes equinumerous with whatever we’re taking the number of. The classes in that class of classes can, it seems, be classes of anything. Classes of cats would be included. But when talking of one in v, one is the class of all classes of Fs such that …

    Why classes of Fs? (No classes of cats, presumably, would be included.) Or is F meant to vary, so that it would be the class of all classes-of-F s, for all possible Fs, such that … (And then cats would be one of the Fs?)

    Everything else in the chapter seems ok, though it’s possible I missed something.

  3. Rowsity Moid says:

    Re the Mostowski footnote on p 156, I wonder whether it’s worth quoting Mostowski, at some point, as you did in Exposition2:

    The different kinds of incompleteness proofs lead to different important corollaries. We obtain them when we investigate the problem of formalization of these proofs. It turns out that the semantical proof is not formalizable within S itself. As a corollary we obtain the important theorem that the notion of ‘truth’ for the system S is not definable within S . The syntactical proofs are on the contrary formalizable within S and studying carefully this fact we can recognize with Godel that the consistency of S is not provable by means formalizable within S.

    I think that’s a very nice way of saying how those things fit together.

    • Peter Smith says:

      Yes I really like that Mostowski quote and was planning to use it in the very next “Interlude” chapter which reviews where we have been and outline what’s coming.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>