THE DESCRIPTIVE COMPLEXITY OF THE SET OF ALL CLOSED ZERO-DIMENSIONAL SUBSETS OF A POLISH SPACE

GABRIEL DEBS AND JEAN SAINT RAYMOND

Abstract. Given a space X we investigate the descriptive complexity class Γ_{X} of the set F_{0}(X) of all its closed zero-dimensional subsets, viewed as a subset of the hyperspace F(X) of all closed subsets of X. We prove that max{Γ_{X}; X analytic } = Σ_{2}^{1} and sup{Γ_{X}; X Borel Π_{ξ}^{0}} ⊇ ⅁Σ_{ξ}^{0} for any countable ordinal ξ ≥ 1. In particular we prove that there exists a one-dimensional Polish subpace of 2^{ω} × ℝ^{2} for which F_{0}(X) is not in the smallest non trivial pointclass closed under complementation and the Souslin operation A.

1. Introduction

If X is a compact metrizable space and if we endow the hyperspace space F(X) of all closed subsets of X with its canonical (compact metrizable) topology then (see Proposition 5.1) the set F_{0}(X) of all zero-dimensional closed subspaces of X is a Π_{2}^{0} = G_{δ} subset of F(X). When X is an arbitrary separable metrizable space there is no canonical topology on F(X). Nevertheless in this general context F(X) is still naturally endowed with a canonical Borel structure (the Effros Borel structure) which is isomorphic to the Borel structure of an analytic (Polish) space if X itself is analytic (Polish). As we shall see for any analytic space X the set F_{0}(X) is Σ_{2}^{1} (Proposition 6.1) and this bound is optimal (Theorem 6.2), which answers Question 5.2 of [11].

Theorem 1.1. There exists an analytic space X_{∞} ⊂ 2^{ω} × 𝕀 for which the set F_{0}(X_{∞}) is Σ_{2}^{1}-complete.

Here and in the sequel we denote by 𝕀 the interval [0, 1], and by ℙ and ℚ the sets of irrational and rational numbers respectively. The definition of the notions of Γ-complete and Γ-hard set are recalled in Section 2.1. We do not know whether one can impose on the space X_{∞} to be Polish or even Borel. However we shall prove the following lower complexity bound:

Theorem 1.2. For any countable ordinal ξ ≥ 3 there exists a Π_{ξ}^{0} set X_{ξ} ⊂ 2^{ω} ×𝕀 for which the set F_{0}(X_{ξ}) is ⅁Σ_{ξ}^{0}-hard.

For the definition of the classes ⅁Γ we refer the reader to Section 7. We point out that in [11] E. Pol and R. Pol showed that F_{0}(𝕀 × ℙ) is actually a Π_{1}^{1} \ Σ_{1}^{1} set (note that Π_{1}^{1} = ⅁Σ_{1}^{0} and Σ_{1}^{1} = ⅁Π_{1}^{0}). We do know not whether the previous result holds for ξ = 2 but in this case we have the following:

2010 Mathematics Subject Classification. Primary: 03E15, 54H05; Secondary: 54F45.

Key words and phrases. Effros Borel structure, zero-dimensional sets, σ-ideals, ⅁Γ classes.

Theorem 1.3. There exists a Polish space Y ⊂ 2^{ω} × 𝕀^{2} for which the set F_{0}(Y) is ⅁Σ_{2}^{0}-hard.

We point out that the class ⅁Σ_{2}^{0} is strictly larger than the more classical Selivanovski’s class of C-sets. In particular the set F_{0}(Y) in Theorem 1.3 is not in the smallest class containing all open sets and closed under complementation and operation A. This gives a partial answer to Question 9.12 of [1] which asks about the complexity of F_{0}(X) for an arbitrary Polish space X.

It is interesting to observe that determining the exact complexity of F_{0}(X) for an explicit Polish space X reveals to be a non trivial problem, as long as compactness is faraway. A typical example is the case of the space 𝕀^{2} \ℚ^{2} pointed out in [11] where the authors ask whether the set F_{0}(𝕀^{2} \ ℚ^{2}) is Π_{1}^{1}, a question still open. However it turns out that the space Y of Theorem 1.3 can in fact be embedded as a closed subset of 𝕀^{5} \ ℚ^{5}. It follows then:

Theorem 1.4. The set F_{0}(𝕀^{5} \ ℚ^{5}) is ⅁Σ_{2}^{0}-hard.

The construction of the space Y in Theorem 1.3 relies on a class of subsets of the plane that we call hypergraphs. More precisely the space Y will be a G_{δ} subset of 2^{ω} × H where H is a G_{δ} hypergraph. This contrasts with the fact that the set F_{0}(H) for H itself is a G_{δ} set. The precise definition of an hypergraph is a bit technical. As a first approach one can say that an hypergraph is a subset H of the plane satisfying G ⊂ H ⊂ \overline{G} where G is the graph of some maximal continuous function f : P ⊂ I → ℝ whose domain P is a co-countable subset of some interval I and strongly oscillating around any element of I \ P.

We only state here two simple properties of hypergraphs:

Theorem 1.5. An hypergraph is a one-dimensional connected Polish space which contains no non-trivial continuum.

Theorem 1.6. A closed subset of an hypergraph is zero-dimensional if and only if it is of empty interior.

2. General notions and notations

2.1. Descriptive classes: In all the paper we shall work in the frame of separable metrizable, mostly Polish, spaces. We assume the reader to be familiar with basic notions and results from Descriptive Set Theory, for example as presented in [6] or [10].

A set A is always viewed as a subset of some Polish space X, and the complexity of A is then relative to the given space X. We recall the fundamental notion of reduction: given A ⊂ X and B ⊂ Y the pair (A, X) is said to be reducible to the pair (B, Y) if there exists a continuous mapping φ : X → Y such that A = φ^{−1}(B). A descriptive class (or more simply a class) is a class of such pairs (A, X) closed under reducibility.

In fact we shall identify a set A with a pair (A, X) for some (any) Polish space X ⊃ A depending on the notion. In particular we shall view descriptive classes as classes of sets and when we speak about the complexity of A we mean its complexity relatively to any Polish space X in which A embeds, that is the absolute complexity of A. But when we say that A is reducible to B we mean that (A, X) is reducible to (B, Y) for some Polish spaces X ⊃ A and Y ⊃ B.

We shall consider in the sequel the classical classes that we list next, but also the less popular classes ⅁Γ that we will present later on in Section 7:

Σ_{ξ}^{0}: the additive Baire class of rank ξ

Π_{ξ}^{0}: the multiplicative Baire class of rank ξ

(for ξ = 2 we shall also use the classical notation F_{σ} and G_{δ}) Σ_{1}^{1}: the class of analytic sets. Π_{1}^{1}: the class of co-analytic sets. Σ_{2}^{1}: the class of projections of co-analytic sets, also denoted by P CA. Π_{2}^{1}: the class of complements of P CA sets, also denoted by CP CA. Δ_{2}^{1} := Σ_{2}^{1} ∩ Π_{2}^{1}

Given some class Γ a set A (not necessarily in Γ) is said to be Γ-hard if any set A′ ⊂ 2^{ω} with A′ ∈ Γ is reducible to A; if moreover A is in Γ then A is said to be Γ-complete. If A is Γ-hard and A is reducible to B (in particular if A is a closed subset of B) then B is Γ-hard too.

To any class Γ we associate its dual class Γ̌ = {A^{c} : A ∈ Γ}. If Γ is not self-dual (Γ ≠ Γ̌) then any Γ-complete set is in Γ \ Γ̌

Computing the exact complexity of a given set A is finding a class Γ such that A is Γ-complete. When this is not accessible one then looks for a lower (upper) bound of this complexity that is a class Γ such that A is Γ-hard (A is in Γ)

For any mapping f : X → Y we denote by Gr(f) its graph.

2.2. Sections in product spaces: We shall very often work in product spaces X×Y and we need to fix a number of practical conventions. Given a set E ⊂ X×Y and an element a ∈ X (the first factor) we denote by

E(a) = {y ∈ Y : (a, y) ∈ E}

the section of E at a parallel to the second factor. We also associate to E the set

Ẽ = {(x, (x, y)) ∈ X × (X × Y) : (x, y) ∈ E} ⊂ X × E

hence

Ẽ(a) = {a} × E(a) ⊂ E.

Observe that as a subset of Y the set E(a) might be as complicated as the set E while Ẽ(a) is a closed subset of E.

2.3. Admissible topologies on F(X): For any topological space (X, τ) we denote by F(X) the space of all closed subsets of X.

We recall that the Vietoris topology on the hyperspace F(X) is the topology τ̃ generated by the sets of the form:

F(V) = {F ∈ F(X) : F ⊂ V } and F^{+}(V) = {F ∈ F(X) : F ∩ V ≠ ∅}

where V is an arbitrary open subset of X. It is well known that if (X, τ) is compact then (F(X), τ̃) is compact too; and if moreover X is metrizable then τ̃ is the topology induced by the Hausdorff metric associated to any compatible metric on X.

For an arbitrary separable metrizable space (X, τ) the topology τ̃ is no more metrizable. However one can embed X in a compact space X̂ (not necessarily densely) and then identify any set F ∈ F(X) with \overline{F} (its closure in X̂). The set F(X) is then identified to the set:

F(X, X̂) = \{K ∈ F(X̂) : \overline{K ∩ X} = K\}

Observe that conversely one can recover F(X) from F(X, X̂) since:

F(X) = {K ∩ X : K ∈ F(X, X̂)}.

This identification induces on F(X) a topology τ̃X̂ which depends on the specific compactification X̂.

A topology on F(X) will be said to be admissible if it is of the form τ̃X̂ for some compactification X̂. We point out that any two admissible topologies on F(X) are first Baire class isomorphic. In particular if Γ is any descriptive class which is invariant by first Baire class isomorphisms, and τ̃X̂_{1} , τ̃X̂_{2} are two compactifications of X, a set S ⊂ F(X) is in Γ(τ̃X̂_{1}) iff S is in Γ(τ̃X̂_{2}). This is in particular the case if Γ is a projective class or a Baire class of infinite rank.

In all the sequel F(X) will implicitly be endowed with an admissible topology. We state next the main properties (see [6] Section 12 C) that we will use in the sequel:

a) If X is analytic (Polish) then F(X) is analytic (Polish).

b) If A is open (closed, compact) in X then the set {F ∈ F(X) : F ∩ A ≠ ∅} is open (analytic, closed) in F(X).

c) The set {(F, F′) ∈ F(X) × F(X) : F ⊂ F′} is Borel in F(X) × F(X).

We mention that one can find in the literature other natural Polish topologies on the hyperspace of closed subsets of a Polish space X, such as the Wijsman topology. In most of these topologies the sets of the form F^{+}(V) is open for V open subset of X; it follows then that the Borel structure generated by such a topology coincides with the Borel structure generated by any admissible topology, that is the Effros Borel structure. Also as far as one is interested in descriptive classes of higher complexity than the Borel class, which is the case for our study, the precise choice of the topology is irrelevant.

2.4. Topological dimension: We recall the following fundamental result from Dimension Theory, that we shall very often use in the sequel:

Theorem 2.5. Suppose that X = ⋃_{n≥0} X_{n}. If for all n > 0, X_{n} is a closed subset of X and dim(X_{n}) = 0 then dim(X) = 1 + dim(X_{0}).

In particular if X_{0} = ∅ one gets:

Theorem 2.6. If X = ⋃_{n≥0} X_{n} and for all n ≥ 0, X_{n} is a closed subset of X and dim(X_{n}) = 0 then dim(X) = 0.

3. Computing the descriptive complexity of F_{0}(X)

3.1. Pseudo-graphs and canonical mappings: The graph of a mapping Φ : X → F(Y) is of course a subset of X × F(Y) but one can also consider the graph of the canonical set-valued mapping (with possibly empty values) associated to Φ that is the set:

E = {(x, y) ∈ X × Y : y ∈ Φ(x)}.

that we shall call the pseudo-graph of Φ. Observe that if (U_{n}) is any countable basis of topology in Y and for all n, A_{n} = {x ∈ X : Φ(x) ∩ U_{n} ≠ ∅} then E = ⋂_{n}(X × U_{n}^{c}) ∪ (A_{n} × U_{n}). It follows from 2.3.a) that if the mapping Φ is Borel (continuous) then E is a Borel (G_{δ}) subset of X × Y with closed sections. Conversely any subset E of X × Y with closed sections is the pseudo-graph of a uniquely determined mapping Φ_{E} : X → F(Y) that we call the canonical mapping associated to E. But if E is Borel or even G_{δ} the mapping Φ_{E} is not Borel in general. However as we shall see in next result a kind of converse is true if we work in one additional dimension.

We recall that to any set E ⊂ X × Y we associate the closed subset of X × E defined by:

Ẽ = {(x, (x, y)) ∈ X × (X × Y) : (x, y) ∈ E} ⊂ X × E.

Since all sections of Ẽ are closed subsets of E one can consider then the canonical mapping ΦẼ : X → F(E). It turns out that the mapping ΦẼ has a better behavior than Φ_{E}. Still if E is Borel or even G_{δ} the mapping ΦẼ is not Borel in general. However we have the following:

Theorem 3.2. Let X and Y be two separable metrizable spaces. Given any set E ⊂ X ×Y and any admissible topology on F(E) there exists a subset Ê of X ×E satisfying:

a) Ẽ ⊂ Ê ⊂ X × E.

b) Ê is closed in X × E and for all x ∈ X, Ê(x) \ Ẽ(x) is countable.

c) The canonical mapping ΦÊ : X → F(E) is of the first Baire class and even continuous if X is zero-dimensional.

Proof. Let Z be a compactification of E defining the admissible topology of F(E). We fix two compatible metrics d_{0} on X and d_{1} on Z and equip X × Z with the sum distance d:

d((x, z) , (x′, z′)) = d_{0}(x, x′) + d_{1}(z, z′).

We fix a countable basis (W_{n})_{n∈ω} of the topology of Z such that for all n, W_{n} is nonempty and for all ε > 0 the set {n ∈ ω : diam(W_{n}) > ε} is finite. We then fix for all n an element e_{n} ∈ W_{n} ∩ E, and set A_{n} = {x ∈ X : Ẽ(x) ∩ W_{n} ≠ ∅} and B_{n} = {x ∈ X : d_{0}(x, A_{n}) ≤ 2^{−n}}. Finally let:

D = ⋃_{n∈ω} B_{n} × {e_{n}} and Ê = Ẽ ∪ D

So clause a) is trivially satisfied and for every x ∈ X, D(x) = {e_{n} : B_{n} ∋ x} is countable.

We first prove that Ê is closed in X × E. For this observe that if x ∈ B_{n} then by definition there exists some x′ ∈ A_{n} such that d_{0}(x, x′) ≤ 2^{−n}, and since x′ ∈ A_{n} then there exists some z ∈ W_{n} such that (x′, z) ∈ Ẽ hence since e_{n} ∈ W_{n} we have

d((x, e_{n}) , Ẽ) ≤ d((x, e_{n}) , (x′, z)) = d_{0}(x, x′) + d_{1}(e_{n}, z) ≤ 2^{−n} + diam(W_{n})

It follows that if a sequence (x_{j}, e_{n_{j}})_{j} in D with x_{j} ∈ B_{n_{j}} converges to some element (x, z) then:

– either for infinitely many j’s, n_{j} = n is constant hence e_{n_{j}} = e_{n} and x_{j} ∈ B_{n}, then z = e_{n} and since B_{n} is closed then x ∈ B_{n}; so (x, z) ∈ D ⊂ Ê,

– or lim_{j} n_{j} = ∞ and in this case the inequality above shows that (x, z) ∈ Ẽ.

So any accumulation point of D lies in Ẽ, hence \overline{D}^{X×E} ⊂ D ∪ Ẽ ; and since Ẽ is a closed subset of X × E then Ê is a closed subset of X × E. In the same way if F = \overline{E}^{X×Z} then \overline{D}^{X×F} ⊂ F̂ := F̃ ∪ D and F̂ is a closed subset of X × F.

Claim 3.3. : For all x ∈ X, F̂(x) = \overline{Ê(x)} = \overline{D(x)}.

Proof. Since F̂ is closed then for all x ∈ X, F̂(x) ⊃ \overline{Ê(x)}; and we shall prove that if W_{n} ∩ F̂(x) ≠ ∅ then W_{n} ∩ D(x) ≠ ∅, which proves that F̂(x) ⊂ \overline{D(x)}.

If W_{n} ∩ D(x) ≠ ∅ then we are done. Otherwise W_{n} ∩ F̃(x) ≠ ∅ and we can pick some z ∈ W_{n} such that (x, z) ∈ F̃ = \overline{Ẽ}. Then there exists some (x′, z′) ∈ Ẽ such that d_{0}(x, x′) < 2^{−n} and z′ ∈ W_{n} hence Ẽ(x′) ∩ W_{n} ≠ ∅ and so x′ ∈ A_{n} and x ∈ B_{n} and then (x, e_{n}) ∈ Ê so e_{n} ∈ W_{n} ∩ D(x). □

So clause b) is satisfied and we now prove clause c). Since F(E) is endowed with the admissible topology associated to the compact space Z ⊃ E then by definition, the study of the mapping ΦÊ : X → F(E) reduces to the study of the mapping Ψ : X → F(Z) defined by

Ψ(x) = \overline{ΦÊ(x)} = \overline{Ê(x)} = F̂(x)

Since F̂ is closed in X × Z and Z is compact then for all open set W in Z the set {x ∈ X : Ê(x) ⊂ W } is open. Moreover it follows from the Claim that for all n:

{x ∈ X : F̂(x) ∩ W_{n} ≠ ∅} = ⋃{B_{p} : e_{p} ∈ W_{n}}

which is an F_{σ} set, hence Ψ is of first Baire class.

Finally if X is zero-dimensional we can choose for d_{0} a metric valued in {0} ∪ {2^{−n} : n ≥ 0}, for example by embedding X in 2^{ω} equipped with its standard ultrametric defined for α ≠ β by d_{0}(α, β) = 2^{−n(α,β)} with n(α, β) = min{n : α(n) ≠ β(n)}. It follows that the sets B_{n} above are clopen and Ψ is then continuous. □

Corollary 3.4. Let X be a Polish zero-dimensional space, Y a separable metrizable space and E ⊂ X × Y. Then the set E_{0} = {x ∈ X : dim(E(x)) = 0} is reducible to F_{0}(E).

Proof. Let Ê ⊂ X × E be the set given by Theorem 3.2. Observe that since Ẽ is closed in Ê then it follows from clause b) and Theorem 2.5 that

x ∈ E_{0} ⟺ dim(E(x)) = 0 ⟺ dim(Ẽ(x)) = 0 ⟺ dim(Ê(x)) = 0

then by clause c) the mapping ΦÊ realizes a reduction of E_{0} to F_{0}(E) with all the desired properties. □

4. The σ-ideal structure of F_{0}(X)

Definition 4.1. Given a set X and I ⊂ A ⊂ P(X) we shall say that I is a σ-ideal of A if for any set A ∈ A, if A ⊂ ⋃_{n≥0} A_{n} with A_{n} ∈ I then A ∈ I.

So by Theorem 2.6 for any space X the set F_{0}(X) is a σ-ideal of F(X).

For any space X let K(X) denote the space of all compact subsets of X equipped with the Vietoris topology. Observe that if X is a compact space, a σ-ideal of K(X) in the sense of Definition 4.1 is a “σ-ideal of compact sets” in the sense of [7]. We also recall that in this case (Xcompact) if C ⊂ K(X) is compact then the set C = ⋃ C ⊂ X is compact.

More generally given a set A ⊂ F(X) (endowed with some admissible topology) we shall say that A is closed under compact unions if for any compact set C ⊂ A the set C = ⋃ C is a member of A (in particular C ∈ F(X)).

Lemma 4.2. For any admissible topology F(X) is closed under compact unions.

Proof. Let X̂ be a compactification of X defining the given admissible topology on F(X). We recall that F(X) is then homeomorphic to the subset F(X, X̂) of K(X̂) (see Section 2.3). We now check that F(X, X̂) is closed under compact unions: Suppose that C ⊂ F(X, X̂) is compact and let C = ⋃ C then

\overline{C ∩ X} = \overline{⋃_{K∈C} K ∩ X} ⊃ ⋃_{K∈C} \overline{K ∩ X} = ⋃_{K∈C} K = C

So \overline{C ∩ X} = C and thus C ∈ F(X, X̂). □

It turns out that most results of [7] concerning σ-ideals of compact sets can be extended, with the same proofs, to σ-ideals of any Σ_{1}^{1} set A ⊂ K(X) closed under compact unions. In particular Theorem 7 and Theorem 11 of [7] can be restated as follows:

Theorem 4.3. (Kechris-Louveau-Woodin) Let X be compact space and I be a σ-ideal of A ⊂ K(X). If A is Σ_{1}^{1} and is closed under compact unions then:

a) If I is Σ_{1}^{1} then I is a G_{δ} subset of A

b) If I is Π_{1}^{1} then I is either a G_{δ} subset of A or is Π_{1}^{1}-complete.

Corollary 4.4. Let X be an analytic space and I be a σ-ideal of F(X).

a) If I is Σ_{1}^{1} for some admissible topology then for any admissible topology I is a G_{δ} subset of F(X) .

b) If I is Π_{1}^{1} for some admissible topology then for any admissible topology I is either a G_{δ} subset of F(X) or Π_{1}^{1}-complete.

Proof. As mentioned above any two admissible topologies on F(X) are first Baire class isomorphic, hence if I is Σ_{1}^{1} for some admissible topology then I is Σ_{1}^{1} for any admissible topology. Corollary 4.4 follows then from Lemma 4.2 and Theorem 4.3. □

We recall that F(X) is implicitly endowed with some admissible topology.

Corollary 4.5. Let X be an analytic space.

a) If F_{0}(X) is Σ_{1}^{1} then F_{0}(X) is a G_{δ} subset of F(X) .

b) If F_{0}(X) is Π_{1}^{1} then F_{0}(X) is either a G_{δ} subset of F(X) or Π_{1}^{1}-complete.

We emphasize that in both statements a) and b) of Corollary 4.5 the G_{δ} condition is relative to F(X) and not absolute, unless the space X itself, hence F(X), is Polish. In fact if one wants to ensure that F_{0}(X) is an (absolute) G_{δ} then requiring X to be Polish is not a restriction since X embeds as a closed subset of F_{0}(X), and in this context we have the following complement to Corollary 4.5.

Proposition 4.6. If X is a Polish space and F_{0}(X) is an F_{σ} subset of F(X) then X is zero-dimensional, hence F_{0}(X) = F(X).

Proof. Embed F(X) in F(X̂) for some compactification X̂ of X and let τ̃ denote the corresponding admissible topology on F(X). Let U be the largest open subset of X such that dim(U) = 0 (such a set exists by Theorem 2.6) and suppose that the set Y = X \ U is nonempty.

Since X is Polish then Y as well as F(Y) are Polish too. It follows from the hypothesis that F_{0}(Y) = F_{0}(X) ∩ F(Y) is an F_{σ} subset of F(Y), hence by Corollary 4.4 F_{0}(Y) is a also a G_{δ} subset of F(Y) which is moreover dense since it contains all finite subsets. Hence by Baire Theorem F_{0}(Y) has a dense interior in F(Y). In particular since ∅ is an isolated element of F(Y) the set F_{0}^{∗}(Y) = F_{0}(Y) \ {∅} is of nonempty interior in F(Y). It follows then from the very definition of the topology τ̃ that there exists some finite family (V_{j})_{0≤j≤k} of open subsets of X̂ such that setting V = ⋃_{j=0}^{k} V_{j} then V ∩ Y ≠ ∅ and

V = {K ∩ Y : K ∈ K(Ŷ) , K ⊂ V and ∀j ≤ k, K ∩ V_{j} ≠ ∅}

is a nonempty subset of F_{0}^{∗}(Y). We then fix for each j an element a_{j} in Y ∩ V_{j} (which by the definition of V is nonempty), set F = {a_{j} : 0 ≤ j ≤ p} and write V = ⋃_{n} W_{n} with W_{0} ⊃ F and for all n, \overline{W_{n}} ⊂ V. It follows that for each n, \overline{W_{n}} ∩ Y ∈ F_{0}^{∗}(Y) so dim(\overline{W_{n}} ∩ Y) = 0 hence by Theorem 2.5 dim(V ∩ Y) = 0. Then U′ = U ∪(V ∩Y) = U ∪V is an open subset of X and since dim(U) = 0 then again by Theorem 2.5 dim(U′) = 0. It follows then from the definition of U that V ∩ Y = ∅ which is a contradiction. Hence Y = ∅ and X = U so dim(X) = 0. □

5. When F_{0}(X) is of low complexity

It follows from the previous results that at least in the frame of Polish spaces, aside in the trivial case of a zero-dimensional space, in which case F_{0}(X) = F(X), the first two possible descriptive complexity classes for the set F_{0}(X) are the class G_{δ} and the class Π_{1}^{1}. In this section we show that both of these classes can really occur. One of the main goals of this work is to prove the existence of other possible classes.

We first mention the following elementary proposition concerning the class G_{δ}. We point out that in Section 8 we shall give an example of a Polish space X which does not satisfy the assumptions of this proposition but for which the set F_{0}(X) is G_{δ}.

Proposition 5.1. If a space X is decomposable into a countable union X = ⋃_{n} F_{n} where each F_{n} is either compact or a closed zero-dimensional subset of X then F_{0}(X) is a G_{δ} subset of F(X).

Proof. Fix a countable basis (U_{n})_{n≥0} of the topology of X and observe that if a space E is zero-dimensional then any pair (A, B) of disjoint closed subsets of E can be separated by a clopen set. Hence for any F ∈ F(X) we can write:

F ∈ F_{0}(X) ⟺ \{ \begin{matrix}∀m, n : \overline{U_{m}} ⊂ U_{n}, ∃ V open : \\ \overline{U_{m}} ⊂ V ⊂ U_{n} ∧ F ∩ ∂V = ∅ \end{matrix}

⟺ \{ \begin{matrix}∀m, n : \overline{U_{m}} ⊂ U_{n}, ∃ V open : \\ \overline{U_{m}} ⊂ V ⊂ U_{n} ∧ F ⊂ V ∪ \overline{V}^{c} \end{matrix}

a) We shall first treat the case where X itself is compact. In this case the condition F ⊂ V ∪ \overline{V}^{c} is open, hence by the equivalence above F(X) is G_{δ}.

b) Coming back to the general case, suppose that for all k, F_{2k} is compact and F_{2k+1} is zero-dimensional. Then by Theorem 2.5 for any F ∈ F(X) we have:

F ∈ F_{0}(X) ⟺ ∀k, F ∩ F_{2k} ∈ F_{0}(F_{2k})

Since F_{2k} is compact then by case a) F_{0}(F_{2k}) is G_{δ} and it follows from 2.3.b) that the mapping F ↦ F ∩ F_{2k} is Borel from F(X) to F(F_{2k}). Hence F_{0}(X) is Borel and then by Corollary 4.5 F_{0}(X) is a G_{δ} subset of F(X). □

As pointed out in the introduction, E. Pol and R. Pol showed in [11] that the set F_{0}(ℙ × 𝕀) is Π_{1}^{1} and not Σ_{1}^{1}. We shall prove in the rest of this section a generalization of this result, with a different proof.

Proposition 5.2. If X is a closed subset of Z × K where Z is zero-dimensional and K is compact then the following are equivalent:

(i) dim(X) = 0.

(ii) For all z ∈ Z, dim(X(z)) = 0. In particular if Z is analytic then F_{0}(X) is Π_{1}^{1}.

Proof. (i) ⟹ (ii) is obvious.

(ii) ⟹ (i): Fix (z, y) ∈ X and W a neighbourhood of (z, y). Since dim(X(z)) = 0 there exists an open neighbourhood V of y in K such that V ∩X(z) is clopen in X(z) and V ∩X(z) ⊂ W (z) hence we can find W_{0} and W_{1} two disjoint open subsets of X, such that W_{0} ⊂ W , W_{0}(z) = V and W_{1}(z) = X(z) \ V.

Since K is compact then π the projection mapping on Z is closed hence the set H = π(X \ (W_{0} ∪ W_{1})) is closed, and since z ∉ H there exists a clopen set U such that z ∈ U ⊂ Z \ H, hence V = W_{0} ∩ π^{−1}(U) is clopen in X and (z, y) ∈ V ⊂ W.

This proves the equivalence, and applying this equivalence to F ∈ F(X) we can write:

F ∈ F_{0}(X) ⟺ ∀z ∈ Z, F (z) ∈ F_{0}(K)

equivalently:

F ∉ F_{0}(X) ⟺ ∃z ∈ Z, L ∉ F_{0}(K) : F (z) = L

Since K is compact one easily checks that the set {(F, z, L) ∈ F(X)×Z ×F_{0}(K) : F (z) = L} is a G_{δ} subset of F(X) × Z × F_{0}(K). Then since Z is analytic and by Proposition 5.1 F_{0}(K) is Polish, it follows then from the second equivalence above that the set F(X) \ F_{0}(X) is Σ_{1}^{1} hence the set F_{0}(X) is Π_{1}^{1}. □

Proposition 5.3. If X = Y × Z is the product of a σ-compact space Y and an analytic zero-dimensional space Z then F_{0}(X) is Π_{1}^{1}.

Proof. Set X = ⋃_{n} F_{n} where for all n, F_{n} = K_{n} × Z with K_{n} compact. Then by Theorem 2.5 we have for F ∈ F(X):

F ∈ F_{0}(X) ⟺ ∀n, F ∩ F_{n} ∈ F_{0}(F_{n})

Since the mapping F ↦ F ∩ F_{n} is Borel the conclusion follows then from Proposition 5.2. □

Observe that in the following theorem if Y were zero-dimensional then X would be zero-dimensional too, and then F_{0}(X) = F(X) would be Σ_{1}^{1}, even G_{δ} if Y and Z are Polish. Also if Z were σ-compact then by Proposition 5.1 F_{0}(X) would be G_{δ}.

Theorem 5.4. If X = Y × Z is the product of a non zero-dimensional analytic space Y and a zero-dimensional non σ-compact analytic space Z then F_{0}(X) is Π_{1}^{1}-hard.

Proof. Fix a compactification Ŷ for Y, and a zero-dimensional compactification Ẑ of Z. Fix also an enumeration (y_{n})_{n} of some countable dense subset of Y. Since Z is not σ-compact then by the classical Hurewicz Theorem we can find a copy of the Cantor set C ⊂ Ẑ such that D = C \ Z is a dense countable subset of C. We then fix an enumeration (ẑ_{k})_{k} of D and for all k, ℓ a clopen neighbourhood W_{k,ℓ} of ẑ_{k} in Ẑ of diameter < 2^{−k−ℓ} and an element z_{k,ℓ} ∈ W_{k,ℓ} ∩ Z. Finally let (k, ℓ) ↦ ⟨k, l⟩ denote any bijection from ω^{2} to ω.

Let K(C) the (compact) space of all compact subsets of C. For any K ∈ K(C) set:

Φ(K) = {(y_{⟨k,ℓ⟩}, z_{k,ℓ}) : (k, ℓ) such that W_{k,ℓ} ∩ K ≠ ∅} ⊂ Y × Z

and

Ψ(K) = Ŷ × K ∪ Φ(K) ⊂ Ŷ × Ẑ .

Claim 5.5. \overline{Gr(Φ)} ⊂ Gr(Ψ).

Proof. Suppose that (K, y, z) = lim_{j}(K_{j}, y_{⟨k_{j},ℓ_{j}⟩}, z_{k_{j},ℓ_{j}})_{j} with (y_{⟨k_{j},ℓ_{j}⟩}, z_{k_{j},ℓ_{j}}) ∈ Φ(K_{j}). Then for all j there exists some z_{j} ∈ W_{k_{j},ℓ_{j}} ∩ K_{j}, so z_{j} ∈ K_{j} and since diam(W_{k_{j},ℓ_{j}}) < 2^{−k_{j}−ℓ_{j}} then d(z_{k_{j},ℓ_{j}}, z_{j}) < 2^{−k_{j}−ℓ_{j}}.

– If lim(k_{j} + ℓ_{j}) = ∞ then lim_{j} d(z_{k_{j},ℓ_{j}}, K_{j}) = 0 hence z ∈ K and (y, z) ∈ Ψ(K).

– If not then for infinitely many j’s the sequence (k_{j}, ℓ_{j})_{j} is constant, with value say (k, ℓ), so (K_{j}, y_{⟨k_{j},ℓ_{j}⟩}, z_{k_{j},ℓ_{j}}) = (K_{j}, y_{⟨k,ℓ⟩}, z_{k,ℓ}) with W_{k,ℓ} ∩ K_{j} ≠ ∅; and since W_{k,ℓ} is closed then W_{k,ℓ} ∩ K ≠ ∅ hence (y, z) ∈ Φ(K) ⊂ Ψ(K). □

It follows from the claim that (Ŷ × K) ∪ \overline{Gr(Φ)} ⊂ Gr(Ψ) ⊂ (Ŷ × K) ∪ Gr(Φ) hence Gr(Ψ) = (Ŷ × K) ∪ \overline{Gr(Φ)} is a closed subset of K(C) × Ŷ × C and the compact-valued mapping K ↦ Ψ(K) is u.s.c.. Hence for any open set U ⊂ Ŷ ×C the set {K ∈ K(C) : Ψ(K) ⊂ U} is open. Moreover if U = V × W is a basic open set then

Ψ(K) ∩ U ≠ ∅ ⟺ \{ \begin{matrix}∃ (k, ℓ), (y_{⟨k,ℓ⟩}, z_{k,ℓ}) ∈ U and K ∩ W_{k,ℓ} ≠ ∅ , \\ or K ∩ W ≠ ∅ \end{matrix}

so the set {K ∈ K(C) : Ψ(K) ∩ U ≠ ∅} is open too. Hence the mapping Ψ : K(C) → F(Ŷ × C) is continuous.

Observe that X̂ = Ŷ × Ẑ is a compactification of X = Y × Z and for all K, Ψ(K) ∩ X is a closed subset of X which by the lemma is dense in Ψ(K). Hence if we identify F(X) to a subspace of F(X̂) then the mapping Ψ is identified to the mapping Ψ̃ : K(C) → F(X) with Ψ̃(K) = Ψ(K) ∩ X which is then continuous for the corresponding topology. Observe finally:

– if K ∈ K(D) then Ψ̃(K) = Φ(K) is countable hence Ψ̃(K) ∈ F_{0}(X)

– if not and z ∈ K \ D then Ψ̃(K) ⊃ Y × {z} hence Ψ̃(K) ∉ F_{0}(X) Hence Ψ̃ is a continuous reduction of K(D) to F_{0}(X), and it is well known that if D is any dense countable subset of the Cantor space then K(D) is a Π_{1}^{1}-complete subset of K(2^{ω}), hence F_{0}(X) is Π_{1}^{1}-hard. □

Corollary 5.6. If X = Y ×Z is the product of a σ-compact non zero-dimensional space Y and an analytic zero-dimensional non σ-compact space Z then F_{0}(X) is Π_{1}^{1}-complete.

Corollary 5.7. If X is a non zero-dimensional and non σ-compact analytic space homeomorphic to its square X^{2} then F_{0}(X) is Π_{1}^{1}-hard.

5.8. The Erdős space: As an application we mention the case of Erdős space S ([5]). We recall that this is the closed subset S of the Hilbert space ℓ^{2} = ℓ^{2}(ℕ) defined by:

S = {(x_{n})_{n≥0} ∈ ℓ^{2} : ∀n, x_{n} = 0 or x_{n}^{−1} ∈ ℕ}.

We claim that the set F_{0}(S) is Π_{1}^{1}-hard. Indeed since any compact subset of S is zero-dimensional then by Theorem 2.5 the Polish space S is non σ-compact. Moreover the isometry Ψ : ℓ^{2} × ℓ^{2} → ℓ^{2} defined by ψ(e_{k}, 0) = e_{2k} and ψ(0, e_{k}) = e_{2k+1} induces an homeomorphism from S^{2} onto S, hence by Corollary 5.7 F_{0}(S) is Π_{1}^{1}-hard. However we do not know the exact complexity of F_{0}(S).

6. The maximum complexity of F_{0}(X) when X is Σ_{1}^{1}

Proposition 6.1. If X is an analytic space then F_{0}(X) is Σ_{2}^{1}.

Proof. Fix a countable basis (U_{n})_{n≥0} of the topology of X. Resuming the analysis in the proof of Proposition 5.1 we have for any F ∈ F(X):

F ∈ F_{0}(X) ⟺ \{ \begin{matrix}∀m, n : \overline{U_{m}} ⊂ U_{n}, ∃ V open : \\ \overline{U_{m}} ⊂ V ⊂ U_{n} ∧ F ⊂ V ∪ \overline{V}^{c} \end{matrix}

⟺ \{ \begin{matrix}∀m, n : \overline{U_{m}} ⊂ U_{n}, ∃ V open : \\ \overline{U_{m}} ⊂ V ⊂ U_{n} ∧ F ∩ V^{c} ∩ \overline{V} = ∅ \end{matrix}

⟺ \{ \begin{matrix}∀m, n : \overline{U_{m}} ⊂ U_{n}, ∃ F′ ∈ F(X) : \\ U_{n}^{c} ⊂ F′ ⊂ \overline{U_{m}}^{c} ∧ F ∩ F′ ∩ (Int(F′))^{c} = ∅ \end{matrix}

Then observe that by 2.3.c) condition “U_{n}^{c} ⊂ F′ ⊂ \overline{U_{m}}^{c}” on F′ is Σ_{1}^{1} while condition “F ∩ F′ ∩ (Int(F′))^{c} = ∅” on (F, F′) is co-analytic since the dual condition “F ∩ F′ ∩ (Int(F′))^{c} ≠ ∅” is equivalent to:

∃x ∈ F ∩ F′ : ∀p (x ∉ U_{p} ∨ (∃q : U_{q} ⊂ U_{p} ∧ F′ ∩ U_{q} = ∅))

which is analytic by 2.3.b). It follows from the previous analysis that F_{0}(X) is the projection of the intersection of an analytic set with a co-analytic set, hence F_{0}(X) is Σ_{2}^{1}. □

Theorem 6.2. There exists an analytic subspace X of 2^{ω} × 𝕀 for which F_{0}(X) is Σ_{2}^{1}-complete.

Proof. Fix an enumeration (I_{n})_{n} of all nonempty subintervals of 𝕀 with endpoints in ℚ, and fix for all n, G_{n} ⊂ I_{n} a copy of ω^{ω} and a homeomorphism h_{n} : G_{n} → ω^{ω}.

Let A be any Σ_{2}^{1} subset of 2^{ω}, that we represent as the projection on the first factor of some Π_{1}^{1} set B ⊂ 2^{ω} × ω^{ω}, and consider the set:

X = {(α, z) ∈ 2^{ω} × 𝕀 : ∀n, z ∉ G_{n} ∨ (z ∈ G_{n} ∧ (α, h_{n}(z)) ∉ B)}

which is clearly Σ_{1}^{1}.

Claim 6.3. α ∈ A if and only if dim(X(α)) = 0.

Proof. – If α ∈ A fix β ∈ ω^{ω} such that (α, β) ∈ B and set for all n, z_{n} = h_{n}^{−1}(β) ∈ G_{n} then (α, h_{n}(z_{n})) = (α, β) ∈ B hence (α, z_{n}) ∉ X. Since the set D = {z_{n}; n ∈ ω} is dense in 𝕀 then the set E = 𝕀 \ D is of empty interior in I hence dim(E) = 0 and since X(α) ⊂ E then dim(X(α)) = 0.

– If α ∉ A then for all β ∈ ω^{ω} (α, β) ∉ B hence for all z ∈ 𝕀, if z ∈ G_{n} then (α, h_{n}(z)) ∉ B, hence X(α) ⊃ 𝕀 hence dim(X(α)) ≥ 1. □

It follows then from Claim 6.3 and Corollary 3.4 that the set A is reducible to F_{0}(X). So starting with a Σ_{2}^{1}-complete set A and considering the corresponding space X, the set F_{0}(X) is then Σ_{2}^{1}-hard, hence by Proposition 6.1, Σ_{2}^{1}-complete.

□

7. The maximum descriptive class of F_{0}(X) when X is Borel

We do not know whether Theorem 6.2 holds for some Polish space X. We are only able to prove that in this more restrictive context the maximum complexity of F_{0}(X) is much beyond the class Π_{1}^{1}. More generally we shall prove a similar result for the case where X is a Π_{ξ}^{0} set, with a lower bound increasing with ξ, still below the class Δ_{2}^{1}.

7.1. The classes ⅁Γ:

7.1.a Games and strategies: Given any set A ⊂ ω^{ω} we denote by G_{A} the standard game on ω with A as the win condition for Player I. More explicitly G_{A} is the game in which the two Players choose alternatively an element in ω:

\begin{matrix}I : & n_{0} & & n_{2} & & ⋯ \\ II : & & n_{1} & & n_{3} & & ⋯ \end{matrix}

Thus an infinite run in the game is an infinite sequence γ = (n_{0}, n_{1}, n_{2} ⋯) ∈ ω^{ω} and Player I wins the run if γ ∈ A.

We view a strategy in such a game as a mapping σ : ω^{<ω} → ω (for Player I ) or τ : ω^{<ω} \ {∅} → ω (for Player II). We denote by Σ_{I} (Σ_{II}) the set of all strategies for Player I (Player II) that we endow with their natural product topologies for which Σ_{I} ≈ Σ_{II} ≈ ω^{ω}.

Given any pair (σ, τ) ∈ Σ_{I} × Σ_{II} we define inductively the infinite run

σ ⋆ τ = γ = (n_{0}, n_{1}, n_{2} ⋯) ∈ ω^{ω}

by n_{0} = σ(∅) , n_{2k} = σ(n_{1}, n_{3}, ⋯, n_{2k−1}) and n_{2k+1} = τ(n_{0}, n_{2}, ⋯, n_{2k}). The mapping ⋆ : Σ_{I} × Σ_{II} → ω^{ω} thus defined is then clearly continuous and:

– the strategy σ ∈ Σ_{I} is winning in the game G_{A} iff for all τ ∈ Σ_{II}, σ ⋆ τ ∈ A – the strategy τ ∈ Σ_{II} is winning in the game G_{A} iff for all σ ∈ Σ_{I}, σ ⋆ τ ∉ A

7.1.b The game operator ⅁: Let B ⊂ X × ω^{ω} where X is an arbitrary Polish space then for all x ∈ X, B(x) ⊂ ω^{ω} and one can consider the game G_{B(x)}, and then define

⅁B = {x ∈ X : Player I wins the game G_{B(x)}}

In all the sequel Γ denotes a non trivial class (Γ and Γ̌ ≠ {∅}) which admits a Γ-complete set (that is Γ is a Wadge class). In particular Γ could be any Baire class or projective class.

Given such a class Γ, a set A ⊂ X is said to be in ⅁Γ if it is of the form A = ⅁B for some B ⊂ X × ω^{ω} in Γ. The reader can find in [10] a detailed study of the operator ⅁. We state next only some elementary properties:

(i) ⅁Γ is closed under countable unions and intersections.

(ii) If Γ is closed under unions with closed sets then ⅁Γ is closed under

operation A. (iii) If all games in Γ are determined then ⅁Γ̌ is the dual class of ⅁Γ. (iv) If Γ ⊂ Π_{n}^{1} then ⅁Γ ⊂ Σ_{n+1}^{1} and if Γ = Π_{n}^{1} then ⅁Γ = Σ_{n+1}^{1}

Observe that since all Borel games are determined then ⅁Δ_{1}^{1} ⊂ Δ_{2}^{1} with strict inclusion in general. In fact it turns out that sets in ⅁Δ_{1}^{1} possess all classical descriptive regularity properties such as Baire property or universal measurability, while for an arbitrary Δ_{2}^{1} set such a property might depend on Set Theory axioms.

It is easy to see that ⅁Σ_{1}^{0} = Π_{1}^{1} and ⅁Π_{1}^{0} = Σ_{1}^{1} (see 6D.2 in [10] edition 2009), and for Baire classes Γ of low rank the classes ⅁Γ coincide with some more classical classes considered much before the intrusion of games in Descriptive Set Theory. In particular the classes ⅁Σ_{2}^{0} and ⅁Σ_{3}^{0} are related to Kolmogorov’s Rsets (we refer the reader to [3] and [4] for definitions and more details). Also relying on the classical transfinite analysis of the class Δ_{2}^{0} one easily derive from 7.1.b.(ii) that ⅁Δ_{2}^{0} is the smallest non trivial class closed under complementation and operation A, also known as Selivanovski’s class of C-sets.

We also point out that by a result due to Solovay ⅁Σ_{2}^{0} is exactly the class of sets admitting a Σ_{1}^{1}-inductive definition (see [10]). This probably explains why ⅁Σ_{2}^{0} sets arise naturally in analysis, though very few natural examples of ⅁Σ_{2}^{0}- complete sets are known, while no such examples are known for higher ⅁Γ classes. We mention the following two simple examples:

– (Louveau [9]): There exists a G_{δ} set G ⊂ 2^{ω} × ω^{ω} such that if π denotes the projection mapping on the first coordinate and B = {π(K); K ∈ K(G)} then the σ-ideal of K(2^{ω}) generated by B is ⅁Σ_{2}^{0}-complete.

– (Saint Raymond [12]): Let T ⊂ 2^{ω^{<ω}} denote the set of all trees on ω. Then the set QB = {T ∈ T : ∃α ∈ ω^{ω}, ∀β ∈ ⌈T ⌉ α ≰ β} (where ≤ denotes the product order on ω^{ω}) is ⅁Σ_{2}^{0}-complete.

The following well known result is the only result we will use in this section. For the convenience of the reader we give the simple argument which is based on the fundamental notion of “good universal sets” which play a central role in recursivity (see [10]).

Lemma 7.2. For any Baire class Γ there exists a set U ⊂ 2^{ω} × ω^{ω} in Γ such that the set ⅁U is ⅁Γ-complete.

Proof. Fix a homeomorphism φ : 2^{ω} × 2^{ω} → 2^{ω} and for all α let φ_{α} denote the partial mapping φ(α, ·) : 2^{ω} → 2^{ω} . Starting from any Γ-set V ⊂ 2^{ω} × (2^{ω} × ω^{ω}) which is universal for Γ-subsets of (2^{ω} × ω^{ω}) define

U = {(φ(α, β), γ) ∈ 2^{ω} × ω^{ω} : (α, β, γ) ∈ V }

Then for any Γ-set B ⊂ 2^{ω} × ω^{ω} there exists some α ∈ 2^{ω} such that B = V (α) so for any (β, γ) ∈ 2^{ω} × ω^{ω} we have:

(β, γ) ∈ B ⟺ (α, β, γ) ∈ V ⟺ (φ(α, β), γ) ∈ U ⟺ (φ_{α}(β), γ) ∈ U hence U is Γ-complete. Moreover for any β ∈ 2^{ω}, since B(β) = U(φ_{α}(β)), then:

β ∈ ⅁B ⟺ Player I wins G_{B(β)}
⟺ Player I wins G_{U(φ(α,β))} ⟺ φ_{α}(β) ∈ ⅁U

hence φ_{α} reduces ⅁B to ⅁U and ⅁U is ⅁Γ-complete. □

Theorem 7.3. Let H be a perfect non zero-dimensional Polish space and G a dense G_{δ} subset of H. Assume that for every dense subset D of G the space H \D is zero-dimensional. Then for any countable ordinal ξ ≥ 3 there exists a Π_{ξ}^{0} set X ⊂ ω^{ω} × H such that F_{0}(X) is ⅁Σ_{ξ}^{0}-hard.

If moreover G is nowhere relatively σ-compact in H then the same conclusion holds for ξ = 2.

Proof. Fix a countable basis (W_{n}) of the topology in H. Since G is dense in H then for all n the set G ∩ W_{n} is perfect so we can fix a copy of ω^{ω} say G_{n} in G ∩ W_{n} and a homeomorphism h_{n} : G_{n} → Σ_{I} ≈ ω^{ω}.

Given any Borel set U ⊂ 2^{ω} × ω^{ω} let

X_{U} = {(α, τ, z) ∈ 2^{ω} × Σ_{II} × H : ∀n, z ∈ G_{n} → (α, h_{n}(z) ⋆ τ) ∉ U}

Claim 7.4. α ∈ ⅁U if and only if dim(X_{U}(α)) = 0.

Proof. – If α ∈ ⅁U then Player I has a winning strategy in the game G_{U(α)}. Fix such a strategy σ^{∗} ∈ Σ_{I} and let for all n, z_{n} = h_{n}^{−1}(σ^{∗}) ∈ G_{n} then for all τ ∈ Σ_{II}, h_{n}(z_{n}) ⋆ τ = σ^{∗} ⋆ τ ∈ U(α) hence (α, τ, z_{n}) ∉ X_{U}. Then by construction the set D = {z_{n} : n ∈ ω} is dense in G hence the set E = H \ D is zero-dimensional. But by the observation above X_{U}(α) ⊂ Σ_{II} × E hence dim(X_{U}(α)) = 0.

– If α ∉ ⅁U then, since the game G_{U(α)} is determined, Player II has a winning strategy. Fix such a strategy τ^{∗} ∈ Σ_{II}; then for all z ∈ H, if z ∈ G_{n} then σ_{n} = h_{n}(z) ∈ Σ_{I}, and since τ^{∗} is winning for Player II then h_{n}(z_{n})⋆τ^{∗} = σ_{n} ⋆τ^{∗} ∉ U(α) hence X_{U}(α, τ^{∗}) ⊃ H and so dim(X_{U}(α)) ≥ dim(X_{U}(α, τ^{∗})) ≥ dim(H) > 0. □

From now on we let U ⊂ 2^{ω} × ω^{ω} be a Σ_{ξ}^{0} set given by Lemma 7.2 and set X = X_{U}. Then as in the proof of Theorem 6.2, applying Corollary 3.4, one concludes that the set F_{0}(X) is ⅁Σ_{ξ}^{0}-hard.

To finish the proof we only need to check that X has the expected complexity. Observe first that since 2^{ω} × Σ_{II} ≈ 2^{ω} × ω^{ω} ≈ ω^{ω} then X can indeed be viewed as a subset of ω^{ω} × H. Moreover for a given n:

(z ∈ G_{n} → (α, h_{n}(z) ⋆ τ) ∉ U) ⟺ (z ∉ G_{n} ∨ (z ∈ G_{n} ∧ (α, h_{n}(z) ⋆ τ) ∉ U))

Since U is Σ_{ξ}^{0} and since h_{n} : G_{n} → 2^{ω} ×ω^{ω} is continuous and its domain G_{n} ≈ ω^{ω} is a Π_{2}^{0} set then for all ξ ≥ 2 the condition “z ∈ G_{n} ∧ (α, h_{n}(z) ⋆ τ) ∉ U” on (α, τ, z) ∈ 2^{ω} ×Σ_{II} ×H is Π_{ξ}^{0}. Moreover if ξ ≥ 3 the condition “z ∉ G_{n}” on z ∈ H defines a Σ_{2}^{0} subset of H, hence an (absolute) Π_{ξ}^{0} set. This proves the first part of the theorem.

If G is nowhere relatively σ-compact in H then no W_{n} ∩ G is contained in a σcompact subset of H. Hence by Hurewicz’ theorem for all n there exists a subset G_{n} of W_{n} ∩ G which is closed in H and homeomorphic to ω^{ω}. Then resuming the complexity analysis of X the last condition “z ∉ G_{n}” defines now an open subset of H hence an (absolute) Π_{2}^{0} set, and it follows that if ξ = 2 then X is a Π_{2}^{0} set. □

Corollary 7.5. For any positive countable ordinal ξ ≠ 2 there exists a Π_{ξ}^{0} set X ⊂ ω^{ω} × 𝕀 such that F_{0}(X) is ⅁Σ_{ξ}^{0}-hard.

Proof. For ξ = 1, ⅁Σ_{1}^{0} = Π_{1}^{1} and the result follows from Corollary 5.6 with X = ℙ×𝕀; and for ξ ≥ 3 the result follows from Theorem 7.3, with H = G = 𝕀. □

We do not know whether Corollary 7.5 holds for ξ = 2, but in Section 9 we shall construct a Π_{2}^{0} subset of ω^{ω} × 𝕀^{2} for which the set F_{0}(X) is ⅁Σ_{2}^{0}-hard.

8. Hypergraphs

Given any function f : P ⊂ ℝ → ℝ and any element a ∈ \overline{P} we denote by:

Ωf(a) := {lim_{j} f(x_{j}) : x_{j} ∈ P and lim_{j} x_{j} = a}
Ω^{−}f(a) := {lim_{j} f(x_{j}) : x_{j} ∈ P, x_{j} ≤ a and lim_{j} x_{j} = a}
Ω^{+}f(a) := {lim_{j} f(x_{j}) : x_{j} ∈ P, x_{j} ≥ a and lim_{j} x_{j} = a}

the sets of all (left, right) cluster values of f at a, so Ωf(a) = Ω^{−}f(a) ∪ Ω^{+}f(a). Observe that if G is the graph of f and \overline{G} its closure in ℝ^{2} then Ωf(a) = \overline{G}(a).

Lemma 8.1. Given any countable subset Q of a non trivial interval I ⊂ ℝ there exists a continuous function f : P = I \ Q → ℝ satisfying for all a ∈ Q:

a) Ωf(a) = Ω^{−}f(a) = Ω^{+}f(a) is a non trivial interval.

b) There exists a continuous function g : I \ {a} → ℝ such that the function f − g : P → ℝ admits a limit at a.

Proof. Fix an enumeration (a_{n})_{n≥0} of Q and set for all n, g_{n}(x) = 2^{−n} sin(\frac{1}{a_{n} − x}).

Then g_{n} : I \ {a_{n}} → [−2^{−n}, 2^{−n}] is a continuous function and

Ωg_{n}(a_{n}) = Ω^{−}g_{n}(a_{n}) = Ω^{+}g_{n}(a_{n}) = [−2^{−n}, 2^{−n}].

Finally set for x ∈ P = I \ Q:

f(x) = ∑_{n=0}^{∞} g_{n}(x).

Since |g_{n}(x)| ≤ 2^{−n} for all x ∈ P the series is uniformly convergent on P, hence the function f is well defined and continuous on P. Similarly for all n, the function h : P ∪ {a_{n}} → ℝ defined by h(x) = ∑_{k≠n} g_{k}(x) is also continuous, so f(x) − g_{n}(x) = h(x) tends to h(a_{n}) when x tends to a_{n} and

Ωf(a_{n}) = Ω^{−}f(a_{n}) = Ω^{+}f(a_{n}) = [h(a_{n}) − 2^{−n}, h(a_{n}) + 2^{−n}].  □

It was pointed to us by E. Pol and R. Pol that the function f used in the previous proof was considered by K. Kuratowski and W. Sierpinski in [8].

Definition 8.2. We shall say that a set H ⊂ ℝ^{2} is an hypergraph if G ⊂ H ⊂ \overline{G} where G is the graph of a continuous function f : I \ Q → ℝ satisfying clauses a) and b) of Lemma 8.1 and for all a ∈ Q, the set H(a) is dense and of empty interior in \overline{G}(a). We shall then refer to the set G as the graph part of H.

8.3. Remarks: a) If H is an hypergraph and I, Q, P, f, G are as in Definition 8.2 we shall write H ≡ (H, I, Q, P, f, G). Observe that this tuple is uniquely determined by H since I is the projection of H on the first factor, Q = I \ P, and P is the set of all elements x ∈ I such that H(x) is a singleton {f(x)}, which defines f and G = Gr(f).

b) If I′ and J′ are intervals such that I′ ∩P ≠ ∅ and f(I′ ∩P) ⊂ J′ then clearly H′ = H ∩ (I′ × J′) is an hypergraph too. It follows that any nonempty open subset W of an hypergraph H contains an hypergraph. Indeed since the graph part G is dense in H one can pick some element (a, f(a)) in W ∩ G and then by continuity of f at a find intervals I′ ∋ a and J′ ∋ f(a) such that f(I′ ∩ P) ⊂ J′ and H ∩ (I′ × J′) ⊂ W.

c) By Baire Theorem an hypergraph cannot be an F_{σ} set of ℝ^{2}: indeed if H were the union of countably many compact sets F_{n} then there would be some n such that G ∩ F_{n} has nonempty interior in G hence some subinterval J of I such that ∀x ∈ P ∩ J (x, f(x)) ∈ F_{n}. And we would have \overline{G} ∩ (J × ℝ) ⊂ F_{n} ⊂ H. In particular for x ∈ Q ∩ J, H(x) would contain an interval and would not be zero-dimensional.

But if Q′ is any countable dense subset of ℝ then \overline{G}\Q×Q′ is a G_{δ} hypergraph. In particular there are G_{δ} hypergraphs which are relatively closed subsets of 𝕀^{2} \ ℚ^{2}.

In all the sequel (H, I, Q, P, f, G) denotes an arbitrary given hypergraph and π : ℝ^{2} → ℝ denotes the projection mapping on the first factor.

Theorem 8.4. If H is an hypergraph and E ⊂ H is such that π(E) is a non trivial interval then the set E is connected. In particular any hypergraph is connected.

Proof. Replacing I by the interval if necessary we may suppose that π(E) = I (see Remark 8.3 b)). So let U_{0} be an open subset of I × ℝ such that U_{0} ∩ E ≠ ∅ with ∂U_{0} ∩ E = ∅ and set U_{1} = I × ℝ \ \overline{U_{0}}. So U_{0} ∩ E and U_{1} ∩ E are two clopen subsets of E and we shall prove that E ⊂ U_{0}.

Observe that since π(E) = I then necessarily E ⊃ G and set K = \overline{G} (the closure of G in ℝ^{2}). Since K is a closed subset of I ×ℝ with compact sections the set-valued mapping x ↦ K̃(x) is u.s.c. (we recall that K̃(x) = {x} × K(x) ⊂ K) hence for i ∈ {0, 1} the set V_{i} = {x ∈ I : K̃(x) ⊂ U_{i}} is open in I; and since K̃(x) ≠ ∅ for all x ∈ I and U_{0} ∩ U_{1} = ∅ then V_{0} ∩ V_{1} = ∅. Moreover since G = Gr(f) ⊂ U_{0} ∪ U_{1} then P ⊂ V_{0} ∪ V_{1}. Hence F = I \ (V_{0} ∪ V_{1}) ⊂ Q is a countable closed subset of I and we shall denote, for any countable ordinal ξ, by F^{(ξ)} its Cantor derivative of order ξ.

Claim 8.5. For any interval J ⊂ I \ F^{(ξ)} there exists i ∈ {0, 1} such that for all x ∈ J, Ẽ(x) ⊂ U_{i}.

Proof. We prove the Claim by induction on ξ:

– For ξ = 0, F^{(0)} = F so J ⊂ V_{0} ∪ V_{1} hence J ⊂ V_{i} for some i; so for all x ∈ J, Ẽ(x) ⊂ K̃(x) ⊂ U_{i}.

– Assume now that the Claim is proved for all η < ξ and fix an interval J ⊂ I \ F^{(ξ)}. Then for all a ∈ J we can fix some η_{a} < ξ such that a ∉ F^{(η_{a}+1)} and an open interval J^{a} =]a − ε, a + ε[ such that J^{a} ∩ F^{(η_{a})} ⊂ {a}.

\underline{Subclaim}: For all a ∈ J there exists i ∈ \{0, 1\} and an open neighbourhood W of a such that for all x ∈ W, Ẽ(x) ⊂ U_{i} .

We first finish the proof of the Claim assuming the Subclaim: Set for i ∈ {0, 1}, W_{i} = {x ∈ J : Ẽ(x) ⊂ U_{i}}. By the Subclaim (W_{0}, W_{1}) is an open covering of J and since Ẽ(x) ≠ ∅ for all x ∈ J and U_{0} ∩ U_{1} = ∅ then W_{0} ∩ W_{1} = ∅; hence J = W_{i} for some i, which proves the Claim for ξ.

To prove the Subclaim we distinguish two cases:

– If a ∉ F^{(η_{a})} then the conclusion follows from the induction hypothesis for η_{a}.

– If a ∈ F^{(η_{a})} we distinguish three cases:

– If a is a right endpoint of I then applying the induction hypothesis for η_{a} with J =]a − ε, a[ we can find i_{−} ∈ {0, 1} such that Ẽ(x) ⊂ U_{i_{−}} for all x ∈]a − ε, a[. Now pick any b ∈ E(a) ⊂ Ωf(a) = Ω^{−}f(a); we can then find some sequence (x_{j})_{j} in ]a − ε, a[∩P such that (a, b) = lim_{j}(x_{j}, f(x_{j})). Then for all j, (x_{j}, f(x_{j})) ∈ E∩U_{i_{−}}; and since E∩U_{i_{−}} is a closed subset of E then (a, b) ∈ E∩U_{i_{−}} too, hence Ẽ(a) ⊂ U_{i_{−}}. Similarly:

– If a is a left endpoint of I we can find i_{+} ∈ {0, 1} such that Ẽ(x) ⊂ U_{i_{+}} for all x ∈ [a, a + ε[.

– If a is an interior point we can find i_{−} and i_{+} in {0, 1} such that Ẽ(x) ⊂ U_{i_{−}} for all x ∈]a − ε, a] and Ẽ(x) ⊂ U_{i_{+}} for all x ∈ [a, a + ε[, hence Ẽ(a) ⊂ U_{i_{−}} ∩ U_{i_{+}}; and since Ẽ(a) is nonempty then necessarily i_{−} = i_{+} = i and Ẽ(x) ⊂ U_{i} for all x ∈]a − ε, a + ε[.

This finishes the proof of Claim 8.5. □

Then applying Claim 8.5 to J = I and ξ such that F^{(ξ)} = ∅ we get that E ⊂ U_{i} with necessarily i = 0 since U_{0} ∩ E ≠ ∅, which proves that the set E is connected. □

Proposition 8.6. If H is an hypergraph with graph part G then dim(H) = dim(\overline{G}) = 1.

Proof. Since H is connected then dim(H) ≥ 1 and we only have to prove that dim(\overline{G}) ≤ 1. So fix (a, b) ∈ \overline{G}; given any neighbourhood V of (a, b) we can find two open intervals I_{a} =]a′, a′′[ and J_{b} =]b′, b′′[ such that (a, b) ∈ W = (I_{a}×J_{b})∩\overline{G} ⊂ V. And we can impose on the endpoints a′ and a′′ to be in P = I \ Q so that A = (\{a′, a′′\}×J_{b})∩\overline{G} = \{(a′, f(a′)), (a′′, f(a′′))\} is finite. Also since the function f is nowhere constant on P the set B = (I × \{b′, b′′\}) ∩ \overline{G} is a closed subset of \overline{G} of empty interior in ℝ × {b′, b′′} hence dim B = 0. And since the boundary of W in \overline{G} is contained in A ∪ B then dim(\overline{G}) ≤ 1. □

Theorem 8.7. If H is an hypergraph and E ⊂ H is such that dim(π(E)) = 0 then dim(E) = 0.

Proof. We shall first prove the theorem under the additional assumption that E ∩ G is dense in E.

Fix (a, b) ∈ E and two intervals I_{a} =]a − ε, a + ε[ , J_{b} =]b − ε, b + ε[ for some ε > 0. We have to find a clopen neighbourhood W of (a, b) in E such that W ⊂ I_{a} × J_{b}. We distinguish the two cases:

– If a ∈ P then (a, b) ∈ G and b = f(a). Then by the continuity of f we can find two open intervals I′ , J′ such that (a, b) ∈ I′ × J′, \overline{I′ × J′} ⊂ I_{a} × J_{b} and f(P ∩I′) ⊂ J′. Since π(E) is of empty interior we can also impose on the endpoints of I′ to be in I′ \π(E) so that I′ ∩π(E) is clopen in π(E). Then W = E ∩π^{−1}(I′) is a clopen subset of E and by the choice of I′ we have W ∩ G ⊂ I′ × J′, hence by the density of G ∩ E in E we have W ⊂ \overline{W ∩ G} ⊂ \overline{I′ × J′} ⊂ I_{a} × J_{b}.

– If a ∈ Q then applying clause b) of Lemma 8.1 we can fix two continuous functions g : I \ {a} → ℝ and h : P ∪ {a} → ℝ such that f(x) = g(x) + h(x) for all x ∈ P. Since H(a) is of empty interior we can find b′, b′′ ∈ ℝ \ H(a) with b′ < b < b′′ and b′′ − b′ < \frac{ε}{2}, and an open interval I′ containing a on which the

oscillation of h is < \frac{ε}{2}; since π(E) is zero-dimensional then it is of empty interior and we can impose on the endpoints of I′ to be in I \π(E). Set Z = I′∩π(E)\{a}; since g is continuous on Z the three sets

U = {x ∈ Z : b′ − h(a) < g(x) < b′′ − h(a)}
U_{−} = {x ∈ Z : g(x) < b′ − h(a) + |x − a|}
U_{+} = {x ∈ Z : g(x) > b′′ − h(a) − |x − a|}

constitute an open covering of Z which is zero-dimensional, hence we can find in Z a clopen covering (U′, U′_{−}, U′_{+}) finer than (U, U_{−}, U_{+}).

We claim that each of the following three sets:

W = ({a}×]b′, b′′[ ∪ π^{−1}(U′)) ∩ E
W_{−} = ({a}×] − ∞, b′[ ∪ π^{−1}(U′_{−})) ∩ E
W_{+} = ({a}×]b′′, +∞, [ ∪ π^{−1}(U′_{+})) ∩ E

is open, hence clopen, in E. We detail the proof for W, the argument being similar for the other two sets. Since π^{−1}(U′) ∩ E is open in E we only need to show that any element of the form (a, y) ∈ E with y ∈]b′, b′′[ is in the interior of W. So suppose by contradiction that (a, y) = lim_{j}(x_{j}, y_{j}) with (x_{j}, y_{j}) ∈ W_{−} ∪ W_{+}. Then necessarily x_{j} ≠ a for co-finitely many j’s; so we may suppose that for all j, x_{j} ∈ U_{−} ∪ U_{+}. Since E ∩ G is dense in E we can also assume that x_{j} ∈ P hence y_{j} = f(x_{j}). Then

lim_{j} g(x_{j}) = lim_{j} f(x_{j}) − lim_{j} h(x_{j}) = y − h(a) ∈]b′ − h(a), b′′ − h(a)[

hence for large j we have:

b′ − h(a) + |x_{j} − a| ≤ g(x_{j}) ≤ b′′ − h(a) − |x_{j} − a|

which is a contradiction since x_{j} ∈ U_{−} ∪ U_{+}.

Hence W is a clopen subset of E and clearly (a, b) ∈ W. To finish the proof we have to show that W ⊂ I_{a} × J_{b}. Again by the density of G ∩ E in E it is sufficient to show W ∩ G ⊂ I_{a} × J_{b}. So let (x, y) ∈ W ∩ G then y = f(x) = g(x) + h(x) and since the oscillation of h on I′ is < \frac{ε}{2} then

b′ − \frac{ε}{2} ≤ b′ − h(a) + h(x) ≤ y ≤ b′′ − h(a) + h(x) ≤ b′′ + \frac{ε}{2}

and since b′′ − b′ < \frac{ε}{2} then |y − b| < ε so (x, y) ∈ I_{a} × J_{b}.

This finishes the proof under the additional density condition and we go back now to the general case. Starting from an arbitrary set E such that dim(π(E)) = 0 consider the closed subset E′ = \overline{E ∩ G}^{E} = \overline{E ∩ G} ∩ E of E. Then E′ ∩ G = E ∩ G and \overline{E′ ∩ G}^{E} = \overline{E ∩ G}^{E} = E′ so E′ satisfies the density condition. Hence dim(E′) = 0 and since E = E′ ∪ ⋃_{a∈Q} E ∩ ({a} × ℝ) and each E ∩ ({a} × ℝ) is a zero-dimensional closed subset of E, then dim(E) = 0. □

Corollary 8.8. Let H be an hypergraph. For any set E ⊂ H the following are equivalent:

(i) dim(E) = 0.

(ii) dim(π(E)) = 0.

Proof. Suppose that dim(E) = 0. If π(E) were not zero-dimensional then π(E) would contain a non trivial interval J hence by Theorem 8.4 the set E′ = E∩J ×ℝ would be a non trivial connected subset of E, a contradiction. The converse implication follows from Theorem 8.7. □

Corollary 8.9. For a closed subset F of an hypergraph H the following are equivalent:

(i) F is of empty interior in H.

(ii) dim(F) = 0.

(iii) dim(\overline{π(F)}) = 0.

Proof. (i) ⇒ (ii): Suppose that F is of empty interior in H. If π(F) were not zero-dimensional then π(F) would contain a nonempty open interval J. Then for all x ∈ J ∩ P, (x, f(x)) ∈ F hence F ⊃ \overline{\{(x, f(x)) : x ∈ J ∩ P \}} and it follows that F contains the nonempty open subset H ∩ (J × ℝ) of H, a contradiction.

(ii) ⇒ (iii): Observe first that by compactness \overline{π(F)} = π(\overline{F}). Also since the grah part G is a closed subset of P × ℝ then necessarily \overline{F} \ F ⊂ Q × ℝ so π(\overline{F}) \ π(F) ⊂ Q.

Suppose now that dim(F)=0. If π(\overline{F}) were not zero-dimensional then it would be of nonempty interior in ℝ hence would contain some open interval I_{0} and then I_{0} \ Q ⊂ π(F), hence F would contain the closure in H of the graph of f_{|I_{0}∩P} which is an hypergraph too, and this is impossible since F is zero-dimensional.

(iii) ⇒ (i): Suppose that dim(\overline{π(F)}) = 0. Then by Corollary 8.8 dim(F) = 0 and if F were not of empty interior then by Remark 8.3 b) F would contain an hypergraph H′, and then we would have that dim(H′) = 0 which contradicts Theorem 8.4. □

Corollary 8.10. If H is a G_{δ} hypergraph then F_{0}(H) is a G_{δ} subset of F(H).

Proof. Set R̂ = [−∞, +∞] and fix a countable basis (U_{n})_{n} of open sets in R̂. Observe that for any set A ⊂ ℝ the set \overline{A}^{ℝ} is of empty interior in ℝ if and only

if the set \overline{A}ℝ̂ is of empty interior in ℝ̂.

Embed H in the compact space R̂×R̂ and consider on F(H) the corresponding admissible topology τ̂_{0}. Then by Corollary 8.9 for F ∈ F(H) we have:

F ∈ F_{0}(H) ⟺ \overline{π(F)}^{ℝ} is of empty interior in ℝ
⟺ \overline{π(F)}ℝ̂ is of empty interior in ℝ̂
⟺ ∀n, ∃m, \overline{U_{m}}ℝ̂ ⊂ U_{n}, π(F) ∩ \overline{U_{m}}ℝ̂ = ∅
⟺ ∀n, ∃m, \overline{U_{m}}ℝ̂ ⊂ U_{n}, F ∩ π̂^{−1}(\overline{U_{m}}ℝ̂) = ∅

where π̂ denotes the projection mapping from R̂ × R̂ onto the first factor. Since

π̂^{−1}(\overline{U_{m}}ℝ̂) is compact then by 2.3 b) condition “F ∩π̂^{−1}(\overline{U_{m}}ℝ̂) = ∅” on F is open, hence F_{0}(H) is a Π_{2}^{0} subset of (F(H), τ̂_{0}).

Now if τ̂ is any admissible topology on F(H) then τ̂ is first Baire class isomorphic to τ̂_{0}, so F_{0}(H) is a Π_{3}^{0} subset of (F(H), τ̂), hence by Corollary 4.4 F_{0}(H) is actually a Π_{2}^{0} subset of (F(H), τ̂). □

Corollary 8.11. Any compact subset of an hypergraph is of empty interior hence zero-dimensional.

Proof. Let K be a compact subset of H and suppose that U ×V is an open subset of ℝ^{2} such that ∅ ≠ (U × V) ∩ H ⊂ K. Pick any element a ∈ U ∩ Q; since \overline{G}(a) is a non trivial interval we can also pick some element b ∈ V ∩ \overline{G}(a) \ H(a), so (a, b) ∈ (\overline{G} \ H) ∩ (U × V). We can then find (a_{j}, b_{j}) ∈ G ∩ (U × V) such that (a, b) = lim_{j}(a_{j}, b_{j}); and since G is a graph then H(a_{j}) = K(a_{j}) = {b_{j}} hence (a_{j}, b_{j}) ∈ K and so (a, b) ∈ K ⊂ H, which is a contradiction.

Hence K is closed and of empty interior and the last part of the conclusion follows then from Corollary 8.9. □

Corollary 8.12. An hypergraph is a connected space which contains no non trivial continuum.

Observe that an hypergraph H cannot be decomposable into a countable union of closed zero-dimensional or compact subsets since by Corollary 8.11 it would be a countable union of closed zero-dimensional subsets hence by Theorem 2.5 H itself would be zero-dimensional which contradicts Proposition 8.6.

9. The maximum descriptive class of F_{0}(X) when X is Polish

We can now prove the following complement to Corollary 7.5

Theorem 9.1. For any G_{δ} hypergraph H there exists a Π_{2}^{0} subset X of 2^{ω} × H such that F_{0}(X) is ⅁Σ_{2}^{0}-hard.

Proof. We check that H and its graph part G satisfy all the assumptions of Theorem 7.3 for ξ = 2: By Proposition 8.6 dim(H) = 1 and it is easily seen as in Remark 8.3 c) that if W is a nonempty open subset of H and if a σ-compact set T = ⋃_{n} F_{n} (with T_{n} compact) contains G ∩ W then some F_{n} contains the whole interval \overline{G}(x) for some x ∈ Q ∩ W hence T meets ℝ^{2} \ H. Thus G ∩ W is not relatively σ-compact in H. Finally observe that if D ⊂ G then π(D)∩π(H\D) = ∅ hence if D is dense in G then π(D) is dense in π(H) hence π(H \ D) is of empty interior in π(H), so dim(π(H \ D)) = 0 and by Theorem 8.7 dim(H \ D) = 0. □

9.2. Back to games: For the next result we need to consider games in which one of the Players, namely Player II, is required to make his moves in {0, 1}. Thus if γ = (n_{0}, n_{1}, n_{2} ⋯) ∈ ω^{ω} is any infinite run in such a game then n_{2k+1} ∈ {0, 1}. The main advantage of this variation is that in this case the space Σ_{II}^{∗} of all strategies for Player II is now compact: Σ_{II}^{∗} = {0, 1}^{(ω^{<ω}\{∅})} ≈ 2^{ω} , while for Player I the situation is unchanged: Σ_{I}^{∗} = ω^{(2^{<ω})} ≈ ω^{ω}. The basic observation is that any Σ_{2}^{0} game on ω can be reduced (in a precise sense) to a Σ_{2}^{0} game of the previous form. To state this properly let us introduce a notation. Let ⋆ denote the operation on ω^{ω} defined by:

α ⋆ β(n) = \{ \begin{matrix}α(k) & if n = 2k \\ β(k) & if n = 2k + 1 \end{matrix}

Then the mapping (α, β) ↦ α ⋆ β is clearly a homeomorphism from ω^{ω} × ω^{ω} onto ω^{ω}. Notice that if we view α and β as two (trivial) strategies for Player I and Player II respectively then α ⋆ β is just the infinite run obtained by the ⋆ operation introduced in 7.1.a.

Set:

ω^{ω} ⋆ 2^{ω} = {α ⋆ β : (α, β) ∈ ω^{ω} × 2^{ω}}
= {γ ∈ ω^{ω} : ∀k, γ(2k + 1) ∈ {0, 1} }

We need the following variation of Lemma 7.2. It is worth noting that the situation is not symmetrical and one cannot replace in this statement Σ_{2}^{0} by Π_{2}^{0}, equivalently Player I by Player II, while any Borel game of rank ξ ≥ 3 on ω can be reduced to a game where both Players’ moves are in {0, 1}.

Lemma 9.3. There exists a Σ_{2}^{0} set V ⊂ 2^{ω} × (ω^{ω} ⋆ 2^{ω}) such that the set ⅁V is ⅁Σ_{2}^{0}-complete.

Proof. Given any ε ∈ 2^{<ω} ∪ 2^{ω} let ν = Ψ(ε) ∈ ω^{<ω} ∪ ω^{ω} be the increasing enumeration of the set N = {j < |ε| : ε(j) = 1} and let β = Φ(ε) ∈ ω^{|ν|} be defined by: β(0) = ν(0) and β(k + 1) = ν(k + 1) − ν(k) − 1. Observe that |Ψ(ε)| = |Φ(ε)| ≤ |ε|.

The mapping Φ thus defined is clearly one-to-one on the set P ∪ Q where P = {ε ∈ 2^{ω} : ∀j, ∃k > j, ε(k) = 1} and Q = {ε ∈ 2^{<ω} : ε(|ε| − 1) = 1} with Φ(P) = ω^{ω} and Φ(Q) = ω^{<ω}; and we shall denote by Φ_{∗} : 2^{<ω} ∪ 2^{ω} → Q ∪ P its inverse. Moreover the mapping Φ_{|P} : P → ω^{ω} is a homeomorphism.

Then to any set A ⊂ ω^{ω} we associate a set A^{∗} ⊂ ω^{ω} ⋆ 2^{ω} defined as follows: an element α ⋆ ε ∈ ω^{ω} ⋆ 2^{ω} belongs to A^{∗} if:

– either |Ψ(ε)| = |Φ(ε)| < ∞

– or |Ψ(ε)| = |Φ(ε)| = ∞ and if ν = Ψ(ε) and β = Φ(ε) then (α ∘ ν) ⋆ β ∈ A

Claim 9.4. Player I wins the game G_{A} if and only if he wins the game G_{A^{∗}}.

Proof. – If Player I has a winning strategy σ in G_{A} he constructs a strategy σ^{∗} in G_{A^{∗}} by playing as follows: If in an infinite run in G_{A^{∗}} in which Player II plays some ε ∈ 2^{ω}, then following σ^{∗} Player I plays α ∈ ω^{ω} defined inductively by: α(0) = σ(∅) and for k > 0:

α(k) = \{ \begin{matrix}σ(Φ(ε_{|k})) & if ε(k − 1) = 1 \\ 0 & if not \end{matrix}

If ε ∉ P then by definition of A^{∗} Player I wins the run. Otherwise ε ∈ P and if ν = Ψ(ε) and β = Φ(ε) then from the definition of σ^{∗} we have α ∘ ν = σ(β) and since σ is winning in G_{A} then (α ∘ ν) ⋆ β ∈ A so by definition of A^{∗}, α ⋆ ε ∈ A^{∗}, hence σ^{∗} is winning in G_{A^{∗}}.

– Conversely if Player I has a winning strategy σ^{∗} in G_{A^{∗}} he constructs a strategy σ in G_{A} by playing as follows: In an infinite run in G_{A} in which Player II plays some β ∈ ω^{ω} then following σ Player I plays α ∈ ω^{ω} defined for all k by: α(k) = σ^{∗}(Φ_{∗}(β_{|j_{k}})) where (j_{k}) = Ψ(Φ_{∗}(β)) is the enumeration of the set {j : ε(j) = 1} for ε = Φ_{∗}(β). Notice that β_{|j_{k}} ∈ Q hence σ is well defined. Moreover if α′ = σ^{∗}(ε) then α = α′ ∘ ν and since σ^{∗} is winning in G_{A^{∗}} then by definition of A^{∗} we have α ⋆ β ∈ A, hence σ is winning in G_{A}. □

Let U ⊂ 2^{ω} × ω^{ω} and V ⊂ 2^{ω} × (ω^{ω} ⋆ 2^{ω}) defined by V (δ) = (U(δ))^{∗} for all δ ∈ 2^{ω}.

Claim 9.5. If U is a Σ_{2}^{0} set then V is a Σ_{2}^{0} set too.

Proof. Observe that for any set A ⊂ ω^{ω} ⋆ 2^{ω} and any γ = (α ⋆ ε) ∈ ω^{ω} ⋆ 2^{ω} we have

γ ∉ A^{∗} ⟺ ε ∈ P ∧ α ⋆ Φ(ε) ∉ A

hence for any δ ∈ 2^{ω}:

(δ, γ) ∉ V ⟺ ε ∈ P ∧ (δ, α ⋆ Φ(ε)) ∉ U

So letting π : 2^{ω} × ω^{ω} → ω^{ω} and ρ : 2^{ω} × P → 2^{ω} × ω^{ω} denote the mappings defined by:

π(δ, γ) = ε and ρ(δ, γ) = (δ, α ⋆ Φ(ε))

we have

2^{ω} × (ω^{ω} ⋆ 2^{ω}) \ V = π^{−1}(P) ∩ ρ^{−1}(2^{ω} × ω^{ω} \ U)

and since the mappings π and ρ are continuous and P is a G_{δ} set it follows that 2^{ω} × (ω^{ω} ⋆ 2^{ω}) \ V is a G_{δ} subset, hence V is a Σ_{2}^{0} subset, of 2^{ω} × (ω^{ω} ⋆ 2^{ω}). □

To finish the proof of Lemma 9.3 let U ⊂ 2^{ω} × ω^{ω} be a Σ_{2}^{0}-complete set given by Lemma 7.2 and consider the set V ⊂ 2^{ω} × (ω^{ω} ⋆ 2^{ω}) as above. By Claim 9.5 V is a Σ_{2}^{0} set hence ⅁V is ⅁Σ_{2}^{0} set and we now check that the set ⅁V is ⅁Σ_{2}^{0}-hard.

So let A ⊂ 2^{ω} be any ⅁Σ_{2}^{0} set. By Lemma 9.3 there exists a continuous mapping φ : 2^{ω} → 2^{ω} which reduces the set A to ⅁U, hence by Claim 9.4 we have:

ε ∈ A ⟺ φ(ε) ∈ ⅁U ⟺ Player I wins G_{(⅁U)(φ(ε))}
⟺ Player I wins G_{((⅁U)(φ(ε)))^{∗}} = G_{V (φ(ε))} ⟺ φ(ε) ∈ ⅁V

which proves that φ reduces the set A to ⅁V. □

We recall that it is not known whether the set F_{0}(𝕀^{2} \ ℚ^{2}) is Π_{1}^{1}.

Theorem 9.6. F_{0}(𝕀^{5} \ ℚ^{5}) is ⅁Σ_{2}^{0}-hard.

Proof. We shall actually construct a space Y for which the set F_{0}(Y) is ⅁Σ_{2}^{0}-hard and which can be embedded as a closed subset in 𝕀^{5} \ℚ^{5}. It will follow that F_{0}(Y) is a closed subset of F_{0}(𝕀^{5} \ ℚ^{5}) hence F_{0}(𝕀^{5} \ ℚ^{5}) is ⅁Σ_{2}^{0}-hard too.

The definition of the space Y follows the same general scheme of definition as for the spaces X_{U} constructed in the proof of Theorem 7.3 and will be of the form:

Y = {(α, τ, z) ∈ 2^{ω} × Σ_{II}^{∗} × H : ∀n, z ∈ F_{n} → (α, h_{n}(z) ⋆ τ) ∉ V }

where V is the set given by Lemma 9.3, H is a specific hypergraph that we will construct, the set Σ_{II}^{∗} ≈ ω^{ω} of strategies replaces the previous set Σ_{II}, and for all n, h_{n} : F_{n} → Σ_{I}^{∗} is a homeomorphism defined on a closed subset F_{n} of H which will replace the Π_{2}^{0} set G_{n} of the proof of Theorem 7.3.

Since the Σ_{2}^{0} set V satisfies also Lemma 7.2 we can apply Claim 7.4 to conclude as in Theorem 7.3 that F_{0}(Y) is ⅁Σ_{2}^{0}-hard. Moreover since the F_{n}’s are closed subsets of H the immediate analysis of the previous definition shows that X is indeed a Π_{2}^{0} set.

Our plan is to show that for a suitable choice of H and the F_{n}’s the space Y above can be embedded as a closed subset in 𝕀^{5} \ ℚ^{5}. We point out that unlike in the proof of Theorem 7.3 where the G_{n}’s were constructed for a given space H in the present case we will have to construct H and the F′_{n}s simultaneously, which will be done in a series of steps.

We recall that the notation \overline{A} for a subset of H refers to the closure in ℝ^{2}.

Lemma 9.7. In any hypergraph H with graph part G there exists a closed subset F of G satisfying: F ≈ ω^{ω}, \overline{F} ≈ 2^{ω}, and for all q ∈ Q , card (\overline{F} (q)) ≤ 1.

Proof. Observe first that given any q ∈ Q then by Definition 8.2 we can write f = g + h with h : P ∪ {q} → ℝ continuous and g : I \ {q} → ℝ continuous and such that Ωg(q) = \overline{G}(q) is a non trivial interval. Then for any cluster value ℓ ∈ Ωg(q) and any neighbourhood J of q one can find an infinite sequence (J_{n})_{n} of pairwise disjoint closed non trivial intervals in J \ {q} with endpoints in P and of arbitrary small diameter such that lim_{n} d(q, I_{n}) = 0 and the function g_{| ⋃_{n} I_{n}} has limit ℓ at q; and since h is continuous on P ∪ {q} then f_{|P ∩⋃_{n} I_{n}} has a limit (namely ℓ + h(q)) at q.

Fix an enumeration (q_{n})_{n∈ω} of Q; we shall construct a family (r_{s}, J_{s})_{s∈ω^{<ω}} satisfying for all s:

(i) J_{s} a closed non trivial interval with endpoints in P, (ii) diam(J_{s}) ≤ 2^{−|s|}, (iii) J_{s^{⌢}n} ⊂ J_{s} and J_{s^{⌢}m} ∩ J_{s^{⌢}n} = ∅ if m ≠ n, (iv) r_{s} ∈ J_{s} ∩ Q,

(v) if |s| = k and q_{k} ∈ J_{s} then r_{s} = q_{k}, (vi) r_{s} ∉ J_{s^{⌢}n} for all n and lim_{n} d(r_{s}, J_{s^{⌢}n}) = 0, (vii) f_{|P ∩⋃_{n} J_{s^{⌢}n}} has a limit at r_{s}. Take for J_{∅} any open interval with endpoints in P. Suppose that the family

(J_{s})_{s∈ω^{k}} is constructed we shall define for each s ∈ ω^{k}, the element r_{s} and the family (J_{s^{⌢}n})_{n∈ω}.

First if q_{k} ∈ J_{s} then we define r_{s} = q_{k}; if not we choose r_{s} arbitrarily in J_{s} ∩ Q so conditions (iv) and (v) are satisfied. Once q = r_{s} ∈ J_{s} is chosen, observe that since J_{s} has endpoints in P then q is necessarily in the interior of J_{s}, and following the previous observations, we can find a family (J_{s^{⌢}n})_{n∈ω} satisfying the remaining conditions. Let

F^{∗} = ⋂_{k} ⋃_{s∈ω^{k}} J_{s} and K = \overline{F^{∗}}

Claim 9.8. : For any z ∈ K there exists a unique maximal sequence σ = (s_{j}) in ω^{<ω} such that: z ∈ J_{s_{j}}, |s_{j}| = j and s_{j} ⊂ s_{j+1}. Then:

– if σ is finite with last element s then z ∈ Q and z = r_{s}

– if σ is infinite then z ∈ P and {z} = ⋂_{j} J_{s_{j}}

Proof. The construction is by induction on j. For j = 0 then necessarily s_{0} = ∅ which is legal since z ∈ \overline{F^{∗}} ⊂ J_{∅}. Suppose that s_{j} is already defined then again since z ∈ K ⊂ {r_{s_{j}}} ∪ ⋃_{n} J_{s_{j}^{⌢}n} then:

– either z = r_{s_{j}} and then |s_{j}| = j and z = q_{j} and in this case σ = (s_{i})_{i≤j} is maximal since z ∉ J_{s} for any s ⊃ s_{j} with |s| = j + 1

– or z ∈ J_{s_{j}^{⌢}n} for some unique n and so necessarily s_{j+1} = s_{j}^{⌢}n. This finishes the construction of σ and:

– either σ is finite and z = r_{s} where s is last element of σ

– or σ is infinite and {z} = ⋂_{j} J_{s_{j}} and we have to show that z ∈ P. If not then we would have z = q_{k} for some k hence q_{k} ∈ J_{s_{k}} with r_{s_{k}} ≠ q_{k} which is in contradiction with condition (v). □

This defines a mapping h : K → ω^{<ω} ∪ ω^{ω} ≈ P(ω) ≈ 2^{ω} which is clearly a homeomorphism such that F^{∗} = h^{−1}(ω^{ω}) = K ∩ P ≈ ω^{ω} and K \ F^{∗} = h^{−1}(ω^{<ω}) = K ∩ Q = {r_{s} : s ∈ ω^{<ω}}; hence F^{∗} is a closed subset of P. Finally set F = π^{−1}(F^{∗}): since π is a homeomorphism from G onto P then ω^{ω} ≈ F^{∗} ≈ F and F is a closed subset of G; and since by condition (vii) f_{|F^{∗}} admits a continuous extension g : K → ℝ then \overline{F} = Gr(g) hence for all q ∈ Q, \overline{F} (q) is either \{g(q)\} if q = r_{s} ∈ K, or else empty. □

Lemma 9.9. There exists an hypergraph H with graph part G and a sequence (F_{n}) of subsets of H satisfying:

a) \overline{H} \ H is countable,

b) any nonempty open subset of H contains some F_{n}.

c) for all n, F_{n} ≈ ω^{ω} , \overline{F}_{n} ≈ 2^{ω} and F_{n} = \overline{F}_{n} ∩ H ⊂ G

Proof. Start from an hypergraph H′ with graph part G which is co-countable in \overline{G} (see Remark 8.3.c) and let (W_{n})_{n} be a basis of the topology of H′ with for all n, W_{n} = H′ ∩ (I_{n} × J_{n}) ≠ ∅ for some intervals I_{n}, J_{n}. Then applying Lemma 9.7 to each hypergraph H_{n} = H′ ∩ W_{n} with graph part G_{n} = G ∩ W_{n}, we can find a closed subset F_{n} of G_{n} ∩ W_{n} such that for all q ∈ Q, \overline{F}_{n}(q) is contained in some singleton {q^{(n)}}. Let

H = H′ \ {(q, q^{(n)}) : q ∈ Q and n ∈ ω}

then \overline{G} \ H = (\overline{G} \ H′) ∪ (H′ \ H) is countable hence \overline{H} = \overline{G} and \overline{H} \ H is countable. In particular for all q ∈ Q, \overline{G}(q) \ H(q) is countable, so H(q) is dense in \overline{G}(q), and since H(q) ⊂ H′(q) then H(q) is of empty interior in \overline{G}(q). Hence H is an hypergraph with same graph part G. Finally for all n ∈ ω and all q ∈ Q, (\{q\} × \overline{F}_{n}(q)) ∩ H = ∅, hence \overline{F}_{n} ∩ H ⊂ G and since F_{n} is a closed subset of G then F_{n} = \overline{F}_{n} ∩ G = \overline{F}_{n} ∩ H. □

Lemma 9.10. Let H and (F_{n}) be as in Lemma 9.9, let V be an arbitrary Σ_{2}^{0} subset of ω^{ω} and for all n, let Φ_{n} : 2^{ω} × 2^{ω} × F_{n} → ω^{ω} be a continuous mapping. Then the space:

X = {(α, β, z) ∈ 2^{ω} × 2^{ω} × H : ∀n, z ∈ F_{n} → Φ_{n}(α, β, z) ∉ V }

can be embedded as a closed subset in 𝕀^{5} \ ℚ^{5}.

Proof. Since V is a Σ_{2}^{0} set and the F_{n}’s are closed subsets of H then X is clearly a Π_{2}^{0} subset of the compact space K = 2^{ω}×2^{ω}×\overline{H}. Observe that if (α, β, z) ∈ K\X then either z ∈ D = \overline{H} \ H which is countable, or z ∈ F_{n} ⊂ \overline{F}_{n} ≈ 2^{ω} for some n. Hence

K \ X ⊂ ⋃_{z∈D, n∈ω} 2^{ω} × 2^{ω} × (\{z\} ∪ \overline{F}_{n})

Since for all z ∈ D and all n, the set 2^{ω} × 2^{ω} × (\{z\} ∪ \overline{F}_{n}) is a zero-dimensional compact space then by Theorem 2.5 dim(K \ X) = 0, and we can write the σcompact space K \X as the union of a countable family (K_{j})_{j} of pairwise disjoint compact sets: K \ X = ⋃_{j} K_{j} with lim_{j} diam(K_{j}) = 0. Hence if Δ denotes the diagonal of K then E = Δ ∪ ⋃_{j} K_{j} × K_{j} is a closed equivalence relation on K. Let L be the quotient (compact) space K/E and ρ : K → L be the canonical quotient mapping. Since the restriction of ρ to X is a one-to-one perfect mapping on its image Y = ρ(X) then it is a homeomorphism from X onto Y; moreover the set L \ Y is countable as the collection of the E-equivalence classes K_{j}.

Note that by Proposition 8.6, dim(Y) = dim(X) ≤ dim(K) = dim(\overline{G}) = 1, and since L\Y is countable then by Theorem 2.5, dim(L) ≤ 2, hence the compact space L can be embedded in ℝ^{5}.

Fix now a homeomorphism h_{0} : L → L_{0} ⊂ ℝ^{5}; then D_{0} = (ℚ^{5} \ L_{0}) ∪ h_{0}(L \ Y) is a countable dense subset of ℝ^{5}, and since ℝ^{5} is a CDH space ([2]) then there exists a homeomorphism h_{1} : ℝ^{5} → ℝ^{5} such that h_{1}(D_{0}) = ℚ^{5} and we can assume that the compact space L_{1} = h_{1}(L_{0}) is a subset of 𝕀^{5}. Hence h = h_{1}∘h_{0}∘ρ induces a homeomorphism from X onto L_{1} \ ℚ^{5} = L_{1} ∩ (𝕀^{5} \ ℚ^{5}) which is a closed subset of 𝕀^{5} \ ℚ^{5}. □

\underline{End of the proof of Theorem 9.6}: Starting from H and (F_{n}) as in Lemma 9.9 we fix for all n, an arbitrary homeomorphism h_{n} : F_{n} → Σ_{I}^{∗} ≈ ω^{ω}. It is clear then that the space Y defined at the beginning of the proof is of the form considered in Lemma 9.10. Hence Y can be embedded as a closed subset in 𝕀^{5} \ ℚ^{5} and since F_{0}(Y) is ⅁Σ_{2}^{0}-hard then F_{0}(𝕀^{5} \ ℚ^{5}) is ⅁Σ_{2}^{0}-hard too. □

References

1. T. Banach, R. Cauty, M. Zarichnyi, Open problems in infinite-dimensional topology, in: Problems in Topology II, edited by E. Pearl, Elsevier (2007).

2. R. Bennet, Countable dense homogeneous spaces, Fund. Math 74 (1972), 189–194

3. J. Burgess, Classical hierarchies from a modern standpoint. I. C-sets., Fund. Math. 115 no. 2, (1983), 81–95.

4. J. Burgess, Classical hierarchies from a modern standpoint. II. R-sets., Fund. Math. 115, no. 2, (1983), 97–105.

5. P. Erdős, The dimension of the rational points in Hilbert space, Ann. Math., 2e serie, 41, (1940), 734–736

6. A. Kechris, Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995.

7. A. Kechris, A. Louveau, H. Woodin, The structure of σ-ideals of compact sets, Trans. Amer. Math. Soc. 301 (1987), no. 1, 263–288.

8. K. Kuratowski and W. Sierpinski, Les fonctions de classe 1 et les ensembles connexes punctiformes, Fund. Math. 3 (1922), 303–313.

9. A. Louveau, circulated notes.

10. Y. N. Moschovakis, Descriptive Set Theory, Studies in logic 100 North-Holland, Amesterdam (1979); second edition: Mathematical surveys and monographs 155, Amer. Math. Soc. Providence, Rhode Island (2009)

11. E. Pol and R. Pol, Isometric embeddings and continuous maps onto the irrationals, arXiv:1706.04396v1.

12. J. Saint Raymond, Cofinal trees and analytic inductions, Fund. Math., 191 (2006) , 175–185