Does induction sometimes allow false statements to be proven correctly?

[p6.626x1034js]

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

Describe the fallacy in the following "proof" by induction:

Theorem: 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.

Proof: The statement is obviously true for n = 1. The step from k to k+1 can be illustrated by going from n = 3 to n = 4. Assume, therefore, that the statement is true for n = 3 and let G1,G2,G3,G4 be four blonde girls, at least one of which, say G1, has blue eyes. Taking G1,G2, and G3 together and using the fact that the statement is true when n = 3, we find that G2 and G3 also have blue eyes. Repeating the process with G1,G2 and G4, we find that G4 has blue eyes. Thus all four have blue eyes. A similar argument allows us to make the step from k to k+1 in general.

Corollary: All blonde girls have blue eyes.

Proof: Since there exists at least one blonde girl with blue eyes, we can apply the foregoing result to the collection consisting of all blonde girls.

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

 

[Alesak]

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

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.

 

[Hurkyl]

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.

 

[Hurkyl]

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.

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."

 

[Hurkyl]

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.

Spoiler

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.

 

[Alesak]

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

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."

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

 

[p6.626x1034js]

thanks for your replies
it looks like my solution is not satisfying hehe

 

[p6.626x1034js]

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.

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

 

[uart]

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

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?

 

[p6.626x1034js]

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?

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.

 

[Alesak]

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?

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.

 

[p6.626x1034js]

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.

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.

 

[Alesak]

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.

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

 

[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.

 

[Alesak]

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.

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.

 

[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 eyestherefore, 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.

 

[Alesak]

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

 

[Hurkyl]

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.

 

[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.

 

[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.

 

[Alesak]

...

I've never encountered this problem in induction, but it's certainly good to keep it in mind.

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.

I've got General topology from Willard and he gives it as theorem - basicaly this:

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.

Proof is by contradiction. Suppose there exists nonempty set of natural numbers where S(k) doesn't hold. Then this set must have the smallest number n, by well-ordered property of naturals. Since n is the smallest number where S(k) is false, S(n-1) is true. But by 2) assumption S(n) must by true. Hence contradiction.

It supposedly works for any ordinal number (can I say set N is ordinal number? Ordinal number is set with well-order, right? I don't understand why it is called "number" when it is in fact set).

 

[Hurkyl]

It supposedly works for any ordinal number (can I say set N is ordinal number? Ordinal number is set with well-order, right? I don't understand why it is called "number" when it is in fact set).

An ordinal number "is" a transitive well-ordered set in the same sense that the natural number 5 "is" {0,1,2,3,4}.It's a general mathematical principle that absolute "is" questions are not really important: the meaningful aspect of what something "is" is what you can do with such an object and how it relates to other objects. Representing an ordinal number by exhibiting a transitive well-ordered set whose order type is quantified by that ordinal number is just that -- a representation.

Of course, it is a sufficiently convenient representation that it is usually used without comment. Incidentally, the same is true in set theory about natural numbers: one generally uses "5" and {0,1,2,3,4} synonymously without making any comment on it.

(it may be of interest to look up "model theory")

It's not all that different from the fact that people generally don't distinguish between the natural number "5" and the real number "5".Anyways, ordinal numbers are called numbers, presumably, because they are the extension of the natural numbers you need to quantify well-order types, and you can do (ordinal) arithmetic with them.Honestly, if it weren't for the fact I'd probably confuse people, there are situations where I would even call things like vector spaces "numbers". e.g. in algebraic topology, properties of interest (e.g. the homology) are often quantified by vector spaces, and there is a sort of arithmetic you can do with vector spaces. Just to be clear, I'm talking about the vector spaces themselves, not individual vectors.