Borel sets in P<sub>ω</sub>: 1

A Tang

► To cite this version:

A Tang. Borel sets in P<sub>ω</sub>: 1. [Research Report] IRIA-RR-137, IRIA. 1975, pp.58. hal-04716072

HAL Id: hal-04716072

https://inria.hal.science/hal-04716072v1

Submitted on 1 Oct 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

Borel sets in P<sub>ω</sub> :1

A. Tang

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°137

Octobre 1975
BOREL SETS IN P<sub>ω</sub> : I

A. Tang

IRIA/LABORIA

**Résumé** : Nous étudions la structure des ensembles $B_\delta$ dans P_ω qui contiennent des rétractés calculables de P_ω .

**Abstract** : We study the structure of $B_\delta$ sets in Pω which include all the computable retracts of Pω .

<figure><img src="image_3.png" /></figure>
# Borel sets in Pw : I

A. Tang

IRIA-Laboria

78150 Rocquencourt, France

## 0 : Introduction

While descriptive set theory has been studied in Hausdorff spaces, we shall be here studying descriptive set theory in a non-Hausdorff space, namely, Pw (power set of w). Pw is the space of all subsets of w where the open sets are generated by the following sub-base : the class of { x ⊂ w | n ∈ x } where n ∈ w. Pw is introduced in [4] as a model of Lambda-calculus. In [5], we studied Scott's notion of effectively given data types and showed that all effectively given data types are computable retracts of Pw. The retracts of Pw are a subclass of the $B_δ$ sets which are Borel sets in Pw. The focus of this paper is on the class of $B_δ$ sets in Pw as well as their complements, the $B_σ$ sets.

Cantor space (abbreviated as $2^ω$) and Pw have the same elements, but the topology of $2^ω$ is generated by a relatively larger sub-base, namely, the class of { x ⊂ w | n ∈ x } and { x ⊂ w | n ∉ x } where n ∈ w. Thus the open sets in $2^ω$ can be specified by positive or negative information, whereas the open sets in Pw are strictly specified by positive information. The Borel sets in $2^ω$ and Pw turn out to be the same.

Section 1 provides us the background material for our studies. We define the Borel hierarchy $\{B_α(Pw)\}_{α<Ω}$ in Pw and examine its relation with the
classical Borel hierarchy {$F_α(2^ω)}_{α<Ω}$ in $2^ω$. {$B_α(Pω)}_{α<Ω}$ essentially starts a stage slower than {$F_α(2^ω)}_{α<Ω}$, but ultimately the two hierarchies generate the same class of sets.

The main part of Section 2 is devoted to the class of $B_σ∩B_δ$ sets in $Pω$, the subsets in $Pω$ which are both $B_σ$ and $B_δ$. We prove the following characterization of $B_σ∩B_δ$ sets : A is a $B_σ∩B_δ$ set in $Pω$ if and only if A and its complement $A^C$ are closed under chain.

In Section 3, we study Wadge's notion of reducibility among subsets of $Pω$. Let $p$ be the following map from $ω^ω$ (Baire space) to $Pω$ : for $α∈ω^ω$, $p(α) = \{ n∈ω | (∃m∈ω)(α(m)=n+1) \}$. For subsets A, E of $Pω$, define A to be Wadge reducible to E in $Pω$ if and only if $p^{-1}(A)$ is Wadge reducible to $p^{-1}(E)$ in Baire space. We show that A is a $B_σ∩B_δ$ set in $Pω$ if and only if $p^{-1}(A)$ is a $F_σ∩G_δ$ set in Baire space.

In Section 4, we study enumeration reducibility which is stronger than Wadge reducibility. In this reducibility, we can have a pair of Borel sets A, E in $Pω$ such that the sets A, $A^C$, E and $E^C$ are all pairwise incomparable in their degrees. The structure of enumeration degrees of the $B_δ$ sets is studied in a later paper.
## Notations

(a) Suppose $\mathcal{X}$ is a topological space and A, E are arbitrary classes of subsets in $\mathcal{X}$, then:

(1) a $A(\mathcal{X})$ set is a set in A, and a $\hat{A}(\mathcal{X})$ is a set whose complement is in A;

(2) a $F(\mathcal{X})$ set is a closed set in $\mathcal{X}$, and a $G(\mathcal{X})$ set is an open set in $\mathcal{X}$;

(3) a $A_\sigma(\mathcal{X})$ set is a countable union of sets in A, and a $A_\delta(\mathcal{X})$ set is a countable intersection of sets in A;

(4) a $A \in E(\mathcal{X})$ set is a set which belongs to either A or E, and a $A \notin E(\mathcal{X})$ set is a set which belongs to both A and E;

(5) a $A \in \mathcal{E}(\mathcal{X})$ set is a union of a $A(\mathcal{X})$ set and a $E(\mathcal{X})$ set, and a $A \notin \mathcal{E}(\mathcal{X})$ set is an intersection of a $A(\mathcal{X})$ set and a $E(\mathcal{X})$ set;

(6) a $A \notin E(\mathcal{X})$ set is a $A(\mathcal{X})$ set but not a $E(\mathcal{X})$ set.

(b) Suppose $\mathcal{X}$ is a topological space and A is any subset of $\mathcal{X}$ . Then $A^c$ stands for the complement of A in $\mathcal{X}$, and $Cl(A)$ stands for the closure of A in $\mathcal{X}$.

(c) Suppose $\mathcal{X}$ and $\mathcal{Y}$ are topological spaces, $[\mathcal{X} \to \mathcal{Y}]$ stands for the space of all continuous functions from $\mathcal{X}$ to $\mathcal{Y}$ endowed with the product topology

(d) $\emptyset$ designates the end of a proof.

(e) $\iff$ stands for 'if and only if', and $\Rightarrow$ stands for 'implies'.
# 1 : Borel hierarchy in P<sub>ω</sub>

## 1.1 : P<sub>ω</sub> and its topology

The topology of P<sub>ω</sub>, apart from the one given in the introduction, can also be specified as follows : a subset E of P<sub>ω</sub> is open if (a) whenever x belongs to E and x∈y, then y belongs to E, and (b) whenever x belongs to E, then some finite subset of x is in E. We consider some examples of open sets in P<sub>ω</sub>.

(i) Given y∈ω, let U<sub>y</sub> be the set { x∈ω | y∈x }. When y is a finite subset of ω, U<sub>y</sub> satisfies conditions (a) and (b) above, hence U<sub>y</sub> is an open set in P<sub>ω</sub>. When y is an infinite subset of ω, U<sub>y</sub> is not an open set because it violates condition (b) — U<sub>y</sub> doesn't contain any finite subset of ω.

(ii) Given y∈ω, let W<sub>y</sub> be the set { x∈ω | x∈y }, i.e. the set of all subsets of y. The complement of W<sub>y</sub> can be verified to be an open set in P<sub>ω</sub>, hence W<sub>y</sub> is a closed set.

(iii) Say that a subset E of P<sub>ω</sub> is closed under superset if whenever x belongs to E and x⊆y, then y belongs to E. Thus condition (a) in the above specification of the topology of P<sub>ω</sub> says that the open sets in P<sub>ω</sub> are closed under superset. Consider the set A = { x∈ω | 3<x } . By (i) above, A is a closed set in P<sub>ω</sub>. A is not an open set in P<sub>ω</sub> because it is not closed under superset.

Similarly, we can define the notion of 'closed under subset' as follows : E⊆P<sub>ω</sub> is closed under subset if whenever x belongs to E and y⊆x, then y belongs to E. The closed sets in P<sub>ω</sub> are all closed under subset.
As the open sets in $P\omega$ are closed under superset, every non-empty open set in $P\omega$ contains the element $\omega$. Similarly, every non-empty closed set in $P\omega$ contains the element $\emptyset$ (null-set of $\omega$). From this observation, we can infer:

(i) The only clopen sets in $P\omega$ are $\emptyset$ (null-set of the space $P\omega$) and the set $P\omega$; and

(ii) Every pair of non-empty open sets in $P\omega$ has a non-empty intersection. Hence $P\omega$ is not a Hausdorff space. A further consequence is that $P\omega$ is not metrizable because metric spaces are always Hausdorff.

Unlike $P\omega$, $2^\omega$ is a metric space. Besides, the sets in the sub-base of $2^\omega$ given in the introduction are all clopen sets in $2^\omega$. $P\omega$ and $2^\omega$ do have the following similarity: they are both compact spaces. In fact, $P\omega$ is 'supercompact' in the sense that given any open cover of $P\omega$, some set in the cover is the entire set, i.e. $P\omega$. To see this, observe that in the given open cover of $P\omega$, some set has to cover (or contain) the element $\emptyset$ — this set must be $P\omega$ because $P\omega$ is the only open set in the space $P\omega$ containing the element $\emptyset$.

A $T_0$ space is a space where the elements are uniquely determined by their neighborhoods — in other words, two elements in the space are the same if and only if they have the same neighborhood. The topology of $P\omega$ turns $P\omega$ to a $T_0$ space. As a $T_0$ space, $P\omega$ has the following universal property:

**Proposition 1.1.1**

Every separable $T_0$ space can be embedded in $P\omega$.

*Proof:* Suppose $T$ is a $T_0$ space with a countable base $\{U_n\}_{n\in\omega}$. Define the map $\Phi: T \to P\omega$ as follows: for $x$ in $T$, $\Phi(x) = \{n\in\omega | x\in U_n\}$.
Φ is a 1-1 map because the elements in $T$ are uniquely determined by their neighborhoods. Now observe that for $n$ in $ω$, $n$ belongs to $Φ(x)$ if and only if $x$ belongs to $U_n$. From this observation, we can deduce that $Φ$ is a continuous as well as open map. Hence $Φ$ embeds $T$ in $Pω$. □

Among the consequences of Proposition 1.1.1, we have:

(i) $2^ω$ and $ω^ω$ are both subspaces of $Pω$ because they are separable $T_0$ spaces. Is $Pω$ a subspace of $2^ω$? — no, because all subspaces of a Hausdorff space are necessarily Hausdorff; and

(ii) The function space $[Pω \to Pω]$ is a separable $T_0$ space, hence it is a subspace of $Pω$.

Finally, we point out that there are at least two ways to look at $Pω$. The first way is to treat $Pω$ as a function space, namely, $\mathcal{O}^ω$ — the space of all functions from $ω$ to Sierpinski space $\mathcal{O}$ with the product topology. The second way is to treat $Pω$ as a lattice with the following partial ordering: $x \subset y$ if and only if $x$ is a subset of $y$. Under this partial ordering, $Pω$ is a complete lattice where the 'top' element is $ω$ and the 'bottom' element is $\emptyset$.
1.2 : Borel hierarchy {$F_α(Pω)}_{α<Ω}$

Although the open sets in Pw form a proper subclass of the open sets in $2^ω$, the Borel sets in both spaces turn out to be the same. To establish the latter fact, we need to know how the Borel sets in Pw are generated.

The classical Borel hierarchy {$F_α(2^ω)}_{α<Ω}$ (where Ω is the first uncountable ordinal) in $2^ω$ is defined as follows:

(i) $F_0(2^ω)$ is the family of closed sets in $2^ω$; and for $α<Ω$,

(ii) the sets of the family $F_α(2^ω)$ are countable intersections or unions of sets belonging to $F_ξ(2^ω)$ with $ξ<α$ according to whether $α$ is even or odd (limit ordinals are understood to be even).

As the open sets in $2^ω$ form a subclass of the $F_σ(2^ω)$ sets (or the $F_Ι(2^ω)$ sets), the sets in {$F_α(2^ω)}_{α<Ω}$ are closed under complement and consequently constitute all the Borel sets in $2^ω$.

Unfortunately, the open sets in Pw do not form a subclass of the $F_σ(Pw)$ sets. In fact, the only open sets in Pw which are in $F_σ(Pw)$ are $\emptyset$ and Pw. Now suppose we define {$F_α(Pw)}_{α<Ω}$ as follows:

(i) $F_0(Pw)$ is the family of closed sets in Pw; and for $α<Ω$,

(ii) the sets of the family $F_α(Pw)$ are countable intersections or unions of sets belonging to $F_ξ(Pw)$ with $ξ<α$ according to whether $α$ is even or odd.

It is not difficult to verify that the sets in {$F_α(Pw)}_{α<Ω}$ form only a proper subclass of the Borel sets in Pw. For example, the open set $U_{\{1\}}$ is not contained in {$F_α(Pw)}_{α<Ω}$ because while it can be verified that all the sets in {$F_α(Pw)}_{α<Ω}$ are closed under subset, $U_{\{1\}}$ is clearly not closed under subset. A different method to 'generate the Borel sets in Pw is therefore needed.
We define a hierarchy ${B_α(Pω)}_{α<Ω}$ of subsets in Pω as follows :

(i) $B_0(P\omega)$ is the Boolean closure of the open sets in Pω, i.e. the smallest Boolean algebra containing all the open sets in Pω; and for $α<Ω$,

(ii) the sets of the family $B_α(Pω)$ are countable intersections or unions of sets belonging to $B_ξ(Pω)$ with $ξ<α$ according to whether $α$ is even or odd.

To facilitate understanding of the sets in ${B_α(Pω)}_{α<Ω}$, we prove the following lemma :

**Lemma 1.2.1**

(a) $B_0(P\omega)$ is the family of all finite unions of $F^nG(P\omega)$ sets.

(b) $B_1(P\omega)$ is the family of all countable unions of $F^nG(P\omega)$ sets.

(c) $B_0(P\omega) \subset \hat{B}_1(P\omega)$

**Proof** : Clearly all finite unions of $F^nG(P\omega)$ sets are contained in the Boolean closure of the open sets in Pω. (a) now follows from the fact that the family of all finite unions of $F^nG(P\omega)$ sets is closed under finite unions and complement.

(b) follows from (a) because $B_1(P\omega)$ sets are countable unions of $B_0(P\omega)$ sets.

(c) is trivial because $\hat{B}_1(P\omega)$ sets are countable intersections of $B_0(P\omega)$ sets. $\square$

We consider some examples of sets in ${B_α(Pω)}_{α<Ω}$.

(i) $F_1(P\omega) \subset B_1(P\omega)$ because $F_1(P\omega)$ sets are countable unions of closed sets in Pω.

(ii) Let $e$ be any finite subset of $ω$. ${e}$ is equal to the intersection $U_e$ and $W_e$, hence ${e}$ is a $F^nG(P\omega)$ set.
(iii) Put $A = \{ \text{all finite subsets of } \omega \}$. Being a countable union of $e$'s, $A$ is in $B_1(P\omega)$. $A$ is in fact a $F_\sigma(P\omega)$ set.

(iv) Let $y$ be any subset of $\omega$. Note:
$$ \{y\} = W_y \cap \bigcap_e \{ U_e \mid e \text{ is a finite subset of } y \} $$
Hence $\{y\}$ is the intersection of a closed set and a $G_\delta$ set in $P\omega$.

**Proposition 1.2.2**

The sets in $\{B_\alpha(P\omega)\}_{\alpha<\Omega}$ constitute all the Borel sets in $P\omega$.

**Proof:** It suffices to show that the sets in $\{B_\alpha(P\omega)\}_{\alpha<\Omega}$ form a $\sigma$-algebra.
Clearly they are closed under countable unions and intersections. That they are closed under complement follows from Lemma 1.2.1(c). In general, the respective positions of the complements of the sets in $\{B_\alpha(P\omega)\}_{\alpha<\Omega}$ can be seen from the following figure:

<figure><img src="image_4.png" /><figcaption>Fig. 1</figcaption></figure>

<figure><img src="image_5.png" /></figure>

We proceed to compare $\{B_\alpha(P\omega)\}_{\alpha<\Omega}$ with the Borel hierarchy $\{F_\alpha(2^\omega)\}_{\alpha<\Omega}$ in $2^\omega$, and subsequently demonstrate that the Borel sets in $P\omega$ and $2^\omega$ are in fact the same.

**Proposition 1.2.3**

(a) $B_0(P\omega) \subset F_1(2^\omega)$

(b) $G(2^\omega) \subset B_1(P\omega)$

**Proof:** (a) By lemma 1.2.1, the $B_0(P\omega)$ sets are finite unions of $F_\alpha G(P\omega)$ sets. It suffices to show that the $F_\alpha G(P\omega)$ sets are $F_1(2^\omega)$ sets — this follows from the inclusions $G(2^\omega) \subset F_1(2^\omega)$ and $F_\alpha G(P\omega) \subset F_\alpha G(2^\omega)$.
(b) It suffices to show that the sets in the following sub-base of the topology of $2^ω$: the class of $\{x \subset ω \mid n \in ω\}$, $\{x \subset ω \mid n \notin ω\}$ (where $n \in ω$) are $B_0(Pω)$ sets. We have seen that $\{x \subset ω \mid n \in ω\}$ is an open set in $Pω$ and $\{x \subset ω \mid n \notin ω\}$ is a closed set in $Pω$, hence they are $B_0(Pω)$ sets. ☐

Using Proposition 1.2.3, we can obtain a stepwise comparison of $\{B_α(Pω)\}_{α<Ω}$ and $\{F_α(2^ω)\}_{α<Ω}$, a chart of which is given as below:

$$ \begin{array}{l@{\qquad}l} \begin{array}{l} B_0(P\omega) \subset B_1(P\omega) \subset \dots \\ \cup \quad \cup \end{array} & \begin{array}{l} C \quad B_\alpha(P\omega) \subset B_{\alpha+1}(P\omega) \subset \dots \\ \cup \quad \cup \end{array} \\[1.5ex] \begin{array}{l} F_0(2^\omega) \subset F_1(2^\omega) \subset \dots \\ \cup \quad \cup \end{array} & \begin{array}{l} C \quad F_\alpha(2^\omega) \subset F_{\alpha+1}(2^\omega) \subset \dots \\ \cup \quad \cup \end{array} \\[1.5ex] \begin{array}{l} \hat{B}_1(P\omega) \subset \hat{B}_2(P\omega) \subset \dots \end{array} & \begin{array}{l} C \quad \hat{B}_{\alpha+1}(P\omega) \subset \hat{B}_{\alpha+2}(P\omega) \subset \dots \end{array} \\ \multicolumn{4}{c}{( α < Ω )} \end{array} $$

<caption>Fig. 2</caption>

**Proposition 1.2.4**

The Borel sets in $Pω$ and $2^ω$ are the same.

**Proof** : Clearly the Borel sets in $Pω$ form a subclass of the Borel sets in $2^ω$ because the open sets in $Pω$ are only a proper subclass of the open sets in $2^ω$.

From Fig. 2 above, we obtain the following inclusions : for $α<Ω$,
$B_α(Pω) \subset F_α(2^ω) \subset \hat{B}_{α+1}(Pω) \subset B_{α+2}(Pω) \subset F_{α+2}(Pω)$.

Hence the sets in $\{F_α(2^ω)\}_{α<Ω}$ are 'sandwiched' among the sets in $\{B_α(Pω)\}_{α<Ω}$ and similarly, the sets in $\{B_α(Pω)\}_{α<Ω}$ are 'sandwiched' among the sets in $\{F_α(2^ω)\}_{α<Ω}$. Since the sets in $\{F_α(2^ω)\}_{α<Ω}$ are all the Borel sets in $2^ω$ and the sets in $\{B_α(Pω)\}_{α<Ω}$ are all the Borel sets in $Pω$, we conclude that the Borel sets in $Pω$ and $2^ω$ are the same. ☐
## 2 : $B_\sigma$ sets and $B_\delta$ sets in $P\omega$

We saw in the last section that $\{B_\alpha(P\omega)\}_{\alpha<\Omega}$ starts a stage 'slower' than $\{F_\alpha(2^\omega)\}_{\alpha<\Omega}$ in the sense that for each $\alpha<\Omega$, $B_\alpha(P\omega)$ forms a proper subclass of $F_\alpha(2^\omega)$. In this section, we study the sets in $B_1(P\omega)$ and $\hat{B}_1(P\omega)$ along the following issues :

(i) How do the $B_1(P\omega)$ sets and the $\hat{B}_1(P\omega)$ sets differ from each other in their properties ?

(ii) It is well-known that Hausdorff difference hierarchy in $2^\omega$ generate all the $F_\sigma \cap G_\delta(2^\omega)$ sets. Does Hausdorff difference hierarchy in $P\omega$ generate all the $B_\sigma \cap B_\delta(P\omega)$ sets ?

(iii) Is there any structural property to characterize the $B_\sigma \cap B_\delta(P\omega)$ sets in $P\omega$ ?

For the sake of convenience, we shall abbreviate $B_0(P\omega)$, $B_1(P\omega)$ and $\hat{B}_1(P\omega)$ as $B$, $B_\sigma$ and $B_\delta$ respectively.

## 2.1 : Normal forms for $B_\sigma$ sets and $B_\delta$ sets in $P\omega$

When we study a class of sets, it is desirable to have a normal form or a general representation of the sets in the class. Here, we establish normal forms for the classes $B_\sigma$ and $B_\delta$.

We observed in the last section that $B_\sigma$ is the family of all countable unions of $F^nG(P\omega)$ sets. Our first step is to obtain a normal form for the $F^nG(P\omega)$ sets.
**Proposition 2.1.1**

(a) A normal form for $G(P\omega)$ is $\{x\subset\omega \mid e\subset f(x)\}$;

(b) A normal form for $F(P\omega)$ is $\{x\subset\omega \mid f(x)\subset e\}$; and

(c) A normal form for $F^nG(P\omega)$ is $\{x\subset\omega \mid f(x)=e\}$

where $e$ is any non-empty finite subset of $\omega$, and $f$ ranges over $[P\omega \to P\omega]$.

*Proof*: (a) $\{x\subset\omega \mid e\subset f(x)\}$ is clearly a $G(P\omega)$ set, being the inverse image of the open set $U_e$ via the continuous function $f$.

Suppose $E$ is an open set in $P\omega$. Define $f: P\omega \to P\omega$ as follows:
for $x\in P\omega$,

$$f(x) = \begin{cases} e & \text{if } x \in E \\ \emptyset & \text{if otherwise} \end{cases}$$

Since $E$ is an open set, $f$ is a continuous function. Now $E$ is equal to the set $\{x\subset\omega \mid e\subset f(x)\}$.

(b) Use essentially the idea in (a).

(c) Note $\{x\subset\omega \mid f(x)=e\} = \{x\subset\omega \mid e\subset f(x)\} \cap \{x\subset\omega \mid f(x)\subset e\}$.
Hence $\{x\subset\omega \mid f(x)=e\}$ is a $F^nG(P\omega)$ set.

Suppose $E$ is a $F^nG(P\omega)$ set and $E = E_1 \cap E_2$ where by (a) and (b) above, $E_1$ is equal to $\{x\subset\omega \mid f_1(x)\subset e\}$ and $E_2$ is equal to $\{x\subset\omega \mid e\subset f_2(x)\}$ for some $f_1, f_2$ in $[P\omega \to P\omega]$. Define $f_3: P\omega \to P\omega$ as follows: for $x\in P\omega$,

$$f_3(x) = \begin{cases} e' & \text{if } f_1(x) \notin e \text{ and } e\subset f_2(x) \\ e & \text{if } f_1(x) \subset e \text{ and } e\subset f_2(x) \\ \emptyset & \text{if otherwise} \end{cases}$$

(where $e'$ is any finite subset of $\omega$ properly containing $e$)

It is simple to check that $f_3$ is a continuous function. Now $E$ is equal to the set $\{x\subset\omega \mid f_3(x)=e\}$. $\square$
**Proposition 2.1.2**

A normal form for $B_\sigma$ is $\{ x \subset \omega \mid (\exists i \in \omega)(f(i,x)=e) \}$ where $e$ is an non-empty finite subset of $\omega$ and $f$ ranges over $[\omega \times P\omega \to P\omega]$.

**Proof:** Note $\{ x \subset \omega \mid (\exists i \in \omega)(f(i,x)=e) \} = \bigcup_{i \in \omega} \{ x \subset \omega \mid f(i,x)=e \}$.

It follows from Proposition 2.1.1(c) that every set of the form $\{ x \subset \omega \mid (\exists i \in \omega)(f(i,x)=e) \}$ is $B_\sigma$.

Conversely, suppose $E$ is $B_\sigma$. Hence there exists $F \in G(P\omega)$ sets $E_i$ ($i \in \omega$) such that $E = \bigcup_{i \in \omega} E_i$. By Proposition 2.1.1(c), there exists $f_i \in [P\omega \to P\omega]$ for each $i \in \omega$ such that $E_i$ is equal to the set $\{ x \in \omega \mid f_i(x)=e \}$. Let $f: \omega \times P\omega \to P\omega$ be the function which maps $(i,x)$ to $f_i(x)$. $f$ is clearly continuous. Now,

$$ 
\begin{align*} 
E &= \bigcup_{i \in \omega} \{ x \subset \omega \mid f_i(x)=e \} \\ 
&= \{ x \subset \omega \mid (\exists i \in \omega)(f_i(x)=e) \} \\ 
&= \{ x \subset \omega \mid (\exists i \in \omega)(f(i,x)=e) \} . \square 
\end{align*} 
$$

Next, we demonstrate Scott's normal form theorem which states that $\{ x \subset \omega \mid f(x)=g(x) \}$ where $f,g \in [P\omega \to P\omega]$ is a normal form for $B_\delta$. The easy direction is the following:

**Proposition 2.1.3**

Every set of the form $\{ x \subset \omega \mid f(x)=g(x) \}$ (where $f,g \in [P\omega \to P\omega]$) is $B_\delta$.

**Proof:** Suppose $E = \{ x \subset \omega \mid f(x)=g(x) \}$ for some $f,g \in [P\omega \to P\omega]$. Note:

$$ E = \{ x \subset \omega \mid (\forall i \in \omega)(i \in f(x) \Leftrightarrow i \in g(x)) \} $$

For each $i$ in $\omega$, $\{ x \subset \omega \mid i \in f(x) \Leftrightarrow i \in g(x) \}$ is a $F \in G$ set in $P\omega$. Hence $E$, being a countable intersection of $F \in G(P\omega)$ sets, is a $B_\delta$ set in $P\omega$. $\square$
To show that every $B_\delta$ set is of the form $\{x\le\omega \mid f(x)=g(x)\}$ for some $f,g$ in $[P_\omega \to P_\omega]$, we need the following lemma:

**Lemma 2.1.4**

(a) The class of subsets in $P_\omega$ of the form $\{x\le\omega \mid f(x)=g(x)\}$ (where $f,g$ belong to $[P_\omega \to P_\omega]$) is closed under countable intersection.

(b) Every $F\cup G(P_\omega)$ set can be expressed as $\{x\le\omega \mid f(x)=g(x)\}$ for some $f,g$ in $[P_\omega \to P_\omega]$.

**Proof:** (a) Suppose $A=\bigcap_{i\in\omega} A_i$, where $A_i = \{x\le\omega \mid f_i(x)=g_i(x)\}$ ($f_i,g_i$ in $[P_\omega \to P_\omega]$). Define $f,g: P_\omega \to [\omega \to P_\omega]$ as follows: for $x$ in $P_\omega$ and $i$ in $\omega$, $f(x)(i)=f_i(x)$ and $g(x)(i)=g_i(x)$.
$f$ and $g$ are clearly continuous functions. Note:

$$ 
\begin{aligned}
A &= \bigcap_{i \in \omega} \{ x \le \omega \mid f_i(x) = g_i(x) \} \\
&= \{ x \le \omega \mid (\forall i \in \omega) ( f_i(x) = g_i(x) ) \} \\
&= \{ x \le \omega \mid f(x) = g(x) \}
\end{aligned}
$$

But $[P_\omega \to [\omega \to P_\omega]]$ is a subspace of $[P_\omega \to P_\omega]$, as a consequence of Proposition 1.1.1. Hence we can think of $f,g$ as elements in $[P_\omega \to P_\omega]$.

(b) Suppose $A$ is a $F\cup G(P_\omega)$ set, say $A=A_1\cup A_2$ where $A_1$ and $A_2$ are closed set and open set in $P_\omega$ respectively. Let $e,e'$ be any pair of distinct non-empty finite subsets of $\omega$. Define $f,g: P_\omega \to P_\omega$ as follows: for $x\in P_\omega$,

$$ f(x) = \begin{cases} \omega & \text{if } x \in A_2 \\ \emptyset & \text{if } x \in A_1 \setminus A_2 \\ e & \text{if otherwise} \end{cases} \qquad g(x) = \begin{cases} \omega & \text{if } x \in A_2 \\ \emptyset & \text{if } x \in A_1 \setminus A_2 \\ e' & \text{if otherwise} \end{cases} $$

It is routine to check that $f,g$ are continuous functions. As $e$ is different from $e'$, it follows from our definitions of $f$ and $g$ that the set $\{x\le\omega \mid f(x)=g(x)\}$ is equal to $A_1\cup A_2=A$. $\square$
**Proposition 2.1.5 (D. Scott)**

Every $B_\delta$ set in $P_\omega$ is of the form $\{x\le\omega \mid f(x)=g(x)\}$ for some $f,g$
in $[P_\omega \to P_\omega]$.

**Proof**: By Lemma 1.2.1, every $B_\delta$ set in $P_\omega$ is some countable intersection of $F_\infty G(P_\omega)$ sets. The proposition now follows from Lemma 2.1.4. $\square$

**Remark**: One can deduce from Proposition 2.1.5 that $\{x\le\omega \mid f(x)\le g(x)\}$ (where $f,g$ belong to $[P_\omega \to P_\omega]$) is also a normal form for $B_\delta$ sets.
## 2.2: Properties of $B_\sigma$ sets and $B_\delta$ sets in $P\omega$

The $B_\sigma$ sets in $P\omega$ are countable unions of $F^nG(P\omega)$ sets. They have a finitary property which we define as follows: a subset $E$ of $P\omega$ has finitary property if for every $x$ in $E$, there exists some finite subset $e$ of $x$ such that $\{y \in \omega \mid e \prec y \prec x\} = W_x \cap U_e$ is a subset of $E$.

### Proposition 2.2.1

(a) A subset $E$ of $P\omega$ has finitary property $\iff E$ is a union of $F^nG(P\omega)$ sets. Hence all $B_\sigma$ sets in $P\omega$ have finitary property.

(b) Every non-empty subset of $P\omega$ with finitary property contains some finite subset of $\omega$. Hence every non-empty $B_\sigma$ set in $P\omega$ contains some finite subset of $\omega$.

(c) The finitary property does not characterize the $B_\sigma$ sets in $P\omega$, i.e. there exists a subset $E$ of $P\omega$ which has finitary property and which is not $B_\sigma$.

**Proof:** (a) ($\Rightarrow$) Use the fact that for any subset $x$ of $\omega$ and any finite subset $e$ of $x$, $\{y \in \omega \mid e \prec y \prec x\} = W_x \cap U_e$ is a $F^nG(P\omega)$ set.
($\Leftarrow$) Note that all $F^nG(P\omega)$ sets have finitary property, and the class of subsets in $P\omega$ with finitary property is closed under infinite union.

(b) This follows trivially from the definition of finitary property.

(c) Let $E$ be $\{x \in \omega \mid x \text{ is co-infinite}\}$. It is well-known that $E$ is not a $F_\sigma$ set in $2^\omega$. As the $B_\sigma$ sets in $P\omega$ form a subclass of the $F_\sigma(2^\omega)$ sets, $E$ is not $B_\sigma$. $E$ has finitary property because given any $x$ in $E$, $\{y \in \omega \mid y \prec x\} = W_x$ is a subset of $E$. $\square$
**Remark :** The finitary property is not shared by the $B_\delta$ sets in $P\omega$. For example :

(i) Let A be $\{x\subset\omega \mid x \text{ is infinite}\}$. A is a $B_\delta$ set in $P\omega$,
but A is not $B_\sigma$ because it doesn't contain any finite subset of $\omega$.

(ii) We noted in 1.2 that for any subset $y$ of $\omega$, $\{y\}$ is a $F_\delta G_\delta(P\omega)$ set. When $y$ is finite, $\{y\}$ is a $F_\sigma G(P\omega)$ set, hence a $B_\sigma$ set. When $y$ is infinite, $\{y\}$ is not $B_\sigma$ because it doesn't contain any finite subset of $\omega$. Thus for any subset $y$ of $\omega$, $\{y\}$ is $B_\sigma$ if and only if $y$ is a finite subset of $\omega$.

We shall see in 2.5 that the finitary property is connected with some
chain property . At present, we study some other chain property given as follows :
a subset E of Pw is closed under chain if for every increasing chain {$x_i$}$_{i\in\omega}$
( x_i \subset x_{i+1} for all i in \omega ) in E, the union $\bigcup_{i\in\omega} x_i$ belongs to E .

**Proposition 2.2.2**

(a) Every $B_\delta$ set in $P\omega$ is closed under chain .

(b) The 'closed under chain' property doesn't characterize the $B_\delta$ sets in $P\omega$.

(c) The 'closed under chain' property is not shared by the $B_\sigma$ sets in $P\omega$.

**Proof :** (a) Suppose the given $B_\delta$ set is equal to $\{x \subset \omega \mid f(x) \subset g(x)\}$ for some $f,g$ in $[P\omega \to P\omega]$. Let $\{x_i\}_{i \in \omega}$ be any increasing chain in $\{x \subset \omega \mid f(x) \subset g(x)\}$. Hence for all $i$ in $\omega$, $f(x_i)$ is a subset of $g(x_i)$. By the continuity of $f$ and $g$, $f(\bigcup_{i \in \omega} x_i)$ is necessarily a subset of $g(\bigcup_{i \in \omega} x_i)$. Hence the given $B_\delta$ set is closed under chain.

(b) Let A be { x ⊂ ω | x is co-finite } . A is closed under chain ( in fact, there is not any strictly increasing chain in A ) . A is not a B<sub>δ</sub> set , as we have already pointed out in our proof of Proposition 2.2.1 .

(c) Let A be { x ⊂ ω | x is finite } . A is a B<sub>σ</sub> set and A is not closed under chain . □
Note that the 'closed under chain' property in Pw is in fact a degenerate notion of the 'closed under limit' property in $2^ω$. Whereas the 'closed under chain' property does not characterize the $B_δ$ sets in Pw, the 'closed under limit' property does characterize the closed sets in $2^ω$ (which form a proper subclass of the $B_δ$ sets in Pw), as we all know.

We have seen that every non-empty $B_σ$ set in Pw contains some finite subset of w. The following proposition gives us a contrast between the $B_δ$ sets and the $B_σ$ sets in Pw in terms of the existence of infinite subsets of w.

**Proposition 2.2.3**

(a) Suppose A is a $B_δ$ set in Pw and A is not $B_σ$, then A contains some infinite subset of w.

(b) Suppose A is a $B_σ$ set and y is an infinite subset of w in A. If we remove y from A, then the resulting set $A'=A\{y\}$ is not $B_δ$.

**Proof :** (a) If the given $B_δ$ set A doesn't contain any infinite subset of w, then A is a union of finite subsets of w, hence it is $B_σ$.

(b) Suppose y is an infinite subset of w in the given $B_σ$ set A. Since A has finitary property, there exists some finite subset e of y such that $\{x \in w | e \subset x \subset y\}$ is a subset of A. Now $\{x \in w | e \subset x \subset y\}$ is a subset of A', and it is straightforward to see that A' is not closed under chain. $\square$

Is there a criteria to determine when a given $B_σ$ set in Pw is $B_δ$ ?
- yes, there is. In 2.4, we will show that a subset A of Pw is $B_σ \cap B_δ$
if and only if A and $A^C$ are closed under chain. Consequently, for any
given $B_σ$ set A in Pw, A is $B_δ$ if and only if A is closed under chain.
## 2.3 : Hausdorff difference hierarchy in Pw

The $B_\sigma \cap B_\delta$ sets in Pw form a Boolean algebra containing all the B sets. While we know that the B sets in Pw are finite unions of $F^\infty G(Pw)$ sets, we are here to study how the $B_\sigma \cap B_\delta$ sets in Pw are generated. For this, we need to know about Hausdorff difference hierarchy.

Suppose A is a given subset in a separable topological space X.
Hausdorff sequences $\{P_\alpha^A\}_{\alpha \in \Omega_r}$ and $\{Q_\alpha^A\}_{\alpha \in \Omega_r}$ are defined as follows : for
$\alpha$ in $\Omega_r$ ( the class of ordinal numbers ),

$$P_0^A = A$$

$$Q_0^A = A^c$$

$$P_{\alpha+1}^{A} = C1(Q_{\alpha+1}^{A}) \cap A$$

$$Q_{\alpha+1}^{A} = C1(P_{\alpha}^{A}) \cap A^{c}$$

for limit ordinal $\alpha$, $P_\alpha^A = C1(Q_\alpha^A) \cap A$

$$Q_{\alpha}^{A} = \bigcap_{\beta < \alpha} Q_{\beta}^{A}$$

Here are some of the properties of $\{P_\alpha^A\}_{\alpha \in \Omega_r}$ and $\{Q_\alpha^A\}_{\alpha \in \Omega_r}$ :

(i) $\{P_\alpha^A\}_{\alpha \in \Omega_r}$ and $\{Q_\alpha^A\}_{\alpha \in \Omega_r}$ are decreasing sequences.

(ii) For $\alpha$ in $\Omega_r$, $C1(P_\alpha^A) = P_\alpha^A \cup Q_{\alpha+1}^A$ and $C1(Q_{\alpha+1}^A) = P_{\alpha+1}^A \cup Q_{\alpha+1}^A$. Also note $P_0^A \cup Q_0^A = X$ and $P_\alpha^A \cup Q_\alpha^A$ is a closed set for all limit ordinals $\alpha$. $\{P_\alpha^A \cup Q_\alpha^A\}_{\alpha \in \Omega_r}$ and $\{P_{\alpha+1}^A \cup Q_{\alpha+1}^A\}_{\alpha \in \Omega_r}$ are decreasing sequences of closed sets in X.

(iii) For $\alpha$ in $\Omega_r$, $P_\alpha^A \setminus P_{\alpha+1}^A = C1(P_\alpha^A) \setminus C1(Q_{\alpha+1}^A)$ and $Q_{\alpha+1}^A \setminus Q_{\alpha+2}^A = C1(Q_{\alpha+1}^A) \setminus C1(P_{\alpha+1}^A)$. Also note $Q_0^A \setminus Q_1^A = X \setminus C1(P_0^A)$ and $Q_\alpha^A \setminus Q_{\alpha+1}^A = (P_\alpha^A \cup Q_\alpha^A) \setminus C1(P_\alpha^A)$ for all limit ordinals $\alpha$. Hence $P_\alpha^A \setminus P_{\alpha+1}^A$ and $Q_\alpha^A \setminus Q_{\alpha+1}^A$ are differences of two closed sets for all ordinals $\alpha$.
(iv) Note :

$P_\omega \supset C_1(P_0^A) \supset C_1(Q_1^A) \supset C_1(P_1^A) \supset \dots \supset C_1(Q_\alpha^A) \supset C_1(P_\alpha^A) \supset C_1(Q_{\alpha+1}^A) \supset \dots$
where $\alpha$ ranges over $\text{Or}$.

(v) For $\delta$ in $\text{Or}$, say that $P_\delta^A$ stabilizes if $(\forall \beta \in \text{Or})(\delta < \beta \Rightarrow P_\delta^A = P_\beta^A)$; similarly for $\gamma$ in $\text{Or}$, say that $Q_\gamma^A$ stabilizes if $(\forall \beta \in \text{Or})(\gamma < \beta \Rightarrow Q_\gamma^A = Q_\beta^A)$. It is well-known that no uncountable strictly decreasing of closed sets exists in a separable space. As $\{P_\alpha^A \cup Q_\alpha^A\}_{\alpha \in \text{Or}}$ is an uncountable decreasing sequence of closed sets in $\mathcal{X}$, there exists $\delta, \gamma < \Omega$ such that $P_\delta^A$ and $Q_\gamma^A$ stabilize. The set $P_\delta^A \cup Q_\gamma^A$ is called the residue of $A$. Note :

$$ 
\begin{aligned}
A &= [P_0^A \setminus P_1^A] \cup \dots \cup [P_\alpha^A \setminus P_{\alpha+1}^A] \cup \dots \cup P_\delta^A \quad (\alpha < \delta) \\
&= [C_1(P_0^A) \setminus C_1(Q_1^A)] \cup \dots \cup [C_1(P_\alpha^A) \setminus C_1(Q_{\alpha+1}^A)] \cup \dots \cup P_\delta^A
\end{aligned}
$$
and

$$ 
\begin{aligned}
A^c &= [Q_0^A \setminus Q_1^A] \cup \dots \cup [Q_{\alpha+1}^A \setminus Q_{\alpha+2}^A] \cup \dots \cup Q_\gamma^A \quad (\alpha+1 < \gamma) \\
&= [\mathcal{X} \setminus C_1(P_0^A)] \cup \dots \cup [C_1(Q_{\alpha+1}^A) \setminus C_1(P_{\alpha+1}^A)] \cup \dots \cup Q_\gamma^A
\end{aligned}
$$

We can now replace $\{P_\alpha^A\}_{\alpha \in \text{Or}}$ and $\{Q_\alpha^A\}_{\alpha \in \text{Or}}$ by $\{P_\alpha^A\}_{\alpha < \delta}$ and $\{Q_\alpha^A\}_{\alpha < \gamma}$ respectively.

We consider some examples of Hausdorff sequences in $P_\omega$:

(i) Suppose $A$ is a closed set in $P_\omega$. Then for all $\alpha \ge 1$, $P_\alpha^A = \emptyset$ and $Q_\alpha^A = \emptyset$.

(ii) Let $A$ be $\{0\}$. Then $Q_1^A = \{0\}$ and for all $\alpha \ge 1$, $P_\alpha^A = \emptyset$ and $Q_{\alpha+1}^A = \emptyset$. Hence $P_1^A$ and $Q_2^A$ stabilize, and the residue of $A$ vanishes.

(iii) Let $A$ be $\{\omega\}$. Then for all ordinals $\alpha$, $P_\alpha^A = A$ and $Q_\alpha^A = A^c$. Hence $P_0^A$ and $Q_0^A$ stabilize, and the residue of $A$ is the whole set $P_\omega$.
Hausdorff hierarchy ${H_\alpha}(X)_{\alpha<\Omega}$ in a separable space $X$ is defined
as follows : for $\lambda=0$ or any limit ordinal $< \Omega$, and $n \in \omega$,

$$
H_{\lambda+2n}(X) = \{ A \subset X \mid Q_{\lambda+n+1}^{A} \text{ stabilizes } \}
$$

$$
H_{\lambda+2n+1}(X) = \{ A \subset X \mid P_{\lambda+n+1}^{A} \text{ stabilizes } \}
$$

Thus ${H_\alpha(X)}_{\alpha<\Omega}$ classifies the subsets $A$ in $X$ in terms of the ordinal
$\delta<\Omega$ at which $P_\delta^A$ or $Q_\delta^A$ stabilizes.

Now Hausdorff difference hierarchy ${D_\alpha}(X)_{\alpha<\Omega}$ is a subhierarchy of
${H_\alpha}(X)_{\alpha<\Omega}$ whose range consists of all the subsets in $X$ with an empty
residue. The definition of ${D_\alpha}(X)_{\alpha<\Omega}$ is as follows : for $\lambda=0$ or any
limit ordinal $< \Omega$, and $n \in \omega$,

$$
D_{\lambda+2n}(X) = \{ A \subset X \mid Q_{\lambda+n+1}^{A} = \emptyset \}
$$

$$
D_{\lambda+2n+1}(X) = \{ A \subset X \mid P_{\lambda+n+1}^{A} = \emptyset \}
$$

`$\{D_\alpha(X)\}_{\alpha<\Omega}$` can also be defined in terms of 'alternating unions'.

`A \subset X` is an alternating union of an `\alpha+1`-decreasing (`\alpha<\Omega`) sequence of closed sets in `X` if there exists a decreasing sequence `\{F_\beta\}_{\beta<\alpha+1}` of closed sets in `X` such that:

$$
A = (F_0 \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots \quad \text{if } \lambda+1 \text{ is even}
$$

$$
= (F_0 \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots \cup F_{\alpha+1} \quad \text{if } \alpha+1 \text{ is odd}
$$

where $\lambda+2n < \alpha+1$, $n \in \omega$ and $\lambda=0$ or any limit ordinal.

An equivalent definition of ${D_\alpha}(X)_{\alpha<\Omega}$ is : for $\alpha$ in $\Omega$,

$D_\alpha(X) = \{ A \subset X \mid A \text{ is an alternating union of an } \alpha+1\text{-decreasing sequence of closed sets in } X \}$

Thus $D_0(X)$ is the family of closed sets in $X$ ; $D_1(X)$ is the family of
differences of two closed sets in $X$ , etc . The equivalence of the two
definitions of ${D_\alpha}(X)_{\alpha<\Omega}$ is a classical fact , the proof of which can be
found in [2] .
The sets in ${D_n(X)}_{n \in \omega}$ can be shown to constitute all the finite unions of $F_n^c(X)$ sets. In particular, the range of ${D_n(P\omega)}_{n \in \omega}$ is the family of B sets.

The classical Hausdorff theorem states that the sets in ${D_\alpha(X)}_{\alpha<\Omega}$ constitute all the $F_\sigma \cap G_\delta$ sets in $X$, where $X=\omega^\omega$ or $2^\omega$. We are here to demonstrate that the sets in ${D_\alpha(P\omega)}_{\alpha<\Omega}$ constitute all the $B_\sigma \cap B_\delta$ sets in $P\omega$ - this gives us a structural characterization of the $B_\sigma \cap B_\delta$ sets in $P\omega$ in terms of alternating unions of closed sets. The easy direction is the following:

**Proposition 2.3.1**

The sets in ${D_\alpha(P\omega)}_{\alpha<\Omega}$ are $B_\sigma \cap B_\delta$ sets in $P\omega$.

*Proof:* Suppose A belongs to ${D_\alpha(P\omega)}_{\alpha<\Omega}$ and for $\delta, \gamma<\Omega$, $P_\delta^A = P_\gamma^A = \emptyset$. We can express A and $A^c$ as follows:

$$A = [C_1(P_0^A) \setminus C_1(Q_1^A)] \cup \dots \cup [C_1(P_\alpha^A) \setminus C_1(Q_{\alpha+1}^A)] \cup \dots \quad (\alpha < \delta)$$
and

$$A^c = [P\omega \setminus C_1(P_0^A)] \cup \dots \cup [C_1(Q_{\alpha+1}^A) \setminus C_1(P_{\alpha+1}^A)] \cup \dots \quad (\alpha+1 < \delta)$$

So A and $A^c$ are both countable unions of $F_n^c(P\omega)$ sets, hence they are $B_\sigma$ sets in $P\omega$. Thus A is a $B_\sigma \cap B_\delta$ set in $P\omega$. $\square$

To see the converse direction which is equivalent to saying that every $B_\sigma \cap B_\delta$ set in $P\omega$ has an empty residue, we need the following lemmas:

**Lemma 2.3.2**

$A \subset P\omega$ admits an infinite alternating chain ${x_i}_{i \in \omega}$ if ${x_i}_{i \in \omega}$ is an increasing chain of elements in $P\omega$ such that for $i$ in $\omega$, $x_{2i}$ belongs to A and $x_{2i+1}$ belongs to $A^c$. No $B_\sigma \cap B_\delta$ set in $P\omega$ admits an infinite alternating chain.

*Proof:* Suppose A admits the infinite alternating chain ${x_i}_{i \in \omega}$. Note
that {$x_{2i}}_{i \in \omega}$ and {$x_{2i+1}}_{i \in \omega}$ are both increasing chains in A
and $A^c$ respectively. As A is a $B_\sigma \cap B_\delta$ set, A and $A^c$ are
both closed under chain. Hence $x = \bigcup_{i \in \omega} x_{2i}$ ($= \bigcup_{i \in \omega} x_{2i+1}$) belongs
to $A \cap A^c$, contradiction. □

**Lemma 2.3.3**

(a) Let A be any given subset in Pω. For every finite subset e of ω in C1(A)\A, there exists some y in A such that e is a subset of y.

(b) When A in (a) is a $B_\sigma$ set, then y can be taken to be a finite subset of ω.

Proof : (a) Suppose $A \subset P\omega$ and the finite subset $e$ of $\omega$ in $Cl(A)\setminus A$
are given. Consider the set $A' = Cl(A) \setminus U_e$ which is an intersection
of two closed sets in $P\omega$, hence a closed set. A cannot be
a subset of $A'$, for otherwise $A'$ would be a closed set containing
$A$ — note that $A'$ is a proper subset of $Cl(A)$. Hence there
exists some $y$ in $A \setminus A'$. Now note that $e$ is a subset of $y$.

(b) Now assume A in (a) is a $B_\sigma$ set, hence A has finitary
property. As y lies in A, there exists some finite subset e'
of y such that $W_y \cap U_e$, is a subset of A. Since e is a
subset of y, we can infer that there exists a finite subset y'
of y in $W_y \cap U_e$, such that e is a subset of y'. □

**Remarks** : (i) Lemma 2.3.3(a) is not true if e is not a finite subset of ω.

Let A be Pω\{ω}. Note that the closure of A is the entire set Pω, and that there exists no y in A such that ω ( ∈ Cl(A)\A ) is a subset of y.

(ii) Lemma 2.3.3(b) is not true if A is a $B_\delta$ set instead of a
$B_\sigma$ set. Let A be {ω}. Note that the closure of A is the
entire set Pω, and there exists no finite subset of ω in A.
**Proposition 2.3.4**

Suppose A is a $B_\sigma \cap B_\delta$ set in $P\omega$, then the residue of A is empty.

**Proof:** Suppose A is a $B_\sigma \cap B_\delta$ set and the residue of A, $P_\delta^A \cup Q_\gamma^A$ (where we assume that $P_\delta^A$ and $Q_\gamma^A$ stabilize), is non-empty. Note that $P_\delta^A \cup Q_\gamma^A$ is a closed set in $P\omega$, and that $P_\delta^A = (P_\delta^A \cup Q_\gamma^A) \cap A$ and $Q_\gamma^A = (P_\delta^A \cup Q_\gamma^A) \cap A^c$, both being the intersection of a closed set and a $B_\sigma$ set, are non-empty $B_\sigma$ sets in $P\omega$. We derive a contradiction by showing that A admits an infinite alternating chain. Using induction, we define a sequence $\{x_i\}_{i \in \omega}$ of finite subsets of as follows:

i=0 : Since $P_\delta^A$ is a non-empty $B_\sigma$ set, there exists some finite subset of $\omega$ in $P_\delta^A$, say $x_0$.

Assume $x_i$ has been defined and is a finite subset of $\omega$.

**Case (i):** *i* is even

Apply Lemma 2.3.3(b) to obtain some finite subset $x_{i+1}$ of $\omega$ in $Q_\gamma^A$ such that $x_i$ is a finite subset of $x_{i+1}$.

**Case (ii):** *i* is odd

Apply Lemma 2.3.3(b) to obtain some finite subset $x_{i+1}$ of $\omega$ in $P_\delta^A$ such that $x_i$ is a finite subset of $x_{i+1}$.

Clearly, A admits the infinite alternating chain $\{x_i\}_{i \in \omega}$, thus we have a contradiction. ☐

Thus the range of $\{D_\alpha(P\omega)\}_{\alpha<\Omega}$ is the set of all $B_\sigma \cap B_\delta$ sets in $P\omega$.
We conclude this subsection by observing some property of $\{D_\alpha(P\omega)\}_{\alpha<\Omega}$.

**Proposition 2.3.5**

(a) $D_0(P\omega) \cap \hat{D}_0(P\omega) = \{\emptyset, P\omega\}$

(b) For all ordinals $\alpha$, $D_{\alpha+1}(P\omega) \cap \hat{D}_{\alpha+1}(P\omega) = D_\alpha(P\omega) \cup \hat{D}_\alpha(P\omega)$
**Proof :** (a) (a) is equivalent to saying that the only clopen sets in Pω are Ø and Pω - we observed this fact in 1.1.

(b) The non-trivial part is to show that the family $D_{\alpha+1}(P\omega) \cap \hat{D}_{\alpha+1}(P\omega)$ is contained in $D_{\alpha}(P\omega) \cup \hat{D}_{\alpha}(P\omega)$ for all ordinals $\alpha$. So suppose A is a set in $D_{\alpha+1}(P\omega) \cap \hat{D}_{\alpha+1}(P\omega)$.

Case (i) : $\omega$ belongs to A.

As A is in $D_{\alpha+1}(P\omega)$, there exists a decreasing sequence $\{F_\beta\}_{\beta<\alpha+2}$ of closed sets in Pω such that:

$A = (F_0 \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots$ if $\alpha$ is even
$= (F_0 \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots \cup F_{\alpha+1}$ if $\alpha$ is odd
where $\lambda+2n < \alpha+2$, $n \in \omega$ and $\lambda=0$ or any limit ordinal.

As $F_0$ is the largest closed set in the sequence $\{F_\beta\}_{\beta<\alpha+2}$, $\omega$ belongs to $F_0$. $F_0$ must be the set Pω, because Pω is the only closed set in the space Pω containing the element $\omega$. Hence,
$A = (P\omega \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots$ if $\alpha$ is even
$= (P\omega \setminus F_1) \cup \dots \cup (F_{\lambda+2n} \setminus F_{\lambda+2n+1}) \cup \dots \cup F_{\alpha+1}$ if $\alpha$ is odd
which means:

$A^c = (F_1 \setminus F_2) \cup \dots (F_{\lambda+2n+1} \setminus F_{\lambda+2n+2}) \cup \dots \cup F_{\alpha+1}$ if $\alpha$ is even
$= (F_1 \setminus F_2) \cup \dots (F_{\lambda+2n+1} \setminus F_{\lambda+2n+2}) \cup \dots$ if $\alpha$ is odd
where $\lambda+2n < \alpha$, $n \in \omega$ and $\lambda=0$ or any limit ordinal.

$A^c$, being the alternating union of an $\alpha+1$-decreasing sequence $\{F_{\beta+1}\}_{\beta<\alpha+2}$ of closed sets in Pω, is in $D_\alpha(P\omega)$. Hence A is in $\hat{D}_\alpha(P\omega)$.

Case (ii) : $\omega$ belongs to $A^c$.

Use the same idea in Case (i) to show that A belongs to $D_\alpha(P\omega)$.

In both cases, A belongs to $D_\alpha(P\omega) \cup \hat{D}_\alpha(P\omega)$. $\square$
## 2.4: A characterization of $B_\sigma \cap B_\delta$ sets in $P\omega$

Here, we give a characterization of the $B_\sigma \cap B_\delta$ sets in $P\omega$ in terms of the 'closed under chain' property which we introduced in 2.2. We observed earlier that all the $B_\delta$ sets in $P\omega$ are closed under chain. Hence if A is a given $B_\sigma \cap B_\delta$ set in $P\omega$, then we know that A and $A^C$ are both closed under chain. The converse of the latter fact is also true, as we are going to show.

### Proposition 2.4.1

Suppose A is a given subset in $P\omega$. If A and $A^C$ are closed under chain, then A is a $B_\sigma \cap B_\delta$ set in $P\omega$.

**Proof:** Suppose A and $A^C$ are closed under chain, and A is not a $B_\sigma \cap B_\delta$ set in $P\omega$. By Proposition 2.3.1, the residue of A, $P_\delta^A \cup Q_\gamma^A$ (where we assume that $P_\delta^A$ and $Q_\gamma^A$ stabilize), is non-empty. Using induction, we define a sequence $\{x_i\}_{i \in \omega}$ of finite subsets of $\omega$ alternating in and out of $P_\delta^A \cup Q_\gamma^A$ as follows:

i=0: Since $P_\delta^A \cup Q_\gamma^A$ is a non-empty closed set in $P\omega$, $\emptyset$ belongs to $P_\delta^A \cup Q_\gamma^A$, hence $\emptyset$ belongs to either $P_\delta^A$ or $Q_\gamma^A$. We can assume that $\emptyset$ belongs to $P_\delta^A$ (whether $\emptyset$ belongs to $P_\delta^A$ or $Q_\gamma^A$ is not essential to our proof), and take $x_0$ to be $\emptyset$.

Assume $x_i$ has been defined and is a finite subset of $\omega$.

Case (i): i is even

Here, $x_i$ is in $P_\delta^A$.

*Claim:* There exists some finite subset $x_{i+1}$ of $\omega$ in $Q_\gamma^A$ such that $x_i$ is a subset of $x_{i+1}$.

*Proof:* As $x_i$ belongs to the closure of $Q_\gamma^A$, hence by Lemma 2.3.3(a), there exists some $y$ in $Q_\gamma^A$ such that $x_i$ is a subset of $y$.
If $y$ is a finite subset of $\omega$, then take $x_{i+1}$ to be $y$.

Suppose $y$ is an infinite subset of $\omega$. Note :

$y = \bigcup \{ e \in \omega \mid e \text{ is a finite subset of } \omega \text{ in } W_y \cap U_{x_i} \}$

$W_y \cap U_{x_i}$ is a subset of $P_\delta^A \cup Q_\gamma^A$ because $P_\delta^A \cup Q_\gamma^A$ is closed under subset and $y$ belongs to $Q_\gamma^A$. If all the finite subsets $e$ of $\omega$ are in $P_\delta^A$, then $y$ would be in $P_\delta^A$ since $P_\delta^A$ is closed under chain ( being the intersection of two sets closed under chain, namely, $P_\delta^A \cup Q_\gamma^A$ and $A$ ). As $y$ is in $Q_\gamma^A$, we conclude that there exists some finite subset $e$ of $\omega$ in $W_y \cap U_{x_i}$. Take $x_{i+1}$ to be $e$.

Case (ii) : $i$ is odd

Here, $x_i$ is in $Q_\gamma^A$. Use the same idea in Case (i) to obtain some
finite subset $x_{i+1}$ of $\omega$ in $P_\delta^A$ such that $x_i$ is a subset of $x_{i+1}$.
Thus we have constructed an increasing chain $\{x_i\}_{i \in \omega}$ of finite subsets
of $\omega$ alternating in and out of $E$. Now $\{x_{2i}\}_{i \in \omega}$ and $\{x_{2i+1}\}_{i \in \omega}$
are increasing chains in $A$ and $A^c$ respectively. As $A$ and $A^c$
are closed under chain, $x = \bigcup_{i \in \omega} x_{2i}$ ($= \bigcup_{i \in \omega} x_{2i+1}$) belongs to $A \cap A^c$,
contradiction. $\square$

Corollary 2.4.2

Suppose $A$ is a $B_\sigma$ set in $P^\omega$. Then $A$ is $B_\sigma \cap B_\delta$ if and only $A$ is closed under chain.
## 2.5: B sets in P<sub>ω</sub>

We have seen that the B sets in P<sub>ω</sub> are all the sets in {D<sub>n</sub>(P<sub>ω</sub>)}n∈ω.
Here, we establish a criteria to determine when a given B<sub>α</sub> ∩ B<sub>δ</sub> set in P<sub>ω</sub>
is a B set.

Given A⊂P<sub>ω</sub>, say that A admits an alternating chain {x<sub>i</sub>}<sub>i=0</sub><sup>n</sup> of
length n+1 (n∈ω) if {x<sub>i</sub>}<sub>i=0</sub><sup>n</sup> is an increasing chain of elements in P<sub>ω</sub>,
and for i in ω, x<sub>i</sub> belongs to A if and only if i is an even integer.

First, we observe some trivial facts.

(i) If A⊂P<sub>ω</sub> does not admit any alternating chain of length n+1, then A cannot admit alternating chains of length m+1 for all m≥n (n,m∈ω).

(ii) If A ⊂ Pω admits an infinite alternating chain, then A admits an
alternating chain of arbitrary finite length.

(iii) If A⊂P<sub>ω</sub> is closed under superset, then A cannot admit any alternating chain of length 2. Hence all open sets in P<sub>ω</sub> cannot admit any alternating chain of length 2.

(iv) Say that A⊂Pω is sandwiched if (∀x,y∈A)(∀z⊂ω)(x⊂z<y ⇒ z∈A).
Note that A is sandwiched if and only if A does not admit any
alternating chain of length 3. All F^nG(Pω) sets are sandwiched.

**Proposition 2.5.1**

If A is a B set, then there exists some n∈ω such that A cannot admit
alternating chains of length m+1 for all m≥n.

Proof: The B sets are finite unions of F^nG(P^ω) sets.

Case (i) : A is a F^nG(P^ω) set.

In this case, A does not admit alternating chains
of length m+1 for all m≥3.
**Case (ii) :** A is a union of $n$ ($n \ge 1$) $F^1G(P\omega)$ sets.
We claim that A cannot admit any alternating chain
of length $2n+1$. For otherwise, assume A admits
some alternating chain of length $2n+1$, and $A=\bigcup_{i=1}^n A_i$
where $A_i$'s ($i \le n$) are $F^1G(P\omega)$ sets. Then
by the pigeon-hole principle, one of the $A_i$'s must
admit an alternating chain of length 3, contradiction. $\square$

**Proposition 2.5.2**

Suppose $A \subset P\omega$ is a $(B_\sigma \cap B_\delta) \setminus B$ set, then A can admit alternating chains of arbitrary finite length.

**Proof :** Given $n \in \omega$, we want to demonstrate that A admits an alternating chain of length $n+1$. Without loss of generality, assume that $n$ is an even integer. Since A is a $(B_\sigma \cap B_\delta) \setminus B$ set, we are assured that for all integers $m$, $P_m^A \setminus P_{m+1}^A$ and $Q_m^A \setminus Q_{m+1}^A$ are non-empty $F^1G(P\omega)$ sets. Using induction, we define $\{x_j\}_{j=0}^n$ with the following properties :

(i) $x_0 \in P_k^A \setminus P_{k+1}^A$ where $k$ is $\frac{n}{2}$;

(ii) $x_{2j} (\ 2j \le n) \in P_{k-j}^A \setminus P_{k-j+1}^A$ and $x_{2j+1} (\ 2j+1 \le n) \in Q_{k-j}^A \setminus Q_{k-j+1}^A$.

$j=0$: Let $x_0$ be any non-empty finite subset of $\omega$ in the non-empty $F^1G(P\omega)$ set $P_k^A \setminus P_{k+1}^A$, the existence of which is guaranteed by Proposition 2.2.1(b).

$2j+1 (\ 2j+1 \le n)$ : Assume $x_{2j}$ has been defined and lies in $P_{k-j}^A \setminus P_{k-j+1}^A$.
Since $x_{2j}$ belongs to the closure of $Q_{k-j}^A$, we can apply Lemma 2.3.3(b) to obtain some finite subset $x_{2j+1}$ of $\omega$ in $Q_{k-j}^A$ such that $x_{2j}$ is a subset of $x_{2j+1}$. Note that $x_{2j+1}$ cannot be in $Q_{k-j+1}^A$ because $P_{k-j+1}^A \setminus Q_{k-j+1}^A$ is a closed set in $P\omega$ and $x_{2j+1} \in Q_{k-j+1}^A$ would imply $x_{2j} \in P_{k-j+1}^A$.

$2j (\ 2j \le n$ and $j \ge 1)$ : Assume $x_{2j-1}$ has been defined and lies in $Q_{k-j+1}^A \setminus Q_{k-j+2}^A$. Since $x_{2j-1}$ belongs to the closure of $P_{k-j}^A$, we
can apply Lemma 2.3.3(b) to obtain some finite subset $x_{2j}$ of $\omega$
in $P_{k-j}^A \setminus P_{k-j+1}^A$.

Clearly A admits the alternating chain ${x_i}_ {i=0}^n$. Finally note that
all the $x_i$'s ($i \le n$) in our construction are finite subsets of $\omega$. $\square$

**Remarks :** (i) What we have in fact proved in Proposition 2.5.2 is the following : Suppose A is a $B_\sigma \cap B_\delta$ set in $P\omega$ and $P_n^A \setminus P_{n+1}^A$ ($n \in \omega$) is non-empty, then A admits an alternating chain of length $2n+1$.

(ii) Using the method of proof in Proposition 2.5.2, we can establish the following fact : Suppose $A \subset P\omega$ is a $B_\sigma \cap B_\delta$ set and $P_\omega^A$ is non-empty, then given any finite subset $e$ of $\omega$ in $P_\omega^A$ (such an $e$ exists because $P_\omega^A$ is a non-empty $B_\sigma$ set) and any integer $n$, there exists an alternating chain ${x_i}_ {i=0}^n$ of finite subsets of $\omega$ such that $x_0=e$ and A admits ${x_i}_ {i=0}^n$. Corollary : A and $A^C$ both contain infinitely many subsets $e'$ of $\omega$ such that $e$ is a subset of $e'$.

Combining Proposition 2.5.1 and Proposition 2.5.2, we have the following
criteria to determine when a given $B_\sigma \cap B_\delta$ set in $P\omega$ is a $B$ set :

**Proposition 2.5.3**

Suppose A is a $B_\sigma \cap B_\delta$ set in $P\omega$, then A is a B set if and only if there exists some integer $n$ such that A cannot accept any alternating chain of length $n+1$.

We close this subsection by giving an example of a $(B_\sigma \cap B_\delta) \setminus B$ set $C$ in $P\omega$. $C$ is a countable union of $C_n$'s ($n \in \omega$ and $n \ge 1$) where $C_n$'s are defined as follows :

$C_n = \{\{n^2\}, \dots, \{n^2, \dots, m, \dots, n^2+2i\}, \dots\} \text{ ( } n^2 \le m \le n^2+2i, 1 \le i \le n \text{ )}$
As we shall re-visit C in future, we examine the properties of C in detail:

(i) C is a $B_\sigma$ set in $P_\omega$ because all the elements in C are finite subsets of $\omega$.

(ii) Each $C_i$ ($i \ge 1$) consists of an ascending chain of length $i+1$, which is part of some alternating chain of length $2i+1$ alternating in and out of C. For example, consider $C_3$. $C_3$ consists of an ascending chain of length 4. Now define an alternating chain $\{x_i\}_{i=0}^6$ of length 7 as follows:

$$x_0 = \{9\}$$

$$x_1 = \{9, 10\}$$

$$x_2 = \{9, 10, 11\}$$

$$x_3 = \{9, 10, 11, 12\}$$

$$x_4 = \{9, 10, 11, 12, 13\}$$

$$x_5 = \{9, 10, 11, 12, 13, 14\}$$

$$x_6 = \{9, 10, 11, 12, 13, 14, 15\}$$

$C_3 = \{x_0, x_2, x_4, x_6\}$ is part of $\{x_i\}_{i=0}^6$. This shows that C can admit an alternating chain of arbitrary length $n+1$ ($n \in \omega$). Hence by Proposition 2.5.1, C is not a B set in $P_\omega$.

(iii) For all $x$ in $C_i$, and for all $y$ in $C_j$, $x \prec y = \emptyset$ whenever $i \neq j$.

(iv) Given any $x$ in C, there exists only finitely many $y$'s in C such that $x$ is a subset of $y$.

(v) C is closed under chain because there isn't any strictly increasing infinite chain in C. $C^c$ is also closed under chain because $C^c$ contains all infinite subsets of $\omega$. Hence by Proposition 2.4.1, C is a $B_\sigma \cap B_\delta$ set in $P_\omega$.
(vi) Note $P_{\omega}^{C}=\emptyset$. Otherwise, pick some finite subset $e$ of $\omega$ in $P_{\omega}^{C}$ (which is a $B_{\sigma} \cap B_{\delta}$ set in $P_{\omega}$). By remark(ii) after Proposition 2.5.2, there exists infinitely many subsets $e'$ of $\omega$ in $C$ such that $e$ is a subset of $e'$ - this contradicts (d) above. Also note that $Q_{\omega}^{C}$ is non-empty because $\emptyset$ belongs to $\bigcap_{n \in \omega} Q_{n}^{C} = Q_{\omega}^{C}$. Thus $Q_{\omega}^{C}$ is a non-empty closed set in $P_{\omega}$, and $C$ belongs to $D_{\omega}(P_{\omega})$.
## 2.6: More about chain properties in Pω

We introduced the 'closed under chain' property in 2.2. Here, we introduce two more chain properties, namely:

(a) 'closed under finite chain' property, which is weaker than the 'closed under chain' property; and

(b) 'closed under strong chain' property, which is stronger than the 'closed under chain' property.

We will show that the two chain properties above can also be used to characterize the $B_σ∩B_δ$ sets in Pω.

A subset A of Pω is closed under finite chain if for every increasing chain $\{x_i\}_{i∈ω}$ of finite subsets of ω in E, the union $\bigcup_{i∈ω} x_i$ belongs to E. It is clear that if A⊆Pω is closed under chain, then A is closed under finite chain. There exists a subset A of Pω such that A is closed under finite chain but A is not closed under chain. Let A be the set $\{b_i∪ua | i∈ω\}$ where $a=\{2k|k∈ω\}$ and $b_i=\{0, ..., i-1, i\}$. A is closed under finite chain because there isn't any increasing chain of finite subsets of ω in A (in fact, A doesn't even have any finite subset of ω). A is not closed under chain because $ω=\bigcup_{i∈ω} (b_i∪ua)$ is not in A. Thus the 'closed under finite chain' property is weaker than the 'closed under chain' property.

Next we introduce a semi-finitary notion in Pω to characterize the subsets in Pω which are closed under finite chain. A⊆Pω has semi-finitary property if for each x in A, there exists some finite subset e of x such that all the finite subsets of ω in $W_x∩U_e$ are in A. It is clear that if A⊆Pω has finitary property, then A has semi-finitary property.
There exists a subset A of P<sub>ω</sub> such that A has semi-finitary property but A does not have finitary property. Let E<sub>C</sub> denote the set { w \ i | i ∈ ω } . Now take A to be E<sup>C</sup>. A has semi-finitary property because all the finite subsets of ω are in A. A does not have finitary property, for otherwise there exists some finite subset e of ω such that U<sub>e</sub> is a subset of A - this is clearly false by our definition of E. Thus the semi-finitary property is weaker than the finitary property. We are going to show that for subsets A of P<sub>ω</sub>, A has semi-finitary property if and only A<sup>C</sup> is closed under finite chains. The easy direction is the following:

**Proposition 2.6.1**

If A<sub>C</sub> has semi-finitary property, then A<sup>C</sup> is closed under finite chain.

**Proof** : Suppose A<sub>C</sub> has semi-finitary property and A<sup>C</sup> is not closed under finite chain. Thus we can find some increasing sequence {x<sub>i</sub>}<sub>i∈ω</sub> of finite subsets of ω in A<sup>C</sup> such that x = ⋃<sub>i∈ω</sub> x<sub>i</sub> belongs to A. Since A has semi-finitary property, there exists some finite subset e of x such that all the finite subsets of ω in W<sub>x</sub>∩U<sub>e</sub> are in A. Now e∩x implies e∩x<sub>i</sub> for some i in ω because {x<sub>i</sub>}<sub>i∈ω</sub> is an increasing chain and e is a finite subset of ω. Hence x<sub>i</sub> belongs to A, contradiction. □

Conversely,

**Proposition 2.6.2**

If A<sub>C</sub> is closed under finite chain, then A<sup>C</sup> has semi-finitary property.

**Proof** : Suppose A<sub>C</sub> is closed under finite chain and A<sup>C</sup> does not have semi-finitary property. Let x be some element in A<sup>C</sup> contradicting the semi-finitary property, i.e. for each finite subset e of x in A<sup>C</sup>, there exists some finite subset e' of ω in W<sub>x</sub>∩U<sub>e</sub> such that e'
belongs to A. Using induction, we define two increasing sequences
{$x_i$} and {$y_i$} of finite subsets of $\omega$ in $A^\omega$ and A
respectively as follows:

i=0 : Write x as the union of some increasing sequence of initial
segments of x ( y<x is an initial segment of x if y is a finite
subset of w and for all n in x, ney implies n≤z for all z
in y ) . If all the initial segments of x belong to A , then x is
in A since A is closed under finite chain . As x belongs to A<sup>c</sup> ,
there exists some initial segment x<sub>0</sub> of x in A<sup>c</sup> . Since x
contradicts the semi-finitary property , we can find some finite subset
y<sub>0</sub> of w in W_x^n U_x<sub>0</sub> such that y<sub>0</sub> belongs to A .

i=k+1 :

(i) Assume $y_k$ has been defined and is a finite subset of x in A.
Now write x as the union of some increasing sequence of initial
segments z of x such that $y_k$ is a subset of z. If all these z's
are in A, then x is in A as A is closed under finite chain. As
x is in $A^c$, there exists some initial segment z of x in $A^c$ such
that $y_k$ is a subset of z.

(ii) Assume $x_k$ has been defined and is a finite subset of x in $A^c$.
Since x contradicts the finitary property, we can find some finite
subset $y_{k+1}$ of w in $W_x \cap U_{x_k}$ such that $y_{k+1}$ belongs to A.
It is clear from our construction above that x is equal to $\bigcup_{i \in w} x_i$
and $\bigcup_{i \in w} y_i$. As A is closed under finite chain, x ($= \bigcup_{i \in w} y_i$) belongs
to A, contradiction. Hence $A^c$ has semi-finitary property. □
**Proposition 2.6.3**

For subsets A of P<sub>ω</sub>, A is B<sub>σ</sub>∩B<sub>δ</sub> if and only if A and A<sup>C</sup> are closed under finite chain.

Proof : (⇒) If A is a B<sub>σ</sub>∩B<sub>δ</sub> set, then A and A<sup>C</sup> are closed under chain, hence they are closed under finite chain.

(⇔) In our proof of Proposition 2.4.1, we only assume that A and A<sup>C</sup> are closed under finite chain to show that A is B<sub>σ</sub>∩B<sub>δ</sub>. □

Next we introduce the notion of 'closed under strong chain' in P<sub>ω</sub>.

A<sub>C</sub>P<sub>ω</sub> is closed under strong chain if whenever {x<sub>i</sub>}<sub>i∈ω</sub> is a sequence of elements in A such that x̄<sub>i</sub> ≤ x̄<sub>i+1</sub> for all i in ω and lim<sub>i∈ω</sub> x̄<sub>i</sub> = x̄ = ⋃<sub>i∈ω</sub> x<sub>i</sub>, then ⋃<sub>i∈ω</sub> x<sub>i</sub> belongs to A. (Here, for a given x<sub>c</sub>ω, x̄ denotes the binary real number 0·x<sub>0</sub>(0)x<sub>1</sub>(1)x<sub>2</sub>(2).... x(i).... where for i in ω,

$$x(i) = \begin{cases} 1 & \text{if } i \in x \\ 0 & \text{if otherwise} \end{cases}$$

Thus elements of P<sub>ω</sub> are mapped to binary real numbers in [0, 1] under <sub>c</sub>. denotes the usual 'less than' in [0, 1]. )

It is clear that if a subset A of P<sub>ω</sub> is closed under strong chain, then it is closed under chain. There exists a subset A of P<sub>ω</sub> such that A is closed under chain but A is not closed under strong chain. Let A be {ω\i | i∈ω}. A is closed under chain because there is no strictly increasing chain in A. A is not closed under strong chain. To see this, note that for every i in ω, a<sub>i</sub>(j)=1 for all j∈ω except j=i. It follows ā<sub>i</sub> ≤ ā<sub>i+1</sub> for all integers i. Now lim<sub>i∈ω</sub> ā<sub>i</sub> = 0·1111.... = ω̄ = ⋃<sub>i∈ω</sub> ā<sub>i</sub>. But ω does not belong to A.

We are going to demonstrate that for subsets A of P<sub>ω</sub>, A has finitary property if and only if A<sup>C</sup> is closed under strong chain. The easy direction is the following:
**Proposition 2.6.3**

If $A \subset P_\omega$ has finitary property, then $A^c$ is closed under strong chain.

**Proof:** Assume $A \subset P_\omega$ has finitary property and $\{x_i\}_{i \in \omega}$ is a sequence of elements in $A^c$ satisfying $\overline{x_i} \le \overline{x_{i+1}}$ for all $i$ in $\omega$ and $\lim_{i \in \omega} \overline{x_i} = \bigcup_{i \in \omega} x_i$. Suppose $x = \bigcup_{i \in \omega} x_i$ belongs to $A$. Hence there exists some finite subset $e$ of $x$ such that $W_x \cap U_e$ is a subset of $A$. Now $\overline{e} \le \lim_{i \in \omega} \overline{x_i} = \bigcup_{i \in \omega} x_i$. Since $e$ is a finite subset of $\omega$, there exists some $j$ in $\omega$ such that for all integers $i$, $e \subset x_i$ whenever $j \le i$. This contradicts the assumption that all the $x_i$'s ($i \in \omega$) are in $A^c$. $\square$

Conversely,

**Proposition 2.6.4**

If $A \subset P_\omega$ is closed under strong chain, then $A^c$ has finitary property.

**Proof:** Suppose $A \subset P_\omega$ is closed under strong chain and $A^c$ does not have finitary property - hence there exists some $x$ in $A^c$ such that for every finite subset $e$ of $x$ in $A^c$, there exists some $y$ in $W_x \cap U_e$ such that $y$ belongs to $A$.

Using induction, we are going to construct a sequence of elements $\{x_i\}_{i \in \omega}$ in $A$ with the following properties:

(i) $\overline{x_i} \le \overline{x_{i+1}}$ for all integers $i$

(ii) $x = \bigcup_{i \in \omega} x_i$

(iii) $\lim_{i \in \omega} \overline{x_i} = \bigcup_{i \in \omega} x_i$

At the same time, we define a sequence of elements $\{y_i\}_{i \in \omega}$ with the following properties:

(i) $y_i$ is a finite subset of $x_i$ for all integers $i$

(ii) $x = \bigcup_{i \in \omega} y_i$
i=0 : Set $y_0$ = smallest integer j such that $j \in x$. Let $x_0$ be
any subset of $\omega$ in A satisfying $y_0 \subset x$.

i+1 : Assume {x_j}_{j≤i} and {y_j}_{j≤i} have been defined and satisfy the required properties. Since x_i belongs to A (note x_i ⊂ x), x_i is different from x. Therefore there exists some integer k such that k ∈ x, k ⊂ x_i, and for all integers j less than k, j belongs to x_i if and only if j belongs to x. Now set y_{i+1} = {k} ∪ { j ∈ ω | j < k and j ∈ x_i } - in other words, the elements in y_{i+1} are all the elements in x which are less than or equal to k. Let x_{i+1} be any subset of ω in A satisfying y_{i+1} ⊂ x_{i+1}.

We now verify that {$x_i$}$_{i \in \omega}$ and {$y_i$}$_{i \in \omega}$ satisfy the stated properties.
All the properties except (i) for {$x_i$}$_{i \in \omega}$ are clear from our
construction. To see $x_i \subsetneq x_{i+1}$ for all integers $i$, note that $k$
(as defined in our definition of $y_{i+1}$) belongs to $x_{i+1}$ whereas
$k$ does not belong to $x_i$, and for all integers $j$ less than $k$,
$j$ belongs to $x_i$ if and only if $j$ belongs to $x_{i+1}$.

Since A is closed under strong chain, $x = \bigcup_{i \in \omega} x_i$ belongs to A,
contradiction. □

As all the $B_\sigma$ sets in $P\omega$ have finitary property and the notion
of 'closed under strong chain' is stronger than the notion of 'closed under
finite chain', it follows from Proposition 2.6.3 that for subsets A of $P\omega$,
A is $B_\sigma \cap B_\delta$ if and only if A and $A^c$ are closed under strong chain.
### 3 : Wadge degrees in P<sub>ω</sub>

Wadge reducibility in $ω^ω$ (see [6]) is used to study the complexity of the Borel sets in $ω^ω$ in terms of the relative levels in the Borel hierarchy $\{F_α(ω^ω)\}_{α<Ω}$. Here, we study Wadge reducibility in P<sub>ω</sub> which is defined in terms of Wadge reducibility in $ω^ω$. In this section, we show that the structure of Wadge degrees of $B_σ∩B_δ$ sets in P<sub>ω</sub> is isomorphic to the structure of Wadge degrees of $F_σ∩G_δ$ sets in $ω^ω$.

We are indebted to B. Wadge for many invaluable hints.

#### 3.1 : Wadge reducibility in P<sub>ω</sub>

Given subsets A, B in $ω^ω$, A is Wadge reducible (abbreviated as $A≤_W B$) to B if there exists a continuous function $f:ω^ω→ω^ω$ such that $A=f^{-1}(B)$.
In [6], it is shown that this notion of reducibility can be given game-theoretically. Consider the following two-person game G(A,B) between Player I and Player II. Player I moves first and picks some integer. Player II moves next and also picks an integer. In general, Players I and II move consecutively and they pick an integer at each move. We can use reals α and β to code Player I's moves and Player II's moves as follows : for $n∈ω$, $α(n)$ denotes Player I's n<sup>th</sup> move and $β(n)$ denotes Player II's n<sup>th</sup> move. Player I wins the game if $α∈A \Leftrightarrow β∈B$. A strategy by Player II is a continuous function $τ:ω^ω→ω^ω$ such that for $α∈ω^ω$ (the real played by I) and $n∈ω$, $β(n)=τ(α)(n)$. The relation between Wadge reducibility in $ω^ω$ and the game G(A,B) is as follows : $A≤_W B$ if and only if Player II has a winning strategy in the game G(A,B).
We define the enumeration map $p$ from $\omega^\omega$ to $P_\omega$ as follows : for $\alpha \in \omega^\omega$,
$p(\alpha) = \{ n \in \omega \mid (\exists m \in \omega)(\alpha(m)=n+1 ) \} $ - thus $p$ codes the positive range of $\alpha$
into a set of integers . It is not difficult to verify that $p$ is a continuous
map from $\omega^\omega$ onto $P_\omega$ . Wadge reducibility in $P_\omega$ is defined as follows :
for subsets $A, E$ of $P_\omega$, $A$ is Wadge reducible ( also abbreviated as $\leq_W$ )
to $E$ if $p^{-1}(A)$ is Wadge reducible to $p^{-1}(E)$ in $\omega^\omega$ .

We collect here some of the results on Wadge reducibility in $\omega^\omega$ from [6] :

(W1) Suppose $A, E$ are Borel sets in $\omega^\omega$, then either Player I or Player II has a winning strategy in the game $G(A,E)$; hence $A \leq_W E$ or $E^C \leq_W A$.

(W2) Say that $A$ is a genuine $D_\alpha(\omega^\omega)$ set if $A$ belongs to $D_\alpha(\omega^\omega)$ and $A \notin D_\beta(\omega^\omega) \cup \hat{D}_\beta(\omega^\omega)$ for all $\beta < \alpha$. If $A$ is a genuine $D_\alpha(\omega^\omega)$ set and $E$ is a genuine $D_\beta(\omega^\omega)$ set, then $A \leq_W E \Leftrightarrow \alpha \leq \beta$.

(W3) The $F_\sigma \setminus G_\delta$ sets in $\omega^\omega$ form a Wadge degree, so do the $G_\delta \setminus F_\sigma$ sets.

As Wadge reducibility in P<sub>ω</sub> is defined in terms of Wadge reducibility
in ω<sup>ω</sup>, the two reducibilities share many properties in common. For example,
(i) for subsets A, E of P<sub>ω</sub>, A ≤<sub>ω</sub> E <span style="font-size: smaller;">⇔</span> A<sup>C</sup> ≤<sub>ω</sub> E<sup>C</sup> ;
(ii) if A, E are Borel sets in P<sub>ω</sub>, then A ≤<sub>ω</sub> E or E<sup>C</sup> ≤<sub>ω</sub> A .
They differ in the following two properties:

(i) $A \not\subseteq W A^C$ for any subset $A$ of $P^\omega$, and

(ii) least upper bound of any strictly increasing sequence of Wadge degrees of Borel sets in P<sub>ω</sub> does not exist ( where we assume that given any set A in the sequence, there exists some other set E in the sequence whose degree is strictly greater than that of A, i.e. A < E ).
**Proposition 3.1.1**

A $\subsetneq_{w}^{<}$ A$^{C}$ for any subset A of Pw.

**Proof :** Assume $A \subsetneq_{w}^{<} A^{C}$ for some subset A of Pw, hence Player II has a winning strategy in the game $G(p^{-1}(A), p^{-1}(A^{C}))$. We derive a contradiction by exhibiting a winning strategy for Player I in the game $G(p^{-1}(A), p^{-1}(A^{C}))$. Player I plays 0 in his first move. In the $n+1$<sup>th</sup> move ($n \in \omega$), Player I plays the integer which is played by Player II in the $n$<sup>th</sup> move. Hence at the end of the game, the reals played by both players have the same positive range, so Player I wins. ☐

**Proposition 3.1.2**

Assume {$A_i$}$_{i<\alpha}$ is an $\alpha$-sequence of Borel sets in Pw where $\alpha$ is a limit ordinal and $A_i \subsetneq_{w} A_{i+1}$ (abbreviated for $A_i \subsetneq_{w} A_{i+1} \& A_{i+1} \subsetneq_{w} A_i$) for $i<\alpha$, then least upper bound of the Wadge degrees of $A_i$ ($i<\alpha$) does not exist.

**Proof :** Given {$A_i$}$_{i<\alpha}$ satisfying the hypothesis, assume least upper bound of the Wadge degrees of $A_i$ ($i<\alpha$) exists and $E \subsetneq_{w} Pw$ is of such a degree. We derive a contradiction by demonstrating $E \subsetneq_{w} E^C$.

**Claim :** for Borel sets A and A', $A \subsetneq_{w} A'$ implies $A^{C} \subsetneq_{w} A'$.

**Proof :** Suppose $A \subsetneq_{w} A'$. Since A, A' are Borel sets, either $A^{C} \subsetneq_{w} A'$ or $A' \subsetneq_{w} A$. If $A' \subsetneq_{w} A$ holds, then $A \subsetneq_{w} A' \subsetneq_{w} A$, hence $A \subsetneq_{w} A'$, contradicting Proposition 3.1.1. Hence $A^{C} \subsetneq_{w} A'$.

**Claim :** $E \subsetneq_{w} E^C$

**Proof :** It suffices to show that for all $i<\alpha$, $A_i \subsetneq_{w} E^C$ holds. This follows from the last claim and the hypothesis that for each $i<\alpha$, $A_i \subset E$.

The last claim gives us the contradiction. ☐
### 3.2: Wadge degrees of $B_\sigma$ sets and $B_\delta$ sets in $P\omega$

Here, we show that for subsets $A$ of $P\omega$ and $\alpha<\Omega$, $A$ belongs to $D_\alpha(P\omega)$ if and only if $p^{-1}(A)$ belongs to $D_\alpha(\omega^\omega)$. From this and (W2) in 3.1, it follows trivially that if $A$ is a genuine $D_\alpha(P\omega)$ set and $E$ is a genuine $D_\beta(P\omega)$ set, then $A \leq_E E \iff \alpha \leq \beta$. It also follows that the $B_\sigma \setminus B_\delta$ sets in $P\omega$ are of the same Wadge degree, so are the $B_\delta \setminus B_\sigma$ sets.

First, we study some properties of the enumeration map $p$. To this end, we define an equivalence relation $\equiv_p$ in $\omega^\omega$ as follows: for $\alpha, \beta$ in $\omega^\omega$, $\alpha \equiv_p \beta \iff p(\alpha)=p(\beta)$, i.e. $\alpha$ and $\beta$ have the same positive range. For subsets $A$ of $\omega^\omega$, let $A^*$ denote the transitive closure of $A$ with respect to $\equiv_p$.

#### Proposition 3.2.1

(i) $p$ is an open map.

(ii) Suppose $F$ is a family of subsets in $P\omega$, then $(\bigcup_{A\in F} A)^* = \bigcup_{A\in F} A^*$.

(iii) $A\subset P\omega$ is open $\Rightarrow A^*$ is open.

(iv) $p$ is not a closed map.

(v) If $A\subset P\omega$ is a closed set and $A=A^*$, then $p(A)$ is a closed set.

**Proof :** (i) It suffices to show that $p$ maps every basic interval in $\omega^\omega$ (by a basic interval in $\omega^\omega$, we mean a set of the form $\{\alpha \in \omega^\omega | \alpha(n)=m\}$) to an open set in $P\omega$. This is trivial because :
$$p(\{\alpha \in \omega^\omega | \alpha(n)=m\}) = \{x \in \omega^\omega | m-1 < x\} \text{ whenever } m \text{ is positive}$$

(ii) the proof of this is trivial.

(iii) By (ii), it suffices to show that for every basic interval $I = \{\alpha \in \omega^\omega | \alpha(n)=m\}$ in $\omega^\omega$, $I^*$ is an open set in $\omega^\omega$. Note $I^*$ is the set $\bigcup_{i \in \omega^\omega} \{\alpha \in \omega^\omega | \alpha(i)=m\}$ which is clearly an open set in $\omega^\omega$.
(iv) Let {$\alpha$} be any element in $\omega^\omega$ with an infinite range. {$\alpha$} is a closed set in $\omega^\omega$, but $p({\alpha})$ is not even a $B_\sigma$ set in $P\omega$, as a consequence of Proposition 2.2.1.

(v) Suppose $A\subset P\omega$ is closed. By (i), $p(A^c)$ is an open set in $P\omega$. Since $A=A^*$ and $p$ is an onto map, $p(A^c)$ is equal to $[p(A)]^c$. Hence $p(A)$ is closed. [ ]

From Proposition 3.2.1(v), we conclude that for subsets A of Pω,
A belongs to D₀(Pω) if and only if p⁻¹(A) belongs to D₀(ω⁹) . We can
interpret the latter fact as an equation , namely : p⁻¹[D₀(Pω)] = D₀(ω⁹) ∩ K
where K is the inverse range of the enumeration map p , i.e.

$K = \{ p^{-1}(E) | E \subset P\omega \}$. Note that $K$ is identical to the family $\{ A \subset P\omega | A = A^* \}$.
In the following, we demonstrate that for all $\alpha < \Omega$, $p^{-1}[D_\alpha(P\omega)] = D_\alpha(\omega^\alpha) \cap K$.
Hence $p^{-1}[B_\sigma \cap B_\delta] = [F_\sigma \cap G_\delta(\omega^\omega)] \cap K$.

**Lemma 3.2.2**

$K$ is closed under the closure operation, i.e. $A \in K \Rightarrow Cl(A) \in K$.

Proof : We need to show the following : if $x \in Cl(A)$ and $x \equiv_p y$, then $y \in Cl(A)$.

Given $x$ in $Cl(A)$, let $\{x_i\}_{i \in \omega}$ be any sequence of elements in $A$
such that $x=\lim_{i \in \omega} x_i$. We shall define a sequence of elements $\{y_i\}_{i \in \omega}$
in $A$ such that :

(i) $y = \lim_{i \in \omega} y_i$ and

(ii) for each $i \in \omega$, $y_i(k)=y(k)$ whenever $k \le i$.

Given $i \in \omega$, let $b_i$ be the finite set $\{ y(k) \mid k \le i, y(k) \text{ is positive} \}$.
$x \equiv_p y$ and $x = \lim_{j \in \omega} x_j$, one of the $x_j$'s must contain $b_i$ in its range,
say $z$. Define $y_i$ in $\omega^\omega$ as follows :

$y_i(k) = y(k) \quad \text{whenever} \quad k \le i$

$y_i((i+m)) = z(m) \quad \text{whenever } m \in \omega \text{ and } 1 \le m$
Observe $y_i \equiv \bar{p}_i z$. Consequently $y_i$ belongs to $A$. It is clear from our definition of $y_i$'s that $y_i$'s satisfy (i) and (ii) above. Hence $y=\lim_{i \in \omega} y_i$ belongs to $C1(A)$. $\square$

**Lemma 3.2.3**

For subsets $E$ of $P\omega$, $C1[p^{-1}(E)] = p^{-1}[C1(E)]$.

**Proof :** Clearly $C1[p^{-1}(E)]$ is a subset of $p^{-1}[C1(E)]$ because $p^{-1}[C1(E)]$ is a closed set in $\omega^\omega$ containing $p^{-1}(E)$. To show that $p^{-1}[C1(E)]$ is a subset of $C1[p^{-1}(E)]$, suppose $x$ belongs to $p^{-1}[C1(E)]$. We shall define a sequence of elements $\{x_i\}_{i \in \omega}$ in $p^{-1}(E)$ such that $x=\lim_{i \in \omega} x_i$. Given $i$ in $\omega$, let $b_i$ be the set $\{x(k)-1 \mid k \le i\}$ and $x(k)$ is positive. Note that $b_i$, being a subset of $p(x)$, belongs to $C1(E)$. By Lemma 2.3.3, there exists some $z$ in $U_{b_i} \cap E$. Now take any element $\beta$ in $p^{-1}(z)$ and define $x_i \in \omega^\omega$ as follows :

$$x_i(k) = x(k) \quad \text{if } k \le i$$ 
$$x_i(i+m) = \beta(m) \quad \text{for } m \in \omega \text{ and } 1 \le m$$

Note $x_i \equiv \bar{p}_i \beta$. Also note that $x_i$ belongs to $p^{-1}(E)$ because $x_i \equiv \bar{p}_i \beta$ and $\beta$ belongs to $p^{-1}(E)$ which is closed under $\equiv \bar{p}_i$. It follows from our definition of $x_i$'s that $x=\lim_{i \in \omega} x_i$, hence $x \in C1[p^{-1}(E)]$. $\square$

**Lemma 3.2.4**

For $A \in K$, $p[C1(A)] = C1[p(A)]$.

**Proof :** Since $A=A^*$, $p^{-1}[p(A)]$ is equal to $A$. Now apply Lemma 3.2.3. $\square$

**Lemma 3.2.5**

For subsets $A_1, A_2$ in $K$, $p(A_1) \setminus p(A_2) = p(A_1 \setminus A_2)$.

**Proof :** Clearly $p(A_1) \setminus p(A_2)$ contains $p(A_1 \setminus A_2)$. To show that $p(A_1) \setminus p(A_2)$ is a subset of $p(A_1 \setminus A_2)$, consider any element $x$ in $p(A_1) \setminus p(A_2)$.
Observe $p(A_1) \cap p(A_2) = p(A_1) \cap [p(A_2)]^c = p(A_1) \cap p(A_2)^c$ ( $[p(A_2)]^c$ is equal to $p(A_2)^c$ because $A_2^* = A_2$ and $p$ is an onto map ). So there exists $z_1, z_2$ in $A_1$ and $A_2^c$ respectively such that $p(z_1) = p(z_2) = x$. Hence $z_1 \equiv_p z_2$. Since $A_1$ and $A_2$ are in $K$, we conclude that $z_1$ and $z_2$ both belong to $A_1 \cap A_2^c$ ( or $A_1 \setminus A_2 $ ). Therefore $x$ belongs to $p(A_1 \setminus A_2)$. $\square$

**Proposition 3.2.6**

For subsets $E$ of $P\omega$ and $\alpha<\Omega$, $E$ belongs to $D_\alpha(P\omega)$ if and only if $p^{-1}(E)$ belongs to $D_\alpha(\omega^\omega)$. Hence $E$ is a $B_\sigma \cap B_\delta$ set in $P\omega$ if and only if $p^{-1}(E)$ is a $F_\sigma \cap G_\delta$ set in $\omega^\omega$.

**Proof :** ($\Rightarrow$) This follows from the continuity of $p$. ($\Leftarrow$) Suppose $p^{-1}(E)=A$ is in $D_\alpha(\omega^\omega)$. We consider the Hausdorff sequences $\{P_\beta^A\}_{\beta\le\alpha}$, $\{Q_\beta^A\}_{\beta\le\alpha}$ obtained from $A$, as well as the Hausdorff sequences $\{P_\beta^E\}_{\beta\le\alpha}$, $\{Q_\beta^E\}_{\beta\le\alpha}$ obtained from $E$.

Claim : For $\beta \le \alpha$, $P_{\beta}^{A}$ and $Q_{\beta}^{A}$ are in $K$.

**Proof :** We prove by induction on $\beta \le \alpha$.

$\beta=0$ :

$P_0^A = A$ and $Q_0^A = A^c$ are obviously in $K$.

$\beta+1$ : Assume $P_\beta^A$ and $Q_\beta^A$ are in $K$.

$Q_{\beta+1}^A = C1(P_\beta^A) \cap A^c$ is in $K$ since $C1(P_\beta^A)$ is in $K$.

$P_{\beta+1}^A = C1(Q_{\beta+1}^A) \cap A$ is in $K$ since $C1(Q_{\beta+1}^A)$ is in $K$.

$\beta$ is a limit ordinal : Assume $P_\gamma^A$, $Q_\gamma^A$ are in $K$ for all $\gamma<\beta$.

$Q_\beta^A = \bigcap_{\gamma<\beta} Q_\gamma^A$ and $P_\beta^A = \bigcap_{\gamma<\beta} P_\gamma^A$, both being the intersection of sets in $K$, belong to $K$.
Claim : For $\beta<\alpha$, $p(P_\beta^A)=P_\beta^E$ and $p(Q_\beta^A)=Q_\beta^E$.

Proof : We prove by induction on $\beta<\alpha$.

$\beta=0$ :

$p(P_0^A)=p(A)=E$ and $p(Q_0^A)=p(A^C)=E^C$.

$\beta+1$ : Assume $p(P_\beta^A)=P_\beta^E$ and $p(Q_\beta^A)=Q_\beta^E$.

$p(Q_{\beta+1}^A) = p[C_1(P_\beta^A) \setminus A] = p[C_1(P_\beta^A)] \setminus p(A) = C_1[p(P_\beta^A)] \setminus p(A)$
$= C_1(P_\beta^E) \setminus E = Q_{\beta+1}^E$ ( by Lemma 3.2.2, 3.2.4, 3.2.5 & the last claim )

$p(P_{\beta+1}^A) = p[C_1(Q_{\beta+1}^A) \setminus A^C] = p[C_1(Q_{\beta+1}^A)] \setminus p(A^C) = C_1[p(Q_{\beta+1}^A)] \setminus p(A^C)$
$= C_1(Q_{\beta+1}^E) \setminus E^C = P_{\beta+1}^E$ ( by Lemma 3.2.2, 3.2.4, 3.2.5 & the last claim )

$\beta$ is a limit ordinal : Assume $p(P_\gamma^A)=P_\gamma^E$ and $p(Q_\gamma^A)=Q_\gamma^E$ for $\gamma<\beta$.

$p(Q_\beta^A) = p(\bigcap_{\gamma<\beta} Q_\gamma^A)$
$= \bigcap_{\gamma<\beta} p(Q_\gamma^A)$
(since all the $Q_\gamma^A$'s, $\gamma<\beta$, are in $K$)
$= \bigcap_{\gamma<\beta} Q_\gamma^E = Q_\beta^E$

$p(P_\beta^A) = p(\bigcap_{\gamma<\beta} P_\gamma^A)$
$= \bigcap_{\gamma<\beta} p(P_\gamma^A)$
(since all the $P_\gamma^A$'s, $\gamma<\beta$, are in $K$)

$= \bigcap_{\gamma<\beta} p_\gamma^E = p_\beta^E$

This proves the claim.

Now,

$p^{-1}(E) = [C_1(A) \setminus C_1(Q_1^A)] \cup [C_1(P_1^A) \setminus C_1(Q_2^A)] \cup \dots \cup [C_1(P_\beta^A) \setminus C_1(Q_{\beta+1}^A)] \cup \dots$ ($\beta<\alpha$)

Hence,

E

$= p[C_1(A) \setminus C_1(Q_1^A)] \cup p[C_1(P_1^A) \setminus C_1(Q_2^A)] \cup \dots \cup p[C_1(P_\beta^A) \setminus C_1(Q_{\beta+1}^A)] \cup \dots$ ($\beta<\alpha$)

$= \{p[C_1(A)] \setminus p[C_1(Q_1^A)]\} \cup \{p[C_1(P_1^A)] \setminus p[C_1(Q_2^A)]\} \cup \dots \cup \{p[C_1(P_\beta^A)] \setminus p[C_1(Q_{\beta+1}^A)]\} \cup \dots$

( by Lemma 3.2.2, 3.2.5 and the first claim )
$$ = \{\mathrm{Cl}[\mathrm{p}(A)] \cap \mathrm{Cl}[\mathrm{p}(Q_1^A)]\} \cup \{\mathrm{Cl}[\mathrm{p}(P_1^A)] \cap \mathrm{Cl}[\mathrm{p}(Q_2^A)]\} \cup \dots \cup \{\mathrm{Cl}[\mathrm{p}(P_\beta^A)] \cup \mathrm{Cl}[\mathrm{p}(Q_{\beta+1}^A)]\} \cup \dots \\ (\beta < \alpha) $$

(by Lemma 3.2.4 and the first claim)

$$ = [\mathrm{Cl}(E) \cap \mathrm{Cl}(Q_1^E)] \cup [\mathrm{Cl}(P_1^E) \cap \mathrm{Cl}(Q_2^E)] \cup \dots \cup [\mathrm{Cl}(P_\beta^E) \cap \mathrm{Cl}(Q_{\beta+1}^E)] \cup \dots \quad (\beta < \alpha) $$
(by the second claim)

Hence $E$ belongs to $D_\alpha(P^\omega)$. $\square$

### Corollary 3.2.7

The structure of Wadge degrees of $B_\sigma \cap B_\delta$ sets in $P^\omega$ is isomorphic to the structure of Wadge degrees of $F_\sigma \cap G_\delta$ sets in $\omega^\omega$. Hence, the genuine $D_\alpha(P^\omega)$ sets form a Wadge degree for each $\alpha < \Omega$. And if $A$ is a genuine $D_\alpha(P^\omega)$ set and $E$ is a genuine $D_\beta(P^\omega)$ set, then $A \preceq_W E$ if and only if $\alpha \le \beta$.

### Corollary 3.2.8

If $A$ is a $B_\sigma \setminus B_\delta$ set in $P^\omega$, then $p^{-1}(A)$ is a $F_\sigma \setminus G_\delta$ set in $\omega^\omega$; similarly, if $A$ is a $B_\delta \setminus B_\sigma$ set in $P^\omega$, then $p^{-1}(A)$ is a $G_\delta \setminus F_\sigma$ set in $\omega^\omega$. Hence by (W3) in 3.1, the $B_\sigma \setminus B_\delta$ sets in $P^\omega$ are of the same Wadge degree, so are the $B_\delta \setminus B_\sigma$ sets in $P^\omega$.

As a further application of Proposition 3.2.6, we give a different proof of Proposition 2.3.5(b) which says that $D_{\alpha+1}(P^\omega) \cap \hat{D}_{\alpha+1}(P^\omega)$ is equal to $D_\alpha(P^\omega) \cup \hat{D}_\alpha(P^\omega)$ for each $\alpha < \Omega$. The non-trivial direction is to show that $D_{\alpha+1}(P^\omega) \cap \hat{D}_{\alpha+1}(P^\omega)$ is a subfamily of $D_\alpha(P^\omega) \cup \hat{D}_\alpha(P^\omega)$. Assume that there exists a set $A$ in $[D_{\alpha+1}(P^\omega) \cap \hat{D}_{\alpha+1}(P^\omega)] \setminus [D_\alpha(P^\omega) \cup \hat{D}_\alpha(P^\omega)]$. Note that $A^c$ also belongs to $[D_{\alpha+1}(P^\omega) \cap \hat{D}_{\alpha+1}(P^\omega)] \setminus [D_\alpha(P^\omega) \cup \hat{D}_\alpha(P^\omega)]$. By Proposition 3.2.6, $p^{-1}(E)$ and $p^{-1}(E^c)$ are both $[D_{\alpha+1}(\omega^\omega) \cap \hat{D}_{\alpha+1}(\omega^\omega)] \setminus [D_\alpha(\omega^\omega) \cup \hat{D}_\alpha(\omega^\omega)]$ sets. By (W2) in 3.1, $p^{-1}(E) = p^{-1}(E^c)$, hence $E = E^c$, contradicting Proposition 3.1.1.
## 4 : Enumeration degrees in Pω

Here, we study another notion of reducibility among subsets of Pω, namely, enumeration reducibility (abbreviated as $A \leq_e C$). Enumeration reducibility is stronger than Wadge reducibility. Unlike Wadge reducibility, the $B_δ \setminus B_α$ sets in Pω are not of the same enumeration degree. Besides, it is no longer true that either $A \leq_e E$ holds or $E \subseteq_e A$ holds for arbitrary pair of Borel sets A, E in Pω.

### 4.1 : Enumeration reducibility in Pω

Given subsets A, C of Pω, A is enumeration reducible to C (abbreviated as $A \leq_e C$) if there exists a continuous function f : Pω → Pω (f serves as an enumeration operator) such that $A=f^{-1}(C)$. Alike Wadge reducibility in $ω^ω$, enumeration reducibility can be defined in terms of a two-person game. Consider the following game G'(A,C) between Player I and Player II. Player I moves first and picks a subset of ω. Player II moves next and also picks a subset of ω. In general, Player I and Player II move consecutively and they pick a subset of ω (which may be empty) at each turn. For $n \in ω$, let $a_n$ denote the set of integers which have been displayed by Player I up to and including Player I's $n+1^{th}$ move, and $c_n$ denote the set of integers which have been displayed by Player II up to and including Player II's $n+1^{th}$ move. Player II wins the game G'(A,C) if the following condition is
satisfied : $a = \bigcup_{n \in \omega} a_n$ belongs to A if and only if $c = \bigcup_{n \in \omega} c_n$ belongs to C.
A strategy by Player II is a continuous function $f : P_\omega \to P_\omega$ such that for
$n \in \omega$, $b_n = f(a_n)$. It is now clear that A is enumeration reducible to C if
and only if Player II has a winning strategy in the game $G'(A,C)$.

Suppose A is enumeration reducible to C via $f$, we show why A is Wadge
reducible to C in $P^\omega$ (or $p^{-1}(A)$ is Wadge reducible to $p^{-1}(C)$ in $\omega^\omega$).
For $a \in \omega$, let $a'$ denote the set $\{ m-1 \mid m \text{ is a positive integer in } a \}$
(Thus $\{1,2\}'=\{0,1\}$ , $\{0,2\}'=\{1\}$ , $\{\text{even integers}\}'=\{\text{odd integers}\}$). Define
$\tau : \omega^\omega \to \omega^\omega$ as follows : for $\alpha \in \omega^\omega$ and $n \in \omega$,

$$
\tau(\alpha)(0) = \begin{cases} \{\text{least integer in } f[\alpha(0)]\} + 1 & \text{if } f[\alpha(0)] \neq \emptyset \\ 0 & \text{if otherwise} \end{cases}
$$
$$
\tau(\alpha)(n+1) = \begin{cases} \{\text{least integer in } f[\{\alpha(0), \dots, \alpha(n)\}]\} \setminus \{\tau(\alpha)(0), \dots, \tau(\alpha)(n)\} + 1 & \text{( if } f[\{\alpha(0), \dots, \alpha(n)\}] \setminus \{\tau(\alpha)(0), \dots, \tau(\alpha)(n)\} \neq \emptyset \text{)} \\ 0 & \text{( if otherwise )} \end{cases}
$$

$\tau$ is a continuous function and $p[\tau(\alpha)]=f[p(\alpha)]$ for all $\alpha \in \omega^\omega$. Besides, note
$p^{-1}(A)=\tau^{-1}[p^{-1}(C)]$, thus A is Wadge reducible to C in $P^\omega$. Hence
enumeration reducibility is stronger than Wadge reducibility.

As enumeration reducibility is stronger than Wadge reducibility, it
follows immediately from Proposition 3.1.1 that A is not enumeration reducible
to $A^C$ for arbitrary subset A of $P^\omega$. We mention here a direct proof of the
latter fact. Suppose that for some subset A of $P^\omega$, we have $A \subseteq E A^C$ via
some enumeration operator f. Let $x_0$ denote any fixed point of f. Then we
have $x_0 \in A \iff x_0=f(x_0) \in A^C$, contradiction.
The proof of the following proposition is routine.

**Proposition 4.1.1**

Suppose $A \subseteq E$.

(a) If A admits an alternating chain of length $n+1$ ($n \in \omega$), then E also admits an alternating chain of length $n+1$.

(b) If E is closed under chain, then A is also closed under chain.

(c) If E is closed under subset, then A is also closed under subset.

(d) If E is closed under superset, then A is also closed under superset.

**Corollary 4.1.2**

The $B_\delta \setminus B_\sigma$ sets in $P_\omega$ are not of the same enumeration degree.

*Proof:* Put $A = \{\omega\}$ and $E = \{\omega \setminus 0\}$. A and E are both $B_\delta \setminus B_\sigma$ sets in $P_\omega$. By Corollary 3.2.8, A and E are of the same Wadge degree in $P_\omega$. However A is closed under superset while E is not, so we cannot have $E \subseteq A$, as a consequence of Proposition 4.1.1(d). $\square$

**Corollary 4.1.3**

There exists a pair of Borel sets $A, E$ in $P_\omega$ such that $A, A^c, E$ and $E^c$ are all pairwise incomparable in their enumeration degrees.

*Proof:* Put $A = \{\omega \setminus i \mid i \in \omega\}$ ($= \{\text{co-unity subsets of } \omega\}$), and $E = \{\text{co-finite subsets of } \omega\}$. A and E are both Borel sets in $P_\omega$. It suffices to show $A \not\subseteq E$, $A \not\subseteq E^c$, $E \not\subseteq A$ and $E \not\subseteq A^c$.

*Claim:* $A \not\subseteq E$

*Proof:* Since E is closed under superset and A is not, A cannot be enumeration reducible to E as a consequence of Proposition 4.1.2(d).
Claim : $A \subsetneq_e E^C$

Proof : Since $E$ is closed under subset and $A$ is not, $A$ cannot be enumeration reducible to $E$ as a consequence of Proposition 4.1.1(c).

Claim : $E \subsetneq_e A$

Proof : Assume $E$ is enumeration reducible to $A$ via some $f$ in $[P_\omega \to P_\omega]$. Suppose $f$ maps $\omega$ to $\omega\ni i$ for some $i$ in $\omega$. As $f$ is monotonic, $f$ maps all the elements in $E$ to $\omega\ni i$. Since $E$ is equal to $f^{-1}(A)$, we conclude $f^{-1}({\omega\ni i})=E$. But ${\omega\ni i}$ is a $B_\delta$ set in $P_\omega$, hence $E=f^{-1}({\omega\ni i})$ is $B_\delta$, contradicting the fact that $E$ is not a $B_\delta$ set in $P_\omega$.

Claim : $E \subsetneq_e A^C$

Proof : Assume $E$ is enumeration reducible to $A^C$ via some $f$ in $[P_\omega \to P_\omega]$. Suppose $f$ maps $\emptyset$ to $\omega\ni i$ for some $i$ in $\omega$. As $f$ is monotonic, $f$ maps all the elements in $E^C$ to $\omega\ni i$. Since $E$ is equal to $f^{-1}(A^C)$, we conclude $f^{-1}({\omega\ni i})=E^C$. But ${\omega\ni i}$ is a $B_\delta$ set, hence $E^C=f^{-1}({\omega\ni i})$ is $B_\delta$, contradicting the fact that $E^C$ is not a $B_\delta$ set in $P_\omega$.

The last four claims establish the proposition. $\square$
## 4.2: Enumeration degrees of $B_σ∩B_δ$ sets in $Pω$

We show here that Wadge reducibility and enumeration reducibility agree with each other in the domain of $B$ sets, and we construct two $(B_σ∩B_δ)\setminus B$ sets $A, C$ in $Pω$ with $A \equiv_w C$ and $A \not\le_w C$.

### Proposition 4.2.1

If $A \subsetneq Pω$ is a $B$ set and $C \subsetneq Pω$ is a $B_σ∩B_δ$ set, then $A \leq_c C \Leftrightarrow A \leq_w C$.

**Proof :** ($\Rightarrow$) since $\leq_c$ is stronger than $\leq_w$.

($\Leftarrow$) Suppose $A \leq_w C$ and assume that $A$ is non-empty without loss of generality. Since $A$ is a $B$ set, there exists some $n \in ω$ such that $P_n^A$ is non-empty and $P_m^A$ is empty for all $m>n$. As $C$ is $B_σ∩B_δ$ and $A \leq_w C$, it follows from (W2) in 3.1 that $P_n^C$ is also non-empty.

Case (i) : $Q_{n+1}^A$ is empty

Let $x_0$ be any finite subset of $ω$ in $P_n^C$. Now apply the method of proof in Proposition 2.5.2 to obtain an alternating chain $\{x_i\}_{i=0}^{2n}$ with $x_{2j} \in P_{n-j}^C$ (where $2j \le 2n$) and $x_{2j+1} \in Q_{n-j}^C$ (where $2j+1 \le 2n$). Define $f: Pω \to Pω$ as follows :

$$f(P_n^A) = \{x_0\}$$

$$f(P_{n-j}^A \setminus P_{n-j+1}^A) = \{x_{2j}\} \quad \text{where} \quad 2j \le 2n$$

$$f(Q_{n-j}^A \setminus Q_{n-j+1}^A) = \{x_{2j+1}\} \quad \text{where} \quad 2j+1 \le 2n$$

$$f(Q_0^A \setminus Q_1^A) = \{ω\} \quad \text{if } Q_0^A \setminus Q_1^A \text{ is non-empty}$$

$f$ is continuous and $A=f^{-1}(C)$.

Case (ii) : $Q_{n+1}^A$ is non-empty

As $C$ is a $B_σ∩B_δ$ set and $A \leq_w C$, $Q_{n+1}^C$ is also non-empty.
Let e be any finite subset of ω in Q<sub>n+1</sub><sup>C</sup> , and x<sub>0</sub> be
any finite subset of ω in P<sub>n</sub><sup>C</sup> extending e ( i.e. e<x<sub>0</sub> ) .
Apply the method of proof in Proposition 2.5.2 to obtain an
alternating chain {x<sub>i</sub>}<sub>i=0</sub><sup>2n</sup> with x<sub>2j</sub> ∈ P<sub>n-j</sub><sup>C</sup> ( where 2j≤2n )
and x<sub>2j+1</sub> ∈ Q<sub>n-j</sub><sup>C</sup> ( where 2j+1≤2n ) . Define f : P<sub>ω</sub> → P<sub>ω</sub>
as follows :

$$
\begin{align*}
f(P_n^A) &= \{x_0\} \\
f(P_{n-j}^A \setminus P_{n-j+1}^A) &= \{x_{2j}\} \quad \text{where} \quad 2j \le 2n \\
f(Q_{n-j}^A \setminus Q_{n-j+1}^A) &= \{x_{2j+1}\} \quad \text{where} \quad 2j+1 \le 2n \\
f(Q_0^A \setminus Q_1^A) &= \{\omega\} \quad \text{if } Q_0^A \setminus Q_1^A \text{ is non-empty}
\end{align*}
f \text{ is continuous and } A=f^{-1}(C) . \quad \square
$$

Thus Wadge reducibility and enumeration reducibility agree with each
other in the domain of B sets. Next, we show that the two reducibilities
disagree with each other in the domain of all the B<sub>σ</sub>∩B<sub>δ</sub> sets in P<sub>ω</sub>. To
this end, we construct two B<sub>σ</sub>∩B<sub>δ</sub> sets A, C in P<sub>ω</sub> with A ≡<sub>ω</sub> C and
A <sub>ω</sub> C. C is as described in 2.5, namely, C is a countable union of
C<sub>n</sub>'s ( n∈ω and n≥1 ) where C<sub>n</sub> is :

C<sub>n</sub> = { {n<sup>2</sup>} , ..., {n<sup>2</sup>,...,m,...,n<sup>2</sup>+2i} , ... }

( n<sup>2</sup>≤m≤n<sup>2</sup>+2i, 1≤i≤n )

The first few $C_n$'s ($n \le 3$) are as follows :

$$
C_1 = \{ \{1\} , \{1,2,3\} \}
$$

$$
C_2 = \{ \{4\} , \{4,5,6\} , \{4,5,6,7,8\} \}
$$

$$
C_3 = \{ \{9\} , \{9,10,11\} , \{9,10,11,12,13\} , \{9,10,11,12,13,14,15\} \}
$$
Next, we describe A. $A$ is a countable union of $A_n$'s ($n \in \omega$) where
$A_n$'s are as follows:

$$
A_0 = \{0\}
$$

$$
A_1 = \{1\}, \{0,1,2,3\}
$$

$$
A_2 = \{4\}, \{4,5,6\}, \{0,4,5,6,7,8\}
$$

$$
A_3 = \{9\}, \{9,10,11\}, \{9,10,11,12,13\}, \{0,9,10,11,12,13,14,15\}
$$

.

.

.

.

$$
A_n = \{n^2\}, \dots, \{n^2, \dots, m, \dots, n^2+2i\}, \dots, \{0, n^2, \dots, k, \dots, n^2+2n\} \\
( n^2 \le m \le n^2+2i, n^2 \le k \le n^2+2i, 1 \le i \le n-1 )
$$

.

.

We note the following properties of A :

(i) A is a $B_\sigma$ set in $P_\omega$ because all the elements in A are finite subsets of $\omega$.

(ii) Each $A_i$ consists of an ascending chain of length $i+1$, which is part of some alternating chain of length $2i+1$ alternating in and out of A.
For example, consider $A_2$. $A_2$ consists of an ascending chain of length 3.
Define the following alternating chain $\{x_i\}_{i=0}^4$ of length 5 :

$$
x_0 = \{4\}
$$

$$
x_3 = \{4, 5, 6, 7\}
$$

$$
x_1 = \{4,5\}
$$

$$
x_4 = \{0,4,5,6,7,8\}
$$

$$
x_2 = \{4, 5, 6\}
$$
$A_2 = \{x_0, x_2, x_4\}$ is part of $\{x_i\}_{i=0}^4$. This shows that $A$ can admit an alternating chain of arbitrary length $n+1$ ($n \in \omega$). Hence by Proposition 2.5.1, $A$ is not a $B$ set in $P\omega$.

(iii) $A$ is closed under chain because there isn't any strictly increasing infinite chain in $A$. $A^c$ is also closed under chain because $A^c$ contains all infinite subsets of $\omega$. Hence by Proposition 2.4.1, $A$ is a $B_\sigma \cap B_\delta$ set in $P\omega$.

(iv) Note $P_\omega^A$ is empty. Otherwise, pick some finite subset $e$ of $\omega$ in $P_\omega^A$ (which is a $B_\sigma \cap B_\delta$ set in $P\omega$). We can apply remark(ii) after Proposition 2.5.2 to obtain an alternating chain $\{x_i\}_{i=0}^n$ alternating in and out of $A$ with $x_0=e$ for arbitrary $n \in \omega$. But no $e$ in $A$ has this property. Also note that $Q^A$ is non-empty because $\emptyset$ belongs to $\bigcap_{n \in \omega} Q_n^A = Q_\omega^A$. Hence $Q_\omega^A$ is a non-empty closed set in $P\omega$, and $A$ belongs to $D_\omega(P\omega)$.

**Proposition 4.2.2**

There exists $B_\sigma \cap B_\delta$ sets $A, C$ in $P\omega$ with $A \equiv_C C$ and $A \not\equiv_C C$.

**Proof :** Consider the sets $A, C$ constructed above. We have observed that $A$ and $C$ are both genuine $D_\omega(P\omega)$ sets. By (W2) in 3.1, $A \equiv_C C$. 

**Claim :** $A \not\equiv_C C$

**Proof :** Suppose not and $A=f^{-1}(C)$ for some continuous $f: P\omega \to P\omega$. Consider the set $A' = \{x \in A | 0 < x\}$. Note $A' = \{a_n\}_{n \in \omega}$ where $a_n=\{0, n^2, \dots, n^2+2i, \dots\}$ ($1 \le i \le n$). $A'$ is an infinite set. Since $f$ is a monotonic function, $f$ maps the elements in $A'$ to elements in $C$ extending $f(\{0\})$. We observed in 2.5 that there exists only finitely many $y$'s in $C$ extending $f(\{0\})$, i.e. $C' = \{y \in C | f(\{0\}) < y\}$ is a finite
set. Since $f(A')$ is a subset of $C'$, we conclude that there exists some $y$ in $C'$ such that infinitely many elements in $A'$ are mapped to $y$ via $f$. Consider such a $y$ and put $A'' = \{ x \in A' | f(x)=y \}$ - so $A''$ is an infinite subset of $A'$. Let cardinality of $y$ be $n$. Since $A''$ is an infinite subset of $A'$, there exists some $m \ge n$ such that $a_m$ belongs to $A''$, i.e. $f(a_m)=y$. Now $a_m$ belongs to $A_m$ which is an ascending chain of $m+1$ elements all are subsets of $a_m$. As noted before, $A_m$ is part of the alternating chain $\{b_i\}_{i=0}^{2m}$ of length $2m+1$ where $b_i = \{m^2, \dots, m^2+k, \dots\}$ ($1 \le k \le i$) for $i < 2m$ and $b_{2m} = a_m$. Since $f$ is a monotonic function, $f(A_m)$ has to be an ascending chain of $m+1$ distinct elements in $C$ all contained in $f(a_m)=y$. This means $\text{cardinality}(y) \ge m+1 > n$, contradiction.

The last claim establishes the proposition. $\square$
## References

[1] J.W. Addison : Methods of alternating chains, Theory of Models, North Holland Publishing Company, 1965

[2] C. Kuratowski : Topology I, Warsaw and Wrocław, 1958

[3] D. Scott : Continuous lattices, Technical Monograph PRG-7, Oxford University Computing Laboratory, Programming Research Group, 1970

[4] D. Scott : Data types as lattices, to appear in Springer Lecture Notes, 1974

[5] A. Tang : Recursion theory and descriptive set theory in effectively given $T_0$ spaces, Ph.D. thesis, Princeton University, 1974

[6] B. Wadge : Ph.D. thesis, U. C. Berkeley

## Acknowledgement

I should like to express my thanks to my supervisor Professor D. Scott, Professor J.W. Addison and Dr. B. Wadge for their advice and encouragement.

This research is supported partly by Princeton University and partly by I.R.I.A., France.