Kirchberger's theorem

Remarks

Proof idea: for each $p \in P$, the set of pairs $(a, b) \in \R^{d+1}$ with $a \cdot p < b$ is an open half-space, hence convex, and likewise for each $q \in Q$ with $a \cdot q > b$. The hypothesis says that every $d + 2$ of these half-spaces in $\R^{d+1}$ have a common point. By Helly's theorem in $\R^{d+1}$, all of them have a common point $(a, b)$, which separates $P$ from $Q$.

Example: take finite sets of red and blue points in the plane. If every four of the points can be split by a line according to their colours, then so can all of them.

The number $d + 2$ cannot be lowered. In the plane, take the red points $(0, 0)$, $(1, 1)$ and the blue points $(1, 0)$, $(0, 1)$. No line separates them, since the two diagonals cross, while every three of the four points can be separated.

Going deeper

For a student

The theorem is a Helly-type result for linear separability. In machine learning it bounds the size of a certificate that two finite classes are not linearly separable: some $d + 2$ points already show it. The proof shows a general pattern: a separation problem becomes a common-point problem for convex sets in a space of parameters, where Helly's theorem applies.