Ebbinghaus, Flum, and Thomas: Mathematical Logic

We now turn to consider H.-D. Ebbinghaus, J. Flum and W. Thomas, Mathematical Logic (Springer, 2nd end. 1994: pp. 289). This is the English translation of a book first published in German in 1978, and appears in a series ‘Undergraduate Texts in Mathematics’, which indicates the intended level: parts of the book, however, do seem more than a little ambitious for most undergraduates.

EFT’s book is often warmly praised and is (I believe) quite widely used. But revisiting it, I can’t find myself wanting to recommend it as a good place to start, certainly not for philosophers but I’m not sure I’d recommend it for mathematicians either. The presentation of the core material on the syntax and semantics of first-order logic in the first half of the book is done more accessibly and more elegantly elsewhere. In the second half of the book, the chapters do range widely across interesting material. But again most of the discussions will often go too quickly if you haven’t encountered the topics before, and – if you want revision/amplification of what you already know – you will mostly do better elsewhere.

Some details The book is divided into two parts. EFT start Part A with a gentle opening chapter talking about a couple of informal mathematical theories (group theory, the theory of equivalence relations), giving a couple of simple informal proofs in those theories. They then stand back to think about what goes on in the proofs, and introduce the project of formalization. So far, so good.

Ch. 2 describes the syntax of first-order languages, and Ch. 3 does the semantics. The presentation goes at a fairly gentle pace, with some useful asides (e.g. on handling the many-sorted languages of informal mathematics using a many-sorted calculus vs. use restricted quantifiers in a single-sorted calculus). This is reasonably well done though EFT do make quite heavy work of some points of detail.

Ch. 4 is called ‘A Sequent Calculus’. The version chosen strikes me as really not very nice. For a start (albeit a minor point that only affects readability), instead of writing a sequent as ‘Γ ⊢ φ’, or ‘Γ ⇒ φ’, or even ‘Γ: φ’, EFT just write an unpunctuated ‘Γ φ’.  Much more seriously, they adopt a system of rules which many would say runs together a classical logical rule for the connectives with a structural rule in an unprincipled way that hides e.g. the relation between classical and intuitionistic logic. [To be more specific, they introduce a classical ‘Proof by Cases’ rule that takes us from the sequents (in their notation) Γ ψ φ and Γ ¬ψ φ to Γ φ, and then then show that this almost immediate yields Cut as a derived rule. This seems to me to muddy waters that usual presentations of the sequent calculus strive to keep clear.]

Ch. 5 gives a Henkin completeness proof for first-order logic. For my money, there’s too much symbol-bashing and not enough motivating chat here. (I really don’t think it is good exegetical policy to complicate matters as EFT do by going straight for a proof for the predicate calculus with identity, though they are not alone in this.) Ch. 6 is briskly about The Löwenheim-Skolem Theorem, compactness, and elementarily equivalent structures (but probably fine if you’ve met this stuff before).

Ch. 7, ‘The Scope of First-Order Logic’ is really rather odd. It briskly argues that first-order logic is the logic for mathematics (readers of Shapiro’s book on second-order logic won’t be so quickly convinced!). The reason given is that we can reconstruct (nearly?) all mathematics in first-order ZF set theory – which the authors then proceed to give the axioms for. These few pages surely wouldn’t help if you have never seen the axioms before and don’t already know about the project of doing-maths-inside-set-theory.

Finally in Part A, there’s rather ill-written chapter on normal forms, on extending theories by definitions, and (badly explained) on what the authors call ‘syntactic interpretations’.

Part B of the book discusses a number of rather scattered topics. It kicks off with a nice little chapter on extensions of first-order logic, more specifically on second-order logic, on Lω1ω [which allows infinitely long conjunctions and disjunctions], and LQ [logic with quantifier Qx, ‘there are uncountably many x such that …’]. Then Ch. 10 is on ‘Limitations of the Formal Method’, and in under forty pages aims to talk about register machines, the halting problem for such machines, the undecidability of first-order logic, Trahtenbrot’s theorem and the incompleteness of second-order logic, Gödel’s incompleteness theorems, and more. This would just be far too rushed if you’d not seen this material before, and if you have then there are plenty of better sources for revising/consolidating/extending your knowledge.

Ch. 11 is by some way the longest in the book, on ‘Free Models and Logic Programming’. This is material we haven’t covered in the Guide. But again it doesn’t strike me as a particular attractive introduction.

Ch. 12 is back to core model theory, Fraïssé’s Theorem and Ehrenfeucht Games: but (I’m sorry – this is getting repetitious!) you’ll again find better treatments elsewhere, this time in books dedicated to model theory. Finally, there is an interesting (though quite tough) concluding chapter on Lindström’s Theorems which show that there is a sense in which standard first-order logic occupies a unique place among logical theories.

Summary verdict The core material in Part A of the book is covered better (more accessibly, more elegantly) elsewhere. Of the supplementary chapters in Part B, the two chapters that stand out as worth looking at by enthusiasts are perhaps Ch. 9 on extensions of first-order logic, and Ch. 13 (though not easy) on Lindström’s Theorems.