Mileti, Modern Mathematical Logic

Joseph Mileti’s Modern Mathematical Logic (CUP 2023, 502 pp.) is announced as begin aimed at advanced undergraduates or beginning graduates.(Mileti says he assumes familiarity with some basic abstract algebra; however, this seems perhaps more needed to best appreciate some illustrative examples rather than as necessary background for grasping core content.)

Despite the title, the coverage is old-school and the approach thoroughly conventional. Mileti starts with basic first-order logic (though there’s no real proof theory). Then there’s a little model theory, entry-level axiomatic set theory, some computability theory, and the book ends with a treatment of incompleteness.

A familiar menu, then: how well is it served it up? There is friendly signposting and some nice turns of phrase. But …

Some details Chapter 2, the first substantial chapter, is thirty pages on ‘Induction and Recursion’. We get a pretty dense treatment of what Mileti calls ‘generating systems’, three different ways of defining the set of generated whatnots, proofs that these definitions come to the same, then a criterion for free generating systems, a proof that we can do recursive definitions over the free systems, and so on. This is all done in what strikes me as a rather heavy-handed way which could be pretty off-putting as a way of starting out. Many students, I would have thought, will just feel they have been made to labour unnecessarily hard at this point for small returns. And when the very general apparatus is applied e.g. in the next chapter to prove, e.g., unique parsing results, I don’t think that what we get is more illuminating than a more local argument. (I suppose my pedagogic inclination in such cases is to motivate a general proof idea by proving an interesting local case first and then, at an appropriate point later, saying ‘‘Hey, we can generalize …”.)

Chapter 3, the next fifty pages, is on propositional logic. A minor complaint is that the arrow connective is initially introduce in the preface as meaning ‘implies’ (oh dear), and then we get not a word of discussion of the truth-functional treatment of the connective (unless my attention flickered). But my main beef here is with the chosen formal proof system. This is advertised as natural deduction, but it is a sequent system, where on the left of sequents we get sequences rather than sets (why?). And although the rules are set out in a way that would naturally invite tree-shaped proofs, they are actually applied to produce linear proofs (why?). Moreover, the chosen rule-set is not happily motivated. We have disjunctive syllogism rather than a proper vE rule; double negation elimination is called ¬E (so intuitionistic logic doesn’t have negation elimination? — Mileti’s system doesn’t have a nice inituitionistic subsystem). OK: Mileti isn’t going to be interested in proof theory; but he should at least have chosen a modern(!) proof system with proof-theoretic virtues!

We then get the sort of propositional completeness proof that (a) involves building up a maximal consistent set starting from some given wffs by looking at every possible wff in turn to see if it can next be chucked into our growing collection while maintaining consistency, rather than the sort of proof that (b) chucks in simpler truth-makers only as needed, Hintikka style. We are not told what might make the Henkin strategy better than the more economical Hintikka one.

Perhaps the best/most interesting thing in this chapter is the final section (and the accompanying exercises) on compactness for propositional logic, which gives a nice range of applications.

Chapter 4 is on ‘First-order logic: languages and structures’ — so some 40 pages on basic semantics. Chapter 5 is on ‘Relationships between structures’ — another longish chapter, 35 pages on substructures, homomorphisms between structures, embeddings, and the like. Chapter 6 , ‘Implications and compactness’, is an even longer chapter — some 48 pages introducing a proof system for FOL and proving soundness and completeness, then drawing out some consequences of compactness, before going on to talk about theories framed in a first-order language, with a substantial final section on random graphs.

In headline terms: I found the basic treatment of the semantics, and again of the formal proof-system and completeness for FOL, pretty unattractive. On the other hand, the more model-theoretic Chapter 5, and the second half of Chapter 6 strike me as notably more readable.

In just a bit more detail, we get a highly conventional story about the syntax of FOL languages. In particular, the same symbols are recruited for double duty, as part of the construction of a quantifier operator, and for use as parameters/temporary names. Of course, this means we have to fuss about rules for distinguishing free from bound occurrences of variables, and fuss at length about avoiding unwanted variable capture when substituting terms for variables (§4.4 on substitution is no less than eleven rather dense pages long). Why do things this way? It’s only ninety years since Gentzen taught us how to do better, in ways that have become more and more familiar as modern proof-theorists spread the word!

In the middle of Chapter 4, though, there is a nice short first section on definability. Issues of definability and related topics about what classes of structures can be captured by which languages, and so on, are then taken up in the next chapter — which ends with a nice section §5.5 which introduces the Tarski-Vaught test and shows how to get from there to a version of the downward L-S theorem for a countable language. §4.3 and Chapter 5 could I think be tackled standalone by someone who knows some basic FOL from other sources; and these sections do work pretty well.

After a section defining semantic entailment for FOL, Chapter 6 introduces a deductive system for quantificational logic, far too briskly (it seems to me) to be of much use to anyone who is encountering one for the first time. And the soundness and completeness results are done no more attractively than for the earlier propositional logic case. I can’t really recommend these sections. But then §6.4 on applications of compactness and §6.5 on theories are nice (and the concluding section on random graphs is an interesting bonus).

Chapter 7 is titled ‘Model theory’. Of the five sections, the first three can’t be recommended. In particular, §7.2 makes unnecessarily heavy weather of that fun topic, nonstandard models of arithmetic and analysis. By contrast, I thought §7.4 on quantifier elimination did a notably better-than-often job at explaining the key ideas and working through examples. §7.5 on algebraically closed fields worked pretty well too.

And now we get two chapters on set theory, together amounting to almost a hundred pages. There’s a major oddity. The phrase ‘cumulative hierarchy’ is never mentioned: nor is there any talk of sets being found at levels indexed by the ordinals. The usual V-shaped diagram of the universe with ordinals running up the spine is nowhere to be seen. I do find this very strange — and not very ‘modern’ either! There are minor oddities too. For example, the usual way of showing that the Cartesian product of A and B (defined as the set of Kuratowski pairs \langle a, b\rangle) is a set according to the ZFC axioms is to use Separation to carve it out of the set \mathcal{P}(\mathcal{P}(A \cup B)) in the obvious way. Mileti instead uses an unobvious construction using Replacement. Why? A reader might well come away from the discussion with the impression that Replacement is required to get Cartesian products and hence all the constructions of relations and functions which depend on that. (I rather suspect that Mileti isn’t much interested in ‘modern’ finer-tuned discussions of what depends on what, such as the question of  which set-theoretic claims really do depend on something as strong as replacement.)

So: Chapter 8 gives us ZFC, and the usual sort of story about how to develop arithmetic and analysis in set theory. The mentioned oddities apart it is generally OK: but the recommendations for entry-level set theory in the Study Guide do the job better and in a friendlier way. However I should mention that, at the end of the chapter, §8.7 on models, sets and classes, does explain the role of class talk rather nicely.

Chapter 9 is on ordinals, cardinals, and the axiom of choice; and I thought this chapter worked comparatively well. Finally in this group, Chapter 10 is much shorter, just two sections on “Set-theoretic methods in model theory”. The first, just four pages, is on sizes of models; and then the second is an opaque and to my mind misjudged ten pages on ultraproducts.

We are now on the home straight … only 117 pages to go. The last two long chapters  are on ‘Computable sets and functions’ and ‘Logic, computation, and incompleteness’.

In broad-brush terms, the content is pretty much the sort of thing you could predict. So Chapter 11, some seventy pages, introduces the primitive recursive functions, shows they are not all the intuitively computable functions, and so goes on to discuss partial recursive functions. Then we get a machine model of computation, with Mileti choosing URM machines over Turing machines. We find out that the URM computable partial functions are just the partial recursive functions, and there is some sensible discussion of the Church-Turing Thesis. The chapter concludes by looking at computably enumerable (but perhaps not computable) sets.

Then Chapter 12 starts by talking about coding expressions and deductions, and about arithmetic definability. §12.3 shows that the set of true sentences of formal first-order arithmetic is undecidable. Mileti then starts looking at Robinson Arithmetic in particular and shows that it can represent computable functions. The final section of the book gives us a proof of incompleteness.

So these final two chapters cover material which is already beautifully covered in some classic books from e.g. the early editions of Boolos and Jeffrey  onwards. To be sure, these chapters are perfectly respectable, perhaps the best in the book, and Mileti can write with an engaging turn of phrase. But are they particularly attractively done, especially accessible, splendidly clear, plainly to be preferred to the existing entry-level recommendations in the Study Guide? I rather think not.

Summary verdict Some parts of this book can be recommended for supplementary reading for self-study. But to be frank, I’m still not quite sure what the point of Mileti’s text is. The title rather belies the content — what’s so ‘modern’ here? The treatments of the various topics do usually seem thoroughly conventional and often even rather old-school. And I’m not persuaded that — sixty years on from Mendelson! — there is still any special additional virtue in having core FOL, some model theory, set theory, and some computability theory all done within a single set of covers, a benefit that makes the book worth more that the sum of its parts. So, I’m afraid I can’t jump to join in the chorus of rather extravagant praise printed at the front of the book. (Though equally, if you do want to really really  insist on having just one single text to back up a lecture course covering the whole of the traditional menu for a wide-ranging multi-semester mathematical logic course, this probably is your best option at its level.)

Scroll to Top