gödel’s incompleteness illustrated

I am having a great time reading Smullyan’s Gödel’s Incompleteness Theorems, a thin volume with the most elegant description of Gödel’s and Tarski’s work i’ve read so far. It’s also the most succint, and it starts with a very nice and very clear demonstration of indecidability that is the simplest i have ever seen. I like it a lot, and it’s short enough for a quick blog post. Here it goes.

Imagine you have a machine that knows how to print strings composed of finite combinations of the characters P, N, (, ) and ~. We’ll call any string composed of any number of these characters an expression. Thus P~, (P~) or ~PN(P) are expressions. But only some expressions are valid. Valid expressions are called sentences and our machine can only print sentences. Sentences must have one of the following forms:

• P(X)
• ~P(X)
• PN(X)
• ~PN(X)

where X is any expression. So, for instance, P(N), ~PN(~P(NNP)) are sentences, but N(P) or (P(NP)) are not.

Everything our machine prints is a sentence, but we don’t know whether our machine is capable of printing all possible sentences. We’ll say that the sentence X is printable if our machine can print it.

Our sentences can be assigned a meaning. Let’s define the norm of an expression X as the expression X(X), and with that give the following interpreations to our sentences:

• P(X) means that the expression X is printable
• PN(X) means that X’s norm (i.e., X(X)) is printable
• ~P(X) means that the expression X is not printable
• ~PN(X) means that X’s norm (i.e., X(X)) is not printable

With those meanings associated to sentences, we can actually say whether a sentence is true or false, and our little machine becomes self-referential: it prints sentences that say what the machine can or cannot print!

Now, let’s assume that our machine never lies: it only prints true sentences. The question is: will our machine be able to print all true sentences? Or is there a sentence that is true but our machine cannot print?

Think about it for a bit.

The trick is to find a sentence that is self-referential, and says out loud “i cannot be printed”. If a sentence that means “this sentence cannot be printed” were printable, that sentence would be false, but we are supposing that our machine never lies. Therefore, our machine cannot print the sentence “this sentence cannot be printed”, which is then a true sentence.

In symbols, our sentence is ~PN(~PN). This sentence says that the norm of ~PN is not printable, but remember that the norm of X is X(X), so the norm of ~PN is ~PN(~PN).

So you see, as soon as you have a system that is capable of self-reference, you’ll be able to prove that the system is incomplete, in the sense that, if it is accurate, it won’t be able to express all truths about itself. Gödel was able to find a way of expression arithmetic propositions as numbers, and that opened the door to self-reference. And the fun began!

This is just an appetizer: if you are not scared by a bit of math (and it’s only a bit), by all means give Smullyan’s book a try. It’s much, much better than any of his famous puzzle collections.