Context: earlier chapters of Beginning Mathematical Logic: A Study Guide introduce a range of core topics in mathematical logic. This final chapter revisits many of those topics suggesting rather more advanced readings, pressing on from the earlier introductory ones. [So this chapter replaces what was ‘Part III’ of an earlier version of the Study Guide.] It isn’t particularly exciting, then, as a stand-alone read as it mostly annotated lists of books, without the earlier arm-waving overviews of topics. And this chapter is also a bit more idiosyncratic and partial and uneven in level in its recommendations. But better than nothing, I hope. And it goes without saying that if you have some improved suggestions on a favourite topic area of yours, then now is the time to let me know!
The sections on algebras for logicians and on type theory are new, and I’d particularly welcome more advice.
Delayed by distractions of one sort and another, I’ve now finished the first draft of a new chapter for the Beginning Mathematical Logic Study Guide. Earlier in the month, I posted a draft version of Part I of the revised Guide (i.e. Chapters 1 to 9). And now — drum roll and fanfare — here at last is
As always, comments are extremely welcome. If you want to know how this new chapter fits into the overall shape of the Guide, and hence its intended purpose, take a quick look at the short §§1.2–1.4 in Part I.
So, as they say, enjoy! I certainly much enjoyed rereading Boolos when writing about provability logic in particular.
Afterthought: This Chapter 10 is quite long. On reflection, I’m now rather inclined to divide it into a chapter on modal logics and a chapter on provability logic.
A further afterthought: To my considerable surprise, I find that the earlier Boolos book is not available at the Usual PDF Repositories … so (for many readers) it won’t be at all helpful to have it as the main recommendation on provability logic. So I will revise accordingly.
I thought it would be a doddle to update the chapter on modal logic for the Study Guide. But — needless to say! — it hasn’t quite worked out that way.
Now, propositional modal logics have long been of considerable interest to philosophers reflecting on notions of necessity, or when thinking about the logic of tensed discourse and the like. And first-order and higher-order quantified modal logics are of current interest to philosophers dabbling in modal metaphysics (no don’t! — that way madness lies …). Propositional modal logics are also of interest to mathematicians and computer scientists theorizing about relational structures. But none of these topics need be of much concern to those beginning mathematical logic. Apart from the link between modal S4 and Intuitionistic logic, the one bit of modal logic that is of real core interest to mainstream mathematical logic is (surely) provability logic, with its closest of connections to issues about Gödelian incompleteness etc.
So that’s the thought which is now going to structure the coverage of modal logic in the Beginning Mathematica Logic guide. I’ll introduce a modicum a modal logic at an introductory level: then let’s move on to the fun stuff about provability logics.
But what to recommend by way of accessible introductory reading on provability logic? I’ve found myself revisiting the classics by Smoryński and Boolos, and then reading a variety of Handbook articles, as well as some other pieces. Which has been fun — and instructive, as I’d forgotten an embarrassing amount. Rather to my surprise, however, I found Boolos’s The Logic of Provability rather less easy going than I’d remembered it; so I’m left a bit uncertain what to recommend as the most approachable path into the subject. Perhaps half of Smoryński’s book …
(An aside: Smoryński’s 1985 book seemingly reproduces pages produced by an electric typewriter. Boolos’s 1993 book is more conventionally typeset, but it’s done in such a cluttered way as to be often very unfriendly to the eye. We are so used now to seeing decently LaTeXed maths books that ploughing through less well-produced texts like these can be enough of a chore to get in the way of processing the content.)
Anyway, here for fun is a result proved by Beklemishev that I’ve been reminded of, that he got by a proof using an extension of provability logic.
Call finite strings in the alphabet of e.g. ordinary decimal arithmetic worms. So the worm is a string of digits . And we will define to be the result of decreasing ‘s last digit by 1 if you can, or deleting that digit if it is already 0.
And now consider a sequence of worms constructed according to the following two rules:
(1) if , then put (chop off the head of the worm!);
(2) if , let be the maximum such that . Then put to be followed by copies of the part of starting after position .
For example, suppose we start with the worm
Then the sequence continues …
following by five copies of
And so it goes.
Well, you know your Goodstein sequences and your hydra battles, so you can predict what follows. But it is nice to know all the same!
(1) For any initial worm , there is an such that is empty.
(2) That result, suitably coded, is unprovable in first-order Peano arithmetic. In fact, its statement is equivalent to the 1-consistency of PA.
[For references see Sergei Artemov’s article in the Handbook of Modal Logic.]
Having got this far, I am well aware that there are now some mismatches in the level/breadth of the overviews in the various chapters, and also places which call for more cross-references. For example, I need to go back to the overview on set theory to say just a paragraph or so more about ordinals, in order to make a better connection with the use of small ordinals in the current chapter when waving my arms at Gentzen’s consistency proof. So smoothing out the coverage of Part I of the Study Guide is a next task. But at least there is now a full draft to play with.
The chapter starts by briskly outlining a standard natural deduction system for intuitionistic logic. Then there are two sections giving rough-and-ready overviews, one on motivation and the BHK interpretation, the other on some additional formal details and giving a sketch of Kripke semantics. There are then the usual sections suggesting main readings, followed by some additional reading options. The chapter ends with some pointers to a few pieces with a more historical/philosophical flavour. The usual chapter format, in other words.
Since this is newly minted, I’d very much welcome comments/suggestions — particularly about alternative/additional readings at the right kind of introductory level. (Also very welcome, advance suggestions for what should appear in the planned later section when we briefly revisit intuitionism at a more sophisticated level in Part III of the Guide.)
The chapter on model theory in the Beginning Mathematical Logic Study Guide was last updated quite recently, in particular to take account of Roman Kossak’s nice 20221 book Model Theory for Beginners (College Publications). Rather little has changed, then, in this current revision, except some minor tidying (though I have dropped as unnecessary a previously footnoted long proof). But still, here it is, the revised Chapter 5 (as it is now numbered).
What to cover in the Guide straight after standard classical FOL?
Theories expressed in first-order languages with a first-order logic turn out to have their limitations — that’s a theme that will recur when we look at model theory, theories of arithmetic, and set theory. You will find explicit contrasts being drawn with richer theories expressed in second-order languages with a second-order logic. That’s why — although this is of course a judgement call — I do on balance think it is worth knowing just something early on about second-order logic, in order to be in a position to understand something of the contrasts being drawn. Hence this next short chapter.
Here is the first main chapter of the Study Guide, on First-Order Logic. Nothing much has changed in the recommendations (or the occasional disparaging comments about non-recommended books!). However, the surrounding chat has been tidied up. I have in particular heeded a friendly warning about “mission creep” (the overview sections were getting too long, too detailed — especially about various proof-systems). So I hope the balance is improved.
One comment (which I have also now added to Chapter 1 — the section on “Choices, choices” where I say something about how I have decided which texts to recommend). If I were choosing a text book around which to shape a lecture course on FOL, or some other topic, I would no doubt be looking at many of the same books that I mention in the Guide; but my preference-rankings could well be rather different. So, to emphasize, the recommendations in this Guide are for books which I think should be particularly good for self-studying logic, without the benefit of classroom introductions or backup.
As I’ve mentioned before, I have started work on revising/updating/extending/cutting-down the much-used Study Guide (Teach Yourself Logic as was, now retitled a bit more helpfully Beginning Mathematical Logic).
I’d thought about dropping the three-part structure. But I have decided, after some experimentation, to keep it. So after some preliminaries, Part I is on the core math logic curriculum. Part II (fairly short) looks sideways at some ways of deviating from/extending standard FOL. Part III follows up the topics of Part I at a more advanced level. So, for example, there is an introductory chapter on e.g. model theory in Part I, and then some suggestions about more advanced reading on model theory in another chapter in Part III. (Having one long chapter on model theory, one long chapter on arithmetic, etc. made for unwieldy and dauntingly long chapters, so that’s why it is back to the original plan.)
Over the next couple of weeks, I’ll be posting some early revised chapters from Part I, and I’ll very much be welcoming comments and suggestions (and corrections, of course) at this stage. Please, please, don’t hesitate to have your say (either using the comments boxes, or by email to peter_smith at logicmatters.net). A lot of students — possibly including your own students! — are downloading the Guide each month: if you think they are being led astray, now is the time to say!
Here then, for starters, are the Preface and a couple of preliminary chapters. Not terribly exciting, but much snappier than before. They will explain more about the structure and coverage of the Guide to those who don’t already know it. Next up, the long key chapter on FOL.
So August was the first full month for Logic Matters with its snappy new web host, and with its sparse new look. Everything seems to have settled down to be working pretty satisfactorily (though some further minor tinkering remains to be done when I am in the mood). The stats are pretty much in line with the previous averages — just under 40K unique visitors in the first month. Or so they say. I’m never sure quite what to read into such absolute numbers.
Relative numbers are more reliable, no doubt. And one consistency is that — month by month — the Study Guide gets downloaded more than the Three Big Red Logic Books combined. So really that settles what I need to do next. Namely, eschew all kinds of logical distractions and concentrate on actually finishing rewriting the damned thing: no more procrastination. So that’s my plan for the next ten weeks. I have a time-table. And, if things don’t go too far adrift, I hope to start posting excerpts from the new version here by the end of the month. Who knows? — I might even get a few useful comments/suggestions from new contributors …