Question

Determine what is wrong with the following “proof” by induction that all dogs are the same breed. Theorem 1. All dogs are the same breed. Proof. For each natural number, let P(n) be the statement “any set of n dogs consists entirely of dogs of the same breed.” We demonstrate that for each natural number n, P(n) is true. P(1) is true, because a set with only one dog consists entirely of dogs of the same breed. Now, let k be any fixed, arbitrary natural number and suppose P(k) is true, i.e., every set of k dogs consists of dogs of the same breed. Let D be a set of k + 1 dogs, where D = {d1, d2, . . . , dk, dk+1} and each di is a dog. If dog d1 is removed from D, then we have a set D1 of k dogs. By the inductive hypothesis, the dogs in D1 have the same breed. Now, if dog dk+1 is removed from D, then we have set D2 of k dogs. Again by the inductive hypothesis, the dogs in D2 have the same breed. Because D1 and D2 overlap, all k + 1 dogs must be of the same breed. This shows P(k + 1) is true. Therefore, by mathematical induction, for all natural numbers n, any set of n dogs consist entirely of dogs of the same breed.

Answer 1

The inductive case is not true completely.

For ,  the set has two dogs. If you remove one, you get and if you remove the other you get . But that is, they do not overlap which cannot guarantee that the breeds are the same. This implies that is not true and the rest induction breaks apart.