2012 - Page 6 of 7 - Logic Matters

The next step after IFL?

Logic, This and that / 4 Comments / February 18, 2012 February 26, 2012

I have added a page of suggestions of what to read after my intro. logic book. I’d be particularly interested to hear comments, take suggestions, etc. And it isn’t just a question of putting a favourite sequence of books in front of people for them to battle through, so that they can eventually jump examination hoops. There is also the matter of inducing a certain amount of that elusive desired quality we call ‘mathematical maturity’. How do we best help bring that about?

If you couldn’t get to the Vermeer exhibition

This and that / Leave a Comment / February 16, 2012 February 16, 2012

If you couldn’t get to the Fitzwilliam Museum’s astonishing small exhibition
‘Vermeer’s Women: Secrets and Silence’ (or you went once the word got around, and it all became rather uncomfortably packed), then this is just to say that the book-of-the-exhibition is unusually good. It is beautifully produced, as so often with such catalogues, the introductory essays are genuinely illuminating (and reproduce many more pictures than were being shown in Cambridge), and it is pretty inexpensive as these things go. It was a great pleasure to see the real paintings, of course — especially on our first visit, before the crowds discovered the exhibition. But quietly reading and re-reading this book is also wonderful. Warmly recommended. The first, long, customer review on Amazon.com is spot on.

“Drop the Health Bill”

This and that / 2 Comments / February 14, 2012 February 14, 2012

Most of us in the UK care deeply about the future of the NHS. We know there are all kinds of problems — and some of them are inevitable, with medical possibilities ever-expanding, an ageing population, and finite resources. But many voices I trust say, very loudly, that the current Lansley health bill is not the way to tackle them. So I’ve signed the Drop the Health Bill petition (along with over 100K other people): I hope you will too if you are a British citizen or UK resident. Here’s a persuasive BMJ blogpost by the petition’s originator.

Spread the word, for indeed numbers here can matter.

The Pacifica Quartet play Shostakovich

Music / 1 Comment / February 10, 2012 February 10, 2012

Recent posts here have been a bit sternly logical. Well, this one isn’t exactly light relief, but at least it isn’t yet more on Gödel.

A tweet in response to one of mine (about my favourite quartets performing at the moment) warmly recommended the Pacifica Quartet, new to me. And the first instalment of their Shostakovich cycle released last September has got a lot of praise from the critics (“stunning”, “electrifying”, “one of the top 10 classical recordings of 2011”, etc.). So I sent off for the remarkably cheap double CD. Now I’m bowled over too. Amazing playing. This first release includes the eighth quartet (the most familiar? the most performed?) and this is surely the best performance I’ve ever heard. Very warmly recommended indeed. I’m not sure I can add “Enjoy!” as these are emotionally wrenching pieces: but yes, electrifying.

Two footnotes. The Pacifica are playing Shostakovich for three evenings at the Wigmore Hall in March (some tickets still available). And there’s a very illuminating website about the Shostakovich quartets here.

What to read before, after, or instead of IGT

Gödel's theorems / 2 Comments / February 8, 2012 February 10, 2012

I’m sometimes asked for recommendations about what to read after IGT – or indeed, what to read instead of tackling IGT if you are looking for something less weighty, or for something more like a conventional mathematical text. So here are some suggestions, for different kinds of audiences.

Gödel’s First Theorem, continuing the story

Gödel's theorems / Leave a Comment / February 6, 2012 February 6, 2012

I’ve a book review to finish, reading for a seminar to get under my belt, and other time consuming stuff waiting. So I’m going to have put aside for a week or more the continuing self-imposed task of writing notes on the expository tradition on the first theorem. But the promised Part 2 has now been been added (and some improvements made to the previous Part — in particular, I’ve improved the treatment of Kleene 1943). The immediately next task is to backtrack and add an earlier section on the obviously missing element of Part 1, namely a discussion of the last chapter of Quine’s Mathematical Logic (1940/1951). Then it is on to the long march through a stack of post-Kleene textbooks and other discussions of Gödel.

Well, I’m (re)learning quite a bit, and I hope this will show up in various little ways in the second edition of my own book. Meanwhile, for anyone else interested, here’s the current version of the notes (a mere 33 pages).

Gödel’s First Theorem, from Gödel 1931 to Kleene 1943

Gödel's theorems / 7 Comments / January 24, 2012 January 24, 2012

As ‘homework’, before writing more of the second edition of my Gödel book, I’m reading through the literature to see how others have handled the First Incompleteness Theorem, both in the early papers from Gödel on, and then in the later textbook tradition. How do is the Theorem stated? How is it proved?

I’ve started writing notes on the expository history, and here’s the first (19 page) instalment. The notes don’t at all aim to be comprehensive, though I’d like to know about significant omissions as I go along. They have been written, as much as anything, as a rather detailed aide-memoire for myself (and a source of bits and pieces I might use). I have done some joining up of the dots to make them tolerably readable, but I certainly haven’t put in the time to spell out everything out in the way a beginning student might want. Still, you shouldn’t need much background to follow the twists and turns.

The notes come in three parts. Part 1 looks at early papers by the Founding Fathers. Part 2, to follow, will look at three pivotal works, Mostowki’s Sentences Undecidable in Formalized Arithmetic and Kleene’s Introduction to Metamathematics (both from 1952), and then Tarski, Mostowski and Robinson’s Undecidable Theories (1953). Part III will continue the story on through some sixty years of textbooks.

Make what use of these notes that you will. Though the usual warning applies in spades, as I’m no historian: caveat lector! Remember how very easy it to LaTeX your work. Just because what you write then looks very pretty doesn’t mean that it is any more authoritative …

Carnap and the Diagonalization Lemma (Continued)

Gödel's theorems / 14 Comments / January 9, 2012 February 24, 2012

[mathjax]Let’s distinguish what I’ll call the Diagonalization Equivalence from the familiar Diagonalization Lemma. The former is a semantic claim: in the right conditions, for any one-place predicate $F(x)$ of theory T there is a corresponding sentence $G$ such that $G$ is true if and only if $F(\overline{\ulcorner G \urcorner})$ is true. The latter is a syntactic claim: in the right conditions, for any one-place predicate $F(x)$ of theory T there is a corresponding sentence $G$ such that $T \vdash G \leftrightarrow F(\overline{\ulcorner G \urcorner})$ .

In the previous post, I claimed that in his §35 Carnap proves the semantic Diagonalization Equivalence, which he uses in §36 to prove the semantic version of Gödel’s First Theorem. But I said he doesn’t prove the Lemma there or give the now canonical syntactic version of the Theorem (the one depending on the syntactic assumption of $\omega$ -consistency).

Well, no one has protested yet. So, thus emboldened, let me now stick my neck out further!

What happens later in the book? Carnap’s notation and terminology together don’t make for an easy read. But as far as I can see, when he returns to Gödelian matters later, he still is using the semantic Diagonalization Equivalence and not the syntactic Diagonalization Lemma. If the latter was going to appear anywhere, you’d expect to find it in §60 when Carnap returns to the incompleteness of arithmetics: but it isn’t there. (An indication: Carnap here talks of provability being ‘definable’ in arithmetics, and it is indeed expressible — but we know it isn’t capturable/representable by a trivial argument from the Diagonalization Lemma proper. So Carnap hereabouts is still dealing with semantic expressibility, and doesn’t seem to invoke the syntactic notion of capturing/representing needed for the Lemma.)

So, in summary: Yes, Carnap gives a nice tweak to the argument in §1 of Gödel 1931 for the semantic incompleteness theorem, by generalizing the basic idea to give the Diagonalization Equivalence. But this isn’t the modern Diagonalization Lemma. Which isn’t to say that we can’t get the Lemma easily using the wff Carnap constructs: however, as far as I can see, Carnap didn’t explicitly take the step in 1934, even though he is often credited with it.

What am I missing?

Carnap and the Diagonalization Lemma

Gödel's theorems / 1 Comment / January 6, 2012 January 24, 2012

Carnap is often credited with proving the Diagonalization Lemma in Logische Syntax der Sprache. But where does he do it?

Well, in §35 Carnap notes the general recipe for taking a one-place predicate $F(x)$ and constructing a sentence $G$ such that $G$ is true if and only if $F(\overline{\ulcorner G \urcorner})$ is true, where as usual $\overline{\ulcorner G \urcorner}$ is the formal numeral for the Gödel number for $G$ .

Fine. But that claim about constructing a semantic equivalence isn’t the Diagonalization Lemma as normally understood, which is a syntactic thesis, not about truth-value equivalence but about provability. It is the claim that, in the setting of the right kind of theory $T$ , then for any one-place predicate $F(x)$ we can construct a sentence $G$ such that $T \vdash G \leftrightarrow F(\overline{\ulcorner G \urcorner})$ . And Carnap doesn’t prove that in §35.

When we turn to §36, where Carnap proves the incompleteness of his system II, again he appeals to his semantic result not the syntactic Diagonalization Lemma. We now take the relevant predicate to be NOT-PROVABLE: so we get a sentence $G$ which is true if and only if it isn’t provable. And then Carnap appeals to the soundness of his system II to argue in the elementary way that $G$ isn’t provable. So at this point Carnap is giving a version of the semantic incompleteness argument sketched in the opening section of Gödel 1931 (the one that appeals to a soundness assumption), and not a version of Gödel’s official syntactic incompleteness argument which appeals to $\omega$ -consistency. Indeed, Carnap doesn’t even mention $\omega$ -consistency in the context of his §36 incompleteness proof. He doesn’t need to.

To summarize so far: in §§35–36, Carnap doesn’t use the theorem that his system II proves $G\ \leftrightarrow\$ NOT-PROVABLE $(\overline{\ulcorner G \urcorner})$ , i.e. he doesn’t appeal to an application of the Diagonalization Lemma in the modern sense. He doesn’t need it (yet), and he doesn’t prove it (here).

But maybe he returns to the fray later in the book … the story continues!

Amethe von Zeppelin (continued)

This and that / Leave a Comment / January 6, 2012 January 6, 2012

A generous correspondent (much better at this Googling malarkey than I) writes: “Amethe Smeaton was the daughter of a colonial administrator (later a liberal MP) called Donald Smeaton. She was born in the late 1890s and was at Girton College during WW1 but left without graduating because of ill health. She corresponded briefly with Russell about Principia in 1917. She married a Scottish army officer called Ian McEwan in 1919: they had a son who served in the Scots Guards and who was killed in WW2. In 1924 she published in the Morning Post an adulatory account of an interview she had with Mussolini (apparently she spent time in Italy as a child and therefore spoke Italian.) Graf von Zeppelin was cited as co-respondent in her divorce in 1929: it was said that they had been “found living as Count and Countess von Zeppelin” at Mentone. She married the count in Cap Martin, France in August that year. (He had been a German army officer during WW1, then had travelled in the forests of Bolivia, publishing an account of his adventures in 1926. According to A J Ayer, he chased Otto Neurath through the streets of Munich with a revolver at one point.) They bought a house called Schloss Mauerbach near Vienna in 1939. I think she died around 1966.”

And I’ve thought to look in the Carnap-Quine Correspondence. It seems that the translation wasn’t entirely a happy experience for Carnap. The translation was organized by Ogden as editor of The International Library, went slowly, and Quine had suggested a very appropriate Harvard academic who was keen to do the job but Ogden would not make the change. And Carnap then writes ‘Ogden sent me Ch.I and II of [the translation]. I had to spend much work in revising and correcting them; I found a lot of mistakes, misunderstandings and unsuitable expressions.’ But perhaps the experience got better after that, as Carnap doesn’t return to make later complaints.