The prisoner's mistake

Here is a very subtly wrong application of induction I came across:

A prisoner has been condemned to death, and the judge tells him he will be executed at some point during the next month, which happens to be January. However, the judge refuses to fix a date, saying "I promise you that you won't know what day you are to be executed until the guards come to collect you at 8 o'clock in the morning of that day."

So the prisoner goes back to his cell and thinks this over. Firstly, he realises that he cannot possibly be executed on January 31st, because if it gets to 8:10 am on January 30th and the guards haven't come to collect him, then he will know that he is to be killed the next day (since he has to be executed in January) - but this contradicts what the judge said!

Next, he realises that he cannot be executed on January 30th, since if it gets to 8:10 am on January 29th and the guards haven't come, then since he knows they won't be coming on the 31st, they must be coming on the 30th, so he knows the day of his execution in advance and this again contradicts the judge.

Now using exactly the same reasoning, he sees he cannot be executed on the 29th, the 28th, the 27th... in fact he cannot be executed at all! The prisoner stops worrying, and is consequently rather surprised when the guards come for him on the 17th...

So where did the prisoner go wrong? This is a subtle problem, and I'm not sure I've solved it. To avoid spoiling your fun I've put my answer lower down the page.

Okay, what I think the answer is is this: the prisoner's logic is entirely correct, but the judge's statement is wrong, or at least inconsistent with the assertion that he is to be executed in January. A possible correction would be: "Either you will be executed on the 31st, or you won't know the day in advance."

Induction relies on finding a base case in which a statement is true and proving that if the statement holds for the nth item in a sequence, it holds for the successor.

In this case, the prisoner is finding a base case, then proving that the (n-1)th case is true. This is not so much the flaw. To attack the prisoner's argument, we must either attack his base-case, or his successor rule. His base case is sound, as I see it.

His successor rule is flawed: it is not inductive, but particular; that is, it is not a rule that works in general, for all pairs of successive items, but rather it only works for that instance. While, if not executed on the morning of the 30th, he knows he is done for the next morning, on the 29th he does not know which of the following days he will be executed: the 29th or 30th, and he may be executed on that day, without knowing that he will be executed that morning. Thus, the induction is broken. As time is not symmetric forwards and backwards, and the statement is that he will not have foreknowledge, to start from the future, then work back to the past is an invalid step. I could, of course, prove this using situation calculus, but that is for another day, if not another node.