Find the error in the “proof” that Apostol gives that all blonde girls have blue eyes. See I.4.4, Exercise #12, in Volume 1 for a statement of the false proof.
This proof assumes that the statement is true for
, i.e., it assumes that if there are three blonde girls one of which has blue eyes, then they all have blue eyes. Clearly, this is a false assumption.
The correct solution is to say that the set of blonde girls with is not an inductive set, since addition is no defined for blonde girls with blue eyes, hence we cannot apply the proof by induction.
As others pointed out, that’s not the reason why this proof by induction is wrong. Of course that, by our experience (in real life), the assertion being made is clearly a false one. But that’s not why the proof is incorrect.
This proof by induction (with a fallacy) is adapted from an example by the Hungarian mathematician, George Pólya. In his example, he proved (with a fallacy) that there is no horse of a different color ahah :-)
I do not think this solution is correct. The problem is with the base case. The induction hypothesis is ok. We cannot make the induction base case with the group of size 1. In fact, the base case here should be for n=2.
If we could prove that in a set of 2 blonde girls, when 1 has blue eyes the second one necessarily has blue eyes, then all blonde girls have blue eyes as in the example. However, in the set of 2 blondes, they both do not necessarily have blue eyes, in case 1 has. Thus, the base step with n=2 is incorrect. And n=1 is not a base step since it does not refer to a group.
It is the same as with fibonacci numbers. The case n=1 does not exist (here n=1 is not a group). The induction base case starts at n=2.
Hi! I don’t think this solution is correct, as we may not know whether our assumptions in any other exercises are correct or not.
An assumption cannot be wrong, as it still is a required procedure for the method of induction i.e. you HAVE to assume it is not false. For example, take an arbitrary claim, which is to be proven by the method of induction. How will we know whether the step, where we assume the claim is true for a value k, is correct or not? I think that in this case, we have to point out a logical flaw NOT in the assumption, but in the process of proving that k+1 yields what is not expected.
This problem is very similar to the “all horses have the same color” problem, by the same person who posed this question. (Link: https://en.wikipedia.org/wiki/All_horses_are_the_same_color)
SOLUTION: For the set of girls with n members, n=1, we have all girls with blue eyes. (given in the question).
Assume this statement to be true: For the set of girls with n members, n=k, assume that they all have blue eyes.
Now, for the set of girls with n members, n=k+1, we can separate them in two sets, the first k number of girls and the last k number of girls (i.e. first set doesn’t contain the newly added member whereas the second set doesn’t contain the first member). From our assumption, the first set must have all girls with blue eyes, as it has k number of girls and we know that it has at least one girl with blue eyes, as required by the question. Therefore, the second set has at least one blue girl because the first and the second set overlap, meaning that the second set, also with k number of girls, have blue eyes (This is also the method used in the book, to prove that the asserted statement is true). Therefore all girls have blue eyes…
HOWEVER, this logic assumes that the first set and the last set overlap. And while this is true for pretty much any big set, it is not true for the set of girls with n members, n=2 (i.e. going from n=1 to n=2 illustrative of the process of going from k to k+1). Here the first set of girls (i.e. the first girl) consists of only 1 member, who has blue eyes, cause we must have one girl with blue eyes as a requirement from the question. However the second set also consists of one girl (the added member), who may or may not have blue eyes. In this case, the two sets do not overlap, and hence, we cannot say that this second set has at least one girl with blue eyes, which means that this added member does not necessarily have blue eyes. This is the error in the ‘proof’.
Please let me know if I don’t make sense or if any of my arguments are incorrect.
Thanks
Nevermind, I get it now! The inductive step does not work assuming n = 1.
This solution is incorrect. The ‘proof’ illustrates how to prove n + 1 from the induction hypothesis, and just happens to use the case n = 3 as an example.