[poetically]

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.

[dwohnitmok]

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

[shkkmo]

> 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

The inductive step should be proven completely independently of proving a base case. Indeed, if the inductive step is proven correctly you see that it is limited in scope to n>1.

You can then use any base case you can prove where n>1. Let's say you pick a base case of one trillion. Easy enough to show thay every set of one trillion horses is the same color (since no such sets can exist). You can then easily use induction to show that every set larger than one trillion horses is also the same color!

So really, both base and induction were wrong in different ways but if the induction had been proven correctly, the inapplicable base case would have been clear.

[poetically]

So what would say is the error in the inductive step here?

[dwohnitmok]

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.

[dan-robertson]

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]

Yes, this is what I said in another comment.

[dan-robertson]

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]

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]

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

[shkkmo]

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

[dan-robertson]

> Consider a function over sets of real numbers …

I think you just misunderstood the notation. f is a function from (say) X -> Y. But the parent talks about it as if it were a function from the power set P(X). That is, for A a subset of X, when the commenter above says that f(A) is a constant, they meant that f(A) = {c} for some c in X. This is a bit of loose usage of the standard notation f(A) := {f(a) : a in A} is commonly understood.

Obviously an arbitrary function f : P(X) -> … needn’t satisfy the properties but no one was suggesting that.

[poetically]

I don't understand what you're arguing. What exactly is incorrect in what I wrote?

[fnord123]

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.