Rendered at 23:37:05 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
hyperhello 21 hours ago [-]
> Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points.
I can't make out the point here (no pun). Of course a line can pass through any two points. It could pass through three if those points were collinear but the statement says they're not. So what is the new fact?
Sniffnoy 20 hours ago [-]
I think what's going on here is that you've misunderstood the theorem's hypothesis. The hypothesis isn't that no three of the points are collinear; rather, it's the weaker statement that there isn't any one single line that all the points lie on. It's true that with your version of the hypothesis the theorem would be trivial; but with the actual hypothesis it is is nontrivial.
fxwin 17 hours ago [-]
> hypothesis
I think you meant premise?
loose-cannon 13 hours ago [-]
The thing that you assume in a theorem is usually called a hypothesis.
fxwin 12 hours ago [-]
looks like both words are valid, TIL!
stackghost 19 hours ago [-]
>rather, it's the weaker statement that there isn't any one single line that all the points lie on
... of course there's no single line that all the points lie on. They've been defined to be non-collinear.
Edit: can't reply because of HN's stupid rate-limit mechanism, but to this:
>So the theorem proves that no matter which way you arrange any finite set of points, except for all on the same line, then you can always find a line with exactly two points.
Of course you can. It's absolutely implied by the problem definition. My 9 year old could do this, given a ruler and a pencil, with 100% success rate. I absolutely do not believe this is a novel "theorem"
chenb4425 18 hours ago [-]
I think you are mistaking the fact that you can easily find an example satisfying the theorem’s statement with the proof that the statement is always true. Of course given any set of points that aren’t all on the same line, your nine your old could find a line passing through only two points. But could they explain to you why this is always possible, no matter the configuration of points? You can’t just say “I draw a line between two points and that’s it.” You must also explain why there isn’t a third point on the line, and why that line’s existence is guaranteed, which is not obvious (at least to me).
stackghost 10 hours ago [-]
>You must also explain why there isn’t a third point on the line, and why that line’s existence is guaranteed, which is not obvious (at least to me).
There isn't a third point on the line you found because the problem stipulates that the set of points is not collinear.
h3lp 8 hours ago [-]
So it says that not ALL points are on that single line. But it doesn't stipulate that THREE points can't be on the line---the theorem is about proving that you can find one that doesn't have the third point.
chenb4425 8 hours ago [-]
That's only assuming your set of points only contains three points. If you have four or more points, it's entirely possible that a line you draw between two points passes through a third.
.
...
If you're given the above set of points, it's obviously not collinear due to the point at the top, but if you draw a line through any of the bottom two points, it will hit a third.
hyperhello 19 hours ago [-]
His statement helped me. It's not that every three points are non-collinear, it's that any three points are non-collinear. A set of points all lying on a line is the only exception; you can have every point lying on a line except for one, or two, or whatever you want. In a square grid of sixteen points, there are lots of sets of four collinear points for example, but not all sixteen, and that's what counts.
So the theorem proves that no matter which way you arrange any finite set of points, except for all on the same line, then you can always find a line with exactly two points.
emil-lp 18 hours ago [-]
You don't understand the statement. A bit of mathematical maturity is needed, sometimes, to parse a theorem statement.
In any finite set of points, either there is a line hitting all points, or there is a line hitting exactly 2 points.
It's nontrivial to prove.
ky3 17 hours ago [-]
Maybe this'll help: Every bunch of points on a plane has a lonely bridge. A lonely bridge is a line connecting only two points, no more.
Obvious caveat: The points can't all lie in the same line (the collinear condition).
Not-so-obvious caveat: There can't be an infinite number of points.
fxwin 17 hours ago [-]
> It could pass through three if those points were collinear but the statement says they're not
The theorem doesn't presume that no three points are collinear, it presumes that the set as a whole isn't collinear, which is a much weaker statement.
glimshe 21 hours ago [-]
Try to come up with a set non-colinear points where NO line passes through two and ONLY TWO points and you'll see the value of the statement.
You may think "I'm sure I can arrange these points in a way where EVERY line will cross three or more points" but you will fail if you try unless ALL points are colinear.
JetSetWilly 17 hours ago [-]
You can always find a line that passes between two points. Why would you even try to find a line that doesn’t pass between two points? What is the difficult part here.
glimshe 13 hours ago [-]
The difficult part is that you may think that there's an arrangement where you could force every line to go through 3 or more points. The line extends to infinity, keep in mind.
ky3 17 hours ago [-]
Find one that bridges only two points, no more. Unless ofc you're given a configuration that's obviously impossible: all of them in a line.
scythe 20 hours ago [-]
This is true for finite sets. For infinite sets, the Sierpinski triangle is a counterexample.
tzs 16 hours ago [-]
That’s an uncountable set. If we want a counter example for uncountable sets a simpler example is a circular area.
Anyone happen to know if it is true for countably infinite sets?
ky3 17 hours ago [-]
> the Sierpinski triangle is a counterexample
How so? It's bounded by the large initial triangle. The line containing any two of the vertices doesn't intersect any other point.
tzs 21 hours ago [-]
It can help to think about theorems like this by restating them as a puzzle asking for a counterexample.
Given N points, N > 2, can you arrange them in a Euclidean plane so that (1) they are not all on the same line, and (2) every line that goes through two of the points must also go through at least one more of the points?
The theorem says that you cannot do this.
squirrel 17 hours ago [-]
Well put. A similar way to say it: ask the 9 year old to draw ALL of the possible lines connecting two points in the set — of course this is possible, just might take awhile. The theorem says that at least one of the lines drawn must hit ONLY the two points the 9 year old used when drawing that particular line, not any others.
squirrel 16 hours ago [-]
I just thought of another way to restate. Suppose you give me any finite set of points, any finite set at all, and you also tell me that when the 9 year old draws any line through any two of them, she will always hit a third. Then I can immediately conclude all the points lie on a single line, that is, that any line the 9 year old draws will hit all the points.
chenb4425 21 hours ago [-]
It’s that the line passes through exactly two points, which if you think about it is not exactly obvious.
math_loser 21 hours ago [-]
> So what is the new fact?
For all arbitrarily sized (but finite) sets of not collinear points, there's always a line that passes through exactly two points in the set.
pratikdeoghare 18 hours ago [-]
> According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An algorithm can find an ordinary line in a set of n points in time O(n log n). [1]
There are many such lines (think convex hull) and they are easy to find.
This makes it hard to appreciate the theorem.
You keep thinking oh whats the big deal.
The boundary lines of the convex hull can easily have 3 points each. So not as obvious as all that.
frotaur 16 hours ago [-]
In the proof, it claims that "At least two of these must fall on the same side of P′, the perpendicular projection of P on ℓ.".
However, this is not true as it is possible that P'=B. However it seems the proof still goes through (at least as depicted in the image, haven't thought hard about the general case).
cirpis 16 hours ago [-]
I dont think theres an issue, the point P' simply belongs to both sides of itself. With this convention in place it is still true that there are two points in the same side, and the proof goes through verbatim.
Its mostly a question of whether you count the line defining a half-plane as belonging to the half plane or not, and clearly they do here
Nail2680 20 hours ago [-]
I might be too stupid to understand why this is interesting and useful. If it helps I am a working physicist, and a lot of pure math is lost on me. I think I followed this, but I don't know why one would care or this would be interesting.
alan-crowe 12 hours ago [-]
It is interesting to a pure mathematician. Since it is obviously true, one's intuition is that it should have a simple proof. In particular, the obvious induction ought to work.
The base case is n=2. The line joining them passes through exactly two points because that is all you have.
Now we attempt the induction step. We have n+1 points. Leave one, p, out. We know that the theorem applies to the n points by the induction hypothesis. So we have points q and r that have a line going through them. And the point of the theorem is that the line goes through only q and r, exactly two points of the n. All we have to do is add in p, not on that line, and we are done.
But we are also stuck. Point p is not one of the n points participating in the induction hypothesis. Nothing tells us that p is not on the line joining q and r.
So how do we prove it? It is a good, intriguing puzzle, but in proof theory, not geometry.
tirutiru 18 hours ago [-]
The Appolonius circle is a theorem in pure geometry. It is used in the 'method of images' in physics. And not just for ancient textbook problems either. I saw a paper in experimental fluid mechanics that builds up the intuition with images (2D incompressible flow). Appolonius live and kicking in the 21st century.
The Kochen-Specker theorem is interesting (if not useful). The proofs have a similar flavour to Sylvester. One tries to make a set of projections 'compatible' and it turns out to be impossible. Maybe there's a deeper connection.
emil-lp 22 hours ago [-]
Futility closet is fantastic!
stackghost 19 hours ago [-]
>Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points.
Isn't this a tautology?
The problem definition states that the set of points is in Euclidean space, which from Euclid's Axioms means we can draw a line between any two points. The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of them. This is just simple logic.
fxwin 16 hours ago [-]
> The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of them
This is wrong and you are misunderstanding what collinearity means. You could have a set of points where all but one are on the same line, and the set of a whole will be not collinear, while we can obviously draw a line that passes through more than two of them.
A different way of stating the theorem is that any finite set of points has either a line passing through all points (i.e. the set is collinear) or there exists a line that passes through exactly two points. This dichotomy (why two and not three? Why can't we construct a set where any line passes through at least three points?) is not immediately obvious.
agnishom 19 hours ago [-]
That is not what was meant. Here is a better rephrasing:
Let X be a set of points not all of which are collinear. Then, there are two points a, b in X such that the line l passing through X only passes through a and b.
stackghost 19 hours ago [-]
>Let X be a set of points not all of which are collinear. Then, there are two points a, b in X such that the line l passing through X only passes through a and b.
I don't see how this rephrasing changes anything. Of course there are two points a and b because again, the definition of the problem leads naturally, obviously, and definitionally to this result.
isomorphic_duck 19 hours ago [-]
Not all points being collinear does NOT mean that all 3-tuples of points are non-collinear! The hypothesis of the theorem is the former. And what it proves is that there is at least one such 3-tuple.
Cerium 19 hours ago [-]
The other thread above helped me. You can have as many collinear points as you want as long as at least one point in the set is non-collinear.
Consider a 3x3 grid. It satisfies this argument.
agnishom 17 hours ago [-]
Not really. Perhaps this will help:
Can you have a set of points Y on a plane such that Y satisfies the following? Given any line passing through 2 points on Y, there is also a third point in Y that it passes through.
LegionMammal978 19 hours ago [-]
"The set is not collinear" here means "there is no straight line passing through all the points simultaneously", not "there is no straight line passing through some three points".
stackghost 19 hours ago [-]
... yes, I understand.
There's nothing novel here. I feel like I'm taking fucking crazy pills.
hyperhello 19 hours ago [-]
Math is like that. But try to put any number of points in some configuration where you can't find some line with only two on it. In this diagram, you can't do an axis-aligned line with more or less than three -- but you can go diagonal and cross only two points. There's always a way to find only two points.
. . .
. . .
. . .
stackghost 10 hours ago [-]
>There's always a way to find only two points.
As soon as the set of points are defined to be non-collinear in Euclidean space, this property must be true, purely from the definition of the problem. To suggest otherwise would be to violate either the problem definition or the axioms of Euclidean geometry.
hyperhello 9 hours ago [-]
You're still not quite getting it, the statement isn't that trivial. It deals with the area between totally collinear (obviously impossible to find a lonely pair) and totally non-collinear (obviously impossible not to find a lonely pair).
I can't make out the point here (no pun). Of course a line can pass through any two points. It could pass through three if those points were collinear but the statement says they're not. So what is the new fact?
I think you meant premise?
... of course there's no single line that all the points lie on. They've been defined to be non-collinear.
Edit: can't reply because of HN's stupid rate-limit mechanism, but to this:
>So the theorem proves that no matter which way you arrange any finite set of points, except for all on the same line, then you can always find a line with exactly two points.
Of course you can. It's absolutely implied by the problem definition. My 9 year old could do this, given a ruler and a pencil, with 100% success rate. I absolutely do not believe this is a novel "theorem"
There isn't a third point on the line you found because the problem stipulates that the set of points is not collinear.
.
...
If you're given the above set of points, it's obviously not collinear due to the point at the top, but if you draw a line through any of the bottom two points, it will hit a third.
So the theorem proves that no matter which way you arrange any finite set of points, except for all on the same line, then you can always find a line with exactly two points.
In any finite set of points, either there is a line hitting all points, or there is a line hitting exactly 2 points.
It's nontrivial to prove.
Obvious caveat: The points can't all lie in the same line (the collinear condition).
Not-so-obvious caveat: There can't be an infinite number of points.
The theorem doesn't presume that no three points are collinear, it presumes that the set as a whole isn't collinear, which is a much weaker statement.
You may think "I'm sure I can arrange these points in a way where EVERY line will cross three or more points" but you will fail if you try unless ALL points are colinear.
Anyone happen to know if it is true for countably infinite sets?
How so? It's bounded by the large initial triangle. The line containing any two of the vertices doesn't intersect any other point.
Given N points, N > 2, can you arrange them in a Euclidean plane so that (1) they are not all on the same line, and (2) every line that goes through two of the points must also go through at least one more of the points?
The theorem says that you cannot do this.
For all arbitrarily sized (but finite) sets of not collinear points, there's always a line that passes through exactly two points in the set.
There are many such lines (think convex hull) and they are easy to find. This makes it hard to appreciate the theorem. You keep thinking oh whats the big deal.
[1] https://en.wikipedia.org/wiki/Sylvester%E2%80%93Gallai_theor...
However, this is not true as it is possible that P'=B. However it seems the proof still goes through (at least as depicted in the image, haven't thought hard about the general case).
Its mostly a question of whether you count the line defining a half-plane as belonging to the half plane or not, and clearly they do here
The base case is n=2. The line joining them passes through exactly two points because that is all you have.
Now we attempt the induction step. We have n+1 points. Leave one, p, out. We know that the theorem applies to the n points by the induction hypothesis. So we have points q and r that have a line going through them. And the point of the theorem is that the line goes through only q and r, exactly two points of the n. All we have to do is add in p, not on that line, and we are done.
But we are also stuck. Point p is not one of the n points participating in the induction hypothesis. Nothing tells us that p is not on the line joining q and r.
So how do we prove it? It is a good, intriguing puzzle, but in proof theory, not geometry.
The Kochen-Specker theorem is interesting (if not useful). The proofs have a similar flavour to Sylvester. One tries to make a set of projections 'compatible' and it turns out to be impossible. Maybe there's a deeper connection.
Isn't this a tautology?
The problem definition states that the set of points is in Euclidean space, which from Euclid's Axioms means we can draw a line between any two points. The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of them. This is just simple logic.
This is wrong and you are misunderstanding what collinearity means. You could have a set of points where all but one are on the same line, and the set of a whole will be not collinear, while we can obviously draw a line that passes through more than two of them.
A different way of stating the theorem is that any finite set of points has either a line passing through all points (i.e. the set is collinear) or there exists a line that passes through exactly two points. This dichotomy (why two and not three? Why can't we construct a set where any line passes through at least three points?) is not immediately obvious.
Let X be a set of points not all of which are collinear. Then, there are two points a, b in X such that the line l passing through X only passes through a and b.
I don't see how this rephrasing changes anything. Of course there are two points a and b because again, the definition of the problem leads naturally, obviously, and definitionally to this result.
Consider a 3x3 grid. It satisfies this argument.
Can you have a set of points Y on a plane such that Y satisfies the following? Given any line passing through 2 points on Y, there is also a third point in Y that it passes through.
There's nothing novel here. I feel like I'm taking fucking crazy pills.
As soon as the set of points are defined to be non-collinear in Euclidean space, this property must be true, purely from the definition of the problem. To suggest otherwise would be to violate either the problem definition or the axioms of Euclidean geometry.
EITHER all points are on the same line
OR 2 of the points are on the line only for them