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.

P(n) denotes "All dogs in a set of order n are the same color".<br>

Clearly, the basis step P(1) is true.<br>

For the induction step we have a set S with |S| = k+1 and we wish to prove there exists subsets, S1 and S2, of S such that<br>

(1) |S1| = |S2| = k<br>

(2) Union(S1,S2) = S<br>

(3) Intersection(S1,S2) is not empty<br>

This holds for all k > 1. But, for the induction step to work it must hold for k = 1 also.<br>

Let S = {a,b}. Power-set(S) = { empty , {a} , {b} , S }.<br>

S and the empty subset fail (1).<br>

{a} and {b} pass (1) and (2), but fail {3}.<br>

Therefore, all we can say is P(1) is true.<br>

I first saw this thirty years ago in an abstract algebra class. I think it was an exercise in  the book "Algebra" by MacLane and Birkoff.<br>

Posted by Bractals on 2005-02-16 01:15:35