5 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.

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.
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.
  - Ericson2314 5y ago
    Pre formal methods, sophists spin false proofs like this example. Post formal methods, sophists spin false propositions.
  - 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.

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.
- Ericson2314 5y ago
  Pre formal methods, sophists spin false proofs like this example. Post formal methods, sophists spin false propositions.
- 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.