Kleene: Mathematical Logic
In the preface to his Mathematical Logic (John Wiley 1967, Dover reprint 2002: pp. 398), Stephen Cole Kleene writes
After the appearance in 1952 of my Introduction to Metamathematics, written for students at the first-year graduate level, I had no expectation ofwriting another text. But various occasions arose which required me tothink about how to present parts of the same material more briefly, to a more general audience, or to students at an earlier educational level. These newer expositions were received well enough that I was persuaded to prepare the present book for undergraduate students in the Junior year.
You’d expect, therefore, that this later book would be more accessible, a friendlier read, than Kleene’s remarkable IM. But in fact, this doesn’t actually strike me as being obviously the case. I’d still recommend reading the older book, augmented by one chapter of this later ‘Little Kleene’. To explain:
Some details The book divides into two parts. The first part, ‘Elementary Mathematical Logic’ has three chapters. Ch. 1 is on the propositional calculus (including a Kalmár-style completeness proof). This presents a Hilbert-style proof system with an overlay of derived rules which look rather natural-deduction-like (but aren’t the real deal). There is a lot of fussing over details in rather heavy-handed ways. I couldn’t recommend anyone nowadays starting here, while if you’ve already read a decent treatment of the propositional calculus (and e.g. looked at Mendelson to see how things work in a Hilbert-style framework) you won’t get much more out of this.
Much the same goes for the next two chapters. Ch. 2 gives an axiomatic version of the predicate calculus without identity, and Ch. 3 adds identity. (Note, a completeness proof doesn’t come to the final chapter of the book). Again, these chapters are not done with a sufficiently light touch to make them a particularly attractive read now.
The second part of the book is titled ‘Mathematical Logic and the Foundations of Mathematics’. Ch.4 is basically an abridged version of the opening three chapters of IM, covering the paradoxes, the idea of an axiomatic system, introducing formal number theory. You might like to read in particular §§36–37 on Hilbert vs. Brouwer and ‘metamathematics’. Ch. 5 is a sixty page chapter on ‘Computability and Decidability’. Kleene is now on his home ground, and he presents the material (some original to him) in an attractive and illuminating way, criss-crossing over some of the same paths trodden in later chapters of IM. In particular, he uses arguments for incompleteness and undecidability turning on use of the Kleene T-predicate (compare §33.7 of IGT1 or §43.8 of IGT2). This chapter is certainly worth exploring.
Finally, the long Ch. 6 proves the completeness theorem for predicate logic by Beth/Hintikka rather than by Henkin (as we would now think of it, he in effect shows the completeness of a tree system for logic in the natural way). But nicer versions of this approach are available. The last few sections cover some supplementary material (on Gentzen systems, Herbrand’s Theorem, etc.) but again I think all of it is available more accessibly elsewhere
Summary verdict Do read Chapter 5 on computability, incompleteness, decidability and closely related topics. This is nicely done, complements Kleene’s earlier treatment of the same material, and takes an approach which is interestingly different from what you will mostly see elsewhere.