186 comments

·December 4, 2021eperdew

amitkgupta84

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.

diffeomorphism

Disagree. The induction step works perfectly fine for n>=2. In particular, if you can give me the base case "any two horses have the same color", then this proof works and all horses have the same color.

The problem is that the base case is n=2, but the student checked n=0 and n=1.

amitkgupta84

The base case is not n=2, it’s clearly stated as n=1 in the proof.

The inductive step works fine if you introduce the premise n>=2. It is not valid to introduce that premise. The inductive step is therefore wrong.

The proof in the post is saying the base case is P(1) and the inductive case is that for all n, P(n) => P(n+1)

“P(1)” is true. “For all n, P(n) => P(n+1)” is false. The inductive step is wrong

A completely different proof not present in this post could be:

Base case: P(1) and P(2) Inductive case: for all n > 1, P(n) => P(n+1)

In that completely different proof, the inductive step would be correct and the base case would be wrong. That proof is not in the original post.

wisty

No, the induction step works for n>=3. The induction step fails for n=2.

For n=2, you can't prove h1 is the same colour as h2, because you don't have a h3 to compare it to.

mcphage

Their inductive step is perfectly valid. However, requires a group of horses with one removed to still have a horse remaining. Using N=1 is an incorrect base case. Had they proved the N=2 base case, their entire argument would work.

Of course, you can’t prove the N=2 base case, so that’s why the argument uses the wrong base case.

amitkgupta84

The inductive step introduces a premise that “requires a group of horses with one removed to still have a horse remaining.” It is not valid to introduce this premise. The inductive step is not valid.

dsizzle

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

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

Ericson2314

Pre formal methods, sophists spin false proofs like this example. Post formal methods, sophists spin false propositions.

sidedishes

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

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

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

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?

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.

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.

GhettoComputers

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

andi999

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.

phkahler

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.

nnoitra

It's part of the inductive proof process. Assuming that it holds for n you need to show that it implies that it holds for n + 1 as well.

phkahler

>> It's part of the inductive proof process. Assuming that it holds for n you need to show that it implies that it holds for n + 1 as well.

No. That's wrong. They assert it up front (that it is true for any n horses) and then go on to use it in the proof for n+1. The only time it's OK to assert your claim up front is if you're trying to prove it false by contradiction.

For an inductive proof, you must prove that if it holds for one case (n=1 here) it also holds for the next case. The base case is important and is proven (or obviously) true. A set of n is not the base case here, and they assert something about it without proof.

EDIT: Nope, my dumb. The wording is odd, but for induction we show that it is true for n=X (X is the base case and is 1 in this example). the inductive step is to show that being true for n implies being true for n+1 which is what they did here.

shkkmo

That isn't really a problem, just poorly worded (like a number of sentences in the article.) This is a pretty standard step of an inductive that should read more like: Given that n is some positive integer where every set of n horses has the same color...then you try to prove that holds true for n+1 as well.

The actual problem in that proof is setting up the proofs of the inductive rule. There is an implicit assumption/condition that n+1 >= 3 that is not acknowledged.

If you acknowledge that condition, then it becomes quite clear that you can only prove a base case for n = 1 and only prove an induction rule for n >= 2 .

throwvirtever

I feel like I'm too ignorant of mathematics to be confused by this "proof".

When you set out to prove "for any set of n horses, every horse in that set has the same color" and you then "suppose for all sets of n horses, every horse in the set has the same color" as a first step, you're messing with a tautology, aren't you? I mean if you've supposed that it's true for all, it's definitely true for any, right?

What am I missing that makes the problem subtle and interesting, rather than just blatantly circular from the start?

mannerheim

The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.

shkkmo

There are two steps of an inductive proof

one is proving the inductive rule that: p(n) implies p(n+1)

the other is proving that there exists some number i for which p(i) is true. This, combined with the proof of the inductive rule, allows you to prove that p(n) is true for all n >= i.

ajuc

It's not circular, because you aren't using the assumption A in the final proof, you are just using the implication A(N) => A(N+1) in the final proof.

the final proof is:

```
A(1) is true
AND
A(N) implies A(N+1)
means that
A(N) is true for all N >= 1
```

the assumption that A is true for N was just used as a condition in the implicationIf A(N) is false in general - you would realize that despite assuming it - because the implication or the base case couldn't be proven.

indianboy42

Isn't that just how proof by induction works? You assume the hypothesis is true for n and prove it for n+1

ahartmetz

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.

smohare

That’s not the issue at all, since the base case of n=1 is established trivially and so the quoted statement is merely the inductive hypothesis. But the inductive argument relies on n>2 to invoke transitivity on a non-empty intersection necessitating a separate justification for n=2.

dsizzle

This post is basically a paraphrase of a well-known example, which has its own Wikipedia page https://en.m.wikipedia.org/wiki/All_horses_are_the_same_colo...

I think the fallacy is explained better there tbh.

I also think it’s confusing to say one isn’t the base case. When you apply the inductive step there you hit N=2, and indeed the step fails because there’s no overlap.

tux3

This is indeed much clearer than the OP's version. In this one, the transitivity is obvious, because the article clearly explains that you may take out any horse from n + 1 and note that the remaining n have the same color, then do that observation again with another one, and use the horses that never left the group as a transitive link.

I agree this is much more worth looking at.

wruza

*(wiki) Thus in any group of horses, all horses must be the same color.*

Yes, *iff n horses have the same color*. I fail to see any paradox here (and in subj tfa too) and why induction is of any importance to it. We worked it all out of a restricting assumption which wasn’t contradicted, but that’s it. It doesn’t tell us anything about all other cases, e.g. when *n horses do not have the same color*.

Can someone please explain what I’m missing here?

dsizzle

The inductive step allows you to stipulate what seems like a strong assumption, in this case that all horses in sets of size N have the same color. I think you're reacting to that seeming like it's the problem, because at first that seems like where the "cheating" is occuring: you can obviously have a set of horses that aren't all the same color.

But actually that's part the power of the inductive step: you *do* have the freedom to choose whatever assumptions you want. The question is whether it's true for N+1, for all N. In this case, it's not: the inductive step fails. But there's nothing flawed with the starting premise per se (aside from it being intuitively obvious that it will never work). The interest here is that it seems you can get further than you should be able to, and it's a little tricky to figure out where the logic falls apart.

Dylan16807

What you're missing is that "n horses have the same color" *is* true for n=1. So therefore we *should* be able to invoke the induction to bigger and bigger numbers.

If the induction actually was valid for 1->2, we'd have a hell of a problem.

wruza

Now I think I understand the subtlety, thanks! The induction part is important here because we start *from* n=1 (where the assumption is not as obviously questionable as for n in general, because it’s coincidentally/degeneratively true in relation to our reasoning) and then the “base error” allows us to generalize into a bigger mistake.

lambdatronics

Yeah, it's phrased weird. In the inductive step, what you want to do is prove that "if all sets of horses with size n have the same color, then all sets of horses with size n+1 have the same color." In order to prove that, you start with the assumption that all sets of horses with size n have the same color. They're not actually assuming it's true for *all* n right away, they're just assuming that they've gotten it for *some* n.

GolDDranks

"Now suppose for all sets of n horses, every horse in the set has the same color"

This sounds so obviously false to me, that I initially thought that he must have meant "now suppose for all sets of n horses such that every horse in the set has the same color". I.e. take all sets of n horses and then filter them to only get the uniformly colored sets.

But he doesn't mean that, it is meant as the induction step:

"Now suppose a world where for all _possible_ sets of n horses, it turns out that every horse in the set _necessarily_ has the same color."

In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.

crdrost

I'm not sure any wording helps, because the reason it strikes us so poorly is that it's such an implausible idea.

It might help to make it more concrete, to say “assume that we've proven this for say n = 3, all sets of three horses have the same color. Then I can prove it’s true for n+1, because my set {Auris, Brunellus, Camper, Diego} of four horses is the union of two overlapping 3-sets, {Auris, Brunellus, Camper} and {Brunellus, Camper, Diego}. By the transitive property, Diego must have the same color as Auris and the result holds. But obviously this works not just for 3 going to 4, but also 4 going to 5... Any set of size n+1 is made up of two overlapping sets of size n.”

Maybe also someone can then intuit that the wool is being pulled over their eyes in this step?

diffeomorphism

That is the same sentence just abbreviated and using standard words. Nobody says "suppose a world where", you just say "suppose that". Also, you just say "if ..., then ...", not "suppose if ..., then it necessarily turns out that ...".

> In my mind, the article is a bit poorly worded, but then again, maybe it makes sense for mathematicians.

That is the point. This example is given to first year students to show them why you need to be careful in your proofs and why properly wording/formulating statements is important.

wombatpm

There are variations of this style of proof the shows all horses have an infinite number of legs, since horses must have an even number of legs to stand, yet they have two legs in back and forelegs in front, giving them six legs which is an odd number of legs for a horse. The only number that is even and odd is infinity, hence horses have an infinite number of legs.

There is also lemma that since Alexander the Great rode a Black horse, he did not exist, but if he did exist he would have an infinite number of arms and legs

pinerd3

This is clever, but I wouldn't call it a variation on this style of proof — the OP was an example of a somewhat-subtle logic error, while this is just two instances of wordplay (forelegs ⇔ four legs; six legs being an 'odd' number of legs for a horse).

The joke is funny though

pests

I don't understand. How is that six legs? How is that an odd number? Am I missing a joke?

erulabs

Yes, it's an English language joke:

Two legs in back, and "forelegs" in front (four-legs). 2 + 4 = 6, which is a *peculiar* (aka odd) number of legs for a horse to have. Thus horses have both odd and even number of legs, meaning horses have infinite legs.

pfdietz

Actually, the argument was that Alexander the Great had an infinite number of arms. You see, in a famous battle he was forewarned. And as we all know, forewarned is four armed. The rest of the argument is similar.

pests

Holy moly did I miss the joke

I'm a complete native and fluent English speaker for 30+ years.

Thank you for the explanation - I know others here may need it but, and in all kindness, I'm lmaoing over here being explained this joke like a toddler.

ars

forelegs means "front legs", but also sounds like "four legs". "odd number" means "strange number", and also "number not divisible by 2".

null

[deleted]

james_in_the_uk

Six legs on a horse would be very odd indeed

pfdietz

The situation could be much worse.

allannienhuis

fourlegs

charcircuit

infinity is typically not defined to be even or odd.

georgeoliver

Wow, I guess I should have studied logic!

Can someone explain in English how the author goes from "[now] suppose for all sets of n horses, every horse in the set has the same color" to 'proving' anything?

amalcon

Though incorrect, this is meant to be an example of proof by induction. Proof by induction is (to simplify a little) where you prove that any number N+1 will have a given property as long as N has that property. You can use this same rule twice to prove that N+2 has this property, and so on.

Finally, you prove that any arbitrary number (say, 1) has the property in another way, and you've proven that property for all N greater than or equal to 1.

The error in the proof is explained in the linked page, but basically the problem is that the proof that N implies N+1 doesn't actually work for all N, and particularly it doesn't let us go from 1 to 2.

joppy

This is standard induction: let P(n) be some statement about the number n. If you can establish that P(n) implies P(n+1) for all n >= 1, and that P(1) is true, then P must be true for every positive integer. You can find many examples by googling for “induction proof”.

The problem in the proof is that the inductive step P(n) implies P(n+1) only holds for n >= 3, and so the fact that P(1) is true does not imply anything for the larger integers.

didibus

Okay, but my issue and I think the one of the OP is that even for n >= 3 how did they prove that all horses are the same color for n >= 3?

amalcon

It's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can prove that all groups of 3 horses are by labelling them A, B, C. A and B are the same color because they are a group of 2; B and C are the same color because they are also a group of 2; A and C are the same color transitively (or because they are also a group of 2). Therefore A, B, and C are the same color. This step is logically sound, and you can do this for any N greater than three.

The problem is that this fails when tried for N=2, because then each sub-group can have only one horse in it. We already know that each horse is the same color as itself, so we don't actually reveal any new information by doing this. Since it doesn't work for N=2, the base assumption used for the N=3 case is incorrect.

dack

Yeah this is why I'm confused as well. I don't follow how if we assume n are the same color, that it implies anything about n+1. It sounds like the article is saying that the N+1 logic makes sense for n > 2, but I don't see how it does.

jpmoral

The idea is that if it holds for n = 3 then it holds for n > 3. The way to show that it holds for n = 3 is to show that it holds for n = 2, which it doesn't.

bonaldi

This is quite tricky to do, because it’s almost a sleight of hand and expressing it in English is like watching the trick from behind the magician - you can obviously see the wrongness.

But: if you skip a pair of horses (which is how the trick is done/the error introduced) it might be:

Assume any group of 3 horses are the same colour. Can we show that adding another horse will result in a group of horses that are all the same colour?

Well yes: take your new group of 4 horses, and extract 1. (h1). Three horses remain and they must by definition be the same colour. Put h1 back and extract a different horse (h2). Now three remain and must by definition be the same colour as each other.

But when h2 was out, h1 was part of a group that was all the same colour. And when h1 was out, h2 was part of a group that was all the same colour. Therefore they must *all* be the same colour. It doesn’t matter how many different horses you find and bring to your initial group of 3, the rules will mean the resulting group of 4 is always the same colour. And so it is true for a group of 4 horses.

By the same reasoning, it must then be true for a group of 5, and so on up to all horses.

So *all* horses are the same colour, so long as the first assumption (that any group of 3 horses must be the same colour) holds.

The trick/error is jumping from “a group of 1 horses must all be the same colour” to “a group of 3 horses must be the same colour” which is an easy jump to miss if you go from “1” to “n”, instead of “1” to “3”.

(The logic doesn’t work for a pair of horses, because once h1 is taken out there are no other horses left that h2 must be the same colour as.)

marcodiego

This is called proof by induction. There is an intuitive path to understand it: Consider the set of the natural numbers; it contains 0 (zero) and for any K which belongs to this set, its successor (K + 1) also does. It is clear that if a property if valid for 0 and, in the case it is valid for a K which is not 0 implies it is also valid for K + 1, then such property is valid for all natural numbers.

TylerE

He does't. Read the last paragraph:

This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not n=1, but rather n=2. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.

null

[deleted]

null

[deleted]

rp1

This brings up an interesting problem with inductive arguments I’ve never thought of: how does one prove a base case is a sufficient starting point for induction? In the horse example, we know there can be groups of multi-colored horses so our intuition guides us to a counter example, but it seems like a detail like that could easily be overlooked for something more complicated.

poetically

You have to find the minimal case where the inductive invariant is valid. In this case when the horses are separated into two groups, A and B, the assumption is that their intersection is non-empty (A ∩ B ≠ ∅). Because only in the case where the intersection is non-empty can we apply transitivity of equality to conclude that their union (A ⋃ B) satisfies what we are trying to prove. But as the article argues this fails for a very simple counter-example where A and B are non-empty but their intersection is empty.

auggierose

Sorry, this answer is confusing. The base case just needs to have the property you want to prove. The induction step does all of the heavy lifting to go from n to n+1. In this case, the induction step fails, because it cannot go from 1 to 2. Simple as that.

Edit: I removed the wrong. It’s just confusing.

poetically

Where exactly is my error?

shkkmo

Any example is a base case that is sufficient for starting an inductive truth, as long as it is covered in your inductive rule.

The actual error is is a logic error in the proof of the inductive rules that takes a logical step that only holds for n>=2 but doesn't acknowledge that condition. If that logical step is done properly and the condition made explicit, it is clear that a base case of n=1 won't prove anything with that inductive rule that only applies to n>=2.

eperdew

You don't have to. See my top level comment. In short, you have to strengthen your goal in order to have a strong enough inductive hypothesis to prove anything. E.g., instead of "picking a base case" that's sufficient, you work the base case into the goal, like n >= 2 -> P(n). Then you do the base case as part of a branch in the inductive step, without using your inductive hypothesis.

GhettoComputers

You can't, you just make assumptions with imperfect information. https://plato.stanford.edu/entries/goedel-incompleteness/

k_bx

> 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. Hence, all horses in H are brown.

This is an error. h1 and h2 don’t have to be the same by any previous conclusions. If you have two horses, white and brown, it’s true to say if we remove one or another that “all horses that are left are same colour”, but they by no means need to be of same colour between themselves.

ineedasername

Reminds me of "everything has a 50/50 chance".

Because for any event or proposition it will either happen or not happen, two possible states. And you figure probabilities from the canonical fair coin and come up with two states & a 50/50 chance of either one coming up. So the proposition "A giant meteor will hit the Earth tomorrow" will either happen or not happen, so there's a 50/50 chance of a global extinction event tomorrow.

fallingfrog

Hmm, I think there is a more basic error here. If you remove an element from your set of n + 1 horses, you get *different* sets of n horses depending on which one you take out. Here's where the mistake is:

"Consider any set H of n+1 horses. We may pick a horse at random, h_1 in H, and remove it from the set, getting a set of n horses. By the inductive hypothesis, all of the n remaining horses are the same color.

On the other hand, if we remove a different horse h_2 in H, we again get a set of n horses which are all the same color. Let us call this color “brown,” just to give it a name. 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. Hence, all horses in H are brown."

Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the *same* uniform color as *one another*. The ambiguity lies in the English phrase "same color" which can be interpreted in two different ways. It could mean "uniform color within the set of n horses" or "uniform across every set of n horses".

shkkmo

Edit: You seem to have deleted the part I was responding to. Here's a new response:

> Nope, when you removed h1, and when you removed h2, by assumption you got two sets of uniform color, but you never proved they had the same uniform color as one another.

This part of the proof happens sneakily here:

>> But when we removed h_1, we got that all the remaining horses had the same color as h_2.

The sneaky part is 'all the remaining horses' which does allow you to prove they're all the same color if the number of "remaining horses" is > 0.

This is where the inductive step sneaks in the n>=2 assumption.

Original:

> The base case is the former but the inductive step appears to be assuming the latter

The inductive step doesn't make that assumption. What it does do is assume that n>=2. The step basically says: from a set s1 of n+1 horses, remove horse h1 (this assumes n>=0). This gives you a set s2 of n horses, and we already know that all sets of n horses have horses of one color. Now take the original set of n+1 horses and remove a different horse (h1<>h2 assumes n>=1), leaving a set s2 of n horses, which we again already know are all same color. Now assume that there is yet another horse h3 (h1<>h2<>h3 assumes n>=2) that is in the original set s1. Since h3 is in s2 with h1 and in s3 with h2, h3 is the same color as h1 and h2. Since h3 is any arbitrary member of s1 besides h1 and h2 we know that all members of s1 are the same color.

Thus the inductive rule is indeed valid for every n≥2. If you can ever prove that every pair from a horse population has the same color you have also shown that every size of sets of horses from that population will also all have the same color.

SamBam

Consider if it *were* true that, for any set of 3 horses, they were all the same color (within the set of three).

This would mean it would be impossible to have a set of 3 brown horses and a white horse hanging around.

Why? Because if you added the white horse to the group and removed another horse, then you wouldn't have a group of three of the same color. So this would contradict our assumption.

So, if our assumption at top is true, it can only be true if *all* horses are the same color.

That's all that the original proof is saying, only stated slightly differently. It's saying that the only way the hypothesis could be true for N is if it's also true for N + 1.

vecter

You can conclude that H - {h1} and H - {h2} share the same color with each other because (assuming n >= 2), there will be a third horse h3 in both those sets. Therefore by transitivity, these two sets must have the same color.

This is implied and not explicitly stated, so it could be clarified.

mstade

This reminds me of another story involving horses and, while not quite as formal as this, at least involved some creative (or humorous at least) argumentation.

A while back in Sweden some fella started a movement which argued that horses are in fact a fruit that does not exist. It became a quite popular meme and the founder was even interviewed on national television. (Yes, really.) When asked how a horse could possibly be a fruit that doesn't exist, he likened them to dragons. See, dragons are a kind of lizard, but they're also just a figment of our imagination and so therefore can not possibly exist. Horses are the same except they're a fruit, and they don't exist. He presented this argument with a straight face in the middle of a riding school with horses in the background, leaving the interviewer dumbfounded. It was a glorious and hilarious moment in Swedish television history.

GhettoComputers

Unrelated to inductive reasoning, but a fascinating fact is that humans are naturally dark skinned (native Europeans used to have blue eyes and dark skin), some humans today have melanin mutations that cause them to be lighter, and chimpanzees are all white: they are just covered in black hair.

BeFlatXIII

Related to skin pigmentations, a "white" horse with a black nose is, in fact, a fully greyed-out horse. True white horses have pink noses and are much rarer.

air7

I think a better explanation would be that the induction step missed an edge case: To claim that H/h1 and H/h2 are the same color, we need the two sets to overlap by at least one horse. This actually works perfectly for all but n=2...

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.