Register to reply

Mathematical Induction

by Galileo
Tags: induction, mathematical
Share this thread:
Galileo
#1
Jul29-04, 04:43 AM
Sci Advisor
HW Helper
Galileo's Avatar
P: 2,002
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.)
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
NateTG
#2
Jul29-04, 12:54 PM
Sci Advisor
HW Helper
P: 2,537
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
#3
Jul29-04, 03:12 PM
Astronomy
Sci Advisor
PF Gold
marcus's Avatar
P: 23,232
Quote Quote by Galileo
Here's an unsolved problem I found in my Algebra book.
See if you can spot where the error in reasoning lies:
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
#4
Jul29-04, 04:02 PM
Sci Advisor
HW Helper
Galileo's Avatar
P: 2,002
Mathematical Induction

Quote Quote by 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)
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

(also I believe that in Netherlands there is no capital punishment so
how do you have it in your Algebra book?)
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
#5
Jul29-04, 06:20 PM
P: 1,367
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
#6
Jul29-04, 06:47 PM
Astronomy
Sci Advisor
PF Gold
marcus's Avatar
P: 23,232
Quote Quote by Galileo
...


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...
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
#7
Jul30-04, 02:56 AM
Sci Advisor
HW Helper
Galileo's Avatar
P: 2,002
Quote Quote by 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.
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
#8
Jul31-04, 09:38 AM
P: 646
Quote Quote by Galileo
.................... 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, .............
Unfortunate assumption .... he thinks he will survive till jan 30 .... so his P(0) fails. (hmm what an example of circular induction )
Galileo
#9
Jul31-04, 01:44 PM
Sci Advisor
HW Helper
Galileo's Avatar
P: 2,002
Quote Quote by TenaliRaman
Unfortunate assumption .... he thinks he will survive till jan 30 .... so his P(0) fails.
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
#10
Jul31-04, 05:43 PM
P: 1,367
Quote Quote by Galileo
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.
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
#11
Aug1-04, 03:26 AM
Sci Advisor
HW Helper
Galileo's Avatar
P: 2,002
Quote Quote by e(ho0n3
Are you convinced?
Yes

For P(k) to be true P(m) must be true for m>k. The reasoning is indeed circular.
Thanks
NateTG
#12
Aug2-04, 12:49 PM
Sci Advisor
HW Helper
P: 2,537
Quote Quote by 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?
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
#13
Aug2-04, 09:26 PM
P: 646
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
#14
Aug3-04, 10:03 PM
ExtravagantDreams's Avatar
P: 83
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
#15
Aug5-04, 12:38 PM
Sci Advisor
HW Helper
P: 2,537
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
#16
Aug5-04, 06:44 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,155
<recovering from severe blow to head > Whaa ???


Register to reply

Related Discussions
Mathematical induction Math & Science Software 2
Mathematical Induction Math & Science Software 3
Mathematical Induction Math & Science Software 4
Mathematical Induction Math & Science Software 9
Mathematical induction Math & Science Software 2