The revised Study Guide — Modal logics

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

A draft of the first chapter of Part II, Chapter 10 on Modal Logics.

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.

Piranese, not Piranese

It gathered such good reviews and was on many prize shortlists too, winning the The Women’s Prize for Fiction 2021. But of the forty novels I’ve read so far this year, this is the one I got the least from. In fact, to be honest, I found Susanna Clarke’s Piranese to be pretentious (“Look at me! how deep and significant …!”) pseudo-philosophical tosh.

But one good thing came out of the irritation that novel engendered. I was prompted to send off for the book of Piranese drawings from the British Museum produced to accompany an exhibition in 2020. And this (remarkably inexpensive) book is really a thing of beauty. And I think I might well prefer these very expressive sketches and freer drawings to such of the familiar etchings that I knew. If you want a pleasurable evening or two exploring monumental and strange spaces, I do warmly recommend you try this Piranese, rather than Piranese.

Tim Button on set theory

Just to note that Tim Button has a trio of linked papers on set theory coming out in the Bulletin of Symbolic Logic, and already downloadable from his website.

The first paper is on ‘Axiomatizing the bare idea of a cumulative hierarchy of set’:

The following bare-bones story introduces the idea of a cumulative hierarchy of pure sets: ‘Sets are arranged in stages. Every set is found at some stage. At any stage S: for any sets found before S, we find a set whose members are exactly those sets.We find nothing else at S’. Surprisingly, this story already guarantees that the sets are arranged in well-ordered levels, and suffices for quasi-categoricity. I show this by presenting Level Theory, a simplification of set theories due to Scott, Montague, Derrick, and Potter.

The second paper is on ‘Axiomatizing the bare idea of a potential hierarchy’:

Potentialists think that the concept of set is importantly modal. Using tensed language as a heuristic, the following bare-bones story introduces the idea of a potential hierarchy of sets: ‘Always: for any sets that existed, there is a set whose members are exactly those sets; there are no other sets’. Surprisingly, this story already guarantees well-foundedness and persistence. Moreover, if we assume that time is linear, the ensuing modal set theory is almost definitionally equivalent with non-modal set theories; specifically, with Level Theory, as developed in Part 1.

The third paper is on ‘A boolean algebra of sets arranged in well-ordered levels’:

On a very natural conception of sets, every set has an absolute complement. The ordinary cumulative hierarchy dismisses this idea outright. But we can rectify this, whilst retaining classical logic. Indeed, we can develop a boolean algebra of sets arranged in well-ordered levels. I show this by presenting Boolean Level Theory, which fuses ordinary Level Theory (from Part 1) with ideas due to Thomas Forster, Alonzo Church, and Urs Oswald. BLT neatly implement Conway’s games and surreal numbers; and a natural extension of BLT is definitionally equivalent with ZF.

Note the punch at the end of each of the second and third abstracts: set theories we might have thought to be significant rivals to the industry standard turn out to be definitionally equivalent to (versions of) it.

One presentational remark. In Potter’s presentation of his version of Scott-Derrick set theory in his Set Theory and its Philosophy the key definitions of a ‘history’ and the ‘accumulation of a history’ are given in a rather take-it-or-leave-it spirit, just as tricks that work. Button’s definitions at the very outset of a ‘history’ and the ‘potentiation of a history’ likewise will give pause those new to Scott’s trick: perhaps just a little more could be said to win over the reader and carry them through.

But that is a very minor quibble. This trio of papers strike me as taken together a simply terrific achievement.

Beklemishev’s worm

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 w is a string of digits x_0x_1...x_n. And we will define w^* to be the result of decreasing w‘s last digit x_n by 1 if you can, or deleting that digit if it is already 0.

And now consider a sequence of worms w_0, w_1, w_2, \ldots constructed according to the following two rules:

(1) if x_n = 0, then put w_{m+1} = w^*_m (chop off the head of the worm!);

(2) if x_n > 0,  let k = be the maximum i < n such that x_i < x_n. Then  put w_{m+1} to be w^*_m followed by m copies of the part of w^*_m starting after position k.

For example, suppose we start with the worm

w_o = 2031

Then the sequence continues …

w_1 =203030
w_2 = 20303
w_3 = 20302222
w_4 = 203022212221222122212221
w_5 = 203022212221222122212220 following by five copies of 22212221222122212220

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!

THEOREM

(1) For any initial worm w_0, there is an m such that w_m 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.]

The revised Study Guide — Part I

Here, then, is a full draft of Part I of the revised Beginning Mathematical Logic Study Guide (vi + 114pp).

It is, I hope, in a reasonable state. But it goes without saying that comments, suggestions and corrections of the inevitable typos will still be most welcome.

The plan now is to add the much shorter Part II (briefly looking over the fence at some areas of logic mostly of interest to philosophers rather than mathematicians), and then the more substantial Part III (advanced readings on the topics of Part I). But hopefully, revising these further chapters will be relatively speedy, as I won’t be writing expansive overviews for them. I want this time-consuming project off my laptop by the end of the year!

Offer: free web-hosting for three months

Earlier in the year, I moved Logic Matters from Bluehost to Siteground. I chose Siteground after doing an amount of homework — they do typically get well recommended in the techie press.

I’m very pleased to have made the effort, as this site now runs much more snappily, and various management tasks are made just that bit more easy. I’ve had very little occasion to use their support services, but when I have done, all has gone smoothly enough. So I wouldn’t hesitate also to recommend Siteground, especially for hosting a WordPress site. They are somewhat more expensive after the first year than Bluehost, but you get what you pay for.

I mention all this because Sitegound have just e-mailed “a limited time exclusive offer that you can share with your friends, relatives, co-workers or anyone else”:

People who visit our website through your referral link until November 25, 2021 will be able to sign up and use any of our shared hosting plans for 3 months free of charge. Additionally, they will be able to request 1 manual professional website migration from our support team and will not be charged for this service either. This is an exclusive offer that is not publicly available on our website and can only be granted by our existing customers like you.

So: for anyone thinking of moving host, or indeed starting their first site, here is the referral link! (Disclosure: as is the way with these things, I get a bit of free hosting for any successful referral.)

A First Journey: Chs 1 to 4

The authors write that they have “deliberately chosen not to write another comprehensive textbook, of which there already exist quite a few excellent ones, but instead to deliver a slim text which provides direct routes to some significant results of general interest.” But they also say that the book is intended for “undergraduate students, graduate students at any stage, or working mathematicians, who seek a first exposure to core material of mathematical logic and some of its applications.” So we are led to expect the chapters here to be accessible to beginners on a topic, though perhaps beginners with a reasonable level of mathematical maturity.

So how do things go? And more specifically — my immediate interest, of course, in looking at this book here and now! — are any of the chapters appropriate for recommending in the Beginning Mathematical Logic Study Guide?

Chapter 1 is called “Counting to Infinity”, and is more-or-less entirely a fast-track introduction to ordinals and then cardinals treated set-theoretically but informally (i.e. without getting entangled with formalized ZFC). Before the exercises start, this is just 21 relentless pages of definitions/theorems/proofs with very little by way of explanatory  chat. To take just one example, the naive reader may very well wonder why ordinal exponentiation is defined in terms of functions with finite support (a notion which is defined, used once, and never motivated). What kind of reader is going to find this sort of presentation helpful? Perhaps as after-the-event lecture notes, following on from more informal presentations, these pages might have been useful to those attending the course from which these notes arise. But as a stand-alone text, the body of this chapter has nothing to really recommend it. (There is some interest in the exercises though.)

Chapter 2, “First-order Logic” is if anything worse. It is a baldly presented gallop through a Mendelson-style axiomatic system (with particularly dense thickets of symbols along the way). I really can’t imagine anyone coming away from, e.g., the completeness proof with a good sense of what’s going on: there are so many, much better, treatments out there.

Chapter 3 is “First Steps in Model Theory”. We get Tarski-Vaught after 3 pages (compare, after 43 pages of Kossak’s Model Theory for Beginners, and after 66 pages of Kirby’s  An Invitation to Model Theory), and we get quantifier elimination after 8 pages (not treated by Kosssak, and Kirby takes 97 pages to introduce the idea). We get to Ax’s Theorem in 16 pages. I wonder how many will be illuminated by this sort of ultra-rushed tour?

Chapter 4 is on “Recursive Functions”, defining primitive recursive, partial recursive and total recursive functions, touching on Turing machines (without a single diagram or a single program illustrated), proves the Turing-computable functions are recursive, proves the unsolvability of the halting problem, etc. Now, this is markedly less sophisticated material than the model theory in the previous chapter, so this present chapter is probably quite a bit more accessible. But on the other hand, there is zero elegance here, and yet this is an area where we can make the concepts and the proof-ideas look so delightful (and thereby engender a good understanding). So I again can’t recommend this as a good read.

Sorry to be, thus far, so consistently negative: but take it as a community service to warn off any unwary readers. And I  would have given up on the book at this point, except that the next chapter on arithmetic promises “a complete proof of Gödel’s Second Incompleteness Theorem”. Really? I think I should look to see …


And just to balance out all that negativity, let me offer some brief but very warm praise for another book (of a rather different kind). I couldn’t resist picking up a copy of Paolo Aluffi’s Algebra: Notes from the Underground from the CUP Bookshop a couple of days ago. This is so far looking terrific, a real pleasure to read. It is “only” an undergrad intro to algebra (I have my reasons for wanting to look at an up-to-date entry-level text to see how it handles things). But, as with his big grad-level book, I do very much admire and envy Aluffi’s presentational style. I may say more about this when I have read more.

A First Journey Through Logic?

Home from Rhodes, post-flight covid tests thankfully negative, a few domestic chores done, and so it’s back to work on the Study Guide …

The initial task is to tidy the hundred or so pages of Part I of the Guide, covering the core mathematical logic curriculum at an elementary level. I’ve posted drafts of the nine  chapters here on the blog, which have each been downloaded hundreds of times. But I’ve had almost no comments/correctiond. Which I’ve decided to take in a cheerfully positive spirit — I like to infer that people don’t think I’m going so horribly wrong that they need to protest loudly (if only to stop me leading their students astray)! So the tidying work will, I hope, mainly be a matter of trying to imposing greater consistency of level and tone between the nine chapters.

However, first, I had better do a bit of homework, and get acquainted with a fairly recent book which I hadn’t noticed before, A First Journey through Logic by Martin Hills and François Loeser, published in the AMS Student Mathematical Library in 2019. “The book starts with a presentation of naive set theory, the theory of sets that mathematicians use on a daily basis. Each subsequent chapter presents one of the main areas of mathematical logic: first order logic and formal proofs, model theory, recursion theory, Gödel’s incompleteness theorem, and, finally, the axiomatic set theory. Each chapter includes several interesting highlights— outside of logic when possible either in the main text, or as exercises or appendices.” Which is a promising prospectus, with its chapters covering just the same main topics as Chapters 2 to 7 of the Study Guide. However, this is a book of under two hundred small-format pages. Which rather suggests that either the authors aren’t aiming to get very far on any particular topic (though such a book can be very useful when well done, cf. Robert Wolf’s A Tour Through Mathemtical Logic). Or else our authors must have written with considerable compression at the probable cost of ready accessibility.

I’m afraid that our authors have taken the second line. They say in their Introduction that the book originates from a course taught at École Normale Supérieure: and it reads exactly like souped-up lecture notes spelling out carefully lots of technical details, to back up a course of lectures which explain the rationales for the various formal constructions. But without the explanatory, arm-waving, motivational chat, the arid formal details make for a hard and uninviting journey. Perhaps some chapters might serve as brisk revision material: but surely they not the place to make a beginning on mathematical logic.

I’ll say just a bit more in two follow-up posts.

Postcard from Rhodes

Ancient Kamiros

A week on Rhodes, in stunning October weather, to stay with the Digital Nomad Daughter. Our first time travelling abroad since the pandemic struck. We seem to have survived the covid festival at the airport (we didn’t think our fellow travellers’ mask game was exactly optimal), and fingers crossed for the return. But here seems safer than at home.

Of course being with family again is terrific; and Rhodes is a delight in all kinds of ways. But it’s been particularly good as well to have been jolted out of our routine ways. After two years of restrictions at various levels, it is all too easy to fall into quite a deep rut, where one day runs into another with very little to distinguish them. To be sure, it’s a comfortable rut (and we are very conscious how fortunate we are compared with so many); but still, it is enervating to say the least. A vivid reminder of other possibilities is correspondingly enlivening. Let’s hope the effect doesn’t wear off the moment we step back into grey Cambridge days. Though, given the grim direction that covid statistics are taking, and not just in the UK, who knows if we will be able travel again soon.

But we’ll worry about that later. For now, there is sun and an empty beach to contend with …

The Pavel Haas Quartet play Brahms

The Pavel Haas Quartet back at long last at Wigmore Hall last night, playing two Brahms Quintets, with their original violist Pavel Nikl for the string quintet and their good friend Boris Giltburg for the piano quintet. In simply great form, as the audience agreed, judging by the reception. Free to stream (performance starts about 4.30 in). Don’t miss them.

Scroll to Top