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?
That's absurd. Anyone who's ever seen a field with horses in it would trivially know that this is a faulty assumption to make.
You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate".
It's equally valid logic.
because that's how inductive proofs work. You assume something is true for N and show that this implies that it's also true for N+1. This combined with base case (for example for N=1) proves that it's true for all N >= 1.
The assumption is just a tool used to check if you can prove the implication, the real "meat" of the proof is in the implication.
Are you aware of proofs by contradiction? A: "assume N is the largest natural number". If that's true then there shouldn't be any natural numbers larger than N, but we can create N+1 and show it's larger AND natural, so assumption A leads to contradiction, so there is no such thing as the largest natural number.
We used false assumption in our proof, but the proof was correct.
It's a similar idea with inductive proofs - you make an assumption and see where it leads you. You don't use the assumption for the proof, you use the implication A(N)=> A(N+1) for the proof, the assumption A is just a way to see if you can prove the implication.
> You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate". It's equally valid logic.
The logic isn't actually circular, your coconut analogy is wrong. Correct analogy would be:
"when we assume N coconuts can migrate we can formally show that it implies N+1 coconuts can migrate" + "we can show that 1 coconut can migrate". You only need these 2 facts to prove all coconuts can migrate.
But beyond that, in mathematical logic, for p -> q, you can still prove this to be true, even if p is false. In fact, if you can prove p is always false, p -> q is 'vacuously true' - it's true because you can never come up with an example of 'p and not q'.
So mathematically, there's no problem with assuming an induction hypothesis that's actually false here. The real problem occurs is that the result doesn't follow from the assumption because the induction step of the 'proof' sneakily assumes that n >= 3, i.e., the induction step simply doesn't work for the n = 2 case.
You don't get to assume the thing you're trying to prove is true as a part of the proof that it's true. The only time we assume something like that is in a proof by contradiction, where the contradiction implies either an error in our logic, or an error in the assumptions.
1) Prove H(0)
2) Prove that if H(n), then H(n+1)
Then, by the axiom of induction, this is proven for all positive integer values of n. Because if those two conditions hold, we would have
H(0) is true
H(1) is true because H(0) -> H(1) ((2) with n=0) and H(0)
H(2) is true because H(1) -> H(2) ((2) with n=1) and H(1)
and so on.
The assumption isn't what's being proven, it's proving the inductive hypothesis for the next integer.
one is proving the inductive rule that: p(n) implies p(n+1)
the other is proving that there exists some number i for which p(i) is true. This, combined with the proof of the inductive rule, allows you to prove that p(n) is true for all n >= i.
1. There exists some number of horses where all horses are of the same color. This is obviously true when you have 1 horse.
2. The second step is that you have to prove that if you have some number of horses n, and they are all of the same color, then if you add another horse all the horses are of the same color.
He's saying there is some set of n+1 horses, n of which are of the same color. Then he makes the (false) claim that removing one horse at random leaves you with n horses, which therefore must all be of the same color. This is incorrect because the assumption is that there is a set of n horses, not "if you have n number of horses they are all the same color.
The base case of n=1 is just fine. It's adding a randomly colored horse to a set of horses that doesn't always result in an n+1 set of like-colored horses. He doesn't even explain the illogical step correctly, so the whole thing is a mess.
> This is incorrect because the assumption is that there is a set of n horses, not "if you have n number of horses they are all the same color.
You have this exactly backwards. The assumption you say is not being made is exactly the one that is being made (and is a step that occurs similarly in every inductive proof.)
the final proof is:
A(1) is true
AND
A(N) implies A(N+1)
means that
A(N) is true for all N >= 1
If A(N) is false in general - you would realize that despite assuming it - because the implication or the base case couldn't be proven.