Logic

If you have access to a library which subscribes to Springer Link, you should be able to download an e-copy of this very recent addition to the growing list of editions of Gödel’s various notebooks. (If you don’t have good library access, then tough — Springer are price-gouging at £111.50 for the PDF, and more for the print-on-demand version.)

The editors Maria Hämeen-Anttila and Jan von Plato write in their short Preface

If there is one “must” to be cleared in the enormous mass of the Kurt Gödel Papers kept at the Firestone Library of Princeton University, it is the series of four notebooks titled Resultate Grundlagen. Gödel wrote these 368 pages between 1940 and 1942, except for the first 33 and last 12 pages. There is a continuous page numbering and the same goes for the theorems. It has been a great fortune for us to meet the task of transcribing, translating, and editing these notebooks.

And later, in their introductory essay

Resultate Grundlagen [RG] is a collection of results Gödel considered finished. … Close to two thirds of RG deal with set theory … Next to set theory, RG contains results on arithmetic and recursive functions. Type theory is one clearly separate topic, and so is what Gödel called “positive logic.” The latter relates to intuitionism which was one of Gödel’s permanent interests from the early 1930s on. This interest is clearly seen in [RG] with about one part in four devoted to intuitionistic logic and its interpretation.

So that tells us two things. First, about the topics of the RG notebooks themselves. And second, inadvertently, that the language of this edition is sometimes only an approximation to good English. Evidently, Springer’s contribution to the publishing of this book didn’t run to a native-speaker copy-editor. This matters, I think, for two reasons. First, readers for whom English is not their first language will stumble. Second, the editors have (oddly to my mind) not given their transcription of Gödel’s obsolete German shorthand in a parallel text (surely an achievement worth preserving for future researchers): so occasionally the reader might wonder whether seemingly odd or stuttering phrasing is in the original or is a result of rendering into clumsy English. In fact the editors write

RG is a polished shorthand text when compared with such sources of preliminary work as [other notebooks]. There are next to no cancellations, but there are additions that often result in awkward sentence structures. The question is to what extent such passages should get improved in translation.

Given this sort of issue, why indeed not pre-empt a reader’s questions with a parallel text, as in the canonical edition of the Works?

On the key set-theoretic content, the editors write

After the transcription and translation work was done, we were lucky to find in Akihiro Kanamori a reader without comparison of Gödel’s results on foundations. … Aki took up the task and presented us with a splendid essay on The remarkable set theory in Gödel’s 1940–42 Resultate Grundlagen, an essay that explains how Gödel had arrived at numerous results independently discovered by others later, sometimes much later, in an anticipation of the development of set theory from 1942 on, the year Gödel left formal work in logic and foundations.

Which is good to know; but since Kanamori’s essay isn’t included in the book as an introduction (and isn’t yet available elsewhere), the rest of us will have to wait a little for a knowledgeable guide to Gödel’s achievement in RG. All that said, it remains astonishing to find how productive Gödel was in those years when he was publishing so little. Fascinating but frustrating to dip into.

To continue. Chapter 7 of Mileti’s MML is titled “Model theory”. Of the five sections, the first three can’t be recommended. In particular, §7.2 makes such heavy weather of that fun topic, nonstandard models of arithmetic and analysis. There are so many alternative treatments which will be more accessible and give a more intuitive sense of what’s going on. By contrast, I thought §7.4 on quantifier elimination did a 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 and (defined as the set of Kuratowski pairs ) is a set according to the ZFC axioms is to use Separation to carve it out of the set 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, without explicitly mentioning the cumulative hierarchy (let alone the possibility of potentially more natural axiomatisations in terms of levels) 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 Beginning Mathematical Logic 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 do the job of explaining 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. (Perhaps the perceived unevenness is all in my mind! And I know from my own efforts in writing long-ish books that maintaining a consistent level of approachability, of proportions of helpful less formal chat around the more formal stuff and so on, is difficult. I can only report how I am finding the book — and, as they say, your mileage may vary.)

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.

And so it goes: as with the earlier chapters, a mixed bag.

Towards the end of last year, within a week or two of publishing Jeremy Avigad’s Mathematical Logic and Computation (a bumpy ride, but very well worth having), CUP also released another textbook, Joseph Mileti’s Modern Mathematical Logic. I’d earlier seen a substantial set of notes that Mileti had posted online, and (to be frank) wasn’t over-impressed; so I haven’t been rushing to read this. But I thought I would now take a look at the book version, with a view to seeing whether there are any chapters which I’d want to mention or even recommend in the next iteration of the Beginning Mathematical Logic Study Guide.

Level and coverage? MML is announced as aimed at advanced undergraduates or beginning graduates (by US standards, anyway), though the book is distinctly less ambitious than Avigad’s. 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. The coverage is broadly conventional, starting with basic first-order logic (though with the opposite emphasis to Avigad: there’s no real proof theory). Then there’s a little model theory, entry-level axiomatic set theory, some computability theory, and a treatment of incompleteness. At this point, then, at least just glancing at the table of contents and diving into the first chapters, I’m not at all sure quite what makes this a book on especially modern mathematical logic in either topics or general approach.

I rather liked the tone of the short Introduction; and going through the next couple of chapters, there is friendly signposting and some nice turns of phrase. But …

But 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 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 …”.) I note, by the way, that by the end of §2.2 the reader is already supposed to know about countable sets and accept without demur that a countable union of countable sets is countable.

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 on 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; removing double negation elimination doesn’t give intuitionistic logic. 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!

As for completeness, we get the sort of proof that (a) involves building up a maximal consistent set starting from some given wffs by going along 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.

To finish on a positive note, 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.

To be continued