Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dog Colors (an inductive proof)

  1. Mar 31, 2009 #1
    I didn't really know where else to post this, it has a set, so I figured here would be the best place. The question is to find the flaw in this argument.

    Claim: In every set of n dogs, all dogs have the same color.
    Proof: By induction on n.

    Basis: Take n = 1. In every set containing one dog, all dogs in that set must have the same color.

    Inductive Step: Assume that in every set of digs with n dogs, all dogs in that set have the same color. We will show that in every set of dogs with n + 1 elements, all dogs in that set have the same color. Let D be a set consisting of the dogs d1, d2, ..., dn, dn+1. Let D1 be the subset of D consisting of d1, d2, d3, ..., dn and let D2 be the subset of D consisting of d2, d3, ..., dn, dn+1. D1 and D2 are sets with n dogs each. Hence, by the inductive hypothesis, all dogs in D1 have the same color, and all dogs in D2 have the same color. Since D1 and D2 share d2 as an element, we conclude that all dogs in D have the same color, that of d2.

    I have two ideas as to why this may be false:

    1. The inductive hypothesis is improperly stated, and therefore the proof is false.
    2. The proof only states that d2 is a common element between both sets, therefore all must be the same color as d2. However, d3, d4, ..., and dn are also common to both sets, and the induction could be done on either of those dogs. If d2 is brown and d5 is white, all the dogs would have to be both brown and white, and therefore the proof fails.

    I would greatly appreciate it if anyone could verify my arguments or point any flaws in my arguments. Thanks!
  2. jcsd
  3. Mar 31, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    I think the usual name for this is "all horses are the same color", if you need to Google for it.

    The base assumption is correct.

    The problem with the inductive step is not that there are elements beside d_2 in common, but that d_2 may not be in common (if n = 1). If the assumption held for n = 2 dogs (it doesn't) then it would hold for any n.
  4. Mar 31, 2009 #3
    Your inductive step is valid only for n>1.
    So, your first step should be the proof for n=2.
  5. Mar 31, 2009 #4
    Hey thanks for the help CRGreathouse, and Rogerio.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook