Hodel: An Introduction to Mathematical Logic

Richard E. Hodel’s An Introduction to Mathematical Logic* (PWS Publishing, 1995, reprinted Dover Publications, 2013: pp. 491) was originally launched into the world by a relatively obscure publisher, but has now been taken up and cheaply republished by Dover. I hadn’t heard of the book before a few people recommended it, commenting on the lack of any mention in earlier versions of the TYL Guide. The book covers first-order logic and some recursion theory, with a less usual – though not unique – feature being a full textbook treatment of Hilbert’s Tenth Problem (the one about whether there is an algorithm which tells us when a polynomial equation p(x) = 0 has a solution in the integers).

So how does Hodel fare against his competitors? Overall, the book is pretty clearly written, though it does have a somewhat old-fashioned feel to it (you wouldn’t guess, for example, that it was written some twenty years after George Boolos and Richard Jeffrey’s Computability and Logic). And Hodel does give impressively generous sets of exercises throughout the book – including some getting the student to prove significant results by guided stages. However, I can’t really recommend his treatment of logic in the first half of the book.

Some details Ch. 1 ‘Background’ is an unusually wide-ranging introduction to ideas the budding logician should get her head round early. We get a first informal pass at the notions of a formal system and of an axiomatized system in particular, the idea of proof by induction, a few notions about sets, functions and relations, the idea of countability, the ideas of an algorithmically computable function and of effective decidability. We even get a first pass at the idea of a recursive function (and a look at Church’s Thesis about how the informal idea of being computable relates to the idea of recursiveness). This is very lucidly done, and can be recommended to any beginner.

Ch. 2 is on ‘The language and semantics of propositional logic’ and is again pretty clearly done. Ch. 3 turns to formal deductive systems for propositional logic. Unfortunately, Hodel chooses to work primarily with Shoenfield’s system (the primitive connectives are ¬ and  ∨ , every instance of ¬A ∨ A is an axiom, and there are four rules of inference). I really can’t see the attraction of this system among all the competitors, or why it should be thought as especially appropriate as a starting point for beginners. It neither has the naturalness of a natural deduction system, nor the austere Bauhaus lines of one of the more usual Frege-Hilbert axiomatic systems. The chapter does also consider other systems of propositional logic in the concluding two sections, but goes too quickly to be very helpful. So this key chapter is not a success, it seems to me.

Ch. 4 on ‘First-order languages’, including Tarskian semantics, is again pretty clear (and could be helpful to a beginner who is first encountering the ideas and is looking for reading to augment another textbook). But as we’d expect given what’s gone before, when we turn to Ch. 5 on ‘First-order logic’ we can a continuance of the discussion of a Shoenfield-style system (except that Hodel takes ∀ rather than ∃ as primitive). Which is, by my lights, much to be regretted. The ensuing discussion of completeness, while perhaps a little laboured, is carefully structured with a good amount of signposting, so some might find it helpful if they have struggled with other treatments. But there are better presentations of first-order logic overall.

Ch. 6 is called ‘Mathematics and logic’ and touches on an assortment of topics about first-order theories and their limitations (and a probably rather-too-hasty look at set theory as an example).

But the next two chapters do form a nice unit. Ch. 7 discusses ‘Incompleteness, undecidability and indefinability’. Recursive functions are defined Shoenfield-style as those arising from a certain class of initial functions by composition and regular minimization, which eases the proof that all recursive functions are representable (though doesn’t do much to make recursiveness seem a natural idea to beginners). Then, by making the informal assumption that certain intuitively decidable relations are recursive, Hodel proves Gödel’s incompleteness theorem, Church’s Theorem and Tarski’s Theorem. The next chapter fills in enough detail about recursive functions and relations to show how to lift that informal assumption. This seems all pretty clearly done, even if not a first-choice for real beginners.

Then Ch. 9 extends the treatment of computability by showing that the functions computable by an unlimited register machine are just the recursive ones: but, again this sort of thing is done at least as well in other books.

Finally, Ch. 10 deals with Hilbert’s tenth problem (so the first five sections of Ch. 8 and then this chapter form a nice, stand-alone treatment of the negative solution of Hilbert’s problem, which can be recommended).

Summary verdict Beginners could all usefully read Hodel’s opening chapter, which is better than usual in setting the scene, and supplying the student with a useful toolkit of preliminary ideas. The presentation of first-order logic in Chs. 2-6 is based around an unattractive formal system, and while the discussion of the usual meta-theoretic results is pretty clear, it doesn’t stand out from the good alternatives: so overall, I wouldn’t recommend this as your first encounter with serious logic. Students, however, might find Chs. 7 and 8 provide a nice complement to other discussions of Gödelian incompleteness and Church and Tarski’s Theorems. While more advanced students could revise their grip on basic definitions and results by (re)reading §§8.1–8.5 and then enjoy tackling Ch. 10 on Hilbert’s Tenth Problem.