# Does induction sometimes allow false statements to be proven correctly?

1. Aug 12, 2012

### p6.626x1034js

so i was reading an old thread that mentioned the following problem from Apostol's Calculus I

I'm not sure if I my solution is correct, so I am posting it here for opinions:

The inductive step is correct, i.e. if it can be shown that the theorem holds for n=3, then the theorem is true.

The inductive step starts by assuming that the theorem holds for n=3.
I claim that this assumption is equivalent to the following:
⇔all members of any set of 3 blonde girls have blue eyes if at least one in every set has blue eyes
⇔all members of any set of 3 blonde girls have blue eyes if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes (because we can take one blonde girl with blue eyes and make her a member of every set)
⇔all blonde girls have blue eyes if at least one blonde girl if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes
⇔all members of any set of 1 blonde girl have blue eyes if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes

That is, I claim that the assumption that the theorem holds for n=3 is equivalent to the assumption that every blonde girl has blue eyes, if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes. This is only the assumption part.

To prove a theorem by mathematical induction,
(1)a base case must be shown to be correct and
(2)it must be shown that assuming that the theorem holds for n =k it also holds for n =k +1.

In the theorem, these translate into:
(1)base case for n=1 is obviously correct
(2)inductive step: Assuming that "every blonde girl has blue eyes, if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes" then the theorem holds for n =k +1. (here I substituted the hypothesis with the equivalent statement)

Therefore, the theorem is correct only if the condition "every blonde girl has blue eyes if at least one girl (in the WHOLE UNIVERSAL SET) has blue eyes" is satisfied.

Is my reasoning valid?

Regards

2. Aug 12, 2012

### Alesak

It is helpful to have exact theorem of induction method here:

Code (Text):
Let S(n) be some statement for n natural and assume:

1) S(1) is valid

2) S(k) true implies S(k+1) true.

Then S(n) is true for all n.

From this you can see that you can assume for n=3 that S(3) is "G1, G2, G3 have blue eyes" and no S(n) here reads "G1, G2, G4 have blue eyes" so you cannot use it as an assumption.

3. Aug 12, 2012

### Hurkyl

Staff Emeritus
You seem to have misread the argument.

The inductive step assumes it's true for n=k and (allegedly) proves it's true for n=k+1.

The n=3 case was merely an example of the argument being made.

4. Aug 12, 2012

### Hurkyl

Staff Emeritus
In the argument under consideration, S(n) is "Given any collection of n blonde girls. If at least one of the girls has blue eyes, then all n of them have blue eyes."

5. Aug 12, 2012

### Hurkyl

Staff Emeritus
Incidentally, the problem with this argument is not a particularly complicated one. When you actually identify the problem, it should be obvious that you have found the flaw.

The trick is actually spotting it.

The trick is that the error occurs in a (possibly) surprising location of the argument. Furthermore, the argument is cleverly presented in a fashion that distracts the easily distracted.

6. Aug 12, 2012

### Alesak

Found the error! Really simple and clever! Now I will annoy all my friends with this problem.

I missed that, thanks.

EDIT: I got the solution wrong, I thought that S(1) doesn't hold, but it probably does.

Last edited: Aug 12, 2012
7. Aug 12, 2012

### p6.626x1034js

it looks like my solution is not satisfying hehe

8. Aug 12, 2012

### p6.626x1034js

so, i still cannot figure out the error. Please enlighten me.

9. Aug 12, 2012

### uart

The inductive step $P_k \rightarrow P_{k+1}$ should hold for all $k \ge 1$ (or in general >= whatever base case you choose). Can you see the value of "k" for which the inductive step is invalid?

10. Aug 12, 2012

### p6.626x1034js

Thank you!

no, the implication $P_1 \rightarrow P_{2}$ is not true (if there exists a set of 1 blonde girl whose member does not have blue eyes).

Is the following proof convincing?

Suppose, that $P_1 \rightarrow P_{2}$ if there exists a set of 1 blonde girl whose member G1 does not have blue eyes. G1 can be paired with any other girl in the universal set. The existence of such set would contradict $P_{2}$. Therefore, $P_{1}\rightarrow P_{2}$ does not hold if there exists a set of 1 blonde girl whose member G1 does not have blue eyes.

11. Aug 12, 2012

### Alesak

Well there still must be the error in the induction itself. There is no reason we could not start from 1, if for 1 it's true.

12. Aug 12, 2012

### p6.626x1034js

yes, we can start from n =1. This completes the first step of the proof. However, a proof by induction requires 2 statements, which you outlined in your first post, to be true.

Both statements MUST be true. however, in this theorem, statement (2) does not hold for some k (k=1), that is $P_{k} \rightarrow P_{k+1}$ is not true when k =1 (the second step requires that statement (2) be valid for all k ≥1). therefore, the second step is invalid for k=1 but valid for any other k ≥2.

13. Aug 12, 2012

### Alesak

But in general, it is not necessary to check induction step from k=1 to k=2. So why it should be necessary here?

14. Aug 12, 2012

### p6.626x1034js

i think, in general, it is necessary.

"domino" analogy: even if the first domino falls, if it does not cause the second domino to fall, then one cannot guarantee that the rest of the dominoes would fall.

15. Aug 12, 2012

### Alesak

But is not necessary to check the step from the first domino to second, once you checked kth domino will cause the k+1th domino to fall. And I still don't see the problem in Apostols general proof. Maybe the problem is that his proof requires at least k=2 to make sense.

16. Aug 12, 2012

### p6.626x1034js

yes, the inductive step does require k ≥2 to be valid, and if that's the case, the base case should be k =2 not k=1; and even if we use the base case k=2, the theorem still cannot be proven

base case k =1:
the proof is flawed because it fails to carry out the inductive step
(1)S(1) is valid but
(2)S(k) true DOES NOT imply that S(k+1) true [because S(1) does not imply S(2) (just one counterexample makes the whole statement false)]

in other words, the implication in step (2) is generally FALSE because we found a counterexample. but it is true for n ≥2

base case k =2
even if the inductive step is true, the proof cannot be carried out because the base case k=2 does not hold
case k=2 is false because there exists a pair of blonde girls one of whom does not have blue eyes

therefore, the theorem is false

domino analogy:
Suppose the first one falls but the the second one does not. It is still possible that a kth domino falls and causes all the rest to fall. In that case, the theorem holds only for n ≥k but not for n =1 to n =k-1

But in this problem, only k =1 falls; but we CANNOT force any other domino to fall.

17. Aug 12, 2012

### Alesak

Fair enough. Is that what you had in mind Hurkyl?

18. Aug 12, 2012

### Hurkyl

Staff Emeritus
I think the two of you were saying the same thing, just looking at it in different directions so you were talking past each other.

Yah, it's what I had in mind. The problem was the implied argument for the inductive step is only valid for k > 1.

(although, as p6 points out, while the argument is invalid, the conclusion could still be valid in the right circumstances)

As inductive arguments are commonly split by having the base case cover the "small" situation and the inductive step covering the "large" situation, it takes extra mental effort think of the inductive step in the small situation. The presentation helps get your mind thinking about the inductive step for "large" k, making it extra difficult to rewind back to think about the inductive step in the small k case.

This is a real concern in realistic arguments. It is not terribly uncommon for an intuitive argument to work in the large case, but fail for a wide variety of small cases, and analyzing the small cases can sometimes be pretty tough.

Inductive arguments have the potential to be extra trappy, because for the simple examples one learns the notion on, the base case is usually only the smallest case and the inductive step works for everything else. So, it's somewhat surprising to encounter an inductive step like the one in the opening post where you have to have to cover both 1 and 2 in the base case.

Last edited: Aug 13, 2012
19. Aug 13, 2012

### Stephen Tashi

This will be a digression, but it addresses ithe title of the thread.

Is the principle of induction an assumption or a theorem?

If we know (somehow) that the principle of induction can never be used to prove false statements then the principle of induction is a theorem. Otherwise, it is an assumption.

20. Aug 13, 2012

### jgens

If you construct the natural numbers via the von Neumann ordinals (you actually only need to focus on the finite ordinals and ω), then you get well-ordering automatically and this allows you to prove the principal of mathematical induction. Any other construction of the natural numbers should also furnish a proof of the inductive principle.