Peter Smith's Blog, page 52

Gödel Without Tears, slowly, 10

A good time to join the party, if you haven’t yet been following along with this chapter-by-chapter posting of a new version of Gödel Without (Too Many) Tears.

Along with revised versions of early chapters (thanks to all those who sent comments and corrections, a few here, and more by e-mail), here is Chapter 10, on ‘The Arithmetization of Syntax’. So this is where we get to today:And then, over the next four chapters, we (at last) get to prove the first incompleteness theorem, in pretty much Gödel’s way. We also introduce the Diagonalization Lemma, prove Rosser’s Theorem and Tarski’s Theorem. A busy but fun week!

The post Gödel Without Tears, slowly, 10 appeared first on Logic Matters.

From a small corner of Cambridge, 11

Sunday morning. Trinity Street almost deserted. Not so long ago, there would have been quite a few people around by this time. But now, walking in to the Sunday Market as we have started doing again, the city centre is very quiet. There are little queues for the market food stalls; but evidently people are still coming into town much less. And of course the usual hordes of tourists have quite vanished, while most of the students aren’t back yet. The out-of-term Cambridge of fifty years ago has re-appeared. Strange, but it has its attractions.

Who knows what the coming weeks will bring? Students returning, a marked upswing in local Covid cases, increased reluctance again of older residents to venture out? Perhaps our reluctance is overdone. But levels of trust that the government is giving wise guidance are, shall we say, low; it is pretty difficult to interpret the various statistics for ourselves; so our generation’s erring on the side of excess caution is natural enough. Things are not looking hopeful.

We will try to enjoy the relative safety while we can.

So the days rattle by. While more confined to home and garden, various grands projets are underway. Encouraged by Youtube how-to videos (how did we manage before?), new skills are being acquired. Next up, getting handier with a silicone caulk gun …

Having so little to report, Zoom calls with friends are full of similar trivial domestic detail. Comforting in its way, though.

No concerts, then, and no trips to the London galleries and museums. But the wonderful Wigmore Hall series of free online concerts starts tonight; and as soon as the weather turns more autumnal again, we must book timed tickets to the Fitzwilliam. And as for reading … Having so very much enjoyed recently revisiting Wolf Hall and Bring Up the Bodies, I’m launched into the last part of Hilary Mantel’s trilogy, The Mirror and the Light. Best, I think, to treat this massive volume as itself another three books (and anyway, I don’t want to finish it too quickly). So having read the first two parts of the new book, I’m pausing — and re-reading with great enjoyment Kate Atkinson’s Case Histories. That’s the first of her Jackson Brodie novels, which are both wonderfully well written and also gripping detective stories. What’s not to like? If you don’t know the series, very warmly recommended for when you need distracting but not mindless reading!

The post From a small corner of Cambridge, 11 appeared first on Logic Matters.

Gödel Without Tears, slowly, 9

Today’s chapter is about ‘Expressing and capturing the primitive recursive functions’. We prove (in reasonable detail) that although the language of basic arithmetic only has the successor, addition and multiplication functions built in, we can in fact form a wff to express any primitive recursive function we pick. And then we prove (or rather, wave our arms at a proof) that even the weak Robinson Arithmetic can reprsent or ‘capture’ every primitive recursive function.

Even cutting lots of corners, this chapter is inevitably a bit fiddly. But one nice idea we meet is the use of a coding device for handling finite sequences of numbers. I try to make clear (a) how having such a device will enable us to express/capture primitive recursive functions, while (b) distinguishing the neat general coding idea from Gödel’s particular implementation of the device using his beta function.

The post Gödel Without Tears, slowly, 9 appeared first on Logic Matters.

Gödel Without Tears, slowly, 8

I’ll be briefer than usual, though today’s attached episode is longer than usual. After a short Interlude (where we’ve been, where we are going), there’s a quite substantial chapter ‘Primitive Recursive Functions’.  And there’s a nice diagonal argument to enjoy!

The post Gödel Without Tears, slowly, 8 appeared first on Logic Matters.

Gödel Without Tears, slowly, 7

Next, we have the shortest chapter so far, on Quantifier Complexity, which introduces the notions of and wffs.

But there is an intriguing little result in this chapter. If the consistent theory T which includes Robinson Arithmetic Q proves a given sentence, that sentence must be true. You don’t have to believe the theory T is true to accept its consequences are true. For example, suppose T is the wildly infinitary apparatus that Wiles uses to prove Fermat’s Last Theorem, which is equivalent to a sentence. Then you don’t have to believe that infinitary apparatus is actually correct (whatever exactly that means); all you need to believe to accept Fermat’s Last Theorem (assuming Wiles’s corrected derivation from T is correctly done) is that T  is consistent. I still find that rather remarkable.

The post Gödel Without Tears, slowly, 7 appeared first on Logic Matters.

Gödel Without Tears, slowly, 6

We get back to proving the First Incompleteness Theorem next week. In this week’s five chapters, we are reading into the record some necessary arithmetical background.

Everything in today’s chapter will very probably be quite familiar; but we do need to say just a little in GWT (a very little) about  ‘First-order Peano Arithmetic’, the benchmark formalized theory of arithmetic.  The most interesting claims (for a student who has not met them before, unlikely for a reader of this blog!) are those in the final section about non-standard models — but that brisk section is optional!

The post Gödel Without Tears, slowly, 6 appeared first on Logic Matters.

Gödel Without Tears, slowly, 5

Where have we got to in this slow introduction to the incompleteness theorems? Theorem  8 from Chapter 4 tells us that if a consistent, effectively axiomatized, theory is “sufficiently strong”, then it must be negation incomplete. And we announced that even the very weak arithmetic called Robinson Arithmetic is sufficiently strong (in which case, stronger consistent, effectively axiomatized, theories must also meet the condition, and so must be incomplete). But we didn’t say anything at all about what this weak theory of arithmetic looks like! Today’s Chapter 5 explains.

So here are revised versions of Chapters 1 to 4 together with the new Chapter 5 on ‘Two weak arithmetics’. (Many thanks to those who have commented on the earlier chapters here or by email: there are quite a few small improvements as a result.)

The post Gödel Without Tears, slowly, 5 appeared first on Logic Matters.

Two big red logic books, again

When I saw the proof copies of the Amazon cheap print-on-demand versions of IFL2 and IGT2, I changed the layout a bit, increased the width of the ‘gutter’ so that a two-page opening worked better with the binding. I’ve just got author copies of the now published versions, and I must say that things have worked out excellently. The quality of the printing and paper is very good (if anything I prefer these copies to the original CUP printings); and the cover is simple but OK. One happy purchaser, when his order arrived, emailed “amazing”. I’m not quite sure I’d go as far as that; but at the price, the books really are pretty well produced,  certainly to a higher standard than I was originally expecting. Buy with confidence, as they say.

Since these new versions are not coming from a publisher with a marketing department, your university librarian will not get to know about it them the usual way. You will therefore need to give them the details and ask them to order a printed copy for the library (details below). Please do take a moment do this: the books are more or less at cost, peanuts for a library, so I don’t have a financial incentive in asking this. It is just that many students prefer working from a physical book, and a few have real problems with prolonged onscreen reading. 

It will be back to Gödel Without Tears on Monday. Meanwhile, many thanks to the handful who have posted comments here, and to the larger number of kind e-mailers. Corrected and slightly revised versions of the first four chapters will be posted together with the first of next week’s tranche of chapters. I’m finding it quite fun to revisit this material. (But in lockdown life, it perhaps doesn’t take so much to amuse!)

Info for librarians (and for you, if you’ve been meaning to order and need a nudge!):

Peter Smith, An Introduction to Formal Logic (2nd edition, originally published by CUP 2020; now available as Amazon print on demand).

ISBN-13 : 979-8675803941
ASIN : B08GB4BDPG

Peter Smith, An Introduction to Gödel’s Theorems (2nd edition, originally published by CUP 2013; corrected version now available as Amazon print on demand).

ISBN-13 : 979-8673862131
ASIN : B08GB4L9JT

The post Two big red logic books, again appeared first on Logic Matters.

Gödel Without Tears, slowly, 4

The previous chapter gestured towards a proof of incompleteness which relies on constructing a Gödel sentence which is true if and only if it is unprovable. This proof idea is ingenious. Too ingenious? Some, when they first encounter it, worry that an illegitimate trick is being played.

That’s wrong, as hopefully will become quite clear in later chapters. It might help, though, to counter any temptation to think that there’s something fishy about the incompleteness theorem if we pause to look at a different sort of proof — one that doesn’t depend on the construction of a tricksy Gödel sentence.

Chapter 4, ‘Undecidability and incompleteness’, therefore gives a lovely proof which I first learnt from Timothy Smiley a very long time ago. The argument is one of my favourite ones in all logic — it’s so elegant and easy to understand that every student should know it!

The post Gödel Without Tears, slowly, 4 appeared first on Logic Matters.

Gödel Without Tears, slowly, 3

This short chapter, ‘Outlining a Gödelian Proof’ gives a first indication of the way that we are going to prove  (the semantic version of) the first incompleteness theorem by constructing a Gödel sentence which is true if and only if unprovable. The detailed construction has to wait until a later chapter; but we do meet the key idea of the arithmetization of syntax.

The post Gödel Without Tears, slowly, 3 appeared first on Logic Matters.