What do you think of Enderton’s Mathematical Introduction to Logic?
Now I’m back from my Bahamian break, I’m intermittently doing some reading, preparing for another version of the Teach Yourself Logic Guide to be put online at the end of the month. I’ve just been taking another look at Enderton’s much used, and often recommended, A Mathematical Introduction to Logic (to which I perhaps gave rather short shrift before). It strikes me as a good book, meeting it again after a long gap, now in the guise of its second edition. But it also strikes me as tougher going than it purports to be. So my summary verdict, from the draft page-and-a-bit that I’ll be adding to the appendix on the Big Books on Mathematical Logic, is that Enderton’s Chs 1 and 2 would make good supplementary reading if you’ve already read a more user-friendly text on first-order meta-theory, and that his even-more-action-packed Ch.3 would make good consolidatory reading if you’ve already read something more introductory on incompleteness (like IGT, for example!).
But what do/did you think of Enderton’s text as a teacher/student? I’d be interested to hear as it is still recommended so often. If you want to read more of my detailed comments, in initial draft, go below the fold!
Introduction The first edition of Herbert B. Enderton’s A Mathematical Introduction to Logic (Academic Press, 1972: pp. 295) rapidly established itself as much-used textbook, not just among the mathematicians it was aimed towards but for some philosophy courses too. A second edition was published in 2002, and a glance at the section headings indicates much the same overall structure: but in fact there are many local changes and improvements: I’ll confine my comments here to this later version of the book (which by now should be equally widely available in libraries).
Enderton’s text deals with first order-logic and a smidgin of model theory, followed by a look at formal arithmetic, recursive functions and incompleteness. A final chapter covers second-order logic and some other matters.
A Mathematical Introduction eventually became part of a logical trilogy, with the publication of the wonderfully lucid Elements of Set Theory (1977) and Computability Theory (2010). The later two volumes strike me as masterpieces of exposition, providing splendid ‘entry level’ treatments of their material. The first volume, by contrast, is not the most approachable first pass through its material. It is good (often very good), but I’d say at a notch up in difficulty from what you might be looking for in an introduction to the serious study of first-order logic and/or incompleteness.
Some details After a brisk Ch. 0 (‘Some useful facts about sets’, for future reference), Enderton starts with a 55 page Ch. 1, ‘Sentential Logic’. Now, this chapter is in certain respects slightly odd. For the usual motivation for separating off propositional logic and giving it an extended treatment at the beginning of a book at this level is that this enables us to give a nice, clutter-free introduction to the key ideas of semantic entailment, provability in a formal deductive system, and to the role of soundness and completeness proofs. But (except for some indications in final exercises) there is no formal proof system mentioned in this chapter, so no soundness or completeness proofs.
So what does happen in this chapter? Well, we do get a proof of the expressive completeness of , etc. We also get an exploration (which can be postponed) of the idea of proofs by induction and the Recursion Theorem, and based on these we get proper proofs of unique readability and the uniqueness of the extension of a valuation of atoms to a valuation of a set of sentences containing them. We get a direct proof of compactness. And we get a first look at the ideas of effectiveness and computability.
Ch. 2, ‘First-Order Logic’, is over a hundred pages long, and covers a lot. It starts with an account of first-order languages, and then there is a lengthy treatment of truth and models. Mathematicians, at least, should be able to cope (but does Enderton forget his officially intended audience on p. 83 where he throws in an unexplained commutative diagram?): philosophers could probably do with more hand-holding.
Enderton then introduces a Hilbert-style deductive system: if you are not already used to such a system, you won’t get much of a feel for how they work, as the discussion starts almost immediately on metatheory (here Mendelson is better). Then we get the soundness and completeness theorems. The proof of the latter is chunked up into clearly marked stages, but is still not, I think, a ‘best buy’ among initial presentations.
The chapter ends with a little model theory — compactness, the LS theorems, interpretations between theorems — and an application, the construction of non-standard analysis. But again, this is all pretty briskly done.
Ch. 3, ‘Undecidability’, is also a hundred pages long and also covers a great deal. After a preview introducing three somewhat different routes to (versions of) Gödel’s incompleteness theorem we initially meet: (1) A theory of natural numbers with just the successor function built in (which is shown to be complete and decidable, and a decision procedure by elimination of quantifiers is given). (2) A theory with successor and the order relation (also shown to admit elimination of quantifiers and to be complete). (3) Presburger arithmetic (shown to be decidable by a quantifier elimination procedure, and shown not to define multiplication) (4) Robinson Arithmetic with exponentiation.
The discussion then turns to the notions of definability and representability. We are then taken through a long catalogue of functions and relations representable in Robinson-Arithmetic-with-exponentiation, including functions for encoding and decoding sequences. Next up, we get the arithmetization of syntax done at length, leading as you’d expect to the incompleteness and undecidability results.
But we aren’t done with this chapter yet. We get (sub)sections on recursive enumerability, the arithmetic hierarchy, partial recursive functions, register machines, the second incompleteness theorem for Peano Arithmetic, applications to set theory, and finally we learn how to use the -function trick so we can get take our results to apply to any nicely axoimatized theory containing plain Robinson Arithmetic.
As is revealed by that quick description (which actually skips over some other bits) there really is a great deal in Ch. 3. To be sure, the material here is not particularly mathematically difficult in itself (indeed it is one of the delights of this area that the initial Big Results come so quickly). However, I doubt that such an action-packed presentation is the best way to first meet this material. It would, however, make for splendid revision-consolidation-extension reading after tackling e.g. my Gödel book.
The final Ch. 4 is much shorter, on ‘Second-Order Logic’. This goes very briskly at the outset. It again wouldn’t be my recommended introduction for this material, though it could make useful supplementary reading for those wanting to get clear about the relation between second-order logic, Henkin semantics, and many-sorted first-order logic.
posted on Logic Matters: http://bit.ly/17ZrvPU 21, 2013 at 11:11PM