Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 42 (2001), No. 2, 401-406.

A Methodologically Pure Proof of a Convex Geometry Problem

Victor Pambuccian

Department of Integrative Studies, Arizona State University West P. O. Box 37100, Phoenix AZ 85069-7100, USA e-mail: pamb@math.west.asu.edu

Abstract. We prove, using the minimalist axiom system for convex geometry proposed by W. A. Coppel, that, given n red and n blue points, such that no three are collinear, one can pair each of the red points with a blue point such that the n segments which have these paired points as endpoints are disjoint. MSC 2000: 51G05, 52A01, 52B11, 51K05

The problem stated in the abstract appeared as problem A-4 on the 1979 North American W. L. Putnam Competition. There the 2n points are considered to be in the standard Euclidean plane. As stated by us, as a theorem of Coppel’s minimalist convex geometry, this problem is a statement that describes a universal property of any reasonable geometric order relation, which we believe is general and interesting enough to justify a study of its possible proofs.

Here is the only proof I know to exist in print (in both [8] and [5]): “There is a finite number (actually n!) of ways of pairing each of the red points with a blue point in a 1-to-1 way. Hence there exists a pairing for which the sum of the lengths of the segments joining paired points is minimal.” It is then shown that for such a pairing no two of the n segments intersect. There is a major discrepancy between the statement of this problem and its proof. In the statement there appear only notions of betweenness and collinearity, whereas the proof uses the notion of length. This goes against the principle of purity of the method of proof, enunciated by Hilbert a century ago: “In modern mathematics […] one strives to preserve the purity of the method, i. e. to use in

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2001 Heldermann Verlag

the proof of a theorem as far as possible only those auxiliary means that are required by the content of the theorem.” ([7, p. 27])^{1}

As contributions to this programme, of providing methodologically pure proofs of important geometry problems we cite H. S. M. Coxeter’s proof from axioms of betweenness and incidence of the Sylvester-Gallai problem ([3], [4]), and the proofs from affine axioms of a generalized Euler line theorem by A. W. Boon [1] and E. Snapper [12].

The proof that we shall present, which respects the Hilbertian purity requirement, proceeds inside the following axiomatic framework: There is one kind of individual variables, points, and a ternary relation among points B of betweenness (with B(abc) to be read as ‘b lies between a and c (b could be equal to a or to c)’). When we say ‘segment ab intersects segment cd’ we mean ‘there is a point x, different from a, b, c, d such that B(axb) and B(cxd)’, and when we say that ‘x, y and z are collinear’ (for which we use the abbreviation L(xyz)) we mean B(xyz)∨B(yzx)∨B(zxy). The axioms are:

A 1 B(aab)

A 2 B(aba) → a = b

A 3 B(abc) → B(cba)

A 4 B(abc) ∧ B(acd) → B(bcd)

A 5 b ≠ c ∧ B(abc) ∧ B(bcd) → B(acd)

A 6 a ≠ b ∧ B(acb) ∧ B(adb) → B(acd) ∨ B(adc))

A 7 a ≠ b ∧ B(abc) ∧ B(abd) → B(acd) ∨ B(adc)

A 8 (∀ab_{1}b_{2}cd) B(acb_{1}) ∧ B(cdb_{2}) → (∃b) B(b_{1}bb_{2}) ∧ B(adb)

A 9 (∀ab_{1}b_{2}c_{1}c_{2}) B(ac_{1}b_{1}) ∧ B(ac_{2}b_{2}) → (∃d) B(b_{1}dc_{2}) ∧ B(b_{2}dc_{1})

This axiom system is equivalent to the axiom system consisting of (L1)–(L4), (C) and (P) in [2]. The main difference consists in the adoption of the betweenness predicate as only primitive notion, in the spirit of [14], as opposed to using points and segments and an incidence relation between them, as done in [2]. Axioms A1–A7 are equivalent to the axioms (L1)–(L4), and A8, A9 are restatements of axioms (C) and (P) respectively, which are forms of the Pasch axiom, the ‘outer form’ and the ‘inner form’. Models of the axioms A1–A9 will be called linear geometries. Let 𝔏 be a linear geometry. If x and y are two points in 𝔏, then we denote by [x, y] the segment xy, the set of all points z with B(xzy), and, for x ≠ y, by ⟨x, y⟩, the line xy, the set all points z with L(xyz). A subset C of 𝔏 is called convex (affine) if it contains [x, y] (respectively ⟨x, y⟩) for all x, y ∈ C. The convex (affine) hull of a subset A of 𝔏 is defined to be the intersection of all convex (respectively affine) sets containing A, and is denoted by [A] (resp. ⟨A⟩). The convex hull of a finite set is called a polytope. A point e of a subset S of 𝔏 is called an extreme point of S if S \ {e} is convex. A face of a convex set C is a set A such that C ∩ ⟨A⟩ = A and C \ A is convex. A dimension theory may be developed for affine sets, as shown in [2], and in the case of polytopes all dimensions involved are finite. The notation dim S refers to dim⟨S⟩. A subset H of a finite dimensional affine set A is called a hyperplane in A if dim H = dim A − 1. A face F of a polytope P is a facet (edge) if F is a hyperplane in ⟨P ⟩ (resp. dim F = 1).

1“In der modernen Mathematik (wird) solche Kritik sehr häufig geübt, woher das Bestreben ist, die Reinheit der Methode zu wahren, d. h. beim Beweise eines Satzes womöglich nur solche Hülfsmittel zu benutzen, die durch den Inhalt des Satzes nahe gelegt sind.”

Here are some facts about polytopes, proved in [2], that we shall use in the sequel:

(i) Any two points e and e′ in the extreme set S of a polytope P can be connected in S by edges of P (see [2, IV. Prop. 23]). (ii) If F and G are faces of a polytope P such that F ⊂ G, then there exists a finite sequence F_{0}, F_{1}, …, F_{r} of faces of P, with F_{0} = F and F_{r} = G, such that F_{i−1} is a facet of F_{i} for i ∈ {1, …, r} (see [2, IV. Cor. 16]). (iii) If F is a face of a polytope P with dim F = dim P − 2, then F is contained in exactly two facets of P and is their intersection (see [2, IV. Prop. 15]).

Our problem can be restated as follows: Let a_{1}, …, a_{n} and b_{1}, …, b_{n} be points, such that no three of them are collinear. Then there is a permutation^{2} σ of {1, …, n} such that no two segments [a_{i}, b_{σ(i)}] and [a_{j}, b_{σ(j)}] with i ≠ j intersect. In the formal language of our axiomatics this can be expressed, for every n ≥ 2, as the sentence φ_{n}: (∀a_{1} … a_{n}b_{1} … b_{n}) ⋁_{1≤i<j<k≤n}(L(a_{i}a_{j}a_{k}) ∨ L(b_{i}b_{j}b_{k})) ⋁_{1≤i<j≤n,1≤k≤n}(L(a_{i}a_{j}b_{k}) ∨ L(a_{i}b_{j}b_{k})) ⋁_{σ∈S_{n}}((∀x) ⋀_{1≤i<j≤n} ¬(B(a_{i}xb_{σ(i)}) ∧ B(a_{j}xb_{σ(j)}))).

We first prove the following

Lemma. Given a set S of n points, with no three collinear, p an extreme point of the polytope P := [S], and a natural number k with 1 ≤ k < n, one can partition S into two subsets U_{k} and V_{k}, such that U_{k} contains k points, p ∈ V_{k}, and [U_{k}] ∩ [V_{k}] = ∅.

Proof. Let d be the dimension of S. If d = 2, then, by (ii) and (iii) there are exactly two edges (which are facets in our case), ⟨p, q_{1}⟩ and ⟨p, r⟩ that contain p. We shall construct a sequence of subsets Q_{i} of S, for i = 1, … n − 1, as follows: let Q_{1} = {q_{1}}, and suppose that Q_{i} with 1 ≤ i < n − 1 has already been constructed. Denote by q_{i+1} the point in S for which ⟨p, q_{i}⟩ is one of the edges that contain p in the polytope [S \ Q_{i}] (the one different from ⟨p, r⟩, for i < n − 2; for i = n − 2 we set q_{i+1} := r), and let Q_{i+1} = Q_{i} ∪ {q_{i+1}}. The two sets U_{k} = Q_{k} and V_{k} = S \ U_{k} have the desired properties (by the definition of facets, and the fact that there are no three collinear points).

Suppose now that the statement of the lemma has been established for all dimensions < d. Let L be a d − 2-dimensional face of P containing p, and let H and H′ be the two facets of P that contain L (cf. (ii) and (iii)). We shall construct a sequence of subsets U_{i} of S having i elements, with i = 1, …, n − 1. We start with J_{1} := ((H ∩ S) \ L) ∪ {p}, which is a finite set of points containing p, of dimension d − 1, so, by our inductive hypothesis, there are partitions of J_{1} into two subsets A_{1,j} and B_{1,j}, such that [A_{1,j}] ∩ [B_{1,j}] = ∅, A_{1,j} has j elements, and p ∈ B_{1,j}, for any 1 ≤ j < |J_{1}|. Let U_{i} := A_{1,i} for 1 ≤ i ≤ |J_{1}| − 1. Let m ≥ 1, and suppose that J_{h} has been defined for all 1 ≤ h ≤ m. Let α = ∑_{h=1}^{m}(|J_{h}|−1) and suppose U_{α} has been defined as well. Let J_{m+1} be:

2The set of all permutations of {1, …, n} will be denoted by S_{n}.

(a) the set of all points of S contained in the facet containing L that is different from H′ of the polytope [(S \ (∪_{i=1}^{m}J_{i})) ∪ {p}], if that polytope is d-dimensional;

(b) the set of all points of S contained in H′, if (S \ (∪_{i=1}^{m}J_{i})) is contained in H′. By our inductive hypothesis, there are partitions of J_{m+1} into two subsets A_{m+1,j} and B_{m+1,j}, such that [A_{m+1,j}] ∩ [B_{m+1,j}] = ∅, A_{m+1,j} has j elements, and p ∈ B_{m+1,j}, for any 1 ≤ j < |J_{m+1}|. Let U_{α+i} = U_{α} ∪ A_{m+1,i} for 1 ≤ i ≤ |J_{m+1}| − 1. Since (b) must occur after a finite number of steps, we have defined U_{i} for all i ∈ {1, …, n − 1}. The desired partition of S is obtained by setting V_{k} = S \ U_{k} ([U_{k}] ∩ [V_{k}] = ∅ is a consequence of the definition of faces and facets). □

Theorem. For all n ≥ 1 φ_{n} is valid in all linear geometries.

Proof. Let S be a set of n red and n blue points (a more suggestive way to refer to a_{1}, …, a_{n} and b_{1}, …, b_{n}), no three of which are collinear.

The proof that the sentences φ_{n} hold in linear geometry will proceed inductively on n. For n = 1 the statement is vacuously true. Suppose now that n ≥ 2 and that the validity of φ_{i} has been established for all 1 ≤ i ≤ n − 1. We will show that φ_{n} must hold as well. If there are two extreme points of S of different colour, then we are done, since by (i) they can be connected by edges whose endpoints are extreme points of S. One of those edges must have different coloured endpoints, say e_{1} and e_{2}, which are points of S, and thus one can partition S into two sets with an equal number of red and blue points, namely S′ = {e_{1}, e_{2}} and S′′ = S \ S′. Since in S′′ there are n − 1 points of each colour, the red ones can be paired with the blue ones such that the segments that have those pairs as endpoints do not intersect. Adding to that pairing the pair (e_{1}, e_{2}), we obtain the desired result, since the segment [e_{1}, e_{2}] is an edge, thus cannot be intersected by any segment with endpoints in S′′.

So from now on, we shall assume that the set of extreme points of S is monochromatic, say blue. Let p be an extreme point of S. By the above Lemma, there is, for every k with 1 ≤ k ≤ 2n−1 a partition of S into two sets U_{k} and V_{k} such that p ∈ V_{k}, U_{k} has k points and [U_{k}] ∩ [V_{k}] = ∅. Notice that, by the construction of the set U_{k} described in the above Lemma, U_{1} contains an extreme point of S, thus a blue point, and that U_{2n−1} contains all the points except p, so more red points than blue points. Thus there exists a k with 1 ≤ k ≤ n − 1 for which U_{2k} (and thus V_{2k} as well) contains an equal number of red and blue points. Since both φ_{k} and φ_{n−k} have been assumed to be true, there is a pairing of the blue and red points in U_{2k} and V_{2k} such that the respective segments do not intersect. Given that [U_{2k}] ∩ [V_{2k}] = ∅, the segments with endpoints in U_{2k} cannot intersect those in V_{2k}, so we have obtained the desired pairing of the points in S. □

Is our proof of the statements φ_{n} in a strict sense superior to the proof presented in [8] and [5]? In other words does that proof require strictly stronger assumptions than ours? The answer is, surprisingly, No! That proof can be done inside an axiom system that is incomparable to ours. To see that, notice that what was needed in the argument of the proof in [8] and [5] was an ability to add the lengths of segments, compare any two segments, and the triangle inequality (which is used in the proof that the blue-red pairing with minimal sum of the lengths is the desired pairing, for the assumption of an intersection of two segments with red and blue endpoints [r, b] with [r′, b′], would, via triangle inequality, lead to the conclusion that the sum of the lengths of [r, b′] and [r′, b] is less than that of [r, b] and [r′, b′], which contradicts the minimality of the sum of the pairing that paired r with b and r′ with b′). An axiom system for a theory that allows one to do just that was proposed by M. Moszyńska [10]. That axiom system, say Σ, is formulated in a language with one sort of individuals, points, and two primitive notions, a quaternary one of equidistance, ≡, with ab ≡ cd to be read as ‘the segments ab and cd are equal in length’, and a ternary one for betweenness, B. Given that Σ is somewhat involved, we shall describe its models, and refer to [10] for Σ itself (cf. also [9]). Let X be a set, G be an (additive) Abelian ordered group, and ϱ : X × X → G a regular metric, i. e. a function satisfying the following properties:

ϱ(a, b) ≥ 0; ϱ(a, b) = 0 ↔ a = b; ϱ(a, b) = ϱ(b, a), ϱ(a, b) + ϱ(b, c) ≥ ϱ(a, c); (∀a_{1} … a_{n}b_{1} … b_{n})(∃q_{0} … q_{n}) ⋁_{σ∈S_{n}}[⋀_{i=1}^{n}(ϱ(q_{0}, q_{i−1}) + ϱ(q_{i−1}, q_{i}) = ϱ(q_{0}, q_{i}) ∧ϱ(q_{i−1}, q_{i}) = ϱ(a_{σ(i)}, b_{σ(i)}))]; (∀abca′c′)(∃b′) ϱ(a, b) + ϱ(b, c) = ϱ(a, c) ∧ ϱ(a, c) = ϱ(a′, c′) → ϱ(a, b) = ϱ(a′, b′) ∧ ϱ(b, c) = ϱ(b′, c′). Every model of Σ is a set X, equipped with a regular metric ϱ, such that ab ≡ cd if and only if ϱ(a, b) = ϱ(c, d) and B(abc) if and only if ϱ(a, b) + ϱ(b, c) = ϱ(a, c). Of the axioms A1–A9 for B, only A1–A4 are consequences of Σ. Notice that the triangle inequality is essential for the φ_{n} to be true in a theory of metric betweenness and equidistance. To be precise, even if all other axioms of plane Euclidean geometry over Pythagorean fields hold, but the triangle inequality fails, φ_{2} need not hold. In particular, this means that some form of the Pasch axiom, from which the triangle inequality may be deduced (in the presence of the customary axioms for equidistance and betweenness), in our axiom system A8 and A9, is indispensable for the proof of φ_{2}. It was shown in [6] and [11] that the triangle inequality is strictly weaker than the Pasch axiom in a certain axiom system for plane Euclidean geometry over Pythagorean fields. Thus there are models of Σ that are not linear geometries, so Σ is not stronger than A1–A9. To see that φ_{2} does not hold in an axiom system for plane Euclidean geometry in which the triangle inequality does not hold, we shall use Szczerba’s [13] method of constructing semi-orders of the field of real numbers. Let a be a transcendental number in ℝ, satisfying 0 < a < 1. Then X = \{1, a, a^{2}, \frac{a^{2}\sqrt{2}}{a+1}, ^{\frac{a(1−a)\sqrt{2}}{a+1}}, \frac{a\sqrt{a^{2}+1}}{a+1}, ^{\frac{a(a−1)\sqrt{a^{2}+1}}{a+1}}\}, as a subset of the vector space ℝ over ℚ is linearly independent, so it can be extended to a base B of ℝ over ℚ. Let b_{i} with i = 0, …, 7 be the enumeration of the elements of X in the order in which they are written in X, and suppose all the elements of B are indexed by a set I that includes {1, …, 7}. The mapping ψ : B → ℝ, defined by ψ(b_{i}) = b_{i} for all i ∈ I, except i = 3 and 7, for which ψ(b_{i}) = −b_{i}, can be extended by linearity to an isomorphism of vector spaces f : ℝ → ℝ. Let P be the set of all positive numbers of ℝ. Then R := ⟨ℝ, f(P)⟩ is a semi-ordered field, with x < y if and only if y − x ∈ f(P) (the order relation is closed under addition but not under multiplication). Then, in R × R, betweenness and equidistance can be defined as in regular metric spaces, with the metric ϱ defined by ϱ((x_{1}, x_{2}), (y_{1}, y_{2})) = f(P)\sqrt{(x_{1} − y_{1})^{2} + (x_{2} − y_{2})^{2}}, where _{f(P)}\sqrt{x} denotes the f(P)-positive element whose square is x. In this model, the betweenness axioms A1–A7 hold, but not A8 and not A9. So do the axioms of Σ, with the exception of one axiom schema (A14_{n} in [10]). One can check that φ_{2} fails in this model by choosing a_{1} = (0, a), a_{2} = (a^{2}, 0), b_{1} = (a, 0), b_{2} = (0, −a). Acknowledgment. I would like to thank Prof. Dr. Yuri Movsisyan of Yerevan State University, Armenia, for having invited me to give a lecture at the Mathematics-Physics School in Yerevan, where I came up with the idea of a methodologically pure proof of this problem, and to the Armenian General Benevolent Union, in particular to Lana Kazangian, for having made my stay in Yerevan both possible and meaningful.

References

[1] Boon, A. W.: Die Eulersche Gerade – Ein Beweis. Euclides (Groningen) 57 (1978), 56–57.

[2] Coppel, W. A.: Foundations of convex geometry. Cambridge University Press, Cambridge 1998.

[3] Coxeter, H. S. M.: A problem of collinear points. Amer. Math. Monthly 55 (1948), 26–28.

[4] Coxeter, H. S. M.: Introduction to Geometry. 2nd ed., Wiley Classics, New York 1989.

[5] Erickson, M. J.; Flowers,J.: Principles of Mathematical Problem Solving. Prentice-Hall, Upper Saddle River 1999.

[6] Gupta, H. N.; Prestel, A.: Triangle and Schwarz inequality in Pasch-free Euclidean geometry. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 20 (1972), 999–1003.

[7] Hilbert, D.: Vorlesung über die Grundlagen der Geometrie. Göttingen, WS 1898-1899, ed. H. V. Schaper.

[8] Klosinski, L. F.; Alexanderson, G. L.; Hillman, A. P.: The William Lowell Putnam Mathematical Competition. Amer. Math. Monthly 87 (1980), 634–640.

[9] Mendris, R.; Zlatoš, P.: Axiomatization and undecidability results for metrizable betweenness relations. Proc. Amer. Math. Soc. 123 (1995), 873–882.

[10] Moszyńska, M.: Theory of betweenness and equidistance relations in regular metric spaces. Fund. Math. 96 (1977), 17–29.

[11] Prestel, A.: Euklidische Geometrie ohne das Axiom von Pasch. Abh. Math. Sem. Univ. Hamburg 41 (1974), 82–109.

[12] Snapper, E.: An affine generalization of the Euler line. Comptes Rendus Math. Rep. Acad. Sci. Canada 1 (1978/1979), 279–281 and Amer. Math. Monthly 88 (1981), 196– 198.

[13] Szczerba, L. W.: Independence of Pasch’s axiom. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 18 (1970), 491–498.

[14] Szczerba, L. W.; Tarski, A.: Metamathematical discussion of some affine geometries. Fund. Math. 104 (1979), 155–192.

Received February 1, 2000