Point out the flaw in a proof by induction.

[htirwin]

This is from a lecture where the professor gave an example of a flawed proof by induction, let the students try to figure what was wrong, and then explained the problem.

There is one issue with the professors logic that seems flawed to me, but it might just be a case of ambiguity, or a mistake in communicating the information. I'll talk about that later.

So here it is, point out the flaw, and then I'll explain the professor's explanation.

Predicate( P(n) ): in any set of n people, all people in the set have the same hair color.

Proof: by induction

Base Case: P(1), in a set of 1 person, all people in the set have the same hair color. Check

Inductive Step: show P(n) -> P(n+1)

Assume P(n) is true for some arbitrary n >= 1. That is, the people in the set have the same hair color, and the set is of size n.

Then, pers_1, pers_2, ... pers_n are all people in a set of size n, with the same hair color.

And pers_2, pers_3 ... pers_n+1 are also a set of size n and so they each have the same hair color.

Therefore hair_color(pers_1) = hair_color(pers_2) = hair_color(pers_n) = ... = hair_color(pers_n+1).

Q.E.D.

[Catfish4]

The "hair color" property isn't right by itself.
It should rather be: a set of n people genetically engineered to have the same hair color. Then the proof works.

[abhishekm71]

I think the base condition should be P(2) because in the inductive step we are taking (n-1) people from the original set and then adding an (n+1)th individual to make a total of n people.

[firedraco]

Then, pers_1, pers_2, ... pers_n are all people in a set of size n, with the same hair color.

Look at this. From your P(n), it means all the people in this set have the same hair color (call it C1).

And pers_2, pers_3 ... pers_n+1 are also a set of size n and so they each have the same hair color.

And from P(n) this means they also have the same color (call it C2).

You then need to prove C1 = C2, which is impossible. (The proof given already assumes this, even though you must prove it)

[htirwin]

@ firedraco, They have elements in common namely pers_2, which means C1 = C2. But as abhishekm71 pointed out, the issue is that the inductive step isn't applicable for the base case n = 1. It must be true for all n >= 1.

Specifically, if n = 1, then in the set of size n, pers_2, ... don't exist, and so there are no elements in common to link the two sets. This is the explanation the professor gave, and it is correct.

But you bring up the subject I had a problem with, and that is that it was proposed that if you were able to start with a base case of n = 2 and prove that correct, then the proof would work in the same format. You would be able to prove the claim in that case, but I'm wasn't sure about in the same way. Sure you could have a set {p1, p2} and a set, {p2, p3}, and assuming that elements of any set of two must have same characteristics, then you can prove that p3 is same c as p1, and so {p1, p2, p3} is also a set with elements of all the same characteristics. And you can see that it is easy to prove the original claim from here. I had an issue with the idea that the exact same proof with the proper base case is valid.

But maybe it does work, because if you start with the base case, and then add an arbitrary element, x. {p1, p2} ---> {p1, p2, x}, then {p2, x} is a set of two and must have the same c, and ... . At first I didn't think it was full proof because it didn't account for non overlapping sets, {a, b}, {c, d, f}. But I guess now that I think about it, I think it is complete because you can choose any x, and ... .

[vlad from moscow]

The logic error is in the step 2 when you are considering P( 2 ). person1 has "the same hair color" and person2 has "the same hair color" because they are members of individual P( 1 ). But there is no proof that person1 and person2 has the same hair color when they form P( 2 ).

[rapidcoder]

The inductive step is broken, it is not induction at all.

For induction you need to proove that if you have a set of size n of people with the same hair color, *all* possible sets created from that set by adding one element to that set retain the same-hair-color property.

The induction step here shows only you *can* extend the set in such a way to retain the same color, but not that this is the only possible way.

Induction needs strict implication P(n) => P(n+1) for all possible inputs, not P(n) => P(n+1) for some possible inputs or for some additional narrowing assumptions.

[htirwin]

@Rapidcoder: This was my thought. But the professor insisted that the only problem with the proof was that you needed to start with a base case of P(2), because you need that intersection for all n from your base case on. The problem with the example, is that the intersection only applies for n>=2.

The professors point is good. He is pointing out an easy to make mistake in assuming that because you have written p1, p2, ... , pn, that p2, ... , pn actually exist.

I thought it looked sort of bogus because if n = 2, then you have {p1, p2}, and you let n+1 make {p1, p2, p3}. And you can see they intersect. And {p2, p3} is a set of two so also same color. But n+1 can also make {p7, p9, p6}.

Here is a link to the example, it's on page 109. The video can be found on itunes university Math for Computer Science, by MIT.

http://courses.csail.mit.edu/6.042/spring12/mcs.pdf

[abhishekm71]

The problem is that P(2) itself cannot be proven in any way. Hence all subsequent inductions are irrelavant.

[htirwin]

Right, but the professor claims that it was successfully proven that P(2) -> p(3) , and p(3) -> p(4), and ... p(n) -> P(n+1), but not P(1) -> P(2). This is what I have a hard time with accepting.

[rapidcoder]

That is, you professor claims that:

If all two people in set have the same hair color (P(2)), then all people in any set of people of size >= 2 have same hair color P(n), n >= 2?

[cire]

That is, you professor claims that:

If all two people in set have the same hair color (P(2)), then all people in any set of people of size >= 2 have same hair color P(n), n >= 2?

It looks to me like the professor is claiming that if P(n) is true for a sample of the population, it is also true for P(2) to P(n-1) and so it is likely to keep being true for p(n+1) to p(N) where N is the entire population. That is inductive reasoning. It is fallacious because the sample is not representative of the population - a good reason to avoid selection bias.

One uses inductive reasoning to deal with probabilities, not absolutes.

[firedraco]

Right, but the professor claims that it was successfully proven that P(2) -> p(3) , and p(3) -> p(4), and ... p(n) -> P(n+1), but not P(1) -> P(2). This is what I have a hard time with accepting.

I think rapidcoder got this right. He's saying that IF you happened to be able to prove P(2) (you can't), THEN you could prove everything else. But since P(1) does NOT imply P(2), you can't.

[rapidcoder]

He neither has proven P(2) -> P(3) and P(3) -> P(4), etc.

P(2) -> P(3) proof does not hold. Actually it does not hold even for a weaker definition of P - where P(n) means there exists a subset of size n, where all people have the same hair color. His P is stronger - because he claims that *all* subsets of size n must have the same hair color.

Assume P({p1, p2}) = true for some p1, p2, where p1 != p2. This does not imply there exists p3 (p3 != p2 and p3 != p1) such that P({p1, p3}) & P({p2, p3}); therefore you can't conclude P({p1, p2, p3}). Even more, it does not imply P({p1, p3}) nor P({p2, p3}) for all possible values of p3.

[htirwin]

@Rapidcode: That's what I was thinking at first too, but I now realize that the proof does prove p(2) -> P(3) ...

If you assume all subsets of size n have items of same color, then a set of size n+1, must also.

For example, if n = 2, then a subset of size 3, {x, y, z}, has subsets {x, y}, {y, z}, and {x, z}. Each of which are size n, and have overlapping elements.

You can pick any set >= n, and show it is made up of overlapping subsets of size n.