Year: 2012

Three cheers for TeXShop

As I write this, I’m printing out a hard copy of the Gödel book — hopefully the version to be taken along to CUP along with the PDF file when they re-open next week.

I’ve been tinkering with this second edition, on and off, since I got the contract back in July 2011 (and no doubt bored everyone who visits here by talking about it so much). It’s a long-ish book: 403 pages in all, with lots of symbols, lots of cross-references to resolve, not to mention auto generated bibliography and index. I’ve been using TeXShop + LaTeX (plus BibDesk) on a Mac. How many times did this document processing system crash, foul-up, or produce unintended gremlins over the eighteen months?

Zero. Yep, zero.

I’d say I was really impressed if it weren’t what I’ve come to take for granted. But it is pretty amazing now I stop to think about it. So it surely should occasionally still be said: Three cheers for LaTeX, for BibDesk, and not least to Richard Koch for TeXShop, my constant companion!

In the dunce’s corner …

I’m spending a bit of quality time in the dunce’s corner, having dashed off a ‘solution’ to a problem in propositional calculus (yes propositional calculus, for heaven’s sake) over at math.stackexchange and got it quite wrong. And as fate would have it, I was off-line for a while, staying over with my aged mother, so couldn’t quickly delete it. Ho hum. So much for totting up “reputation points” eh?

OK: here’s the problem for you (from Enderton’s Math Logic book): let # be the three-place connective such that #(A, B, C) is true so long as the majority of A, B, C are true. Show that {#, ¬} is not an expressively adequate set of connectives.

Knowing I’m quite capable of that sort of thing makes the business of doing a final read of  Gödel 2 for thinkos a bit fraught. Even at this last minute stage I’ve found a silly omission. Ah well ….

Still, there are mistakes and mistakes. I had occasion a couple of days ago to look at James Robert Brown’s Philosophy of Mathematics where he makes a complete hash of understanding why the Intermediate Value Theorem is non-trivial (no, a diagram does not cut it). I was wondering about whether to bang on about that here, when — by one of those coincidences — I came across the ever-excellent T.W. Körner‘s Companion to Analysis where he takes a sideswipe at Brown: “The author cannot understand the problems involved in proving results like the intermediate value theorem and has written his book to share his lack of understanding with a wider audience.” Körner than proceeds to give a presentation which should be enough for most readers to work out (at least some of) what’s gone so wrong in Brown’s discussion. Job done.

Proof reading again …

I’m slowly working through the proof-reader’s corrections for Gödel Mark 2 (and re-reading the book carefully one last time as I go). So far, I’ve got through a quarter of the book, and CUP’s reader has found two tiny slips (one a missing space I’d spotted myself, and the other a missing ‘that’ which is arguably optional anyway). OK, the reader also sprinkles around some suggestions for altering punctuation and italicization: but so far, I’m not inclined to make any of those further changes — taking the line that there is no special reason to depart from the conventions I adopted in the first edition which satisfied another proof reader.

So two tiny errors found in the first ninety-odd pages of my submitted PDF. Extremely good, I’d say. But no, it isn’t because I’m amazingly accurate at proof-reading my own work before sending it off. Au contraire. This is very much due to that experiment a few months ago in ‘crowd-sourcing’ the preliminary proof-reading for typos and thinkos. I can only say again how very grateful I am to everyone who helped out. The experiment obviously worked: I recommend it warmly to anyone else writing a similar book.

Weather report

“If you don’t like the weather in New England now, just wait a few minutes.” Mark Twain’s remark applies in spades in Old England. Changeable or what?

But one nice thing about retirement which they don’t tell you  — and I’m trying to look on the bright side here, you understand — is that the weather you experience really does get a whole lot better. For suddenly you have the freedom to snatch whatever nice half-days there are (and there are quite a few scattered about the average week, even this time of year) and you can get out for a walk in the winter sun. And when it is cold and dank and grey all day, you have the freedom to stick at home in the warm, Reading a Good Book or whatever.

Not that my timetable used to be so very constraining, to be honest. But after a few decades you do rather get into a fixed mindset: Thursdays are work days and so it must be nose to the grindstone.

Not now: these days, it is positively Liberty Hall.  Nice morning? Then the proof-correcting can wait. Bitter afternoon (as it is now)? Then it is tea and cake and Haydn and the red pen …

Make mine an Earl Grey.

The Decline of the West, Episode 42

Here’s a very dispiriting new blog post by Tim Gowers about the dire state of school maths teaching in the UK. I’m a bit surprised, though, that he’s surprised by what he discovered (but then being in the happy situation of teaching Trinity mathmos is likely to colour your view of the world!). Certainly, my experience teaching Cambridge philosophy students — a very bright lot — about half of whom had done A-level maths and got top grades, was that very few of them really understood any maths. They might have picked up a bag of tricks to apply in response to some formulaic questions. But as for some conceptual understanding of classical analysis or an appreciation of the idea of rigorous proof ‘in the wild’ … Sigh. (No wonder philosophy of mathematics can leave them cold!)

And judging from the many comments to Tim Gowers’s post, the decline in school maths teaching is not confined to this declining off-shore island.

Well, there’s no point in moaning about this, though I hope my local friendly mathematicians are exercising what influences they can to help stop the rot. But it does mean that there’s a real problem for teachers of logic and writers of logic books aimed at students. We tend to be mathematically ept ourselves, and students are good at dissembling — or at least, at remaining silent — so we can so easily fail to realize just how mathematically inept so many of them are (through no fault of theirs, let it be emphasized). What to do? I don’t have the teaching problem any more: but I still do have the writing problem. I guess I’ve fallen over the years into working with the principle if in doubt, go slower and explain even more. But it does make for long books to write and long books to read.

 

Teach Yourself Logic, #7. A bit of deviance

There’s a new version of the self-help Guide downloadable from the Teach Yourself Logic page (added: updated to Version 7.1, Nov. 26).

Heavens this is time consuming! — but having (as it now seems, foolishly) started, I guess I should do the best job on this that I can. Anyway, there are new sections on extensions of classical logic (second order, plural, free) and deviations from the classical paradigm (intuitionism, relevance logics). There also is a major structural change to the Guide. It is now going to be in two big chapters, one on the basics and one on more advanced stuff. Partly this is to make it all look less daunting (the idea is that any grad student working in logic-relevant areas ought to know the sort of stuff that is in Ch. 1, and then the enthusiasts for this or that area can pursue the relevant sections of Ch. 2). And partly this is to acknowledge the fact more advanced work in one area can often presuppose familiarity the basics in other areas.

All suggestions for improvement welcome as always. I’d welcome in particular any additional introductory suggestions on Second-Order Logic, and on Intuitionistic Logic. At the moment, on Second-Order Logic, I start by mentioning the article

  • Herbert Enderton, ‘Second-order and Higher-order Logic’, Stanford Encyclopedia of Philosophy. http://plato.stanford.edu/entries/logic-higher-order/

And suggest following that up with

  • John L. Bell, David DeVidi and Graham Solomon’s Logical Options: An Introduction to Classical and Alternative Logics (Broadview Press 2001), §3.3.

But now what? Stewart Shapiro, Foundations without Foundationalism: A Case for Second-Order Logic, Oxford Logic Guides 17 (Clarendon Press, 1991) is very accessible — but is there something less weighty to read beforehand?

And on Intuitionist Logic, I suggest starting with

  • John L. Bell, David DeVidi and Graham Solomon’s Logical Options §§5.2, 5.3., which give an elementary explanation of the contructivist motivation for intuitionist logic, and then explains a tree-based proof system for both propositional and predicate logic.
  • Graham Priest, An Introduction to Non-Classical Logic (CUP, much expanded 2nd edition 2008), Chs. 6, 20. These chapters of course flow on naturally from Priest’s treatment in that book of modal logics, first propositional and then pred icate.
  • Then, up a notch in mathematical sophistication (but manageable if you have tackled earlier chapters in this book, so you are familiar with the style), there is Dirk van Dalen, Logic and Structure (Springer, 4th edition 2004), §§5.1–5.3.

We will return in Ch. 2 to some further explorations of intuitionism where we’ll mention e.g. Dummett’s book. But what about other more introductory level material?

 

Postcard from Turin

It’s been a while since we were in Italy, so a quick city break — this time to Turin (a new city for us). The central city is rather impressive, wide colonnaded streets and some large piazzas. And with the streets being laid on pretty much on a grid system, you get some very long urban views, with occasional glimpses of the mountains beyond. We (unsurprisingly) had some pretty good meals, and paused not a few times in cafés — for the best ever macchiato, go to the delightful Caffe Mulassano. But the high point of our visit was (surprisingly) the Museo Egizio. Yes, of course this is famous, usually said to be the best Egyptian museum outside Cairo: but to be honest we went a bit dutifully, only to be bowled over. The collection really is quite overwhelming. The museum is undergoing refurbishment, and a  lot of the exhibits are still shown in a very old fashioned way, but even so, the cumulative effect especially of all the small ancient grave goods is astonishing. And the theatrically lit new display of the monumental statues is exceedingly dramatic. Surely unmissable if you happen to find yourself in Turin.

Teach yourself logic, #5: Arithmetic, computation and Gödelian incompleteness

I’ve just written a (partial) draft of another chunk of my developing Teach Yourself Logic reading guide. As always, comments and suggestions will be very welcome indeed. I’ve tried to restrain myself, but this segment of the Guide is already rather long. But here goes …

A standard part of any logician’s education will be an encounter with first-order Peano Arithmetic as a non-trivial example of a rigorously formulated axiomatic system, and with Gödel’s epoch-making proof of the incompleteness of PA, and indeed of any nice enough theory that can ‘do’ enough arithmetic.

Gödel’s 1931 proof uses facts about primitive recursive functions (a subclass of the computable functions), and you certainly need to know about them. A more general treatment of the idea of an effectively computable function (arguably capturing all of them) was developed a few years later, is of the greatest intrinsic interest and also throws more light on the incompleteness phenomenon. So there’s a choice to be made. Do we look at things in a roughly historical order, proving initial versions of Gödel’s incompleteness theorem before moving on to look at the general treatment of computable functions. Or do we do some of the general theory first? Here are two books to start with which take the two different routes:

  • Peter Smith, An Introduction to Gödel’s Theorems (CUP 2007) does things in the historical order. Don’t be put off by the series title ‘Cambridge Introductions to Philosophy’: putting it in that series was the price I paid for cheap paperback publication. This is still quite a meaty logic book, with a lot of theorems and a lot of proofs, but I hope rendered very accessible.
  • Richard Epstein and Walter Carnielli, Computability: Computable Functions, Logic, and the Foundations of Mathematics (Wadsworth 2nd edn. 2000) does computability theory first. This is a nicely introductory book, clearly done, with lots of interesting historical information too in Epstein’s 28 page timeline on ‘Computability and Undecidability’ at the end of the book.

As you’ll already see from these two books, this is a delightful area. Elementary computability theory is conceptually very neat and natural, and the early Big Results are proved in quite remarkably straightforward ways (just get the hang of the basic ‘diagonalization’ construction, the idea of Gödel-style coding, and one or two other tricks and off you go …).

A notch up in difficulty, here’s another book that focuses on the general theory of computation:

  • George Boolos, John Burgess, Richard Jeffrey, Computability and Logic (CUP 5th edn. 2007). This is the latest edition of an absolute classic. The first version (just by Boolos and Jeffrey) was published in 1974; and there’s in fact a great deal to be said for the 1990 third edition as being the best. The later versions have been done by Burgess and have perhaps lost elegance and some of the individuality, and the level of difficulty has become uneven. But this is still great stuff, and you will want to read the first two parts of the book at an early stage, perhaps being more selective when it comes to the last part, ‘Further Topics’.

An interestingly unusual route to the incompleteness phenomenon is traced in

  • Melvin Fitting, Incompleteness in the Land of Sets (College Publications, 2007). Short, also fairly elementary, elegant and very clear.

After these, where should you go? Here are three stand-out suggestions:

  • Nigel Cutland, Computability: An Introduction to Recursive Function Theory (CUP 1980). This is a rightly much-reprinted classic and is beautifully put together. It does have the look-and-feel of a maths text book. But if you can cope with Boolos and Jeffrey, you can manage this.
  • Raymond Smullyan, Godel’s Incompleteness Theorems (Oxford Logic Guides, OUP, 1992) is another modern classic. Terse and elegant, proving some beautiful slightly abstract versions of the incompleteness theorems.
  • Richard Kaye, Models of Peano Arithmetic (Oxford Logic Guides, OUP, 1991) is a third classic, connecting up the treatment of arithmetic with material on model theory, and telling us a great deal about non-standard models of PA (models which contain more than the ‘real’ natural numbers). And this reveals more about what PA can and can’t prove — though be warned that this book is rather more challenging in places.

That is probably more than enough about the logical basics. The literature on computability is huge, however, and I haven’t yet mentioned any books that approach things from a computer-science rather than a pure-logic perspective, and deal inter alia with the fascinating topic of computational complexity. So I had better touch on a few of those. But first, here’s an aside mentioning a few more books with a logical flavour, at very varied levels:

[At this point, in small print, I go on to mention (with shorter comments)

  1. Rósza Péter, Recursive Functions  (1967).
  2. Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability (1967)
  3. Herbert B. Enderton, ‘Elements of Recursion Theory’, in J. Barwise, ed., Handbook of Mathematical Logic (1977).
  4. Piergiorgio Odifreddi, Classical Recursion Theory , Vol. 1 (1989)
  5. Martin Goldstern and Haim Judah, The Incompleteness Phenomenon (1998).
  6. A. Shen and N. K. Vereshchagin, Computable Functions (2003).
  7. Per Lindström, Aspects of Incompleteness (2003). Terse, not always reader-friendly, but well repays the effort.
  8. Torkel Franzén, Inexaustibility (2004).
  9. S. Barry Cooper, Computability Theory (2004).
which all have virtues of various kinds!]

As I mentioned, computer scientists are — surprise, surprise! — interested in the theory of computation, and their books tend to have a different slant. It is certainly worth knowing at least a little about the topic of computational complexity. I’ll mention just three places to start:

  • Michael Sipser, Introduction to the Theory of Computation (Thomson, 2nd edn. 2006) is a standard and very well regarded text. It aims to be very accessible and to take its time giving clear explanations of key concepts and proof ideas. I think it is successful. The last third of the book is on computational complexity.
  • Ofed Goldreich, P, NP, and NP-Completeness (CUP, 2010). Short, clear, and introductory stand-alone treatment of computational complexity.
  • Ashley Montanaro, Computational Complexity, notes for a 2012 lecture course here in Cambridge. This has a useful quick guide to further reading, so I don’t need to add anything further here.

And that’s surely more than enough! But any suggestions for additions? deletions? improvements? 

Scroll to Top