Mathematical Induction

Galileo

Here's an unsolved problem I found in my Algebra book.
See if you can spot where the error in reasoning lies:

A serial killer is sentenced to be executed.
He asks the judge not to let him know the day of the exectuion.
The judge says: "I sentence you to be executed at 10 A.M. some
day of this coming January, but I promise that you will not be aware
that you are being executed that day untill they come to get you
at 8 A.M." The killer goes to his cell and proceeds to prove, as follows,
that he can't be executed in January.

Let P(n) be the statement that I can't be executed on January (31-n).
I want to prove P(n) for [itex]0 \leq n \leq 30[/itex]. Now I can't be
executed on January 31, for since that is the last day of the month
and I am to be executed that month, I would know that was the day
before 8 A.M. (when they wouldn'y come to get me), contrary to the judge's sentence. Thus P(0) is true.
Suppose that P(m) is true for [itex]0\leq m \leq k[/itex], where [itex]k\leq 29[/itex]. That is, suppose I can't be executed on January (31-k) through
January 31. Then January (31-k-1) must be the last possible day for
execution, and I would be aware that was the day before 8 A.M. contrary
to the judge's sentence. Thus I can't be executed on January (31-(k+1)),
so P(k+1) is true. Therefore I can't be executed in January.
(Of course, the serial killer was executed on January 17.)

NateTG

If we allow for the possibility of no execution at all in January, then the entire argument fails, since on Jan 31, the serial killer still isn't sure.

marcus

Galileo I believe that the error in reasoning is with the Judge!
He cannot logically make such a promise to the prisoner.

(in my humble opinion and with all due respect for the Judge)

(also I believe that in Netherlands there is no capital punishment so
how do you have it in your Algebra book?)

Galileo

Hehe, sounds like the logic beat common sense. There goes the system

The error in reasoning (if there is one) is definitely in the induction step.
His claim that he cannot be executed on Januray 31 is true. But saying
that he would know on January 29 that he would be executed
on January 30 because it cannot happen on January 31 sounds fishy.
Sounds like he's reasoning backward in time or something

You see, the whole reason why we can't execute people is because of
this paradox. It's in the book to convince us of how right our our system is

Ok, just kidding. There are no good dutch books on mathematics in existence. Everyone here uses books that are written in english.
This problem is from 'Linear Algebra' by Fraleigh and Beauregard.

e(ho0n3

The basic problem is P(n) is a time dependent statement. Say it's 7:00 AM, 30 January. The killer knows they will either kill him today or tomorrow. So basically P(0) and P(1) can't be decided until 8:00 AM ON THAT DATE. Thus, the whole argument is flawed. In other words, the killer can say P(0) is true only after they didn't kill him/her on 30 January.

marcus

the logic would be the same if the month of January had 2 days instead of 31. Indeed maybe in ancient times the fierce Dutch tribes dwelling in the marshlands and forest of Holland DID have exactly 2 days in their month of January. (It was because they had difficulty counting beyond this number.)

So the judge told the prisoner "I promise they will come to get you at 8AM either Jan 1 or Jan 2 and that you will not know beforehand (at 7:30 AM or anytime before they appear) that they are coming that day."

The judge has made a mistake and he cannot make good on his promise.

This was also true among the ancient Swedes, whose month of January had always exactly 3 days.

Galileo

Hmmm. Not entirely convincing. He's simply reasoning by contradiction:
"Suppose I will be executed on the 31st. Then I won't be picked up the 30th
thus I would know in advance, so I can't be executed the 31st."
He can make that conclusion beforehand.

Although time dependancy does seem to play a role.

TenaliRaman

Unfortunate assumption .... he thinks he will survive till jan 30 .... so his P(0) fails. (hmm what an example of circular induction )

Galileo

Why can he not assume that? His supposition is that he will be executed on January 31. Then ofcourse he won't be executed on the other days so he'll survive 'till Jan 30.

I really can't find any error in his logic. (That doesn't mean there isn't one)

e(ho0n3

You are using P(1) to prove P(0) and this is wrong. What you are basically saying is: "Suppose P(0) = F. P(1) = T, therefore P(0) = T." Are you convinced?

Galileo

Yes

For P(k) to be true P(m) must be true for m>k. The reasoning is indeed circular.
Thanks

NateTG

Huh? How do you come up with any circularity. The argument the prisoner makes is not circular, and the induction is quite valid.

In the scenario, either the judge is fallible, or the situation is self-contradictory. At that point, either the Judge's statement is invalid, or LEM does not apply.

Let's make this a bit simpler:

If Judge says "You will be executed tomorrow, but you won't know that you'll be executed tomorrow until they come and get you." That the statement is self-contradictory is rather obvious.

TenaliRaman

ok i need to run to college now so i will finish this up pretty fast.

first of all the person is assuming that he will survive till jan 30. Then using this he proves that he wont be killed on jan 31 then he uses this to prove that he wont be killed on jan 30.

so what he has done is,
"Question:Prove that chickens don't fly?
Answer:Assume chickens don't fly. Since chickens don't fly QED..."
if u think that this proof is valid, then u live in an axiomatic system way different than mine :p :D

ExtravagantDreams

agreed

This prisoner is making an assumption on a previous assumption. Even if (s)he made it to the 29th, (s)he wouldn't know if they were going to kill him/her tomorrow or the day after until 8 am on the 30th.

This is more noticable when you say you have 10 days left. Will the prisoner die tomorrow? 3 days?

Obviously, the prisoner did not expect to die on the 17th, yet it happened.

NateTG

No, what's going on is essentially the following:

The judge says: 0=1.

The prisoner says:
The Judge knows what he's talking about so 0=1.
Now assume (by contradiction) that I will be killed.
But we know that 1!=0 so the assumption must be false.
Therefore I will not be killed.

Gokul43201

<recovering from severe blow to head > Whaa ???