3 ms·

Hmm, I think there is a more basic error here. If you remove an element from your set of n + 1 horses, you get different sets of n horses depending on which on

Hmm, I think there is a more basic error here. If you remove an element from your set of n + 1 horses, you get different sets of n horses depending on which one you take out. Here's where the mistake is: "Consider any set H of n+1 horses. We may pick a horse at random, h_1 in H, and remove it from the set, getting a set of n horses. By the inductive hypothesis, all of the n remaining horses are the same color. On the other hand, if we remove a different horse h_2 in H, we again get a set of n horses which are all the same color. Let us call this color “brown,” just to give it a name. In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. Hence, all horses in H are brown." Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another. The ambiguity lies in the English phrase "same color" which can be interpreted in two different ways. It could mean "uniform color within the set of n horses" or "uniform across every set of n horses".

SamBam 5y ago
Consider if it were true that, for any set of 3 horses, they were all the same color (within the set of three). This would mean it would be impossible to have a set of 3 brown horses and a white horse hanging around. Why? Because if you added the white horse to the group and removed another horse, then you wouldn't have a group of three of the same color. So this would contradict our assumption. So, if our assumption at top is true, it can only be true if all horses are the same color. That's all that the original proof is saying, only stated slightly differently. It's saying that the only way the hypothesis could be true for N is if it's also true for N + 1.
shkkmo 5y ago
Edit: You seem to have deleted the part I was responding to. Here's a new response: > Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another. This part of the proof happens sneakily here: >> But when we removed h_1, we got that all the remaining horses had the same color as h_2. The sneaky part is 'all the remaining horses' which does allow you to prove they're all the same color if the number of "remaining horses" is > 0. This is where the inductive step sneaks in the n>=2 assumption. Original: > The base case is the former but the inductive step appears to be assuming the latter The inductive step doesn't make that assumption. What it does do is assume that n>=2. The step basically says: from a set s1 of n+1 horses, remove horse h1 (this assumes n>=0). This gives you a set s2 of n horses, and we already know that all sets of n horses have horses of one color. Now take the original set of n+1 horses and remove a different horse (h1<>h2 assumes n>=1), leaving a set s2 of n horses, which we again already know are all same color. Now assume that there is yet another horse h3 (h1<>h2<>h3 assumes n>=2) that is in the original set s1. Since h3 is in s2 with h1 and in s3 with h2, h3 is the same color as h1 and h2. Since h3 is any arbitrary member of s1 besides h1 and h2 we know that all members of s1 are the same color. Thus the inductive rule is indeed valid for every n≥2. If you can ever prove that every pair from a horse population has the same color you have also shown that every size of sets of horses from that population will also all have the same color.
vecter 5y ago
You can conclude that H - {h1} and H - {h2} share the same color with each other because (assuming n >= 2), there will be a third horse h3 in both those sets. Therefore by transitivity, these two sets must have the same color. This is implied and not explicitly stated, so it could be clarified.

SamBam 5y ago

Consider if it were true that, for any set of 3 horses, they were all the same color (within the set of three). This would mean it would be impossible to have a set of 3 brown horses and a white horse hanging around. Why? Because if you added the white horse to the group and removed another horse, then you wouldn't have a group of three of the same color. So this would contradict our assumption. So, if our assumption at top is true, it can only be true if all horses are the same color. That's all that the original proof is saying, only stated slightly differently. It's saying that the only way the hypothesis could be true for N is if it's also true for N + 1.

shkkmo 5y ago

Edit: You seem to have deleted the part I was responding to. Here's a new response: > Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another. This part of the proof happens sneakily here: >> But when we removed h_1, we got that all the remaining horses had the same color as h_2. The sneaky part is 'all the remaining horses' which does allow you to prove they're all the same color if the number of "remaining horses" is > 0. This is where the inductive step sneaks in the n>=2 assumption. Original: > The base case is the former but the inductive step appears to be assuming the latter The inductive step doesn't make that assumption. What it does do is assume that n>=2. The step basically says: from a set s1 of n+1 horses, remove horse h1 (this assumes n>=0). This gives you a set s2 of n horses, and we already know that all sets of n horses have horses of one color. Now take the original set of n+1 horses and remove a different horse (h1<>h2 assumes n>=1), leaving a set s2 of n horses, which we again already know are all same color. Now assume that there is yet another horse h3 (h1<>h2<>h3 assumes n>=2) that is in the original set s1. Since h3 is in s2 with h1 and in s3 with h2, h3 is the same color as h1 and h2. Since h3 is any arbitrary member of s1 besides h1 and h2 we know that all members of s1 are the same color. Thus the inductive rule is indeed valid for every n≥2. If you can ever prove that every pair from a horse population has the same color you have also shown that every size of sets of horses from that population will also all have the same color.

vecter 5y ago

You can conclude that H - {h1} and H - {h2} share the same color with each other because (assuming n >= 2), there will be a third horse h3 in both those sets. Therefore by transitivity, these two sets must have the same color. This is implied and not explicitly stated, so it could be clarified.