https://jeremykun.com/2011/07/16/false-proof-all-horses-are-the-same-color/ Math [?] Programming Navigation Skip to content * Home * Main Content * Primers * Research * Program Gallery * Proof Gallery * About the Author * Support Post navigation - Graph Coloring, or Proof by Crayon False Proof - The Reals are Countable - False Proof - All Horses are the Same Color Posted on July 16, 2011 by j2kun Problem: Show that all horses are of the same color. "Solution": We will show, by induction, that for any set of n horses, every horse in that set has the same color. Suppose n=1, this is obviously true. Now suppose for all sets of n horses, every horse in the set has the same color. 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. [hr]Explanation: The argument here is valid for almost all n. For large n, it is a very natural argument that follows from the inductive hypothesis. However, it fails for n=2 (and this is the only time it fails). By having only two horses, we cannot conclude that the removed horses have the same color, because there aren't any horses remaining in H to apply the transitivity of "having the same color as." 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. Share this: * Click to share on Facebook (Opens in new window) * Click to share on Reddit (Opens in new window) * Click to share on Twitter (Opens in new window) * More * * Click to email this to a friend (Opens in new window) * Click to share on Pinterest (Opens in new window) * * Click to share on LinkedIn (Opens in new window) * Click to share on Tumblr (Opens in new window) * * Like this: Like Loading... This entry was posted in Proof Gallery and tagged false proof, induction. Bookmark the permalink. Post navigation - Graph Coloring, or Proof by Crayon False Proof - The Reals are Countable - 9 thoughts on "False Proof - All Horses are the Same Color" 1. [7ce67] Mitchell Kaplan July 23, 2012 at 12:06 pm Reply I enjoyed your "proof", but I'd suggest a revision to the reason it's invalid. I don't think it's so much that you need to consider the case of 2 horses. What the proof does, is not the normal sort of induction that I've seen. Typically you show it's true for n=1 (which in the horse proof is trivial). Then you assume that it's true for n, and then show that this means it's true for n+1. You can't do that in this horse of a different color proof. If you assume it's true for n, you really don't have any way of getting to n+1. To start by assuming that it's true for ANY collection of n+1, you're begging the question. In any case, I still have to say that I enjoyed reading it. LikeLike + [90b17] j2kun July 23, 2012 at 12:17 pm Reply The proof fails for n=2 because the general argument works precisely when there are at least three horses. In particular, there has to be a horse which was not removed in order to conclude that the two removed horses share its color. Rest assured that this is a standard induction argument, and I don't assume anything about the set of n+1 horses (H in the above proof). So in fact, if it were true that any set of n = 3 horses is unicolored, then it would be true that any set of n > 3 horses is unicolored. LikeLike 2. [7ce67] mitchell Kaplan July 23, 2012 at 8:41 pm Reply You're right, I misread your "proof". For some reason I thought I read that you started with the assumption about n+1 horses. Must have been before I had my coffee. LikeLike 3. [ed5be] bubchi89 January 17, 2014 at 12:57 am Reply @mitchellkaplan You actually hinted at another common mistake with induction (not sure if j2kun has another false proof demonstrating it): 1. Take the case with n+1 2. Reduce it to the case with n (incorrectly!) 3. Apply the induction hypothesis on the reduced case 4. Expand the case with n to the case with n + 1 For example, I remember seeing this in graph-related proofs where you would remove a node from the graph except the resulting graph didn't satisfy certain constraints (and hence the induction hypothesis did not apply to it!). Another similar mistake is to take the n case and make the erroneous claim that every n+1 case can be extended from a n case. I also saw this with respect to graphs where not every graph with constraint "Foo" and n+1 nodes could be constructed from a graph with constraint "Foo" and n nodes. Induction's pretty hard? LikeLike 4. [d55f2] Rose Myers August 11, 2016 at 5:32 am Reply Before I read the explanation, I had deduced that the problem was with the case of n = 1, because you need at least two different things in order for "same as" to make sense. (Never trust a proof that uses "obviously" or trivially".) LikeLike + [90b17] j2kun August 11, 2016 at 8:22 am Reply I disagree, because I am certainly the same height as myself, as am I the same age and weight and myself. I don't see why that is invalid to say. LikeLike o [d55f2] Rose Myers August 11, 2016 at 8:56 am OK. I guess x = x is legitimate. Perhaps my unease with it has to do with rhetorical tautologies being frowned upon. LikeLike 5. [5290d] jhnbyrn October 4, 2019 at 12:53 pm Reply "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" So, I should suppose the thing that you are about to prove? LikeLike + [90b17] j2kun October 7, 2019 at 8:34 pm Reply This is how induction works. Here n is a fixed number, and you're using it to prove the statement holds for n+1. LikeLike Leave a Reply Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] WordPress.com Logo You are commenting using your WordPress.com account. ( Log Out / Change ) Google photo You are commenting using your Google account. ( Log Out / Change ) Twitter picture You are commenting using your Twitter account. ( Log Out / Change ) Facebook photo You are commenting using your Facebook account. ( Log Out / Change ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] Search [ ] [Search] A Programmer's Introduction to Mathematics Buy my book, which teaches programmers how to engage with mathematics. Every chapter includes an application, from cryptography to economics, physics, neural networks, and more! Github repositoryMedium @jeremyjkun[twitter1-e1500589540515] RSS * RSS - Posts * Follow Following + [ffc085] Math [?] Programming Join 20,355 other followers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [ffc085] Math [?] Programming + Customize + Follow Following + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar Send to Email Address [ ] Your Name [ ] Your Email Address [ ] [ ] loading [Send Email] Cancel Post was not sent - check your email addresses! Email check failed, please try again Sorry, your blog cannot share posts by email. %d bloggers like this: [b]