Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Take $k$ points $\lbrace x_1,\ldots. x_k \rbrace$ in $\mathbb{R^n}$ with the constraint that the line through any two of them contains a third point from the same set. I want to show that all points lie on the same line.

Proof:

Base Case - Obvious

Hypothesis - The claim holds for the $n=k-1$ points $\lbrace x_1,\ldots,x_{k-1}\rbrace$. Then all of these $k-1$ points lie on the same line $l$. Suppose $x_k$ is not on this line. Take $l_1$ to be the line passing through $x_1$ and $x_k$. By assumption $l_1$ contains a point $x_0$ distinct from $x_1, x_n$. However, $x_0 \not \in l\cap l_1=\lbrace x_1 \rbrace.$ A contradiction.

When I wrote this proof I was visualizing it taking place in the plane. Does this proof hold for any $\mathbb{R}^n$?

Isn't induction the ONLY way to go about this problem since n can be arbitrary?

share|improve this question
    
When you say $l_1$ contains a point $x_0$ distinct from $x_1,x_n$, you might instead say that $l_1$ contains a point $x_i$ for some $1<i<k$. The $x_0$ isn't specified to be in the set, though it clearly is supposed to be the point the line contains, and the line is through the points $x_1$ and $x_k$, not $x_n=x_{k-1}$ –  Clayton Mar 1 '13 at 2:23
1  
Your application of the induction hypothesis doesn't work. You only know that all pairs of these $k-1$ points have one of the $k$ points on their line, but this can be the $k$-th point, so you don't know that they all have one of the $k-1$ points on their line, which is what you'd need to apply the induction hypothesis. –  joriki Mar 1 '13 at 3:16

2 Answers 2

up vote 1 down vote accepted

This is known as the Sylvester-Gallai Theorem. It's usually stated and proved for points in the plane, but the usual proofs go through in $n$-space, since all the action is seen to take place in a plane in $n$-space.

share|improve this answer

I think you need to clarify what assumption you are referring to when you argue "by assumption, $l_1$ contains a point $x_0$ distinct from $x_1, \bf{x_k}$." [bold face mine]. All you know is that there is a line $l_1$ determined by $x_1, x_{k}$, with the assumption, for the sake of contradiction, that $x_k$ is not on the line $l$. The If you are using the constraint on "the" line referenced in the problem statement be such that between any two points on that line (which happens to be $l$ in your case), lies another point on that line, why is $l_1$ subject to that

For your argument to work (to obtain a contradiction), you need to rework your hypothesis. $x_0$ must lie on $l$, but you have not yet given any reason why $x_0$ must be on $l$. You are introducing another line $l_1$ which may not be subject to that problem statement's constraint, and if the intersection of $l_1$ with $l$ is only one point $x_1$ from the given set, $x_0$ can, without contradiction, lie off of $l$. If you mean to be referring to your base case, (when you argue "by assumption"), then you should make your base case explicit (which you should do whatever the case). It's just not clear what assumption you are referring to.

I think you have the pieces you need to put the argument together; I simply think you need to argue your "point" (excuse the pun) a little more explicitly.

Perhaps I have not been entirely clear, but I'm simply having trouble accepting your logic without having you fill in the gaps and explicate a bit more.

To answer your added question at the very end, induction is arguably the best route to go, because as you say, $n$ is arbitrary. There is certainly some geometry one can bring in, but induction would be used, nonetheless.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.