Logic

Logic Works?

I can hardly complain about people adding unnecessarily to the over-supply of introductory logic books, having done it myself. But here’s yet another one, Logic Works: A Rigorous Introduction to Formal Logic by Lorne Falkenstein, Scott Stapleford and Molly Kao (published just six months ago by Routledge). I’ve been asked what I think of it. Having now taken a look at the book, I’ll save you the trouble of doing the same. It’s pretty bad. Not that I’ve struggled through all 645 pages. But you’ll forgive me that: life is short and patience limited.

That’s a strange subtitle, no? As if introductions to formal logic aren’t usually rigorous. Or at least, as rigorous as they need to be — and as they say, “sufficient unto the day is the rigour thereof”. You might be tempted to worry, then, that a book that especially advertises itself as “rigorous” is likely to be unnecessarily laboured. You’d be right. And actually it is worse than that. It’s not just heavy-handed in explaining the technicalities, but quite generally the long-winded prose is depressingly clotted and terminally uninviting. I pity the poor students who have this inflicted on them!

Two sample episodes. Chapter 6 presents a Fitch-style deduction system for propositional logic. Good choice (though the system isn’t as streamlined as it could be). But the authors plod through a turgid presentation, without zip and zest, making very heavy going of things. It is really pretty difficult to imagine a reader coming to appreciate that by doing things Fitch-style we can arrive at a really rather elegant, natural, and highly user-friendly system. Things aren’t helped by the printed pages being a typographical mess. 

The same applies in spades to the grimly laborious chapters introducing the language of predicate logic. Who would ever guess from these longueurs that the beautiful and compelling basic idea of a quantifier/variable notation for expressions of generality is so very neat and attractive once explained that it can be introduced well enough to convey a reading knowledge to any beginning mathematics student in half a lecture? (I was surprised to see that one of the authors does have some mathematical background — yet the writing throughout gives no sense of the aesthetic attractions of rigorous mathematical ideas.)

I could go into more detail, but I won’t. A rather depressing read, then, which I can’t recommend at all. If you want a good introduction to formal logic which also ranges quite widely, I’d stick to Nick Smith’s!

[Added And see Phil’s comment!]

Juliette Kennedy, Gödel’s Incompleteness Theorems

I was in the CUP Bookshop the other day, and saw physical copies of the Elements series for the first time. I have to say that the books are suprisingly poorly produced, and very expensive for what they are. I suspect that the Elements are primarily designed for online reading; and I certainly won’t be buying physical copies.

I’ve now read Juliette Kennedy’s contribution on Gödel’s Incompleteness Theorems. Who knows who the reader is supposed to be? It is apparently someone who needs the notion of a primitive recursive function explained on p. 11, while on p. 24 we get a hard-core forcing argument to prove that “There is no Borel function F(s) from infinite sequences of reals to reals such that if ran(s) = ran(s’), then F(s) = F(s’), and moreover F(s) is always outside ran(s)” (‘ran’ isn’t explained). This is just bizarre. What were the editors of this particular series thinking?

Whatever the author’s strengths, they don’t include the knack of attractive exposition. So I can’t recommend this for reading as a book. But if you already know your way around the Gödelian themes, you could perhaps treat this Element as an occasionally useful scrapbook to dip into, to follow up various references (indeed, some new to me). And I’ll leave it at that.

Greg Restall, Proofs and Models in Philosophical Logic

I notice that Juliette Kennedy’s book on Gödel’s incompleteness theorems in the Cambridge Elements series has now also been published. I’ll no doubt get round to commenting on that in due course, along with John Bell’s short book on type theory. But first, let me say something about Greg Restall’s contribution to the series: as I said, for the coming few days you can freely download a PDF here.

There does seem little consistency in the level/intended audience of the various books in this series. As we will see, Bell’s book is pretty hard-core graduate level, and mathematical in style and approach. Burgess’s book I found to be a bit of a mixed bag: the earlier sections are nicely approachable at an introductory level; but the later overview of topics in higher set theory — though indeed interesting and well done — seems written for a different, significantly more mathematically sophisticated, audience. It is good to report, then, that Greg Restall — as his title promises — does keep philosophers and philosophical issues firmly in mind; he writes with great clarity at a level that should be pretty consistently accessible to someone who has done a first formal logic course.

After a short scene-setting introduction to the context, there are three main sections, titled ‘Proofs’, ‘Models’ and ‘Connections’. So, the first section is predictably on proof-styles — Frege-Hilbert proofs, Gentzen natural deduction, single-conclusion sequent calculi, multi-conclusion sequent calculi — with, along the way, discussions of ‘tonk’, of the role of contraction in deriving certain paradoxes, and more. I enjoyed reading this, and it strikes me as extremely well done (a definite recommendation for motivational reading in the proof-theory chapter of the Beginning Math Logic guide).

I can’t myself muster quite the same enthusiasm for the ‘Models’ section — though it is written with the same enviable clarity and zest. For what we get here is a discussion of variant models (at the level of propositional logic) with three values, with truth-value  gaps, and truth-value gluts, and with (re)-definitions of logical consequence to match, discussed with an eye on the treatment of various paradoxes (the Liar, the Curry paradox, the Sorites). I know there are many philosophers who get really excited by this sort of thing. Not me. However, if you are one, then you’ll find Restall’s discussion a very nicely organized introductory overview.

The shorter ‘Connections’ section, as you’d expect, says something technical about soundness and completeness proofs; but it also makes interesting remarks about the philosophical significance of such proofs, depending on whether you take a truth-first or inferentialist approach to semantics. (And then this is related back to the discussion of the paradoxes.)

If you aren’t a paradox-monger and think that truth-value gluts and the like are the work of the devil, you can skim some bits and still get a lot out of reading Restall’s book. For it is always good to stand back and see an area — even one you know quite well — being organised by an insightful and eminently clear logician. Overall, then, an excellent and very welcome Element.

The Logic of Number

Having been so very struck by Russell and Frege as a student —  a long time ago in a galaxy far, far away — I have always wanted some form of logicism to be true. And the deviant form canvassed by Tennant back in his rich 1987 book Anti-Realism and Logic (I mean, deviating from neo-Fregean version we all know) is surely worth more attention than it has widely received. So I’m looking forward to reading Tennant’s latest defence of his form of logicism, in his new book The Logic of Number, published a few weeks ago at a typically extortionate OUP price.

On a quick browse, the book goes in a somewhat different direction to what I was expecting, having read Tennant’s 2008 piece ‘Natural Logicism via the Logic of Orderly Pairing’. The additional new apparatus for developing arithmetic added in that paper seems not to be in play again here. Rather, the book doesn’t (I think) develop arithmetic as far, but instead goes on to discuss logicist accounts of rationals and reals.

I’ll perhaps try to say something more about the book in due course, when some other reading commitments are done and dusted. Meanwhile you might well in fact be able to take a look if interested. For The Logic of Number, I’m glad to say, has just been also made available at Oxford Scholarship Online. So if your university library has a suitable OUP subscription, it should be free to read.

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.

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

Scroll to Top