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:
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.

But that opens up another problem. How should we reason if we find ourselves in the role of the prisoner (in the sense of entertaining something apparently true from an external perspective but which gives rise to contradictions when we reason about it, not in the sense of being condemned to death)? Should we just embrace the contradictions and thus conclude that everything is the case as classical logic would imply? Clearly that seems absurd. Obviously one way out is to reject the claim that if we can conclude something deductively that we necessarily know it. And that is probably correct, as the case discussed here shows. But the problem can still arise if we are told that, for example, we won’t be executed on any day where we can deduce without contradiction that we will be executed. There are probably many ways of overcoming this problem, but allow me to put forward an idea that I have mentioned on several occasions already, that certain predicates which appear classical at first glance may really be partial truth predicates (partial functions, often invoked in discussions of computability, that yield truth values). The case we are considering then is simply one where that predicate doesn’t yield a value for, given that if we assume it to yield a value contradictions arise (we can’t assume that it yields false, that the fact we will be executed can’t be deduced, since we have just deduced it, but neither can we assume that it yields true since if it did then contradictions would arise, contradicting the claim that we could deduce that fact without contradiction). And thus no contradictions arise, and we can reason classically without coming to the conclusion that everything is the case. (I would also “cancel out” the kings assertion, meaning that we would reason the same way about when we would be executed no matter whether he makes the assertion or not. Which is more evidence that this is a satisfactory way of approaching the problem, since the king’s assertion doesn’t actually add more information from which we might reach new conclusions.)

Blog at WordPress.com.