CANTOR BENDIXON DEGREES AND CONVEXITY IN ℝ^{2}

MENACHEM KOJMAN

Abstract. We present an ordinal rank, δ^{3}, which refines the standard classification of non-convexity among closed planar sets. The class of closed planar sets falls into a hierarchy of order type ω_{1} + 1 when ordered by δ-rank.

The rank δ^{3}(S) of a set S is defined by means of topological complexity of 3-cliques in the set. A 3-clique in a set S is a subset of S all of whose unordered 3-tuples fail to have their convex hull in S. Similarly, δ^{n}(S) is defined for all n > 1.

The classification cannot be done using δ^{2}, which considers only 2-cliques (known in the literature also as “visually independent subsets”), and in dimension 3 or higher, the analogous classification is not valid.

1. Introduction

Let S be a set in a linear space, and suppose that S is not convex. One would like to measure how far S is from being convex. The most natural number for measuring non-convexity of a set S is the least number of convex subsets of S needed to cover S. Let us, then, define γ(S) as the least cardinality of a collection of convex sets whose union equals S. The function γ is adopted as the basic measurement of non convexity. Classification by γ gives countably many different classes of sets with finite γ and (potentially) only two classes with infinite γ: sets with countable γ and sets with uncountable γ.

In this paper we define for each n > 1 a degree functions δ^{n}, and show that δ^{3} refines the γ-classification for closed, planar sets. The class {S : S ⊆ ℝ^{2} is closed and γ(S) ≤ ℵ_{0}} is divided by δ^{3} to ℵ_{1} sub-classes, while {S : S ⊆ ℝ^{2} is closed and γ(S) > ℵ_{0}} is a single δ^{3}-class.

The first step in understanding the structure of a set S with γ(S) = λ is to understand why S fails to decompose into a union of fewer than λ convex sets.

There is an easy sufficient condition for S not to be a union of fewer than λ convex sets: the existence of a subset P ⊆ S of cardinality λ, with the property that for any two points in P, the line segment connecting them is not contained in S. No two of those points can sit in the same convex subset of S, hence S is not a union of n convex sets. Call a subset of S with this property “visually independent”. Let α(S) be the supremum of cardinalities of all visually independent subsets in S.

Does α measure non-convexity adequately? This can be rephrased as whether there exists a “reasonable” function f so that γ(S) ≤ f(α(S)).

For general sets this is badly false (see [5], Section 5), and also in “nice” sets in dimension 3 or higher the connection between α and γ is not well behaved. Nevertheless, closed sets in ℝ^{2} show some tight connections between α and γ. A long sequence of results [4, 9, 2, 1] culminated in the discovery [3] that γ(S) ≤ f(α(S)) for some function f, for closed planar sets. Later it was shown that f is at most n^{6} in [8]. Recently, n^{6} was lowered to 18n^{3} by Matousek and Valtr in [6], where also a lower bound of O(n^{2}) was set.

In sets which are not a finite union of convex sets, the connection between α and γ is not as tight. There exist compact, planar sets with countable α and uncountable γ ([5], Example 2.1). Put differently, the class of closed planar sets with countable α contains also sets with uncountable γ. This means that the notion of visual independence does not capture all the information as to why a closed S ⊆ R^{2} cannot be covered by countably many convex subsets.

However, a generalization of visual independence does. Call a subsets P ⊆ S a 3-clique if every 3-element subset X ⊆ P satisfies that its convex closure is not contained in S. Theorem 2.2 in [5] says that a closed set in the plane is not a countable union of convex sets if, and only if, it contains an uncountable (actually perfect) 3-clique. Namely, the only reason for such S not to be a countable union of convex sets is that it contains an uncountable 3-clique.

Since, by this theorem, the full information about non-convexity of a closed planar set is stored in the collection of its 3-cliques, it is natural to try and classify non-convexity of such sets by classifying their 3-cliques. It turns out that the standard topological classification of closed countable sets — the Cantor Bendixon degree — indeed works: for every closed planar set which is a countable union of convex sets there exists a countable ordinal which bounds the Cantor Bendixon degrees of all 3-cliques in S. This ordinal is, then, the degree of non-convexity of S.

1.1. Statement of the results. Let S be a subset of a linear space. Call P ⊆ S an n-clique in S if n ≥ 2 and for every n-element subset X of P the convex closure of X is not contained in S. Let δ^{n}(S) be the supremum of Cantor-Bendixon degrees of all n-cliques in S. Since every n-clique is also an n + 1-clique, δ^{n}(S) ≤ δ^{n+1}(S) for all n ≥ 2. The rank δ(S) is the supremum over Cantor-Bendixon degrees of n-cliques for all n, that is, δ(S) = sup{δ^{n}(S) : n < ω}.

It is proved that for every closed set in a polish linear space, an uncountable δ implies an uncountable γ. Surely, if δ(S) is uncountable then δ^{n}(S) is uncountable for some n. In the case of closed planar sets this n has to be ≤ 3, by [5], theorem 2.2. Thus, (Corollary 6 below) for a closed planar S, the rank δ^{3}(S) is countable if and only if S is a countable union of convex sets. In other words, δ^{3} refines γ on closed planar sets by breaking the class of closed S ⊆ ℝ^{2} to ℵ_{1} + 1 classes, so that the top class is that of sets with uncountable γ and all smaller classes stratify the class of sets with countable γ. Since for countable sets the rank δ^{n} clearly coincides with the usual Cantor-Bendixon degree, any closed set of Cantor-Bendixon degree α is an example of a set with δ^{3}(S) = α; is is easy to construct uncountable sets of degree α as well.

Perles’ Example 2.1 in [5], in which γ is uncountable yet δ^{2} equals 1, shows that one cannot get similar classification with δ^{2} instead of δ^{3}. In dimension d > 2 a compact set may have δ-rank 1 but still have an uncountable γ (see [5], Example 4.2). Thus, Corollary 6 is sharp in two senses: first, δ^{3} cannot be weakened to δ^{2} and ℝ^{2} cannot be replaced by ℝ^{3}.

The last remark suggests that classification of closed, non-convex sets in ℝ^{3} requires other methods. A more complicated rank function classifies non convexity of closed sets in all finite dimensions. Such rank function exists and will be presented in [7].

1.2. History. Infinite unions of convex sets were studied in [5]. We refer the reader to that paper for basic facts and examples concerning such sets.

The following problem is still open:

Problem 1. Is it true that a closed planar set in which the closure of every visually independent subset is countable, is a countable union of convex sets?

This problem was asked by G. Kalai and only very minor step towards solving it direction was made ([5], Theorem 4.2).

1.3. Notation. Our notation is standard, except, maybe, for denoting the set of natural numbers by ω. A topological space X is polish if it is complete, metric and separable. A sequence is a function whose domain is an initial segment of ω. By n^{ω} we denote the space of all infinite sequences over n symbols and by n^{k} the set of sequences of length k over n symbols. The space n^{ω} is topologized by declaring the set of all infinite sequences that extend a given finite sequence as a basic open set. This topology is polish, by the metrics which assigns to two sequences η, ν ∈ n^{ω} the distance 1/k where k is the first coordinate in which η and ν are different. We write η ◁ ν to denote that the sequence η is an initial segment of the sequence ν and by η ν the concatenation of η with ν is denoted.

2. Cantor-Bendixon degrees and convexity

We begin by recalling the definition of the Cantor-Bendixon degree of a set S in some topological space X. A point x ∈ S is isolated in S, if there is an open neighborhood u ∋ x so that S ∩ u = {x}. By induction on ordinals define the α-th derived subset of S:

1. S^{(0)} = S

2. S^{(α+1)} = S^{(α)} − {x : x is isolated in S^{(α)}}.

3. If α is limit, then S^{(α)} = ⋂_{β<α} S^{(β)}

Let rk(S), the Cantor-Bendixon degree of S be the least ordinal α for which S^{(α)} = S^{(α+1)}. Thus, for example, the Cantor-Bendixon degree of a set which is dense in itself is 0.

Fact 2. If S is a subset of a polish space and rk(S) = α + 1 then there is a closed subset C ⊆ S with rk(C) = rk(S).

Given a set S and a point x ∈ S, the degree of x in S, which we denote by rk_{S}(x) is the last ordinal α for which x ∈ S^{(α)}, if x does not belong to S^{(α)} for all α; if x ∈ S^{(α)} for all α, we say that rk_{S}(x) = ∞. Clearly, for every set S and β < rk(S) there are points x ∈ S with rk_{S}(x) = β (but S^{rk(S)} may be null).

We remark that a separable metric space is second countable, and therefore the Cantor-Bendixon degree of every set in such a space is always countable.

3. Proofs

Definition 3. Let S be a set in a topological vector space. Let δ^{n}(S) be the supremum over all Cantor-Bendixon degrees of n-cliques in S. Let δ(S) := sup{δ^{n}(S) : n < ω}.

Theorem 4. Suppose that S is a closed set in a polish linear space E and γ(S) ≤ ℵ_{0}. Then δ(S) < ω_{1}.

Proof. Suppose that S ⊆ E, E is a polish linear space and δ(S) = ω_{1}. Let n ≥ 2 be the least so that δ^{n}(S) = ω_{1}. We may assume, then, that there are closed n-cliques of unbounded (countable) Cantor-Bendixon degrees in S.

Lemma 5. Suppose that u is an open neighborhood in E and that u contains ncliques in S of unbounded Cantor-Bendixon degrees. Then there exist open neighborhoods u_{0}, …, u_{n−1} such that for every i < n, clu_{i} ⊆ u, u_{i} contains cliques of unbounded Cantor-Bendixon degrees and so that for every choice of y_{i} ∈ clu_{i}, conv(y_{0}, …, y_{n−1}) ⊈ S.

Proof of Lemma. Fix a countable base B for the topology of E (e.g. all balls of rational radius and a center in some countable dense set).

Define now a mapping from ω_{1} to n-tuples from B, β ↦ (u_{i}^{β}, …, u_{n−1}^{β}), as follows. Let β < ω_{1} be given. Choose first an n-clique P ⊆ u and n points in P, x_{0}^{β}, …, x_{n−1}^{β} such that rk_{P} (x_{i}^{β}) ≥ β. Since the complement of S is open, there are open neighborhood u_{i} of x_{i}^{β} for i < n so that for every choice of y_{i} ∈ u_{i} it holds that conv(y_{0}, …, y_{n−1}) ⊈ S. By shrinking each u_{i}, we may assume that u_{i} ∈ B, clu_{i} ⊆ u and that conv(y_{0}, …, y_{n−1}) ⊈ S for every choice of y_{i} ∈ clu_{i}^{β}. Let (u_{i}^{β}, …, u_{n−1}^{β}) := (u_{0}, …, u_{n−1}).

Since there are only countably many n-tuples from B, there is a fixed n-tuple (u_{0}, …, u_{n−1}) and an unbounded I ⊆ ω_{1} so that (u_{0}, …, u_{n−1}) = (u_{0}^{β}, …, u_{n−1}^{β}) for every β ∈ I.

Therefore, for every i < n and an ordinal β < ω_{1}, there exists a closed clique P and a point x ∈ P ∩u_{i} with rk_{P} (x) ≥ β. Since u_{i} is open, rk(P ∩u_{i}) ≥ β. Therefore each u_{i} contains cliques of unbounded degrees.

Suppose now that S is closed, γ(S) ≤ ℵ_{0} and S contains n-cliques of unbounded degrees. By induction on k define neighborhoods u_{η} for η ∈ n^{k} so that:

1. d(u_{η}) < 1/k for all η, ν ∈ n^{k}.

2. η ◁ ν ⇒ clu_{ν} ⊆ u_{η}

3. u_{η} contains closed cliques in S of unbounded Cantor-Bendixon degrees.

4. if η_{0}, …, η_{n−1} are distinct and agree up to k − 1 then for every choice of y_{i} from clf(η_{i}) the convex closure of {y_{0}, …, y_{n−1}} is not contained in S.

At stage k + 1 use Lemma 5 to find, for each η ∈ n^{k}, sub-neighborhoods {u_{η i} : i < κ}, of u_{η}, which satisfy conditions 1–4 above.

Suppose now that u_{η} is defined for every finite sequence over n and define g : n^{ω} → S by g(η) := ⋂_{k} u_{η↾k}. Since E is complete, g is well defined. Since S is closed, g(η) ∈ S for every η ∈ n^{ω}.

Suppose now that S = ⋃_{n} C_{n}. The space n^{ω} of all infinite sequences over n symbols is a complete separable metric space under the metrics d(η, ν) = 1/k for the least k such that η(k) ≠ ν(k). By the Baire category theorem, there is some index m so that f^{−1}(C_{m}) is somewhere dense. Choose some k and a sequence ν ∈ n^{k} so that f^{−1}(C_{m}) is dense in {η ∈ n^{ω} : ν ◁ η}. For every i < n there must be, then, a sequence η_{i} so that η_{i}↾k + 1 = η i, and f(η_{i}) ∈ C_{m}. But then f(η_{i}) ∈ u_{η i} by the definition of g, and therefore conv(g(η_{0}), …, g(η_{n−1})) ⊈ S by condition 4. Therefore C_{m} is not convex.

Corollary 6. A closed planar set is a countable union of convex sets if and only if δ^{3}(S) < ω_{1}.

Proof. One direction is proved above.

For the other direction suppose that S ⊆ ℝ^{3} is closed and is not a countable union of convex sets. By Shelah’s theorem there is a perfect 3-clique P ⊆ S. Every subset of P is a 3-clique, and since P is perfect, it contains countable sets of unbounded Cantor-Bendixon degrees.

We observe that Perles’ Example 2.1 in [5], of a compact planar set S, satisfies that δ^{2}(S) = 1 while δ^{3}(S) = ω_{1}. Hence, classification by δ^{2} does not refine the classification by γ.

It is natural to ask at this point whether δ^{4}(S) classifies non-convexity of closed sets in ℝ^{3} analogously to the manner δ^{3} classifies closed sets in ℝ^{2}. This is false by Example 4.1 in [5]. This example is of a compact S ⊆ ℝ^{3} with δ(S) = 1 and γ(S) > ℵ_{0}.

References

[1] Marylin Breen. A decomposition theorem for m-convex sets. Israel J. Math., 24:211–216, 1976.

[2] Marylin Breen. An R^{d} analogue of Valentine’s theorem on 3-convex sets. Israel J. Math., 24:206–210, 1976.

[3] Marylin Breen and David C. Kay. General decomposition theorems for m-convex sets in the plane. Israel J. Math., 24:217–233, 1976.

[4] H. G. Eggleston. A condition for a compact plane set to be a union of finitely many convex sets. Proc. Camb. Phil. Soc, 76:61–66, 1974.

[5] M. Kojman, M. A. Perles, and S. Shelah. Sets in a Euclidean space which are not a countable union of convex subsets. Israel J. Math., 70(3):313–342, 1990.

[6] Jiri Matousek and Pavel Valtr. On visibility and covering by convex sets. Israel J. math, 1998. in press.

[7] Menachem Kojman. Classifying non convexity in higher dimensions. in preparation.

[8] M. A. Perles and S. Shelah. A closed n + 1-convex set in R^{2} is the union of n^{6} convex sets. Israel J. math., 70:305–312, 1990.

[9] F. A. Valentine. A three point convexity property. Pacific J. Math., 7:1227–1235, 1957.

Department of Mathematics and Computer Science, Ben Gurion University of the Negev, Beer Sheva, Israel

   E-mail address: kojman@cs.bgu.ac.il