5 ms·

The problem is the second line: "Now suppose for all sets of n horses, every horse in the set has the same color." There is no justification for that. They th

The problem is the second line: "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.

indianboy42 5y ago
Isn't that just how proof by induction works? You assume the hypothesis is true for n and prove it for n+1
- ahartmetz 5y ago
  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.
  - Arcsech 5y ago
    There are two parts to an inductive proof: 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.
    - runarberg 5y ago
      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 https://en.wikipedia.org/wiki/All_horses_are_the_same_color
      - joshuamorton 5y ago
        You've got it backwards. Induction is usually proving that n implies n+1, So knowing it's true for 2 you can prove for 3. The issue is that this proof only works with the base case of 2, for...reasons.
nnoitra 5y ago
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.
- phkahler 5y ago
  >> 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.
throwvirtever 5y ago
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?
- mannerheim 5y ago
  The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.
  - na85 5y ago
    But why would anyone assume that n horses, for arbitrary n, are the same color? 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.
    - mannerheim 5y ago
      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.
    - ajuc 5y ago
shkkmo 5y ago
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 .
smohare 5y ago
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.

indianboy42 5y ago

Isn't that just how proof by induction works? You assume the hypothesis is true for n and prove it for n+1

ahartmetz 5y ago
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.
- Arcsech 5y ago
  There are two parts to an inductive proof: 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.
  - runarberg 5y ago
    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 https://en.wikipedia.org/wiki/All_horses_are_the_same_color
    - joshuamorton 5y ago
      You've got it backwards. Induction is usually proving that n implies n+1, So knowing it's true for 2 you can prove for 3. The issue is that this proof only works with the base case of 2, for...reasons.

nnoitra 5y ago

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.

phkahler 5y ago
>> 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.

throwvirtever 5y ago

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?

mannerheim 5y ago
The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.
- na85 5y ago
  But why would anyone assume that n horses, for arbitrary n, are the same color? 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.
  - mannerheim 5y ago
    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.
  - ajuc 5y ago

shkkmo 5y ago

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 .

smohare 5y ago

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.