Saying it's the base case that's wrong is a little weird. In general your base case can be vacuously true without any issue. However, if it is (and your goal is non-vacuously true for something), then your inductive step will require a branch in it. One side of the branch in your proof will look like a proof of a base case.
I have maybe a skewed view on this from using Coq.
The problem is that the base case is n=2, but the student checked n=0 and n=1.
Of course, you can’t prove the N=2 base case, so that’s why the argument uses the wrong base case.
H(1) is true
H(n) => H(n+1) (with a sleight of hand that it's only for n >= 2)
It seems to me like changing either the argument to assert H(2) is true, or the scope of the second statement to include n = 1, would be enough. It seems the fault of both statements equally to not fit with the other, so why is it weirder to say the base case is wrong?
One could write a completely different proof where the base case(s) cover n=1,2 and the inductive step is as in the post. In such a proof, the base case would be wrong and the inductive step would be correct. But that’s a different proof, not the one in the post.
No I'm still with eperdew on this. You don't apply an inductive argument to base cases, so that statement doesn't really make sense. From a pedagogical point of view, I think it is very important to drive home the point that there is nothing special about your choice of base case, other than that it affects the argument in your inductive step, otherwise it's too easy to make the choice of base case seem "magical."
In fact I'd go further. Whenever you have an error in an inductive argument, it is always in the inductive step and never the base case, since you can always choose whatever base case you want (you might just find it makes your inductive step impossible to prove, so if you do prove something, you've made a logical error in your inductive step).
At worst, an "error" in choice of base case leads to a proof that cannot be completed, not an erroneous proof.
EDIT: "it is always in the inductive step and never the base case" except of course if you've somehow made an error in the initial proof of the base case, but that is distinct from choosing the "wrong" base case.
EDIT 2: I just understood what you meant by "apply," (doesn't fulfill the preconditions of the inductive step, vs I thought you meant relevant to proving the base case) sure that's a reasonable way of looking at it too, but again I'm very wary of saying that it's the wrong base case that leads to proving a falsehood as I lay out elsewhere.
The problem afaics is that there is a supposition that we are talking about sets of horses with the same colour. So if you "suppose for all sets of n horses, every horse in the set has the same color" then you can prove that horses in that set have the same colour. If P then P.
"Now suppose for all sets of n horses, every horse in the set has the same color."
There is no justification for that. They then go on to talk about removing a horse from such a set, but we've already lost.
The actual problem in that proof is setting up the proofs of the inductive rule. There is an implicit assumption/condition that n+1 >= 3 that is not acknowledged.
If you acknowledge that condition, then it becomes quite clear that you can only prove a base case for n = 1 and only prove an induction rule for n >= 2 .
When you set out to prove "for any set of n horses, every horse in that set has the same color" and you then "suppose for all sets of n horses, every horse in the set has the same color" as a first step, you're messing with a tautology, aren't you? I mean if you've supposed that it's true for all, it's definitely true for any, right?
What am I missing that makes the problem subtle and interesting, rather than just blatantly circular from the start?
There is also lemma that since Alexander the Great rode a Black horse, he did not exist, but if he did exist he would have an infinite number of arms and legs
The joke is funny though
Two legs in back, and "forelegs" in front (four-legs). 2 + 4 = 6, which is a peculiar (aka odd) number of legs for a horse to have. Thus horses have both odd and even number of legs, meaning horses have infinite legs.
Can someone explain in English how the author goes from "[now] suppose for all sets of n horses, every horse in the set has the same color" to 'proving' anything?
Finally, you prove that any arbitrary number (say, 1) has the property in another way, and you've proven that property for all N greater than or equal to 1.
The error in the proof is explained in the linked page, but basically the problem is that the proof that N implies N+1 doesn't actually work for all N, and particularly it doesn't let us go from 1 to 2.
The problem in the proof is that the inductive step P(n) implies P(n+1) only holds for n >= 3, and so the fact that P(1) is true does not imply anything for the larger integers.
But: if you skip a pair of horses (which is how the trick is done/the error introduced) it might be:
Assume any group of 3 horses are the same colour. Can we show that adding another horse will result in a group of horses that are all the same colour?
Well yes: take your new group of 4 horses, and extract 1. (h1). Three horses remain and they must by definition be the same colour. Put h1 back and extract a different horse (h2). Now three remain and must by definition be the same colour as each other.
But when h2 was out, h1 was part of a group that was all the same colour. And when h1 was out, h2 was part of a group that was all the same colour. Therefore they must all be the same colour. It doesn’t matter how many different horses you find and bring to your initial group of 3, the rules will mean the resulting group of 4 is always the same colour. And so it is true for a group of 4 horses.
By the same reasoning, it must then be true for a group of 5, and so on up to all horses.
So all horses are the same colour, so long as the first assumption (that any group of 3 horses must be the same colour) holds.
The trick/error is jumping from “a group of 1 horses must all be the same colour” to “a group of 3 horses must be the same colour” which is an easy jump to miss if you go from “1” to “n”, instead of “1” to “3”.
(The logic doesn’t work for a pair of horses, because once h1 is taken out there are no other horses left that h2 must be the same colour as.)
This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not n=1, but rather n=2. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.
I think the fallacy is explained better there tbh.
I also think it’s confusing to say one isn’t the base case. When you apply the inductive step there you hit N=2, and indeed the step fails because there’s no overlap.
I agree this is much more worth looking at.
Yes, iff n horses have the same color. I fail to see any paradox here (and in subj tfa too) and why induction is of any importance to it. We worked it all out of a restricting assumption which wasn’t contradicted, but that’s it. It doesn’t tell us anything about all other cases, e.g. when n horses do not have the same color.
Can someone please explain what I’m missing here?
But actually that's part the power of the inductive step: you do have the freedom to choose whatever assumptions you want. The question is whether it's true for N+1, for all N. In this case, it's not: the inductive step fails. But there's nothing flawed with the starting premise per se (aside from it being intuitively obvious that it will never work). The interest here is that it seems you can get further than you should be able to, and it's a little tricky to figure out where the logic falls apart.
If the induction actually was valid for 1->2, we'd have a hell of a problem.
Edit: I removed the wrong. It’s just confusing.
The actual error is is a logic error in the proof of the inductive rules that takes a logical step that only holds for n>=2 but doesn't acknowledge that condition. If that logical step is done properly and the condition made explicit, it is clear that a base case of n=1 won't prove anything with that inductive rule that only applies to n>=2.
> Now [assume that] for all sets of n horses, every horse in [each] set has the same color.
QED.
This is just tautology. No further analysis needed, really.
(If your proof includes your hypothesis as an assumption, then it must be a proof by contradiction.)
EDIT: Before you refute, read again carefully. The assumption _is_ the hypothesis. It is not existentially quantified or set in the base case. It is the entire, universally quantified hypothesis.
The flaw is that the second part of the proof requires n >= 2
The proof is showing that it is true for n=1, and then showing that if it is true for n (the part where we "suppose it is") then it is true for n+1, proving by induction that it is true for all n >= 1.
"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".
> 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.
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.
This is implied and not explicitly stated, so it could be clarified.
This sounds so obviously false to me, that I initially thought that he must have meant "now suppose for all sets of n horses such that every horse in the set has the same color". I.e. take all sets of n horses and then filter them to only get the uniformly colored sets.
But he doesn't mean that, it is meant as the induction step:
"Now suppose a world where for all _possible_ sets of n horses, it turns out that every horse in the set _necessarily_ has the same color."
In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.
It might help to make it more concrete, to say “assume that we've proven this for say n = 3, all sets of three horses have the same color. Then I can prove it’s true for n+1, because my set {Auris, Brunellus, Camper, Diego} of four horses is the union of two overlapping 3-sets, {Auris, Brunellus, Camper} and {Brunellus, Camper, Diego}. By the transitive property, Diego must have the same color as Auris and the result holds. But obviously this works not just for 3 going to 4, but also 4 going to 5... Any set of size n+1 is made up of two overlapping sets of size n.”
Maybe also someone can then intuit that the wool is being pulled over their eyes in this step?
> In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.
That is the point. This example is given to first year students to show them why you need to be careful in your proofs and why properly wording/formulating statements is important.
>Now suppose for all sets of n horses, every horse in the set has the same color.
"We will prove that $thing is true. Step 1: assume $thing is true"
I guess I don't see what the big deal is. Of course you can befuddle someone if they don't carefully read what you wrote.
Example: prove that a tree of size n has exactly n-1 edges.
This is an error. h1 and h2 don’t have to be the same by any previous conclusions. If you have two horses, white and brown, it’s true to say if we remove one or another that “all horses that are left are same colour”, but they by no means need to be of same colour between themselves.
Because for any event or proposition it will either happen or not happen, two possible states. And you figure probabilities from the canonical fair coin and come up with two states & a 50/50 chance of either one coming up. So the proposition "A giant meteor will hit the Earth tomorrow" will either happen or not happen, so there's a 50/50 chance of a global extinction event tomorrow.
A while back in Sweden some fella started a movement which argued that horses are in fact a fruit that does not exist. It became a quite popular meme and the founder was even interviewed on national television. (Yes, really.) When asked how a horse could possibly be a fruit that doesn't exist, he likened them to dragons. See, dragons are a kind of lizard, but they're also just a figment of our imagination and so therefore can not possibly exist. Horses are the same except they're a fruit, and they don't exist. He presented this argument with a straight face in the middle of a riding school with horses in the background, leaving the interviewer dumbfounded. It was a glorious and hilarious moment in Swedish television history.
> 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.
Right, but for transitivity you actually need there to be a third horse to connect h_1 and h_2. i.e. for this logical chain, you need "all the remaining horses" to be a non-empty set.
But that is clearly not true if I have a set of n horses, n-1 out of which are black and one is brown. So the premise is already wrong.
To diagnose the problem with the proof, it’s worth knowing why proof by induction works, to thereby know how it actually works, and then diagnose which part of how it’s meant to be executed isn’t actually being executed in this blog post.
We need a starting point. For natural numbers, that’s Peano arithmetic. For simplicity, Peano arithmetic says that for any unary predicate P, the following is axiomatic:
If
P(1)
And
For all n > 0, P(n) => P(n+1)
Then
For all n > 0, P(n)
Proof by induction involves formulating your hypothesis in the form “For all n > 0, P(n)”, then proving the two conjuncts “P(1)” and “For all n > 0, P(n) => P(n+1)”, and finally concluding your hypothesis by modus applied to the inductive Peano axiom for P.
In this case:
P(n) is “in all sets of horses of size n, all the horses in the set are the same color”
The first conjunct, P(1), generally referred to as the base case, is true, and correctly recognized as such in the blog post.
The second conjunct, “For all n > 0, P(n) => P(n+1)”, generally referred to as eg inductive case, is false for this P.
It’s not about “would the inductive case be true if the base case were different”. There is a single proof presented in the article. It has a base case which is a true statement, and an inductive case which is a false statement. So the problem is the inductive case.
You could have a different proof which, reformulating the Peano axioms a little, could look like:
Base: P(1) and P(2)
Inductive: For all n > 1, P(n) => P(n+1)
In this different proof, let’s call this Proof 2, the base case would be false and the inductive case would be true.
Maybe the author is not intending to say the base case is “wrong” in that is false, but that is “wrong” in that it should have been formulated as in Proof 2, and that the inductive case is valid when interpreted in the sense of Proof 2. But this is completely confused. Why would it have been better for the proof presented in the article be interpreted as a proof (Proof 2) that’s not presented in the article? Both proofs fail, neither is a “better” formulation.
Rather than saying: the proof presented in the article should instead have be formulated in a superficially different but fundamentally equally invalid way, under which formulation the base case would be wrong.
Let’s just say: the inductive case of the proof presented in the article is false.
Once you get beyond the surface of the problem things are simple. and tasty.
