Peter Smith's Blog, page 37

On apparently not avoiding explosion after all

table.center { width: 20%; margin-left: auto; margin-right: auto; text-align: center;}table.center2 { width: 40%; margin-left: auto; margin-right: auto; text-align: center;}

I’ve been drafting some notes on “Other logics” for Beginning Mathematical Logic, and am currently writing something about relevant logics. A seemingly obvious point occurred to me about a familiar semantic story for First Degree Entailment — one that has surely been made before, but (because I haven’t read enough, or because my eyes glazed over at some crucial point, or because my memory is playing up) I can’t recall seeing discussed. So I’m wondering what the fan of that sort of semantic story says in response. Here’s an excerpt from what I’ve drafted (which also includes stuff about disjunctive syllogism as that is relevant in the context from which this comes), raising the point in question:

Logicians are an ingenious bunch. And it isn’t difficult to cook-up a formal system for a propositional language equipped with connectives written “” and “’ for which analogues of disjunctive syllogism and explosion don’t generally hold.

For example, suppose we build a model which assigns every wff one of four values. Label the values T, B, N, F. And suppose that, given an assignment of such values to atomic wffs, we compute the values of complex wffs using the following tables:

TFBBNNFTTBNFTTTTTBTBTBNTTNNNTBNF

These tables are to be read in the obvious way. So, for example, if takes the value B, and takes the value N, then [image error] takes the value B and takes the value T.

Suppose in addition that we define a quasi-entailment relation as follows: some premisses [image error] entail a given conclusion [image error] — in symbols — just if, on any valuation which makes each premiss either T or B, the conclusion is also either T or B.

Then, lo and behold, the analogue of disjunctive syllogism is not always a correct entailment: on the same suggested valuations, both and are either T or B, while is N, so [image error]. And we don’t always get explosion either, since both and are B while is N, so .

Which is all fine and good: but what is the logical significance of this construction? Can we give some semantic interpretation to the assignments of values, so that our tables really do have something to do with negation and disjunction, and so that entailment does become a genuine consequence relation?

Well, suppose — just suppose! — that propositions can not only be plain true or plain false but can also be both true and false at the same time, or neither true nor false. In a phrase, suppose there can be truth-value gluts and truth-value gaps.

Then there will indeed be four truth-related values a proposition can take — T (true), B (both true and false), N (neither), F (false). And, interpreting the values like that, the tables we have given arguably respect the meaning of `not’ and `or’. For example, if is both true and false, the same should go for . While if is both true and false, and is neither, then is true because its first disjunct is, but it isn’t also false as that would require both disjuncts to be false (or so we might argue). Moreover, the intuitive idea of entailment as truth-preservation is still reflected in the definition of entailment, which says that if premisses are all true (though maybe false as well), the conclusion is true (though maybe false as well).

But what on earth can we make of that supposition that some propositions are both true and false at the same time? This will seem simply absurd to most of us.

However, a vocal minority of philosophers do famously argue that while, to be sure, regular sentences
can’t be both true or false, the likes of the paradoxical liar sentence “This sentence is false” can be. It is fair to say that few are persuaded by this line. However, I don’t want to get entangled in that debate here. For it isn’t clear that this extravagant idea actually helps very much. Suppose we do countenance the possibility that some special sentences have the deviant status of being both true and false (or being neither). Then we might reasonably propose to add to our formal logical apparatus an operator ‘!’ to signal that a sentence is not deviant in that way, governed by the following table:

TTBFNFFT

Why not? After all, we have use for such a sign, given that we are confident of many sentences in use that they are not deviant cases. But then note that . And similarly, if say and are the atoms present in , then always holds. Yet this modified form of explosion — when built out of regular claims, a contradictory pair entails anything — is surely just as unwelcome as the original unrestricted form of explosion. (Parallel remarks apply to disjunctive syllogism. We still have, e.g., .)

So we haven’t really got anywhere, in particular if our concern is to give a satisfyingly non-explosive account of entailment.

Or so it seems! Comments?

The post On apparently not avoiding explosion after all appeared first on Logic Matters.

In hidden place, so lett my days forthe pass

One of the last poems of Sir Thomas Wyatt seems apt to these strange times. The whirl of the world has slowed right down for many of us, with cautious avoidance of too-public spaces, and few social encounters. But the quiet has brought — at least for the lucky — its own unexpected pleasures. And with the steady reminders of the fragility of our days, a chance — without the usual noise — to come more to terms with that:

Stond who so list upon the slipper toppe
of courtes estates, and lett me heare rejoyce;
and use me quyet without lett or stope,
unknowen in courte, that hath such brackish joyes.
In hidden place, so lett my dayes forthe passe,
that when my years be done, withouten noyse,
I may dye aged after the common trace,
For him death greep'the right hard by the croppe
that is moche knowen of other, and of himself alas,
doth die unknowen, dazed with dredful face.

Sir Thomas had witnessed the execution of friends, dazed with dreadful face, his patron Thomas Cromwell had fallen, and he himself had recently been accused to treason. No wonder, the wish to leaves court’s estates far behind.

He died very suddenly shortly after writing this, when sent on a mission to Falmouth. To quote from Alice Oswald’s wonderful short introduction to her choice of Wyatt’s poems,  “He rode too fast, caught a chill, and died at a friend’s house in Dorset. Strangely, for a man of his status, he was buried not in his own grave, but in his host’s family tomb. His mistress, Elisabeth Darrell, whom he’d been forced to leave two years before, was living in Exeter, and I can’t help wondering,” Oswald continues, “whether, on his way to the West Country, he decided to fake his own death to rejoin her. The beauty of that idea is that it changes the poem ‘Stond who so list …’ from a wish into a whispered decision” to let his days pass in a hidden place.

I rather hope that that is true.

The post In hidden place, so lett my days forthe pass appeared first on Logic Matters.

The revised Study Guide — Modal logics

Delayed by various 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 in to 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.

The post The revised Study Guide — Modal logics appeared first on Logic Matters.

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.

The post Piranese, not Piranese appeared first on Logic Matters.

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.

The post Tim Button on set theory appeared first on Logic Matters.

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 the very idea of 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 post Beklemishev’s worm appeared first on Logic Matters.

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!

The post The revised Study Guide — Part I appeared first on Logic Matters.

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

The post Offer: free web-hosting for three months appeared first on Logic Matters.

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.

The post A First Journey: Chs 1 to 4 appeared first on Logic Matters.

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

The post A First Journey Through Logic? appeared first on Logic Matters.