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?
Please return at 5pm UK for the solutions and a discussion.
NO SPOILERS. Instead please post your favourite logic jokes.
Today’s Gödelian puzzle is a pre-celebration of UNESCO’s World Logic Day, which takes place annually on January 14. (The date was chosen since it is both the day Gödel died, in 1978, and the day the logician Alfred Tarski was born, in 1901.)
To find out more about World Logic Day 2022 – this Friday – and read a list of all the events planned click here.
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.
