This is another old paradox, which I'm posting mostly because I like the author's style in presenting it:
In the Hanged-Man Paradox, a man, K, is sentenced on Sunday to be hanged, but the judge, who is evidently French or enamored of the French wit for surprising those sentenced to the guillotine in their last moments, orders that the hanging take place on one of the next five days at noon. Smiling wistfully, he says to K, "You will not know which day until they come to take you to the gallows."
K, who has evidently been condemned for logical perversions, cannot prevent his mind from nevertheless trying to figure out in advance which day will be his last. He quickly realizes it cannot be Friday, because if he has not been hanged by Thursday noon, he will know nearly a full day before they come to get him that he will be hanged on Friday. He is simultaneously pleased at his cleverness and depressed that he has pushed his date with the gallows closer to Sunday.
Soon enough, he realizes that if Friday is logically excluded, then so is Thursday, because if he has not been hanged by noon Wednesday, he will know that, Friday being excluded, his date must be Thursday. In like manner, he can exclude Wednesday, Tuesday, and Monday. As a logician, he smugly concludes that the judge's decree is false. On Thursday noon he is hanged. The paradox is that he is surprised when they come to take him to the gallows.
(One can easily think up less macabre relatives of the Hanged-Man Paradox, such as the Surprise Quiz, a device with which we are all familiar and by which no doubt many of us have illogically been surprised.)
Russell Hardin, Collective Action 147 (1982) (paragraph breaks added). (Of course this isn't a real paradox — just a cautionary tale.) Hardin concludes (p. 148): "His problem was that facing a hangman focused his mind a little too admirably."
P.S. On people named K, see Kozinski & Volokh, The Appeal, 103 Mich. L. Rev. 1391 (2005).
UPDATE: AnonVCfan refers, in the comments, to the "less refined, ugly cousin of this paradox," the famous dialogue from The Princess Bride. I'll reproduce here what I wrote in the comments: "I see the Princess Bride dialogue as illustrating the fact from Game Theory that the game of Matching Pennies has no Nash equilibrium in pure strategies. The Hanged Man's paradox is 'simpler' in a way, because all you need to refute it is elementary logic."
UPDATE 2: Just so no one gets confused here — this paradox is only "simpler" in a way. It's got an intuitive explanation, but in fact it's very hard, and logicians have written like a hundred articles about it. For a good overview, see this paper by Tim Chow. I can follow the gist of it, but the technical aspects are beyond my knowledge of logic.
Related Posts (on one page):
- A most ingenious paradox:
- Ellsberg paradox, take 4:
- Ellsberg paradox, take 3:
- Ellsberg paradox, take 2:
- Balls:
/Now I have a headache. Spasibo.
http://www.imdb.com/title/tt0093779/quotes
Consider the first step of the argument. If the execution happens on the last day then the prisoner will not be surprised. The supposed argument here is that the prisoner knows the judge is infallible so will carry out his sentence as he said thus he know he must be executed today and is not surprised. However, if such logic worked the prisoner would also be convinced he CAN'T be executed on the last day. Thus he *would* be surprised by an execution on the last day and nothing gets started.
To illustrate the point try expunging the slippery concept of surprise and replacing it with some formal notion of proof. For instance if x ranges over days of the week you might have axioms Ex(Executed(x)) and (Pf(Executed(x))->~Executed(x)). Now either the Pf predicate includes proofs from inconsistent axioms or it doesn't. If it does it shows that there will be no execution on any day and we realize the judge did not speak truly. If it doesn't then you don't ever prove you can't be executed on the last day.
In either case while still interesting the paradoxical aspect falls apart when you try to formalize the statement illustrating that the real problem is with our assumption that one is never surprised if one has a argument that something will happen, even if that argument turns out to be in an inconsistent system.
If you assume that "You will be executed and you will be surprised," then K's reasoning is correct and he can never be executed. Because that contradicts the assumption, the assumption must be wrong. The negation of the assumption is: "You might not be executed, or you might not be surprised."
Under that new assumption -- where you're no longer committed to the Archangel Gabriel truth of what the judge said -- everything makes sense. You can no longer rule out Friday because there's some chance that you won't be surprised. So now all days are fair game, and you may in fact be surprised!
It is inappropriate because any paradox can be tautologically resolved by assuming that the terms of the paradox are inaccurate. Reasonable discussion of paradoxes or hypotheticals generally requires accepting the preliminary statements as true.
It is incorrect because all Sasha has shown is that it is not logically consistent to assume the judge was incorrect in the first place, since doing so in the way Sasha did leads to the conclusion that the judge was not incorrect after all.
Finally, the analysis is unreasonable because Sasha claims the paradox has an "easy resolution." Considering the vast literature on the paradox, it is not reasonable that Sasha's two-sentence triviality would resolve the paradox and that, if it did, the resolution would be "easy."
But the reasoning of the condemened man that he could not be executed on Friday also seems to be sound. Once you grant that, then all is lost.
The only "solution" I was able to come up with back at Berkeley was that the condemned man could think to himself "if come Thursday evening I am still alive, then will I be executed on Friday? If I am, then the judge said can't be true, since I would know about it on Thursday. If I am not, then what the judge said also can't be true, because he said I would be executed by Friday. So I guess if I am alive Thursday evening, then I just won't know what my fate will be on Friday."
Then it becomes just another epistemological riddle -- showing that we can't ever really know anything. At the time I was satisfied with that, but my brainer buddies weren't. And now I am not either.
Lets assume that someone is 'surprised' by any event which occurs which has a less than 50% chance of occuring. In this case, a 'schedule' where the convict is hanged with a 50%-e chance (where e is an arbitrarily small number) on Monday, 25% on Tuesday, 12.5% on Wednesday, 6.25% on Thursday, and 3.125% on Friday, and a 3.125%+e chance of no hanging, then on Monday, he will be surprised (chance is 50%-e). On Tuesday, he will be surprised, because he will have updated his probabilities to take P(event(tuesday)=1) given event(monday) = 0. That will be approximately (25%-e)/(50%+e), which is marginally less than fifty percent, and so he would be surprised. The same updates occur for Wednesday, Thursday, and Friday. The convict is always surprised, and yet there is a 96.875%-e chance he will ultimately hang.
You can extend this and guarantee execution by continuing the 'game' infinitely. In the limit, the cumulative probability of execution will approach 1, and yet the convict will be surprised on any given day that it occurs. You can also choose a lower percentage chance for surprise and still get the same result, though slower. (If you go too low, you start running into the issue of convergence occuring after natural death, but I doubt anyone is so pessimistic that they would only be surprised if they 'lost' a, say, 1 in 100 shot, and not surprised if they lost a 1.25 in 100 shot. The terminally optimistic might be surprised even with probabilities greater than 1/2.)
Or, less 'logically', think outside the box and assume the judge meant noon in Texas, without telling the crook. (7PM in France.) Then, the convict would feel dread leading until noon, and relax after noon. He would then be surprised, EVEN ON FRIDAY, when the guards came at 7PM.
First, assume there are five boxes, labled "1," "2," "3," "4," &"5." You are told, correctly, that one and only one of these boxes contains a red ball. You are also told (correctly, if it is logically possible for the speaker to be correct) that it will be impossible for the subject to deduce which box the ball is in before he opens it.
This seems to me an exact parallel to the hangman paradox: the ball cannot be in the fifth box opened, because if the subject had not found the ball by the time he reached the last box, he would know this box would have to contain the ball. Knowing it could not be in the 5th box opened, he knows it could not be in the 4th box he opens, because otherwise, if he reached box 4, he would know it had to be in that one, etc. It makes no difference which order he opens the boxes.
But now suppose the subject comes to box 4 without having found the ball yet. Suppose he opens the box and the box contains a red ball. Was he in a position to deduce that he would do so? No. Therefore, both portions of the paradox (one box contains the ball and the subject will never be able to correctly deduce in advance which one it will be prior to opening) is satisfied.
You cannot correctly conclude that this statement is true.
Certainly you cannot correctly conclude that the statement is true, since by doing so, you make the statement false. But, since you cannot correctly conclude that the statement is true, it IS true, and anyone to whom the statement is not directed can see that.
I believe that the hanging (or exam) statement is similar. It challenges the person it is directed to to come to a conclusion, and that conclusion is self-defeating. The only thing the person can do is abandon coming to a conclusion, perhaps realizing that the statement is true despite being unable to "conclude" that it is true -- much in the way that you can "see" how the bolded statement above is true without being able to "conclude" that it is true.
A more striking variant is to use the one-day version. Suppose a teacher said:
I will give you an exam tomorrow, and you will not expect it (with certainty).
What is the student supposed to do with that? If the student expects the exam (with certainty), then the teacher's statement is false regardless of whether the teacher gives the exam. Thus, if the teacher's statement can be false, what's the basis for concluding (with certainty) there will be an exam? Thus, the fact of expecting the exam with certainty renders the teacher's statement potentially false, in which case the student cannot (logically) expect the exam with certainty. Seems to me this is quite parallel with the first bolded statement above. And, note that others can expect with certainty that the exam will be given, but the student to whom the statement is made cannot, or at least cannot get there logically.
The only point this raises, to me, is whether to call this a paradox. I would not call the situation raised by the first bolded statement a paradox, but I would not argue with those who defined "paradox" to include that situation. By extension, I do not view the second situation as a paradox, but again have no problem with those who do (and indeed I see how it has a greater claim to that term than the first -- sometimes the difference between "not a paradox" and "paradox" is how you dress it up).
I like your formulation. It's crisper than the ones I've seen.
When in fact the version with multiple days is just a harder-to-understand version of the single day problem, and any real understanding of the paradox can be made by looking at the single day version.
So the judge says "You cannot correctly conclude that this statement is true" and "if you can't correctly conclude that the first statement is true, you will be executed". That's essentially the hanging problem without the days in it and is much easier to understand (and is the same as the exam problem).
(c) There will be an examination next week and its date will not be deducible in advance using this announcement as an axiom.
This is a self-referential statement of the type which is contradictory.
However, a better formalization of the paradox is:
(c') There will be an examination next week and its date will not be deducible in advance *by the students* using this announcement as an axiom.
This statement isn't contradictory, and anyone who is not one of the students may deduce it is true. (And there's no need to say that the students are just psychologically surprised--they're logically surprised).
Let's look at Friday-it's a beautiful morning, the birds are singing, the sun is shining, and the prisoner wakes up in a good mood because he knows he will not be hanged today! So what is his reaction when he is led to the gallows? Surprise!
How can the prisoner argue to spare his life without proving the judge right? As soon as he opens his mouth to say "You can't hang me today" the judge has a hole big enough to drive a truck through. "Did you come here expecting to be hanged?" Regardless of the answer, the solution drives logically to a hanging. A "No" answer hangs the prisoner outright. A "Yes" brings the next question: "Upon what grounds are you objecting to your hanging?" Any response is an admission this his hanging is a surprise to him, allowing the judge to hang him.
And if the prionser does not open his mouth, either because he is too dumb to follow logic, or smart enough to realize when he is outmaneuvered, he gets hanged anyway.
Marty H.
It's not that the judge's statement must be untrue, rather that K cannot conclude that it is true. Because K cannot conclude that the statement is true, it can be true.
I can understand the reasoning to exclude Friday, because if he is still alive on Thursday, then Friday would be the only remaining day for execution and would not be a surprise.
But I'm sorry that I don't follow how this an work backward to exclude the other days.
On Monday a.m., he only knows that he could NOT be executed with surprise on Friday, but that he could be executed on Monday, Tuesday, or Wednesday.
It seems to me that the paradox would work only if it is limited to two days. He knows that he cannot be executed on the second day because he would know this is what will happen after the first day so he will know that he execution must be on the first day, therefore excluding it as well. But when you add a 3rd day, it seems there is uncertainty as you work forward through time.
Also, negating "you will be surprised" does not result in "you will not be surprised" but rather "you might not be surprised," i.e. you might be executed on Friday or you might not be executed at all.
Also, the inherent nature of surprise is such that when you have ~H v ~S, there is a level of uncertainty about ~H and ~S, so if you are or are not hung, surprise is an emergent property from it.
That's how the backwards reasoning works. Every time you eliminate a day, might as well strike it off the calendar completely, and then the next-to-last day becomes the last feasible day. Lather, rinse, repeat.
Lets rephrase your ball and box problem a little. Suppose you are told 1) There is a red ball in one of the five boxes. and 2) There is no order that you can open the boxes which will allow you to deduce which box the ball is in before you open the box.
There is no paradox here. One of these statements is false.
Everyone else: people keep taling about surprise. The judge doesn't say anything about K being surprised in the first example. That's in some other versions of this conundrum. If you want to talk about a slippery concept, then the one you should deal with is whether K can "know" anything from logical deduction.
Sorry for being dense here, but it seems that the paradox only works if you travel backwards through time.
I agree that on Wednesday night you would know that Thursday is dq'd.
But on Tuesday night, you would not know whether the execution was to be Wednesday or Thursday, right?
Without going into too much detail, it seems clear to me that the paradox comes about because:
The terms of the paradox reference the mental state of a participant in the paradox.
This hugely complicates the logic. It's a sneaky way of making logic self-referential.
The act of working out the logic of the paradox feeds back into and affects the conditions of the paradox. That's what makes it so hard.
You could make a class of paradoxes of this sort.
You won't conclude that this is a fact, and you'll be wrong.
What I was trying to say earlier is nicely detailed in Fitch's proof in the linked paper.
Either the judge is merely making some purely psychological claim (in fact you will have the emotional state of surprise). In this case there is no proof of contradiction. You can have this emotional state many ways and it need not obey strict logical deduction. In particular if the statement is about your psychological state then there is no guarantee that you won't be surprised to be executed on the last day. Any demonstration that you wouldn't be surprised would be self-defeating here.
Conversly if we take the judge to be saying some precisce and formulizeable then by Fitch's proof we get a contradition. Thus we CAN'T assume the judge is infallible.
In effect in the second case you are asking, 'but what if an infallible agent says 'A and not A'. The assumption is self-contradictory so there is no problem.
In other words I think what makes this problem seem so hard is that there are two points that need to be clarified. The first is the fully formal apparent paradox and the second is the confusion between surprise and deducibility.
I agree with the emotional state part - that's a dead end. I do not agree with your statement that any attempt to formalize the judge's comment results in a contradiction. Certain formulations result in a contradiction. Those aren't the only formulations, or the most interesting.
Let me be more precise. Fitch's proof is fairly boring. It just reiterates the man's failed logic using formal notation. The man's logic leads him to conclude that the judge has uttered a contradiction; Fitch's proof does the same.
That's a pretty satisfying solution to the paradox: the judge said something meaningless, and the man figured out it was meaningless. The fact that he got hung anyway (and was surprised) is irrelevant.
But it's not totally satisfying, since what the judge said turns out to be true. That's what makes it a paradox - the judge's statement seems like a contradiction but actually it's true. Perhaps the man (and Fitch) both failed to properly formalize the logic behind the judge's statement.
Then the question becomes, what is the proper formalization of the statement?
It turns on the formalization of "surprise". Both the man and Fitch take it to mean, "unable to deduce the day of the hanging". The subtlty is that you can still be surprised to get hung even after deducing the day of the hanging. So, "surprise" needs to be formalized differently than the man or Fitch have done.
The prisoner returns to his cell and hangs himself. Thus, he is not executed on one of the next five days, nor is he surprised. The end result is the same, but the prisoner has the satisfaction of cheating the judge.
For example, let's assume that the prisoner writes down his idea of the day on which he will be executed immediately upon hearing the sentence. He may also state that he will not be executed. He keeps his answer secret from the judge. If the actual execution date then differs from that written down by the prisoner, we can say that he has been "surprised". In this rendering of "surprise", we see that the judge cannot reasonably claim that the prisoner will be surprised, since the prisoner may well hit upon the correct day in what he has written down.
We could adopt another rendering of "surprise". The prisoner writes down at the start of each day whether he will be executed on that day. The prisoner's paper is kept secret from the judge. The prisoner is allowed to change his opinion from day to day. If the actual execution takes place on a day when the prisoner has written that it will not take place, the prisoner is regarded as being surprised. In this rendering of "surprise", the prisoner can simply write at the start of each day that he will be executed on that day (since he is allowed to change his opinion each time). Thus, the judge will be shown to have made a counter-factual statement.
Other ways of formalizing the game are possible. All eliminate the paradox.
Was she surprised when he gave her the diamond necklace?
In mignth have been a surprise if he strangled her with the necklace.
This fact is surprising.
This limitation bothers some people, but it makes the universe a more interesting place.
I don't think you've given a fair statement of Godel's Incompleteness Theorem. What he showed was that,in any system of first order logic that is powerful enough to contain statements of basic arithmetic, it will be possible to create well formed statements which cannot be proven.
In fact he did this using formal logic which was self-referential. That's exactly what the Godel number is. It would be odd to say that he proved you can't use formal logic in such a system, since that is exactly what he did.