Year: 2021

Going back and forth

You might have missed Jacob Plotkin’s comment a week ago about about a reference (by me!) to “Cantor’s back-and-forth proof”:

Cantor did not invent/discover or use this method of proof. That honor belongs independently to Felix Hausdorff and E.V. Huntington.

Jacob gave a reference to the short paper where he spells out the evidence. I’ve now had a chance to read it, and it is interesting and instructive (and after all, it is always better to get our history right rather than wrong). So let me add a link to where you can find the paper!

Now’s the time to buy …

For reasons I really won’t bore you with, I need to be republishing my three print-on-demand paperback books, in order to make them more widely available (e.g. in Australia). I’ll also take the opportunity of arranging for — still inexpensive — hardbacks to be published, which will become available through bookstores and library suppliers (with proper ISBNs, etc., to gladden your librarian’s heart). I hope this is all done by mid June.

At the moment you have to use Am*z*n: Intro to Formal Logic is just £8.99/$11; Intro to Gödel’s Theorems is £7.99/$9.99; and Gödel Without (Too Many) Tears is £3.99/$4.99 — with comparable prices in euros. Amazing bargains, of course :) But for reasons I also won’t bore you with, the paperback prices might have to increase a little on re-publishing. So now could be just the time to buy one of the Big Red Logic Books, if you’ve been dithering. Just saying ….

PHQ and Boris Giltburg, radio recording

Boris Giltburg and the Pavel Haas Quartet were playing last night to a live audience at the Louisiana Museum of Modern Art (that’s in Denmark, near Elsinore, on the Øresund coast).

The concert — in which they performed the Brahms and Dvorak Piano Quintets — was broadcast on Danish radio, and the concert is available for listening online on DR P2. (Player at the foot of the page; their concert starts at 43:04). Great stuff!

Roman Kossak’s Model Theory for Beginners

Following on from his Mathematical Logic (2018), Roman Kossak has now published Model Theory for Beginners: 15 Lectures (College Publications, 2021). As the title indicates, the fifteen chapters of this short book — just 138 pages — have their origin in introductory lectures given to graduate students in CUNY. Roughly speaking, the topics of the first half of this new book overlap quite closely with the second half of his previous book. And after grumbling a bit about Part I of that earlier book, I did warm considerably to the model-theoretic Part II, which I think makes for a very approachable elementary introduction to a cluster of issues about definability.

The new treatment is aimed at a rather more sophisticated reader, the writing is a bit less relaxed, and indeed becomes increasingly terse as the book progresses (in later chapters, I could often have done with a sentence or two more motivational chat). But overall, this strikes me as a welcome book. Though I’m at all not sure it is all suitable for beginners.

In a little more detail, after initial chapters on structures and (first-order) languages, Chapters 3 and 4 are on definability and on simple results such as that ordering is not definable in (Z, +). Chapter 5 introduces the notion of types, and e.g. gives Cantor’s back-and-forth proof that countable dense linearly ordered sets without endpoints are isomorphic to (Q, <). Chapter 6 defines elementary equivalence and elementary extension, and establishes the Tarski-Vaught test. Then Chapter 7 proves the compactness theorem, Henkin-style, with Chapter 8 using compactness to establish some results about non-standard models of arithmetic and set theory.

So there is a somewhat different arrangement of initial topics here, compared with books whose first steps in model theory are applications of  compactness. But the early chapters are indeed nicely done. However, I don’t think that Kossak’s Chapter 8 will be found an outstandingly clear and helpful first introduction to applications of compactness — it will probably be best read after e.g. Goldrei’s nice final chapter in his logic text.

Chapter 9 is on categoricity — in particular,  countable categoricity. (Very sensibly, Kossak wants to keep his use of set theory in this book to a minimum; but he does have a section here looking at κ-categoricity for larger cardinals κ.) And now the book starts requiring rather more of its reader. Chapter 10 is on indiscernibility and the Ehrenfeucht-Mostowski Theorem: but it is difficult to get a sense from this chapter of quite why this matters.

Up to this point, the structures we’ve been looking at are all officially relational. Chapter 11 adds functions, and discusses Skolem functions and Skolemization (this could have been more relaxed and helpful). We return to arithmetic in Chapter 12; there’s a compressed  discussion leading up to a version of Robinson’s model-theoretic proof of Tarski’s theorem of the arithmetic undefinability of arithmetic truth. But I rather doubt that this will be readily accessible to someone who hasn’t already read e.g. some of Kaye’s book on non-standard models of PA and met ideas like overspill.

The last three chapters are more advanced still, on saturation, automorphisms of recursively saturated structures, and (very briefly) stability. Are these topics for those just starting out on model theory? That’s a judgement call. But I suspect that the mode of presentation could be found quite challenging by many beginners — for me, more classroom asides in later chapters would have been welcome.

So as with Kossak’s earlier Mathematical Logic, then, I have rather different reactions to the two halves of Beginning Model Theory. But I’d say that the first eight or nine chapters do work very well under the advertised title (and I’ll be recommending them in the Study Guide). Later chapters are probably to be read in parallel with familiar moderately advanced texts like Marker’s classic.

Finally, bonus points for publishing very inexpensively with College Publications, and with tidy LaTeX layout too (however, they still can’t design a nice title page and verso!). But dock half a point for the number of minor typos …

Mathematical logic from a compsci angle?

In the Study Guide entry on First-Order Logic, after the list of main reading suggestions, there is a further list of suggested parallel/additional reading which ends by warmly recommending Melvin Fitting’s First-Order Logic and Automated Theorem Proving (Springer, 2nd edn 2012). Although published in a series aimed at compsci students, this should certainly appeal to logicians who are primarily philosophers or mathematicians but who want to know a little more about some themes (e.g. resolution proof systems) of special interest to computer science, and who want to re-encounter some familiar ideas approached from a slightly different angle. You can, if you want, skip some of the bits on Prolog and still get a particularly elegantly and clearly written account.

I’ve been wondering whether there are other books also written for computer scientists which could similarly appeal to the Guide’s intended readers. I know, of course, Michael Huth and Mark Ryan’s Logic in Computer Science (CUP, 2nd edn 2004). I haven’t reread this recently, but I recall it as being attractively and clearly written — the long first two chapters on propositional and predicate logic are well done, with a few interesting extras for the philosophical or mathematical reader (e.g. on SAT solvers). But then the later chapters go off in directions no doubt of key concern to computer scientist, but less interesting for the rest of us (for me, anyway!).

I’ve had Mordechai Ben-Ari’s Mathematical Logic for Computer Science (Springer 3rd edn 2012) recommended to me. But I thought this pretty second-rate.   The level of exposition is poor, and indeed at points seemingly outright confused (e.g. about the status of the Deduction Theorem for a Hilbert system). Someone who already has a grip on the standard math logic approaches could, I guess, get something out of the book by diving straight into the chapters on propositional resolution, SAT solvers, and first-order resolution, for example. But I didn’t find this material well explained: it is surely treated more pleasingly elsewhere.

To repeat, then, I’m interested in locating logic books coming from a compsci angle which will however also appeal to someone whose main interest remains in philosophy or mathematics. Luis Augusto’s book is advertised as aimed at such readers, but you know what I think of that. So are there other options?  I’d be very interested to hear!

Not so unlocked

Cows sheltering under a tree, in the meadow below Ely Cathedral. Not the most clement spring day, but still a lovely sight. We are still erring on the side of caution in our strayings from home (because too many others are evidently not). But Ely makes a welcome change of scene from our small corner of Cambridge. And there’s the wonderful Topping’s book shop to visit. Small steps out of lockdown. There’s a longish way for us to go on to whatever is the new normal; but I think it is the same story for many of our generation.

Luis Augusto’s Formal Logic

“Of making many logic books there is no end; and much study is a weariness of the flesh.” The author of logical Ecclesiastes had probably just been reading the likes of Luis M. Augusto’s unnecessary Formal Logic: Classical Problems and Proofs (College Publications, 2019). I’ve noted before that this publisher’s quality control is lousy. Fortunately, because its books are relatively inexpensive, you can take the chance and order one which has a tempting-seeming  blurb, without cursing too much if the punt doesn’t come off.

This particular book aims to highlight problems which, though they “feature in introductory logic textbooks aimed at computer science students, … are largely or wholly absent from textbooks targeting a mathematical or philosophical studentship.” Looking for books with a compsci angle for the Logic Guide, I was intrigued.  But, apart from being written in poor almost-English, the technical exposition here is unappealingly hard going, and the level of motivational explanation third-rate. It could be so much better. So this is just a warning note: if you are similarly tempted by the blurb for this book, simply resist. And if that sounds a bit tetchy, it could be because my flesh is more than a bit weary after trying to study it for a day.

Roman Kossak’s Mathematical Logic

What do you make of this?

Think of a number, say 123. What is 123? It is a sequence of digits. To know what this sequence represents, we need to understand the decimal system. The symbols 1, 2, and 3 are digits. Digits represent the first ten counting numbers (starting with zero). The number corresponding to 123 is 1 . 100 + 2 . 10 + 3 . 1. In this representation, the number has been split into groups: three ones (units), two tens, and one hundred.

I’d worry that someone who wrote that is hopelessly confused between numerals (expressions which reprsesent) and numbers (what the numerals represent). And just how can a number (that very thing which is represented) be “split into groups”?

Or what about this, following some examples of equinumerous collections?

All those equinumerous collections have their individual features, but there is one thing that they all have in common. That is this one thing that we call the size. This common feature is the size of the collection and of all other collections that are equinumerous with it. Now we can introduce the following, more formal definition: a counting number is the size of a finite collection.

So numbers are “features”, i.e. properties? A moment ago they were things that can be split into groups! (Great-uncle Frege is not resting quietly …)

Let’s put this sort of thing down to a certain arm-waving carelessness rather than confusion: still, it doesn’t exactly inspire confidence in the more conceptual/philosophical remarks in Roman Kossak’s Mathematical Logic (Springer 2018).

Actually, this book is mis-titled. There is little core logic here. The early chapter entitled ‘First-Order Logic’ is a fleeting introduction to first-order languages, too fast for real newbies, and the idea of a formal deductive system is only mentioned, and then without elaboration, at p.132 (and the book has just 155 pages before the final summary chapter and the appendices start). What the book is in fact centrally about is signalled by its subtitle: “On Numbers, Sets, Structures, and Symmetry”.

As Kossak says in his final summary, his “aim in this book was to explain the concept of mathematical structure, and to show examples of techniques that are used to study them. It would be hard to do it honestly without introducing some elements of logic and set theory.” The examples of structures are near all numerical ones. So Part I is an introduction to the construction of the integers, rationals and reals from the naturals, and a lightning tour of some of the presupposed set theory. This is done in with a fair amount of motivational chat, so some credit for that. But I still think the beginner would be notably better off reading one of the usual introductions to these ideas in elementary set theory books like Enderton’s or Goldrei’s. Charitably, the author is rushing on to get to what really does interest him, the book’s distinctive content in the seventy-odd pages of Part II.

And this Part, to get much more positive, is a very approachable introduction to some simple model theoretic ideas, but taking a rather different route to that of some familiar texts.  So Kossak explores the first-order definable features of various structures defined over the natural numbers, the integers, the rationals, the reals, and the complex numbers, and he nicely brings out some of the perhaps unexpected complications. He helps himself to the compactness theorem and e.g. the Tarski–Seidenberg theorem (which are not proved) to give partial demonstrations of various results. And along the way, the reader is introduced not only to basic notions like that of an elementary extension but also somewhat more sophisticated ideas like being a minimal structure. This is done with a light touch, helpful examples, and again a good amount of motivational chat. I’m not sure that some of the sketched proofs are quite as clear as they could be, and there can be philosophical wobbles in the commentaries. But this Part of Kossak’s book does, I think, get across some basic model theoretic ideas without too many tears, in an unusually accessible way, making connections that aren’t often brought out; and (those wobbles apart) I enjoyed it and learnt from it.

Added: However, since writing this, Kossak’s 2021 short book Model Theory for Beginners has landed on my desk, which covers the same ground as Part II and significantly more but in the same accessible style. At first glance, this looks very likely to be the book to go for, and I’ll report back in a few days.

PHQ — Prague spring

Six months after their last live concert, with Covid restrictions easing in the Czech Republic, the Pavel Haas Quartet have been able to start playing again, streaming two concerts over the last weekend. It was wonderful to hear them.

One highlight, for me, was getting to know Martinů’s 7th quartet, which they played so engagingly in the first of the concerts, recorded for a Duke University series. John Gilhooly at Wigmore Hall had persuaded the PHQ to play a Martinů cycle starting last year  — but of course, like so many other musical plans, all that was thwarted by Covid. Hopefully the cycle (and a recording or two?) will still happen sooner rather than later: if this sample was anything to go by, PHQ will make Martinů their own in the same way that they give such compelling performances of the other Czech greats.

Another highlight was the performance of the Brahms Piano Quintet, joined by Boris Giltburg in the second of the concerts, recorded for a Spivey Hall series. In particular, the gentle second movement was simply magical (with Giltburg making other pianists in a couple of discs I know seem positively flatfooted). Another recording, please, of this together perhaps with the Shostakovich Piano Quintet! — for I’ve also heard Giltburg play that with the PHQ a couple of times quite outstandingly.

These concerts, perhaps, had more significance for the PHQ than just restarting playing; for they were joined for the first time by their new violist Luosha Fang. They had suddenly parted company with the violist, composer and conductor Jiří Kabát at the beginning of 2020, asked the prize-winning Luosha Fang to join them, and (again) plans were blown up by Covid. Now, I don’t have a good enough ear to be the best judge, but from these concerts she is surely an inspired choice for them. Her playing seems wonderful (for example in the exposed viola part in the movement  of the second quartet by Pavel Haas that PHQ played as an encore for the Duke concert), and very much in keeping with the style of the quartet. We can only hope this transatlantic marriage works out for them all.

The links I gave for the concerts in a post last week have now expired, as each was only available for three days. Hopefully the recordings will eventually be made available more widely.

Added: The PHQ and Boris Giltburg are playing the Spivey Hall programme, plus Bartok, in the Library of Congress series, freely available from June 18th —  details here.

Scroll to Top