Peter Smith's Blog, page 53

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.

Gödel Without Tears, slowly, 2

This very short second chapter ‘The First Theorem, two versions’ makes a key distinction between the semantic and syntactic flavours of the incompleteness theorem. That distinction is already there in Gödel 1931; but if I recall rightly, it was Andrzej Mostowski in his short book twenty-one years later who first brings it out really clearly and explicitly. The chapter also makes another key point: we should really talk, not of an incompleteness theorem (after all, mere incompleteness in itself might be boringly repairable) but of an incompletability theorem.

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

Gödel Without Tears, slowly, 1

Looking at my lecture notes Gödel Without (Too Many) Tears, they now seem rather patchy. They could certainly be clearer in a number of places, and could be better arranged too. Since they are downloaded two thousand times a year or so — and people have said that they find them useful — it seems worth making the effort to revisit the notes and improve them where I can.

So here is the first installment of a revised version, the brief Preface, and Chapter 1 on Incompleteness, the Very Idea. There are now eighteen short chapters (some very short), and I’ll be posting them at the rate of a chapter a day, starting now (with weekends off, and a composite update on the next three Mondays). You can either read along slowly, or join the party later.

I have tried to keep the notes, as before, at under a third the length of IGT2. So you get some headline news without too much (distracting?) extra detail. Comments and corrections are most welcome, indeed encouraged — except from Gödel cranks! In particular, don’t hesitate to let me know about typos. I will try to respond to comments and queries day by day (depending how few/many there are).

You can comment by replying to the blog post for the relevant chapter. Three points about using the comments system:

If the system does not recognize your email address as a real one and that of someone who has had comments approved before, your comment will be held in a moderation queue (for obvious enough reasons!).
If your comment is approved, your email address won’t be published, however. (Comments which use offensive names won’t be published even if the comment is a sensible one. Yes, people are that silly!)
If your comment is more than a sentence or two long, it is probably worth editing it off-line and checking it before copying, pasting, and posting (notionally you have a few minutes to edit, but this doesn’t work for everyone).

Alternatively, you can mail peter underscore smith at logicmatters dot net.

[Added: I’ve already corrected Chap 1 to remove some typos — thanks to David Furcy!]

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