Peter Smith's Blog, page 52

Gödel Without Tears, slowly, 15

[I’ve retitled the previous post, to keep blog post numbers in sync with chapter numbers!]

We at last move on to the Second Theorem. In Chapter 15, we introduce the theorem, and explain its significance for Hilbert’s programme. This involves a  cartoon history trying to bring out the attractions of Hilbert’s programme (surely one of the great ideas in the philosophy of maths — if only it had worked!).

 

 

 

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

Gödel Without Tears, slowly, Interlude

Today’s short episode is a second ‘Interlude’, separating the chapters on the first incompleteness theorem from the final three chapters on the second theorem. But it mentions (or at least, gestures at) enough interesting points for it to be worth its own post.

[There a reference to a Theorem 51, which is the previously unnumbered result — now indeed to be recognized as a theorem in its own right — at the end of §13.3. which says that if a theory T is p.r. axiomatized and contains Q, the formal predicate ProvT does not capture the property of being a T-theorem.]

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

Gödel Without Tears, slowly, 15

Today’s short episode is a second ‘Interlude’, separating the chapters on the first incompleteness theorem from the final three chapters on the second theorem. But it mentions (or at least, gestures at) enough interesting points for it to be worth its own post.

[There a reference to a Theorem 51, which is the previously unnumbered result — now indeed to be recognized as a theorem in its own right — at the end of §13.3. which says that if a theory T is p.r. axiomatized and contains Q, the formal predicate ProvT does not capture the property of being a T-theorem.]

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

Lea Desandre sings Monteverdi and more …

Twenty minutes of delight and balm for the soul: Lea Desandre singing with Thomas Dunford and members of Les Arts Florissants.

The post Lea Desandre sings Monteverdi and more … appeared first on Logic Matters.

Gödel Without Tears, slowly, 14

In this last (and short!) chapter related to the first incompleteness theorem, we meet ‘Tarski’s Theorem’. And so we arrive at what might be thought of as the Master Argument for incompleteness — for appropriate theories, provability-in-T  is expressible in T but truth isn’t, so provability isn’t truth.

Onwards to the second theorem next week!

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

Gödel Without Tears, slowly, 13

We get today to Chapter 13, called ‘The Diagonalization Lemma, and Rosser’s Theorem’. Not that we actually prove Rosser’s theorem in detail, as this is fiddly. But I do establish the Lemma, show how it can be used to derive the syntactic version of the first theorem again, and I indicate the key construction for getting to Rosser’s theorem.

(Looking back at Chapter 12, though, I see that the section which actually proves the first theorem there had become rather oddly arranged: I’ve rearranged a bit, separating out the theorem from a couple of corollaries worth remarking. So I’ve included a revised Chapter 12 too.)

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

Gödel Without Tears, slowly, 12

And, at last ….

Cue drumroll …

‘The First Incompleteness Theorem, syntactic version’

This is the version of the theorem that Gödel highlights in his epochal 1931 paper, and which people usually have in mind when they talk of ‘the’ incompleteness theorem. We have to do a little  more work than for the semantic version, but again — once we have grasped the trick of constructing a Gödel sentence, and understood the idea of capturing/representing/defining primitive recursive relations in a formal theory, the proof is delightfully simple. Which is not to diminish  Gödel’s achievement in the slightest: on the contrary, it was very important to him that the ideas involved are straightforward to handle once you grasp them.

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

Gödel Without Tears, slowly, 11

And at last, we get to a proof of ‘The First Incompleteness Theorem, semantic version’, uisng pretty much Gödel’s materials. And given our background work over previous chapters, it is very easy. Grasp the trick in constructing the described Gödel sentence, and everything then falls speedily and simply into place. Enjoy!

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

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.