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.(adsbygoogle = window.adsbygoogle || []).push({});

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_{1}, d_{2}, ..., d_{n}, d_{n+1}. Let D_{1}be the subset of D consisting of d_{1}, d_{2}, d_{3}, ..., d_{n}and let D_{2}be the subset of D consisting of d_{2}, d_{3}, ..., d_{n}, d_{n+1}. D_{1}and D_{2}are sets with n dogs each. Hence, by the inductive hypothesis, all dogs in D_{1}have the same color, and all dogs in D_{2}have the same color. Since D_{1}and D_{2}share d_{2}as an element, we conclude that all dogs in D have the same color, that of d_{2}.

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_{2}is a common element between both sets, therefore all must be the same color as d_{2}. However, d_{3}, d_{4}, ..., and d_{n}are also common to both sets, and the induction could be done on either of those dogs. If d_{2}is brown and d_{5}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!

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Dog Colors (an inductive proof)

**Physics Forums | Science Articles, Homework Help, Discussion**