Wolfgang Rautenberg’s A Concise Introduction to Mathematical Logic is a pretty ambitious undertaking, seeing that at the indicated introductory level it covers “classical material such as logical calculi, [the] beginnings of model theory, and Gödel’s incompleteness theorems, as well as some topics motivated by applications, such as a chapter on logic programming” (from the Foreword by Lev Beklemishev). This sketch in point of fact aims at the fist six chapters of the book, with the seventh, and last, chapter being devoted to the deep and philosophically loaded subject of self-reference. The inclusion of an explicit chapter on this topic is cause for praise in itself, given its centrality in what Kurt Gödel set into motion eighty years ago: nothing less than a logical/philosophical/cultural earthquake with aftershocks that seem to go on and on. Rautenberg states that his book is intended “also [to be] of interest to students of philosophy (with an adequate mathematical background) because of the epistemological applications of Gödel’s incompleteness theorems, which are discussed in detail.” The present book is the third edition of this text, sporting more elaboration and some expansion, e.g., Horn programming, for the purposes of computer program design. Thus, A Concise Introduction to Mathematical Logic spreads its net quite wide, taking aim even at philosophers and computer scientists.
But it is a compact effort nonetheless, and this should be borne in mind by the reader: “…[a]lthough the book is primarily designed to accompany lectures on a graduate level, most of the first three chapters are also readable by undergraduates … [with] the first hundred pages cover[ing] … an undergraduate course on mathematical logic, combined with a due portion of set theory.” But “[s]tarting from Chapter 4 [p.135], the demands on the reader begin to grow …” and the author recommends “[meeting] the challenge … by attempting to solve the problems without recourse to the hints.” The author even goes so far as to give (welcome) pedagogical advice: “The density of information in the text is rather high; a newcomer may need one hour for one page. Make sure to have paper and pencil at hand when reading the text.” [This is of course universally valid policy …]
It is without question the case, then, that A Concise Introduction to Mathematical Logic is dense in the sense indicated, what with applications of the compactness theorem appearing on p.30, quickly followed by “Hilbert calculi” on p. 35; the completeness theorem caps off the first 100 pages, i.e. the material advertised for undergraduates, preceded by some serious model theory. Of course, completeness (of fist order logic) is one of the most evocative results in the subject, stating that a true statement (i.e. one modeled in the theory) is provable (or derivable) there, and its appearance at the juncture Rautenberg stipulates can move the student to keep going in the subject, girding his loins for what lies ahead. And his loins had better be girded, seeing that nonstandard models make their appearance immediately after the aforementioned coverage of completeness, followed by Z(ermelo-)F(raenkel-with)C(hoice) and Skolem’s paradox presented in only ten pages.
Après ça le déluge: logic programming and Horn resolutions, some hard-core model theory at the speed of light (including the Ehrenfeucht game), things to do with Gödel (recursive functions, arithmetization, representability, &c.), and then, as mentioned above, the last chapter on self-reference. And there are some beautiful results included here: p. 250: “Every consistent (recursively) axiomatizable theory [interpreting elementary arithmetic] is incomplete” (my favorite meta-mathematical theorem), p. 252 (Tarski, after Gödel, so to speak): “The notion of truth in [some language] N is not definable in N,” p. 254 has Church’s result on the undecidability of the set of all tautological sentences, and finally, on p. 255, we get Matiyasevich’s 1970 result to the effect that there is no algorithm that decides for all polynomials P(x) in Z[x] whether the diophantine equation P(x) = 0 is solvable in Z, settling Hilbert’s tenth problem — and, yes, Rautenberg goes on to discuss the proof (albeit, in his own words, as a brief sketch).
The third edition of A Concise Introduction to Mathematical Logic is a fine piece of scholarship and will more than repay the efforts of the committed student who chooses this means as an entry into modern mathematical logic.
Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.
Preface.- Introduction.- Notation.- Propositional Logic.- First-Order Logic.- Complete Logical Calculi.- Foundations of Logical Programming.- Elements of Model Theory.- Incompleteness and Undecidability.- On the Theory of Self-Reference.- Bibliography.- Index of Terms and Names.- Index of Symbols.