Perfect cliques and G_{δ} colorings of Polish spaces

Wiesław Kubiś

Ben-Gurion University of the Negev, Beer-Sheva Israel and University of Silesia, Katowice Poland

                      E-mail: kubis@math.bgu.ac.il

July, 2001

Abstract

A coloring of a set X is any subset C of [X]^{N}, where N > 1 is a natural number. We give some sufficient conditions for the existence of a perfect C-homogeneous set, in case where C is G_{δ} and X is a Polish space. In particular, we show that it is sufficient that there exist C-homogeneous sets of arbitrarily large countable Cantor-Bendixson rank. We apply our methods to show that an analytic subset of the plane contains a perfect 3-clique if it contains any uncountable k-clique, where k is a natural number or ℵ_{0} (a set K is a k-clique in X if the convex hull of any of its k-element subsets is not contained in X).

2000 AMS Subject Classification: Primary: 52A37, 54H05, Secondary: 03E02, 52A10. Keywords: Open (G_{δ}) coloring, perfect homogeneous set, clique.

1 Introduction

For a set X and natural number N, [X]^{N} denotes the collection of all N-element subsets of X. A (two-color) coloring of X is (represented by) a set C ⊆ [X]^{N}. We identify [X]^{N} with a suitable subspace of the product X^{N}. We are interested in the following problem: find sufficient conditions for the existence of a perfect C-homogeneous set P ⊆ X, where X is a Polish space and C ⊆ [X]^{N} is open (or more generally G_{δ}). A natural example for this problem is the following: let X ⊆ ℝ^{N} be closed and C = {s ∈ [X]^{k}: conv s ⊈ X}. Then C is open and a C-homogeneous set is called a k-clique in X. It is known (see [3]) that there exists a closed set X ⊆ ℝ^{2} such that X is not a countable union of convex sets but every k-clique in X is countable for every k < ω. On the other hand, it is proved in [3] that if a closed set X ⊆ ℝ^{2} contains an uncountable k-clique for some k then it contains a perfect 3-clique. We prove that if C is a G_{δ} coloring of a Polish space and there are no perfect C-homogeneous sets, then there is a countable ordinal γ such that the Cantor-Bendixson rank of every Chomogeneous set is < γ. In the context of cliques, this strengthens the result of Kojman [2] (see Theorem 3.1(a) below). From our result it follows that if C is a G_{δ} coloring of an analytic space then either there exists a perfect C-homogeneous set or all C-homogeneous sets are countable. This is not true for F_{σ} colorings: a result of Shelah [4] states that consistently there exist F_{σ} 2-colorings with uncountable but not perfect homogeneous sets. Concerning cliques, we investigate analytic subsets of the plane. We prove that if an analytic set X ⊆ ℝ^{2} contains an uncountable ℵ_{0}-clique then X contains also a perfect 3-clique.

1.1 Notation

Any subset of [X]^{N} is called a coloring (or an N-coloring) of X. We write ¬C instead of [X]^{N} \ C. A set S ⊆ X is C-homogeneous if [A]^{N} ⊆ C. We identify [X]^{N} with the subspace of X^{N} consisting of all N-tuples (x_{0}, …, x_{N−1}) with x_{i} ≠ x_{j} for i ≠ j. Thus we may consider topological properties of colorings. If f: X → Y is a function then we write f[S] for the image of a set S ⊆ X and f(s) for the value at a point s ∈ X. By a perfect set we mean a compact, nonempty, topological space with no isolated points.

2 On colorings

First we recall a simple result on open 2-colorings of analytic spaces (see Todorčević-Farah’s book [5, p. 81]). We present a proof for completeness.

Proposition 2.1. Let X be an analytic space and let C ⊆ [X]^{2} be open. Then either there exists a perfect C-homogeneous set or else X is a countable union of ¬C-homogeneous sets, i.e. X = ⋃_{n∈ω} A_{n} where [A_{n}]^{2} ∩ C = ∅ for every n ∈ ω.

Proof. Let f: ω^{ω} → X be continuous and onto X. Define

C′ = {s ∈ [ω^{ω}]^{2} : f[s] ∈ C}.

Note that if {x, y} ∈ C′ then f(x) ≠ f(y). Now observe that if ω^{ω} is a union of countably many ¬C′-homogeneous sets, then the same holds for X. Also, if P is a compact, perfect, C′- homogeneous subset of ω^{ω} then f ↾ P is one-to-one and hence f[P] is a perfect C-homogeneous set. Thus we may assume that X = ω^{ω} and that X cannot be covered by countably many ¬C-homogeneous sets. Let V consist of all x ∈ ω^{ω} such that some neighborhood of x is a countable union of ¬Chomogeneous sets. By assumption, it follows that V ≠ ω^{ω}. Let B = ω^{ω} \ V. Now we are working in B: construct a tree T = {u_{s}: s ∈ 2^{<ω}} of open subsets of B such that T defines a Cantor set and {x, y} ∈ C whenever x ∈ u_{s}, y ∈ u_{t} and s, t ∈ 2^{k} are distinct, k < ω. Coming to split u_{s}, where s ∈ 2^{k}, we first find a pair {x, y} ∈ [u_{s}]^{2} ∩ C (this is possible since u_{s} is not ¬C-homogeneous). Next, using the fact that C is open, enlarge x, y to open sets u_{s^{⌢}0}, u_{s^{⌢}1}, preserving C-homogeneity. The perfect set obtained from T is evidently C-homogeneous.

The above result is no longer valid when we replace the word ”open” with ”closed”, see [5, p. 83]. Also, the above proposition cannot be strengthened for colorings of triples: there exists a clopen 3-coloring of 2^{ω} such that there are no uncountable homogeneous sets neither of this color nor of its complement, see Blass’ example [1]. In this example, the Cantor-Bendixson rank of any homogeneous set is at most 1. Below we show that in this situation, there always exists a countable ordinal which bounds the Cantor-Bendixson ranks of all homogeneous sets. In fact this is true for G_{δ} colorings. For a topological space Y and an ordinal α we denote by Y^{(α)} the α-derivative of Y; the Cantor-Bendixson rank of Y is the minimal ordinal γ such that Y^{(γ+1)} is empty.

Theorem 2.2. Let C be a G_{δ} N-coloring of a Polish space X. If for every countable ordinal γ there exists a C-homogeneous set of the Cantor-Bendixson rank ⩾ γ then X contains a perfect C-homogeneous set.

Proof. Fix a countable base B in X and fix a complete metric on X. Let C = ⋂_{n∈ω} C_{n}, where each C_{n} is open and C_{n+1} ⊆ C_{n}. We will construct a tree of open sets T = {u_{s}: s ∈ 2^{<ω}} with the following properties:

(i) cl u_{s^{⌢}i} ⊆ u_{s}, cl u_{s} ∩ cl u_{t} = ∅ if s, t are incompatible and diam(u_{s}) < 2^{− length(s)};

(ii) if k < ω and s_{0}, …, s_{N−1} ∈ 2^{k} are pairwise distinct then

{x_{0}, …, x_{N−1}} ∈ C_{k}

whenever x_{i} ∈ u_{s_{i}}, i < N;

(iii) if k < ω then for each γ < ω_{1} there exists a C-homogeneous set P = P_{k,γ} such that P^{(γ)} ∩ u_{s} ≠ ∅ for each s ∈ 2^{k}.

We start with u_{∅} = X. Suppose that u_{s} has been defined for all s ∈ 2^{⩽k}. Fix γ < ω_{1} and consider P = P_{k,γ+1}, as in (iii). Then for each s ∈ 2^{k} the set P^{(γ)} ∩ u_{s} is infinite. Fix S ⊆ P^{(γ)} such that |S ∩ u_{s}| = 2 for each s ∈ 2^{k}. Next, enlarge each x ∈ S ∩ u_{s} to a small open set v_{x} ∈ B, contained in u_{s}, such that {y_{0}, …, y_{N−1}} ∈ C_{k+1} whenever y_{i} are taken from pairwise distinct v_{x}’s. This is possible, because C_{k+1} is open. Let φ(γ) = {v_{x}: x ∈ S}. This defines a mapping φ: ω_{1} → [B]^{<ω}. As B is countable, there is unbounded F ⊆ ω_{1} such that φ ↾ F is constant, say {v_{s^{⌢}i}: s ∈ 2^{k}, i < 2}, where v_{s^{⌢}i} ⊆ u_{s}. Set u_{s^{⌢}i} = v_{s^{⌢}i}. Observe that (i) holds if we let v_{x}’s to be small enough. Also (ii) holds, by the definition of v_{x}’s. Finally, (iii) holds, because P_{k,γ+1}^{(γ)} ∩ u_{t} ≠ ∅ for t ∈ 2^{k+1} whenever γ ∈ F. By (ii) the perfect set obtained from this construction is C-homogeneous.

Using the above theorem and arguments from the proof of Proposition 2.1 we obtain the following (see Shelah [4, Remark 1.14]):

Corollary 2.3. Let 1 ⩽ N < ω and let C be a G_{δ} N-coloring of an analytic space X. If there exists an uncountable C-homogeneous set then there exists also a perfect one.

3 Applications to convexity

Let X ⊆ E, where E is a real vector space. A subset K of X is a k-clique (k can be a cardinal or just a natural number, we will use this notion for k < ω and k = ℵ_{0}) if conv S ⊈ X whenever S ∈ [K]^{k}. If E is finite-dimensional and k > dim E then we can define the notion of a strong k-clique replacing conv S by int conv S in the definition. A finite set S ⊆ X is (strongly) defected in X if conv S ⊈ X (int conv S ⊈ X). It is clear that the relation of strong defectedness is open and defectedness is open provided that X is closed. Applying the results of the previous section we get the following:

Theorem 3.1. (a) Let X be a closed set in a Polish linear space and let N < ω. If X does not contain a perfect N-clique then all N-cliques in X are countable. Moreover, there exists an ordinal γ < ω_{1} which bounds the Cantor-Bendixson ranks of all N-cliques in X.

(b) Let X be an analytic subset of ℝ^{m}. If m < N < ω and X contains an uncountable strong N-clique then X contains also a perfect one.

Theorem 3.1(a) was proved, under the stronger assumption that X is a countable union of convex sets, by Kojman in [2]. In [3] we proved, in particular, that in a closed planar set either all cliques are countable or there exists a perfect 3-clique. Here we prove the same for analytic sets, namely:

Theorem 3.2. Let X ⊆ ℝ^{2} be analytic. If X contains an uncountable ℵ_{0}-clique then X contains a perfect 3-clique.

Proof. Fix a continuous function f: ω^{ω} → X onto X and fix an uncountable ℵ_{0}-clique K ⊆ X. We may assume that every line contains only countably many points of L: otherwise, for some line L, X ∩ L contains an uncountable ℵ_{0}-clique, so it contains a perfect 2-clique (Proposition 2.1), which is also a 3-clique in X. Fix uncountable K′ ⊆ ω^{ω} such that f ↾ K′ is a bijection onto K. A finite collection {u_{0}, …, u_{k−1}} of open subsets of ω^{ω} will be called relevant if each u_{i} contains uncountably many points of K′, cl u_{i} ∩ cl u_{j} = ∅ whenever i < j < k and

int conv{f(x_{0}), f(x_{1}), f(x_{2})} ⊈ X

whenever x_{0}, x_{1}, x_{2} are taken from pairwise distinct u_{i}’s. To find a perfect 3-clique in X, it suffices to construct a perfect tree of open sets in ω^{ω} with relevant levels. If P is a perfect set obtained from such a tree then f ↾ P is one-to-one and f[P] is a perfect strong 3-clique. Suppose that we have a relevant collection {u_{0}, …, u_{k}}. We have to show that it is possible to split each u_{i} to obtain again a relevant collection. We will split u_{k}. Let L = K′ ∩ u_{k} and pick y_{i} ∈ u_{i} for i < k. Define c_{i}: [L]^{2} → 2 by letting c_{i}(x_{0}, x_{1}) = 1 iff conv{f(x_{0}), f(x_{1}), f(y_{i})} ⊈ X. Observe that there are no infinite c_{i}-homogeneous sets of color 0: if S ⊆ L is infinite then, by Carathéodory’s theorem, there is s ∈ [S]^{3} such that f[s] is defected in X (because f[S] is defected) and hence for some x_{0}, x_{1} ∈ s we have conv{f(x_{0}), f(x_{1}), f(y_{i})} ⊈ X, because conv T ⊆ ⋃_{x,y∈T} conv{x, y, p} for T ⊆ ℝ^{2}, p ∈ ℝ^{2}. Using k times the theorem of Dushnik-Miller we obtain uncountable L′ ⊆ L which is c_{i}-homogeneous of color 1 for i < k. Shrinking L′ we may assume that each nonempty open subset of L′ is uncountable. Now choose disjoint open sets v_{0}, v_{1} with cl v_{j} ⊆ u_{k} and v_{j} ∩ L′ ≠ ∅ for j < 2. To finish the proof we need the following geometric property of the plane:

Claim 3.3. Let A, B ⊆ X ⊆ ℝ^{2} and c ∈ ℝ^{2} be such that A, B are uncountable, each line contains countably many points of A ∪ B and conv{a, b, c} ⊈ X whenever a ∈ A, b ∈ B. Then there are a_{0} ∈ A, b_{0} ∈ B such that int conv{a_{0}, b_{0}, c} ⊈ X.

Proof. Suppose this is not true. Observe that, replacing A and B if necessary, we may assume that for some b_{0} ∈ B, [a, b_{0}] ∪ [a, c] ⊈ X whenever a ∈ A. Indeed, if [b, c] ⊆ X for some b ∈ B then we take b_{0} = b, otherwise we take any a_{0} ∈ A and we replace A and B. Now, without loss of generality, we may assume that b_{0} = (−1, 0), c = (1, 0) and A is contained in (−1, 1) × (0, 1). Now, if some vertical line contains two elements of A then we are done: we take a_{0} ∈ A such that some a_{1} ∈ A is below a_{0}, then the relative interiors of segments [b_{0}, a_{1}], [c, a_{1}] are contained in the interior of conv{a_{0}, b_{0}, c}. Assume that each vertical line contains at most one element of A. As A is uncountable, there is a_{1} ∈ A such that arbitrarily close to a_{1} there are uncountably many points both on the left and the right side of a_{1}. Suppose now that e.g. {b_{0}, a_{1}} is defected in X. As [b_{0}, a_{1}] contains only countably many points of A, we can find a_{2} ∈ A which is close enough to a_{1}, on the left side of a_{1} and not in [b_{0}, a_{1}]. If a_{2} is below [b_{0}, a_{1}] then we can set a_{0} = a_{1}, otherwise we can set a_{0} = a_{2}.

Let i = 0. Using Claim 3.3 for A = f[v_{0} ∩L′], B = f[v_{1} ∩L′] and c = f(y_{i}) we get x_{j} ∈ v_{j} such that int conv{f(x_{0}), f(x_{1}), f(y_{i})} ⊈ X. By continuity, shrink v_{0}, v_{1} and enlarge y_{i} to an open set u′_{i} ⊆ u_{i} such that each triple selected from f[v_{0}] × f[v_{1}] × f[u′_{i}] is (strongly) defected in X. Repeat the same argument for each i < k, obtaining a relevant collection {u′_{0}, …, u′_{k−1}, v′_{0}, v′_{1}} which realizes the splitting of u_{k}. This completes the proof.

Actually, we have proved that if an analytic planar set X contains any uncountable ℵ_{0}-clique then either X contains a perfect strong 3-clique or else, X ∩ L contains a perfect 2-clique for some line L.

References

[1] A. Blass, A partition theorem for perfect sets, Proc. Amer. Math. Soc. 82 (1981) 271-277.

[2] M. Kojman, Cantor-Bendixson degrees and convexity in ℝ^{2}, Israel J. Math. 121 (2001) 85-91.

[3] S. Geschke, M. Kojman, W. Kubiś, R. Schipperus, Convex decompositions in the plane and continuous pair colorings of the irrationals, submitted.

[4] S. Shelah, Borel sets with large squares, Fund. Math. 159 (1999) 1-50.

[5] S. Todorchevich, I. Farah, Some Applications of the Method of Forcing, Yenisei, Moscow 1995.