Peter Smith's Blog, page 109

Teach Yourself Logic, again

There’s an even bigger, even better, shiny new Version 10.0 of the TYL Study Guide now available at the usual URL http://www.logicmatters.net/tyl/  Form an orderly queue …

The  structure of the Guide has significantly changed again (hence the jump in version number). The key section on basic first-order logic at the beginning of the mathematical logic chapter was getting more and more sprawling: it has now been hived off into a separate chapter, divided into sections, and further expanded. My sense is that quite a few readers are particularly interested in getting advice on this first step after baby logic, so nearly all the effort in this particular revision of the Guide has been concentrated on making improvements here. So, inter alia, there are new comments on four outstanding relatively elementary books: Derek Goldrei’s Propositional and Predicate Calculus, Melvin Fitting’s  First-Order Logic and Automated Theorem Proving,  Raymond Smullyan’s Logical Labyrinths, and (not least) Jan von Plato’s very recent Elements of Logical Reasoning.

I still intend sometime to return to say more about the last of these when I’ve had a chance to re-read it: it is in many ways a very welcome addition to the literature. For the moment, I just remark that this book is based on the author’s introductory lectures. I rather suspect that without his lectures and classroom work to round things out, the fairly bare bones presented here in a relatively short compass would be quite tough as a first introduction, as von Plato talks about a number of variant natural deduction and sequent calculi. But suppose you have already met one system of natural deduction, and (still a beginner) want to know rather more about ‘proof-theoretic’ aspects of this and related systems. Suppose, for example, that you want to know about variant ways of setting up ND systems, about proof-search, about the relation with so-called sequent calculi, etc. Then this is a very clear, very approachable and interesting book. Experts will see that there are some novel twists, with deductive systems tweaked to have some very nice features: beginners will be put on the road towards understanding some of the initial concerns and issues in proof theory.

Logic matters, but not that much, apparently …

Looking at the Leiter blog … and no, this isn’t going to be about certain recent kerfuffles, where there has perhaps been rather too much rushing to judgement.

As I was saying, looking at the Leiter blog, I’m struck by the new list of “recent hires“. So far, there are sixty two “tenure-track and post-doc” appointments listed. Only four mention logic at all in any shape or form, and judging from publication lists and websites, the relevant people’s interests are in non-technical philosophy of logic overlapping with the philosophy of language and epistemology (topics like vagueness, theories of truth,  the epistemology of basic logical principles, the sense in which Russell was a logicist). Only one person on the whole list mentions philosophy of mathematics at all (and again, only with that same historical paper on Russell’s logicism to show for it). Fine topics to be interested in, but not perhaps at the core of logic or philosophy of maths.

It could be that Leiter’s list — or rather the list provided on his comment thread — is a bit unrepresentative. But it could be one more straw in the wind, showing how far the direction in most philosophy departments has turned from a central engagement with two of the founding disciplines of analytical philosophy.

A few quiet updates

Some recent changes/additions to the site:

There’s was a quiet update of Godel Without (too many) Tears a couple of weeks ago adding a new section, and slightly tinkering with what I say about recursive-but-not-primitive-recursive functions to remove a possible suggestio false.
There’s also been an update to a handout on Tennenbaum’s Theorem which adds a section on how not to prove the theorem and tinkers elsewhere.
The writing of exercises-and-solutions for the Gödel book proceeds at a snail’s pace, but there is a possibly interesting set of exercises on (informal) induction now added.

Next task of this kind: to get back to the Teach Yourself Logic Guide. For a start, I’ve three introductory books on my desk with different virtues, that I’d like to add notes on. In particular, Jan von Plato’s Elements of Logical Reasoning is very recently out with CUP and provides an interestingly route into logic, and although intended as an introductory book for students  has elements that will certainly interest their teachers too. More in due course …

Logical snippets

For about eighteen months now, I’ve been a regular visitor to the very useful question-and-answer site, math.stackexchange.com – this is a student-orientated forum, not to be confused with the truly wonderful mathoverflow.net which is its research-level counterpart. OK, you can think of this as (hopefully) constructive procrastination on my part …

Of course, many of the questions there, including many I’ve found myself answering, are very ephemeral or very localized or based on very specific confusions. But a small proportion of the exchanges I’ve contributed to which might, for one reason or another, be of some interest, even help, to other students — at least, to beginners and near beginners.

So I’ve put together a page of links to these logical scraps, morsels, excerpts, … snippets, shall we say. I’ve grouped the links by level and/or topic.

In praise of … Rachel Podger/ATOS Trio

We’ve been to two exceptional concerts in the last few days. First we went up to the Wigmore Hall for the Schubert birthday concert, where the ATOS trio played the two Schubert piano trios to deserved acclaim from a rapt audience. Wonderfully nuanced playing, deeply felt. About as good as it gets for performances of these stunning pieces  (it is time the ATOS recorded them). If you get the chance to see the trio, they really are quite outstanding.

Then a very different evening, listening to Rachel Podger and Brecon Baroque playing eight of the concertos from Vivaldi’s L’estro Armonico  in the antechapel at King’s College. I love their deservedly multi-award-winning recording of La Stragavanza, and the live concert was just terrific — played with verve and enjoyment, playfulness and charm, and a lot of light and shade. Technically brilliant too. The performances made the case wonderfully well for Rachel Podger’s description of these works, in her lovely talk to the audience after the first concerto, as intriguingly complex and rule-bending. The audience was sadly a bit thin, but again was bowled over. A recording of L’estro Armonico is the next project for these players together: you will want the CDs when they are out, and in the meantime get their earlier Vivaldi recording (their Bach is brilliant too …).

GWT2

A complete first draft of the revised version of Gödel Without Tears is now available for download here.

I hope in due course to improve the suggestions for further reading, particularly with pointers to resources on the web. But the notes are at least now online in a reasonable initial form, and are certainly better than what they replace. Please do let me know about typos/thinkos!

Any suggestions for web resources on Robinson Arithmetic, PA, primitive recursive functions, etc.?

As I’ve said, I’m in the middle of revising my much-downloaded introductory notes Gödel Without (Too Many) Tears. I’d rather like to add to the end of each chunk of the notes a very short section of “Further/Parallel Reading”, where this ideally points to again to freely available material — i.e. webpages or pdfs which are at a similar sort of introductory level (and very clear, and relatively short).

I’d love to hear, then, about any free resources out there (other than Wikipedia!) that you have found particularly useful as a student or teacher, on any of the following topics from the first half of the notes:

 The very idea of a diagonal argument
 Robinson Arithmetic
Induction
(First-order) Peano Arithmetic
The beginnings of the arithmetical hierarchy/quantifier complexity
Primitive recursive functions
Why the p.r. functions can be expressed in the language of basic arithmetic/ represented in Robinson Arithmetic.

Pointers to other people’s lecture handouts and all other suggestions most gratefully received!

GWT again, TYL again, Haydn again

Just to note that more sections of Gödel Without (Too Many) Tears have been revised: you can always get the latest version here.

I hope it isn’t laziness or fatigue, but I find (slightly to my surprise) that I’m proceeding with quite light touch updating, rather than major rewriting — even when the corresponding parts of the second edition of the book have been significantly reorganised. But as I read through, I still think GWT works reasonably well, in its own terms, and I don’t want to spoil that. So I’m clarifying, re-sectioning, cutting a few things out, trying to improve readability, rather than anything more ambitious. Enjoy!

GWT gets a significant number of downloads (which is what makes it worth plugging away at improving it). But the Teach Yourself Logic Study Guide continues to be downloaded even more often, so I guess duty calls, and I need to get back to work on that. There’s a somewhat daunting list of suggestions of ways of improving/extending it. (Remind me: just how did I get myself embroiled in this seemingly unending project  …?)

On another theme entirely, a couple of months back I discovered that there’s a 32 CD boxed set of all the Academy Of Ancient Music’s recordings of Haydn symphonies under Christopher Hogwood (that’s not a complete set, but Symphonies 1–75, and six more). I got it remarkably cheaply, via an Amazon associate: but it doesn’t seem listed just at the moment. But if you can get your hands of the set (or indeed any of the individual volumes the set collects), these performances are an unalloyed delight. Just the thing for accompanying writing logic handouts …

Konstancja Duff playing Schubert

Another post today, again spreading the word — this time not about a maths result I chanced to stumble across, but about a young pianist (who happens to be a recent Cambridge philosophy student, and who is now studying for a Masters in Performance at the Royal College of Music). Again, I just chanced to come across Konstancja Duff’s SoundCloud page, and recognising her name I started listening in particular to her performance there of the Schubert G Major sonata. And then I continued listening, and listened again. It is a very good, serious and reflective (philosophical!) performance of one of Schubert’s masterpieces. I thought it rather remarkable, enjoyed it a great deal, and hope you will too.

Colouring natural numbers, colouring real numbers

If you have lots of objects lined up in a row, and only a relatively small palette of colours to paint them with, then you’ll expect to be able to find some patterns lurking in any colouring of the objects.

Here’s a famous and lovely combinatorial theorem to that effect due to Van der Waerden.

For any r and k, there is an N big enough so that, however the numbers 1, 2, 3, … N are coloured with r colours, there will be an monochromatic arithmetic progression of numbers which is k long.

For example, suppose you have r = 7 colours, and put k = 4, then there is a number N = W(7, 4) such that, it doesn’t matter how you colour the first N or more positive integers with 7 colours, you’ll find an arithmetical sequence of numbers a, a + e, a + 2e, a + 3e  which are all the same colour. As is so often the way with numbers that crop up in this sort of combinatorics, no one knows how big W(7, 4) is: the best published upper limit for such numbers is huge.

Here’s a simple corollary of  Van der Waerden’s theorem (take the case where k = 4, and remark that  a + a + 3e  = a + e + a + 2e)

For any finite number of colours, however the positive integers are coloured with those colours, there will be distinct numbers a, b, c, d the same colour such that a + d = b + c.

So far so good. But now let’s ask: does this still hold if instead of considering a finite colouring of the countably many positive integers we consider a countable colouring of  the uncountably many reals? In other words, does the following claim hold:

(E) For any -colouring of the real numbers, there exist distinct numbers a, b, c, d the same colour such that a + d = b + c.

Or since a colouring is a function from objects to colours (or numbers labelling colours) we can drop the metaphor and rephrase (E) like this.

(E*) For any function there are four distinct reals, a, b, c, d such that f(a)  = f(b) = f(c) = f(d), and a + d = b + c.

So is (E*) true? Which, you might think,  seems a natural enough question to ask if you like combinatorial results and like thinking about what results carry over from finite/countable cases to non-countable cases. And the question looks humdrum enough to have a determinate answer.   No?

Yet Erdős showed that (E*) can’t be proved or disproved by ZFC. Why so? Because (E*) turns out to be equivalent to the negation of the Continuum Hypothesis. Which is surely a surprise. At any rate,  (E*) is the most seemingly humdrum proposition I’ve come across, a proposition not-obviously-about-the-size-of-sets, that is independent of our favourite foundational theory.

Make of that what you will! — but I just thought it was fun to spread the word. You’ll learn more, and be able to follow up references, in an arXiv paper by Stephen Fenner  and William Gasarch here.