Study Guide

Ahah! Another step onwards …

So a first proof copy of the Study Guide has arrived surprisingly promptly.

Partly this is to check the cover design, but mainly it is for reading through for typos and layout blunders and other typographical mishaps. It is really startling what newly hits the eye when you have a draft in front of you in physical book form, even after you have previously seen piles of print-out.

But I’m pleased with the look of the book. As you’ll have seen, the design inside and out is just like the other Big Red Logic Books — but people say they look pretty smart, so I’ll rest content with that!

The revised Study Guide: a final draft?

I’ve now checked through the complete draft of Beginning Mathematical Logic: A Study Guide, and  you can download it here (all viii + 185 pages of it).

I’ve made a few late content changes (the long ‘overview’ sections on FOL and on set theory have been split into two parts, and I’ve added a few paragraphs in each case). Obviously, this is the sort of project that one could keep tinkering with almost without limit. But I’m going to call it a day.

So it will be one final read through for me, for residual typos and to check for aesthetic flaws like hyphenations that cross pages and so on. And I need to design the cover properly and that sort of thing. Meanwhile, this is the last call for corrections and suggestions, before putting it into the Amazon paperback publishing system for those who would like a hard copy. (Yes, yes, I know that using Amazon is not ideal: but I can and will set the price so low that their royalty take will be pennies. And the result will be much cheaper than the alternatives.)

Added January 21 There’s an updated version (some typographical changes, a few typos corrected, some minor changes in Chapters 1, 2, 4 and 5.) I’ve started setting up the KDP paperback process, doing the cover design etc. The paperback will come out at x + 184 pages, unless the last minute changes alter that, and yet still can be priced at £4.99/$5.99, which is a decent bargain. If you’ve seen a paperback of one of the other, same-format, Big Red Logic books, you’ll know that Amazon in fact make an unexpectedly decent job of their cheap print-on-demand paperbacks.

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.

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

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