The Unexpected Hanging Paradox

4Jiro

5Measure

3JBlack

4cousin_it

2Chris_Leong

3shminux

2Chris_Leong

2Richard_Kennaway

2Slider

4Chris_Leong

0Samuel Hapák

New Comment

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.

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

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.

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.

The Unexpected Hanging Paradox has been described as follows:

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:

Key:For row Uk:

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.