The Unexpected Hanging Paradox
The Unexpected Hanging Paradox has been described as follows:
A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to the prisoner. He will not know the day of the hanging until the executioner knocks on his cell door at noon that day.
Having reflected on his sentence, the prisoner draws the conclusion that he will escape from the hanging. His reasoning is in several parts. He begins by concluding that the “surprise hanging” can’t be on Friday, as if he hasn’t been hanged by Thursday, there is only one day left—and so it won’t be a surprise if he’s hanged on Friday. Since the judge’s sentence stipulated that the hanging would be a surprise to him, he concludes it cannot occur on Friday.
He then reasons that the surprise hanging cannot be on Thursday either, because Friday has already been eliminated and if he hasn’t been hanged by Wednesday noon, the hanging must occur on Thursday, making a Thursday hanging not a surprise either. By similar reasoning, he concludes that the hanging can also not occur on Wednesday, Tuesday or Monday. Joyfully he retires to his cell confident that the hanging will not occur at all.
The next week, the executioner knocks on the prisoner’s door at noon on Wednesday — which, despite all the above, was an utter surprise to him. Everything the judge said came true.
I first heard this paradox years ago, but only now do I think that I can provide a satisfactory account. I guess some people won’t see this as a deeply challenging problem though, as it’s quite clear that the word “unexpected” is under-defined. For example, it could mean unexpected based on the information that you have at the start or unexpected based on the information you have on a particular day or unexpected based on the day of the hanging.
We’ll consider different definitions of unexpected, which involves considering different definitions of expectected. We’ll define E* as expected based on the information that you have at the start, which we’ll further clarify as meaning that you are able to logically deduce that it must be on a particular day. Clearly, no day is expected based on definition E*, which mean that a hanging any day would be unexpected based on this information. Call this definition of unexpected U*.
Next, we’ll define E1 to mean expected based on the information you have on a day excluding the judge’s statement. On Friday, an execution will count as expected according to this definition and an execution on any other day will count as unexpected. As before we can create a definition of unexpected, U1, from E1. We do this by excluding the day that is expected according to E1. The hanging will therefore be unexpected according to U1 if it occurs according to this definition between Monday and Thursday.
Next, we define E2 to mean expected based on the information you have on a day, interpreting the judge’s statement to mean that the hanging is unexpected according to U1. The hanging occurring on Friday would be in contradiction with knowing that the hanging would unexpected according to definition U1. If the hanging occurs on Thurday, you’ll know that it’ll occur that day as it can’t occur on Friday. Again, we define U2 from E2, but this time, in addition to excluding any day where a hanging would be expected by E2, we exclude any day where the hanging would be inconsistent with the interpretation of the judge’s statement used by E2. According to this definition, the hanging will be unexpected if it occurs between Monday and Wednesday.
We can continue on in this vein. E3 is defined by taking the judge to be asserting U2, which means that the hanging can’t occur on Thursday or Friday without being inconsistent with the judge’s statement; and can’t occur on Wednesday without the prisoner being able to figure it out on Wednesday. The hanging meets the defintion of U3 if it occurs on Monday or Tuesday. We then get E4 from U3 and U4 occurs on Monday. Then E5 from U4 and U5 doesn’t occur on any day.
We can even create a chart demonstrating for each day whether the test would be unexpected if it occurred on that day:
| Definition | Mon | Tues | Weds | Thurs | Fri | |
| E* | Expected just before the judge’s announcement | U | U | U | U | U |
| U* | Complement of E* | |||||
| E1 | Expected on that day given that the judge meant U* (judge’s statement provides no useful information beyond it being that week) | U | U | U | U | E |
| U1 | Complement of E1 | |||||
| E2 | Expected on that day given that the judge meant U1 | U | U | U | E | I |
| U2 | Complement of E2 | |||||
| E3 | Expected on that day given that the judge meant U2 | U | U | E | I | I |
| U3 | Complement of E3 | |||||
| E4 | Expected on that day given that the judge meant U3 | U | E | I | I | I |
| U4 | Complement of E4 | |||||
| E5 | Expected on that day given that the judge meant U4 | E | I | I | I | I |
| U5 | Complement of E5 | |||||
| E6 | Expected on that day given that the judge meant U5 | I | I | I | I | I |
| U6 | Complement of E6 |
Key:
For row :
E: Day when the hanging would be correctly expected if the judge meant (before the announcement for E*, on the day otherwise).
U: Day when the hanging would be unexpected according to .
I: Day when being hanged on that day would be inconsistent with the judge’s statement.
Each EN was defined in terms of U(N-1). The prisoner interprets the judge to be envisioning a notion of expected E$ such that if the hanging occurs on day D, it is unexpected if the prisoner couldn’t determine on day D that it it was going to occur on day D given the knowledge that the hanging will be unexpected according to U$. Here U$ consisted of any day not expected according to E$ nor inconsistent with how E$ interpreted the judge’s statement.
Such a notion would indeed have the property that if L is the last possible day according to notion E$, that the prisoner would know on day L that the hanging would occur on that day since if it occurred on any later day it would meet notion E$. The “paradox” provided by the prisoner simply proves an impossibility result.
In my books, this is a much more satisfying solution than simply noting that the word “unexpected” is underdefined. Instead, we’ve mapped out the possibility space of such definitions and shown that the prisoner’s desire for a reflective definition can’t be met, but instead that there is inevitably some “precession” instead.
Consider an unexpected hanging without the extra days: The judge tells you “I am going to hang you on Monday, but the day of the hanging is not something you will be able to predict.”
The prisoner follows the same reasoning as in the unexpected hanging: the surprise hanging can’t be Monday, because he would then know when it is, and it’s not a surprise. The judge then hangs him on Monday, and of course it’s a surprise. In other words, the unexpected hanging paradox doesn’t require the extra days at all.
If by “surprise” you mean “can’t logically be proven”, then the judge’s statement is equivalent to “X is true, but you cannot prove X”. From that statement, everyone except you can prove X, and you cannot.
Doesn’t “A and B” imply A even if B is “you can’t prove A”?
Yes, it does. The paradox is that if you accept “A and you cannot prove A” as a premise, and logically derive A, then you arrive at a contradiction: A is true and you can prove it. By the usual laws of logic, this means that you should refute the premise. That is, conclude that the judge is lying.
But if the judge is lying, then what basis do you have for proving that A is true?
Of course, this whole argument may not apply to someone who uses a different basis for reasoning than classical logic with the Law of Excluded Middle.
I agree with resolving the paradox along these lines: the judge was simply making a false statement.
Maybe a more satisfying way to reach that conclusion is to use Gödelian machinery. Interpret the judge’s statement S as saying “there is an integer N from 1 to 5, such that for any M from 1 to 5 the statement ‘N=M’ is not provable from the statement ‘N>M-1 and S is true’ and the axioms of PA”. Since the self-reference in S happens within a nested statement about provability, S can be interpreted as a statement about integers and arithmetic, using an arithmetized definition of provability in PA, and using the diagonal lemma (quining) to get its own Gödel number. And then yup, S can be shown to be false, by an argument similar to the paradox itself.
I guess I feel the need to not only show why the judge’s statement must be false if interpreted in the manner that the prisoner interpreted it, but to also show how non-contradictory interpretations of the judge’s statement manage to be almost, but not quite reflective.
First, you unexpectedly switched from the unexpected hanging to the unexpected test in your third last paragraph :)
Second, surprise is best defined as inaccurate map, and the judge/teacher in their pronouncement assumes that the prisoner/student will not be able to come up with an accurate map. If the prisoner can come up with one, then the judge’s assertion of “it will be a surprise” will be just another inaccurate map, not the territory. The two maps cannot be both accurate given the stipulation of “surprise”.
The prisoner’s reasoning, as described, is a maximally inaccurate map.
What would be a maximally accurate map for the prisoner? That crucially depends on the mechanism the judge uses to decide on the day. If the judge rolls a five-sided fair die, then the odds are 20% on Monday, 25% by Tuesday, 33% by Wednesday, 50% by Thursday, 100% by Friday. If the judge instead flips a coin before each day, the probability is 50% each day except on Friday, when there is no coin flip and it’s 100%. If the judge instead decides that Friday is right out and rolls a 4-sided die, then it’s 25%/33%/50%/100%/0%. Maybe the judge always schedules executions on Wednesdays, and if the prisoner knows that, then the odds are 0/0/100%.
Can the prisoner construct an accurate map? Who knows, their capabilities and their knowledge of the judge are not specified in the problem statement. Either way, increased accuracy of one map can only come at the expense of the accuracy of the other map. That’s all there is to it.
“First, you unexpectedly switched from the unexpected hanging to the unexpected test in your third last paragraph :)”—fixed now
Eliezer’s ultimate ultrafinitist principle[1] that you never encounter more than two levels of meta is handy here.
I can’t remember exactly what he called it or where he posted it.
The prisoner concludes that the hanging can’t be on a monday; the chart is missing U6 with all Is.
One of the things that might confuse around this is that one can try to read it as “we will hang you if we find a surprise day to do so” or as “we will hang you and from this sentence you can not deduce when”. The hanging not happening is consistent with the former but not consistent with the latter.
I think the core of the paradox is preserved if the sentence would rather be “we will hang you tomorrow and it will be a surprise for you”. “Proof” of expecting it relies on the sentence, yet the sentence is not false.
Thanks for your suggestion. I just added U6 to the chart.
Five days is too short, but if the judge instead said you’ll die in the next month and it will be a complete surprise for you, it would be easy to execute.
Algorithm is simple, every day an executioner throws a coin. If it’s heads, prisoner lives for another day. If it’s tails, prisoner dies that day. By having 50% chance to live, if the prisoner is taken to be executed, it is a surprise for him. Now the only problem is, if by some small chance a tails wouldn’t fall in the stipulated timeframe. In the original problem, chances of that are 1⁄32. Pretty small, but non-zero. However, for 30 days it’s 10^-9, which is small enough to be pretty damn sure that the judgement will be fulfilled.