You're 100% correct. I would be more unequivocal -- saying that the problem is the base case isn't just a little weird, it is incorrect. Your analysis nails it.
Disagree. The induction step works perfectly fine for n>=2. In particular, if you can give me the base case "any two horses have the same color", then this proof works and all horses have the same color.
The problem is that the base case is n=2, but the student checked n=0 and n=1.
We don't even disagree about anything here....
We both say "P(n) => P(n+1)" does not work for n=1, but does work for n>1.
I would like to give the student partial credit for the "works for n>1" part and deduct points for the missing n=1 case.
The two obvious ways to "fix" that are either giving a proof for "P(1)=>P(2)" (which is currently missing) or establishing P(2) another way and then using induction. Both are fixes of the same thing and not at all "completely different".
The proof has errors, there is no fixing it, you can't prove that all horses have the same color given no data about horses. In this proof the base statement is 100% correct, in all sets of 1 horse all horses will have the same color. Hence the error has to be in the other part.
If a student was tasked with proving that all horses has the same color given no information about horses then the correct answer is "I can't prove this", the answer given in this article would give 0 points since the student obviously doesn't understand what they are doing. When you check that test, would you mark the base case as the source of the error of the proof, or would you mark the inductive step? The base case is correct, if you marked that part wrong the student would rightfully complain, their logic works there.
The base case is proven correctly, the inductive rules is proven OK except that the transitive set rule they invoke requires n>1
As such, the only data you would need yo prove that all sets of horses are the same color is that all pairs of horses are the same color.
I think zero points would be a very harsh grade given that an understanding of how to do an inductive proof was demonstrated and one minor error was made in an otherwise correct proof.
> I think zero points would be a very harsh grade given that an understanding of how to do an inductive proof was demonstrated and one minor error was made in an otherwise correct proof.
Who says the question was to demonstrate an inductive proof? Being able to prove that all horses are the same color if all pairs of horses are the same color isn't particularly useful, as typically that would be the definition of all horses having the same color. All that humbug didn't add any extra information to the problem at all, it didn't make things clearer it just made them harder to understand.
> You mean to tell me that horses are actually different colors? Really? /s
Right, the goal here is to find the logical error in an obviously wrong proof, not how to fix this proof as the proof is obviously wrong from the start. You trying to argue how to "fix" it is the one side-tracking the whole thing.
If you say "B wouldn't be wrong if you changed A, so A is wrong!" then that isn't how you find errors. If A is a correct statement and B is an incorrect statement then B is the wrong statement. If you can make B correct by changing A, then B is still an incorrect statement.
If this was a memorization question where you were supposed to find a particular A and B, then you could say that A is wrong even if the statement is correct, since you knew what A and B are supposed to be. But it isn't, we are just here to find the error in the statement to prove that the proof is wrong, we aren't here trying to find a correct version of this statement.
Their inductive step is perfectly valid. However, requires a group of horses with one removed to still have a horse remaining. Using N=1 is an incorrect base case. Had they proved the N=2 base case, their entire argument would work.
Of course, you can’t prove the N=2 base case, so that’s why the argument uses the wrong base case.
The inductive step introduces a premise that “requires a group of horses with one removed to still have a horse remaining.” It is not valid to introduce this premise. The inductive step is not valid.
I mean “valid” in the mathematical/logical sense. It does not follow from the stated assumptions that n > 1, in the inductive step is this proof.
This has nothing to do with the idea that it can be common practice to prove claims of the form for all n > N, P(n) by induction when N is a number like 4. Yes there is a perfectly valid way to use proof by induction to do such proofs. Has nothing to do with this blog post.
In a proof, you can absolutely assume something like "A is true", you do it as a part of a sub-proof. Then anything you prove in the sub-proof like "B is true" can be brought back into the main proof in the form: A implies B is true.
The blog post glosses over this assumption and thus ends up concluding "p(n) implies p(n+1)" instead of "p(n) implies (n>1 implies p(n+1))”
Nah, the inductive step is simply incorrect. For it to be correct it needs to say "for n > 1 the following is true", but it doesn't, the statement isn't true since they forgot to add that part. And if you added "for n > 1" to make the inductive statement correct then it is obvious where the reasoning goes wrong.
In other words, the base case is correct, in all sets of 1 horse all horses has the same color. The inductive step is not correct. Even if you changed the where you put the base case to N=2, the inductive steps reasoning is still wrong as long as it doesn't include the "for n > 1" part.
You wouldn't need to add "for n > 2" to the inductive step, any more than you need to include "for n > 1" for arguments where the base step is 1, or "for n > 20" for arguments where the base step is 20.
You need to do it because you prove the statements separately. Currently the inductive step statement is false, it says that applies for all sets. It doesn't.
Note that you can use false intermediate steps like that and still reach a correct conclusion. Then the conclusion is correct but the proof is still wrong since the steps you used were wrong.
The “vacuously true” part seems unnecessary (and weirdly subjective). The N=1 base case requires considering N=2 when you apply the inductive step and that fails.
The example I'm about to give is overkill, but I'm trying to make my point very carefully.
Suppose you want to prove something for integers >= 2. E.g., suppose you want to prove for all n >= 2, n is positive. The statement you're trying to prove for a given n is actually
P(n) := n >= 2 -> n is positive
Let's prove it by induction.
P(0) is 0 >= 2 -> 0 is positive. P(0) is vacuously true, because 0 < 2.
Suppose P(n). We want to show P(n + 1). Our goal is
n + 1 >= 2 -> n + 1 is positive. Let's break this into the cases n >= 2 and n < 2.
For n >= 2, we assume P(n) and have the LHS of the implies. This gives us n is positive. Say by definition or by a lemma that n positive -> n + 1 is positive, and we handle this branch.
For n < 2, the inductive hypothesis tells us nothing. Assume the LHS of our goal, i.e. n + 1 >= 2. We want to prove n + 1 is positive. Well 2 is positive and therefore n + 1 is positive by transitivity.
This is what I mean by the base case not being special. E.g., in Coq, induction over the natural numbers always starts at 0. When you think about doing induction starting at another number, you're transforming your goal to include something of the form n >= m -> P(n).
> E.g., in Coq, induction over the natural numbers always starts at 0. When you think about doing induction starting at another number, you're transforming your goal to include something of the form n >= m -> P(n).
The concept of a “minimal base case” really weirded me out but I couldn’t quite put my finger on why. Thanks for the painstaking explanation, this was perspective-broadening.
But does this do anything meaningful, or is it just pointless drudgery because Coq is a machine and can't 'understand'/assume even simple maths/logic if it isn't explicitly stated? This is not a slight on Coq by any means, just pointing out the difference between human proofs and machine proofs. (Humans can of course be tricked into thinking that subtly false statements are trivially true, which the much more meticulous machine proof would discover)
That is, what is being gained by looking at the vacuously true cases where n<2, when the only interesting base case is the one where the LHS of the implication is true?
I wrote out quite a bit for this, but I think that the main point is that by falling back to the formalism, we see the the LHS of the implication affects our inductive hypothesis. I think this is something that is not clear if you just do "base case starting at n" style proofs."
As far as drudgery, Coq will solve the trivial cases automatically, so you'd never have to prove the n = 0 case by hand. That said, there's a reason most math is done on paper and not in Coq - there's usually an order of magnitude more detail and drudgery in a formal proof, even with automation.
The problem is that the base case is n=2, but the student checked n=0 and n=1.