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:

  1.  The very idea of a diagonal argument
  2.  Robinson Arithmetic
  3. Induction
  4. (First-order) Peano Arithmetic
  5. The beginnings of the arithmetical hierarchy/quantifier complexity
  6. Primitive recursive functions
  7. 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 [updated: you can still get the set for  £1.70 a disc here]. 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 NW(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 + 3 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 $latex \aleph_0$-colouring of the real numbers, there exist distinct numbers abcd 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 $latex f : \mathbb{R} \to \mathbb{N}$ there are four distinct reals, abcd 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.

Introducing Homotopy Type Theory

Yes, Homotopy Type Theory is the latest, greatest, thing (we are told). Yes, a free book is available, following on from a major year-long program at the Institute for Advanced Study at Princeton in 2013-13, and this will tell you lots about the current state of play. And yes, you too started the book and found it pretty impenetrable. What on earth is going on?

Help is at hand.

Robert Harper at CMU ran a grad course last semester, ‘Introducing Homotopy Type Theory’. Notes written up by his students are online. So too are videos of his lectures (use the “stay on the web” option if visiting the site on an iPad). This all looks a pretty good way in if you are still curious about the HoTT phenomenon.

Gödel Without (Too Many) Tears, 2014 version

I’ve made a start updating the notes Gödel Without Tears.

The previous version of the notes was downloaded nearly three thousand times in the last twelve months: so it certainly seems worth putting in the effort to produce a better version, and to get the notes to integrate better with the new edition of my Gödel book.

Some months ago, I rashly said I might try to run some kind of informal online course based on GWT. But unexpected pressures on my time have made that impossible. I’ll only be able to continue updating the notes at irregular intervals. However, you can leave comments on the GWT page to report typos or unclarities. And if you (or your students) post more substantive queries in a sensible form on math.stackexchange then almost certainly someone (quite possibly me!) will answer them.

Scroll to Top