Raymond Smullyan, who passed away last year, is, in my opinion, one of the most underrated logicians ever. He knew extremely well many complicated subjects of mathematical logic and could explain them in simple-to-understand logic puzzles.
His most famous work is outlining how
Tarski's theorem, which is much more general and easier to prove than Gödel's seriously shakes the foundations of mathematics. The key assumptions in Tarski's theorem are negation and self-reference, which is a common theme in Smullyan's puzzles. They always involve people who always lie or always say the truth, and make statements about themselves or about friends who make statements about them, and sometimes if the puzzle is solvable or unsolvable given some piece of information, and you have to work out what's actually happening.
I believe his book
The lady or the tiger? is among the best works of mathematics ever written. He starts with elementary puzzles that confuse laymen and quickly develops to more complicated logic puzzles, concluding with some chapters on formal systems in disguise, that has a puzzle which is essentially the proof of Tarski's theorem.
The key argument in the proof (the Gödel sentence) can be written very elegantly in the "Smullyan way". Consider an island where every inhabitant is either a knight or a knave. Knights always say the truth, while knaves always lie. Some knights, called established knights, belong to an exclusive club (which is essentially provable sentences). The question is, if you hear someone say "I am not an established knight.", what can you say about that person?
Simple, such person has to be a knight, because a knave would never make the true statement that he's not an established knight, so his statement must be true, which means that he's indeed not established. Translating into formal systems, we have a sentence that's true but is not provable. Another beautiful part of the book is the following paragraph:
"I must tell you an interesting and revealing incident," said Ferguson. "A student was asked on a geometry examination to prove the Pythagorean theorem. He handed in his paper, and the Mathematics-Master returned it with a grade of zero and the comment, 'This is no proof!' Later, the lad went to the Mathematics-Master and said, 'Sir, how can you say that what I handed you is not a proof? You have never once in this course defined what a proof is! You have been admirably precise in your definitions of such things as triangles, squares, circles, parallelity, perpendicularity, and other geometric notions, but never once have you defined exactly what you mean by the word 'proof.' How, then, can you so assuredly assert that what I have handed you is not a proof? How would you prove that it is not a proof?'"
This is a sadly accurate depiction of our educational system, and even many professional mathematicians have trouble understanding this simple idea. You can regularly see people pushing for different axiomatizations of mathematics, with philosophies like constructivism/finitism/whatever. In fact, they are trying to circumvent some assumptions of Gödel's theorem to find better foundations. But, as Tarski already proved long ago, this is a fantasy. The impact of Gödel's theorems do not depend on infinity or on a particular arithmetic. They happen whenever you have a language that can make assertions about the semantics of its own sentences. To circumvent this, you must create something that has absolutely no resemblance to human reasoning. Indeed, as Smullyan tells us at the end of his book:
"In the prophetic words of the logician Emil Post (1944), this means that mathematical thinking is, and must remain, essentially creative. Or, in the witty comment of the mathematician Paul Rosenbloom, it means that man can never eliminate the necessity of using his own intelligence, regardless of how cleverly he tries."
So, after this long introduction, paying homage to Smullyan, I will propose here the puzzle that gives the book the title "The lady or the tiger?", which is originally a short story about an unsolvable problem. The puzzle follows below:
A prisoner is having a
lady and tiger trial, but instead of purely chance, he can save himself using logic. There are nine doors. One of the doors has a lady behind and the others are either empty or have tigers behind them. If the prisoner enters the door with the tiger, he dies. If he enters an empty room, nothing happens, and if he enters the one with the lady, he marries her. The lady is a woman the prisoner loves, so he would prefer marrying her.
At each of the nine doors there is a sign. If a lady is inside, the sign says the truth. If a tiger is inside, the statement on the sign is false. If the room is empty, the sign can be either true or false. The signs on each of the rooms are:
I - The lady is in an odd-numbered room.
II - This room is empty.
III - Either sign V is right or sign VII is wrong.
IV - Sign I is wrong.
V - Either sign II or sign IV is right.
VI - Sign III is wrong.
VII - The lady is not in room I.
VIII - This room contains a tiger and room IX is empty.
IX - This room contains a tiger and VI is wrong.
The prisoner then looks at the signs and concludes "This problem is unsolvable! That's not fair!". "I know", laughed the king.
The prisoner replies "Very funny! Come on, now, at least give me a decent clue: is room VIII empty or not?"
The king told the prisoner whether Room VIII was empty or not and the prisoner successfully deduced the location of the lady.
Which room has the lady?
