Peter Smith's Blog, page 110

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.

Gödel book related …

Do please check that your library by now has a copy of the second edition of An Introduction of Gödel’s Theorems (it really is significantly better than the first edition, with a lot of changes throughout). Having put in the work to improve the book, I’d like you/your students to have the best version available!
I’ve just updated the corrections page for IGT2 (thanks to Richard Baron for spotting a few more, fortunately minor, errors). 
I have also updated the page on what to read before/after/instead of IGT2.
I have further updated the notes Gödel Without Tears (the first three episodes  have now been revised).
In updating those notes I’ve removed a few unnecessarily fancy asides — the material appears in a different guise in the newest set of exercises for the book (which will you will find here). Indeed my plan as I work through updating the GWT notes is, at the same time, to add  exercises on the topics of revised episodes as I go along.

The Higgins

The Early Ploughman, Samuel Palmer

We hadn’t been to The Higgins since the now united galleries and museum in Bedford re-opened last year after a really major refurbishment. The building is beautifully renovated    (or mostly so — the café is not particularly attractively laid out), and the museum displays look terrific. In particular, there is currently a very enjoyable small exhibition A National Art: Watercolour & the British Landscape Tradition. This is drawn entirely from the gallery’s own collection, and includes works by Samuel Palmer (including the etching above), Turner, and Cotman, alongside twentieth-century watercolours. Some very fine pieces. All very well worth a visit, and indeed a re-visit.