Mileti, Modern Mathematical Logic, Chs 11–12

We are on the home straight … only 117 pages to go. The last two long chapters of MML 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 (fair enough!). 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. MML 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, 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 recommendations in the BML Study Guide? Without going into more detail, I’d say not — or at least, not for solo self-study: and they wouldn’t really be my first choice for supplementary reading either. (Though they’ll probably get an honourable mention in the next iteration of the Guide.)

To be frank, having finished the book, speed-reading some and taking other parts at a more leisurely pace, 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 seem usually thoroughly conventional and often 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 one set of covers that makes the book worth more that the sum of its parts. So, in summary judgement, I’m afraid I can’t join in the chorus of rather extravagant praise printed at the front of the book. Sorry!

Scroll to Top