Some 300 people have downloaded the February version of the Teach Yourself Logic Guide, so I guess I’m not entirely wasting my energy. Sure, the Guide won’t be a particular exciting project for many: so I must try to get back to blogging about more interesting stuff. But for those who are following, here — far out of chronological sequence — is a draft entry for the Big Books chapter on Goldstern and Judah’s The Incompleteness Phenomenon.
A number of people have recommended this book to me, so I thought I should take a closer look. Well, I have, and I wasn’t bowled over. What am I missing?
Half of The Incompleteness Phenomenon: A New Course in Mathematical Logic by Martin Goldstern and Haim Judah (A.K. Peters, 1995: pp. 247) is a treatment of first-order logic. The rest of the book is two long chapters of just the same length, one on model theory, one on incompleteness and a little on recursive functions. So the emphasis on incompleteness in the title is somewhat misleading: it is at least equally an introduction of some model theory. I have had this book recommended to me more than once, but I find myself immune to its supposed charms (I too often don’t particularly like the way that it handles the technicalities): your mileage may vary.
Some details Ch. 1 starts by talking about inductive proofs in general, then gives a semantic account of sentential and then first-order logic, then offers a Hilbert-style axiomatic proof system.
Early on, the authors introduce the notion of $latex \mathcal{M}$-terms and $latex \mathcal{M}$-formulae. An $latex \mathcal{M}$-term (where $latex \mathcal{M}$ is model for a given first-order language $latex \mathcal{L}$) is built up from $latex \mathcal{L}$-constants, $latex \mathcal{L}$-variables and/or elements of the domain of $latex \mathcal{M}$, using $latex \mathcal{L}$-function-expressions; an $latex \mathcal{M}$-formula is built up from $latex \mathcal{M}$-terms in the predictable way. Any half-awake student is going to balk at this. Re-reading the set-theoretic definitions of expressions as tuples, she will realize that the apparently unholy mix of bits of language and bits of some mathematical domain in an $latex \mathcal{M}$-term is not actually incoherent. But she will right wonder what on earth is going on and why: our authors don’t pause to explain. (A good student who knows other presentations of the basics of first-order semantics should be able to work out after the event what is going on in the apparent trickery of Goldstern and Judah’s sort of story: but this isn’t the way to start, without adequate explication of the point of the procedure.)
Ch. 2 gives a Henkin completeness proof for the first-order deductive system given in Ch. 1. This has nothing special to recommend it, as far as I can see: there a lot of more helpful expositions available. The final section of the chapter is on non-standard models of arithmetic: Boolos and Jeffrey (Ch. 17 in their third edition) do this more approachably.
Ch.3 is on model theory. There are three main sections, ‘Elementary substructures and chains’, ‘ultra products and compactness’, and ‘Types and countable models’. So this chapter — less than sixty pages — aims quite high to be talking about ultraproducts and about types. You could read it after working through e.g. Manzano’s book: but I certainly don’t think this chapter makes for an illuminatingly accessible first introduction to serious model theory.
Ch. 4 is on incompleteness, and the approach here seems significantly more gentle than the previous chapter. The authors make things easier for themselves by adopting a version of Peano Arithmetic which has exponentiation built in (so they don’t need to tangle with Gödel’s beta function). And they only prove a semantic version of Gödel’s first incompleteness theorem (the authors don’t say anything about why we might want to prove the syntactic version of the first theorem, and don’t even mention the second theorem). The proof goes as by showing directly that — via Gödel coding — various syntactic properties and relations concerning PA are expressible in the language of arithmetic with exponentiation (in other words, they don’t argue that those properties and relations are primitive recursive and then show that PA can express all such properties/relations). But this isn’t done particularly well: I think this sort of more direct assault on incompleteness is better handled in Leary’s book (recommended in the Guide).
The book ends by over-briskly introducing the ideas of primitive recursive and recursive functions.
Summary verdict The first two chapters of this book can’t really be recommended either for making a serious start on first-order logic or for consolidatory reading. The third chapter could perhaps be used for a brisk revision of some model theory if you have already done some reading in the area. The final chapter about incompleteness (the title of the book might lead you to think that this will be a high point) isn’t a helpful introduction: it could be skimmed through to see how the authors approach things, but it doesn’t really go far enough for more serious purposes.
When looking at a copy of The Tarskian Turn the other day, I noticed that Horsten recommended Goldstern and Judah re such things as incompleteness and and the undefinability of truth and also liked the phrase “the incompleteness phenomenon”. (This is in the chapter called something like “Standing on the shoulders of giants”.)
Horsten noted that the theorems came in different versions, with differing strength (which he saw as a reason to see incompleteness as a phenomenon) and thought the weaker versions made it easier to think that the stronger ones were true, and that the stronger versions required a lot of technical detail (for which he recommended Boolos, Burgess and Jeffrey to those who were interested).
Yes, Horsten’s was one of those who brought Goldstern and Judah’s book rather belatedly to my attention. I’ve just had another look at their chapter on incompleteness, worrying that my negative view was coloured by being disappointed by their earlier chapters. I’ve slightly expanded my remarks for the Guide, but the headline remains that I think Leary’s Friendly Introduction does this take in incompleteness better.