Did you solve it? 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.

I hope you enjoyed today’s puzzle. Thanks to Professor Benedikt Löwe of Churchill College, Cambridge, for suggesting the idea.

If you are interested in logic, many events are taking place on Friday January 14 to celebrate UNESCO’s World Logic Day.

I’ll be back in two weeks.

I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.

I’m the author of several books of puzzles, most recently the Language Lover’s Puzzle Book. I also give school talks about maths and puzzles (online and in person). If your school is interested please get in touch.