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}. Powerset(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 20050216 01:15:35 