# On Philosophy

## December 18, 2007

### The Execution

Filed under: Logic — Peter @ 12:00 am

Once there was a prisoner who was condemned to die within the month. However, because of the nature of his crimes, the king, who never lied, didn’t feel this was sufficient punishment, and told the prisoner that they would only execute him on a day when he didn’t know that he would be executed, with the intent of keeping him in a state of suspense. Knowing that the prisoner reasoned as follows: clearly I can’t be killed on the last day of the month, because given that I know that I will be killed within the month I would know that I would be executed on that day, and thus, since the king never lies, I cannot be killed on that day. But neither can I be killed on the second to last day of the month, because I know that I can’t be killed on the next day, the last day, as I have just established. Thus the same reasoning that I applied to the last day applies to the second to last day as well. And in this way I can deduce that it is impossible for me to be killed on any day of the month. So the prisoner concluded that the king’s statement entailed that he wasn’t to be executed after all. Despite his deduction the king kept his word, and five days later the prisoner was executed, to his great surprise.

The puzzle then is to uncover how the prisoner’s reasoning is in error, because clearly it must be in error given that it is obvious that the prisoner can still be executed and that he won’t expect it. To do that I think we first need to put into formal terms the prisoner’s reasoning, to see if it really is as gap-free as it initially appears, or whether there is some subtle non-logical inference that constitutes an error in the prisoner’s reasoning. Let’s begin then by naming the primitive propositions.
ex will express the claim that the prisoner is executed on day x
dx will reflect the claim that the prisoner is alive on day x
Obviously then dx ↔ ~e1 ∧ ~e2 ∧ … ∧ ~ex-1, or, in other words, that if the prisoner is alive on a particular day that he hasn’t been executed on any of the previous days and that he doesn’t die of natural causes. I will refer to this as proposition (a).
Additionally e1 ∧ e2 ∧ … ∧ en reflects the fact that the prisoner will be executed some time within the next n days. I will refer to this as proposition (b).
This reflects the basic facts of the prisoner’s condition, but we haven’t captured the idea that the prisoner can know a particular fact or the king’s claim that the prisoner won’t be executed on a day that he knows he will be executed.
We can simplistically capture the claim that some proposition φ is known by asserting K(φ).
And since we are confined to logical deduction in this situation we can capture the idea that if the prisoner can deduce some fact then he knows it by asserting that φ → K(φ), which means that upon concluding φ that we can conclude that φ is known. I will refer to this as proposition (c).
The king’s assertion thus becomes K(ex) → ~ex. I will refer to this as proposition (d).

The prisoner’s reasoning is thus as follows:
suppose dn
thus ~e1 ∧ ~e2 ∧ … ∧ ~en-1 by proposition (a)
thus en by proposition (b)
thus K(en) by proposition (c)
thus ~en by proposition (d)
and now we can discharge our assumption, concluding:
dn → ~en

suppose then that dn-1
thus ~e1 ∧ ~e2 ∧ … ∧ ~en-2 by proposition (a)
thus en-1 ∨ en by proposition (b)
suppose that ~en-1
then dn by proposition (a)
but dn → ~en as established above
thus ~en
but this contradicts proposition (b)
therefore we can discharge our assumption and conclude that:
en-1
thus K(en-1) by proposition (c)
thus ~en-1 by proposition (d)
and now we can discharge our initial assumption, concluding:
dn-1 → ~en-1

And this deduction can be carried on until we can conclude that on every day that the prisoner can’t be executed. And obviously this contradicts proposition (b), that the prisoner will be executed on some day. Unfortunately this reasoning cannot be extended to ω or more days, because it result in an infinite length proof and thus we would be unable to actually conclude anything about days 1, 2, 3, and so on. Unless, that is, we allow meta-theoretic proof by induction, where we conclude that since dω → ~eω is provable and that dx-1 → ~ex-1 is provable if dx-1 → ~ex-1 is that for all y dy → ~ey holds. But of course that has nothing whatsoever to do with the topic at hand.

So, to get back to the main issue, it appears that the prisoner’s reasoning was flawless after all. But, on the other hand, it does contain contradictions, not only as a whole, but in the idea that we can conclude that something is not the case after previously concluding it to be the case. Simply imagine the prisoner’s situation if he happened to live to the last day. Given that it was the last day and he knows he must be killed on some day he can deduce that he will be killed on that day. But, given the king’s assertion, he can also conclude that he won’t be killed that day. Thus he is able to conclude both a proposition and its negation, which seems absurd. And yet all the premises are true, because, given that he believes the king, he must conclude that he won’t be executed. Therefore if the king does come to execute him on the last day he clearly won’t know about it before hand, because he has concluded that he is safe. Perhaps then the “solution” is to say that nothing can be known when contradictions can be derived, although obviously this is not something we can express in the formalism detailed above, because it is clearly incapable of discussing itself meta-theoretically.