CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS

STEFAN GESCHKE, MARTIN GOLDSTERN, AND MENACHEM KOJMAN^{†}

Abstract. We investigate the Ramsey theory of continuous graph-structures on complete, separable metric spaces and apply the results to the problem of covering a plane by functions.

Let the homogeneity number 𝔥𝔪(c) of a pair-coloring c : [X]^{2} → 2 be the number of c-homogeneous subsets of X needed to cover X. We isolate two continuous pair-colorings on the Cantor space 2^{ω}, c_{min} and c_{max}, which satisfy 𝔥𝔪(c_{min}) ≤ 𝔥𝔪(c_{max}) and prove: Theorem. (1) For every Polish space X and every continuous pair-coloring

c : [X]^{2} → 2 with 𝔥𝔪(c) > ℵ_{0},

𝔥𝔪(c) = 𝔥𝔪(c_{min}) or 𝔥𝔪(c) = 𝔥𝔪(c_{max}).

(2) There is a model of set theory in which 𝔥𝔪(c_{min}) = ℵ_{1} and 𝔥𝔪(c_{max}) =

ℵ_{2}. The consistency of 𝔥𝔪(c_{min}) = 2^{ℵ_{0}} and of 𝔥𝔪(c_{max}) < 2^{ℵ_{0}} follows from

[20].

We prove that 𝔥𝔪(c_{min}) is equal to the covering number of (2^{ω})^{2} by graphs of Lipschitz functions and their reflections on the diagonal. An iteration of an optimal forcing notion associated to c_{min} gives: Theorem. There is a model of set theory in which

(1) ℝ^{2} is coverable by ℵ_{1} graphs and reflections of graphs of continuous real functions;

(2) ℝ^{2} is not coverable by ℵ_{1} graphs and reflections of graphs of Lipschitz

real functions. Diagram 1 in the introduction summarizes the ZFC results in Part I of

the paper. The independence results in Part II show that any two rows in Diagram 1 can be separated if one excludes Cov(Lip(ℝ)) from row (3).

1. Introduction

In this paper we study Ramsey properties of continuous graph structures on Polish spaces. A continuous graph-structure on a Polish space X is a pair-coloring c : [X]^{2} → {0, 1} which is continuous with respect to the natural topology on unordered pairs from X. The Ramsey invariant which we use to classify such colorings is the homogeneity number: the least number of homogeneous subsets (of both colors) required to cover X.

Let us explain briefly how set-theoretic study of continuous pair-colorings leads to the consideration of homogeneity numbers. It is not hard to check that for every continuous pair-coloring on an uncountable Polish space there is a homogeneous subset which is perfect, and hence of size continuum, and that the chromatic number

Date: August 11, 2004. 2000 Mathematics Subject Classification. Primary: 03E17, 03E35, 05C55; Secondary: 26A15,

26A16.

Key words and phrases. pair coloring, continuous coloring, homogeneity number, Polish space, Cantor set, Lipschitz function, covering number, optimal forcing, tree forcing, perfect graphs.

† Research partially supported by Israeli Science foundation grant no. 177/01.

2 STEFAN GESCHKE, MARTIN GOLDSTERN, AND MENACHEM KOJMAN^{†}

of the coloring — that is, the number of homogeneous subsets of color 0 required to cover the space — is either countable or continuum^{1}.

This means that, from a set-theoretic point of view, these standard invariants are degenerate. The homogeneity number of continuous pair-colorings is a natural generalization of the chromatic number which is not set-theoretically degenerate. The classification of homogeneity numbers on Polish spaces leads both to an interesting theory in ZFC and to interesting meta-mathematics.

A second reason for the consideration of homogeneity numbers comes from convexity theory. For certain closed subsets of ℝ^{2} the number of convex subsets required to cover them is equal to the homogeneity number 𝔥𝔪(c) of some continuous pair-coloring c on the Baire space [20]. Thus, homogeneity numbers measure the complexity of convex decompositions of certain closed planar sets.

Homogeneity numbers of continuous pair-colorings relate to at least two more subjects. The crucial inequality (Theorem 3.9 below), which reduces general continuous pair-colorings to compact ones, involves the notion of covering a plane by functions. About half of the paper is devoted to that subject. The connection between continuous pair-colorings and covering a plane by functions works in both ways: after establishing the classifications of homogeneity numbers we have at hand an optimal forcing for proving the consistency of “more Lipschitz functions are required to cover (2^{ω})^{2} than continuous ones”. This consistency result implies the consistency of “more Lipschitz functions are required to cover ℝ^{2} than continuous ones”.

Finally, it is perhaps a bit surprising that the classification of continuous homogeneity numbers is related to perfect graphs (see the recent survey [11] and [12]). The forcing construction that separates 𝔥𝔪(c_{min}) from 𝔥𝔪(c_{max}) (Section 4 below) makes a crucial use of a Ramsey connection between perfect graphs and random graphs [4].

Within set theory, continuous pair-colorings are naturally related to the broader class of open colorings, that has been a focus of interest for set theorists for three decades now, and motivated several important developments in the technique of forcing [7, 8, 2]. Open coloring axioms, which are statements in the Ramsey theory of open colorings, are among the more frequently used set-theoretic axioms in the theory of the continuum (see [33, 32, 17, 27] and the references therein).

1.1. The results. Two simple pair-colorings c_{min} and c_{max} are defined on the Cantor space, and are shown to satisfy for every Polish space X and every continuous c : [X]^{2} → 2 with uncountable 𝔥𝔪(c):

𝔥𝔪(c_{min}) ≤ 𝔥𝔪(c) ≤ 𝔥𝔪(c_{max})  (1)

To state the remaining results concisely, we briefly introduce some notation. A function f : X → X covers a point (x, y) ∈ X^{2} if f(x) = y or f(y) = x. For a metric space (X, dist) let Cov(Lip(X)) denote the number of Lipschitz functions from X to X required to cover X^{2} and Cov(Cont(X)) denote the analogous numbers for continuous functions. The Baire space ω^{ω} and the Cantor space 2^{ω} are considered with the standard metric dist(x, y) = \frac{1}{2^{Δ(x,y)}} , where Δ(x, y) = min\{n : x(n) ≠ y(n)\} for x ≠ y.

The remaining ZFC equalities and inequalities are summarized in Diagram 1.

Homogeneity numbers are on the right column and covering-by-functions cardinals are on the middle column. We draw attention to the fact that the rows (2)–(6) have to share at most two consecutive cardinals since Cov(Cont(2^{ω})) cannot be

1This holds for every open coloring on an analytic set [18].

(6)  ( Cov(Cont(2^{ω})))^{+}

(5)  2^{ℵ_{0}}

(4)  𝔥𝔪(c_{max})

(3) Cov(Lip(ℝ)) ≥ Cov(Lip(ω^{ω})) = Cov(Lip(2^{ω})) = 𝔥𝔪(c_{min})

(2) Cov(Cont(ℝ)) = Cov(Cont(ω^{ω})) = Cov(Cont(2^{ω}))

(1)  𝔡

Diagram 1

more than one cardinal below 2^{ℵ_{0}}; thus, four different models of set theory are required to separate them from each other.

The independence results in Part II of the paper show that after excluding Cov(Lip(ℝ)) from row (3) for each of the rows (1)–(5) it is consistent that the value at the row is ℵ_{1} and at all rows above the value is ℵ_{2}. The forcing for separating (2) from (3) is a new example of an optimal forcing in the sense of Zapletal [34] for increasing a cardinal invariant while leaving small everything that can be left small.

The inequality Cov(Lip(2^{ω})) ≤ 𝔥𝔪(c_{min}) and the consistency of 𝔥𝔪(c) < 2^{ℵ_{0}} for every Polish space X and continuous c : [X]^{2} → 2 were proved in [20].

The last inequality cannot hold for all open colorings. In [2] an example of an open pair-coloring on the square of any uncountable Polish space X is given such that X^{2} cannot be covered by fewer than 2^{ℵ_{0}} homogeneous sets. Let us present a slightly simplified version of this coloring.

An unordered pair {(x_{0}, y_{0}), (x_{1}, y_{1})} of elements of X^{2} is of color 0 if it is a 1-1-function and of color 1 otherwise. The set of pairs of color 0 is open. If H ⊆ X^{2} is homogeneous of color 1, then it is either (a part of) a row or (a part of) a column in the square. The homogeneous sets of color 0 are graphs of (partial) injective functions. It is easily checked that X^{2} cannot be covered by less than 2^{ℵ_{0}} homogeneous sets.

1.1.1. Structure of the paper. The paper is divided to two parts. Absolute ZFC results are in Part I and independence results are in Part II. Notation, preliminaries and background material are included at the beginning of each section. The first part employs elementary techniques and does not require any specialized knowledge.

Although we are supposed to assume that every reader will read the whole paper, we suspect that those who will read the second part are knowledgeable in forcing notation. For those readers who read the first part and decide that they have to learn forcing so that they can read the second part, we recommend the standard [26, 6] as sources for notation and introduction to forcing.

We tried to keep notation as standard as possible.

Part I: Results in ZFC

2. The structure of Continuous pair-colorings on Polish spaces

2.1. Basic definitions and preliminary facts.

2.1.1. Colorings, chromatic numbers, and homogeneity numbers. The symbol [A]^{2} denotes the set of all two-element subsets of a set A. Ramsey’s theorem states that if A is infinite, then for every function c : [A]^{2} → 2 := {0, 1} there is an infinite set B ⊆ A so that c is constant on [B]^{2}. A function c : [A]^{2} → 2 is called a paircoloring, and a set B ⊆ A for which c ↾ [B]^{2} is constant is called c-homogeneous or c-monochromatic. In the future we write just c ↾ B instead of c ↾ [B]^{2}. A set H is c-homogeneous of color i for i ∈ 2, if the constant color on H is i.

A pair coloring c on A can be thought of as (the characteristic function of) the edge relation of a graph G = (A, c). In this setting Ramsey’s theorem states that every infinite graph contains either an infinite clique — a subgraph in which any pair of vertices forms an edge — or an infinite independent set — a subset in which no two vertices form an edge.

Recall that the chromatic number of a graph is the least number of independent sets required to cover the set of vertices. Definition 2.1. For a coloring c : [A]^{2} → 2 the homogeneity number of c, denoted by 𝔥𝔪(c), is the minimal number of c-homogeneous subsets required to cover A.

The difference between chromatic and homogeneity numbers is that in the definition of the latter covering is by homogeneous sets of both colors.

2.1.2. Continuous colorings on Polish spaces. Let X be a topological space and let X^{2} := X × X with the product topology. We identify [X]^{2} with the quotient space (X^{2}\{(x, x) : x ∈ X})/ ∼, where (x, y) ∼ (w, z) iff (x, y) = (w, z) or (x, y) = (z, w). Theorem 2.2 (Eilenberg 1941). If X is a connected topological space with more than one point, then [X]^{2} is connected.

Proof. Eilenberg’s Theorem 1 in [14] states that if X is connected and contains more than one point, then either X^{2} \ {(x, x) : x ∈ x} is connected or else X can be linearly ordered by a relation < so that the topology of X refines the order topology defined by < and so that the connected components of X^{2} \ {(x, x) : x ∈ X} are {(x, y) : x < y} and {(x, y) : y < x}. In the former case [X]^{2} is connected as a continuous image of a connected space and in the latter case [X]^{2} is connected because it is homeomorphic to the connected component {(x, y) : x < y}. □

We thank Apollo Hogan for pointing out Theorem 2.2 and referring us to Eilenberg’s paper.

A coloring c : [X]^{2} → 2 is continuous if the preimages of 0 and of 1 are open. Equivalently, c is continuous if for all {x, y} ∈ [X]^{2}, there are disjoint open neighborhoods U and V of x and y, respectively, such that c is constant on U × V. Here we identify c with the corresponding symmetric function from X^{2} \{(x, x) : x ∈ X} to 2. By Theorem 2.2, there are no non-constant continuous colorings of [X]^{2} if X is connected.

A topological space X is Polish if it is homeomorphic to a separable and complete metric space. Every Polish space is a disjoint union of a countable open scattered subset with a perfect subset (where either of the two components may be empty). Since every nonempty perfect subset of a Polish space has the cardinality of the continuum, every uncountable Polish space is equinumerous with the continuum. Definition 2.3. (1) A pair-coloring c on X is reduced if c is continuous and

no nonempty open subset of X is c-homogeneous.

(2) A coloring c : [X]^{2} → 2 is trivial if 𝔥𝔪(c) ≤ ℵ_{0}.

Fact 2.4. If X is a Polish space and c : [X]^{2} → 2, then X = X_{0} ∪ X_{1} such that X_{0} is open, X_{1} is perfect, X_{0} ∩ X_{1} = ∅, c ↾ X_{0} is trivial and c ↾ X_{1} is reduced.

Proof. Let X_{0} be the union of all open sets U ⊆ X for which c ↾ U is trivial. X_{0} is open and since X has a countable basis, c is trivial on X_{0}. Let X_{1} = X \ X_{0}. □

Fact 2.5. A continuous pair-coloring on a Polish space X satisfies 𝔥𝔪(c) > ℵ_{0} if and only if there exists a nonempty perfect Y ⊆ X so that 𝔥𝔪(c) = 𝔥𝔪(c ↾ Y) and c ↾ Y is reduced.

Proof. Suppose 𝔥𝔪(c) > ℵ_{0} and write X = X_{0} ∪ X_{1} as stated in the previous Fact. So c ↾ X_{1} is reduced. Since 𝔥𝔪(c ↾ X_{0}) ≤ ℵ_{0} it follows that 𝔥𝔪(c) = 𝔥𝔪(c ↾ X_{1}) and clearly X_{1} ≠ ∅. On the other hand, suppose Y ⊆ X is perfect and nonempty, that 𝔥𝔪(c) = 𝔥𝔪(c ↾ Y) and c ↾ Y is reduced. Continuity of c gives that the closure of every c-homogeneous set is again c-homogeneous; so if Y ⊆ X is perfect and c ↾ Y is reduced, every c-homogeneous subset of Y is nowhere dense and by the Baire theorem 𝔥𝔪(c) > ℵ_{0}. □

2.1.3. Notation. Let ω^{ω} denote the set of all (infinite) sequences of natural numbers. Let ω^{<ω} denote the set of all finite sequences of natural numbers and let ω^{≤ω} = ω^{<ω} ∪ ω^{ω}. Similarly, 2^{ω}, 2^{<ω}, 2^{≤ω} are the analogous sets for sequences over {0, 1}. Definition 2.6. For x, y ∈ ω^{≤ω} let Δ(x, y) = min{n ∈ ω : x(n) ≠ y(n)} if there is some n ∈ ω such that x(n) ≠ y(n). Otherwise Δ(x, y) is undefined.

If Δ(x, y) is defined for x, y ∈ ω^{≤ω}, put

dist(x, y) := \frac{1}{2^{Δ(x,y)}}

If Δ(x, y) is not defined, put dist(x, y) := 0.

The function dist satisfies the triangle inequality. In fact, it satisfies a stronger inequality: dist(x, z) ≤ max{dist(x, y), dist(y, z)} for all x, y, z. (This makes dist an ultra-metric.)

The following Polish spaces play an important role in this section: the Cantor space (2^{ω}, dist) and the Baire space (ω^{ω}, dist). These spaces are indeed complete, separable metric spaces. The Cantor space is homeomorphic to the usual Cantor set and the Baire space is homeomorphic the space of irrational numbers.

2.1.4. The minimal coloring c_{min}. Definition 2.7. If X and Y are topological spaces and c and d are continuous pair-colorings on X and Y, respectively, then we write c ≤ d if there is a topological embedding e : X → Y, such that for all {x_{0}, x_{1}} ∈ [X]^{2}, c(x_{0}, x_{1}) = d(e(x_{0}), e(x_{1})).

Clearly, if c ≤ d via an embedding e : X → Y, then e^{−1}[A] is c-homogeneous for every d-homogeneous A ⊆ Y. Hence, c ≤ d implies that 𝔥𝔪(c) ≤ 𝔥𝔪(d).

We introduce next a pair coloring c_{min} on the Cantor space which satisfies c_{min} ≤ c for all reduced c. Definition 2.8. (1) Let parity(x, y) denote the parity of Δ(x, y) for x, y ∈

ω^{≤ω} such that Δ(x, y) is defined.

(2) Let c_{parity} := parity ↾ ω^{ω}.

(3) Let c_{min} := parity ↾ 2^{ω}.

Clearly, c_{parity} is a reduced pair-coloring on ω^{ω} and c_{min} is a reduced pair-coloring on 2^{ω}.

If H ⊆ 2^{ω} is c_{min}-homogeneous of color 0, then all splittings in T (H), the tree of all finite initial segments of members of H, occur on even levels. If T is a subtree of ω^{<ω}, we identify every infinite branch of T with its union, a point in ω^{ω}. A set H ⊆ 2^{ω} is, then, maximal c_{min}-homogeneous of color 0 is if and only if H is the set of all infinite branches of a tree T in which t ∈ T has two immediate successors if |t| is even and one immediate successor if |t| is odd. Similarly, H is maximal c_{min}-homogeneous of color 1 if and only if it is the set of all infinite branches of a tree T such that t ∈ T has two immediate successors in T if |t| is odd and one immediate successor in T if |t| is even.

Lemma 2.9. For every reduced pair-coloring c on a Polish space we have:

c_{min} ≤ c.

Consequently, 𝔥𝔪(c_{min}) ≤ 𝔥𝔪(c) for every reduced c.

Proof. Suppose c : [X]^{2} → 2 is reduced and X is Polish. Since no nonempty open set is c-homogeneous in X, X has no isolated points.

By induction on n choose, for every t ∈ 2^{n}, an open set U_{t} ≠ ∅ of diameter < 1/n such that

– t ⊆ s ⇒ cl(U_{s}) ⊆ U_{t},
– Δ(t_{1}, t_{2}) defined implies that cl(U_{t_{1}}) ∩ cl(U_{t_{2}}) = ∅ and
for all x_{1} ∈ cl(U_{t_{1}}), x_{2} ∈ cl(U_{t_{2}}): c(x_{1}, x_{2}) ≡ Δ(t_{1}, t_{2}) mod 2.

At the induction step, for a given t ∈ 2^{n} find x_{1}, x_{2} ∈ U_{t} which satisfy c(x_{1}, x_{2}) ≡ n mod 2 (possible since U_{t} is not c-homogeneous) and inflate x_{1}, x_{2} to a sufficiently small open balls U_{t^{⌢}0}, U_{t^{⌢}1}.

The map e mapping each x ∈ 2^{ω} to the unique element of ⋂_{n} U_{x↾n} is an embedding of 2^{ω} into X which preserves c_{min}. □

In [20] 𝔥𝔪(c_{min}) was denoted simply by 𝔥𝔪. We will also sometimes write 𝔥𝔪 for 𝔥𝔪(c_{min}).

Before we proceed, let us remark that c_{parity} is not more complicated than c_{min}:

Lemma 2.10. c_{parity} ≤ c_{min}

Proof. We have to define an embedding e : ω^{ω} → 2^{ω} witnessing c_{parity} ≤ c_{min}.

For x ∈ ω^{ω}, let e(x) be the concatenation of the sequences b_{n}, n ∈ ω, which are defined as follows.

If n is even, then let b_{n} be the sequence of length 2 · x(n) + 2 which starts with 2 · x(n) zeros and then ends with two ones. If n is odd, let b_{n} be the sequence of length 2 · x(n) + 2 starting with 2 · x(n) + 1 zeros and ending with a single one.

It is clear that e is continuous and it is easy to check that e is an embedding witnessing c_{parity} ≤ c_{min}. □

2.2. Classification of homogeneity numbers. We begin now the classification of homogeneity numbers of continuous pair colorings on Polish spaces. The purpose of this Section is to find two continuous pair-colorings on the Cantor spaces whose homogeneity numbers capture all possible homogeneity numbers of continuous pair colorings. The following sequence of reductions will be performed: First, it will be shown that any homogneity number occurs on some compact space; then, that every homogneity number occurs on the Cantor space; and finally that every number occurs as a homogeneity number of a particularly simple coloring on the Cantor space — an almost node coloring. At the end of the section, we shall be able to isolate a pair-coloring c_{max} with a maximal homogeneity number in the class of continuous pair-colorings on Polish spaces and show that every homogneity number of an arbitrary reduced coloring on a Polish space is equal to 𝔥𝔪(c_{min}) or is equal to 𝔥𝔪(c_{max}).

2.2.1. Reduction to compact spaces. The following two fundamental inequalities hold for c_{min}:

(𝔥𝔪(c_{min}))^{+} ≥ 2^{ℵ_{0}}  (2)
𝔥𝔪(c_{min}) ≥ 𝔡  (3)

The first inequality was proved in [20] and the second one which, really, is the starting point of the present paper, will be proved in Section 3. Although these inequalities are central for this Section, their proofs belong to the setting of covering a square by functions.

From the first inequality it follows that there is room for at most one more homogeneity number above 𝔥𝔪(c_{min}) — since either 𝔥𝔪(c_{min}) or its immediate successor cardinal is the continuum. In [20] it was proved consistent that for all reduced pair-colorings c,

𝔥𝔪(c) = ℵ_{1} < 2^{ℵ_{0}} = ℵ_{2}.  (4)

The second inequality relates 𝔥𝔪(c_{min}) to the domination number 𝔡. This number is the least number of functions from ω to ω needed to eventually dominate every such function. It is not difficult to see that 𝔡 is the least size of a family of compact sets that covers ω^{ω}. It is well-known that every Polish space is a continuous image of ω^{ω}. Therefore every Polish space can be covered by 𝔡 compact sets. Lemma 2.11. For every Polish space X and a continuous pair-coloring c : [X]^{2} → 2 with uncountable 𝔥𝔪(c) there is a compact subspace Y ⊆ X so that 𝔥𝔪(c) = 𝔥𝔪(c ↾ Y).

Proof. Suppose, without loss of generality, that c is reduced on X. Cover X by compact subspaces Y_{α}, α ≤ 𝔡, and denote c_{α} := c ↾ Y_{α}. For each α < 𝔡 fix a collection U_{α} of c_{α}-homogeneous subsets of Y_{α} which covers Y_{α} and such that |U_{α}| = 𝔥𝔪(c_{α}). Thus U = ⋃_{α<𝔡} U_{α} is a collection of c-homogeneous sets which covers X, so 𝔥𝔪(c) ≤ |U|.

In the case that for all α < 𝔡 it holds that 𝔥𝔪(c_{α}) ≤ 𝔥𝔪(c_{min}) we have that 𝔥𝔪(c) ≤ |U| ≤ 𝔡 · 𝔥𝔪(c_{min}), so by (3), 𝔥𝔪(c) ≤ 𝔥𝔪(c_{min}). Since c is reduced, 𝔥𝔪(c) = 𝔥𝔪(c_{min}) and Y ⊆ X can be chosen as a copy of the Cantor space by Lemma 2.9

In the remaining case 𝔥𝔪(c) > 𝔥𝔪(c_{min}), therefore there necessarily exists α < 𝔡 for which 𝔥𝔪(c_{α}) > 𝔥𝔪(c_{min}), and consequently, by (2), 𝔥𝔪(c_{α}) = 𝔥𝔪(c). □

2.2.2. Reduction to colorings on 2^{ω}. For a compact space X let Comp(X) be the set of connected components of X. For x ∈ X let comp(x, X) denote the component of x in X and comp(x) = comp(x, X) when X is clear from the context. Comp(X) becomes a compact space when equipped with the quotient topology. If X is a compact metric space, then so is Comp(X). Recall that compact metric spaces are Polish.

The components of Comp(X) are singletons. Since Comp(X) is compact, it is zero-dimensional. (See [15] for this. We assume compact spaces to be Hausdorff.) Lemma 2.12. Let X be compact and c : [X]^{2} → 2 continuous. Define a coloring \overline{c} : [Comp(X)]^{2} → 2 by

\overline{c}(comp(x), comp(y)) = c(x, y)

for all x, y ∈ X with comp(x) ≠ comp(y). Then \overline{c} is a well-defined continuous pair-coloring on Comp(X).

Proof. Suppose x_{0}, x_{1}, y_{0}, y_{1} ∈ X are such that x_{1} ∈ comp(x_{0}), y_{1} ∈ comp(y_{0}), and x_{0} and y_{0} are in different components. Then c(x_{0}, y_{0}) = c(x_{1}, y_{0}) since x_{0} and x_{1} are in the same component of X \ {y_{0}} and c(·, y_{0}) : X \ {y_{0}} → 2 is continuous. By the same argument, c(x_{1}, y_{0}) = c(x_{1}, y_{1}). Thus c(x_{0}, y_{0}) = c(x_{1}, y_{1}), showing that \overline{c} is well-defined.

For every x ∈ comp(x_{0}), y ∈ comp(y_{0}) fix, by continuity of c, disjoint open U_{x,y} ∋ x, V_{x,y} ∋ y so that c is constant on U_{x,y} × V_{x,y}. Now {U_{x,y} × V_{x,y} : x ∈ comp(x_{0}), y ∈ comp(y_{0})} is an open cover of comp(x_{0})×comp(y_{0}). Since the latter is compact, there is a finite subcover {U_{x_{i},y_{i}} × V_{x_{i},y_{i}} : i < n} of this cover, which can be shrunk so that ⋃_{i<n} U_{x_{i},y_{i}} ∩ ⋃_{i<n} V_{x_{i},y_{i}} = ∅. Thus we found two disjoint open neighborhoods of comp(x), comp(y) respectively so that c is constant on their product. This proves the continuity of \overline{c}. □

Lemma 2.13. Let X be a compact metric space and suppose c : [X]^{2} → 2 is continuous. Then there exists a continuous \overline{c} : [2^{ω}]^{2} → 2 such that 𝔥𝔪(c) ≤ 𝔥𝔪(\overline{c}).

Proof. Let Y := Comp(X) and let f : X → Y be the mapping that maps every x ∈ X to comp(x, X). Let \overline{c} be as in Lemma 2.12. Observe that Y is of countable weight.

Assume that Y is uncountable. Cantor-Bendixson analysis of Y gives us a decomposition of Y into countably many points and a perfect set. Since for every isolated point y ∈ Y the set f^{−1}(y) is c-homogeneous in X by Theorem 2.2, we may replace Y by a perfect subset of Y at the cost of removing countably many c-homogeneous subset of X.

Y is now zero-dimensional, compact, without isolated points and of countable weight. Therefore Y is the Cantor space.

Claim 2.14. 𝔥𝔪(c) ≤ 𝔥𝔪(\overline{c})

By the continuity of \overline{c}, every maximal \overline{c}-homogeneous set in Y is closed. Now using Cantor-Bendixson analysis again, every uncountable maximal \overline{c}-homogeneous set can be decomposed into countably many singletons and a perfect set.

The preimages under f of singletons are c-homogeneous by Theorem 2.2. Also,

Claim 2.15. For any perfect \overline{c}-homogeneous set H ⊆ Y, f^{−1}[H] is c-homogeneous.

Proof. For the claim let H ⊆ Y be perfect and \overline{c}-homogeneous of color i ∈ 2. If x, y ∈ f^{−1}[H] are in different components of X, then clearly c(x, y) = i. Now let z be one of the components of X. Assume |z| > 1. By Theorem 2.2, c is constant on z. Let j ∈ 2 be the constant value of c on z. We have to show i = j.

Let (z_{n})_{n∈ω} be a sequence in H \ {z} that converges to z. Pick (x_{n})_{n∈ω} in X such that for all n ∈ ω, f(x_{n}) = z_{n}. By compactness, (x_{n})_{n∈ω} has a convergent subsequence. We may assume that (x_{n})_{n∈ω} itself converges.

Let x be the limit of (x_{n})_{n∈ω}. Clearly, x ∈ z. Let y ∈ z be different from x. Then c(x, y) = j. By continuity, c(x, y) = lim_{n→∞} c(x_{n}, y) = i. Thus i = j, which finishes the proof of the claim. □

Thus, the preimage under f of every \overline{c}-homogeneous subset of Y is a countable union of c-homogeneous subsets of X. This establishes 𝔥𝔪(c) ≤ 𝔥𝔪(\overline{c}) and proves Lemma 2.13. □

2.2.3. Reduction to simple colorings on 2^{ω}. We are now fishing in a much smaller tank: we can consider only colorings on the Cantor space. The next reduction will show that we can consider only “coarse” pair-colorings on the Cantor space.

Notation 2.16. For a tree T and t ∈ T let succ_{T} (t) be the set of immediate successors of t in T. Recall that if A is a subset of ω^{ω}, then T (A) denotes the set of finite initial segments of the element of A, a subtree of ω^{<ω}. If T is a subtree of ω^{<ω}, then [T] denotes the set of all elements of ω^{ω} which have all their finite initial segments in T. [T] is a closed subset of ω^{ω}. In this way closed subsets of ω^{ω} correspond to subtrees of ω^{<ω} without finite maximal branches.

A natural way to construct continuous pair-colorings on a subset A of ω^{ω} is the following: To each t ∈ T (A) assign a coloring c_{t} : [succ_{T (A)}(t)]^{2} → 2. Now for all {x, y} ∈ [A]^{2} let t be the longest common initial segment of x and y and put c(x, y) := c_{t}(x ↾ n + 1, y ↾ n + 1) where n = dom(t). Clearly, c is continuous. We call a coloring which is defined in this way an almost node-coloring.

A node-coloring on A is obtained by assigning a color to every node t ∈ T (A) and then defining the color of {x, y} ∈ [A]^{2} to be the color of the longest common initial segment of x and y. Equivalently, a node-coloring is an almost node-coloring in which c_{t} : [succ_{T (A)}(t)]^{2} → 2 is constant for all t ∈ T.

Both c_{min} and c_{parity} are node-colorings.

Not every continuous pair-coloring on ω^{ω} is an almost node-coloring. However, the following holds: Lemma 2.17. Let c : [2^{ω}]^{2} → 2 be continuous. Then there is a topological embedding e : 2^{ω} → ω^{ω} such that for every c_{parity}-homogeneous set H ⊆ e[2^{ω}], the coloring c^{e} ↾ H which is induced on H by c via e is an almost node-coloring.

Proof. Let n ∈ ω and let s, t ∈ 2^{n+1} be such that Δ(s, t) = n. Let O_{s} and O_{t} denote the basic open subsets of 2^{ω} determined by s and t, respectively.

Since O_{s} × O_{t} is compact and c is continuous, there is m > n such that for all (x, y) ∈ O_{s} × O_{t}, c(x, y) only depends on x ↾ m and y ↾ m.

It follows that there is a function f : ω → ω such that for all {x, y} ∈ [2^{ω}]^{2}, c(x, y) only depends on x ↾ f(Δ(x, y)) and y ↾ f(Δ(x, y)). We can choose f strictly increasing and such that f(0) ≥ 1. For n ∈ ω let g(n) := f^{n}(0).

Identifying 2^{<ω} and ω, we define the required embedding e : 2^{ω} → ω^{ω} by letting e(x) := (x ↾ g(0), x ↾ g(1), …). Let E := e[2^{ω}]. c induces a continuous paircoloring c^{e} on E via e. By the choice of f, for {u, v} ∈ [E]^{2}, c^{e}(u, v) only depends on u ↾ (Δ(u, v) + 2) and v ↾ (Δ(u, v) + 2). This is because if n = Δ(u, v) and x, y ∈ 2^{ω} are such that e(x) = u and e(y) = v, then Δ(x, y) < g(n) and thus c(x, y) only depends on x ↾ f(Δ(x, y)) and y ↾ f(Δ(x, y)). But since f is strictly increasing, f(Δ(x, y)) < f(g(n)) = g(n + 1).

Now let H be a c_{parity}-homogeneous subset of E. The c_{parity}-homogeneity of H implies that for all {u, v} ∈ [H]^{2}, the restrictions of u and v to Δ(u, v) + 1 uniquely determine the restrictions to Δ(u, v) + 2. Therefore, for all {u, v} ∈ [H]^{2}, c^{e}(u, v) only depends on u ↾ (Δ(u, v) + 1) and v ↾ (Δ(u, v) + 1).

It follows that c^{e} ↾ H is an almost node-coloring. □

Corollary 2.18. For every continuous pair-coloring c : [2^{ω}]^{2} → 2, there is an almost node-coloring d on some compact subset of ω^{ω} such that 𝔥𝔪(c) ≤ 𝔥𝔪(d).

Proof. By the previous Lemma, 2^{ω} can be presented as a union of ≤ 𝔥𝔪(c_{min}) sets on each of which c is reducible to an almost node-coloring. The rest of the proof is as in the proof of Lemma 2.11. □

2.2.4. The coloring c_{max}. We shall now define a maximal almost node-coloring.

Recall that the random graph on ω is, up to isomorphism, the only homogeneous and universal graph in the class of all graphs on ω. (See [16] for some information on the random graph.) Universality means: every graph (ω, E) is embeddable as an induced subgraph into the random graph (in particular, every finite graph is embeddable as an induced subgraph into a finite initial segment of the random graph). Definition 2.19. Let χ_{random} : [ω]^{2} → 2 be the (characteristic function of the) edge relation of the random graph. For s, t ∈ ω^{≤ω} write random(s, t) = i iff n := Δ(s, t) exists and i = χ_{random}(s(n + 1), t(n + 1)). Let c_{random} : [ω^{ω}]^{2} → 2 be defined by c_{random}(x, y) := random(x, y). Finally, let

c_{max} := c_{random} ↾ ∏_{n∈ω}(n + 1)  (5)

Clearly, c_{random} and c_{max} are almost node-colorings. Since ∏_{n∈ω}(n+1) is homeomorphic to 2^{ω}, we regard c_{max} as a coloring on 2^{ω}.

It is interesting to point out: Fact 2.20. Whenever c is an almost node-coloring on a compact subspace of ω^{ω}, then: c_{random} ≰ c.

Proof. Let (x_{n})_{n∈ω} be an infinite path in c_{random}, i.e.,

∀n < m : c_{random}(x_{n}, x_{m}) = 1 ⇔ m = n + 1.

Since every countable graph embeds into (ω^{ω}, c_{random}), such a sequence can be easily found.

On the other hand, if Y ⊆ ω^{ω} is compact and c : [Y]^{2} → 2 is an almost node-coloring, there is no infinite path in (Y, c). Suppose to the contrary that (y_{n})_{n<ω} is a path in (Y, c). Observe that Δ(y_{n+1}, y_{n+2}) > Δ(y_{n}, y_{n+1}) implies that c(y_{n}, y_{n+2}) = 1; and that Δ(y_{n+1}, y_{n+2}) < Δ(y_{n}, y_{n+1}) implies c(y_{n+1}, y_{n+2}) = 0. Thus, Δ(y_{n}, y_{n+1}) is constant for all n — contrary to the compactness of Y.

The fact now follows. □

Lemma 2.21. a) If c is an almost node-coloring on a subset of ω^{ω}, then c ≤ c_{random} via a level preserving embedding (isometry) of ω^{ω} into ω^{ω}.

b) If c is an almost node-coloring on a compact subset of ω^{ω}, then c ≤ c_{max}.

Proof. Let us prove b) first. Suppose c is an almost node-coloring on a compact subset A of ω^{ω}. Then T (A) is a finitely branching subtree of ω^{<ω}. For each t ∈ T (A) fix a coloring c_{t} : [succ_{T (A)}(t)]^{2} → 2 such that the c_{t} witnesses the fact that c is an almost node-coloring. For s, t ∈ T let \overline{c}(s, t) := c(x, y) if s and t are incomparable and x, y ∈ [T] are such that s ⊆ x and t ⊆ y. If s and t are comparable, then \overline{c}(s, t) is undefined.

Let T_{k} = {t ∈ T (A) : |t| = k}. We construct a monotone (i.e., ⊆-preserving) map e : ⋃_{k∈ω} T_{k} → T (∏_{n∈ω}(n + 1)) which induces the required embedding of A into ∏_{n∈ω}(n + 1).

Argue by induction on k. Suppose that e(s) ∈ ∏_{n≤n(k)}(n + 1) is defined for all s ∈ T_{k}, and for all s, t ∈ T_{k} we already have random(e(s), e(t)) = \overline{c}(s, t). Find n(k + 1) > n(k) such that for all s ∈ T_{k} there is t ∈ ∏_{n<n(k+1)}(n + 1) with e(s) ⊆ t and c_{s} ≤ random ↾ succ_{T (∏_{n∈ω}(n+1))}(t). Now it is obvious how to define e on T_{k+1} with images in ∏_{n≤n(k+1)}(n + 1).

a) is proved similarly, using the fact that every countable graph occurs as an induced subgraph of (succ_{ω^{<ω}}(s), random) for every s ∈ ω^{<ω}. □

Corollary 2.22. For every Polish X and every continuous c : [X]^{2} → 2:

𝔥𝔪(c) ≤ 𝔥𝔪(c_{max}).

Proof. Let c be an arbitrary reduced continuous pair-coloring on a Polish X. By Lemma 2.11 there exists a compact Y ⊆ X so that 𝔥𝔪(c) = 𝔥𝔪(c ↾ Y). By Lemma 2.13 there is a coloring \overline{c} on 2^{ω} so that 𝔥𝔪(c) ≤ 𝔥𝔪(\overline{c}) and by Corollary 2.18 there is an almost node-coloring d on 2^{ω} so that 𝔥𝔪(\overline{c}) ≤ 𝔥𝔪(d). Finally, d ≤ c_{max} by Lemma 2.21 above. □

Finally, Theorem 2.23. For every reduced continuous pair-coloring c:

𝔥𝔪(c) = 𝔥𝔪(c_{min}) or 𝔥𝔪(c) = 𝔥𝔪(c_{max})

Proof. By now we have that 𝔥𝔪(c_{min}) ≤ 𝔥𝔪(c) ≤ 𝔥𝔪(_{max}) for all reduced c. But 𝔥𝔪(c_{max}) ≤ (𝔥𝔪(c_{min}))^{+} by (2); so 𝔥𝔪(c) > 𝔥𝔪(c_{min}) implies 𝔥𝔪(c) = 𝔥𝔪(c_{max}).

□

Note however that it is conceivable that there is a simply defined reduced pair coloring c on a Polish space such that neither 𝔥𝔪(c) = 𝔥𝔪(c_{max}) nor 𝔥𝔪(c) = 𝔥𝔪(c_{min}) is provable in ZFC (see Problem 6.1).

We remark that in Theorem 2.23 above, c_{min} can be replaced by c_{parity} and c_{max} can be replaced by c_{random}, since

c_{parity} ≤ c_{min} ≤ c_{max} ≤ c_{random}.

2.2.5. Why c_{max} is more complicated than c_{min}: Random versus perfect graphs. In the second part of the paper we shall prove the consistency of 𝔥𝔪(c_{min}) < 𝔥𝔪(c_{max}). The consistency proof relies on the different finite patterns that appear in each of those two colorings.

Clearly, every finite graph occurs as an induced subgraph of (2^{ω}, c_{max}).

A finite graph is called perfect if in each of its induced subgraphs the chromatic number is equal to the clique number. A perfect graph with n vertices contains either a clique or an independent set of size ⌊\sqrt{n}⌋. This stands in strong contrast to a randomly chosen graph: in a random graph on n vertices there is almost certainly no clique and no independent set of size 2 log n (see [5]). Fact 2.24 (N. Alon). Every finite (induced) subgraph H of (ω^{ω}, c_{parity}) satisfies that the chromatic number of H is equal to the maximal size of a clique in H.

Proof. Two proofs of this fact are in [4]. The proof we include here was suggested to us by Stevo Todorčević. Define a partial order on ω^{ω} by η_{1} ≤ η_{2} iff η_{1} = η_{2} or Δ(η_{1}, η_{2}) is odd and η_{1} precedes η_{2} in the lexicographic ordering on ω^{ω}. A finite induced subgraph of ω^{ω} is a clique iff its elements form a chain in the poset just defined and is an independent set iff its elements form an anti-chain in the same poset. Now recall that a finite partially ordered set with no chain of length k + 1 is a union of k antichains. □

Thus only perfect graphs occur as finite induced subgraphs of c_{min}.

In particular:

c_{max} ≰ c_{min}.  (6)

3. Covering a square by functions

The problem of covering a Euclidean space by smaller geometric objects is well investigated. Klee [25] proved that no separable Banach space can be covered by fewer than 2^{ℵ_{0}} hyperplanes. Steprāns [31] proved the consistency of covering ℝ^{n+1} by fewer than continuum smooth manifolds of dimension n.

We recall that a point (x, y) ∈ X^{2} is covered by a function f : X → X if f(x) = y or f(y) = x. By f^{−1} we mean the set {(y, x) : f(x) = y}, the inverse of f. Thus (x, y) is covered by f iff (x, y) ∈ f ∪ f^{−1}. For a metric space X denote by Cov(Cont(X)) the minimal number of continuous functions from X to X needed to cover X^{2} and by Cov(Lip(X)) denote the analogous number for Lipschitz functions.

Hart and van der Steeg showed the consistency of covering (2^{ω})^{2} by fewer than continuum continuous functions [23], a result that actually follows from Steprāns’ result mentioned above using some easy arguments from the present article. Ciesielski and Pawlikowski observed that Steprans’ result also implies that ℝ^{2} is consistently covered by fewer than continuum continuously differentiable functions [13]. This is optimal in the following sense:

It was pointed out by Márton Elekes that ℝ^{2} is not the union of less than continuum twice differentiable functions and inverses of differentiable functions. This is because there exists a differentiable function f : ℝ → ℝ and an infinite perfect set P ⊆ ℝ such that the derivative of f is constantly 0 on P and no function which is twice differentiable intersects f ↾ P in infinitely many points [3]. Since the derivative of f is 0 on P, no inverse of a differentiable function intersects f ↾ P in more than finitely many points. It follows that already the graph of f is not included in the union of less than continuum twice differentiable functions and inverses of differentiable functions.

In [20] it was shown that (2^{ω})^{2} can consistently be covered by fewer than continuum Lipschitz functions, which also follows from the result by Ciesielski and Pawlikowski on covering ℝ^{2} by continuously differentiable functions. Hart asked whether Cov(Lip(2^{ω})) can be different from Cov(Cont(2^{ω})). Recently, Abraham and Geschke [1] proved that it is consistent to cover ℝ^{n+1} by κ n-ary continuous functions with 2^{ℵ_{0}} = κ^{+n}.

Let us state the following folklore result that was brought to the authors’ attention by Ireneusz Recław (and which should be well-known):

Theorem 3.1. Let κ be an infinite cardinal. Then the least number of functions from κ^{+} to κ^{+} needed to cover κ^{+} × κ^{+} is κ.

Proof. For every α < κ^{+} fix a surjection f_{α} : κ → (α + 1). Now define, for β < κ, g_{β}(α) := f_{α}(β). The functions {g_{β} : β < κ} cover κ^{+} × κ^{+}.

To show that κ^{+} × κ^{+} is not covered by less than κ functions, let F be a family of functions from κ^{+} to κ^{+} of size < κ. We shall find a pair (x, y) ∈ κ^{+} × κ^{+} that is not covered by F.

Let X ⊆ κ^{+} be a set of size κ which is closed under all functions in F. Choose y ∈ κ^{+} \ X. Now for all f ∈ F and all x ∈ X, f(x) ≠ y. Since |F| < |X|, there is x ∈ X such that for all f ∈ F, x ≠ f(y). Now (x, y) is not covered by any function in F. □

This theorem implies that if the continuum is a successor cardinal, then fewer than continuum functions suffice to cover the square of the continuum. In [1] a generalization of Theorem 3.1 to higher dimension is proved.

In the rest of this section the connection between c_{min}-homogeneous sets and covering (2^{ω})^{2} by Lipschitz functions will be explored, and used to prove the inequalities (2) and (3) which were used in the previous Section. Inequality (2) was already proved in [20]. Inequality (3) follows from Theorem 3.9 below.

After proving the crucial Theorem 3.9 we investigate covering by continuous functions.

3.1. 𝔥𝔪 and covering a square by Lipschitz functions.

Definition 3.2. For a, b > 0 let Lip_{a,b} denote the σ-ideal on (2^{ω})^{2} generated by the Lipschitz functions of constant a and the inverses of Lipschitz functions of constant b. The covering number of this ideal, Cov(Lip_{a,b}), is the least number of sets in the ideal needed to cover (2^{ω})^{2}.

Clearly, as the graph of every continuous function is a nowhere-dense subset of (2^{ω})^{2}, Cov(Lip_{a,b}) > ℵ_{0} for every choice of positive a, b. By Theorem 3.1 we know that (Cov(Lip_{a,b}))^{+} ≥ 2^{ℵ_{0}}. Lemma 3.3. 𝔥𝔪 = Cov(Lip_{1, \frac{1}{2}} )

Proof. For x, y ∈ ω^{ω} let x ⊗ y := (x(0), y(0), x(1), y(1), …). It is easily seen that ⊗ : (ω^{ω})^{2} → ω^{ω} and ⊗ : (2^{ω})^{2} → 2^{ω} are uniformly continuous homeomorphisms.

Suppose H_{0} ⊆ 2^{ω} is a maximal c_{min}-homogeneous of color 0. Then T := T (H_{0}) is a tree with the property that t ∈ T has two immediate successors in T if and only if |t| is even and has one immediate successor in T otherwise. Let x ∈ 2^{ω} and define y(n) inductively as follows: Suppose y(i) is defined for all m < n, and we have

t = (x(0), y(0), x(1), y(1), …, x(n − 1), y(n − 1)) ∈ T.

Let y(n) ∈ {0, 1} be the unique i such that t^{⌢}x(n)^{⌢}i ∈ T. Let f_{H_{0}}(x) denote y, which we have just defined from x and H_{0}. We then have (x ⊗ f_{H_{0}}(x)) ∈ H_{0}.

Since the first n digits of y are determined by the first n digits of x, f_{H_{0}} : 2^{ω} → 2^{ω} is a Lipschitz function with constant 1 (with respect to dist).

Similarly, if H_{1} is maximal c_{min}-homogeneous of color 1, then for every x ∈ 2^{ω} there is a unique f_{H_{1}}(x) ∈ 2^{ω} for which f_{H_{1}}(x) ⊗ x ∈ H_{1}. This time, the function f_{H_{1}} is of Lipschitz of constant \frac{1}{2}.

Conversely, from every 1-Lipschitz function f : 2^{ω} → 2^{ω} a maximal c_{min}- homogeneous set H_{f} of color 0 is defined so that for all x, y = f(x) is the unique such that x⊗y ∈ H_{f} and from every 1/2-Lipschitz function f : 2^{ω} → 2^{ω} a maximal c_{min}-homogeneous set _{f}H of color 1 is defined such that y = f(x) is the unique such that y ⊗ x ∈ _{f}H.

Suppose H_{0} is a family of maximal c_{min}-homogeneous subsets of 2^{ω} of color 0 and H_{1} is a family of maximal c_{min}-homogeneous subsets of color 1. For (x, y) ∈ (2^{ω})^{2}, if x ⊗ y ∈ H for some H ∈ H_{0} then y = f_{H}(x), and if x ⊗ y ∈ H for H ∈ H_{1} then x = f_{H}(y). Thus ⋃ H_{0} ∪ ⋃ H_{1} = 2^{ω} implies that for all (x, y) ∈ (2^{ω})^{2} there is some H ∈ H for which f_{H}(x) = y or f_{H}(y) = x.

Conversely, suppose that F_{0} is a family of 1-Lipschitz functions from 2^{ω} to itself and that F_{1} is a family of \frac{1}{2}-Lipschitz functions from 2^{ω} to itself. Let z ∈ 2^{ω} and write z = x ⊗ y. If there is f ∈ F_{0} such that f(x) = y then z ∈ H_{f} and if there is f ∈ F_{1} such that f(y) = x then z ∈ _{f}H. □

3.1.1. Varying the Lipschitz constants. Let Lip be the σ-ideal on (2^{ω})^{2} generated by ⋃_{a>0} Lip_{a,a}, i.e., the σ-ideal generated by all Lipschitz functions and their inverses. Theorem 3.4. 𝔥𝔪 = Cov(Lip)

Proof. Clearly, Cov(Lip) ≤ Cov(Lip_{1, \frac{1}{2}} ). Thus, it follows from Lemma 3.3 that Cov(Lip) ≤ 𝔥𝔪.

Now we prove the converse inequality 𝔥𝔪 ≤ Cov(Lip). We define a coloring c : [2^{ω} × 2^{ω}]^{2} → P(2) as follows.

Let 0 ∈ c((x_{0}, y_{0}), (x_{1}, y_{1})) iff there is a Lipschitz function of constant 1 containing both (x_{0}, y_{0}) and (x_{1}, y_{1}), i.e., if the slope determined by (x_{0}, y_{0}) and (x_{1}, y_{1}) is ≤ 1 or equivalently, if x_{0} and x_{1} do not split after y_{0} and y_{1}.

Let 1 ∈ c((x_{0}, y_{0}), (x_{1}, y_{1})) iff there is a Lipschitz function of constant 1 containing both (y_{0}, x_{0}) and (y_{1}, x_{1}), i.e., if y_{0} and y_{1} do not split after x_{0} and x_{1}.

It is clear that c is continuous and the color ∅ does not occur. We construct a (nonempty) perfect set X ⊆ (2^{ω})^{2} with the following properties:

(i) c ↾ X only takes the values {0} and {1}.

(ii) c ↾ X is reduced.

(iii) For every Lipschitz function f : 2^{ω} → 2^{ω}, f ∩X and f^{−1} ∩X are the unions

of finitely many c-homogeneous sets. If we can construct X, we are done. This is because by (iii), every family F of

Lipschitz functions that covers (2^{ω})^{2} induces a family H of size at most |F| that covers X and consists of c-homogeneous sets. By (i) and (ii), we have 𝔥𝔪 ≤ |H| and thus 𝔥𝔪 ≤ |F|.

The required X will be chosen to be (the graph of) a homeomorphism between two perfect subsets of 2^{ω}. For its construction, partition ω into countably many intervals I_{i}, i ∈ ω, such that the length of every I_{i} is at least i and the elements of I_{i} are below the elements of I_{j} for i < j. For every i ∈ ω let n_{i} denote the first element of I_{i}.

Let T_{0} be a perfect subtree of 2^{<ω} that fully splits at all the levels of height n_{i} for i ≡ 0, 3 mod 4 and does not split at any other level. Let T_{1} be a perfect subtree of 2^{<ω} that fully splits at every level of height n_{i} for i ≡ 1, 2 mod 4 and does not split anywhere else.

Let X be the (graph of the) natural (order preserving) homeomorphism between [T_{0}] and [T_{1}]. Clearly X is closed and satisfies (i) and (ii). It remains to show (iii).

Let f : 2^{ω} → 2^{ω} be a Lipschitz function. Choose i ∈ ω so that the Lipschitz constant of f is below 2^{i} and i ≡ 0 mod 4. T_{0} is the union of finitely many perfect subtrees T_{0}^{1}, …, T_{0}^{m} that have no splittings below level n_{i}. Since i ≡ 0 mod 4, the corresponding subtrees T_{1}^{1}, …, T_{1}^{m} of T_{1} do not split below level n_{i} either. For k ∈ {1, …, m} let X_{k} := X ∩ ([T_{0}^{k}] × 2^{ω}). Now for every k ∈ {1, …, m} and all (x_{0}, y_{0}), (x_{1}, y_{1}) ∈ X_{k} the slope determined by the pair {(x_{0}, y_{0}), (x_{1}, y_{1})} is either ≤ 2^{−i} or ≥ 2^{i} since the length of I_{i} is at least i and by the definition of X. Now by the choice of i, for all k ∈ {1, …, m}, f ∩ X_{k} is c-homogeneous of color {0}.

Similarly, the intersection of every inverse of a Lipschitz function with X is the union of finitely many c-homogeneous sets of color {1}. This shows (iii) and therefore finishes the proof of the theorem. □

Lemma 3.5. Let a, b > 0. Then Cov(Lip_{a,b}) = Cov(Lip_{2·a, \frac{b}{2}} ).

Proof. For i ∈ 2 let X_{i} be the set of all sequences in 2^{ω} starting with i. Let h_{i} : 2^{ω} → X_{i} be the homeomorphism mapping x to (i, x(0), x(1), …).

Let f : 2^{ω} → 2^{ω} be a Lipschitz function of constant a. For i ∈ 2 let f^{i} : 2^{ω} → 2^{ω} be a function which is equal to f ∘ h_{i}^{−1} on X_{i} and constant on X_{1−i} such that f^{i} is Lipschitz of constant 2 · a. (For example, we can choose the constant value of f^{i} on X_{1−i} to be f((\overline{1 − i})) where (\overline{1 − i}) denotes the constant sequence with value 1−i.)

If f : 2^{ω} → 2^{ω} is a Lipschitz function of constant b, then for i ∈ 2 let f_{i} := h_{i} ∘ f. f_{i} is a Lipschitz function of constant \frac{b}{2}.

Now let F be a family of Lipschitz functions of constant a and G a family of Lipschitz functions of constant b. If (2^{ω})^{2} = ⋃{f ∪ g^{−1} : f ∈ F ∧ g ∈ G}, then (2^{ω})^{2} = ⋃{f^{i} ∪ g_{i}^{−1} : i ∈ 2 ∧ f ∈ F ∧ g ∈ G}.

It follows that Cov(Lip_{2·a, \frac{b}{2}} ) ≤ Cov(Lip_{a,b}). Now the lemma follows from the fact that Cov(Lip_{a,b}) is symmetric in a and b. □

Lemma 3.6. Let a, b > 0. If there is c ∈ ℤ such that 2^{c−1} ≤ a and 2^{−c} ≤ b, then Cov(Lip_{a,b}) = 𝔥𝔪. Otherwise Cov(Lip_{a,b}) = 2^{ℵ_{0}}.

Proof. Let a, b > 0 and assume that there is no c ∈ ℤ such that 2^{c−1} ≤ a and 2^{−c} ≤ b. Let c ∈ ℤ be maximal with 2^{c−1} ≤ a. Then 2^{−c} > b and therefore b · 2^{c} < 1. 2^{c−1} ≤ a is equivalent to a · 2^{−c} ≥ \frac{1}{2}, and since c is maximal, we have a·2^{−c} < 1. By Lemma 3.5, Cov(Lip_{a,b}) = Cov(Lip_{2^{−c}·a,2^{c}·b}). But even the diagonal in (2^{ω})^{2} cannot be covered by less than 2^{ℵ_{0}} Lipschitz functions of constant < 1.

Now suppose there is c ∈ ℤ such that 2^{c−1} ≤ a and 2^{c} ≤ b. By Lemma 3.5 we may assume a ≥ 1 and b ≥ \frac{1}{2}, hence Cov(Lip_{a,b}) ≤ Cov(Lip_{1, \frac{1}{2}} ) = 𝔥𝔪. The inequality Cov(Lip_{a,b}) ≥ 𝔥𝔪 follows from Theorem 3.4. □

3.1.2. Covering (ω^{ω})^{2} and ℝ^{2} by Lipschitz functions. We generalize our notation Lip_{a,b} to metric spaces X. For a metric space X let Lip_{a,b}(X) be the σ-ideal on X × X generated by the Lipschitz functions of constant a and the reflections of Lipschitz functions of constant b. Lip(X) denotes the σ-ideal generated by the union of all the ideals Lip_{a,b}(X).

Recall that 𝔥𝔪(c_{parity}) = 𝔥𝔪. It is easily checked that the main arguments for the correspondence between Lipschitz functions on 2^{ω} and c_{min}-homogeneous sets also go through for ω^{ω} and c_{parity}. This shows

Corollary 3.7. For X = 2^{ω} and X = ω^{ω} we have

Cov(Lip(X)) = Cov(Lip_{1, \frac{1}{2}} (X)) = 𝔥𝔪.

At the very moment we do not know the exact relation between the cardinal invariants mentioned above and Cov(Lip(ℝ)). However, we can say something:

Remark 3.8. 𝔥𝔪 ≤ Cov(Lip(ℝ))

Proof. The argument is similar to the argument in the proof of Theorem 3.4.

It is not difficult to construct a topological embedding e : 2^{ω} → ℝ^{2} such that for any two distinct points x, y ∈ 2^{ω} the slope determined by e(x) and e(y) is positive and ≥ Δ(x, y) if Δ(x, y) is even and ≤ \frac{1}{Δ(x,y)} if Δ(x, y) is odd.

If f : ℝ → ℝ is Lipschitz, then e^{−1}[f] is a finite union of c_{min}-homogeneous sets of color 1 and e^{−1}[f^{−1}] is a finite union of c_{min}-homogeneous sets of color 0. A covering family of Lipschitz real functions induces a covering family of no greater size of c_{min}-homogeneous subsets of 2^{ω}. This implies 𝔥𝔪 ≤ Cov(Lip(ℝ)). □

3.2. Covering squares by continuous functions. After having established the equality 𝔥𝔪 = Cov(Lip_{1, \frac{1}{2}} ) = Cov(Lip) and the fact that the Lipschitz constants can be varied to some extent without changing Cov(Lip_{a,b}), it is natural to ask what happens if we replace the Lipschitz functions by continuous functions.

For a topological space X let Cont(X) denote the σ-ideal on X × X generated by the continuous functions from X to X and their inverses. Cont is Cont(2^{ω}). Obviously, Lip_{a,b} ⊆ Cont for all a, b > 0. Theorem 3.1 implies that Cov(Cont)^{+} ≥ 2^{ℵ_{0}}. The same is of course true for 𝔥𝔪. The question is whether Cov(Cont) can be smaller than 𝔥𝔪. This will be answered in Section 5.

Very often cardinal invariants of σ-ideals on Polish spaces do not depend on the particular space the ideal is defined on. This is not true for Cov(Cont(X)). While Cov(Cont(2^{ω})) is consistently smaller than 2^{ℵ_{0}}, the fact that every continuous function from a connected space to a zero-dimensional space is constant implies easily that if X is the disjoint union of ℝ and 2^{ω}, then Cov(Cont(X)) = 2^{ℵ_{0}}.

3.2.1. The crucial inequality. We show that Cov(Cont(X)) is the same for X = 2^{ω}, X = ω^{ω}, and X = ℝ. The proof of this fact depends on the following perhaps surprising Theorem.

Theorem 3.9. Cov(Cont(2^{ω})) ≥ 𝔡

Let e : ω^{ω} → 2^{ω} be the natural embedding, i.e., the one induced by the mapping that maps n ∈ ω to the sequence of zeros of length n followed by a single one. Clearly, 2^{ω} \ e[ω^{ω}] is countable. Now Theorem 3.9 immediately follows from the next lemma, letting K := 2^{ω} and X := e[ω^{ω}].

Lemma 3.10. Let K be an infinite compact space and let X ⊆ K be such that |K \ X| < |X|. If F is a family of continuous functions from K to K covering K^{2}, then X can be covered by |F| compact subsets of X.

Proof. Note that |X| = |K|. We may assume |F| < |K|. By |K \ X| < |X|, there is x ∈ K \ ⋃_{f∈F} f[K \ X].

Let f ∈ F. By the choice of x, f^{−1}(x) ⊆ X for every f ∈ F. By the continuity of f, f^{−1}(x) is closed in K and thus compact.

Since F covers K^{2}, for all y ∈ X there is f ∈ F such that f(x) = y or f(y) = x. In other words,

{f^{−1}(x) : f ∈ F} ∪ {{f(x)} : f ∈ F ∧ f(x) ∈ X}

is a family of compact subsets of X sets that covers X. Clearly, this family is of size ≤ |F|. □

Alternative proof of Theorem 3.9. Let F be an infinite family of continuous functions from 2^{ω} to 2^{ω}. Let M be an elementary submodel of a sufficiently large initial segment of the universe with Skolem functions such that F ⊆ M and |M| = |F|.

Suppose |F| < 𝔡. Then there is a function x ∈ 2^{ω} \ M. Let M[x] denote the Skolem hull of M ∪ {x}. Since |M[x]| = |F| < 𝔡, there is y : ω → ω such that y is not eventually dominated by any function in ω^{ω} ∩ M[x].

Clearly, the embedding e : ω^{ω} → 2^{ω} is an element of M. No f ∈ F maps x to e(y), since such an f would be an element of M[x] and therefore y = e^{−1}(f(x)) would be an element of M[x].

We show that no f ∈ F maps e(y) to x.

Let f ∈ F. Since f is continuous, f^{−1}(x) is a compact subset of 2^{ω}. Since 2^{ω} \ e[ω^{ω}] is countable, 2^{ω} \ e[ω^{ω}] ⊆ M. Since x ∉ M, f^{−1}(x) is disjoint from 2^{ω} \ e[ω^{ω}]. In other words, f^{−1}(x) is a compact subset of e[ω^{ω}]. It follows that the set (f ∘e)^{−1}(x) is bounded, i.e., there is a function in ω^{ω} that eventually dominates every element of (f ∘e)^{−1}(x). By elementarity, (f ∘e)^{−1}(x) is bounded by a function in ω^{ω} ∩ M[x].

Since y is not eventually dominated by a function in ω^{ω} ∩M[x], y ∉ (f ∘e)^{−1}(x). That is, f(e(y)) ≠ x.

This shows that no element of F covers the pair (x, e(y)) ∈ (2^{ω})^{2}. □

The main reason for including the alternative proof of Theorem 3.9 is the curious use of two new reals over M. This detail is somewhat hidden in our proof of Lemma 3.10, but still present there.

In many cases, the standard proof of an inequality of the form Cov(I) ≤ Cov(J), for reasonably nice ideals I and J on the reals, shows that if one adds by forcing over a ground model M a new real r that avoids all elements of I which are coded (by a Borel code) in M, then the generic extension M[r] contains also a new real which avoids all elements of J which are coded in M.

This is not the case with the inequality 𝔡 ≤ Cov(Cont(2^{ω})). It can be shown that after adding a single Miller real m to M (which is unbounded over M, i.e., escapes every bounded subset of ω^{ω} which is coded in M), in the generic extension M[m], 2^{ω} is still covered by the c_{min}-homogeneous sets coded in M. In particular, (2^{ω})^{2} is still covered by the continuous functions coded in M.

The alternative proof of Theorem 3.9 shows that this is not the case after adding two Miller reals, or even after adding first any new real r and then a Miller real m over M[r]. In other words, the “standard” forcing proof of this inequality involves adding two reals, rather than one.

From Theorem 3.9 we get Theorem 3.11. Cov(Cont(ω^{ω})) = Cov(Cont(ℝ)) = Cov(Cont(2^{ω}))

The proof of this theorem uses the following easy observation. Lemma 3.12. Let C be a closed subset of ω^{ω} and let f : C → ω^{ω} be continuous. Then f can be continuously extended to all of ω^{ω}.

Proof. It is easily checked that every closed subspace C of ω^{ω} is a retract of ω^{ω} (by inductively dropping every element of ω^{ω} into C). That is, there is a continuous map q : ω^{ω} → C such that q ↾ C = id_{C}. If f is as above, then f ∘ q is a continuous extension of f to all of ω^{ω}. □

Proof of Theorem 3.11. We first show Cov(Cont(2^{ω})) ≤ Cov(Cont(ω^{ω})). Let f : ω^{ω} → ω^{ω} be continuous. Then f^{−1}[2^{ω}] is closed and thus A := f^{−1}[2^{ω}] ∩ 2^{ω} is a closed subset of 2^{ω}. We can now extend f ↾ A to a continuous function \overline{f} : 2^{ω} → 2^{ω} by the same argument as in the proof of Lemma 3.12.

This shows that a family F ⊆ Cont(ω^{ω})) covering (ω^{ω})^{2} gives rise to a covering family of no greater size in Cont(2^{ω}) and thus, Cov(Cont(2^{ω})) ≤ Cov(Cont(ω^{ω})).

The same argument goes through for ℝ instead of ω^{ω}, using the Tietze-Urysohn theorem.

Now observe that ω^{ω} can be covered by 𝔡 copies of 2^{ω} since 𝔡 is the covering number of the ideal of bounded subsets of ω^{ω}. Let C be a collection of size 𝔡 of copies of 2^{ω} covering ω^{ω}.

To each pair (C, D) ∈ C × C assign a family F_{C,D} of size Cov(Cont(2^{ω})) of continuous functions on ω^{ω} such that C × D ⊆ ⋃{f ∪ f^{−1} : f ∈ F_{C,D}}. This is possible by Lemma 3.12. Let F := ⋃{F_{C,D} : C, D ∈ C}. Now (ω^{ω})^{2} = ⋃{f ∪ f^{−1} : f ∈ F} and the size of F is max(Cov(Cont(2^{ω})), 𝔡) = Cov(Cont(2^{ω})). The last equality is Theorem 3.9.

Again, same argument works for Cov(Cont(ℝ)) as well since ℝ is just ω^{ω} (the irrationals) together with countably many additional points (the rationals) and therefore also can be covered by 𝔡 copies of 2^{ω}. We again use the Tietze-Urysohn theorem to extend continuous mappings defined on closed subspaces of ℝ. □

Part II: Independence results

In the second part of the paper we show that any two rows in Diagram 1 can be separated, where, as mentioned before, we have to exclude Cov(Lip(ℝ)) from row (3). We shall prove that every assignment of ℵ_{1}-s and ℵ_{2}-s to the diagram which is consistent with the arrows is realized in a model of set theory.

We provide two new forcing notions. One for separating 𝔥𝔪(c_{min}) from 𝔥𝔪(c_{max}) and the other for separating Cov(Cont(2^{ω})) from Cov(Lip(2^{ω})). We force over models of CH with countable support iterations of Axiom A forcing notions (see [9]) of size ℵ_{1} which add new reals. Thus, no cardinals are collapsed and in the resulting models the continuum is ℵ_{2}.

Theorem 3.1 implies that if the continuum is a limit cardinal, all three numbers above are equal to the continuum. In fact, it is very easy to make Cov(Cont(2^{ω})) equal to the continuum.

Let M be a model of set theory and assume that F ∈ M is a family of continuous functions on 2^{ω}. If x, y ∈ 2^{ω} are generic over M and independent in the sense that x ∉ M[y] and y ∉ M[x], then no f ∈ F can cover (x, y). It follows that after forcing with a large product of some sort in order to increase the continuum one ends up with a model of set theory where Cov(Cont(2^{ω})) is the continuum. In particular, after forcing with the measure algebra over 2^{ℵ_{2}} over a model of CH, one obtains a model (the Solovay model) in which 𝔡 = ℵ_{1} (since the ground model elements of ω^{ω} dominate the new elements) and Cov(Cont(2^{ω})) = ℵ_{2}.

In [20] it was shown that in the Sacks model all homogeneity numbers of reduced continuous pair-colorings on Polish spaces are equal to ℵ_{1} < 2^{ℵ_{0}}. It follows that 𝔥𝔪(c_{max}), 𝔥𝔪(c_{min}), and Cov(Cont(ℝ)) are small in the Sacks model.

There is a natural forcing ℙ_{c_{min}} for separating 𝔥𝔪(c_{min}) from the numbers below it: forcing with Borel subsets of 2^{ω} which are positive with respect to the σ-ideal J_{min} generated over 2^{ω} by all c_{min}-homogeneous sets. We show that the countable support iteration of this forcing of length ω_{2} produces a model of 𝔥𝔪(c_{min}) = ℵ_{2} and Cov(Cont(2^{ω})) = ℵ_{1}. In this model it holds that covering ℝ^{2} by Lipschitz functions is strictly more difficult than covering ℝ^{2} by continuous functions.

By a new (and yet unpublished) theorem of Zapletal, the existence of large cardinals implies that ℙ_{c_{min}} is optimal for enlarging 𝔥𝔪(c_{min}) in the sense that it does not enlarge numbers which are consistently smaller than 𝔥𝔪(c_{min}). Assuming large cardinals, Shelah and Zapletal proved recently that for every reasonably defined σideal I on the reals whose covering number is provably ≥ 𝔥𝔪(c_{min}), the uniformity of I (i.e., the smallest size of a set not in I) is at most ℵ_{3}. (The uniformity of J_{min} is at most ℵ_{2}.)

The analogous natural forcing for increasing 𝔥𝔪(c_{max}) is, however, not only not optimal, but actually increases the smaller 𝔥𝔪(c_{min}). So another forcing has to be used for separating 𝔥𝔪(c_{min}) from 𝔥𝔪(c_{max}).

We design a new tree-forcing notion ℙ_{c_{max}} for increasing 𝔥𝔪(c_{max}) while leaving 𝔥𝔪(c_{min}) small. The tree-combinatorics required for this forcing stems from a new result of Noga Alon about a Ramsey connection between perfect graphs and random graphs [4] (which Alon proved for this purpose). The countable support iteration of length ω_{2} of P_{c_{max}} produces a model of set theory in which 𝔥𝔪(c_{min}) = ℵ_{1} and 𝔥𝔪(c_{max}) = ℵ_{2}.

4. Consistency of 𝔥𝔪(c_{min}) < 𝔥𝔪(c_{max})

4.1. The c_{max}-forcing. We are looking for a notion of forcing which adds a real that avoids all the c_{max}-homogeneous sets in the ground model but does not increase 𝔥𝔪 when iterated. Definition 4.1. For a pair-coloring c of a finite set with two colors let norm(c) denote the greatest n ∈ ω for which χ_{random} ↾ n ≤ c.

For a subtree p ⊆ T (∏_{n∈ω}(n + 1)) and t ∈ p let c_{t,p} := χ_{random} ↾ {i ∈ ω : t^{⌢}i ∈ succ_{p}(t)}. (See 2.16 for notation.)

Let

ℙ_{c_{max}} := {p ⊆ T ( ∏_{n∈ω}(n + 1)) : p is a tree and
∀t ∈ p∀n ∈ ω∃s ∈ p(s ⊇ t ∧ norm(c_{s,p}) ≥ n)}

The order on ℙ_{c_{max}} is set-inclusion.

In the following we write just ℙ for ℙ_{c_{max}}. For a condition p ∈ ℙ and t ∈ p, let p_{t} = {s ∈ p : s ⊆ t ∨ t ⊆ s}, and call p_{t} the condition p below t. It is clear that p_{t} ∈ ℙ for p ∈ ℙ and t ∈ p. If G ⊆ ℙ is a generic filter over a ground model M, the generic real added by ℙ is the unique element of ⋂{[p] : p ∈ G}. Claim 4.2. The generic real added by ℙ avoids all c_{max}-homogeneous sets in the ground model.

Proof. Suppose that A ⊆ 2^{ω} is c_{max}-homogeneous, say with color 0, and A ∈ M. Let p ∈ ℙ be arbitrary. Choose s ∈ p with t, t′ ∈ succ_{p}(s) satisfying random(t, t′) = 1. Since at least one of [p_{t}], [p_{t′}] has empty intersection with A, assume without loss of generality that [p_{t}] ∩ A = ∅. Now p_{t} ≤ p is a condition in ℙ which forces that the generic real is not in A. Thus, the set of conditions forcing that the generic real is not in A is dense and belongs to M, hence the generic real is not in A. □

Lemma 4.3. Let G be ℙ-generic over the ground model M. Then for each x ∈ (2^{ω})^{M[G]} there is a tree T ∈ M such that [T] is parity-homogeneous and x ∈ [T].

For the proof of this lemma we use the following result of Noga Alon [4] that was proved especially for this purpose. Lemma 4.4. Let n ∈ ω and c : [n]^{2} → 2. Then there is N ∈ ω and C : [N]^{2} → 2 such that whenever e : N → 2^{ω} is 1-1, then there is a c_{min}-homogeneous set H ⊆ 2^{ω} such that c ≤ C ↾ e^{−1}[H].

Proof of Lemma 4.3. Let ẋ be a name for a new element of 2^{ω} and let p ∈ ℙ. Since ẋ is a name for a new real, we may assume, by passing to stronger condition if necessary, that for each splitting node s ∈ p and all t, t′ ∈ succ_{p}(s) with t ≠ t′, the initial segments of ẋ decided by p_{t} and p_{t′} are incompatible.

We may assume that for some k_{s} ∈ ω, each p_{t}, t ∈ succ_{p}(s), decides an initial segment of ẋ of length k_{s} and that the decisions of the p_{t}’s on ẋ are pairwise incompatible when restricted to k_{s}. In other words, for each splitting node s of p we have an embedding e_{s} : succ_{p}(s) → 2^{k_{s}} with p_{t} ⊩ ẋ ⊇ e_{s}(t).

Now Lemma 4.4 implies that we can thin out p to a condition q such that for each splitting node s of q, e_{s}[succ_{q}(s)] is a c_{min}-homogeneous subset of 2^{k_{s}} of some color i_{s} ∈ 2.

Thinning out q further if necessary, we may assume that

(∗) whenever s and t are splitting nodes of q and s ⫋ t, then norm(c_{s,q}) <

norm(c_{t,q}). Now either q has a cofinal set of splitting nodes s with i_{s} = 0, or there is a node

s ∈ q such that for all splitting nodes t ∈ q with s ⊆ t, i_{t} = 1. In the first case, we can thin out q to a condition r such that for all splitting nodes s of r, i_{s} = 0. The property (∗) makes sure that r will be a condition. In the second case we can put r := q_{s} and get a condition such that for all splitting nodes s we have i_{s} = 1.

Finally let T_{r} := {s ∈ 2^{<ω} : ∃r′ ≤ r(r′ ⊩ s ⊆ ẋ)} be the tree of r-possibilities for ẋ. Clearly r forces ẋ to be a branch of T_{r}. By the construction of r, [T_{r}] is c_{min}-homogeneous. □

4.2. Iteration. In this section we show that after forcing with a countable support iteration of the c_{max}-forcing, all the new reals (∈ 2^{ω}) are covered by c_{min}- homogeneous sets in the ground model. This implies that after forcing with a countable support iteration of ℙ of length ω_{2} over a model of CH, we obtain a model of set theory in which 𝔥𝔪 = ℵ_{1} but 𝔥𝔪(c_{max}) = ℵ_{2}. The latter statement follows from Claim 4.2.

4.2.1. A preliminary lemma. Our strategy is the following: For an ordinal α let ℙ_{α} denote the countable support iteration of ℙ of length α. Let ẋ be a ℙ_{ω_{2}}-name for a new element of 2^{ω}. We may assume that there is α < ω_{2} such that ẋ is a ℙ_{α}-name for a real not added at any proper initial stage of the iteration ℙ_{α}. Let q be a condition in ℙ_{α}. Recall the definition of T_{q} ⊆ 2^{<ω} from the proof of Lemma 4.3:

T_{q} = {s ∈ 2^{<ω} : ∃q′ ≤ q(q′ ⊩ s ⊆ ẋ)}.

For each p ∈ ℙ_{α} we will construct a condition q ≤ p such that [T_{q}] is c_{min}- homogeneous. The next lemma tells us how to choose the color of [T_{q}] if ẋ is added in a limit step. That is, we can decrease p such that it becomes an element of one of the sets E_{i}, i ∈ 2, defined below. If p ∈ E_{i}, we can build q ≤ p such that [T_{q}] is c_{min}-homogeneous of color i.

Let us fix some notation. If ℚ is any forcing notion and ẏ is a ℚ-name for a new element of 2^{ω} let y[p] be the maximal element of 2^{<ω} such that p ⊩ y[p] ⊆ ẏ. y[p] exists since ẏ is a name for a new real.

For i ∈ 2 let

E_{i} := {p ∈ ℙ_{α} : ∀β < α∀q ≤ p∃q′ ≤ q∃q_{0}, q_{1} ∈ ℙ_{β,α}

(q′ ↾ β ⊩ q_{0}, q_{1} ≤ q′ ↾ [β, α) ∧ parity(x[q_{0}], x[q_{1}]) = i)}.

Recall that parity(s, t) ∈ 2 implies that s and t are incompatible, i.e., s ⊥ t. Lemma 4.5. E_{0} and E_{1} are open and E_{0} ∪ E_{1} is dense in ℙ_{α}.

This lemma is true for all forcing iterations, not only of variations of Sacks forcing. We do not even use the countable supports.

Proof of Lemma 4.5. Let us start with

Claim 4.6. Let β < α and let q ∈ ℙ_{α} be such that for some i ∈ 2 there are q_{0} and q_{1} such that

q ↾ β ⊩ q_{0}, q_{1} ≤ q ↾ [β, α) ∧ parity(x[q_{0}], x[q_{1}]) = i.

Let γ < β. Then there are q′ ≤ q and q′_{0} and q′_{1} such that

q′ ↾ γ ⊩ q′_{0}, q′_{1} ≤ q′ ↾ [γ, α) ∧ parity(x[q′_{0}], x[q′_{1}]) = i.

To see this, let q′ ≤ q be such that q′ ↾ [β, α) = q ↾ [β, α) and q′ ↾ β decides x[q_{0}] and x[q_{1}]. For j ∈ 2 let q′_{j} := (q′ ↾ [γ, β))^{⌢}q_{j}. Now q′, q′_{0}, and q′_{1} work for the claim.

For the proof of the lemma let p ∈ ℙ_{α}. Suppose p ∉ E_{0}. We show that p has an extension in E_{1}. Since p ∉ E_{0}, there are γ < α and q ≤ p such that for all q′ ≤ q and any two sequences q_{0} and q_{1} for names of conditions, if q′ ↾ γ ⊩ q_{0}, q_{1} ≤ q′ ↾ [γ, α), then q′ ↾ γ ⊮ parity(x[q_{0}], x[q_{1}]) = 0. We are done if we can show

Claim 4.7. q ∈ E_{1}.

Let r ≤ q and β < α. Note that by Claim 4.6, the sets E_{i} are not changed if in the definition we replace “∀β < α” by “for cofinally many β < α”. Thus we may assume β ≥ γ.

Since we assumed that ẋ is not added in a proper initial stage of the iteration (before α), there are q_{0} and q_{1} such that

r ↾ β ⊩ q_{0}, q_{1} ≤ r ↾ [β, α) ∧ x[q_{0}] ⊥ x[q_{1}].

Decreasing r ↾ β if necessary, we may assume that r ↾ β decides parity(x[q_{0}], x[q_{1}]) to be i ∈ 2.

By Claim 4.6, there are r′ ≤ r and r_{0} and r_{1} such that

r′ ↾ γ ⊩ r_{0}, r_{1} ≤ r′ ↾ [γ, α) ∧ parity(x[r_{0}], x[r_{1}]) = i.

By the choice of q, i ≠ 0. Thus i = 1. This shows q ∈ E_{1}. □

4.2.2. Some forcing notation. For n ∈ ω and p ∈ ℙ let p^{n} be the set of all minimal t ∈ p such that norm(c_{t,p}) > n. For p, q ∈ ℙ we write q ≤_{n} p if q ≤ p and p^{n} = q^{n}.

A sequence (p_{n})_{n∈ω} in ℙ is a fusion sequence if there is a nondecreasing unbounded function f : ω → ω such that for all n ∈ ω, p_{n+1} ≤_{f(n)} p_{n}. If (p_{n})_{n∈ω} is a fusion sequence, then p_{ω} = ⋂_{n∈ω} p_{n} is a condition in ℙ, the fusion of the sequence. In this definition, the function f is only added for technical convenience. If we only talk about the identity function instead of arbitrary f, we arrive at an essentially equivalent notion.

The idea behind fusion is that in ℙ, even though it is not countably closed, lower bounds exist for suitably chosen countable sequences. All we have to do while inductively thinning out a condition, is to leave splitting nodes with more and more complicated colorings on their successors untouched. This is exactly what we did, although less formally, in the proof of Lemma 4.3. The method can be extended to countable support iterations.

Let α be an ordinal. For F ∈ [α]^{<ℵ_{0}}, η : F → ω, and p, q ∈ ℙ_{α} let q ≤_{F,η} p if q ≤ p and for all β ∈ F, q ↾ β ⊩ q(β) ≤_{η(β)} p(β). Roughly speaking, q ≤_{F,η} p means that on each coordinate from F, q is ≤_{n}-below p where n is given by η.

A sequence (p_{n})_{n∈ω} of conditions in ℙ_{α} is a fusion sequence if there is an increasing sequence (F_{n})_{n∈ω} of finite subsets of α and a sequence (η_{n})_{n∈ω} such that for all n ∈ ω, η_{n} : F_{n} → ω, p_{n+1} ≤_{F_{n},η_{n}} p_{n}, for all γ ∈ F_{n} we have η_{n}(γ) ≤ η_{n+1}(γ), and for all γ ∈ supt(p_{n}) there is m ∈ ω such that γ ∈ F_{m} and η_{m}(γ) ≥ n.

This notion is precisely what is needed in countable support iterations to get suitable fusions. It essentially means that once we have touched (i.e., decreased) a coordinate of p_{0}, we have to build a fusion sequence in that coordinate.

If (p_{n})_{n∈ω} is a fusion sequence in ℙ_{α}, its fusion p_{ω} is defined inductively. Let F_{ω} := ⋃ F_{n}.

Suppose p_{ω}(γ) has been defined for all γ < β for some β < α. If β ∉ F_{ω}, let p_{ω}(β) be a name for 1_{ℙ}. If β ∈ F_{ω}, then p_{ω} ↾ β forces (p_{n}(β))_{n∈ω} to be a fusion sequence in ℙ. Let p_{ω}(β) be a name for the fusion of the p_{n}(β)’s.

4.2.3. Keeping 𝔥𝔪 small. Let ẋ and α be as before. The way to build a condition q for which T_{q} is c_{min}-homogeneous is the following: q will be the fusion of a fusion sequence (p_{n})_{n∈ω} with witness (F_{n}, η_{n})_{n∈ω}. For each n, (p_{n}, F_{n}, η_{n}) will determine a finite initial segment T_{n} of T_{q}. We have to make sure that T_{q} is the union of the T_{n} and that the T_{n} are good enough to guarantee the c_{min}-homogeneity of [T_{q}]. The latter will be ensured by the (F_{n}, η_{n})-faithfulness of each p_{n}, which is defined below.

First we introduce some tools that help us to carry out the necessary fusion arguments.

We call a condition p ∈ ℙ normal if for every s ∈ p with n := |succ_{p}(s)| > 1, c_{s,p} is isomorphic to c_{random} ↾ n and moreover, if t ∈ p is a minimal proper extension of s with more than one successor in p, then |succ_{p}(t)| = |succ_{p}(s)| + 1. Thus, s ∈ p^{n} iff |succ_{p}(s)| = n + 1.

Let I := T (∏_{i∈ω}(i + 1)) = ⋃{∏_{i<n}(i + 1) : n ∈ ω} and I_{n} := {ρ ∈ I : dom(ρ) = n}. If p ∈ ℙ is a normal condition, then each ρ ∈ I_{n} determines an element s_{ρ} of p^{n}. Let p ∗ ρ := p_{s_{ρ}} = {t ∈ p : s_{ρ} ⊆ t ∨ t ⊆ s_{ρ}}.

A condition q ∈ ℙ_{α} is normal if for all β < α, q ↾ β forces that q(β) is normal. Suppose q ∈ ℙ_{α} is a normal condition. For F ∈ [α]^{<ℵ_{0}}, η : F → ω, and σ ∈ ∏_{γ∈F} I_{η(γ)} let q ∗ σ be defined as follows:

For γ ∈ F let (q ∗σ)(γ) be a name for a condition in ℙ such that ⊩_{ℙ_{γ}} (q ∗σ)(γ) = q(γ) ∗ σ(γ). For γ ∈ α \ F let (q ∗ σ)(γ) := q(γ).

Now (q ∗ σ)_{σ∈∏_{γ∈F} I_{η(γ)}} is a finite maximal antichain below q. Consider the tree T generated by {x[q∗σ] : σ ∈ ∏_{γ∈F} I_{η(γ)}}. If q′ ≤_{F,η} q, then T_{q′} is an end-extension of T.

It is clear that the normal conditions in ℙ form a dense subset and the same is true for ℙ_{α}. Therefore, from now on all the conditions we consider are assumed to be normal. We have to be careful at one point, however. Suppose p ∈ ℙ is a normal condition and we have constructed some q ≤_{n} p. q is not necessarily normal. But it is easy to see that there is some q′ ≤_{n} q which is normal. We call the process of passing from q to q′ normalization at n. Normalization at n will be applied automatically without being mentioned whenever we construct some q ≤_{n} p.

Definition 4.8. Let i ∈ 2 and ẋ be fixed. For F and η as before, a condition q ∈ ℙ_{α} is (F, η)-faithful if for all σ, τ ∈ ∏_{γ∈F} I_{η(γ)} with σ ≠ τ, parity(x[q ∗σ], x[q ∗τ]) = i.

Now we are ready to formulate the lemma that will allow us to handle the case where ẋ is added at a limit step of the iteration. Lemma 4.9. Let α be a limit ordinal and let ẋ be a ℙ_{α}-name for an element of 2^{ω} which is not added by an initial stage of the iteration. Let F, η, and i be as in Definition 4.8 and suppose that q ∈ ℙ_{α} is (F, η)-faithful.

a) Let β ∈ α \ F and let F′ := F ∪ {β} and η′ := η ∪ {(β, 0)}. Then q is (F′, η′)-faithful.

b) Suppose q ∈ E_{i}. Let β ∈ F and let η′ := (η ↾ (F \ {β})) ∪ {(β, η(β) + 1)}. Then there is r ≤_{F,η} q such that r is (F, η′)-faithful.

Proof. a) follows immediately from the definitions.

For b) let δ := max(F) + 1 and n := η(β).

Claim 4.10. There is a condition q′ ≤_{F,η} q such that for each σ ∈ ∏_{γ∈F} I_{η(γ)} there are sequences q_{σ,0}, …, q_{σ,n} of names for conditions such that for all k ≤ n,

q′ ∗ σ ↾ δ ⊩ q_{σ,k} ≤ q ↾ [δ, α),

q′ ∗ σ ↾ δ decides x[q_{σ,k}], and for all l ≤ n with k ≠ l,

q′ ∗ σ ↾ δ ⊩ parity(x[q_{σ,k}], x[q_{σ,l}]) = i.

For the proof of the claim, let {σ_{1}, …, σ_{m}} be an enumeration of ∏_{γ∈F} I_{η(γ)}. We build a ≤_{F,η}-decreasing sequence (q_{j})_{j≤m} such that q_{0} := q and q′ := q_{m} works for the claim. As we construct q_{j}, we find suitable q_{σ_{j},k} for all k < n.

Let j ∈ {1, …, m} and assume that q_{j−1} has already been constructed. Since q ∈ E_{i} and E_{i} is open, there are q_{j}^{∗} ≤ q_{j−1} ∗ σ_{j} and sequences q_{σ_{j},0} and q_{σ_{j},1}^{∗} of names of conditions such that

q_{j}^{∗} ↾ δ ⊩ q_{σ_{j},0}, q′_{σ_{j},1} ≤ q ↾ [δ, α) ∧ parity(x[q_{σ_{j},0}], x[q_{σ_{j},1}^{∗}]) = i.

Iterating this process by splitting q_{σ_{j},1}^{∗} into q_{σ_{j},1} and q_{σ_{j},2}^{∗} and so on and decreasing q_{j}^{∗}, we finally obtain q_{j}^{∗} ≤ q_{j−1} ∗ σ_{j} and q_{σ_{j},k}, k ≤ n, such that for all k ≤ n.

q_{j}^{∗} ↾ δ ⊩ q_{σ_{j},k} ≤ q ↾ [δ, α)

and for all l ≤ n with l ≠ k,

q_{j}^{∗} ↾ δ ⊩ parity(x[q_{σ_{j},k}], x[q_{σ_{j},l}]) = i.

We may assume that q_{j}^{∗} ↾ δ decides x[q_{σ_{j},k}] for all k ≤ n. Let q_{j} ≤_{F,η} q_{j−1} be such that q_{j} ∗ σ_{j} ↾ δ = q_{j}^{∗} ↾ δ and q_{j} ↾ [δ, α) = q ↾ [δ, α). This finishes the construction, and it is easy to check that it works.

Continuing the proof of lemma 4.9, let q_{σ,k} and q′ be as in the claim. For ρ ∈ I_{η(β)} let r^{ρ^{⌢}0}, …, r^{ρ^{⌢}n} be sequences of names for conditions such that for all k ≤ n and all σ ∈ ∏_{γ∈F} I_{η(γ)} with σ(β) = ρ,

q′ ∗ σ ↾ δ ⊩ r^{ρ^{⌢}k} = q_{σ,k}.

Let r be a sequence of names for conditions such that r ↾ δ = q′ ↾ δ and for all σ ∈ ∏_{γ∈F} I_{η′(γ)},

q′ ∗ σ ↾ δ ⊩ r ↾ [δ, α) = r^{σ(β)}.

With this choice of r we have r ≤_{F,η} q. It follows from the construction that r is (F, η′)-faithful. □

A similar lemma is true if the new real is added in a successor step.

Lemma 4.11. Let α be a successor ordinal, say α = δ + 1 and let ẋ be a ℙ_{α}-name for an element of 2^{ω} which is not added by an initial stage of the iteration. Let F, η, and i be as in Definition 4.8 and suppose that q ∈ ℙ_{α} is (F, η)-faithful.

a) Let β ∈ α \ F and let F′ := F ∪ {β} and η′ := η ∪ {(β, 0)}. Then q is (F′, η′)-faithful.

b) Suppose

q ↾ δ ⊩ “ [T_{q(δ)}] is c_{min}-homogeneous of color i”.

Let β ∈ F and let η′ := η ↾ F \ {β} ∪ {(β, η(β) + 1)}. Then there is r ≤_{F,η} q such that r is (F, η′)-faithful.

Proof. As in Lemma 4.9, a) follows directly from the definitions.

For the proof of b) we have to consider two cases. First suppose β = δ. In this case let q′ be a name for a condition in ℙ such that for all σ ∈ ∏_{γ∈F} I_{η(γ)} and all k, l ≤ η(β) with k ≠ l,

q ∗ σ ↾ δ ⊩ q′ ≤_{η(δ)} q(δ) ∧ x[q′ ∗ (σ(δ)^{⌢}k)] ⊥ x[q′ ∗ (σ(δ)^{⌢}l)].

Let r ≤_{F,η} q be such that r ↾ δ ⊩ r(δ) = q′ and for all σ ∈ ∏_{γ∈F} I_{η(γ)} and all k ≤ η(β), r ∗ σ ↾ δ decides x[r(δ) ∗ (σ(δ)^{⌢}k)].

Note that r is indeed (F, η′)-faithful since we assumed q ↾ δ to force that T_{q(δ)} is c_{min}-homogeneous of color i.

If β ≠ δ, the argument will be similar to the one used for Lemma 4.9. Let n := η(β).

For all k ≤ n and all σ ∈ ∏_{γ∈F} I_{η(γ)} let q_{σ,k} be a name for a condition such that

q ∗ σ ↾ δ ⊩ q_{σ,k} ≤ q(δ) ∗ σ(δ)

and for all l ≤ n with l ≠ k

q ∗ σ ↾ δ ⊩ x[q_{σ,k}(δ)] ⊥ x[q_{σ,l}(δ)].

Now fix q′ ≤_{F,η} q such that for all σ ∈ ∏_{γ∈F} I_{η(γ)} and all k ≤ n, q′ ∗ σ ↾ δ decides x[q_{σ,k}]. Note that for all k, l ≤ n with k ≠ l we have that

q′ ∗ σ ↾ δ ⊩ parity(x[q_{σ,k}], x[q_{σ,l}]) = i

since [T_{q(δ)}] was forced to be c_{min}-homogeneous.

Choose r such that r ↾ δ = q′ ↾ δ and for all σ ∈ ∏_{γ∈F} I_{η′(γ)}

r ∗ σ ↾ δ ⊩ r(δ) ∗ σ(δ) = q_{σ,k}

where k = σ(β)(n) (i.e., k is the last digit of σ(β)).

It follows from the definition of r that r ≤_{F,η} q. It is easily checked that r is (F, η′)-faithful. □

Combining the last two lemmas, we can show Lemma 4.12. Let G be ℙ_{ω_{2}}-generic over the ground model M. Then in M[G], 2^{ω} is covered by c_{min}-homogeneous sets coded in the ground model. In particular, in M[G], 2^{ω} is covered by ℵ_{1} c_{min}-homogeneous sets.

Proof. We work in M. Let ẋ be a name for an element of 2^{ω}. We show that ẋ is forced to be a branch through a parity-homogeneous tree in M. We may assume that for some α < ω_{2}, ẋ is an ℙ_{α}-name for a real not added in a proper initial stage of the iteration ℙ_{α}. Clearly, cf(α) ≤ ℵ_{0}. Let p ∈ ℙ_{α}. If α is a limit ordinal, using Lemma 4.5, we can decrease p such that for some i ∈ 2, p ∈ E_{i}. If α is a successor ordinal, say α = δ +1, we can use Lemma 4.3 to decrease p such that for some i ∈ 2

p ↾ δ ⊩ “[T_{p(δ)}] is c_{min}-homogeneous of color i”.

By induction, we define a sequence (p_{n}, F_{n}, η_{n})_{n∈ω} such that (1) for all n ∈ ω, p_{n} ∈ ℙ_{α}, p_{n} ≤ p, F_{n} ∈ [α]^{<ℵ_{0}}, η_{n} : F_{n} → ω, and p_{n} is

(F_{n}, η_{n})-faithful,

(2) for all n ∈ ω, F_{n} ⊆ F_{n+1}, p_{n+1} ≤_{F_{n},η_{n}} p_{n}, and for all γ ∈ F_{n} we have

η_{n}(γ) ≤ η_{n+1}(γ), and

(3) for all n ∈ ω and all γ ∈ supt(p_{n}) there is m ∈ ω such that γ ∈ F_{m} and

η_{m}(γ) ≥ n.

This construction can be done using parts a) and b) of Lemma 4.9 and Lemma 4.11 respectively, depending on whether α is a limit ordinal or not, to extend F_{n} or to make η_{n} bigger, together with some bookkeeping to ensure 3. Now (p_{n})_{n∈ω} is a fusion sequence. Let q be the fusion of this sequence. For each n ∈ ω let T_{n} be the tree generated by {x[p_{n} ∗σ] : σ ∈ ∏_{γ∈F_{n}} I_{η(γ)}}. It is easily seen that T_{q} = ⋃_{n∈ω} T_{n}.

It now follows from the faithfulness of the p_{n} that [T_{q}] is c_{min}-homogeneous of color i. Clearly, q forces ẋ to be a branch through T_{q}. It follows that the set of conditions in ℙ_{α} forcing ẋ to be an element of a c_{min}-homogeneous set coded in M is dense in ℙ_{α}. Since ℙ_{α} is completely embedded in ℙ_{ω_{2}}, this finishes the proof of the lemma. □

Corollary 4.13. It is consistent with ZFC that 2^{ℵ_{0}} = ℵ_{2} and 2^{ω} is covered by ℵ_{1} c_{min}-homogeneous sets, but it is not covered by less than 2^{ℵ_{0}} c_{max}-homogeneous sets.

4.3. Why forcing with ℙ_{c_{max}}? One may ask whether there is an essentially simpler way of increasing 𝔥𝔪(c_{max}) while keeping 𝔥𝔪 small other than iterating our basic forcing notion ℙ. Zapletal [34] showed that in certain cases there is an optimal way of increasing a covering number of a σ-ideal. He observed that there is an optimal way of increasing 𝔥𝔪 in the sense that all cardinal invariants which are not bigger than 𝔥𝔪 in ZFC are kept small (assuming the existence of some large cardinals). The natural forcing to do this is the following:

Definition 4.14. The c_{min}-forcing ℙ_{c_{min}} is the partial order consisting of all perfect subtrees p of 2^{<ω} with the property that for all s ∈ p there are splitting nodes t_{0} and t_{1} of p which extend s such that the length of t_{0} is even and the length of t_{1} is odd.

It is easy to see that the ℙ_{c_{min}}-generic real avoids all the c_{min}-homogeneous sets in the ground model. Therefore iterating ℙ_{c_{min}} increases 𝔥𝔪.

The natural approach for increasing 𝔥𝔪(c_{max}) would be forcing with an iteration of the Borel subsets of 2^{ω} modulo the σ-ideal generated by the c_{max}-homogeneous subsets. However, this attempt must fail. Zapletal observed that this forcing notion is not homogeneous, that is, the forcing notion does not stay the same when restricted to some Borel set not covered by countably many c_{max}-homogeneous sets. We show that in fact, this forcing notion increases 𝔥𝔪.

Theorem 4.15. Let X be any Polish space with some nontrivial continuous paircoloring c : [X]^{2} → 2. Then the Boolean algebra of Borel subsets of X modulo the σ-ideal generated by the c-homogeneous sets is forcing equivalent to ℙ_{c_{min}}.

The theorem easily follows from the next lemma, which is a strengthening of Lemma 2.9.

Lemma 4.16. Assume that A ⊆ X is analytic. If A is not covered by countably many c-homogeneous sets, then c_{min} ≤ c ↾ A, i.e., A has a perfect subset on which c is isomorphic to c_{min}.

Proof. Since A is analytic, there is a continuous map f : ω^{ω} → A which is onto. For s ∈ ω^{<ω} let O_{s} := {x ∈ ω^{ω} : s ⊆ x}. For B ⊆ ω^{ω} let

B′ := B \ ⋃{O_{s} : s ∈ ω^{<ω} ∧ f[B ∩ O_{s}] is not covered

by countably many c-homogeneous sets}.

Note that B′ is closed if B is.

Let B_{0} := ω^{ω}, B_{α+1} := B′_{α} for α < ω_{1} and B_{δ} := ⋂_{α<δ} B_{α} for limit ordinals δ < ω_{1}. Since there are only countably many O_{s}, there is α < ω_{1} such that B_{α} = B_{α+1}. Let B := B_{α}.

Since A is not covered by countably many c-homogeneous sets, B is not empty. Clearly, for every open set O ⊆ ω^{ω}, O ∩ B is empty or f[O ∩ B] is not covered by countably many c-homogeneous sets and therefore is not homogeneous. It now follows from the continuity of f and c that for all s ∈ T (B) and all i ∈ 2 there are s_{0}, s_{1} ∈ T (B) extending s such that c is constant on f[O_{s_{0}} ∩ B] × f[O_{s_{1}} ∩ B] with value i.

This is sufficient to construct inductively a perfect binary subtree T of T (B) such that f ↾ [T] is 1-1 and f[[T]] has the desired properties. □

5. Consistency of Cov(Cont(ℝ)) < Cov(Lip(ℝ))

This section is devoted to the proof of Theorem 5.1. Cov(Cont) < 𝔥𝔪 is consistent.

In Definition 4.14 we have already introduced the forcing notion ℙ_{c_{min}} as the right tool to increase 𝔥𝔪.

In this section we write ℙ for ℙ_{c_{min}}. As usual, for every ordinal α, ℙ_{α} denotes the countable support iteration of ℙ of length α. We have to show Lemma 5.2. After forcing with ℙ_{ω_{2}} over a model of CH the continuous functions coded in the ground model cover (2^{ω})^{2} (in the extension).

How do we construct the required continuous mappings in the ground model? Let ẋ and ẏ be ℙ_{ω_{2}}-names for elements of 2^{ω}. Assume that both, ẋ and ẏ, are

forced to be new reals. We may do so because the constant functions take care about covering pairs (x, y) ∈ (2^{ω})^{2} where x or y are in the ground model.

We may also assume that there are α, β < ω_{2} such that ẋ is in fact a ℙ_{α}-name forced not to be added in a proper initial stage of the iteration ℙ_{α} and the same is true for ẏ with respect to β. Finally, we may assume β ≤ α. In particular, ẏ can be considered as a ℙ_{α}-name.

Now let p ∈ ℙ_{α}. We find q ≤ p with the following property: (∗)_{q,ẋ,ẏ} Let T_{q}(ẋ) be the tree of q-possibilities for ẋ defined as in the proof of Lemma

4.3. Then in the ground model there is a continuous map f : [T_{q}(ẋ)] → 2^{ω} such that if G is ℙ_{α}-generic with q ∈ G, then f maps ẋ_{G} to ẏ_{G}.

Clearly, q forces f(ẋ) = ẏ. Thus, the set of conditions forcing f(ẋ) = ẏ for some continuous ground model function f is dense in ℙ_{α}. This shows that for every ℙ_{ω_{2}}-generic filter G, (ẋ_{G}, ẏ_{G}) is indeed covered by some continuous ground model function. Note that the function f in (∗)_{q,ẋ,ẏ} is just a partial function. But since f is defined on the closed set [T_{q}(ẋ)], it can be extended continuously to all of 2^{ω}.

This finishes the proof of Lemma 5.2 provided we know Lemma 5.3. Let α be an ordinal and ẋ a ℙ_{α}-name for an element of 2^{ω} which is not added in a proper initial stage of the iteration. Then for every p ∈ ℙ_{α} and every ℙ_{α}-name ẏ for an element of 2^{ω} there is q ≤ p such that (∗)_{q,ẋ,ẏ} holds.

Proof. We follow closely the proof of Lemma 4.12. We fix ẋ throughout the following proof.

For p ∈ ℙ and n ∈ ω let p^{n} denote the set of those splitting nodes of p that have exactly n splitting nodes among their proper initial segments. For q ≤ p we write q ≤_{n} p if q^{n} = p^{n}. Every ρ ∈ 2^{n} determines an element s_{ρ} of p^{n}. Let p ∗ ρ := p_{s_{ρ}} = {s ∈ p : s ⊆ s_{ρ} ∨ s_{ρ} ⊆ s}.

We call a condition p ∈ ℙ normal if for all splitting nodes s, t ∈ p such that s ⫋ t and t is a minimal splitting node above s, dom(t) \ dom(s) is odd, i.e., dom(s) and dom(t) have a different parity.

As in the ℙ_{c_{max}}-case, if p is a normal condition and q ≤_{n} p, then there is a normal condition r ≤_{n} q. This is normalization at n that from now on will be done automatically, just as in the ℙ_{c_{max}}-case.

We extend the notion of normality to conditions in ℙ_{α} and for F ∈ [α]^{<ℵ_{0}} and η : F → ω we define ≤_{F,η} on ℙ_{α} as for ℙ_{c_{max}} (see section 4.2.2). Fusion sequences are defined as for ℙ_{c_{max}} and it should be clear that fusions of fusion sequences in ℙ_{α} are again conditions, provided the elements of the fusion sequence are normal.

For f and η as above, p ∈ ℙ_{α}, and σ ∈ ∏_{γ∈F} 2^{η(γ)}, p ∗ σ is defined as in Section 4.2.3.

We also use the notion of faithfulness, but in the present context the definition is a weaker than in Section 4.2.3.

Definition 5.4. For F and η as above, p ∈ ℙ_{α} is (F, η)-faithful iff for all σ, τ ∈ ∏_{γ∈F} 2^{η(γ)} with σ ≠ τ, x[p ∗ σ] ⊥ x[p ∗ τ].

The corresponding statement to Lemma 4.9 and Lemma 4.11 is

Claim 5.5. Let F and η be as before and suppose that q ∈ ℙ_{α} is (F, η)-faithful.

a) Let β ∈ α \ F and let F′ := F ∪ {β} and η′ := η ∪ {(β, 0)}. Then there is r ≤_{F,η} q such that r is (F′, η′)-faithful.

b) Let β ∈ F and let η′ := η ↾ F \ {β} ∪ {(β, η(β) + 1)}. Then there is r ≤_{F,η} q such that r is (F, η′)-faithful.

Proof. In contrast to the ℙ_{c_{max}}-case, a) is not trivial here. This is because ≤_{0} is not equivalent to ≤. But this is rather a notational issue. a) clearly follows from the proof of b).

For b) let δ := max F and let {σ_{0}, …, σ_{m}} be an enumeration of ∏_{γ∈F} 2^{η(γ)}. We define a ≤_{F,η}-decreasing sequence (q_{j})_{j≤m} along with names q_{σ,0} and q_{σ,1}, σ ∈ ∏_{γ∈F} 2^{η(γ)}, for conditions.

Let j ∈ {1, … m} and assume that q_{j−1} has been constructed already. Since ẋ is not added in a proper initial stage of the iteration, there are q_{σ_{j},0} and q_{σ_{j},1} such that for all i ∈ 2

q_{j−1} ∗ σ_{j} ↾ δ ⊩ q_{σ_{j},i} ≤ (q(δ) ∗ (σ_{j}(δ)^{⌢}i))^{⌢}q ↾ (δ, α)

and

q_{j−1} ∗ σ_{j} ↾ δ ⊩ x[q_{σ_{j},0}] ⊥ x[q_{σ_{j},1}].

Let q_{j} ≤_{F,η} q_{j−1} be such that q_{j} ∗ σ_{j} ↾ δ decides x[q_{σ_{j},0}] and x[q_{σ_{j},1}]. This finishes the inductive construction of the q_{j}.

Now let r ≤_{F,η} q_{m} be such that r ↾ δ = q_{m} ↾ δ and for all σ ∈ ∏_{γ∈F} 2^{η(γ)} and all coordinatewise extensions τ ∈ ∏_{γ∈F} 2^{η′(γ)} of σ,

r ∗ τ ↾ δ ⊩ r ∗ τ ↾ [δ, α) = q_{σ,τ(η(β))}.

It is easy to check that r works for the claim. □

To conclude the proof of Lemma 5.3, let p ∈ ℙ_{α}. Using some bookkeeping and parts a) and b) of Claim 5.5 we construct a sequence (p_{n})_{n∈ω} and a sequence (F_{n}, η_{n})_{n∈ω} witnessing that (p_{n})_{n∈ω} is a fusion sequence such that p = p_{0} and for all n ∈ ω, p_{n} is (F_{n}, η_{n})-faithful. We can construct the sequences (p_{n})_{n∈ω} and (F_{n}, η_{n})_{n∈ω} with the additional property that for every n ∈ ω and every σ ∈ ∏_{γ∈F_{n}} 2^{η(γ)}, p_{n} ∗ σ decides ẏ ↾ n. Let q be the fusion of the sequence (p_{n})_{n∈ω}. We have to check that (∗)_{q,ẋ,ẏ} holds.

Let a ∈ [T_{q}(ẋ)] and n ∈ ω. Now q ≤_{F_{n},η_{n}} p_{n} and p_{n} is (F_{n}, η_{n})-faithful. It follows that there is exactly one σ_{a,n} ∈ ∏_{γ∈F_{n}} 2^{η_{n}(γ)} such that x[q ∗ σ_{a,n}] ⊆ a.

Let f(a) := ⋃_{n∈ω} y[q ∗σ_{a,n}]. Since for all n ∈ ω, q ∗σ_{a,n} ≤ p_{n} ∗σ_{a,n} and p_{n} ∗σ_{a,n} decides ẏ ↾ n, f(a) ∈ 2^{ω}. It is easily checked that f : [T_{q}(ẋ)] → 2^{ω} is a continuous map witnessing (∗)_{q,ẋ,ẏ}. □

6. Concluding remarks and open problems

The numbers 𝔥𝔪(c_{min}), 𝔥𝔪(c_{max}), Cov(Cont(ℝ)) and Cov(Lip(ℝ)) are examples of covering numbers of meager ideals. Although the hope expressed by Blass in [10] to find a classification of all “simple” cardinal invariants of the continuum was shattered by the construction in [21] of uncountably many different covering numbers of simply defined meager ideals, there is still hope to find the “largest” nontrivial covering number of a meager ideal. By “nontrivial” it is meant that the number can consistently be smaller than the continuum.

At the moment 𝔥𝔪(c_{max}) is a leading candidate for such a number. The numbers Cov(Cont(ℝ)) and Cov(Lip(ℝ)) are also very large, and the largest known nontrivial covering number of an ideal on ℝ^{2} generated by functions and inverses of functions is the covering number of the ideal generated by continuously differentiable functions and their inverses. So it would be natural to compare 𝔥𝔪(c_{max}) to covering by continuously differentiable functions. As mentioned before, the covering number of the ideal on ℝ^{2} generated by twice differentiable functions and inverses of differentiable functions is already continuum.

The meager ideals which historically led to the study of homogeneity numbers are the convexity ideals of closed subsets of ℝ^{2}. If a closed subset of a Euclidean space is not covered by countably many convex subsets (namely, its convex subsets generate a proper σ-ideal), it has a closed subset on which the convex subsets of the whole set generate a meager ideal (see [24] or [19]). For some closed subsets of the plane, this meager ideal coincides with the homogeneity ideal of some continuous pair coloring [20].

Saharon Shelah remarked recently to the authors that he came close to discovering the properties of 𝔥𝔪 in his investigations of monadic theory of order [29]. In an attempt to remove GCH from the proof in the last section of [28] Shelah found a proof from the assumption 𝔥𝔪 = 2^{ℵ_{0}}. He was able to prove that 𝔥𝔪 = 2^{ℵ_{0}} if the continuum is a limit cardinal, but did not prove more about 𝔥𝔪 and eventually found a way to eliminate GCH which did not involve 𝔥𝔪, which was consequently published in [22].

It is not clear why homogeneity numbers of continuous pair-colorings on Polish spaces were not studied earlier. We can only speculate about that. In the very short time since their study was begun, these numbers were related to quite a few subjects. Apart from the relation to planar convex geometry and to finite random graphs, which were mentioned above, there are relations to large cardinals, determinacy and pcf theory. Quite recently, Shelah and Zapletal [30] defined n-dimensional generalizations of 𝔥𝔪(c_{min}) and integrated forcing, pcf theory and determinacy theory to prove several duality theorem for those numbers.

We do not know at the moment if ℵ_{1} < 𝔥𝔪 < 2^{ℵ_{0}} is consistent or not. We do not know if there is a closed planar set whose convexity number is equal to 𝔥𝔪(c_{max}). We also find the following intriguing: Problem 6.1. Are the equalities 𝔥𝔪(c) = 𝔥𝔪(c_{min}) and 𝔥𝔪(c) = 𝔥𝔪(c_{max}) which hold in V^{P_{cmax}} absolute for a reduced coloring c on a Polish space X? In other words, does a reduced coloring c that satisfies 𝔥𝔪(c) = 𝔥𝔪(c_{max}) in some model of set theory which separates 𝔥𝔪(c_{min}) and 𝔥𝔪(c_{max}) satisfy this in every model that separates 𝔥𝔪(c_{min}) and 𝔥𝔪(c_{max})?

References

[1] U. Abraham, S. Geschke, Covering ℝ^{n+1} by graphs of n-ary functions and long linear orderings of Turing degrees, to appear in Proc. Am. Math. Soc.

[2] U. Abraham, M. Rubin, S. Shelah, On the consistency of some partition theorems for continuous colorings, and the structure of ℵ_{1}-dense real order types, Ann. Pure Appl. Logic 29 (1985), no. 2, 123–206

[3] S. Agronski, A.M. Bruckner, M. Laczkovich, D. Preiss, Convexity conditions and intersections with smooth functions, Transactions of the AMS, Volume 289, Issue 2 (1985), 659–677

[4] N. Alon, Problems and results in Extremal Combinatorics, I, Discrete Math. 273 (2003), 31–53 [5] N. Alon, J. Spencer, The probabilistic method, second edition, With an appendix on the life and work of Paul Erdős, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York (2000)

[6] T. Bartoszyński, H. Judah, Set theory: On the structure of the real line, Wellesley, MA: A. K. Peters Ltd. (1995)

[7] J.E. Baumgartner, Chains and antichains in P(ω), J. Symbolic Logic 45 (1980), no. 1, 85–92 [8] J.E. Baumgartner, All ℵ_{1}-dense sets of reals can be isomorphic, Fund. Math. 79 (1973), no. 2, 101–106

[9] J.E. Baumgartner, Iterated forcing, Surveys in set theory, Lond. Math. Soc. Lect. Note Ser. 87 (1983), 1–59

[10] A. Blass. Simple cardinal characteristics of the continuum Set theory of the reals, 63–90, Israel Math. Conf. Proc., 6, Bar-Ilan Univ., Ramat Gan, 1993

[11] M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas, Progress on Perfect Graphs, Math. Programming, Ser. B 97 (2003), 405–422

[12] M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas, The Strong Perfect Graph Theorem, preprint

[13] K. Ciesielski, J. Pawlikowski, Covering Property Axiom CPA, draft

[14] S. Eilenberg. Ordered topological spaces, Amer. J. Math. 63 (1941), 39–45.

[15] R. Engelking, General topology, translated from the Polish by the author, Second edition, Sigma Series in Pure Mathematics, Heldermann Verlag, Berlin (1989)

[16] P. Erdős, J. Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London (1974)

[17] I. Farah, Analytic quotients: theory of liftings for quotients over analytic ideals on the integers Mem. Amer. Math. Soc. 148 (2000), no. 702

[18] Q. Feng, Homogeneity for open partitions of pairs of reals, Trans. Am. Math. Soc. 339 (1993), No.2, 659–684

[19] S. Geschke and M. Kojman. Convexity numbers of closed sets in R^{n}, Proc. Am. Math. Soc. 130 (2002), No.10, 2871–2881

[20] S. Geschke, M. Kojman, W. Kubis, R. Schipperus, Convex decompositions in the plane, meagre ideals, and colorings of the irrationals, Israel J. Math. 131 (2002), 285–317

[21] M. Goldstern and S. Shelah Many simple cardinal invariants, Arch. Math. Logic 32 (1993), no. 3, 203–221

[22] Y. Gurevich and S. Shelah. Monadic theory of order and topology in ZFC, Ann. Math. Logic 23 (1982), no. 2-3, 179–198

[23] K.-P. Hart, B. van der Steeg, A small transitive family of continuous functions on the Cantor set, Topology and its Applications 123, 3 (2002), 409–420

[24] M. Kojman. Convexity ranks in higher dimensions, Fund. Math. 164 (2000), no. 2, 143–163 [25] V. L. Klee, Jr., Convex sets in Linear spaces II, Duke Mathematical Journal 18 (1951), 875–883

[26] K. Kunen, Set theory. An introduction to independence proofs, 2nd print, Studies in Logic and the Foundations of Mathematics, 102, Amsterdam-New York-Oxford: North-Holland (1983)

[27] J. T. Moore, Open colorings, the continuum and the second uncountable cardinal, Proc. Amer. Math. Soc., in press

[28] S. Shelah, The monadic theory of order, Annals of Mathematics 102 (1975), 379–419

[29] S. Shelah, personal communication, May 2002

[30] S. Shelah and J. Zapletal, Duality and the pcf theory, Math Research Letters 9 (2002), 585– [31] J. Steprāns, Decomposing euclidean space with a small number of smooth sets, Transactions of the AMS, Volume 351, Number 4 (1999), 1461–1480

[32] S. Todorčević, Partition problems in topology, Contemporary Mathematics 84, Providence, American Mathematical Society (1989)

[33] B. Veličković, OCA and automorphisms of P(ω)/fin, Topology Appl. 49 (1993), no. 1, 1–13 [34] J. Zapletal, Descriptive Set Theory and Definable Forcing, Memoirs of the Am. Math. Soc. 793 (2004)

(Geschke) II. Mathematisches Institut, Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany

   E-mail address: geschke@math.fu-berlin.de

(Goldstern) Algebra, TU Wien, Wiedner Hauptstrasse 8-10/118, A-1040 Wien, Austria, Europe

   E-mail address: goldstern@tuwien.ac.at

(Kojman) Department of Mathematics, Ben Gurion University of the Negev, Beer Sheva, Israel

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