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.

"k dogs" ???? hahaha.... This one is SO EASY to shoot down !!!!! You wrote "Now consider a subroup of A of k dogs, with x in the subgroup." You meant a PROPER SUBGROUP of k, and if k=1, there is no PROPER SUBGROUP of k. So the logical leap from k dogs to k+1 dogs ONLY WORKS if k is GREATER than 1. It's obvious that if we could somehow prove that every group of 2 dogs is the same color, then we could prove that ALL dogs are the same color. But we cannot. All we can prove is that every group of 1 dogs is the same color, and we are hounded by the dogged impossibility of going logically from 1 dog to a pack of dogs. I must say that this particular paradox was definitely a horse of a different color !!!!

Posted by Dan on 2003-09-19 19:20:11