9 ms·

I started to write out what is happening here more formally, but I think it was not very elucidating. No matter what, the problem is that the proof of the induc

I started to write out what is happening here more formally, but I think it was not very elucidating. No matter what, the problem is that the proof of the inductive step is wrong. The problem is (as mentioned in the article), that for sets of size two, your inductive hypothesis is not sufficient to prove that h1 and h2 are the same color. 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.

poetically 5y ago
I don't think this is correct. The main argument uses a very specific inductive invariant of applying transitivity of equality to a non-empty set. The argument doesn't apply in the base cases because it is vacuously true so the minimal base case is actually a set with 3 horses because that is the only case where transitivity of equality can be used non-trivially.
- dan-robertson 5y ago
  I think that is a complicated way to look at things. The error is that the argument assumes that for a, b being elements of H, the sets H - {a} and H - {b} meet. This is true for |H|>2 but the first induction case is for |H|=2, where the assumption is obviously false. But when you read the induction case you may think of n as being large and so not notice the error.
  - poetically 5y ago
    Yes, this is what I said in another comment.
    - dan-robertson 5y ago
      I don’t understand what you mean? I think that what I wrote is implicitly agreeing with the GP that the induction argument is wrong not the base case. And I think that you attempted to refute it, but I couldn’t really understand how what you wrote would relate to either side. Do you mean that you agree that your description above was complicated, or that you agree that what I wrote is a fair description of the problem, or do you (now as opposed to before?) think that the problem was the induction step not the base case? Or are you talking about the statement that it is easy to miss the error by thinking of n as big rather than n=2? Maybe it doesn’t matter.
      - poetically 5y ago
        The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This argument is valid only if A ⋂ B ≠ ∅. It doesn't apply to the base cases because anything is true for the empty set and any function on a one element set is trivially constant. So the minimal case where this can be applied in a non-trivial way is a set with 3 elements.
        thaumasiotes 5y ago
        > The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This is not the argument. > This argument is valid only if A ⋂ B ≠ ∅. No, it isn't; it isn't even valid then. Consider a function over sets of real numbers: f([0,2]) = 5 f([1,3]) = 5 f([1,2]) = 5 f([0,3]) = 6 plus other values... I've constructed this function so that, obviously, f(A) = f(B) = f(A ⋂ B) = 5, and A ⋂ B = [1,2] ≠ ∅, but f is not a constant function and f(A ⋃ B) is not 5. f is still a function. We can state the proposition "in a group of N or fewer horses, all of the horses are the same color" like so: ∀G∃c∀x( (|G| ≤ N ∧ x ∈ G) → f(x) = c ) where f is the function that tells you what color a horse is, and N is a free variable. The proof claims that if this proposition is true for the value N = k, then it is also true for the value N = k+1. This claim is correct for all k > 1, but it is not correct for k=1. The problem is that we only show the truth of the proposition for N=1. Abstracting a little further, we can view the proposition above as the potential output of a function of N: p(0) = ∀G∃c∀x( (|G| ≤ 0 ∧ x ∈ G) → f(x) = c ) p(1) = ∀G∃c∀x( (|G| ≤ 1 ∧ x ∈ G) → f(x) = c ) p(2) = ∀G∃c∀x( (|G| ≤ 2 ∧ x ∈ G) → f(x) = c ) p(3) = ∀G∃c∀x( (|G| ≤ 3 ∧ x ∈ G) → f(x) = c ) p(4) = ∀G∃c∀x( (|G| ≤ 4 ∧ x ∈ G) → f(x) = c ) We can now say that the proof is claiming that whenever p(k) is true, p(k+1) is also true, that this claim is correct for all k > 1, and that p(1) has been established. But p(2) has not.
- dwohnitmok 5y ago
  > The argument doesn't apply in the base cases 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.
  - poetically 5y ago
    So what would say is the error in the inductive step here?
    - dwohnitmok 5y ago
      The inductive step is being obscured (intentionally of course in the article to illustrate how the error can hide) behind the n. The inductive step here is not true for all n, n + 1 pairs. It is only true for all n, n + 1 pairs given that n is greater than or equal to 2. The error is to drop that >= condition. Hence the inductive step is wrong as stated in the article (for all n), and its proof is erroneous. Again while changing the base case can "fix" the argument in that it no longer proves an falsehood, without altering the statement of the inductive step it is still not a valid argument and only happens to prove a true statement "by chance." If the base case was the error in the sense of proving a falsehood, then it would be possible to have an unsound inductive argument by choosing the wrong base case, but that's impossible. Rather the wrong base case (but correct inductive step) simply means you end up unable to complete your proof.
- fnord123 5y ago
  Why is the base case 3? H(1) contains one colour of horse. H(2) when removing one horse contains one colour of horse. 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.
amitkgupta84 5y ago
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.
- dsizzle 5y ago
  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.
  - eperdew 5y ago
    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).
    - ashtonbaker 5y ago
      > 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.
GhettoComputers 5y ago
Is Godel's theorem what you're referring to? https://plato.stanford.edu/entries/goedel-incompleteness/ https://plato.stanford.edu/entries/goedel-incompleteness/
sidedishes 5y ago
I don't understand why it's more or less weird to say the base case is wrong vs. the inductive case is wrong. If H(n) is 'all sets of horses of size n contain horses of the same colour', the linked argument seems like 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?
- amitkgupta84 5y ago
  You just said it. The base case is true. The inductive case is wrong. You called it true “with sleight of hand”, but that’s more of a poetic statement; mathematically it’s simply 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.
  - Dylan16807 5y ago
    > You just said it. The base case is true. The inductive case is wrong. Not really. H(1) is true. H(2) is false. But either one could be your base case. The inductive step could be true or false, again depending on what you call your base case.
phkahler 5y ago
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
andi999 5y ago
Yes, I also think it has nothing to do with base case and general case, there is just a flaw in the argument. When arguing that h2 also is brown one assumes wrongly that there are other elements in the reduced set left.

poetically 5y ago

I don't think this is correct. The main argument uses a very specific inductive invariant of applying transitivity of equality to a non-empty set. The argument doesn't apply in the base cases because it is vacuously true so the minimal base case is actually a set with 3 horses because that is the only case where transitivity of equality can be used non-trivially.

dan-robertson 5y ago
I think that is a complicated way to look at things. The error is that the argument assumes that for a, b being elements of H, the sets H - {a} and H - {b} meet. This is true for |H|>2 but the first induction case is for |H|=2, where the assumption is obviously false. But when you read the induction case you may think of n as being large and so not notice the error.
- poetically 5y ago
  Yes, this is what I said in another comment.
  - dan-robertson 5y ago
    I don’t understand what you mean? I think that what I wrote is implicitly agreeing with the GP that the induction argument is wrong not the base case. And I think that you attempted to refute it, but I couldn’t really understand how what you wrote would relate to either side. Do you mean that you agree that your description above was complicated, or that you agree that what I wrote is a fair description of the problem, or do you (now as opposed to before?) think that the problem was the induction step not the base case? Or are you talking about the statement that it is easy to miss the error by thinking of n as big rather than n=2? Maybe it doesn’t matter.
    - poetically 5y ago
      The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This argument is valid only if A ⋂ B ≠ ∅. It doesn't apply to the base cases because anything is true for the empty set and any function on a one element set is trivially constant. So the minimal case where this can be applied in a non-trivial way is a set with 3 elements.
      - thaumasiotes 5y ago
        > The argument in the article is the following: Given some function f, if f(A) = f(B) = f(A ⋂ B) then f is equal to some constant c and f(A ⋃ B) = c. This is not the argument. > This argument is valid only if A ⋂ B ≠ ∅. No, it isn't; it isn't even valid then. Consider a function over sets of real numbers: f([0,2]) = 5 f([1,3]) = 5 f([1,2]) = 5 f([0,3]) = 6 plus other values... I've constructed this function so that, obviously, f(A) = f(B) = f(A ⋂ B) = 5, and A ⋂ B = [1,2] ≠ ∅, but f is not a constant function and f(A ⋃ B) is not 5. f is still a function. We can state the proposition "in a group of N or fewer horses, all of the horses are the same color" like so: ∀G∃c∀x( (|G| ≤ N ∧ x ∈ G) → f(x) = c ) where f is the function that tells you what color a horse is, and N is a free variable. The proof claims that if this proposition is true for the value N = k, then it is also true for the value N = k+1. This claim is correct for all k > 1, but it is not correct for k=1. The problem is that we only show the truth of the proposition for N=1. Abstracting a little further, we can view the proposition above as the potential output of a function of N: p(0) = ∀G∃c∀x( (|G| ≤ 0 ∧ x ∈ G) → f(x) = c ) p(1) = ∀G∃c∀x( (|G| ≤ 1 ∧ x ∈ G) → f(x) = c ) p(2) = ∀G∃c∀x( (|G| ≤ 2 ∧ x ∈ G) → f(x) = c ) p(3) = ∀G∃c∀x( (|G| ≤ 3 ∧ x ∈ G) → f(x) = c ) p(4) = ∀G∃c∀x( (|G| ≤ 4 ∧ x ∈ G) → f(x) = c ) We can now say that the proof is claiming that whenever p(k) is true, p(k+1) is also true, that this claim is correct for all k > 1, and that p(1) has been established. But p(2) has not.
dwohnitmok 5y ago
> The argument doesn't apply in the base cases 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.
- poetically 5y ago
  So what would say is the error in the inductive step here?
  - dwohnitmok 5y ago
    The inductive step is being obscured (intentionally of course in the article to illustrate how the error can hide) behind the n. The inductive step here is not true for all n, n + 1 pairs. It is only true for all n, n + 1 pairs given that n is greater than or equal to 2. The error is to drop that >= condition. Hence the inductive step is wrong as stated in the article (for all n), and its proof is erroneous. Again while changing the base case can "fix" the argument in that it no longer proves an falsehood, without altering the statement of the inductive step it is still not a valid argument and only happens to prove a true statement "by chance." If the base case was the error in the sense of proving a falsehood, then it would be possible to have an unsound inductive argument by choosing the wrong base case, but that's impossible. Rather the wrong base case (but correct inductive step) simply means you end up unable to complete your proof.
fnord123 5y ago
Why is the base case 3? H(1) contains one colour of horse. H(2) when removing one horse contains one colour of horse. 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.

amitkgupta84 5y ago

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.

dsizzle 5y ago
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.
- eperdew 5y ago
  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).
  - ashtonbaker 5y ago
    > 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.

GhettoComputers 5y ago

Is Godel's theorem what you're referring to? https://plato.stanford.edu/entries/goedel-incompleteness/ https://plato.stanford.edu/entries/goedel-incompleteness/

sidedishes 5y ago

I don't understand why it's more or less weird to say the base case is wrong vs. the inductive case is wrong. If H(n) is 'all sets of horses of size n contain horses of the same colour', the linked argument seems like 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?

amitkgupta84 5y ago
You just said it. The base case is true. The inductive case is wrong. You called it true “with sleight of hand”, but that’s more of a poetic statement; mathematically it’s simply 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.
- Dylan16807 5y ago
  > You just said it. The base case is true. The inductive case is wrong. Not really. H(1) is true. H(2) is false. But either one could be your base case. The inductive step could be true or false, again depending on what you call your base case.

phkahler 5y ago

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

andi999 5y ago

Yes, I also think it has nothing to do with base case and general case, there is just a flaw in the argument. When arguing that h2 also is brown one assumes wrongly that there are other elements in the reduced set left.