30 ms·

All Horses Are the Same Color

153 points by poetically 5y ago

GenerocUsername 5y ago
This case is so contrived and meaningless I am forced to believe it is satire.
- vecter 5y ago
  It's a common "false proof" example that's taught in many introductory college classes. I learned this in my discrete math class.
georgeoliver 5y ago
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?
- TylerE 5y ago
  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.
- joppy 5y ago
  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 5y ago
    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?
    - dack 5y ago
      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.
      - ashtonbaker 5y ago
        Assume (accept without questioning) that it’s a property of the universe that any group of 2 horses are the same color. Now, say you have a group of 3 horses, A, B, and C. You can use your knowledge about groups of 2 horses here: A and B must be the same color because they are a group of 2 horses. B and C must be the same color for the same reason. So all the horses are the same color. You can now use the proof for groups of 3 horses to prove the same fact about groups of 4 horses, and so on. The flawed inductive proof tries to generalize this argument to all groups of n and n+1 horses. That is, assume the property is true for groups of n horses, and show that it logically follows that it’s true for groups of n+1 horses. The structure of the argument is the same as my 2/3 horses example. However, you can’t use an argument like that for any value of n, as it isn’t true for n=1. That is, it’s not true that if every group of 1 horses is the same color (a true fact in nature) then it follows that every pair of horses is the same color.
      - joppy 5y ago
        It’s more like “in a world where every group of n horses are the same colour”, no matter of whether that world is the real world or not, “prove that any group of n+1 horses are the same colour”. This inductive step proves nothing about the real world, it needs a base case to kick things off. If you can prove it true for n=5 say, then the inductive step gives you every higher number.
    - 5y ago
- deleted 5y ago
  [deleted]
- deleted 5y ago
  [deleted]
- amalcon 5y ago
  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.
- marcodiego 5y ago
  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.
- marbletiles 5y ago
  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.)
rp1 5y ago
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 5y ago
  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 5y ago
    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 5y ago
      Where exactly is my error?
      - auggierose 5y ago
        In your first sentence. What is the inductive invariant you are talking about?
        poetically 5y ago
eperdew 5y ago
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.
- 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.
zaik 5y ago
I remember this 'proof' from an exercise sheet in a first semester math class. You had to explain why the argument was wrong. I liked this one :)
dsizzle 5y ago
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_color 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 5y ago
  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 5y ago
  (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 5y ago
    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.
wombatpm 5y ago
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
- pests 5y ago
  I don't understand. How is that six legs? How is that an odd number? Am I missing a joke?
  - ars 5y ago
    forelegs means "front legs", but also sounds like "four legs". "odd number" means "strange number", and also "number not divisible by 2".
  - james_in_the_uk 5y ago
    Six legs on a horse would be very odd indeed
    - pfdietz 5y ago
      The situation could be much worse. https://www.penny-arcade.com/comic/2008/05/26/the-unhorse https://www.penny-arcade.com/comic/2008/05/26/the-unhorse
      - cl42 5y ago
        Wow, I can't believe Penny Arcade is still publishing comics. What a run!
        GhettoComputers 5y ago
        They have an expo too. https://en.wikipedia.org/wiki/PAX_(event) https://en.wikipedia.org/wiki/PAX_(event)
renewiltord 5y ago
Clearly a logical error, not a base-case error > 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. Right, but for transitivity you actually need there to be a third horse to connect h_1 and h_2. i.e. for this logical chain, you need "all the remaining horses" to be a non-empty set.
h2odragon 5y ago
All horses are the same color, on the inside. Once you get beyond the surface of the problem things are simple. and tasty.
grifball 5y ago
For understanding: this proof makes sense if you (incorrectly) assume that any two horses are the same color, because then you can take any pair of horses in an n-sized group and split it into intersecting pairs to show that theyre all the same color. With this assumption, this inductive proof would work as well.
ineedasername 5y ago
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.
thwd 5y ago
> We will show, by induction, that [for all sets] of n horses, every horse in [each] set has the same color. > Now [assume that] for all sets of n horses, every horse in [each] set has the same color. QED. This is just tautology. No further analysis needed, really. (If your proof includes your hypothesis as an assumption, then it must be a proof by contradiction.) EDIT: Before you refute, read again carefully. The assumption _is_ the hypothesis. It is not existentially quantified or set in the base case. It is the entire, universally quantified hypothesis.
- jm_l 5y ago
  Proof by inductions often involve showing that Pn implies Pn+1. That is, that a statement's truth for n implies it's truth for n+1. That's what's being done here, and it's a perfectly valid part of this type of proof.
- tomtomlapomme 5y ago
  This is how induction proof work. You prove that something is true for a base (n = 1) case then you prove that if it is true for n it has to be true for n + 1. Therefore it is true for any n. The flaw is that the second part of the proof requires n >= 2
  - thwd 5y ago
    I understand and agree but read carefully. The assumption _is_ the (entire) hypothesis. It is not existentially quantified or set in the base-case. It is the entire hypothesis.
    - ashtonbaker 5y ago
      You should read “n” as “some arbitrary n” in the quote you posted. It’s not an assumption for all n. edit: sorry, you’re right that the wording is a bit sloppy. The “n” in the first quote is “for all n” and the n in the second quote is “some specific n” or “some arbitrary n”. They’re not meant to be the same statement. I don’t think it’s a very carefully written article.
    - 5y ago
na85 5y ago
>We will show, by induction, that for any set of n horses, every horse in that set has the same color. >Now suppose for all sets of n horses, every horse in the set has the same color. "We will prove that $thing is true. Step 1: assume $thing is true" I guess I don't see what the big deal is. Of course you can befuddle someone if they don't carefully read what you wrote.
- georgeoliver 5y ago
  Originally I had the same impression as you, but I'm starting to think the author didn't actually mean to imply your step 1. Their "now suppose for all sets of n" was a poor choice of phrasing and they meant something else than what the average person would assume. For example see https://news.ycombinator.com/item?id=29445778 https://news.ycombinator.com/item?id=29445778
GhettoComputers 5y ago
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 5y ago
  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.
demetrius 5y ago
Except white horses. White horses are not horses at all (at least according to Gongsun Long)
jimbojet 5y ago
Yawn. How did this make it to the top? I thought programmers were supposed to be good at math.
- vecter 5y ago
  I don't think most programmers are "good" at math. Not to say that they're bad either or don't have the ability to get good if they put in the effort. It's just that most programmers don't learn how to prove things because only math majors in college really need to prove things.
  - Jensson 5y ago
    It could be useful if programmers actually learned how to properly prove things. That way they would realize how full of holes their code tend to be.
    - ColinWright 5y ago
      If nothing else, this thread, and others to which we have both contributed, show that the vast majority of people commenting on HN really have no idea about what maths is, no idea about how proofs work, and no real knowledge of maths beyond school algebra (if that). This isn't a criticism, they are not trained in maths, and are not trying to be mathematicians. It is an attempt to set expectations appropriately. So when contributing anything of a mathematical nature, it's useful to remember these threads.
planetsprite 5y ago
Does induction generally work for sets of n given any precondition?
- H8crilA 5y ago
  Yes. Induction is the mathematics equivalent of recursion. Well, at least if you stay within the space of finite things. Example: prove that a tree of size n has exactly n-1 edges.
schleck8 5y ago
Am I the only one who doesn't like titles this cryptic/unrelated to the topic?
fallingfrog 5y ago
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".
- SamBam 5y ago
  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.
- shkkmo 5y ago
  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.
mstade 5y ago
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.
andi999 5y ago
When reading the title I thought: wow this might be true, maybe all horses share the same skin (not fur) color.
GolDDranks 5y ago
"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 5y ago
  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 5y ago
  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.
deleted 5y ago
[deleted]
air7 5y ago
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...
amitkgupta84 5y ago
There’s a lot of confusion in this thread, and the original post. To diagnose the problem with the proof, it’s worth knowing why proof by induction works, to thereby know how it actually works, and then diagnose which part of how it’s meant to be executed isn’t actually being executed in this blog post. We need a starting point. For natural numbers, that’s Peano arithmetic. For simplicity, Peano arithmetic says that for any unary predicate P, the following is axiomatic: If P(1) And For all n > 0, P(n) => P(n+1) Then For all n > 0, P(n) Proof by induction involves formulating your hypothesis in the form “For all n > 0, P(n)”, then proving the two conjuncts “P(1)” and “For all n > 0, P(n) => P(n+1)”, and finally concluding your hypothesis by modus applied to the inductive Peano axiom for P. In this case: P(n) is “in all sets of horses of size n, all the horses in the set are the same color” The first conjunct, P(1), generally referred to as the base case, is true, and correctly recognized as such in the blog post. The second conjunct, “For all n > 0, P(n) => P(n+1)”, generally referred to as eg inductive case, is false for this P. It’s not about “would the inductive case be true if the base case were different”. There is a single proof presented in the article. It has a base case which is a true statement, and an inductive case which is a false statement. So the problem is the inductive case. You could have a different proof which, reformulating the Peano axioms a little, could look like: Base: P(1) and P(2) Inductive: For all n > 1, P(n) => P(n+1) In this different proof, let’s call this Proof 2, the base case would be false and the inductive case would be true. Maybe the author is not intending to say the base case is “wrong” in that is false, but that is “wrong” in that it should have been formulated as in Proof 2, and that the inductive case is valid when interpreted in the sense of Proof 2. But this is completely confused. Why would it have been better for the proof presented in the article be interpreted as a proof (Proof 2) that’s not presented in the article? Both proofs fail, neither is a “better” formulation. Rather than saying: the proof presented in the article should instead have be formulated in a superficially different but fundamentally equally invalid way, under which formulation the base case would be wrong. Let’s just say: the inductive case of the proof presented in the article is false.
chronolitus 5y ago
Things like this make me lose confidence not in Mathematics itself, but in the brain's ability to truly 'grasp' Math. I know I am a layman, and this particular example is peanuts to an adept, but I am sure similar examples exist at a higher level to confound the adept, and the master, and so on. Maybe past a certain level of complexity, Math is really beyond our capability for ordered thought, and only computers may proceed? Hopefully not!
hcks 5y ago
Interesting how every time a proof by induction is posted here many commenters seem absolutely stunted by it. Maybe it is time to create a "Warning: induction" tag?
k_bx 5y ago
> 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.
jhgb 5y ago
"suppose for all sets of n horses, every horse in the set has the same color." But that is clearly not true if I have a set of n horses, n-1 out of which are black and one is brown. So the premise is already wrong.
Blackstrat 5y ago
Perhaps some time with Hume’s Problem of Induction, Karl Popper, or more accessibly “Fooled by Randomness” by Taleb.

153 points by poetically 5y ago

GenerocUsername 5y ago

This case is so contrived and meaningless I am forced to believe it is satire.

vecter 5y ago
It's a common "false proof" example that's taught in many introductory college classes. I learned this in my discrete math class.

georgeoliver 5y ago

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?

TylerE 5y ago
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.
joppy 5y ago
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 5y ago
  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?
  - dack 5y ago
    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.
    - ashtonbaker 5y ago
      Assume (accept without questioning) that it’s a property of the universe that any group of 2 horses are the same color. Now, say you have a group of 3 horses, A, B, and C. You can use your knowledge about groups of 2 horses here: A and B must be the same color because they are a group of 2 horses. B and C must be the same color for the same reason. So all the horses are the same color. You can now use the proof for groups of 3 horses to prove the same fact about groups of 4 horses, and so on. The flawed inductive proof tries to generalize this argument to all groups of n and n+1 horses. That is, assume the property is true for groups of n horses, and show that it logically follows that it’s true for groups of n+1 horses. The structure of the argument is the same as my 2/3 horses example. However, you can’t use an argument like that for any value of n, as it isn’t true for n=1. That is, it’s not true that if every group of 1 horses is the same color (a true fact in nature) then it follows that every pair of horses is the same color.
    - joppy 5y ago
      It’s more like “in a world where every group of n horses are the same colour”, no matter of whether that world is the real world or not, “prove that any group of n+1 horses are the same colour”. This inductive step proves nothing about the real world, it needs a base case to kick things off. If you can prove it true for n=5 say, then the inductive step gives you every higher number.
  - 5y ago
deleted 5y ago
[deleted]
deleted 5y ago
[deleted]
amalcon 5y ago
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.
marcodiego 5y ago
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.
marbletiles 5y ago
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.)

rp1 5y ago

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 5y ago
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 5y ago
  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 5y ago
    Where exactly is my error?
    - auggierose 5y ago
      In your first sentence. What is the inductive invariant you are talking about?
      - poetically 5y ago

eperdew 5y ago

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.

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.

zaik 5y ago

I remember this 'proof' from an exercise sheet in a first semester math class. You had to explain why the argument was wrong. I liked this one :)

dsizzle 5y ago

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_color 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 5y ago
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 5y ago
(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 5y ago
  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.

wombatpm 5y ago

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

pests 5y ago
I don't understand. How is that six legs? How is that an odd number? Am I missing a joke?
- ars 5y ago
  forelegs means "front legs", but also sounds like "four legs". "odd number" means "strange number", and also "number not divisible by 2".
- james_in_the_uk 5y ago
  Six legs on a horse would be very odd indeed
  - pfdietz 5y ago
    The situation could be much worse. https://www.penny-arcade.com/comic/2008/05/26/the-unhorse https://www.penny-arcade.com/comic/2008/05/26/the-unhorse
    - cl42 5y ago
      Wow, I can't believe Penny Arcade is still publishing comics. What a run!
      - GhettoComputers 5y ago
        They have an expo too. https://en.wikipedia.org/wiki/PAX_(event) https://en.wikipedia.org/wiki/PAX_(event)

renewiltord 5y ago

Clearly a logical error, not a base-case error > 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. Right, but for transitivity you actually need there to be a third horse to connect h_1 and h_2. i.e. for this logical chain, you need "all the remaining horses" to be a non-empty set.

h2odragon 5y ago

All horses are the same color, on the inside. Once you get beyond the surface of the problem things are simple. and tasty.

grifball 5y ago

For understanding: this proof makes sense if you (incorrectly) assume that any two horses are the same color, because then you can take any pair of horses in an n-sized group and split it into intersecting pairs to show that theyre all the same color. With this assumption, this inductive proof would work as well.

ineedasername 5y ago

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.

thwd 5y ago

> We will show, by induction, that [for all sets] of n horses, every horse in [each] set has the same color. > Now [assume that] for all sets of n horses, every horse in [each] set has the same color. QED. This is just tautology. No further analysis needed, really. (If your proof includes your hypothesis as an assumption, then it must be a proof by contradiction.) EDIT: Before you refute, read again carefully. The assumption _is_ the hypothesis. It is not existentially quantified or set in the base case. It is the entire, universally quantified hypothesis.

jm_l 5y ago
Proof by inductions often involve showing that Pn implies Pn+1. That is, that a statement's truth for n implies it's truth for n+1. That's what's being done here, and it's a perfectly valid part of this type of proof.
tomtomlapomme 5y ago
This is how induction proof work. You prove that something is true for a base (n = 1) case then you prove that if it is true for n it has to be true for n + 1. Therefore it is true for any n. The flaw is that the second part of the proof requires n >= 2
- thwd 5y ago
  I understand and agree but read carefully. The assumption _is_ the (entire) hypothesis. It is not existentially quantified or set in the base-case. It is the entire hypothesis.
  - ashtonbaker 5y ago
    You should read “n” as “some arbitrary n” in the quote you posted. It’s not an assumption for all n. edit: sorry, you’re right that the wording is a bit sloppy. The “n” in the first quote is “for all n” and the n in the second quote is “some specific n” or “some arbitrary n”. They’re not meant to be the same statement. I don’t think it’s a very carefully written article.
  - 5y ago

na85 5y ago

>We will show, by induction, that for any set of n horses, every horse in that set has the same color. >Now suppose for all sets of n horses, every horse in the set has the same color. "We will prove that $thing is true. Step 1: assume $thing is true" I guess I don't see what the big deal is. Of course you can befuddle someone if they don't carefully read what you wrote.

georgeoliver 5y ago
Originally I had the same impression as you, but I'm starting to think the author didn't actually mean to imply your step 1. Their "now suppose for all sets of n" was a poor choice of phrasing and they meant something else than what the average person would assume. For example see https://news.ycombinator.com/item?id=29445778 https://news.ycombinator.com/item?id=29445778

GhettoComputers 5y ago

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

demetrius 5y ago

Except white horses. White horses are not horses at all (at least according to Gongsun Long)

jimbojet 5y ago

Yawn. How did this make it to the top? I thought programmers were supposed to be good at math.

vecter 5y ago
I don't think most programmers are "good" at math. Not to say that they're bad either or don't have the ability to get good if they put in the effort. It's just that most programmers don't learn how to prove things because only math majors in college really need to prove things.
- Jensson 5y ago
  It could be useful if programmers actually learned how to properly prove things. That way they would realize how full of holes their code tend to be.
  - ColinWright 5y ago
    If nothing else, this thread, and others to which we have both contributed, show that the vast majority of people commenting on HN really have no idea about what maths is, no idea about how proofs work, and no real knowledge of maths beyond school algebra (if that). This isn't a criticism, they are not trained in maths, and are not trying to be mathematicians. It is an attempt to set expectations appropriately. So when contributing anything of a mathematical nature, it's useful to remember these threads.

planetsprite 5y ago

Does induction generally work for sets of n given any precondition?

H8crilA 5y ago
Yes. Induction is the mathematics equivalent of recursion. Well, at least if you stay within the space of finite things. Example: prove that a tree of size n has exactly n-1 edges.

schleck8 5y ago

Am I the only one who doesn't like titles this cryptic/unrelated to the topic?

fallingfrog 5y ago

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

SamBam 5y ago
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.
shkkmo 5y ago
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.

mstade 5y ago

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.

andi999 5y ago

When reading the title I thought: wow this might be true, maybe all horses share the same skin (not fur) color.

GolDDranks 5y ago

"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 5y ago
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 5y ago
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.

deleted 5y ago

[deleted]

air7 5y ago

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

amitkgupta84 5y ago

There’s a lot of confusion in this thread, and the original post. To diagnose the problem with the proof, it’s worth knowing why proof by induction works, to thereby know how it actually works, and then diagnose which part of how it’s meant to be executed isn’t actually being executed in this blog post. We need a starting point. For natural numbers, that’s Peano arithmetic. For simplicity, Peano arithmetic says that for any unary predicate P, the following is axiomatic: If P(1) And For all n > 0, P(n) => P(n+1) Then For all n > 0, P(n) Proof by induction involves formulating your hypothesis in the form “For all n > 0, P(n)”, then proving the two conjuncts “P(1)” and “For all n > 0, P(n) => P(n+1)”, and finally concluding your hypothesis by modus applied to the inductive Peano axiom for P. In this case: P(n) is “in all sets of horses of size n, all the horses in the set are the same color” The first conjunct, P(1), generally referred to as the base case, is true, and correctly recognized as such in the blog post. The second conjunct, “For all n > 0, P(n) => P(n+1)”, generally referred to as eg inductive case, is false for this P. It’s not about “would the inductive case be true if the base case were different”. There is a single proof presented in the article. It has a base case which is a true statement, and an inductive case which is a false statement. So the problem is the inductive case. You could have a different proof which, reformulating the Peano axioms a little, could look like: Base: P(1) and P(2) Inductive: For all n > 1, P(n) => P(n+1) In this different proof, let’s call this Proof 2, the base case would be false and the inductive case would be true. Maybe the author is not intending to say the base case is “wrong” in that is false, but that is “wrong” in that it should have been formulated as in Proof 2, and that the inductive case is valid when interpreted in the sense of Proof 2. But this is completely confused. Why would it have been better for the proof presented in the article be interpreted as a proof (Proof 2) that’s not presented in the article? Both proofs fail, neither is a “better” formulation. Rather than saying: the proof presented in the article should instead have be formulated in a superficially different but fundamentally equally invalid way, under which formulation the base case would be wrong. Let’s just say: the inductive case of the proof presented in the article is false.

chronolitus 5y ago

Things like this make me lose confidence not in Mathematics itself, but in the brain's ability to truly 'grasp' Math. I know I am a layman, and this particular example is peanuts to an adept, but I am sure similar examples exist at a higher level to confound the adept, and the master, and so on. Maybe past a certain level of complexity, Math is really beyond our capability for ordered thought, and only computers may proceed? Hopefully not!

hcks 5y ago

Interesting how every time a proof by induction is posted here many commenters seem absolutely stunted by it. Maybe it is time to create a "Warning: induction" tag?

k_bx 5y ago

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

jhgb 5y ago

"suppose for all sets of n horses, every horse in the set has the same color." But that is clearly not true if I have a set of n horses, n-1 out of which are black and one is brown. So the premise is already wrong.

Blackstrat 5y ago

Perhaps some time with Hume’s Problem of Induction, Karl Popper, or more accessibly “Fooled by Randomness” by Taleb.