Dog Colors (an inductive proof)

[thenava]

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 d₁, d₂, ..., d_n, d_n+1. Let D₁ be the subset of D consisting of d₁, d₂, d₃, ..., d_n and let D₂ be the subset of D consisting of d₂, d₃, ..., d_n, d_n+1. D₁ and D₂ are sets with n dogs each. Hence, by the inductive hypothesis, all dogs in D₁ have the same color, and all dogs in D₂ have the same color. Since D₁ and D₂ share d₂ as an element, we conclude that all dogs in D have the same color, that of d₂.

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 d₂ is a common element between both sets, therefore all must be the same color as d₂. However, d₃, d₄, ..., and d_n are also common to both sets, and the induction could be done on either of those dogs. If d₂ is brown and d₅ 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!

 

[CRGreathouse]

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

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 d₂ is a common element between both sets, therefore all must be the same color as d₂. However, d₃, d₄, ..., and d_n are also common to both sets, and the induction could be done on either of those dogs. If d₂ is brown and d₅ 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!

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.

 

[Rogerio]

Your inductive step is valid only for n>1.
So, your first step should be the proof for n=2.

 

[thenava]

Hey thanks for the help CRGreathouse, and Rogerio.