Logic

The revised Study Guide — final chapter

No, not an occasion to hang out bunting and pop the cork of some fizz. The penultimate chapter  is not finished yet. But here is a first draft of the final chapter!

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.

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.

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.

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 — elementary proof theory

Here is the draft final chapter of Part I of Beginning Mathematical Logic — so this is the last of the group of chapters on core topics at an elementary level. This one on proof theory is newly written; comments will therefore be particularly welcome.

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 revised Study Guide — intuitionistic logic

After the minor revisions of earlier chapters of the Beginning Mathematical Logic Study Guide, something more exciting! Here is a brand new chapter on intuitionistic logic.

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.)

And in Big Red Logic Book news …

Brief version: There is now a hardback version available of the second edition of An Introduction to Formal Logic: ISBN 978-1916906327. It should now be available to order from bookshops (as well as from Am*z*n and some other online sellers). It is priced at £20/$25, about the minimum possible. I’ve just got a sample copy and it is very decently produced.

Longer version: You’ll probably recall that I recovered the copyright of the second edition of IFL a year ago so that I could make the PDF freely available (a pretty small gesture in these difficult times, but every little helps). Lots of students, though, do prefer to work from a physical book: so I also set up an inexpensive print-on-demand paperback (to minimise the cost, that is Am*z*n only). 

Now, as I’ve said before, self-publishing has the downside that the word doesn’t get out to librarians via a publisher’s fancy catalogue. But in any case, in last year’s lockdown, and more recently too, librarians were rightly concentrating on improving their e-resources, so it didn’t seem the time to fuss too much about getting physical copies into libraries. However, things are slowly returning to something more like the old normality for library operations. So I have now arranged for ‘proper’ hardback copies — printed by Lightning Source who do small-run/on-demand printing for some academic presses — to be available for library purchase at minimum cost from, inter alia, standard library suppliers. So do please ask your friendly local university or college librarian to order a copy or two (emphasizing, if you need to, that this is a significantly changed book from the first edition). Online resources are all well and good, though problematic for some students: to repeat, at textbook-length, many — like me — do much prefer to have real books available!

The revised Study Guide — model theory

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).

The revised Study Guide — second-order logic

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.

There are no very substantive changes from the previous version. But it is a little tidier in some respects. So here is Chapter 4: Second-order logic, quite briefly.

The revised Study Guide — first-order logic

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.

Scroll to Top