__Sylvester’s theorem used (see EWD1016)__

On Tuesday 2 January 1996, Ronald W. Bulterman told me the following theorem.

Consider, for `n` ≥ 2, `n` distinct points in the plane; let `k` be the number of all distinct lines such that each of them contains at least 2 of those points. Then `k` = 1 ∨ `k` ≥ `n` .

^{*} _{*} ^{*}

__Proof__ The proof is by mathematical induction on `n`. There are two reasons for trying this proof structure, firstly the shape of the disjunct `k` ≥ `n` in the demonstrandum and secondly the fact that (Euclid’s Axiom) `n` = 2 ⇒ `k` = 1 immediately establishes the base.

With `n`ʹ = `n` +1, we consider for the induction step `n`ʹ distinct points, giving rise to `kʹ` lines. We have to show `kʹ` = 1 ∨ `kʹ` ≥ `n`ʹ, where we may use `k` = 1 ∨ `k` ≥ `n` “ex hypothese”. In view of our demonstrandum being a disjunction, we introduce a case analysis, viz. `kʹ` =1 versus `kʹ` ≠1.

`kʹ` = 1

In this case, the demonstrandum `kʹ` = 1 ∨ `kʹ` ≥ `n`ʹ follows directly (i.e. by predicate calculus alone).

`kʹ` ≠ 1

In this case, the demonstrandum `kʹ` = 1 ∨ `kʹ` ≥ `n`ʹ simplifies directly to `kʹ` ≥ `n`ʹ. The remainder of the proof is devoted to showing how, for `n`ʹ noncollinear points, `kʹ` ≥ `n` follows from the induction hypothesis.

In order to be able to appeal to the induction hypothesis, we single out one of the `n`ʹ points —let us call that point “`A`”— and consider the remaining `n` points and the `k` lines they give rise to all by themselves. Ex hypothese we may use `k` = 1 ∨ `k` ≥ `n`; we exploit the two disjuncts separately.

In the case `k` = 1, the `n` (distinct) points lie on a single line, and, because the `n`ʹ points are noncollinear, that line does *not* contain `A`. Hence `kʹ` = `n` + 1, and since `n`ʹ = `n` + 1, `kʹ` ≥ `n`ʹ has been established.

In the remaining case `k` ≥ `n` —or, since `n`ʹ = `n` + 1, equivalently `k` + 1 ≥ `n`ʹ — , our demonstrandum `kʹ` ≥ `n`ʹ follows from `kʹ` ≥ `k` + 1 or, equivalently, `kʹ` > `k`. How do we establish `kʹ` > `k`? Or, in other words, how can we conclude that the removal of `A` reduces the number of lines? Well, since a line has to go through at least 2 points of the set, such a line disappears if `A` is one of the only 2 points it goes through. Hence we can assert `kʹ` > `k` by a proper choice of `A` provided:

“For any number of distinct, noncollinear points in the plane, there exists a line through exactly 2 of them.”

But this was Sylvester’s conjecture, which since then became a theorem, so we are done.

(End of Proof.)

Austin, 13 January 1996

prof.dr. Edsger W.Dijkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712–1188

USA