Thread: Whats wrong in this proof

We will prove the following statement by mathematical induction: Let L1, L2.....Ln. be n>=2 distinct lines in the plane, no two of which are parallel. Then all these lines have a point in common.

1: For n=2 the statement is true, since any 2 nonparallel lines intersect.
2: Let the statement hold for n = n0, and let us have n = n0+1 lines L1, L2,....Ln as in the statement. By the inductive hypothesis, all these lines but the last one (i.e. the lines L1, L2 ... Ln-1) have some point in common; let us denote it by x. Similarly the n-1 lines L1,L2.....Ln-2, Ln. have a point in common; let us denote it by y. The line L1 lies in both groups, so it contains both x and y. The same is true for the line Ln-2. Now L1 and Ln-2 intersect at a single point only and so we must have x=y. Therefoer all the lines L1....Ln have a point in common, namely the point x.

Something must be wrong. Wat is it?

This is a variant of the Polya's notorious "ALL Horses have the same color" paradox.

Originally Posted by Wikipedia

In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "That's a horse of a different color!". George Pólya posed the following exercise: Find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:
* Basis: If there is only one horse, there is only one color.
* Induction step: Assume as induction hypothesis that within any set of n
horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.

And the explanation is here - All horses are the same color (paradox) - Wikipedia, the free encyclopedia

Personally I think "same" is undefined for 1 element(you need two elements to say that).
And in your case "meeting at a point" needs 2 or more lines. And the explanation is that, for the statement to be >defined< you need two or more points. Hence the base case=1 is INVALID. Choose 2 and you will be in trouble

so you mean this proof is right?? for less than or equal to two.

All horses are the same color Paradox?

Wow, I really do learn something everyday here on MHF!

Originally Posted by asc

so you mean this proof is right?? for less than or equal to two.

NO!!
I said for values of n greater than or equal to 2, statement does not hold. For the remaining values (how many remaining values are there???), it is not defined!!
Thus the problem is not true in general

Originally Posted by asc

We will prove the following statement by mathematical induction: Let L1, L2.....Ln. be n>=2 distinct lines in the plane, no two of which are parallel. Then all these lines have a point in common.

1: For n=2 the statement is true, since any 2 nonparallel lines intersect.
2: Let the statement hold for n = n0, and let us have n = n0+1 lines L1, L2,....Ln as in the statement. By the inductive hypothesis, all these lines but the last one (i.e. the lines L1, L2 ... Ln-1) have some point in common; let us denote it by x. Similarly the n-1 lines L1,L2.....Ln-2, Ln. have a point in common; let us denote it by y. The line L1 lies in both groups, so it contains both x and y. The same is true for the line Ln-2. Now L1 and Ln-2 intersect at a single point only and so we must have x=y. Therefoer all the lines L1....Ln have a point in common, namely the point x.

Something must be wrong. Wat is it?

Examine the inductive step. It implicitly assumes that n0>=3, but your base
case has n=2, but it needs to be redone with n=3 for this to serve as a base
case. Which cannot be done.

RonL

Originally Posted by CaptainBlack

Examine the inductive step. It implicitly assumes that n0>=3, but your base
case has n=2, but it needs to be redone with n=3 for this to serve as a base
case. Which cannot be done.

RonL

Ya right
This holds for n <= 2 ....
asc, I was referring to polya's paradox when I said n <= 1.
Anyway I hope you got the idea. The moral of the story is "Be wary of people who say "the base case is trivial" in induction". They could be pulling a polya on ya