Gödel’s theorems

G

GWT2 — a third instalment

I was prompted to start working on a second edition of Gödel Without (Too Many) Tears by discovering that there was a significant muddle in Chapter 5 (I had inconsistently wavered between taking Baby Arithmetic, so called, as having just a negation connective, and having other connectives too). Thanks again to Ben Selfridge for pointing out that embarrassing glitch.

This new instalment of GWT2 corrects that unfortunate mess, and makes a number of other small improvements for clarity/readability, in what is now numbered as Chapter 6. So here it is!

To save readers having to dart between different PDFs, I have included the revised versions of the Preface and earlier chapters (with only trivial changes from the previous posting).

Need I say it? No: but I still will! Corrections and friendly suggestions are immensely welcome at this stage.

Already updated with many thanks to David Furcy and Léon Probst. (You may need to force your browser to reload the file to get the version dated 18 July.)

GWT2 — a first instalment

I’ve decided to get to work, putting together a revised version of Gödel Without Too Many Tears. 

I’ll obviously correct the known glitches in the first edition. But as I start to read through the opening chapters, I find myself wanting to make quite a lot of little stylistic improvements. And there will be a couple of more significant changes, I think, later in book. So this will be, while not a radically different version, still rather more than a lightly corrected reprint. So we’ll count  it as a second edition, GWT2.

I’ll post revised chapters here in bite-sized instalments, from time to time over the next few weeks. As always, corrections and friendly suggestions are immensely welcome at this stage: now is the time to let me know if you had issues with the first edition.

Here then are the first fourteen pages, based on the old Chapters 1 and 2, now three chapters. Enjoy!

Added 9 July: With many thanks to David Furcy, I’ve already uploaded a corrected version, repairing about ten(!) minor typos.

Juliette Kennedy, Gödel’s Incompleteness Theorems

I was in the CUP Bookshop the other day, and saw physical copies of the Elements series for the first time. I have to say that the books are suprisingly poorly produced, and very expensive for what they are. I suspect that the Elements are primarily designed for online reading; and I certainly won’t be buying physical copies.

I’ve now read Juliette Kennedy’s contribution on Gödel’s Incompleteness Theorems. Who knows who the reader is supposed to be? It is apparently someone who needs the notion of a primitive recursive function explained on p. 11, while on p. 24 we get a hard-core forcing argument to prove that “There is no Borel function F(s) from infinite sequences of reals to reals such that if ran(s) = ran(s’), then F(s) = F(s’), and moreover F(s) is always outside ran(s)” (‘ran’ isn’t explained). This is just bizarre. What were the editors of this particular series thinking?

Whatever the author’s strengths, they don’t include the knack of attractive exposition. So I can’t recommend this for reading as a book. But if you already know your way around the Gödelian themes, you could perhaps treat this Element as an occasionally useful scrapbook to dip into, to follow up various references (indeed, some new to me). And I’ll leave it at that.

Big Red Logic Book, no. 1 — a year on

It is exactly a year ago that the self-published version of An Introduction to Gödel’s Theorems was published as a paperback. It has sold over seven hundred copies in that time, and the monthly trend is slowly upwards. That’s three times as many copies as the CUP paperback was selling. But then, this print-on-demand version is a third of the cost! Even so, the sales figure strikes me as surprisingly high, given that the PDF has also been freely available at the same time as the new paperback. I guess it shows that quite a few people, like me, do prefer to work from a physical book, if one is available at a modest price. As far as downloads go, AWStats currently reports about five hundred a month — though who knows exactly what these (rather volatile) download stats really mean. Still, I count do that as overall a happy success!

Who knows if I will ever get round to a third edition. There’s tidying to be done, and I’d quite like to add a bit more around and about the Second Theorem. It would be fun to catch up with some reading and re-reading and re-thinking. But I don’t cringe when I occasionally have occasion to glance at the book: so I’m not yet feeling an urgent push to getting back to revising it right now.

Big Red Logic Books: now available in Australia!

Short version: paperbacks of An Introduction to Gödel’s Theorems,  An Introduction to Formal Logic, and Gödel Without (Too Many) Tears are now available from Amazon in Australia.

Slightly longer version: An Australian version of Amazon’s KDP print-on-demand service has been up and running since the beginning of the year. Initially, however, it couldn’t handle books in the format of the Big Red Logic Books. But (though they haven’t told authors!) I have just discovered in the last hour that the books are now available locally. The prices are set to the minimum possible (the fixed printing and distribution charges are higher in Oz, but I’ve set the royalties to zero to compensate).

So please spread the word Down Under. The books have been available as PDF downloads for a year, but there are quite a few who much prefer to work from printed books. And do tell local librarians (you might need to do a bit of explaining/cajoling too, as librarians tend to hold their professional noses over self-published books, and don’t approve of Amazon either! — but other publication routes would have been much more expensive).

I’d be interested to hear how the physical copies turn out  (the UK printed ones are really surprisingly good, apart from slightly flimsy covers, given the price point).

New look, new hardback

The three Big Red Logic Books have a new look. I’m staying with the red theme, but no longer using the free Amazon KDP online cover-builder which produced their rather muddy colour and muddy swirls. The outsides, then, are a bit less dull. I’m afraid the insides of the paperbacks stay just the same!

More importantly, perhaps, a hardback of Gödel Without (Too Many) Tears is published today. It is currently available from e.g. Barnes and Noble (in the US), Gardners (the UK library book suppliers), Booktopia (in Oz), as well as the local Amazons. I hope it will soon propagate to other sellers like Blackwells. It won’t just appear on bookshop shelves, however: you’ll have to order it.

I’m not really expecting anyone reading this blog to buy it for themselves! However, you might like to recommend the hardback to your local friendly university or college librarian. Some librarians are pretty resistant to buying from Amazon (especially self-published paperbacks). That’s why I’m experimenting with hardback publication. We are going a step up here, using the same print-on-demand providers now used e.g. by CUP for some of their books, with a “proper” ISBN officially assigned to the Logic Matters imprint. It is still pretty cheap as academic hardbacks go — £14 in the UK and comparable prices elsewhere (so this isn’t going to make my fortune: to be honest, I’ll be pretty surprised if I even recoup the set-up costs.)

Of course the PDF version is still freely available, and I’ve kept the paperback version as Amazon-only as that absolutely minimizes the price to students. But I like to think that the book should be available on the shelves in university libraries, so please take a moment to recommend the hardback! Its ISBN is 978-1916906303. 

(Apologies by the way to readers down under that the paperback is still not locally printed and hence not cheaply available to you: Amazon say they are working on being able to produce paperbacks in the relevant format “soon” …)

Update: At the moment Amazon UK are giving a very long delivery date for the hardback, but I hope that’s temporary. Amazon US by contrast are giving a relatively short delivery date.

A few thoughts about self-publishing

A very enjoyable walk down to my favourite library, the Moore library, in the winter sun. But not, sadly, to then read and write, and think, and idly look out of the windows, and take a coffee break, and write again. It will be a good while yet before all that is possible. I was just donating, via their dropbox, copies of IFL2 and GWT.

Time for an update, perhaps. How have things gone since I got the copyright back from CUP, and have been able to give away IFL2 and IGT2 as freely downloadable PDFs? I’ve just checked: since late August, IFL2 has been downloaded over 3.6K times. And after a quite crazy initial flood (when someone posted a direct link at Hacker News, without saying that the link was to a full book!), IGT2  has been downloaded another 4K times. The two books have sold well over 200 each of the inexpensive print-on-demand versions. (It is very early days for GWT … I’ll report back on that in the New Year.)

I didn’t at all know what to expect. Or rather, I was expecting something like that ratio of freely downloaded PDFs to bought copies: but I had little idea how many would be tempted by the books overall. I guess I am pretty pleased.

And it certainly seems to have been worth the small effort of making the print-on-demand versions available. I did ask online, and got enough responses to suggest that there is a significant minority of readers who significantly prefer to work from “real” books as opposed to onscreen PDFs (which is one reason that libraries should have hard copies available); and some of that minority said that they are prepared to pay a modest amount to get the hard copy too. And so it has turned out.

By the way, as I’ve remarked before, I wasn’t thrilled to bits to be using the Amazon-provided service. But for this kind of enterprise, it does seem the best and easiest option on various counts. And since sales are small, and I’ve only rounded up the price from the minimum possible by pence (in order to cover costs of getting proof copies, sending copies to copyright libraries etc.), you are at least not adding much to Amazon’s grossly undertaxed profits by buying a copy.

In some respects, then, isn’t this an ideal way of publishing book-length projects? Provide freely downloadable PDFs; and make as-inexpensive-as-possible print-on-demand copies available.

Well yes, but only up to a point. It works if you e.g. already have a book or two to your name and you don’t particularly need the imprimatur of a respected academic press for people to think that your book might be worth taking seriously. And if you don’t need that imprimatur for promotion purposes either. And  if you can find enough friends and acquaintances to give honest critical feedback at key writing stages (eventually doing the work of a publisher’s readers). And if you know your way around a document processing package like LaTeX well enough, and have a good enough design eye, to produce pages which look professional.  And if you can find enough other friends and acquaintances who will happily check for typos and thinkos (doing the work of a publisher’s proof-reader). And if you have enough internet presence via a blog or whatever to get the word out there beyond the small circle of those friends and acquaintances!

That’s quite a few rather big “if”s.

So traditional publishers do still have a role to play. Or at least some of them. Mind you, we can all think of publishers like Spr*ng*r where the quality control is minimal, and unheralded books (published at ludicrous prices) fall stone dead from the press. However, you can these days publish with an academic publisher and negotiate to be allowed to keep a PDF freely downloadable (some even put e.g. chapter-by-chapter PDFs open access on their website). CUP, OUP and MIT seem to allow this sort of thing sporadically, though I’m not sure what the principles of choice are. And then there is e.g. the very promising new BSPS Open initiative: the plan is to publish open access monographs under the supervision of an editorial board to maintain quality. It will be interesting to see how initiatives like that develop over the coming few years: for surely, with the gross pressure of costs on libraries (let alone the impoverishment of young academics) the days of publication solely by the £80 monograph must be numbered …

Meanwhile, if it can work for you, I can recommend the self-publishing route!

Kripke on diagonalization

Having thought a bit more about Kripke’s short note on diagonalization, linked in the last post, it seems to me that the situation is this, in rough headline terms.

How do we get from a Diagonalization Lemma to the incompleteness theorem? The usual route takes two steps

(1) The Lemma tells us that for the right kind of theory T, there is a fixed point G in T for the negation of T‘s provability predicate.

(2) We then invoke Theorem X:  if G is a fixed point for the negation of the provability predicate Prov for T, then (i) if T is consistent, it can’t prove G, and (ii) if T is omega-consistent, it can’t prove not-G.

The usual proof for the Diagonalization Lemma invoked in (1) is, as Kripke says, (not hard but) a little bit indirect and tricksy. So Kripke offers us a variant Lemma which has the form: for the right kind of the theory T, there is a fixed point in TK for any T-predicate where TK is T augmented with lots of constants and axioms involving them. The axioms are chosen to make the variant Lemma trivial. But now the application of Theorem X becomes more delicate. We get a fixed point for the negation of TK‘s provability predicate and apply Theorem X to get an incompleteness in TK. And we then have to bring that back to T by massaging away the constants. Not difficult, of course, but equally not very ‘direct’.

So you either go old-school, prove the original Diagonalization Lemma for T in its tricksy way, and directly apply Theorem X. Or you go for Kripke’s variant which more directly uses wffs which are ‘about’ themselves, but have to indirectly use Theorem X, going via TK, to get incompletness for the theory T we start off from. You pays your money and you takes your choice.

For a worked out version of these headline remarks see the last section of the revised draft Diagonalization Lemma chapter for Gödel Without Tears. Have I got this right?

Gödel Without Tears, not quite the end

I was intending to post Chapter 17 today — the final chapter, dealing with Löb’s Theorem and related results. But looking again at my draft version yesterday, I thought it was/is rather a mess, and that some of the material is even in the wrong chapter. So some not-quite-trivial rewriting is needed. It will be a day or two before I can get down to doing that.

Meanwhile, many thanks to all those (some here, more by email) who have sent corrections and comments and suggestions about earlier chapters. I’ll try to get a revised version of the whole thing, plus suggestions for further reading, and an index, done by the middle of next month. And then delight the world with another Big Red Logic Book …

Gödel Without Tears, slowly, 16

Today’s chapter is optimistically entitled ‘Proving the Second Incompleteness Theorem’. Of course we don’t actually do that! But we do say something more about what it takes to prove it (stating the so-called derivability conditions, and saying what it takes to prove them).

As an extra, we say how it can be that there are consistent theories which ‘prove’ their own inconsistency.

[Link now removed]

Scroll to Top