3 ms·

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

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.
        deleted 5y ago
        [deleted]
        poetically 5y ago
        I don't understand what you're arguing. What exactly is incorrect in what I wrote?
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.

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.
      - deleted 5y ago
        [deleted]
      - poetically 5y ago
        I don't understand what you're arguing. What exactly is incorrect in what I wrote?

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.