Solution: If you ask him whether the left road is the correct one—i.e., the road that leads to Pleasantville—the question would be useless, since you have no idea whether he is a liar or a truth-teller. The right question to ask is: “Are you the type who could claim that the left road leads to Pleasantville?” After getting an answer, you will have no idea whether he is a liar or a truth-teller, but you will know which road to take! More specifically, if he answers yes, you should take the left road; if he answers no, you should take the right road. The proof of this is as follows:
Suppose he answers yes. Either he is truthful or he is lying. Suppose he is truthful. Then what he says is really so, hence he is the type who could claim that the left road leads to Pleasantville, and, since he is truthful, the left road really does lead there. On the other hand, if he is lying, then he is not the type who could claim that the left road leads to Pleasantville, since only one of the opposite type—a truth-teller—can make that claim. But since a truth-teller can make the claim, the claim must be correct, and so again the left road is the one leading to Pleasantville. This proves that regardless of whether the yes answer is the truth or a lie, the left road is the correct road to Pleasantville.
Suppose he answers no. If he is truthful, then he really is not the type who could claim that the left road leads to Pleasantville; only a liar would claim that it does. Since a liar would claim that it does, then it really doesn’t, hence the right-hand road must lead to Pleasantville. On the other hand, if he is lying, then he would claim that the left road leads to Pleasantville, since he says he wouldn’t, but since a liar would claim that the left road leads to Pleasantville, then it is really the right road that leads to Pleasantville. This proves that a no answer indicates that the right road leads to Pleasantville, regardless of whether the speaker is lying or telling the truth.
This puzzle somehow reminds me of an old Russian joke.
Boris and Vladimir are two old friends who meet unexpectedly one day on a train. The following conversation ensues:
BORIS: Where are you going?
VLADIMIR: To Minsk.
BORIS (indignantly): Why do you lie to me?
VLADIMIR: Why do you say I am lying?
BORIS: You tell me you are going to Minsk in order to make me think you are going to Pinsk. But I know you are really going to Minsk!
Getting back to the Nelson Goodman principle, it is easy to see how we could uniformly solve the last six problems if we were not restricted to three-word questions. For example, in Problem 1, we could ask: “Are you the type who could claim that you are John?” The same goes for Problem 2. For Problem 3, we ask: “Are you the type who could claim you are Arthur?” For Problem 4, we could ask: “Are you the type who could claim that Arthur is truthful?”
In general, if you want to find out from a constant liar or constant truth-teller—you don’t know which—whether a certain proposition p is true, you don’t ask him: “Is p true?” Instead you ask him: “Are you the type who could claim that p is true?”
THE ABSENTMINDED LOGICIAN
A certain logician, though absolutely brilliant in theoretical matters, was extremely unobservant and highly absentminded. He met two beautiful identical-twin sisters named Teresa and Lenore. The two were indistinguishable in appearance, but Teresa always told the truth and Lenore always lied. The logician fell in love with one of them and married her, but unfortunately he forgot to find out her first name! The other sister didn’t get married till a couple of years later.
Quite shortly after the wedding, the logician had to go away for a logic conference. He returned a few days later. He then met one of the two sisters at a cocktail party and, of course, had no idea whether or not it was his wife. “I can find out in only one question,” he thought proudly. “I’ll simply use the Nelson Goodman principle and ask her if she is the type who could claim that she is my wife!” Then he had an even better idea: “I don’t really have to be that elaborate and ask such a convoluted question. Why, I can find out if she is my wife by asking a much simpler question—in fact, one having only three words!”
• 7 •
The logician was right! What three-word question answerable by yes or no should he ask to find out whether the lady he was addressing was his wife?
• 8 •
A few days later the logician again met one of the two sisters at another cocktail party. He again didn’t know whether it was his wife or his sister-in-law. “It’s high time I find out once and for all my wife’s first name,” he thought. “I can ask this lady just one three-word yes/no question, and then I’ll know!”
What three-word question could he ask?
• 9 •
Suppose that in the last problem, the logician had wanted to know both the identity of the lady he met and the first name of his wife. He is again restricted to asking only one question answerable by yes or no, but this time there is no restriction on the number of words in the question.
Can you find a question that will work?
Epilogue: The logician was in fact married to the truthful sister, Teresa. Lenore’s marriage, two years later, was a curious one: She detested her suitor, but when he one day asked her if she would like to be his wife, she, being a liar, had to answer yes. As a result, they got married!
The moral is that constant lying sometimes has its disadvantages.
SOLUTIONS
1 · The only three-word question I can think of that works is: “Are you James?” If you are addressing John, he will answer yes, since John lies, whereas both James and William would answer no—James because he lies, and William because he tells the truth. So a yes answer means that he is John and a no answer means that he is not John.
2 · The very same question—“Are you James?”—works, only a yes answer now indicates that he isn’t John and a no answer indicates that he is John.
3 · A common wrong guess is: “Are you Arthur?” This question is quite useless here; the answer you get could be the truth or a lie, and you would still have no idea which one is really Arthur.
A question that works is: “Is Arthur truthful?” Arthur will surely answer yes to this question, because if Arthur is truthful, he will truthfully claim that Arthur is truthful, and if Arthur is not truthful, then he will falsely claim that Arthur is truthful. So regardless of whether Arthur is truthful or whether he lies, he will certainly claim that Arthur is truthful. On the other hand, Arthur’s brother—call him Henry—will claim that Arthur is not truthful, because if Henry is truthful, then Arthur is really not truthful and Henry will truthfully claim that Arthur is not. And if Henry lies, then Arthur really is truthful, in which case Henry will falsely claim that Arthur is not truthful. So whether Henry is truthful or not, he will surely claim that Arthur is not truthful. In summary, Arthur will claim that Arthur is truthful and Arthur’s brother will claim that Arthur is not truthful. So if you ask one of the brothers whether Arthur is truthful, and if you get yes for an answer, you will know that you are speaking to Arthur; if you get no for an answer, you will know that you are speaking to Arthur’s brother.
Incidentally, there is another three-word question that works: “Does Arthur lie?” A yes answer to that question would indicate that you are not speaking to Arthur, and a no answer would indicate that you are speaking to Arthur. I leave the verification of this to the reader.
4 · To find out whether Arthur is truthful, all you need to ask is: “Are you Arthur?” Suppose you get the answer yes. If it is a truthful answer, then the one addressed really is Arthur, in which case Arthur is the truthful brother. If the answer is a lie, then the answerer is not really Arthur, in which case Arthur must be the other one, again the truthful brother. So regardless of whether the answer is truthful or a lie, a yes answer indicates that Arthur—whichever one he is—must be truthful. What if you get no for an answer? Well, if it is a truthful answer, then the speaker is not Arthur, but since he is truthful, Arthur must be the brother who lies. On the other hand, if the n
o answer was a lie, then the speaker really is Arthur, in which case Arthur just told a lie. So a no answer, whether it is the truth or a lie, indicates that Arthur is the liar.
5 · Just ask him: “Do you exist?”
6 · Just ask: “Are you truthful?” Both constant truth-tellers and constant liars will answer yes to that question.
7 · We recall that his wife’s sister was not married at the time. A three-word question that works is: “Is Teresa married?” Suppose the lady answers yes. She is either Teresa or Lenore. Suppose she is Teresa. Then the answer is truthful, hence Teresa is really married, and the lady addressed is married and his wife. If she is Lenore, the answer is a lie; Teresa is not really married, so Lenore—who is the lady addressed—is married, hence again the lady addressed is his wife. So a yes answer indicates that he is speaking to his wife, regardless of whether the answer is the truth or a lie. I leave it to the reader to verify that a no answer indicates that he is speaking to his wife’s sister.
8 · The question to ask now is: “Are you married?” Suppose she answers yes. Again, she is either Teresa or Lenore. Suppose she is Teresa. Then the answer is truthful, hence the lady addressed is married, and since she is Teresa, he is married to Teresa. But what if the lady addressed is Lenore? Then the answer is a lie, hence the lady addressed is not really married, and he is married to the other lady, again Teresa. So in either case, a yes answer indicates that his wife’s name is Teresa.
I again leave it to the reader to verify that a no answer indicates that his wife’s name is Lenore.
9 · No, because no such question exists!
You see, in each of the preceding problems, we were trying to find out which of two possibilities holds, but in this problem, we are trying to find out which of four possibilities holds. (The four possibilities are that the lady addressed is Teresa, his wife; that she is Lenore, his wife; that she is Teresa, his sister-in-law; and that she is Lenore, his sister-in-law.) However, a yes/no question can elicit only two possible responses, and with only two possible responses it is impossible to determine which of four possibilities holds.
3
The Barber of Seville
1 • A Double Barber Paradox
Some of you are familiar with Bertrand Russell’s paradox about a barber of a certain town who shaved all of and only those inhabitants who did not shave themselves. In other words, given any inhabitant X who didn’t shave himself, the barber was certain to shave him. But the barber never shaved any inhabitant X who shaved himself. The problem is: Did the barber shave himself or didn’t he?
If the barber shaved himself, then he violated his rule by shaving someone—namely himself—who shaved himself. This is impossible; hence he didn’t shave himself. But if he didn’t shave himself, then he failed to shave someone—again himself—who didn’t shave himself. So it is also impossible that he didn’t shave himself. Therefore, did he shave himself or didn’t he?
The solution is simply that there couldn’t be any such barber. The assumption that such a barber exists leads to a contradiction; hence it is false.
The barber paradox bears a close relation to the famous liar paradox. Consider the sentence written in the following box:
The Sentence in This Box Is False.
Is the sentence true or false? If it is true, then what it asserts is really the case, which means that it must be false, because that is what it asserts. On the other hand, if it is false, then what it asserts is not the case, which means that it is not the case that it is false; hence it must be true. So the assumption that it is false again leads to a contradiction.
There is also Phillip Jourdain’s “double” version of the liar paradox. Consider a card with the following sentence written on one side:
Side 1 The Sentence on the Other Side Is False.
When the card is turned over, it reads:
Side 2 The Sentence on the Other Side Is True.
Side 2, by asserting that the sentence on Side 1 is true, is asserting that what Side 1 says is really the case—in other words, that the sentence on Side 2 is false. So the sentence on Side 2 is indirectly asserting its own falsity, and we have the same paradoxical situation.
I have thought of a paradox that bears much the same relation to Russell’s barber paradox as Jourdain’s double liar paradox bears to the older liar paradox. You should read all three parts of the problem before turning to the solution.
Suppose I tell you that a certain town contains a barber named Arturo and that given any inhabitant X other than Arturo himself, Arturo shaves X if and only if X doesn’t shave Arturo. In other words, if Arturo shaves X, then X doesn’t shave Arturo, but if Arturo doesn’t shave X, then X does shave Arturo. Does this lead to a paradox?
Suppose, instead, I had told you that the town contains a barber named Roberto and that for any inhabitant X, Roberto shaves X if and only if X does shave Roberto. In other words, if Roberto shaves X, then X shaves Roberto, and if X shaves Roberto, then Roberto shaves X. Does this lead to a paradox?
Now, suppose I told you that the town contains both barbers—Arturo and Roberto—satisfying the above conditions. Does this lead to a paradox? Why or why not?
2 • What About This One?
Suppose I told you that the town contains two barbers, Arturo and Roberto, and that Arturo shaves all and only those inhabitants who shave Roberto, and Roberto shaves all and only those inhabitants who don’t shave Arturo. Does this lead to a paradox?
3 • Barber for a Day
A certain town contained exactly 365 male inhabitants. During one year, which was not a leap year, it was agreed that on each day one man would be official barber for the day. No man served as official barber for more than one day. Also, the official barber on a given day was not necessarily the only person who shaved people on that day; nonbarbers could also do some shaving.
Now, it is given that on any day, the official barber for that day—call him X—shaved at least one person. Let X* be the first person shaved by X on the day when X was official barber. We are also given that for any day D, there is a day E such that for any male inhabitants X and Y, if X shaved Y on day E, then X* shaved Y on day D.
Now, the above conditions certainly lead to no paradox, but they do lead to an interesting conclusion, namely that on each day at least one person shaved himself. How do you prove this?
4 • The Barbers’ Club
There is a certain club called the Barbers’ Club. The following facts are known about it.
Fact 1: Every member of the club has shaved at least one member.
Fact 2: No member has ever shaved himself.
Fact 3: No member has ever been shaved by more than one member.
Fact 4: There is one member who has never been shaved at all.
The number of members of this club has been kept a strict secret. One rumor has it that there are less than a thousand members. Another rumor has it that there are more than a thousand members. Which of the two rumors is correct?
5 • Another Barbers’ Club
Here is a well-known logic puzzle, appropriately dressed for the occasion.
Another barbers’ club obeys the following conditions:
Condition 1: If any member has shaved any member—whether himself or another—then all the members have shaved him, though not necessarily all at the same time.
Condition 2: Four of the members are named Guido, Lorenzo, Petruchio, and Cesare.
Condition 3: Guido has shaved Cesare.
Has Petruchio shaved Lorenzo or not?
6 • The Exclusive Club
There is another club known as the Exclusive Club. A person is a member of this club if and only if he doesn’t shave anyone who shaves him.
A certain barber named Cardano once boasted that he had shaved every member of the Exclusive Club and no one else. Prove that his boast involves a logical impossibility.
7 • The Barber of Seville
Any resemblance between the Seville of this story and the famous S
eville of Spain (which in fact there isn’t) is purely coincidental.
In this mythical town of Seville, the male inhabitants wear wigs on those and only those days when they feel like it. No two inhabitants behave alike on all days; that is, given any two male inhabitants, there is at least one day on which one of them wears a wig and the other doesn’t.
Given any male inhabitants X and Y, inhabitant Y is said to be a follower of X if Y wears a wig on all days that X does. Also, given any inhabitants X, Y, and Z, inhabitant Z is said to be a follower of X and Y if Z wears a wig on all days that X and Y both do.
Five of the inhabitants are named Alfredo, Bernardo, Benito, Roberto, and Ramano. The following facts are known about them:
Fact 1: Bernardo and Benito are opposite in their wig-wearing habits; that is, on any given day, one of them wears a wig and the other one doesn’t.
Fact 2: Roberto and Ramano are likewise opposites.
Fact 3: Ramano wears a wig on those and only those days when Alfredo and Benito both wear one.
To Mock a Mocking Bird Page 2
