>> It's part of the inductive proof process. Assuming that it holds for n you need to show that it implies that it holds for n + 1 as well.
No. That's wrong. They assert it up front (that it is true for any n horses) and then go on to use it in the proof for n+1. The only time it's OK to assert your claim up front is if you're trying to prove it false by contradiction.
For an inductive proof, you must prove that if it holds for one case (n=1 here) it also holds for the next case. The base case is important and is proven (or obviously) true. A set of n is not the base case here, and they assert something about it without proof.
EDIT: Nope, my dumb. The wording is odd, but for induction we show that it is true for n=X (X is the base case and is 1 in this example). the inductive step is to show that being true for n implies being true for n+1 which is what they did here.
That isn't really a problem, just poorly worded (like a number of sentences in the article.) This is a pretty standard step of an inductive that should read more like: Given that n is some positive integer where every set of n horses has the same color...then you try to prove that holds true for n+1 as well.
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 .
I feel like I'm too ignorant of mathematics to be confused by this "proof".
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?
> But why would anyone assume that n horses, for arbitrary n, are the same color?
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.
Well, anyone who's seen a field of horses knows that "assume any set of n horses has the same color" is not valid.
So if what you say is true, then that implies the entire field of inductive reasoning is horse shit. But I don't think that's the case, so something's missing.
> Well, anyone who's seen a field of horses knows that "assume any set of n horses has the same color" is not valid.
That's not even true! If n is 0 or 1 then the statement is correct, for example.
If your response is "It's not true for all n, though." well, the inductive proof doesn't assume it for all n either. It only assumes it for one n at a time.
But also, you're getting too hung up on the exact wording of the statement.
For example, we could do the same proofs, but put "on farmer Joe's land" onto the statements.
If we do that, "anyone who's every seen a field with horses in it" can't tell us if the statement is true or not. Maybe all groups of 2 horses in a field on farmer Joe's land do have the same color, because he sorts his horses. And obviously all groups of 3 horses would have to have the same color, etc. etc.
So on farmer Joe's land, A(n=2) is true. And the induction is valid. And using it gives you the correct results! What's the problem with inductive reasoning here?
You seem upset that the induction itself might be valid even if n=2 isn't, but I don't know why. The induction is the same no matter whose farm you're on. That's why you need to prove the base case too.
> But you're not trying to prove X = 3 and starting out by assuming X = 3.
It's really not. There's an entire series of X, and we're saying if we can prove one we can prove the next. You never assume an X when proving that X. And you never assume a higher X when proving a lower X. There are no circles. It's a chain.
"Assume X is 3. Then 2*X=6" is just a different way of saying "If X is 3, then 2*X=6"
You can rewrite the entire thing without the word assume if you want.
You can do the whole thing as "if Y, then Z". "if A(n), then A(n+1)". If pairs of horses are the same color, then triples of horses must be the same color. If triples of horses are the same color, then quads of horses must be the same color. Those sound like reasonable statements to me.
Even if we're talking about all horses in the entire world, I could theoretically go kill every non-brown horse, and the original statements would all become true.
This is math. You can't object to abstract logic by mentioning real-world facts that could change at any moment.
So it's worth noting that the inductive hypothesis isn't false for all values of n - namely, it is true for n = 0,1.
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.
>> The inductive step assumes the hypothesis is true for n
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.
As the article says there is a problem talking about equality among members of a set with size 1. So saying "all the horses in a set of size 1 are the same color" begs the question "same as what?" and that's where the real problem is, and the difficulty in pinning down that kind of thing is why I'm not a mathematician ;-)
There are several 'mathematical' ways you could phrase it (glossing over how to define the colour of a horse):
1) In a set of horses with size n, if horses A and B being both members of this set implies horse A has the same colour as horse B, then all horses in the set have the same colour.
2) In a set of horses with size n, and let f be a function on this set that produces each horse's colour. Then all horses in this set have the same colour if and only if the codomain of f on this set has size 1.
You could probably prove these are equivalent definitions.
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.
In simpler terms the two steps for this problem are:
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.
> He's saying there is some set of n+1 horses, n of which are 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.
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.)
But you don't go from n-1 to n. You'd have to start at the infinite horses case where the conjecture must be true for, well, who knows what reason. Intuitively, "Consider the conjecture proven. If we reduce the difficulty, it's still proven" just seems obviously wrong.
1. Assuming that a property is true for N, prove that it is true for N+1.
2. Prove that the property is true for some concrete N where the proof for step 1 holds.
The trick is that you need to be sure to pick your concrete N correctly, as the article demonstrates. In particular, the problem with the "solution" in the article is that the proof given for step 1 doesn't hold for N=1, because N+1=2, and then just follow the rest of the argument from the article.
I still don’t quite understand. The inductive step shows n + 1 → n right? However with any positive base case b, n → n + 1 isn’t certain for any integers above b, only below it.
Say you’ve proved the case for n = 3 and that n + 1 → n. Then you’ve proven that 2 + 1 → 3, and by induction 1 + 1 → 2, However you’ve never proven it for n = 4 because n → n + 1 has never been established.
Or am I missing something here?
EDIT: I’ve seen in other posts that this the problem with OP is that it hides the transitivity of the operation. In fact the failure of the proof was that it proved transitivity with a false premise. If transitivity was true, then using n + 1 → n is just fine. The Wikipedia article for this statement is actually a lot clearer. https://en.wikipedia.org/wiki/All_horses_are_the_same_color
That’s not the issue at all, since the base case of n=1 is established trivially and so the quoted statement is merely the inductive hypothesis. But the inductive argument relies on n>2 to invoke transitivity on a non-empty intersection necessitating a separate justification for n=2.