June 11, 2005

This title is complet

This sentence is false.

What do you make of that? Give it a thought, and I bet you'll quickly lose track of what "true" and "false" are any more. How does an innocent enough sentence turn this diabolical?

Sentences like that one are called "self-referential" -- they make statements about themselves. For example, this sentence you are reading just now refers to itself. Got that? For another example, this sentence has sixteen words, two commas and a period at the end. Right?

But self-referential sentences that make bald, true assertions about themselves -- like a word/comma/period inventory -- are a novelty for a while, then get boring. I mean, isn't this one boring? Others are more interesting ones. For example, the one that begins this piece is a variation of perhaps the best known self-referential sentence of them all, the Epimenides paradox. Epimenides, who lived in Crete many centuries ago, might have been like most of his contemporaries: long dead and forgotten.

Except that he apparently once said: "All Cretans are liars."

Innocent enough, on the face of it. But wait, Epimenides himself was Cretan! What does that mean for his sole famous utterance? Think about it. If he's a truth-telling Cretan, his statement is false -- at least one Cretan is not a liar. But if his statement is false, that makes him a liar, and his statement is true. Now what?

Want more? What would you do if someone told you: "Disobey this command"? What do you make of this: "This sentence contains exactly thiree mistooks"?

So they're intriguing, maybe you'll concede that. But aside from that, what's so special about self-referential sentences?

One answer to that question involves Kurt Gödel, arguably the most influential mathematician of the 20th century. At 25 in 1931, Gödel published a paper called "On Formally Undecidable Propositions of Principia Mathematica and Related Systems." It challenged some very basic assumptions of logic and mathematics, and has been a major influence on modern scientific thought. Harvard awarded Gödel a honorary degree in 1952, and in doing so called his 1931 work one of the most important advances in logic in modern times.

The really interesting thing about Gödel's Incompleteness Theorem, as it is known, is that it is in effect a mathematical translation of the Epimenides paradox.

First, a little background. If you remember geometry, you will probably also remember that it is founded on certain truths, or axioms. Like the one that says two parallel lines will never meet.

Geometry is different from a science like astronomy, in which we observe phenomena and postulate theorems based on them. The entire edifice of geometry is built on accepting, without proof, some axioms as a foundation. The rest of the edifice is derived logically from these axioms, as theorems. The ancient Greeks discovered this axiomatic method and developed the complex system of geometry we know today.

This idea -- of a small number of axioms that underpin the structure of a logical system like geometry -- has fascinated thinkers throughout history. Many thought geometry's spare base of axioms and its clean, inexorable logic was scientific knowledge at its best. Naturally, they wondered if other fields of mathematics lent themselves to similar methods. Over the last two hundred and fifty years, the axiomatic method has been applied to other branches of mathematics with increasing success. In fact, by the early 20th Century, there was a general belief that each branch of mathematics had a set of basic axioms that were enough to deduce all theorems in that branch. Just as the Greeks had done for geometry.

Unfortunately, Gödel showed this up as the pleasant pipe dream it was. According to his 1931 paper, there are limits to the axiomatic method. They make it impossible to find a sufficient set of founding axioms for even as simple a mathematical system as arithmetic with numbers. More than that, he also showed that it is impossible to be logically consistent in many axiomatic systems that use logic.

That is, we have to accept that by their very definition, such systems will have internal contradictions.

Now you will need extensive mathematical training to understand Gödel's reasoning and proof. But in essence, his Incompleteness Theorem says this: in any axiomatic system, it is possible to construct a formula, say "F", which says "This formula F cannot be proved." He also showed that F can be proved if, and only if, its opposite can also be proved.

By now, you see the paradoxes. "All Cretans are liars" can be true only if at least one Cretan, Epimenides himself, is telling the truth. But that makes it false. If you obey "disobey this command", you have disobeyed it. More simply, if "this sentence is false" is true, it must be false.

Gödel went further still with his theorem, and finally arrived at the only possible conclusion: the axioms of such a system are incomplete, and we can never come up with a complete set. Gödel's Incompleteness Theorem tells us that mathematics is essentially incomplete. As the computer scientist Douglas Hofstadter wrote about the Incompleteness Theorem: "Somehow the full power of human mathematical reasoning eludes capture in the cage of rigor."

Epimenides could never have imagined his link through the centuries to a German mathematician called Kurt Gödel. You see, I am sure that last sentence is true. But this one, now it says nothing at all.

12 comments:

Sanketh said...

I am not sure if you've read Godel, Escher, Bach by Douglas Hofsdtader. Same idea, very nicely communicated. Worth a read.

Anirudh Karnick said...

Interesting post. I like your occasional posts on science. Are there any other science blogs which are free of jargon? If so, please give their addresses.

Anonymous said...

Please to make the science column a regular!!

-
Z

Neela said...

dilip

I enjoyed that post so much that I now have a request:

I've been trying to understand the concept of the Just Temperament vs Equal temperament scale (made famous by Bach's Well Tempered Clavier) in music. Unfortunately, as with the Incompleteness theorem, I can't seem to get my head around it and I was wondering if you could simplify it. Any of the audience also welcome to explain.

Thanks

n!

Anonymous said...

You see, I am sure that last sentence is true.

By "that last" you mean, the "previous" I suppose, or else if you are "sure that, the last sentence is true", then you are not sure ;-)

B

Anuttama said...

Not to nitpick but the "All Cretans are liars" statement is not necessarily a paradox in the form you have phrased it here. If we assume that the statement is true, then we do have a contradiction as Epimenides is a Cretan and hence cannot be telling the truth. If, on the other hand, you assume that the statement is false there is no contradiction. Epimenides may be a liar but that does not necessarily make all Cretans liars -- hence the statement can still be false.

Abi said...

Nice post, Dilip. I really enjoyed it.

Since you are talking about self-referential entities, take a look at this divine question paper from self-referential heaven. (link via Alex Tabarrok of Marginal Revolution).

Suresh said...

Nominated your post for the latest Tangled Bank (scroll to the math section). great stuff !

http://geomblog.blogspot.com/2005/06/tangled-bank.html

Ricky said...

"If he's a truth-telling Cretan, his statement is false -- at least one Cretan is not a liar. But if his statement is false, that makes him a liar, and his statement is true. Now what?"

If his statement is false, it does make him a liar. But that doesn't mean that all other Cretans are liars as well. Only this one. So the fact that he lied means that "Some Cretans are liars" a true statement, not all.

Dilip D'Souza said...

Thanks, all! I'm gratified by the response this post (and my other occasional science posts) got. Some thoughts:

Sanketh, I have indeed read GEB, a fabulous cornucopia of provocative ideas. (This is true: I spent an entire Christmas vacation holed up in my room reading it). I think the Hofstadter quote I have in my piece is from there.

Anirudh, instead of listing blogs for you, may I just point you to Suresh's Tangled Bank post. There's such a lot to read via the links there, all fine stuff; let me plug Cosma Shalizi's work.

Suresh, thanks so much for putting my piece in your compilation. I'm flattered by the company you make me keep...

Neela, I'll soon have something for you, either via email or a comment here or a post by itself, let's see, on Equal vs Just Temperament.

Anuttama, So what you are saying is that to run into the contradiction, we start by assuming the statement in question is true? Got that.

Abi, I have stumbled on that question paper, and have spent many interesting if confusing moments trying to solve it. But I must find an hour or two at a stretch to do it. Fascinating.

zap said...

Btw, have you should read this book called “The Lady or the Tiger” by Raymond Smullyan. It is a book of logic puzzles & has this awesome one called the Monte Carlo Lock mystery that leads one step by step into the heart of Godel’s theorem before you realize it.

Anonymous said...

Btw, have you read this book called “The Lady or the Tiger” by Raymond Smullyan? It is a book of logic puzzles & has this awesome one called the Monte Carlo Lock mystery that leads one step by step into the heart of Godel’s theorem before you realize it.

-
Z