28 I. Convex Sets at Large 7. The Euler Characteristic Helly’s Theorem tells us something special about how convex sets may intersect. Here we introduce another powerful tool to study intersection properties of convex sets. (7.1) Definition. Let A Rd be a subset. The indicator function [A] of A is the function [A] : Rd −→ R such that [A](x) = 1 if x A, 0 if x / A. PROBLEM. 1◦. Prove that [A] · [B] = [A B]. (7.2) Lemma (Inclusion-Exclusion Formula). Let A1,... , Am Rd be sets. Then [A1 . . . Am] = 1 (1 [A1]) · (1 [A2]) · · · (1 [Am]) = m k=1 (−1)k−1 1≤i1i2...ik≤m [Ai 1 . . . Ai k ]. In particular, [A1 A2] = [A1] + [A2] [A1 A2]. Proof. Let us choose an x Rd. Then [A1 . . . Am](x) = 1 if x A1 . . . Am, 0 if x / A1 . . . Am. On the other hand, 1 [Ai](x) = 1 if x / Ai, 0 if x Ai. Therefore, ( 1 [A1](x) ) · · · ( 1 [Am](x) ) = 1 if x / Ai for all i, 0 if x Ai for some i. Hence [A1 . . . Am] = 1 (1 [A1]) · (1 [A2]) · · · (1 [Am]). Expanding the product, we complete the proof. PROBLEM. 1◦. Researchers at a research institute speak French, Russian, and English. Among them, 20 people speak French, 15 speak Russian, and 10 speak English. Also, 8 people speak French and Russian, 5 people speak Russian and English and 7 speak French and English. Two people speak French, Russian and English. How many people work at the institute? We are going to develop a technique which can be viewed as a combinatorial calculus of convex sets. First, we define the class of functions we will be dealing with.
Previous Page Next Page