Gödel

In 1931, the Austrian logician Kurt Gödel published his incompleteness theorem, a result widely considered one of the greatest intellectual achievements of modern times.

The theorem states that in any reasonable mathematical system there will always be true statements that cannot be proved. The result was a huge shock to the mathematical community, where the prevailing view was an unshakeable optimism about the power and reach of their subject. It had been assumed that maths was “complete”, meaning that all mathematical statements are either provable or refutable. The 25-year-old Gödel demonstrated this was incorrect by constructing a true statement that was not provable. Maths, he announced, has its limits.

The incompleteness theorem transformed the study of the foundations of mathematics, and would become an important result for computer science, since it shows that all formalised systems, such as coding languages, have limitations on what they can achieve.

The theorem is also at the heart of today’s puzzle, which we’ll get to shortly.

Gödel’s proof of his theorem is based on self-reference: in a formal mathematical setting, the statement ‘This sentence is unprovable” is both true and formally unprovable.

The technical details of the proof are hard going. Yet the American logician Raymond Smullyan (1919-2017) devised a brilliant way to convey the gist of the incompleteness theorem using simple logic puzzles about truth-tellers and liars. Today’s teaser, composed in cooperation with Professor Benedikt Löwe of Churchill College, Cambridge, is inspired by Smullyan’s approach.

The two tribes of If

In the Ocean of Deduction lies the logical island of If. People born here belong to one of two tribes: the Alethians and the Pseudians. The only way to tell an Alethian from a Pseudian is to talk to them. Alethians always speak the truth, no matter what they are saying. Pseudians will always utter falsehoods, no matter what they are saying.

At the centre of the island, the Master of the Alethians keeps the Ledger of Identity, a book that lists the names of everyone born on the island together with their tribe. The information in the Ledger of Identity is correct and freely available to anyone who asks.

One day, an intrepid explorer arrives on If. She encounters various inhabitants and identifies them as Alethians and Pseudians by asking clever questions.

After several successful such encounters, she meets a man called Kurt. The explorer does not know his tribal affiliation, but before she has time to ask him a question, he says “You will never have concrete evidence that confirms that I am an Alethian.”

1. Is Kurt an Alethian, a Pseudian or neither?

2. How might this relate to Gödel’s incompleteness theorem?

°•°●°°°°●

Earlier today I set you the puzzle below, which is based on Gödel’s incompleteness theorem. As I discussed in the original post, this theorem is one of the most famous in maths and states that in any mathematical system there will always be true statements that cannot be proved.

For example, in a formal mathematical setting, the statement ‘This sentence is unprovable” is both true and formally unprovable. When Gödel published his theorem in 1931 it up-ended the study of the foundations of mathematics and its consequences are still being felt today.

The two tribes of If

In the Ocean of Deduction lies the logical island of If. People born here belong to one of two tribes: the Alethians and the Pseudians. The only way to tell an Alethian from a Pseudian is to talk to them. Alethians always speak the truth, no matter what they are saying. Pseudians will always utter falsehoods, no matter what they are saying.

At the centre of the island, the Master of the Alethians keeps the Ledger of Identity, a book that lists the names of everyone born on the island together with their tribe. The information in the Ledger of Identity is correct and freely available to anyone who asks.

One day, an intrepid explorer arrives on If. She encounters various inhabitants and identifies them as Alethians and Pseudians by asking clever questions.

After several successful such encounters, she meets a man called Kurt. The explorer does not know his tribal affiliation, but before she has time to ask him a question, he says “You will never have concrete evidence that confirms that I am an Alethian.”

1. Is Kurt an Alethian, a Pseudian or neither?

2. How might this relate to Gödel’s incompleteness theorem?

Solution

1. Kurt is neither.

If he was a Pseudian, then the statement “You will never have concrete evidence that confirms that I am an Alethian” is true. But Pseudians never tell the truth, so Kurt cannot be Pseudian.

If he was Alethian, then everything he says, and therefore also the statement “You will never have concrete evidence that confirms that I am an Alethian” is true. But we know the statement is false, since the explorer can go to the Ledger of Infinity, look up his name, and check that he is Alethian. So Kurt is not Alethian.

In conclusion: Kurt was not born on the island of If.

2. Gödel’s incompleteness theorem states that there are mathematical statements that are true but not formally provable. A version of this puzzle leads us to something similar: an example of a statement that is true but there is no concrete evidence for its truth.

For example, assume that the explorer is the first person ever to step on the island who wasn’t born there, so everyone is either an Alethian or a Pseudian, and that the explorer knows this fact. Let us also imagine that the moment Kurt speaks, the Ledger burns to ashes. (The destruction of the ledger is to avoid running into the self-contradictions we saw in 1.)

By our previous argument, no Pseudian can ever utter Kurt’s statement, so Kurt cannot be a Pseudian. Thus, by our additional assumption about everyone being born on If, he must be an Alethian, and thus, his utterance is true, i.e., the explorer will never have concrete evidence that he is an Alethian.

But she will also never have concrete evidence that Kurt’s statement itself is true: if she ever does, it would be concrete evidence that he is an Alethian (since only those speak the truth). But that would say that the statement is false.

So, Kurt’s utterance is true but there is no concrete evidence for its truth. Indeed, his sentence is precisely the type of self-referential statement that forms the basis of Gödel’s proof of his incompleteness theorem. To repeat what I said at the top of the story: in a formal mathematical setting, the statement ‘This sentence is unprovable” is both true and formally unprovable.

In summary, the island of If is a magical place where all true statements about tribal identity can be verified in the Ledger. When we take away the Ledger, however, it doesn’t take too long to find a true sentence for which there is no concrete evidence.

The world of mathematics is analogous to If without the Ledger. Maths has no unmediated access to truth, which leads to the existence of statements that are both true and unprovable.