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.

Induction assumes that there is a set S with a least element (Well Ordering Principle). Induction, in breif, generalizes that a set S is equivalent to N (natural numbers, of course) if and only if every element in S is generated by stepwise combinations of the least element.

To use induction in a formal proof, one must establish a set, a property p(n), and a least element of the set S (call it 1) such that p(1) is true. Then by assuming p(n-1) is true, it must follow that p(n) is true (or equivically, if p(m) is true for all m between 1 and n are true (left inclusive), then p(n) must be true).

Quite clearly, this proof does not correctly use induction because there is no least element of the set in question. In other words, it is never esablished that a set of k dogs has a "least" dog from which the other dogs are generated.

--Graatz

Posted by Jeff on 2003-12-23 20:42:46