Peter Smith's Blog, page 18

Isaacson and Heck on Gödelian matters

In case you missed a recent post by Richard Heck on the FOM list, let me recommend two pieces linked there.

First, at the Saul Kripke’s memorial conference in May, Dan Isaacson gave a talk on “Kripke on Gödel Incompleteness” where he discussed six of Kripke’s papers around and about incompleteness. You can download Isaacson’s interesting paper here. His §5 is very brisk on Kripke’s very short 2020/21 paper “Gödel’s Theorem and direct self-reference”: I also say something about Kripke’s note in the two-page Appendix to the second edition of GWT.

Heck remarks

The construction Kripke describes in “Gödel’s theorem and direct self-reference” was independently discovered and published by both Albert Visser [see his handbook paper on the liar] and myself [in “Self-Reference and the Languages of Arithmetic”]. There’s a footnote in Kripke’s paper about this, but, frankly, I don’t see what’s new in that paper of Kripke’s (though it may well be that he had all this before Visser and I did, I don’t know). Once you have the construction, you can obviously use it for any purpose for which Gödel numberings have been used, e.g., the proof of the incompleteness theorem.

There has been quite a lot of recent work, in fact, on the details of Gödel numberings and intensionality that can arise because of differences between them. For example, the mentioned paper of mine describes a theory of truth that is consistent given ‘typical’ Gödel numberings but inconsistent if you use a Gödel numbering that permits the sort of ‘direct’ self-reference at issue in Kripke’s discussion. Other papers in this tradition include Halbach and Visser’s two papers on “Self-Reference in Arithmetic”, Grabmayr and Visser’s “Self-Reference Upfront”, Grabmayr’s “On the Invariance of Gödel’s Second Theorem With Regard to Numberings”, and Grabmayr, Halbach, and Ye’s “Varieties of Self-Reference in Metamathematics”.

I confess most of those titles are new to me, as I’ve not been keeping up with this literature recently, and given the authors the pointers are likely to be well worth following up.

Something I have read with enjoyment is Heck’s own overview of some of these ideas and related matters, written for a forthcoming handbook on the liar paradox. Written with characteristic clarity here is a version of the paper.

The post Isaacson and Heck on Gödelian matters appeared first on Logic Matters.

Mileti, Modern Mathematical Logic, Chs 11–12

We are on the home straight … only 117 pages to go. The last two long chapters of MML are on “Computable sets and functions” and “Logic, computation, and incompleteness”.

In broad-brush terms, the content is pretty much the sort of thing you could predict. So Chapter 11, some seventy pages, introduces the primitive recursive functions, shows they are not all the intuitively computable functions, and so goes on to discuss partial recursive functions. Then we get a machine model of computation, with Mileti choosing URM machines over Turing machines (fair enough!). We find out that the URM computable partial functions are just the partial recursive functions, and there is some sensible discussion of the Church-Turing Thesis. The chapter concludes by looking at computably enumerable (but perhaps not computable) sets.

Then Chapter 12 starts by talking about coding expressions and deductions, and about arithmetic definability. §12.3 shows that the set of true sentences of formal first-order arithmetic is undecidable. MML then starts looking at Robinson Arithmetic in particular and shows that it can represent computable functions. The final section of the book gives us a proof of incompleteness.

So these final two chapters cover material which is already beautifully covered in some classic books from e.g. the early editions of Boolos and Jeffrey  onwards. To be sure, these chapters are perfectly respectable, and Mileti can write with an engaging turn of phrase. But are they particularly attractively done, especially accessible, splendidly clear, plainly to be preferred to the existing recommendations in the BML Study Guide? Without going into more detail, I’d say not — or at least, not for solo self-study: and they wouldn’t really be my first choice for supplementary reading either. (Though they’ll probably get an honourable mention in the next iteration of the Guide.)

To be frank, having finished the book, speed-reading some and taking other parts at a more leisurely pace, I’m still not quite sure what the point of Mileti’s text is. The title rather belies the content — what’s so “modern” here? The treatments of the various topics do seem usually thoroughly conventional and often rather old-school. And I’m not persuaded that — sixty years on from Mendelson! — there is still any special additional virtue in having core FOL, some model theory, set theory, and some computability theory all done within one set of covers that makes the book worth more that the sum of its parts. So, in summary judgement, I’m afraid I can’t join in the chorus of rather extravagant praise printed at the front of the book. Sorry!

The post Mileti, Modern Mathematical Logic, Chs 11–12 appeared first on Logic Matters.

Schubert on Sunday 2: Eric Lu plays D959

The young American pianist Eric Lu won the Leeds Piano Competition in 2018 at the age of 20. He has since released two discs, the second of music by Schubert, including the extraordinary penultimate sonata in A major, D959.

Some have found Lu’s performance over-romantic. But I like it greatly and find his interpretation very affecting indeed. Here he is playing the sonata in Warsaw in 2021.

The post Schubert on Sunday 2: Eric Lu plays D959 appeared first on Logic Matters.

Category Theory I, the paperback!

So, at last, the paperback version of Category Theory I is available. Sound the trumpets!

Just put the title or the ISBN 1916906370 in the search field of your local Amazon store. And yes, at least for the moment, this is only available as a print-on-demand book from Amazon. But that keeps the price as low as possible — about three coffees. So treat yourself!

The Amazon KDP system makes later editorial revisions particularly easy and cost-free for me, another plus. As I’ve said before, I’m still thinking of this first paperback version as a revisable beta version: it’s there for those — like me — who prefer to work with printed copy once a text gets past a certain length. All comments, corrections, and suggestions for improvement are still most welcome. The PDF of course continues to be freely downloadable: the short Preface and Introduction to that PDF will tell you about the book project, in the most unlikely event that you are reading this but don’t know about it!

The post Category Theory I, the paperback! appeared first on Logic Matters.

Who’s counting? Great fun?

This blog is antediluvian, having been going over seventeen years. Blogging isn’t the cool thing any more; but some of us persist. I noticed a post from Brian Leiter yesterday saying it was the twentieth birthday of his often-provoking but still readable philosophy blog. Congratulations!

Leiter remarks that he gets over three million page views a year, which struck me as a staggering number. I couldn’t help but wonder what Logic Matters gets: over a million, it turns out, according to my host’s stats system (though since I’m not using the same stats counter as Leiter, I could well not be comparing like with like). But even if my stats  exaggerate by a factor of two — perhaps because I have a static front page which many will pass through and Leiter Reports doesn’t — that’s still again a staggering number.

Leiter monetizes his blog and sells advertising space at rather amazing prices. I wouldn’t want to emulate that. True, it costs me over £500 a year to keep Logic Matters going, because the necessary bandwidth is quite high. But so long as I average about 20p royalty for each printed Big Red Logic Book (yes, folks, I’m an extortionist) I cover those costs, and that’s more than good enough. I’m having an amount of fun and spreading the logical word for free: what’s not to like?

Talking of spreading the logical word, I’ve found myself spending a bit more time just recently on math.stackexchange answering the occasional question. Well, it beats wasting time/getting angry on that site just rebranded with the sans-serif swastika. More stats: math.stackexchange keeps a tally of people reached — this is the “estimated number of times people viewed your helpful posts (based on page views of your questions and questions where you wrote highly-ranked answers)”. My tally, after ten or so years of sporadically answering questions there, is another staggering number: two million.

Answering questions on sites like math.stackexchange gets you precisely zero official academic brownie points (unless things have significantly changed since I was in the game). But as far as ”impact” goes, it is surely one of the more useful things you can do. And again, it’s fun for free — apart from giving something back for those times you’ve learnt from other’s answers.

Not your idea of fun? Fair enough. OK, let me recommend The Great if you aren’t already a fan. Series 3 has started, but we can’t speak for that — because we thought, why not go back and rewatch from the beginning of Series 1? So that’s what we are doing, and enjoying it even more than the first time around. Surely that is great fun in anyone’s book. Huzzah!

The post Who’s counting? Great fun? appeared first on Logic Matters.

Mileti, Modern Mathematical Logic, Chs 7–10

To continue. Chapter 7 of Mileti’s MML is titled “Model theory”. Of the five sections, the first three can’t be recommended. In particular, §7.2 makes such heavy weather of that fun topic, nonstandard models of arithmetic and analysis. There are so many alternative treatments which will be more accessible and give a more intuitive sense of what’s going on. By contrast, I thought §7.4 on quantifier elimination did a better-than-often job at explaining the key ideas and working through examples. §7.5 on algebraically closed fields worked pretty well too.

And now we get two chapters on set theory, together amounting to almost a hundred pages. There’s a major oddity. The phrase “cumulative hierarchy” is never mentioned: nor is there any talk of sets being found at levels indexed by the ordinals. The usual V-shaped diagram of the universe with ordinals running up the spine is nowhere to be seen. I do find this very strange — and not very ‘modern’ either! There are minor oddities too. For example, the usual way of showing that the Cartesian product of and (defined as the set of Kuratowski pairs ) is a set according to the ZFC axioms is to use Separation to carve it out of the set in the obvious way. Mileti instead uses an unobvious construction using Replacement. Why? A reader might well come away from the discussion with the impression that Replacement is required to get Cartesian products and hence all the constructions of relations and functions which depend on that. (I rather suspect that Mileti isn’t much interested in ‘modern’ finer-tuned discussions of what depends on what, such as the question of  which set-theoretic claims really do depend on something as strong as replacement.)

So: Chapter 8, without explicitly mentioning the cumulative hierarchy (let alone the possibility of potentially more natural axiomatisations in terms of levels) gives us ZFC, and the usual sort of story about how to develop arithmetic and analysis in set theory. The mentioned oddities apart it is generally OK: but the recommendations for entry-level set theory in the Beginning Mathematical Logic Guide do the job better and in a friendlier way. However I should mention that, at the end of the chapter, §8.7 on models, sets and classes, does do the job of explaining the role of class talk rather nicely.

Chapter 9 is on ordinals, cardinals, and the axiom of choice; and I thought this chapter worked comparatively well. (Perhaps the perceived unevenness is all in my mind! And I know from my own efforts in writing long-ish books that maintaining a consistent level of approachability, of proportions of helpful less formal chat around the more formal stuff and so on, is difficult. I can only report how I am finding the book — and, as they say, your mileage may vary.)

Finally in this group, Chapter 10 is much shorter, just two sections on “Set-theoretic methods in model theory”. The first, just four pages, is on sizes of models; and then the second is an opaque and to my mind misjudged ten pages on ultraproducts.

And so it goes: as with the earlier chapters, a mixed bag.

The post Mileti, Modern Mathematical Logic, Chs 7–10 appeared first on Logic Matters.

Mileti, Modern Mathematical Logic, Chs 4–6

Chapter 4 of Mileti’s MML is on “First-order logic: languages and structures” — so some 40 pages on basic semantics. Chapter 5 is on “Relationships between structures” — another longish chapter, 35 pages on substructures, homomorphisms between structures, embeddings, and the like. Chapter 6 , “Implications and compactness”, is an even longer chapter — some 48 pages introducing a proof system for FOL and proving soundness and completeness, then drawing out some consequences of compactness, before going on to talk about theories framed in a first-order language, with a substantial final section on random graphs. I can’t say that I have carefully read every word, but that hasn’t stopped me forming pretty firm opinions.

In headline terms: I found the basic treatment of the semantics, and again of the formal proof-system and completeness, pretty unattractive. Not to put too fine a point on it, I would have thought that a typical student would find some of the episodes here rather rebarbative. On the other hand, the more model-theoretic Chapter 5, and the second half of Chapter 6 strike me as notably more readable.

In just a bit more detail, we get a highly conventional story about the syntax of FOL languages. In particular, the same symbols are recruited for double duty, as part of the construction of a quantifier operator, and for use as parameters/temporary names — in other words “” has to serve, in different contexts, as both a bound and a free variable. Of course, this means we have to fuss about rules for distinguishing free from bound occurrences of variables, and fuss at length about avoiding unwanted variable capture when substituting terms for variables (MML‘s §4.4 on substitution is no less than eleven rather dense pages long). Why do things this old-fashioned way? It’s only ninety years since Gentzen taught us how to do better, in ways that have become more and more familiar as modern proof-theorists spread the word!

In the middle of Chapter 4, though, there is a nice short first section on definability. Issues of definability and related topics about what classes of structures can be captured by which languages, and so on, are then taken up in the next chapter — which ends with a nice section §5.5 which introduces the Tarski-Vaught test and shows how to get from there to a version of the downward L-S theorem for a countable language. §4.3 and Chapter 5 could I think be tackled standalone by someone who knows some basic FOL from other sources; and these sections do work pretty well.

After a section defining semantic entailment for FOL, Chapter 6 introduces a deductive system for quantificational logic, far too briskly (it seems to me) to be of much use to anyone who is encountering one for the first time. And the soundness and completeness results are done no more attractively than for the earlier propositional logic case. I can’t recommend these sections at all. But then §6.4 on applications of compactness and §6.5 on theories are nice (and the concluding section on random graphs is an interesting bonus).

A pretty mixed verdict on these three chapters, then.

The post Mileti, Modern Mathematical Logic, Chs 4–6 appeared first on Logic Matters.

Schubert on Sunday 1: Janine Jansen and friends play the Octet

I don’t know how many readers of this blog follow up the musical posts, but I do get occasional appreciative messages. Anyway, I am in the mood to start another series of weekly links to performance on video. This time, of pieces all by one composer, for as long as the spirit moves me. (Is it just by chance that, in the past, talking to other philosophical or logical music lovers, it seemed to be Schubert who was so often mentioned as particularly close to their hearts too?)

Where to start? As we’ll find, there are some stunning video recordings available. I’ll try to leaven the heart-wrenching with the more consoling, though in the end I suspect there might be more of the former (did I say it would all be Schubert?). But you can’t get more full of joy than this, to start with.

The post Schubert on Sunday 1: Janine Jansen and friends play the Octet appeared first on Logic Matters.

Mileti, Modern Mathematical Logic, Chs 1–3

Towards the end of last year, within a week or two of publishing Jeremy Avigad’s Mathematical Logic and Computation (a bumpy ride, but very well worth having), CUP also released another textbook, Joseph Mileti’s Modern Mathematical Logic. I’d earlier seen a substantial set of notes that Mileti had posted online, and (to be frank) wasn’t over-impressed; so I haven’t been rushing to read this. But I thought I would now take a look at the book version, with a view to seeing whether there are any chapters which I’d want to mention or even recommend in the next iteration of the Beginning Mathematical Logic Study Guide.

Level and coverage? MML is announced as aimed at advanced undergraduates or beginning graduates (by US standards, anyway), though the book is distinctly less ambitious than Avigad’s. Mileti says he assumes familiarity with some basic abstract algebra; however, this seems perhaps more needed to best appreciate some illustrative examples rather than as necessary background for grasping core content. The coverage is broadly conventional, starting with basic first-order logic (though with the opposite emphasis to Avigad: there’s no real proof theory). Then there’s a little model theory, entry-level axiomatic set theory, some computability theory, and a treatment of incompleteness. At this point, then, at least just glancing at the table of contents and diving into the first chapters, I’m not at all sure quite what makes this a book on especially modern mathematical logic in either topics or general approach.

I rather liked the tone of the short Introduction; and going through the next couple of chapters, there is friendly signposting and some nice turns of phrase. But …

But Chapter 2, the first substantial chapter, is thirty pages on ‘Induction and Recursion’. We get a pretty dense treatment of what Mileti calls “generating systems”, three different ways of defining the set of generated whatnots, proofs that these definitions come to the same, then a criterion for free generating systems, a proof we can do recursive definitions over the free systems, and so on. This is all done in what strikes me as a rather heavy-handed way which could be pretty off-putting as a way of starting out. Many students, I would have thought, will just feel they have been made to labour unnecessarily hard at this point for small returns. And when the very general apparatus is applied e.g. in the next chapter to prove, e.g., unique parsing results, I don’t think that what we get is more illuminating than a more local argument. (I suppose my pedagogic inclination in such cases is to motivate a general proof idea by proving an interesting local case first and then, at an appropriate point later, saying “Hey, we can generalize …”.) I note, by the way, that by the end of §2.2 the reader is already supposed to know about countable sets and accept without demur that a countable union of countable sets is countable.

Chapter 3, the next fifty pages, is on propositional logic. A minor complaint is that the arrow connective is initially introduce in the preface as meaning “implies” (oh dear), and then we get not a word of discussion of the truth-functional treatment of the connective unless my attention flickered. But my main beef here is on the chosen formal proof system. This is advertised as natural deduction, but it is a sequent system, where on the left of sequents we get sequences rather than sets (why?). And although the rules are set out in a way that would naturally invite tree-shaped proofs, they are actually applied to produce linear proofs (why?). Moreover, the chosen rule-set is not happily motivated (we have disjunctive syllogism rather than a proper vE rule: double negation elimination is called ¬E). OK Mileti  isn’t going to be interested in proof theory; but he should at least have chosen a modern(!) proof system with proof-theoretic virtues!

As for completeness, we get the sort of proof that (a) involves building up a maximal consistent set starting from some given wffs by going along looking at every possible wff in turn to see if it can next be chucked into our growing collection while maintaining consistency, rather than the sort of proof that (b) chucks in simpler truth-makers only as needed, Hintikka style. We are not told what might make the Henkin strategy better than the more economical Hintikka one.

To finish on a positive note, perhaps the best/most interesting thing in this chapter is the final section (and the accompanying exercises) on compactness, which gives a nice range of applications.

To be continued

The post Mileti, Modern Mathematical Logic, Chs 1–3 appeared first on Logic Matters.

Postcard from Suffolk

A few days near Aldeburgh. The shortest route from Cambridge takes you on minor roads through deepest Suffolk and that part of the journey is a delight in itself. The weather was a lot kinder than predicted when we booked a short stay. In particular, it was perfect during a lovely walk from Snape Maltings (where the famed concert hall is) along the River Alde, round through a wonderful oak wood, and back along the river.

The small towns in the region are very varied. Some seem in very sad and shabby decline. Others seem considerably more flourishing. Aldeburgh itself, while perhaps slightly battered round the edges, gives the impression of being definitely in the second camp and we like it a lot. Even though the sea there seems always to wear a northern countenance.

The post Postcard from Suffolk appeared first on Logic Matters.