Find the mistake in the following proof that all dogs are the same color (if there's any):

Let's use induction. Consider groups of 1 dog. All dogs of every group are the same color, of course. So we now that it's true for 1. Suppose it's true for groups of k dogs, i.e. every group of k dogs are the same color. Then let's consider any group A of k+1 dogs. Consider a subgroup of A containing k dogs. Let's call x the dog in A but not in the subgroup. Then by induction, all dogs in the subgroup are the same color. Now consider a subroup of A of k dogs, with x in the subgroup. All dogs except for x are the same color. Then, since every group of k dogs are the same color (by induction), all dogs in A are the same color. So x and every dog are the same color.

Unlike some of you pointed out, this is not a misuse of mathematical induction at all. As to the claim about dogs not being well-ordered.... what matters, I believe is that sets of dogs can be well ordered. Your induction, then, functions on sets of sets of dogs. But I digress.

Really the only flaw there is is this one line:

"Then, since ever group of k dogs are the same color (by induction) [true so far], all dos in A are the same color."

The second clause does not follow from the first when k=1 (exactly when it matters). Just because every dog in a set is the same color as itself does not mean all dogs in the set are the same color as all the other dogs.  Since this is used to go from p(n-1) to p(n), invalidates the whole argument.

Posted by FB on 2004-11-30 07:07:07