jump to navigation

Gödel’s Incompleteness Theorems January 23, 2009

Posted by Greg in Mathematics, Philosophy of mind.
trackback

Blah balha
–Evelyn Brister

I’d like to hit two main points in this blog post. First of all, I’d like to discuss Gödel‘s second incompleteness theorem a bit; second, I’d like to see if I can start an actual argument about the philosophical implications of these theorems.

Gödel’s Second Incompleteness Theorem
In my presentation on Tuesday, I discussed Gödel’s first incompleteness theorem, and mentioned in passing that there were actually two. In a sense, this is historically appropriate: while Gödel gave a very detailed proof of his first incompleteness theorem, he gave only a quick sketch of the second one, promising to expand on it in a later paper that never materialized (Franzén, pp. 98). A vague hand-wavy statement of the second incompleteness might be phrased as follows:

Second Incompleteness Theorem. Let S be any consistent formal system capable of expressing a certain amount of arithmetic. Then S does not prove its own consistency.

Note that the “certain amount of arithmetic” required here is more than the “certain amount of arithmetic” required for the first incompleteness theorem. In particular, since systems which can talk about arithmetic can talk about their own theorems (by Gödel-numbering), these systems can express the proposition “there is no proposition A such that I prove both A and not-A“. More concisely, these systems can express the proposition “I am consistent.”

The proof of this is a clever application of the first incompleteness theorem. We start by observing that all the reasoning we carried out (i.e., all the reasoning we handwaved away) to prove the first incompleteness theorem could also be formally carried out within S. That is, we can construct a sentence G which essentially says “G is not provable in S“; then S proves “G if and only if I do not prove G” (S needed to prove this for the first incompletness theorem to go through) and then goes on to prove “if I am consistent, then I do not prove G and I do not prove not-G“.

Now, suppose S could prove its own consistency. If S proves “I am consistent”, then it could use the last statement above to prove “I do not prove G and I do not prove not-G“, from which it could deduce “I do not prove G“. But S has already proven “G if and only if I do not prove G“, so if S proves “I do not prove G” then it goes on to prove G. Since S proves G and contains “a certain amount of arithmetic” allowing it to introspect its own proofs, S proves “I prove G.” But now S has proven “I prove G” and it has also proven “I do not prove G“. We conclude that S is inconsistent.

Philosophical Implications
Tony raised the following question: does Gödel’s incompleteness theorem apply to physical theories? (I think it was Tony — please correct me if I am wrong.) Since elaborate mathematical models are the coin of the realm in physics, it is actually quite plausible to imagine that any particular theory of physics might be expressible as a formal system, and from there only a slight leap of faith to imagine that arithmetic can be expressed in such a system (it’s tempting to say “of course we can do arithmetic in a model of physics!”, but there are technical reasons why this is not quite trivial).

So let us imagine that we have such a theory of physics. From here we can legitimately say that Gödel’s theorem kicks in and gives us a sentence which is neither provable nor disprovable in our theory. Is this a terrific blow to the idea that physics can be completed? I do not believe so. For one thing, we have no reason to believe that the undecidable Gödel sentences will talk about anything particularly interesting when interpreted as physics: they will be huge, unwieldy sentences which talk in coded form about huge, unwieldy integers. If we had a theory of physics which fully explained the origin and ultimate fate of the universe yet failed to decide such abstruse sentences, then it is difficult to see how this theory would be meaningfully — rather than formally — incomplete.

Gödel’s theorem invites another philosophical question: how does it stand in relation to our own minds? Does it prove (as some have claimed) that our reasoning power exceeds that of any formal system? Is this the nail in the coffin for artificial intelligence? Or are we also subject to Gödel’s theorem, making it impossible to understand our own minds? I do not want to ruin the discussion by preaching any answers here — I’d like to see if anyone has their own thoughts on the matter.

Bibliography

  • Barrow, John (1998). Impossibility: The Limits of Science and the Science of Limits. Oxford University Press.

    The only part of this book I have read is the part which discusses Gödel’s theorem. I cannot say for sure whether the rest of the book is quite as silly as the quote I presented.

  • Franzén, Torkel (2005). Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. A K Peters, Wellesley, MA.

    A slim book discussing Gödel’s theorems and many of their misapplications. I relied on this book heavily for my presentation. However, it is probably a challenging read if acronyms like PA and ZFC are new to you.

  • Hofstadter, Douglas (1979). Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, New York.

    An enormous book discussing Gödel’s theorems, the art of Escher, the music of Bach, human consciousness, Zen Buddhism, molecular biology, and generally everything under the sun. This is the book that got me into mathematics. The MIU example was looted from here.

  • Smullyan, Raymond (1987). Forever Undecided: A Puzzle Guide to Gödel. Knopf, New York.

    A fun book discussing Gödel’s second incompleteness theorem through a series of puzzles in the vein of “knight/knave puzzles.” Smullyan builds up to Gödel’s theorem by explaining it in terms of reasoners rather than formal systems per se. This book is quite accessible to someone who is interested in the topic yet unfamiliar with logic.

Advertisements

Comments»

1. ebrister - January 26, 2009

Obviously, that quote was a typo. What I meant to say was “Blah blah blah.” Makes more sense now, eh?

I have a question for you about psychology, not philosophy. It’s clear that the incompleteness theorem says something only in relation to formal systems: that either they are incomplete or inconsistent. And you mentioned that people have tried (in silly and uninformed ways) to apply this theorem outside of formal systems. For instance, to say that the Bible is either incomplete or inconsistent. (Was that your example in class?)

My question is: why do you think people are led to make that move? Is it a respect for logic and math that borders on the magical?

2. ews8704 - January 26, 2009

Great job, Greg! I think I understand it now. I like all the cool links you added in. 🙂

I think some do have a “magical” respect for logic and math that leads them to use it as a cure-all.

I would like to see someone come up with a new book to the Bible that somehow “completes” it, that finds some way to reconcile all those inconsistencies and outright contradictions.

3. C. Steves - January 26, 2009

Personally, I think the misapplication of these theorems might stem from overestimating the power and reach of mathematics and science.

I feel like it might be analogous to a card game where there is a trump suit that automatically over-rides a card of any other value in any suit other than the trump suit.

I only say this because from my personal experiences it seems as though many people (particularly those without an elementary knowledge of science) seem to be of the opinion that science can do anything. I think it goes along with that quote about how the more you know, the more you realize how little you really know.

Then again, I think this question was directed at Greg and I just jumped in and voiced my opinion, so perhaps I’ll be moseying along now…

4. Greg - January 26, 2009

I don’t think misplaced faith in mathematics is really the explanation. My speculation is that a lot of it deals with a lack of technical sophistication combined with the way the story is just so compelling if Gödel applies to everything. Logic is supposed to be the last fortress of Certainty, and yet here comes Gödel out of that fortress to admit defeat and proclaim that we can never be certain. If Gödel applies everywhere and we cannot be certain of anything then logic fits perfectly into the rest of the twentieth century.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: