The Paradox of the Lying Judge

In the discussions of the pirate puzzle an interesting point was raised when Robert Murphy of Texas Tech mused¹ that there may be an analogy to what is conventionally called the Paradox of the Unexpected Hanging.

For a description of that paradox, let me quote Murphy quoting the much-missed Martin Gardner. The puzzle involves a man sentenced to death:

The man was sentenced on Saturday. The hanging will take place at noon, said the judge to the prisoner, on one of the seven days of next week. But you will not know which day it is until you are so informed on the morning of the day of the hanging.

The judge was known to be a man who always kept his word. The prisoner, accompanied by his lawyer, went back to his cell. As soon as the two men were alone the lawyer broke into a grin. Don't you see? he exclaimed. The judge's sentence cannot possibly be carried out.

I don't see, said the prisoner.

Let me explain. They obviously can't hang you next Saturday. Saturday is the last day of the week. On Friday afternoon you would still be alive and you would know with absolute certainty that the hanging would be on Saturday. You would know this before you were told so on Saturday morning. That would violate the judge's decree.

True, said the prisoner.

Saturday then is positively ruled out, continued the lawyer. This leaves Friday as the last day they can hang you. But they can't hang you on Friday because by Thursday afternoon only two days would remain: Friday and Saturday. Since Saturday is not a possible day, the hanging would have to be on Friday. Your knowledge of that fact would violate the judge's decree again. So Friday is out. This leaves Thursday as the last possible day. But Thursday is out because if you're alive Wednesday afternoon, you'll know that Thursday is to be the day.

I get it, said the prisoner, who was beginning to feel much better. In exactly the same way I can rule out Wednesday, Tuesday and Monday. That leaves only tomorrow. But they can't hang me tomorrow because I know it today!

Then Thursday arrives and the man is hanged, quite unexpectedly.

The lawyer's reasoning above, similarly to the solution of the pirate puzzle, involves backward induction.² This, Murphy suggests that there is something fishy above backward induction and it may not be a valid mode of reasoning in many cases, including analysis of the iterated prisoner's dilemma.

Here, I think, Murphy errs. For the proper conclusion is not that there is anything wrong with the lawyer's reasoning, but that the judge is lying (or, more charitably, mistaken).

A system of premises, like the judge's statements or a mathematical system, can be internally contradictory. In some cases, that may be obvious on its face. For example, the judge might have said You will not be hanged. And, also, you will be hanged on Thursday. In that case, anybody who accepted either of the two statements would not be committing an error of logic. Rather, the fault lies with the judge for making contradictory claims and hence lying.

But the contradiction in premises can be so subtle and to prove that a system of premises is contradictory is equivalent in difficulty to proving or disproving any proposition from the premises.⁴ Hence, contradictory system of premises can be studied for a long period of time, producing a large number of useful results and without finding the contradiction. Examples, real and hypothetical, abound.

The Pythagoreans held as one of their premises that all real numbers are rational. From these premises they deduced many useful and accurate results. But then a clever fellow proved from these premises that some clearly real numbers, like \(\sqrt{2}\), cannot be rational. So the Pythagorean's premises implied the contradiction that all real numbers are rational and that some real numbers are not rational. Their response, just like Murphy's, was that there must be something wrong with the proof and reportedly killed the clever fellow.⁵

If Euclid had practiced mathematics in a system which, in addition to the Peano axioms also included the premise that there are only finitely many primes, his proof of their infinity would have led to a contradiction. If our premises had included, expressly or by implication, that the Poincaré conjecture was false, then nobody could have shown that there was anything amiss with them until 2003, when the Poincaré conjecture was proven.

In each of these cases, the discovery of a contradiction by valid deduction from premises does not call into doubt the validity of the deduction. It calls into doubt the validity of the premises.

So it is for the paradox. While the judge may have been known to be a man who always kept his word, he was stating an implicit contradiction and hence lying (or mistaken). That the events in the particular instance seem to conform to the judge's statements does not prove that they were non-contradictory; any more than the Pythagoreans many valid deductions established the internal consistency of their premises.

¹ More than one other commenter were independently put in mind of the same analogy.

² Of course, in principle there is no real difference between mathematical backward and forward induction³ and, in so far as there is, the solution of the pirate puzzle arguably performs mathematical forward induction, reasoning from the \(n\) pirate case to the \(n+1\) pirate case. But the analogy of reasoning between the puzzle and the paradox is still undeniable.

³ Adding to the confusion is the fact that what is called mathematical induction is, in the more general sense of the word, not induction, but deduction, just like all mathematical reasoning.

⁴ Indeed, the common and useful technique of proof by contradiction proves proposition \(p\) by adding its negation \(\neg p\) to the premises and deducing a contradiction.

⁵ One trusts that Murphy is not proposing as harsh practical consequences for errant backward-inducers.