- Joined
- 9/7/07
- Messages
- 220
- Points
- 28
[FONT="]Do you agree with the following inductive proof? Clearly explain why or why not.[/FONT]
Theorem:[FONT="] All horses have the same color.
[/FONT][FONT="]PROOF: Let N denote the number of horses.
[/FONT]
Initial Case:
[FONT="]Clearly with just N=1 horse, all horses -- in this group of one horse -- have the same color.[/FONT]
[FONT="]Inductive Step: [/FONT]
[FONT="](It will be shown that: If it is true for any group of N horses (in which all have the same color), then it is also true for any group of N+1 horses).[/FONT][FONT="] So, let's assume it is true for any group of N horses. Now, given any set of N+1 horses, if you remove a random horse, you get a set of N horses. By the inductive hypothesis, these N horses all have the same color. But by removing any other horse in the pack of N+1 horses, you can conclude that also in this new group of N horses, all have the same color. Since there are some horses common in both groups just considered, then both of the two removed horses must have the same color as the common horses. Therefore all N+1 horses have the same color. QED [/FONT]
[FONT="]The last bit of reasoning goes like this. Let's be concrete, and suppose we assume the case is true when N=8. That is, we assume that in ANY group of 8 horses, they all have the same color. Now consider the case N+1=9. So, remove horse #1 from the group of 9 to get a group of 8 horses. By the inductive hypothesis, these 8 horses (i.e., horses #2 through #9) must all have the same color, let's say, color red. So, in particular, horse #6 has color red. Now, put horse #1 back in and this time remove horse #9. So, we have a (different) group of 8 horses. But by the inductive hypothesis, all these horses (i.e., horses #1 through #8) have the same color. More specifically, they all have the same color as horse #6, which has color red. So, horse #1 has color red, just like all the other 8 horses. So, all the 9 horses have the same color!
[/FONT]
WHAT IS WRONG WITH THE PROOF?
[FONT="]Hint: Although the preceding concrete example is an accurate explanation of the reasoning, a superficial understanding of it is precisely where one is misled in thinking about the unsoundness of the 'proof'![/FONT]
Theorem:[FONT="] All horses have the same color.
[/FONT][FONT="]PROOF: Let N denote the number of horses.
[/FONT]
Initial Case:
[FONT="]Clearly with just N=1 horse, all horses -- in this group of one horse -- have the same color.[/FONT]
[FONT="]Inductive Step: [/FONT]
[FONT="](It will be shown that: If it is true for any group of N horses (in which all have the same color), then it is also true for any group of N+1 horses).[/FONT][FONT="] So, let's assume it is true for any group of N horses. Now, given any set of N+1 horses, if you remove a random horse, you get a set of N horses. By the inductive hypothesis, these N horses all have the same color. But by removing any other horse in the pack of N+1 horses, you can conclude that also in this new group of N horses, all have the same color. Since there are some horses common in both groups just considered, then both of the two removed horses must have the same color as the common horses. Therefore all N+1 horses have the same color. QED [/FONT]
[FONT="]The last bit of reasoning goes like this. Let's be concrete, and suppose we assume the case is true when N=8. That is, we assume that in ANY group of 8 horses, they all have the same color. Now consider the case N+1=9. So, remove horse #1 from the group of 9 to get a group of 8 horses. By the inductive hypothesis, these 8 horses (i.e., horses #2 through #9) must all have the same color, let's say, color red. So, in particular, horse #6 has color red. Now, put horse #1 back in and this time remove horse #9. So, we have a (different) group of 8 horses. But by the inductive hypothesis, all these horses (i.e., horses #1 through #8) have the same color. More specifically, they all have the same color as horse #6, which has color red. So, horse #1 has color red, just like all the other 8 horses. So, all the 9 horses have the same color!
[/FONT]
WHAT IS WRONG WITH THE PROOF?
[FONT="]Hint: Although the preceding concrete example is an accurate explanation of the reasoning, a superficial understanding of it is precisely where one is misled in thinking about the unsoundness of the 'proof'![/FONT]