3 ms·

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?
      - thaumasiotes 5y ago
        > The argument in the article is the following: This is incorrect. You attribute an argument to the article that it does not make. > This argument is valid only if A ⋂ B ≠ ∅ This is vacuously true in that the argument is not valid and its validity therefore implies all propositions including that A ⋂ B ≠ ∅. Although I tend to suspect that that isn't what you meant to say. It is equally true that "This argument is valid only if A ⋂ B = ∅". It is not true that if a function f takes a constant value, you can conclude that A ⋂ B ≠ ∅ for arbitrary A and B.
        poetically 5y ago
        Great, glad we cleared that up.
    - shkkmo 5y ago
      > 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. This is exactly what the person you are responding to was saying. They were talking about the transitive part of the inductive step that the article handwaves to with this line: >> In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. the "remaining horses" is the A ⋂ B set that was mentioned and if that set is empty then know it is the same color as set A is meaningless. Thus given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you only know that f(A ⋃ B) is constant if A ⋂ B is non-empty. Given that in this case A and B are formed by removing different elements from a set of size n+1, the proof only works if n+1>=3 so that A ⋂ B can have at least one member.

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?
    - thaumasiotes 5y ago
      > The argument in the article is the following: This is incorrect. You attribute an argument to the article that it does not make. > This argument is valid only if A ⋂ B ≠ ∅ This is vacuously true in that the argument is not valid and its validity therefore implies all propositions including that A ⋂ B ≠ ∅. Although I tend to suspect that that isn't what you meant to say. It is equally true that "This argument is valid only if A ⋂ B = ∅". It is not true that if a function f takes a constant value, you can conclude that A ⋂ B ≠ ∅ for arbitrary A and B.
      - poetically 5y ago
        Great, glad we cleared that up.
  - shkkmo 5y ago
    > 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. This is exactly what the person you are responding to was saying. They were talking about the transitive part of the inductive step that the article handwaves to with this line: >> In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. the "remaining horses" is the A ⋂ B set that was mentioned and if that set is empty then know it is the same color as set A is meaningless. Thus given f(A ⋂ B) = f(A) and f(A ⋂ B) = f(B), you only know that f(A ⋃ B) is constant if A ⋂ B is non-empty. Given that in this case A and B are formed by removing different elements from a set of size n+1, the proof only works if n+1>=3 so that A ⋂ B can have at least one member.