1 Introduction
The classical Borel, Luzin, and Hausdorff hierarchies in Polish spaces, which are defined using set operations, play an important role in descriptive set theory (DST). Recently, these hierarchies were extended and shown to have similar nice properties also in quasi-Polish spaces [Reference de Brecht4] which include many non-Hausdorff spaces of interest for several branches of mathematics and theoretical computer science.
The Wadge hierarchy, introduced in [Reference Wadge33, Reference Wadge34], is nonclassical in the sense that it is based on a notion of reducibility that was not recognized in the classical DST, and on using ingenious versions of Gale-Stewart games rather than on set operations. For subsets
$A,B$
of the Baire space
$\mathcal {N}=\omega ^\omega $
, A is Wadge reducible to B (
$A\leq _WB$
), if
$A=f^{-1}(B)$
for some continuous function f on
$\mathcal {N}$
. The quotient-poset of the preorder
$(P(\mathcal {N});\leq _W)$
under the induced equivalence relation
$\equiv _W$
on the power-set of
$\mathcal {N}$
is called the structure of Wadge degrees in
$\mathcal {N}$
. W. Wadge [Reference Wadge34] characterized the structure of Wadge degrees of Borel sets (i.e., the quotient-poset of
$({\mathbf B}(\mathcal {N});\leq _W)$
) up to isomorphism. In particular, this quotient-poset is semi-well-ordered, hence it is well-founded and has no three pairwise incomparable elements. For more information on Wadge degrees see [Reference Kechris, Löwe and Steel10, Reference van Wesep36].
This gives rise to the Wadge hierarchy
$\{\mathbf {\Sigma }_\alpha (\mathcal {N})\}_{\alpha <\upsilon }$
(for a rather large ordinal
$\upsilon $
) in
$\mathcal {N}$
which is a great refinement of the Borel hierarchy (for more information see the next section where we also give precise definitions of other notions mentioned in this introduction). The Wadge hierarchy was originally defined only for the Baire space. Using the methods of [Reference Wadge34] it is easy to check that the structure
$({\mathbf B}(X);\leq _W)$
of Wadge degrees of Borel sets in any zero-dimensional Polish space X remains semi-well-ordered and the Wadge hierarchy in such spaces looks rather similar to that in the Baire space.
The Wadge hierarchy of sets was an important development in classical DST not only as a unifying concept (it subsumes all hierarchies known before) but also as a useful tool to investigate second countable zero-dimensional spaces. We illustrate this with two examples. In chapter 4 of [Reference van Engelen31] a complete classification (up to homeomorphism) of homogeneous zero-dimensional absolute Borel sets was achieved, completing a series of earlier results in this direction. In theorem 2.4 of [Reference van Engelen, Miller and Steel32] it was shown that any Borel subspace of the Baire space with more than one point has a nontrivial auto-homeomorphism.
In this paper we attempt to find the “correct” extension of the Wadge hierarchy from Polish zero-dimensional spaces to arbitrary second countable spaces. There are at least three approaches to this problem.
The first approach is to show that Wadge reducibility in such spaces behaves similarly to its behavior in the Baire space, i.e., it is a semi-well-order. Unfortunately, this is not the case: for many natural quasi-Polish spaces X the structure
$({\mathbf B}(X);\leq _W)$
is not well-founded and has antichains with more than two elements (see e.g., [Reference Becher and Grigorieff1, Reference Duparc and Vuilleumier5, Reference Hertling8, Reference Selivanov19]). Thus, this approach does not lead to a reasonable extension of the Wadge hierarchy to quasi-Polish spaces.
The second approach was independently suggested in [Reference Pequignot16, Reference Selivanov27]. The approach is based on the characterization of quasi-Polish spaces as the second countable
$T_0$
-spaces X such that there is a total admissible representation
$\xi $
from
$\mathcal {N}$
onto X [Reference de Brecht4]. Namely, one can define the Wadge hierarchy
$\{\mathbf {\Sigma }_\alpha (X)\}_{\alpha <\upsilon }$
in X by
$\mathbf {\Sigma }_\alpha (X)=\{A\subseteq X\mid \xi ^{-1}(A)\in \mathbf {\Sigma }_\alpha (\mathcal {N})\}$
. One easily checks that the definition of
$\mathbf {\Sigma }_\alpha (X)$
does not depend on the choice of
$\xi $
,
$\bigcup _{\alpha <\nu }\mathbf {\Sigma }_\alpha (X)=\mathbf {B}(X)$
,
${\mathbf {\Sigma }}_\alpha (X)\subseteq {\mathbf {\Delta }}_\beta (X)$
for all
$\alpha <\beta <\upsilon $
, and any
$\mathbf {\Sigma }_\alpha (X)$
is downward closed under the Wadge reducibility in X. This definition is short and elegant but it gives no real understanding of how the levels
$\mathbf {\Sigma }_\alpha (X)$
look like, in particular their set-theoretic descriptions are completely unclear.
The third approach consists in set-theoretic description of subsequent refinements of the Borel hierarchy. It was thoroughly studied in [Reference de Brecht4] for the Borel and Hausdorff hierarchies in quasi-Polish spaces. This study was continued in [Reference Selivanov, Kari, Manea and Petre26, Reference Selivanov27] for an increasing sequence of pointclasses
$\{\mathbf {\Sigma }_\alpha (X)\}_{\alpha <\lambda }$
which exhaust the sets of finite Borel rank, where
$\lambda =sup\{\omega _1,\omega _1^{\omega _1},\omega _1^{\omega _1^{\omega _1}},\ldots \}$
. These classes were conjectured to coincide with the corresponding classes from the second approach and the conjecture was verified for
$\mathbf {\Sigma }_\alpha (X)$
with
$\alpha <\omega _1^{\omega _1}$
(it follows from corollary 5.10 in [Reference Selivanov27] and theorem 2 in [Reference Selivanov, Kari, Manea and Petre26]). Thus, we proposed a way to achieve a reasonable set-theoretic definition of the Wadge hierarchy in X defined as in the second approach.
In this paper we propose a set-theoretic definition for the whole Wadge hierarchy of Borel sets from the second approach. The definition is an infinitary version of the so called fine hierarchy introduced and studied in a series of my publications (see e.g., [Reference Selivanov18, Reference Selivanov23] for a survey). In fact, this paper develops a “classical” infinitary version of the effective finitary version of the Wadge hierarchy in effective spaces and computable quasi-Polish spaces recently developed in [Reference Selivanov28]. Arguably, our infinitary fine hierarchy (IFH), and hence also the Wadge hierarchy, is a kind of “iterated difference hierarchy” over levels of the Borel hierarchy; it only remains to make precise how to “iterate” the difference hierarchies.
Along with describing (hopefully) the right version of the Wadge hierarchy (by identifying it with the IFH) in arbitrary spaces we show that it behaves well in second countable spaces and especially in quasi-Polish spaces. E.g., it provides the description of all levels
$\mathbf {\Sigma }_\alpha (X)$
in quasi-Polish spaces (Theorem 6). Also, all levels of the IFH are preserved by continuous open surjections between second countable spaces which gives a broad extension of results by Saint Raymond and de Brecht for the Borel and Hausdorff hierarchies [Reference de Brecht4, Reference Saint Raymond17] (Theorem 2). In §4.3 we show that several HK-type theorems are inherited by the continuous open images which yields some such theorems in arbitrary quasi-Polish spaces.
Notions and results of this paper apply not only to the Wadge hierarchy of sets discussed so far but also to a more general hierarchy of functions
$A:X\to Q$
from a space X to an arbitrary quasiorder Q. We identify such functions with Q-partitions of X of the form
$\{A^{-1}(q)\}_{q\in Q}$
in order to stress their close relation to k-partitions (obtained when
$Q=\bar {k}=\{0,\dots,k-1\}$
is an antichain with k-elements) studied e.g., in [Reference Hertling7, Reference Selivanov21, Reference Selivanov, Kari, Manea and Petre26, Reference Selivanov27].
For Q-partitions
$A,B$
of X, let
$A\leq _WB$
mean that there is a continuous function f on X such that
$A(x)\leq _QB(f(x))$
for each
$x\in X$
. The case of sets corresponds to the case of two-partitions. Let
${\mathbf B}(Q^X)$
be the set of Borel Q-partitions A (for which
$A^{-1}(q)\in {\mathbf B}(X)$
for all
$q\in Q$
). A celebrated theorem of van Engelen, Miller and Steel (see theorem 3.2 in [Reference van Engelen, Miller and Steel32]) shows that if Q is a countable better quasiorder (bqo) then
$\mathcal {W}_Q=({\mathbf B}(Q^{\mathcal {N}});\leq _W)$
is a bqo. Although this theorem gives an important information about the quotient-poset of
$\mathcal {W}_Q$
, it is far from a characterization.
Many efforts (see e.g., [Reference Hertling7, Reference Selivanov21, Reference Selivanov, Kari, Manea and Petre26, Reference Selivanov27] and references therein) to characterize the quotient-poset of
$\mathcal {W}_Q$
were devoted to k-partitions of
$\mathcal {N}$
. Our approach in [Reference Selivanov21, Reference Selivanov, Kari, Manea and Petre26, Reference Selivanov27] to this problem was to characterize the initial segments
$({\mathbf \Delta }^0_\alpha (k^{\mathcal {N}});\leq _W)$
for bigger and bigger ordinals
$2\leq \alpha <\omega _1$
. To achieve this, we defined structures of iterated labeled trees and forests with the so called homomorphism quasiorder and discovered useful properties of some natural operations on the iterated labeled forests and on Q-partitions.
An important progress was recently achieved by T. Kihara and A. Montalbán in [Reference Kihara and Montalbán11] where a full characterization of the quotient-poset of
$\mathcal {W}_Q$
for arbitrary countable bqo Q is obtained, using an extended set of iterated labeled trees
$(\mathcal {T}_{\omega _1}(Q);\leq _h)$
with the homomorphism quasiorder
$\leq _h$
. Namely,
$(\mathcal {T}_{\omega _1}(Q);\leq _h)$
is equivalent to the substructure of
$\mathcal {W}_Q$
formed by the
$\sigma $
-join-irreducible elements (the equivalence means isomorphism of the corresponding quotient-posets) via an embedding
$\mu :\mathcal {T}_{\omega _1}(Q)\to \mathcal {W}_Q$
. The Wadge hierarchy of Q-partitions of
$\mathcal {N}$
may be thus written as the family
$\{\mathcal {W}_Q(T)\}_{T\in \mathcal {T}_{\omega _1}(Q)}$
, where
$\mathcal {W}_Q(T)=\{A\in Q^{\mathcal {N}}\mid A\leq _W\mu (T)\}$
, and it exhausts all principal ideals of
$\mathcal {W}_Q$
formed by
$\sigma $
-join-irreducible Q-Wadge degrees. For
$Q=\bar {2}$
this yields a new characterization of the Wadge hierarchy of sets.
Main results of our paper may be sketched as follows. We define a Q-IFH
$\{\widehat {\mathcal {L}}(X,T)\}_{T\in \mathcal {T}_{\omega _1}(Q)}$
of Q-partitions of arbitrary space X via natural set operations and propose it as the right extension of the Q-Wadge hierarchy. Theorem 3.36 and Corollary 3.33 show that its levels are ordered as one would expect from the Q-Wadge hierarchy. Theorems 4.7, 4.8 and 4.12 show that this hierarchy in quasi-Polish spaces satisfies Hausdorff–Kuratowski-type theorems. Theorem 4.10 shows that this hierarchy in the Baire space coincides with the hierarchy in [Reference Kihara and Montalbán11]. For a quasi-Polish space X, a continuous open surjection
$\xi :\mathcal {N}\to X$
, and
$T\in \mathcal {T}_{\omega _1}(Q)$
, let
$\mathcal {W}(X,T)=\{A\in Q^X\mid A\circ \xi \in \mathcal {W}_Q(T)\}$
be the levels of Wadge hierarchy of Q-partitions defined according to the second approach. Theorem 4.11 shows that
$\widehat {\mathcal {L}}(X,T)=\mathcal {W}(X,T)$
for every countable bqo Q and every
$T\in \mathcal {T}_{\omega _1}(Q)$
. For the case of two-partitions we obtain a set-theoretic characterization of the Wadge hierarchy from the second approach which looks different from a description of the Wadge hierarchy in [Reference Kihara and Montalbán11] (see also [Reference Louveau, Kechris, Lowe and Steel15, Reference Wadge34]). The characterizations in [Reference Kihara and Montalbán11, Reference Louveau, Kechris, Lowe and Steel15, Reference Wadge34] cannot be straightforwardly extended to arbitrary spaces since they use specific features of the Baire space.
Having papers [Reference Selivanov24, Reference Selivanov27, Reference Selivanov28] at hand would probably simplify reading of the present paper because they contain simpler versions of some notions and results based on similar ideas. Technical notions for the infinitary case are harder than for the finitary case [Reference Selivanov24, Reference Selivanov28] but the ideas are the same. After recalling necessary preliminaries in the next section, we define in §3 the Q-IFH and establish its general properties. In §4 we prove the above-mentioned additional properties of the Q-IFH in second countable spaces and in quasi-Polish spaces.
2 Preliminaries
In this section we briefly recall some notation, notions and facts used throughout the paper. Some more special information is recalled in the corresponding sections below.
2.1 Well and better quasiorders
We use standard set-theoretical notation. In particular,
$Y^X$
is the set of functions from X to Y,
$P(X)$
is the class of subsets of a set X,
$\check {\mathcal {C}}$
is the class of complements
$X\setminus C$
of sets C in
$\mathcal {C}\subseteq P(X)$
. We assume the reader to be acquainted with the notion of ordinal (see e.g., [Reference Kuratowski and Mostowski13]). Ordinals are denoted by
$\alpha, \beta, \gamma,\ldots $
. Every ordinal
$\alpha $
is the set of smaller ordinals, in particular
$ \omega =\{0,1,2,\ldots \}.$
We use some notions and facts of ordinal arithmetic. In particular,
$\alpha +\beta $
,
$\alpha \cdot \beta $
and
$\alpha ^{\beta }$
denote the ordinal addition, multiplication and exponentiation of
$\alpha $
and
$\beta $
, respectively. Every positive ordinal
$\alpha $
is uniquely representable in the Cantor normal form
$\alpha =\omega ^{\alpha _0}+\cdots +\omega ^{\alpha _n}$
where
$n<\omega $
and
$\alpha \geq \alpha _0\geq \cdots \geq \alpha _n$
; we denote
$\alpha *=\omega ^{\alpha _0}$
. The first noncountable ordinal is denoted by
$\omega _1$
.
We use standard notation and terminology on partially ordered sets (posets) and quasiorders (qo’s). To avoid complex notation, we sometimes abuse terminology about posets by applying it also to qo’s; in such cases we just mean the corresponding quotient-poset. A qo
$(P;\leq )$
is well-founded if it has no infinite descending chains
$a_0>a_1>\cdots $
. In this case there are a unique ordinal
$rk(P)$
and a unique rank function
$rk_P$
from P onto
$rk(P)$
satisfying
$a<b\to rk(a)<rk(b)$
. It is defined by induction
$rk_P(x)=\textit{sup}\{rk_P(y)+1\mid y<x\}. $
The ordinal
$rk(P)$
is called the rank (or height) of P, and the ordinal
$rk_P(x)$
is called the rank of
$x\in P$
in P.
A well quasiorder (wqo) is a qo
$Q=(Q;\leq _Q)$
that has neither infinite descending chains nor infinite antichains. Although wqo’s are closed under many finitary constructions like forming finite labeled words or trees, they are not always closed under important infinitary constructions. C. Nash-Williams was able to find a subclass of wqo’s, called better quasiorders (bqo’s), which contains most of the “natural” wqo’s (in particular, all finite qo’s) and is closed under many infinitary constructions. We omit a bit technical notion of bqo which is used only in formulations and we refer the reader to [Reference Simpson, Mansfield and Weitkamp29].
Recall that an (upper) semilattice is a structure
$(S;\sqcup )$
with binary operation
$\sqcup $
such that
$(x\sqcup y)\sqcup z=x\sqcup (y\sqcup z)$
,
$x\sqcup y= y\sqcup x$
and
$x\sqcup x=x$
, for all
$x,y,z\in S$
. By
$\leq $
we denote the induced partial order on S:
$x\leq y$
iff
$x\sqcup y=y$
. The operation
$\sqcup $
can be recovered from
$\leq $
since
$x\sqcup y$
is the supremum of
$x,y$
w.r.t.
$\leq $
. By
$\sigma $
-semilattice we mean a semilattice where also supremums
$\bigsqcup y_j=y_0\sqcup y_1\sqcup \cdots $
of countable sequences of elements
$y_0,y_1,\ldots $
exist. An element x of a
$\sigma $
-semilattice S is
$\sigma $
-join-irreducible if it cannot be represented as the countable supremum of elements strictly below x. As first stressed in [Reference Selivanov22], the
$\sigma $
-join-irreducible elements play a central role in the study of Wadge degrees of k-partitions. They are also of principal importance in [Reference Kihara and Montalbán11].
2.2 Classical hierarchies in topological spaces
We assume the reader to be familiar with basic notions of topology [Reference Engelking6]. The underlying set of a topological space X will be usually also denoted by X, in abuse of notation. We usually abbreviate “topological space” to “space.” A space is zero-dimensional if it has a basis of clopen sets. Recall that a basis for the topology on X is a set
$\mathcal {B}$
of open subsets of X such that for every
$x\in X$
and open U containing x there is
$B\in \mathcal {B}$
satisfying
$x\in B\subseteq U$
. We sometimes shorten “countably based
$T_0$
-space” to “cb
$_0$
-space.”
Let
$\omega $
be the space of non-negative integers with the discrete topology. Let
$\mathcal {N}=\omega ^\omega $
be the set of all infinite sequences of natural numbers (i.e., of all functions
$x \colon \omega \to \omega $
). Let
$\omega ^*$
be the set of finite sequences of elements of
$\omega $
, including the empty sequence
$\varepsilon $
. For
$\sigma \in \omega ^*$
and
$x\in \mathcal {N}$
, we write
$\sigma \sqsubseteq x$
to denote that
$\sigma $
is an initial segment of the sequence x. By
$\sigma x=\sigma \cdot x$
we denote the concatenation of
$\sigma $
and x, and by
$\sigma \cdot \mathcal {N}$
the set of all extensions of
$\sigma $
in
$\mathcal {N}$
. For
$x\in \mathcal {N}$
, we can write
$x=x(0)x(1)\dotsc $
where
$x(i)\in \omega $
for each
$i<\omega $
. For
$x\in \mathcal {N}$
and
$n<\omega $
, let
$x\upharpoonright n=x(0)\dotsc x(n-1)$
denote the initial segment of x of length n. By endowing
$\mathcal {N}$
with the product of the discrete topologies on
$\omega $
, we obtain the so-called Baire space. The product topology coincides with the topology generated by the collection of sets of the form
$\sigma \cdot \mathcal {N}$
for
$\sigma \in \omega ^*$
. It is well known that
$\mathcal {N}\times \mathcal {N}$
and
$\mathcal {N}^\omega $
are homeomorphic to
$\mathcal {N}$
(see e.g., [Reference Kechris9]).
A tree is a nonempty set
$T\subseteq \omega ^*$
which is closed downwards under the prefix relation
$\sqsubseteq $
. The empty string
$\varepsilon $
is the root of any tree. A leaf of T is a maximal element of
$(T;\sqsubseteq )$
. A tree is pruned if it has no leaf. A path through a tree T is an element
$x\in \mathcal {N}$
such that
$x\upharpoonright n\in T$
for each
$n\in \omega $
. For any tree and any
$\tau \in T$
, let
$[T]$
be the set of paths through T and
$T(\tau )=\{\sigma \mid \tau \sigma \in T\}$
. We call a tree T normal if
$\tau (i+1)\in T$
implies
$\tau i\in T$
. A tree is infinite-branching if with every nonleaf node
$\tau $
it contains all its successors
$\tau i$
; every infinite branching tree is normal. A tree is well founded if there is no path through it (i.e.,
$(T;\sqsupseteq )$
is well founded). The rank of the latter poset is called the rank of T; the ranks of well founded trees are precisely the countable ordinals. By a forest we mean a set of strings
$T\setminus \{\varepsilon \}$
, for some tree T; usually we assume forests to be nonempty. Sometimes we use other obvious notation on trees. E.g., with any sequence of trees
$\{T_0,T_1,\ldots \}$
we associate the tree
$T=\{\varepsilon \}\cup 0\cdot T_0\cup 1\cdot T_1\cup \cdots $
such that
$T(i)=T_i$
for each
$i<\omega $
.
A pointclass in a space
$ X $
is a class
$\mathbf {\Gamma }(X)\subseteq P(X) $
of subsets of
$ X $
. A family of pointclasses [Reference Selivanov25] is a family
$ \mathbf {\Gamma }=\{\mathbf {\Gamma }(X)\}_X $
indexed by arbitrary topological spaces X (or by spaces in a reasonable class) such that each
$ \mathbf {\Gamma }(X) $
is a pointclass in
$ X $
and
$ \mathbf {\Gamma } $
is closed under continuous preimages, i.e.,
$ f^{-1}(A)\in \mathbf {\Gamma }(X) $
for every
$ A\in \mathbf {\Gamma }(Y) $
and every continuous function
$ f \colon X\to Y $
. A basic example of a family of pointclasses is given by the family
$\mathcal {O}=\{\tau _X\}_X$
of topologies in arbitrary spaces X.
We will use the following operations on families of pointclasses: the operation
$\mathbf {\Gamma }\mapsto \mathbf {\Gamma }_\sigma $
, where
$\mathbf {\Gamma }(X)_\sigma $
is the set of all countable unions of sets in
$\mathbf {\Gamma }(X)$
, the operation
$\mathbf {\Gamma }\mapsto \mathbf {\Gamma }_\delta $
, where
$\mathbf {\Gamma }(X)_\delta $
is the set of all countable intersections of sets in
$\mathbf {\Gamma }(X)$
, the operation
$\mathbf {\Gamma }\mapsto \mathbf {\Gamma }_c$
, where
$\mathbf {\Gamma }(X)_c=\check {\mathbf {\Gamma }}(X)$
, the operation
$\mathbf {\Gamma }\mapsto \mathbf {\Gamma }_d$
, where
$\mathbf {\Gamma }(X)_d$
is the set of all differences of sets in
$\mathbf {\Gamma }(X)$
.
The operations on families of pointclasses enable to provide short uniform descriptions of the classical hierarchies in arbitrary spaces. E.g., the Borel hierarchy is the sequence of families of pointclasses
$\{\mathbf {\Sigma }^0_\alpha \}_{ \alpha <\omega _1}$
defined by induction on
$\alpha $
as follows [Reference de Brecht4, Reference Selivanov20]:
$\mathbf {\Sigma }^0_0(X):=\{\emptyset \}$
,
$\mathbf {\Sigma }^0_1 := \mathcal {O}$
(the family of open sets),
$\mathbf {\Sigma }^0_2 := (\mathbf {\Sigma }^0_1)_{d\sigma }$
, and
$\mathbf {\Sigma }^0_\alpha (X) =(\bigcup _{\beta <\alpha }\mathbf {\Sigma }^0_\beta (X))_{c\sigma }$
for
$\alpha>2$
. The sequence
$\{\mathbf {\Sigma }^0_\alpha (X)\}_{ \alpha <\omega _1}$
is called the Borel hierarchy in X. We also set
$\mathbf {\Pi }^0_\beta (X) = (\mathbf {\Sigma }^0_\beta (X))_c $
and
$\mathbf {\Delta }^0_\alpha (X) = \mathbf {\Sigma }^0_\alpha (X) \cap \mathbf {\Pi }^0_\alpha (X)$
. The classes
$\mathbf {\Sigma }^0_\alpha (X),\mathbf {\Pi }^0_\alpha (X),{\mathbf {\Delta }}^0_\alpha (X)$
are called levels of the Borel hierarchy in X. The class
$\mathbf {B}(X)$
of Borel sets in X is defined as the union of all levels of the Borel hierarchy in X; it coincides with the smallest
$\sigma $
-algebra of subsets of X containing the open sets. We have
$\mathbf {\Sigma }^0_\alpha (X)\cup \mathbf {\Pi }^0_\alpha (X)\subseteq \mathbf {\Delta }^0_\beta (X)$
for all
$\alpha <\beta <\omega _1$
. We do not recall the well known definition of the Hausdorff difference hierarchy over
$\mathbf {\Sigma }^0_{\alpha }(X)$
,
$\alpha \geq 1$
, which is denoted by
$\{D_\beta (\mathbf {\Sigma }^0_{\alpha }(X))\}_{\beta <\omega _1}$
or by
$\{\mathbf {\Sigma }^{-1,\alpha }_\beta (X)\}_{\beta <\omega _1}$
. The definitions may be found e.g., in §22.E in [Reference Kechris9] or in [Reference Selivanov27]. We recall some structural properties of pointclasses (see e.g., §22.C in [Reference Kechris9]).
-
1. A pointclass
$\mathbf {\Gamma }(X)$
has the separation property if for every two disjoint sets
$A,B\in \mathbf {\Gamma }(X)$
there is a set
$C\in \mathbf {\Gamma }(X)\cap \check {\mathbf {\Gamma }}(X)$
with
$A\subseteq C\subseteq X\setminus B$
. -
2. A pointclass
$\mathbf {\Gamma }(X)$
has the reduction property if for all
$C_0, C_1\in \mathbf {\Gamma }(X)$
there are disjoint
$C^\prime _0,C^\prime _1\in \mathbf {\Gamma }(X)$
such that
$C^\prime _i\subseteq C_i$
for
$i<2$
and
$C_0\cup C_1=C^\prime _0\cup C^\prime _1$
. The pair
$(C^\prime _0,C^\prime _1)$
is called a reduct for the pair
$(C_0,C_1)$
. -
3. A pointclass
$\mathbf {\Gamma }(X)$
has the
$\sigma $
-reduction property if for each countable sequence
$C_0, C_1,\ldots $
in
$\mathbf {\Gamma }(X)$
there is a countable sequence
$C^\prime _0, C^\prime _1,\ldots $
in
$\mathbf {\Gamma }(X)$
(called a reduct of
$C_0, C_1,\ldots $
) such that
$C^\prime _i\cap C^\prime _j=\emptyset $
for all
$i\not =j$
and
$\bigcup _{i<\omega }C^\prime _i=\bigcup _{i<\omega }C_i$
.
It is well-known that if
$\mathbf {\Gamma }(X)$
has the reduction property then the dual class
$\check {\mathbf {\Gamma }}(X)$
has the separation property, but not vice versa, and that if
$\mathbf {\Gamma }(X)$
has the
$\sigma $
-reduction property then
$\mathbf {\Gamma }(X)$
has the reduction property but not vice versa. Let X be a cb
$_0$
-space. It is known (see e.g., theorem 22.16 in [Reference Kechris9] and theorem 3.5 in [Reference Selivanov25]) that any level
$\mathbf {\Sigma }^0_{2+\alpha }(X)$
,
$\alpha <\omega _1$
, has the
$\sigma $
-reduction property, and if X is zero-dimensional then also
$\mathbf {\Sigma }^0_{1}(X)$
has the
$\sigma $
-reduction property.
2.3 Quasi-Polish spaces and admissible representations
A space X is Polish if it is countably based and metrizable with a metric d such that
$(X,d)$
is a complete metric space. Examples of Polish spaces are
$\omega $
,
$\mathcal {N}$
, the Cantor space
$\mathcal {C}$
, the space of reals
$\mathbb {R}$
and its Cartesian powers
$\mathbb {R}^n $
(
$ n < \omega $
), the closed unit interval
$ [0,1] $
, the Hilbert cube
$ [0,1]^\omega $
and the space
$\mathbb {R}^\omega $
.
Quasi-Polish spaces were identified and thoroughly studied by M. de Brecht [Reference de Brecht4] (see also [Reference Chen3] for additional information). Informally, this is a natural class of spaces which contains all Polish spaces, many important non-Hausdorff spaces (like
$\omega $
-continuous domains) and has essentially the same DST as Polish spaces (see below). Let
${P\hspace {-1pt}\omega }$
be the space of subsets of
$\omega $
equipped with the Scott topology, a countable basis of which is formed by the sets
$\{A\subseteq \omega \mid F\subseteq A\}$
, where F ranges over the finite subsets of
$\omega $
. By a quasi-Polish space we mean a space homeomorphic to a
$\mathbf {\Pi }^0_2$
-subspace of
${P\hspace {-1pt}\omega }$
. There are several interesting characterizations of quasi-Polish spaces. For this paper the following characterization in terms of representations is relevant.
A representation of a set X is a surjection from a subspace of
$\mathcal {N}$
onto X. Such a representation is total if its domain is
$\mathcal {N}$
. Representation
$\mu $
is (continuously) reducible to a representation
$\nu $
(
$\mu \leq _c\nu $
) if
$\mu =\nu \circ f$
for some continuous partial function f on
$\mathcal {N}$
. Representations
$\mu,\nu $
are (continuously) equivalent (
$\mu \equiv _c\nu $
) if
$\mu \leq _c\nu $
and
$\nu \leq _c\mu $
. A basic notion of Computable Analysis [Reference Weihrauch35] is the notion of admissible representation. A representation
$\mu $
of a space X is admissible, if it is continuous and any continuous function
$\nu :Z \to X$
from a subset
$Z\subseteq \mathcal {N}$
to X is continuously reducible to
$\mu $
. Clearly, any two admissible representations of a space are continuously equivalent. By theorem 12 in [Reference Brattka and Hertling2], any continuous open surjection from a subspace of
$\mathcal {N}$
onto X is an admissible representation of X. In theorems 41 and 49 of [Reference de Brecht4] the following characterization of quasi-Polish spaces was obtained:
Proposition 2.2. [Reference de Brecht4] A cb
$_0$
-space X is quasi-Polish iff it has a total admissible representation iff there is a continuous open surjection from
$\mathcal {N}$
onto X.
The classical Borel, Luzin and Hausdorff hierarchies in quasi-Polish spaces have properties very similar to their properties in Polish spaces [Reference de Brecht4]. In particular, for any uncountable quasi-Polish space X and any
$\alpha <\omega _1$
,
$\mathbf {\Sigma }^0_\alpha (X)\not \subseteq \mathbf {\Pi }^0_\alpha (X)$
. For any quasi-Polish space X, the Suslin theorem
$\bigcup _{\alpha <\omega _1}\mathbf {\Sigma }^0_{1+\alpha }(X)=\mathbf {B}(X)=\mathbf {\Delta }^1_1(X)$
and the HK theorem [Reference de Brecht4, Reference Kechris9] (saying that
$\bigcup _{\beta <\omega _1}\mathbf {\Sigma }^{-1,\alpha }_\beta (X)=\mathbf {\Delta }^0_{\alpha +1}(X)$
for all
$\alpha \geq 1$
) hold.
Quasi-Polish spaces also share properties of Polish spaces related to Baire category (see e.g., §I.8 of [Reference Kechris9] or §7 of [Reference Chen3] for a general background). According to an extension of a basic fact for Polish spaces from [Reference Saint Raymond17], every quasi-Polish space X is completely Baire, in particular every nonempty closed set
$F\subseteq X$
is nonmeager in F (see corollary 52 in [Reference de Brecht4] or corollary 7.8 in [Reference Chen3]). Using the technique of category quantifiers (§8.J in [Reference Kechris9]), one can show the following preservation property [Reference Chen3, Reference de Brecht4, Reference Saint Raymond17] of levels of the Borel hierarchy.
Proposition 2.3. [Reference Chen3, Reference de Brecht4, Reference Saint Raymond17] Let
$f:X\to Y$
be a continuous open surjection between cb
$_0$
-spaces,
$\alpha <\omega _1$
, and
$A\subseteq Y$
. Then
$A\in \mathbf {\Sigma }^0_{1+\alpha }(Y)$
iff
$f^{-1}(A)\in \mathbf {\Sigma }^0_{1+\alpha }(X)$
. Also, every fiber
$f^{-1}(y)$
is quasi-Polish, hence nonmeager in
$f^{-1}(y)$
.
2.4 Wadge hierarchy in
$\mathcal {N}$
Here we give some additional information on the Wadge hierarchy in the Baire space. In [Reference Wadge34] W. Wadge proved that the structure
$({\mathbf B}(\mathcal {N});\leq _W)$
of Borel sets in the Baire space is semi-well-ordered (i.e., it is well-founded and for all
$A,B\in {\mathbf B}(\mathcal {N})$
we have
$A\leq _WB$
or
$\overline {B}\leq _WA$
). In particular, there is no antichain of size 3 in
$({\mathbf B}(\mathcal {N});\leq _W)$
. He has also computed the rank
$\upsilon $
of
$({\mathbf B}(\mathcal {N});\leq _W)$
which we call the Wadge ordinal. Recall that a set A is self-dual if
$A\leq _W\overline {A}$
. W. Wadge has shown that if a Borel set is self-dual (resp. nonself-dual) then any Borel set of the next Wadge rank is nonself-dual (resp. self-dual), a Borel set of Wadge rank of countable cofinality is self-dual, and a Borel set of Wadge rank of uncountable cofinality is nonself-dual. This characterizes the structure of Wadge degrees of Borel sets up to isomorphism.
In theorem 2 of [Reference van Wesep37], and also in [Reference Steel30], the following separation theorem for the Wadge hierarchy was established: For any nonself-dual Borel set A exactly one of the principal ideals
$\{X\mid X\leq _WA\}$
,
$\{X\mid X\leq _W\overline {A}\}$
has the separation property. The mentioned results give rise to the Wadge hierarchy which is, by definition, the sequence
$\{\mathbf {\Sigma }_\alpha (\mathcal {N})\}_{\alpha <\upsilon }$
of all nonself-dual principal ideals of
$({\textbf {B}}(\mathcal {N});\leq _W)$
that do not have the separation property and satisfy for all
$\alpha <\beta <\upsilon $
the strict inclusion
$\mathbf {\Sigma }_\alpha (\mathcal {N})\subset \mathbf {\Delta }_\beta (\mathcal {N})$
where, as usual,
$\mathbf {\Delta }_\alpha (\mathcal {N})=\mathbf {\Sigma }_\alpha (\mathcal {N}) \cap \mathbf {\Pi }_\alpha (\mathcal {N})$
.
The Wadge hierarchy subsumes the classical hierarchies in the Baire space, in particular
${\mathbf {\Sigma }}_\alpha (\mathcal {N})={\mathbf {\Sigma }}^{-1}_\alpha (\mathcal {N})$
for each
$\alpha <\omega _1$
,
${\mathbf {\Sigma }}_1(\mathcal {N})={\mathbf {\Sigma }}^0_1(\mathcal {N})$
,
${\mathbf {\Sigma }}_{\omega _1}(\mathcal {N})={\mathbf {\Sigma }}^0_2(\mathcal {N})$
,
${\mathbf {\Sigma }}_{\omega _1^{\omega _1}}(\mathcal {N})={\mathbf {\Sigma }}^0_3(\mathcal {N})$
and so on. Thus, the sets of finite Borel rank coincide with the sets of Wadge rank less than
$\lambda =sup\{\omega _1,\omega _1^{\omega _1},\omega _1^{(\omega _1^{\omega _1})},\ldots \}$
. Note that
$\lambda $
is the smallest solution of the ordinal equation
$\omega_1^{\varkappa} =\varkappa $
. Hence, the reader should carefully distinguish
$\mathbf {\Sigma }_\alpha (\mathcal {N})$
and
$\mathbf {\Sigma }^0_\alpha (\mathcal {N})$
. To give the reader an impression about the Wadge ordinal we note that the rank of the qo
$(\mathbf {\Delta }^0_\omega (\mathcal {N});\leq _W)$
is the
$\omega _1$
-st solution of the ordinal equation
$\omega _1^\varkappa =\varkappa $
[Reference Wadge34]. We summarize properties of the Wadge hierarchy of sets in the Baire space which will be tested for survival under extensions to cb
$_0$
-spaces (or to quasi-Polish spaces) and to Q-partitions:
-
1. The levels of the Wadge hierarchy are semi-well-ordered by inclusion.
-
2. The Wadge hierarchy does not collapse, i.e.,
$\mathbf {\Sigma }_\alpha \not \subseteq \mathbf {\Pi }_\alpha $
for all
$\alpha <\upsilon $
. -
3. The Wadge degrees of Borel sets coincide with the sets
$\mathbf {\Sigma }_\alpha \setminus \mathbf {\Pi }_\alpha $
,
$\mathbf {\Pi }_\alpha \setminus \mathbf {\Sigma }_\alpha $
,
$\mathbf {\Delta }_{\alpha +1}\setminus (\mathbf {\Sigma }_\alpha \cup \mathbf {\Pi }_\alpha )$
(where
$\alpha <\upsilon $
), and
$\mathbf {\Delta }_{\lambda }\setminus (\bigcup _{\alpha <\lambda }\mathbf {\Sigma }_\alpha )$
(where
$\lambda <\upsilon $
is a limit ordinal of countable cofinality). -
4. If
$\lambda <\upsilon $
is a limit ordinal of uncountable cofinality then
$\mathbf {\Delta }_{\lambda }= \bigcup _{\alpha <\lambda }\mathbf {\Sigma }_\alpha $
. -
5. All levels are downward closed under Wadge reducibility.
-
6. The levels in item (3) are precisely those having Wadge complete sets.
3 Infinitary fine hierarchies in a set
In this section we define the infinitary fine hierarchy and prove some of its basic properties. The Q-partition version of this hierarchy will be called the Q-IFH, for abbreviation. This section extends (and in fact simplifies) the corresponding material from §5 in [Reference Selivanov27]. The first three subsections describe some related technical notions.
3.1 Iterated
$Q$
-trees
Here we describe a notation system for levels of the Q-IFH. For any qo Q, a Q-tree is a pair
$(T,t)$
consisting of an infinite-branching well founded tree
$T\subseteq \omega ^*$
and a labeling
$t:T\to Q$
. Let
$\mathcal {T}(Q)$
be the set of Q-trees quasi-ordered by the relation:
$(T,t)\leq _h(V,v)$
iff there is a monotone function
$\varphi :T\to V$
with
$\forall v\in T(t(x)\leq _Qv(\varphi (x)))$
; such a function
$\varphi $
is called a morphism from
$(T,t)$
to
$(V,v)$
. As follows from Laver’s results in [Reference Laver and Rota14], if Q is bqo then so is also
$(\mathcal {T}(Q);\leq _h)$
which is usually shortened to
$\mathcal {T}(Q)$
. Thus,
$\mathcal {T}$
is an operator on the class BQO of all bqo’s. The operator
$\mathcal {T}$
and its iterates like
$\mathcal {T}\circ \mathcal {T}\circ \mathcal {T}$
were introduced in [Reference Selivanov22, Reference Selivanov27] and turned out crucial for characterizing some initial segments of
$\mathcal {W}_{\bar {k}}$
[Reference Selivanov, Kari, Manea and Petre26, Reference Selivanov27].
In [Reference Kihara and Montalbán11] a more powerful iteration procedure was invented which yields the set
$\mathcal {T}_{\omega _1}(Q)$
of labeled trees sufficient for characterizing
$\mathcal {W}_Q$
, as discussed in Introduction. We give a slightly different (but equivalent) definition of
$\mathcal {T}_{\omega _1}(Q)$
more convenient for our purposes here. The differences are caused by our desire to first work only with trees (introducing forests at the last stage), and to relate the qo
$\unlhd $
(defined below) to the qo
$\leq _h$
.
Let
$\sigma =\sigma (Q,\omega _1)=\{q,s_\alpha,F_q,F_\alpha \mid q\in Q,\alpha <\omega _1\}$
be the signature consisting of constant symbols q, unary function symbols
$s_\alpha $
, and
$\omega $
-ary function symbols
$F_q,F_\alpha $
(of course we assume all signature symbols to be distinct, in particular
$Q\cap \omega _1=\emptyset $
). Let
$\mathbb {T}_\sigma $
be the set of
$\sigma $
-terms without variables obtained by the standard inductive definition: Any constant symbol q is a term; if u is a term then so is also
$s_\alpha (u)$
; if
$u_0,u_1,\ldots $
are terms then so are also
$F_q(u_0,\ldots ), F_{\alpha }(u_0,\ldots )$
. Informally,
$F_q(u_0,\ldots )$
and
$F_{\alpha }(u_0,\ldots )$
are interpreted as
$q\to (u_0\sqcup \cdots )$
and
$s_\alpha (u_0)\to (u_1\sqcup \cdots )$
respectively (cf. [Reference Kihara and Montalbán11] where e.g., the first expression denotes the tree
$\varepsilon \cup 0\cdot u_0\cup \cdots $
with the root
$\varepsilon $
labeled by q), hence our modification simply avoids forests from the inductive definition.
The
$\sigma $
-terms are represented by (or even identified with) the normal well founded trees with constants on the leafs and other signature symbols on the nonleaf nodes such that the nodes labeled with
$s_\alpha $
have the unique successor while the nodes labeled by
$F_q$
of
$F_\alpha $
have all successors; we refer to such trees as syntactic trees, in order to distinguish them from trees of another kind. As usual, the rank of a term u, denoted
$rk(u)$
, is the rank of its syntactic tree; ranks enable definitions and proofs by induction on terms because the subterms of u are precisely the terms with syntactic tree of the form
$u(\tau )$
, see §2.2. Obviously, the set
$\mathbb {T}_\sigma $
is partitioned into three parts: constant terms (i.e., the terms q for some
$q\in Q$
), s-terms (i.e., the terms
$s_\alpha (u)$
for unique
$\alpha <\omega _1$
and
$u\in \mathbb {T}_\sigma $
) and F-terms (i.e., the terms
$F_q(u_0,\ldots )$
or
$F_\alpha (u_0,\ldots )$
for unique
$q\in Q$
,
$\alpha <\omega _1$
, and
$u_0,u_1,\ldots \in \mathbb {T}_\sigma $
). We define by induction on terms the binary relation
$\unlhd $
on
$\mathbb {T}_\sigma $
as follows (cf. definition 3.1 and its extensions in [Reference Kihara and Montalbán11]). The relation
$\unlhd $
on
$\mathbb {T}_\sigma $
is in fact equivalent to the relation
$\unlhd $
in [Reference Kihara and Montalbán11] restricted to the tree-terms.
-
1.
$q\trianglelefteq r$
iff
$q\leq _Qr$
; -
2.
$q\trianglelefteq s_\alpha (u)$
iff
$q\unlhd u$
; -
3.
$q\trianglelefteq F_r(u_0,\ldots )$
iff
$q\trianglelefteq r$
or
$q\trianglelefteq u_i$
for some
$i\geq 0$
; -
4.
$q\trianglelefteq F_\alpha (u_0,\ldots )$
iff
$q\trianglelefteq u_i$
for some
$i\geq 0$
; -
5.
$s_\alpha (u)\trianglelefteq r$
iff
$u\trianglelefteq r$
; -
6.
$s_\alpha (u)\trianglelefteq s_\beta (v)$
iff (
$\alpha <\beta $
and
$u\trianglelefteq s_\beta (v)$
) or (
$\alpha =\beta $
and
$u\trianglelefteq v$
) or (
$\alpha>\beta $
and
$s_\alpha (u)\trianglelefteq v$
); -
7.
$s_\alpha (u)\trianglelefteq F_r(v_0,\ldots )$
iff
$s_\alpha (u)\trianglelefteq r$
or
$s_\alpha (u)\trianglelefteq v_i$
for some
$i\geq 0$
; -
8.
$s_\alpha (u)\trianglelefteq F_\beta (v_0,\ldots )$
iff
$s_\alpha (u)\trianglelefteq s_\beta (v_0)$
or
$s_\alpha (u)\trianglelefteq v_i$
for some
$i\geq 1$
; -
9.
$F_q(u_0,\ldots )\trianglelefteq r$
iff
$q\trianglelefteq r$
and
$u_i\trianglelefteq r$
for all
$i\geq 0$
; -
10.
$F_q(u_0,\ldots )\trianglelefteq s_\alpha (v)$
iff
$q\trianglelefteq s_\alpha (v)$
and
$u_i\trianglelefteq s_\alpha (v)$
for all
$i\geq 0$
; -
11.
$F_q(u_0,\ldots )\trianglelefteq F_r(v_0,\ldots )$
iff (
$q\trianglelefteq r$
and
$u_i\trianglelefteq F_r(v_0,\ldots )$
for all
$i\geq 0$
) or
$F_q(u_0,\ldots )\trianglelefteq v_i$
for some
$i\geq 0$
; -
12.
$F_q(u_0,\ldots )\trianglelefteq F_\beta (v_0,\ldots )$
iff (
$q\trianglelefteq s_\beta (v_0)$
and
$u_i\trianglelefteq F_\beta (v_0,\ldots )$
for all
$i\geq 0$
) or
$F_q(u_0,\ldots )\trianglelefteq v_i$
for some
$i\geq 1$
; -
13.
$F_\alpha (u_0,\ldots )\trianglelefteq r$
iff
$s_\alpha (u_0)\trianglelefteq r$
and
$u_i\trianglelefteq r$
for all
$i\geq 1$
; -
14.
$F_\alpha (u_0,\ldots )\trianglelefteq s_\beta (v)$
iff
$s_\alpha (u_0)\trianglelefteq s_\beta (v)$
and
$u_i\trianglelefteq s_\beta (v)$
for all
$i\geq 1$
; -
15.
$F_\alpha (u_0,\ldots )\trianglelefteq F_r(v_0,\ldots )$
iff (
$s_\alpha (u_0)\trianglelefteq r$
and
$u_i\trianglelefteq F_r(v_0,\ldots )$
for all
$i\geq 1$
) or
$F_\alpha (u_0,\ldots )\trianglelefteq v_i$
for some
$i\geq 0$
; -
16.
$F_\alpha (u_0,\ldots )\trianglelefteq F_\beta (v_0,\ldots )$
iff (
$s_\alpha (u_0)\trianglelefteq s_\beta (v_0)$
and
$u_i\trianglelefteq F_\beta (v_0,\ldots )$
for all
$i\geq 1$
) or
$F_\alpha (u_0,\ldots )\trianglelefteq v_i$
for some
$i\geq 1$
.
From results in [Reference Kihara and Montalbán11] it follows that
$(\mathbb {T}_\sigma ;\trianglelefteq )$
is a bqo. Let
$\mathbb {T}_{q,s}$
be the set of constant terms and s-terms. Then
$(\mathbb {T}_{q,s};\trianglelefteq )$
is bqo, hence
$(\mathcal {T}(\mathbb {T}_{q,s});\leq _h)$
is also bqo. The next definition makes precise the relation between the introduced qo’s
$\trianglelefteq $
and
$\leq _h$
.
Definition 3.2. We associate with any
$u\in \mathbb {T}_\sigma $
the labeled tree
$T(u)$
by induction as follows:
$T(q)$
is the singleton tree labeled by q,
$T(s_\alpha (u))$
is the singleton tree labeled by
$s_\alpha (u)$
,
$T(F_q(u_0,\ldots ))=q\to (T(u_0)\sqcup T(u_1)\sqcup \cdots )$
,
$T(F_\alpha (u_0,\ldots ))=s_\alpha (u_0)\to (T(u_1)\sqcup T(u_2)\sqcup \cdots )$
.
Please be careful in distinguishing
$T(u)$
(which is an element of
$\mathcal {T}(\mathbb {T}_{q,s})$
) and the tree
$T(\tau )$
above
$\tau \in T$
. Obviously,
$T(u)$
is a singleton tree iff
$u\in \mathbb {T}_{q,s}$
. The next lemma is checked by cases from Definition 3.1 using induction on terms.
Lemma 3.3. The function
$u\mapsto T(u)$
is an isomorphism between
$(\mathbb {T}_\sigma ;\trianglelefteq )$
and
$(\mathcal {T}(\mathbb {T}_{q,s});\leq _h)$
.
-
1. If u has no entries of symbols
$s_\alpha,F_\alpha $
then
$T(u)$
is obtained from the syntactic tree of u by replacing any label
$F_q$
(on the nonleaf nodes) by label q. Therefore, the set of such trees
$T(u)$
essentially coincides with the set
$\mathcal {T}(Q)$
from the beginning of this subsection. -
2. For
$u=s_\beta (v)$
where
$v=F_\alpha (q_0,s_\gamma (F_{q_1}(r_0,r_1,\ldots )),s_\delta (q_2),q_3,q_4,\ldots )$
, we have:
$T(u)=(\{\varepsilon \},u)$
(the singleton tree labeled by u itself), and
$T(v)=\{\varepsilon,0,1,2,3,\ldots \}$
labeled resp. by
$s_\alpha (q_0),s_\gamma (F_{q_1}(r_0,r_1,\ldots )),s_\delta (q_2),q_3,q_4,\ldots $
.
The next lemma is immediate by induction on terms.
Lemma 3.5. Any term
$u\in \mathbb {T}_\sigma $
satisfies precisely one of the following alternatives:
-
1.
$u=q$
for a unique
$q\in Q$
; -
2.
$u=s_{\beta _0}\cdots s_{\beta _m}(q)$
for unique
$m<\omega $
,
$\beta _0,\ldots,\beta _m<\omega _1$
,
$q\in Q$
; -
3.
$u=F_q(u_0,\ldots )$
for unique
$q\in Q$
and
$u_0,\ldots \in \mathbb {T}_\sigma $
; -
4.
$u=F_\alpha (u_0,\ldots )$
for unique
$\alpha <\omega _1$
, and
$u_0,\ldots \in \mathbb {T}_\sigma $
; -
5.
$u=s_{\beta _0}\cdots s_{\beta _m}(F_q(u_0,\ldots ))$
for unique
$m<\omega $
,
$\beta _0,\ldots,\beta _m<\omega _1$
,
$q\in Q$
,
$u_0,\ldots \in \mathbb {T}_\sigma $
; -
6.
$u=s_{\beta _0}\cdots s_{\beta _m}(F_\alpha (u_0,\ldots ))$
for unique
$m<\omega $
,
$\beta _0,\ldots,\beta _m<\omega _1$
,
$\alpha <\omega _1$
,
$u_0,\ldots \in \mathbb {T}_\sigma $
.
Terms from items (1) and (2) above will be called singleton terms. With any singleton term u a unique element
$q\in Q$
is associated denoted by
$q(u)$
. Below we will also need the following technical notions.
Definition 3.6. We associate with any
$u\in \mathbb {T}_\sigma $
the ordinal
$sh(u)$
and the term
$u'\in \mathbb {T}_\sigma $
as follows: if u is not an s-term then
$sh(u)=0$
and
$u'=u$
, otherwise
$sh(u)=\omega ^{\beta _0}+\cdots +\omega ^{\beta _m}$
and
$u'=q,F_q(u_0,\ldots ),F_\alpha (u_0,\ldots )$
if u satisfies resp. the alternative (2), (5), or (6) above.
Note that “sh” comes from “shift.” We collect some obvious properties of
$u'$
.
-
1.
$u'=u$
iff u is not an s-term. -
2.
$u'$
is a subterm of u, so
$u'\trianglelefteq u$
and if u is an s-term then
$rk(u')<rk(u)$
. -
3.
$u'$
is not an s-term, hence
$u''=u'$
. -
4.
$u'\in Q$
iff u is a singleton term.
Definition 3.8. We associate with any nonsingleton term
$u\in \mathbb {T}_\sigma $
the set
$\mathcal {F}(u)$
of sequences
$S=(\tau _0,\ldots )$
in
$\omega ^*$
constructed as follows:
$\tau _0\in T(u')=(T_0,t_0)$
; if
$t_0(\tau _0)$
is a singleton term then
$S=(\tau _0)$
, otherwise
$\tau _1\in T(t_0(\tau _0)')=(T_1,t_1)$
; if
$t_1(\tau _1)$
is a singleton term then
$S=(\tau _0,\tau _1)$
, otherwise
$\tau _2\in T(t_1(\tau _1)')=(T_2,t_2)$
; and so on.
-
1. For any
$u\in \mathbb {T}_\sigma $
and
$\tau \in T(u)$
,
$t_u(\tau )\trianglelefteq u$
, where
$t_u$
is the labeling function on
$T(u)$
, and
$rk(t_u(\tau ))\leq rk(u)$
. -
2. If u is not a singleton term then
$rk(t_u(\tau )')< rk(u)$
for every
$\tau \in T(u)$
. -
3. For any nonsingleton term
$u\in \mathbb {T}_\sigma $
, every sequence in
$\mathcal {F}(u)$
is finite.
Proof. (1) For
$u\in \mathbb {T}_{q,s}$
the assertion is obvious because
$\tau =\varepsilon $
and
$t_u(\tau )= u$
. Let
$u=F_q(u_0,\ldots )$
, then either
$\tau =\varepsilon $
or
$\tau \in T(u_i)$
for a unique
$i\geq 0$
. In the first case
$t_u(\tau )= q\trianglelefteq u$
and
$rk(t_u(\tau ))=0< rk(u)$
. In the second case by induction we have
$t_u(\tau )= t_{u_i}(\tau )\trianglelefteq u_i\trianglelefteq u$
and
$rk(t_u(\tau ))=rk(t_{u_i}(\tau ))\leq rk(u_i)<rk(u)$
.
Finally, let
$u=F_\alpha (u_0,\ldots )$
. Then either
$\tau =\varepsilon $
or
$\tau \in T(u_i)$
for a unique
$i\geq 1$
. In the first case
$t_u(\tau )= s_\alpha (u_0)\trianglelefteq u$
and
$rk(t_u(\tau ))=rk(s_\alpha (u_0))=rk (u_0)+1\leq rk(u)$
. In the second case we have:
$t_u(\tau )= t_{u_i}(\tau )\trianglelefteq u_i\trianglelefteq u$
and
$rk(t_u(\tau ))=rk(t_{u_i}(\tau ))\leq rk(u_i)<rk(u)$
.
(2) Since u is not singleton, u is not a q-term. If u is an s-term then
$t_u(\tau )=u$
, so by Lemma 3.7(2) we have
$rk(t_u(\tau )')=rk(u')<rk(u)$
. If
$u=F_q(u_0,\ldots )$
then, by the proof of item (1),
$rk(t_u(\tau )')\leq rk(t_u(\tau ))<rk(u)$
. Finally, let
$u=F_\alpha (u_0,\ldots )$
. For
$\tau \not =\varepsilon $
the assertion follows again from the proof of item (1). For
$\tau =\varepsilon $
we have
$t_u(\varepsilon )=s_\alpha (u_0)$
, hence, by the proof of item (1) and Lemma 3.7(2),
$rk(t_u(\varepsilon )')=rk(s_\alpha (u_0)')<rk(s_\alpha (u_0))\leq rk(u)$
.
(3) Suppose the contrary: the sequence
$\tau _0,\tau _1,\ldots $
from Definition 3.6 is infinite, hence all terms
$t_0(\tau _0),t_1(\tau _1),\dots $
are not singleton. By item (2) we then have
$rk(u')> rk(t_0(\tau _0)')> rk(t_1(\tau _1)')>\cdots $
, contradicting the well-foundedness of syntactic trees.⊣
With any
$(\tau _0,\ldots,\tau _m)\in \mathcal {F}(u)$
we associate the constant
$q(\tau _0,\ldots,\tau _m)=t_m(\tau _m)\in Q$
. For any
$q\in Q$
we set
$\mathcal {F}_q(u)=\{(\tau _0,\ldots,\tau _m)\in \mathcal {F}(u)\mid q=t_m(\tau _m)\}$
.
-
1. If u has no entries of symbols
$s_\alpha,F_\alpha $
then
$sh(u)=0$
,
$u'=u$
, and
$\mathcal {F}(u)=\{(\tau )\mid \tau \in T(u)\}$
. -
2. For the term
$u=s_\beta (v)$
from Examples 3.4(2), we have:
$sh(u)=\omega^\beta $
,
$u'=v$
,
$T(u')=\{\varepsilon,0,1,2,3,\ldots \}=(T_0,t_0)$
,
$t_0(\varepsilon )=s_\alpha (q_0)$
,
$t_0(0)=s_\gamma (F_{q_1}(r_0,r_1,\ldots ))$
,
$t_0(1)=s_\delta (q_2)$
,
$t_0(2)=q_3,\,t_0(3)=q_4,\ldots $
,
$sh(t_0(\varepsilon ))=\omega ^\alpha $
,
$sh(t_0(0))=\omega ^\gamma $
,
$sh(t_0(1))=\omega ^\delta $
,
$sh(t_0(2))=0,\ sh(t_0(3))=0,\ldots $
,
$t_0(\varepsilon)'=q_0$
,
$t_0(0)'=F_{q_1}(r_0,r_1,\ldots )$
,
$t_0(1)'=q_2$
,
$t_0(2)'=q_3,\,t_0(3)'=q_4,\ldots $
. Thus,
$\mathcal {F}(u)=\{(\varepsilon,\varepsilon), (0,\varepsilon ),(0,0),(0,1),\ldots,(1,\varepsilon ),(2),(3),\ldots \}$
and the corresponding labels of elements of
$\mathcal {F}(u)$
are
$q_0,q_1,r_0,r_1,\ldots,q_2,q_3,q_4,\ldots $
.
To be more consistent with notation of previous papers and of Introduction, we sometimes denote
$\mathcal {T}(\mathbb {T}_{q,s})$
by
$\mathcal {T}_{\omega _1}(Q)$
and use the structures from Lemma 3.3 interchangeably. Let
$\mathcal {T}^\sqcup _{\omega _1}(Q)$
be the set of nonempty labeled forests obtained from trees in
$\mathcal {T}_{\omega _1}(Q)$
by deleting the root (alternatively and equivalently, one can think of
$\mathcal {T}^\sqcup _{\omega _1}(Q)$
as the set of countable disjoint unions of trees in
$\mathcal {T}_{\omega _1}(Q)$
). The relation
$\leq _h$
is extended to the larger structure of forests in the obvious way.
The characterization of
$\mathcal {W}_Q$
(see Introduction) in terms of the iterated labeled trees may be now described as follows (see [Reference Kihara and Montalbán11] for more details). The relation
$\simeq $
below denotes the equivalence of qo’s.
Proposition 3.11. [Reference Kihara and Montalbán11] We have
$(\mathcal {T}^\sqcup _{\omega _1}(Q);\leq _h)\simeq (\mathbf {\Delta }^1_1(Q^{\mathcal {N}});\leq _W)$
, for every countable bqo Q. The isomorphism of quotient-posets is induced by a map
$\mu :\mathcal {T}_{\omega _1}(Q)\to \mathbf {\Delta }^1_1(Q^{\mathcal {N}})$
sending trees onto the
$\sigma $
-join irreducible elements.
For more details on the map
$\mu $
see Section 4.4 below. For any
$\gamma <\omega _1$
, apply the construction above to the smaller signature
$\sigma (Q,\gamma )=\{q,s_\alpha,F_q,F_\alpha \mid q\in Q,\alpha <\gamma \}$
in place of
$\sigma (Q,\omega _1)$
. The resulting set of labeled trees is denoted by
$\mathcal {T}_{\omega ^\gamma }(Q)$
. We obtain an operator
$\mathcal {T}_{\omega ^\gamma }$
on BQO. Finally, for any
$\alpha <\omega _1$
we define the operator
$\mathcal {T}_{\alpha }$
on BQO as follows:
$\mathcal {T}_0$
is the identity operator, and for any positive countable ordinal
$\alpha $
we set
$\mathcal {T}_\alpha =\mathcal {T}_{\omega ^{\alpha _0}}\circ \cdots \circ \mathcal {T}_{\omega ^{\alpha _n}}$
where
$n<\omega $
and
$\alpha _0\geq \cdots \geq \alpha _n$
are the unique ordinals with
$\alpha =\omega ^{\alpha _0}+\cdots +\omega ^{\alpha _n}$
. The set of forests
$\mathcal {T}^\sqcup _{\alpha }(Q)$
is obtained from
$\mathcal {T}_{\alpha }(Q)$
by the above construction. In particular,
$\mathcal {T}_{\alpha +1}=\mathcal {T}_{\alpha }\circ \mathcal {T}$
where
$\mathcal {T}$
is the operator from the beginning of this subsection.
3.2 Hierarchy bases
We recall (see e.g., [Reference Selivanov27]) the technical notion of a (hierarchy) base. Such bases serve as a starting point for constructing the Q-IFH. They have nothing in common with topological bases.
Definition 3.12. By a base in a set X we mean a sequence
${\mathcal L}(X)=\{{\mathcal L}_\alpha \}_{\alpha <\omega _1}$
,
${\mathcal L}_\alpha ={\mathcal L}_\alpha (X)\subseteq P(X)$
, such that every
${\mathcal L}_\alpha $
is closed under countable union and finite intersection (in particular,
$\emptyset, X\in {\mathcal L}_\alpha $
), and
${\mathcal L}_\alpha \cup \check {\mathcal L}_\alpha \subseteq {\mathcal L}_\beta \cap \check {\mathcal L}_\beta $
for all
$\alpha <\beta <\omega _1$
.
A major natural example of a hierarchy base in a topological space X is the Borel base
$\mathcal {L}(X)=\{\mathbf {\Sigma }^0_{1+\alpha }(X)\}_{\alpha <\omega _1}$
. There are “unnatural” bases, e.g., the bases
$\{\mathbf {B}(X),\mathbf {B}(X),\ldots \}$
and
$\{P(X),P(X),\cdots \}$
over which any IFH of sets collapses to the first level.
With any base
$\mathcal {L}(X)$
in X we associate some new bases as follows. For any
$\beta <\omega _1$
, let
$\mathcal {L}^\beta (X)=\{\mathcal {L}_{\beta +\alpha }(X)\}_{\alpha }$
; we call this base in X the
$\beta $
-shift of
$\mathcal {L}(X)$
. For any
$U\subseteq X$
, let
$\mathcal {L}(U)=\{\mathcal {L}_{\alpha }(U)\}$
where
$\mathcal {L}_{\alpha }(U)=\{U\cap S\mid S\in \mathcal {L}_{\alpha }(X)\}$
; we call this base in U the U-restriction of
$\mathcal {L}(X)$
.
-
1.
$(\mathcal {L}^\beta )^\gamma (X)=\mathcal {L}^{\beta +\gamma }(X)$
. -
2. If
$\beta *<\alpha *$
(see §2.1) then
$\mathcal {L}^\beta _\alpha (X)=\mathcal {L}_\alpha (X)$
. Therefore, many levels of
$\mathcal {L}(X)$
remain unchanged under the
$\beta $
-shift.
Proof. (1) Indeed,
$((\mathcal {L}^\beta )^\gamma )_\alpha =\mathcal {L}^\beta _{\gamma +\alpha }=\mathcal {L}_{\beta +(\gamma +\alpha )}=\mathcal {L}_{(\beta +\gamma )+\alpha }=\mathcal {L}^{\beta +\gamma }_\alpha $
.
(2) Since
$\beta +\alpha =\alpha $
by the definition of
$\beta *$
and
$\alpha *$
,
$\mathcal {L}^\beta _\alpha (X)=\mathcal {L}_{\beta +\alpha }(X)=\mathcal{L}_\alpha (X)$
.⊣
By a morphism
$g:\mathcal {L}(X)\to \mathcal {L}(Y)$
of bases we mean a function
$g:P(X)\to P(Y)$
such that
$g(\emptyset )=\emptyset $
,
$g(X)=Y$
,
$g(\bigcup _nU_n)=\bigcup _ng(U_n)$
for every countable sequence
$\{U_n\}$
in
$P(X)$
(so, in particular,
$U\subseteq V$
implies
$g(U)\subseteq g(V)$
), and
$U\in {\mathcal L}_\alpha (X)$
implies
$g(U)\in {\mathcal L}_\alpha (Y)$
for each
$\alpha <\omega _1$
. Obviously, the identity function on
$P(X)$
is a morphism of any base in X to itself, and if
$g:\mathcal {L}(X)\to \mathcal {L}(Y)$
and
$h:\mathcal {L}(Y)\to \mathcal {L}(Z)$
are morphisms of bases then
$h\circ g:\mathcal {L}(X)\to \mathcal {L}(Z)$
is also a morphism. We illustrate the notion of morphism with the following well known fact. Recall that a function
$f:X\to Y$
between spaces is
$\mathbf {\Sigma }^0_{1+\alpha }$
-measurable iff
$f^{-1}(U)\in \mathbf {\Sigma }^0_{1+\alpha }(X)$
for any open set U in Y.
Lemma 3.14. Let
$f:X\to Y$
be
$\mathbf {\Sigma }^0_{1+\alpha }$
-measurable and let
$\mathcal {L}(X),\mathcal {L}(Y)$
be the Borel bases in
$X,Y$
resp. Then
$f^{-1}:P(Y)\to P(X)$
is a morphism from
$\mathcal {L}(Y)$
to
$\mathcal {L}^\alpha (X)$
. In particular, if f is continuous then
$f^{-1}:P(Y)\to P(X)$
is a morphism of
$\mathcal {L}(Y)$
to
$\mathcal {L}(X)$
.
The following class of bases will be frequently mentioned in the sequel.
Definition 3.15. A base
${\mathcal L}(X)$
is reducible if every
${\mathcal L}_\alpha (X)$
has the
$\sigma $
-reduction property.
The next fact follows from results in [Reference Kechris9] and [Reference Selivanov25] mentioned in the end of Subsection 2.2.
Lemma 3.16. The Borel base in every zero-dimensional cb
$_0$
-space is reducible. The one-shift of the Borel base in every cb
$_0$
-space is reducible.
We conclude this subsection with introducing some auxiliary notions used in the sequel. For any tree
$T\subseteq \omega ^*$
and a T-family
$\{U_\tau \}$
of subsets of X (
$\tau $
ranges over T), we define the T-family
$\{\tilde {U}_\tau \}$
of subsets of X by
$\tilde {U}_\tau =U_\tau \setminus \bigcup \{U_{\tau '}\mid \tau \sqsubset \tau '\in T\}$
; the sets
$\tilde {U}_\tau $
will be called components of the family
$\{U_\tau \}$
. The T-family
$\{U_\tau \}$
is monotone if
$U_\tau \supseteq U_{\tau '}$
for all
$\tau \sqsubseteq \tau '\in T$
. We associate with any T-family
$\{U_\tau \}$
the monotone T-family
$\{U^{\prime }_\tau \}$
by
$U^{\prime }_\tau =\bigcup _{\tau ^{\prime }\sqsupseteq \tau }U_{\tau ^{\prime }}$
. Below we mostly work with monotone T-families though the next lemma shows that they are in a sense equivalent to arbitrary ones.
Lemma 3.17. Let T be a well founded tree,
$\mathcal {L}(X)$
be a base, and
$\{U_\tau \}$
be a T-family of
${\mathcal L}_\alpha $
-sets. Then the components are differences of
${\mathcal L}_\alpha $
-sets (hence they belong to
${\mathcal L}_{\alpha +1}\cap \check {\mathcal L}_{\alpha +1}$
),
$\bigcup _\tau U_\tau =\bigcup _\tau \tilde {U}_\tau $
,
$\tilde {U}_\tau =\widetilde {U'}_\tau $
, and
$\tilde {U}_\tau \cap \tilde {U}_{\tau '}=\emptyset $
for
$\tau \sqsubset \tau '\in T$
.
Proof. We check only the second assertion, the proofs of others being even simpler. Since
$\tilde {U}_\tau \subseteq U_\tau $
,
$\bigcup _\tau U_\tau \supseteq \bigcup _\tau \tilde {U}_\tau $
. Conversely, let
$x\in \bigcup _\tau U_\tau $
. Then the set
$\{\tau \in T\mid x\in U_\tau \}$
is nonempty. Since
$(T;\sqsupseteq )$
is well founded,
$ x\in U_\tau $
for some maximal element
$\tau $
of
$(\{\tau \in T\mid x\in U_\tau \};\sqsubseteq )$
; but then
$x\in \tilde {U}_\tau $
.⊣
The next lemma is also easy.
Lemma 3.18. Let T be a well founded tree,
$\mathcal {L}(X)$
be a base,
$\{U^i_\tau \}_i$
be a sequence of monotone T-families of
${\mathcal L}_\alpha $
-sets, and
$U_\tau =\bigcup _iU^i_\tau $
for each
$\tau \in T$
. Then
$\{U_\tau \}$
is a monotone T-family of
${\mathcal L}_\alpha $
-sets and
$\tilde {U}_\tau \subseteq \bigcup _i\widetilde {U^i_\tau }$
for each
$\tau \in T$
.
We call a T-family
$\{V_\tau \}$
of
${\mathcal L}_\alpha $
-sets reduced if it is monotone and satisfies
$V_{\tau i}\cap V_{\tau j}=\emptyset $
for all
$\tau i,\tau j\in T$
,
$i\neq j$
. Obviously, for any reduced T-family
$\{V_\tau \}$
of
${\mathcal L}_\alpha $
-sets the components
$\tilde {V}_\tau $
are pairwise disjoint. The reduced T-families form a very special but important class of the monotone T-families. The next lemma is checked by a top-down (assuming that trees grow downwards) application of the
$\sigma $
-reduction property.
Lemma 3.19. Let T be an infinitely-branching well founded tree,
$\mathcal {L}(X)$
be a base,
$\{U_\tau \}$
be a monotone T-family of
${\mathcal L}_\alpha $
-sets, and let
${\mathcal L}_\alpha $
have the
$\sigma $
-reduction property. Then there is a reduced T-family
$\{V_\tau \}$
of
${\mathcal L}_\alpha $
-sets such that
$V_\tau \subseteq U_\tau $
,
$\bigcup _\tau V_\tau =\bigcup _\tau U_\tau $
,
$\bigcup _i\{V_{\tau i}\mid \tau i\in T\}=\bigcup _i\{V_\tau \cap U_{\tau i}\mid \tau i\in T\}$
, and
$\tilde {V}_\tau \subseteq \tilde {U}_\tau $
for each
$\tau \in T$
.
Proof. If
$T=\{\varepsilon \}$
is singleton, there is nothing to prove. Otherwise, let
$\{V_i\}$
be a reduct of
$\{U_i\}$
and let
$U^{\prime }_{i\tau }=V_i\cap U_{i\tau }$
for all
$i\tau \in T$
. Apply this procedure to the trees
$T(i)$
and further downwards whenever possible. Since T is well founded, we will finally obtain a desired reduced family which we call a reduct of
$\{U_\tau \}$
.⊣
Lemma 3.20. For every well founded tree T, a base
$\mathcal {L}$
(X),
$\rho \in T$
and
$\alpha <\omega _1$
, there is a unique reduced T-family
$\{U_\tau \}$
of
${\mathcal L}_\alpha $
-sets such that
$\tilde {U}_\rho =X$
(and then necessarily
$\tilde {U}_\tau =\emptyset $
for all
$\tau \in T\setminus \{\rho \}$
).
Proof. Obviously, it is enough to set
$U_\tau =X$
if
$\tau \sqsubseteq \rho $
and
$U_\tau =\emptyset $
otherwise.⊣
3.3 Defining
$Q$
-partitions by iterated families
Here we define the notion of a u-family (
$u\in \mathbb {T}_\sigma $
) in a given base
$\mathcal {L}(X)$
and explain how such (iterated) families determine Q-partitions of X. The definitions use induction on terms in §3.1, induction scheme of Definition 3.2 and Lemma 3.3. The u-families F are defined simultaneously for all
$X,\mathcal {L}(X)$
as follows.
-
1. F is a q-family in
$\mathcal {L}(X)$
iff
$F=\{X\}$
. -
2. The
$s_\alpha (u)$
-families in
$\mathcal {L}(X)$
coincide with the u-families in
$\mathcal {L}^{\omega ^\alpha }(X)$
. -
3. F is an
$F_q(u_0,\ldots )$
-family in
$\mathcal {L}(X)$
iff
$F=(\{U_\tau \},\{F_\tau \})$
where
$\{U_\tau \}$
is a monotone T-family of
${\mathcal L}_0$
-sets with
$U_\varepsilon =X$
and, for each
$\tau \in T$
,
$F_\tau $
is a
$t(\tau )$
-family in
$\mathcal {L}(\tilde {U}_\tau )$
, where
$(T,t)=T(F_q(u_0,\ldots ))$
. -
4. F is an
$F_\alpha (u_0,\ldots )$
-family in
$\mathcal {L}(X)$
iff
$F=(\{U_\tau \},\{F_\tau \})$
where
$\{U_\tau \}$
is a monotone T-family of
${\mathcal L}_0$
-sets with
$U_\varepsilon =X$
and, for each
$\tau \in T$
,
$F_\tau $
is a
$t(\tau )$
-family in
$\mathcal {L}(\tilde {U}_\tau )$
, where
$(T,t)=T(F_\alpha (u_0,\ldots ))$
.
Reduced u-families F are defined by taking
$\{U_\tau \},F_\tau $
in (3) and (4) to be reduced. From Lemma 3.5 we obtain the following information on the structure of u-families in
$\mathcal {L}(X)$
where we use notions from Definition 3.6.
Lemma 3.22. Let F be a u-family in
$\mathcal {L}(X)$
. If u is a singleton term then
$F=\{X\}$
, otherwise
$F=(\{U_\tau \},\{F_\tau \})$
where
$\{U_\tau \}$
is a monotone
$T(u')$
-family of
${\mathcal L}^{sh(u)}_0$
-sets with
$U_\varepsilon =X$
and, for each
$\tau \in T(u')$
,
$F_\tau $
is a
$t(\tau )$
-family in
$\mathcal {L}^{sh(u)}(\tilde {U}_\tau )$
.
Now we define (again simultaneously for all
$X,\mathcal {L}(X)$
) the notion “a u-family F in
$\mathcal {L}(X)$
determines a partition
$A\in Q^X$
”.
-
1. A q-family F in
$\mathcal {L}(X)$
determines A iff
$A=\lambda x.q$
is the constant function
$A(x)=q$
. -
2. An
$s_\alpha (u)$
-family F in
$\mathcal {L}(X)$
determines A iff F determines A as a u-family in
$\mathcal {L}^{\omega ^\alpha }(X)$
. -
3. For
$u\in \{F_q(u_0,\ldots ),F_\alpha (u_0,\ldots )\}$
, a u-family
$F=(\{U_\tau \},\{F_\tau \})$
in
$\mathcal {L}(X)$
determines A iff for each
$\tau \in T(u)$
,
$F_\tau $
determines the restriction
$A|_{\tilde {U}_\tau }$
of A to
$\tilde {U}_\tau $
.
By definitions above and Lemma 3.22, a u-family F in
$\mathcal {L}(X)$
that determines a Q-partition A may be interpreted as a mind-change “algorithm” for computing the value
$A(x)\in Q$
for any given
$x\in X$
as follows. We use the set
$\mathcal {F}(u)$
from Definition 3.8 and Lemma 3.9.
If u is a singleton term,
$A(x)=q(u)$
is a constant Q-partition. Otherwise,
$F=(\{U_{\tau _0}\},\{F_{\tau _0}\})$
where
$\{U_{\tau _0}\}$
is a monotone
$u'$
-family of
${\mathcal L}^{sh(u)}_0$
-sets with
$U_\varepsilon =X$
and, for each
$\tau _0\in T(u')$
,
$F_{\tau _0}$
is a
$t_0(\tau _0)$
-family in
$\mathcal {L}^{sh(u)}(\tilde {U}_{\tau _0})$
(which coincides with the
$t_0(\tau _0)'$
-family in
$\mathcal {L}^{sh(u)+sh(t_0(\tau _0))}(\tilde {U}_{\tau _0})$
). Since the components
$\tilde {U}_{\tau _0}$
(called first level components of F) cover X (by the definition of a monotone family),
$x\in \tilde {U}_{\tau _0}$
for some
$\tau _0\in T(u')$
;
$\tau _0$
is searched by the usual mind-change procedure working with differences of
${\mathcal L}^{sh(u)}_0$
-sets (see Lemma 3.17).
If the term
$t_0(\tau _0)$
is singleton,
$A|_{\tilde {U}_{\tau _0}}$
is a constant Q-partition and we have computed
$A(x)\in Q$
. Otherwise,
$F_{\tau _0}=(\{U_{\tau _0\tau _1}\},\{F_{\tau _0\tau _1}\})$
and we can continue the computation as above and find a second level component
$\tilde {U}_{\tau _0\tau _1}$
of F containing x; this is a harder mind-change procedure working with differences of
${\mathcal L}^{sh(u)+sh(t_0(\tau _0))}_0$
-sets. We continue this process until we reach a sequence
$(\tau _0,\ldots,\tau _m)\in \mathcal {F}(u)$
such that
$x\in \tilde {U}_{\tau _0\cdots \tau _m}$
and
$t_m(\tau _m)$
is a singleton term; such components
$\tilde {U}_{\tau _0\cdots \tau _m}$
are called terminating and have the associated constants
$q(\tau _0,\ldots,\tau _m)\in Q$
. Note that the terminating components cover X and if the family F is reduced then the terminating components form a partition of X. In any case we have:
$A^{-1}(q)=\bigcup \{\tilde {U}_{\tau _0\cdots \tau _m}\mid (\tau _0,\ldots,\tau _m)\in \mathcal {F}_q(u)\}$
for each
$q\in Q$
.
If the family F above is reduced then the computation is “linear” since the components of each level are pairwise disjoint and cover the parent component, otherwise the computation is “parallel” since already at the first level x may belong to several components
$\tilde {U}_{\tau _0}$
(and F may determine no Q-partition).
The described procedure enables to write a u-family F, where u is not a singleton term, in an explicit (but not completely precise) form of
$u'$
-family
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
in
${\mathcal L}^{sh(u)}(X)$
which is sometimes more intuitive than the form
$(\{U_{\tau }\},\{F_\tau \})$
above.
-
1. If u has no entries of symbols
$s_\alpha,F_\alpha $
then a u-family F in
$\mathcal {L}(X)$
is essentially a monotone family
$T(u)$
-family
$\{U_\tau \}$
of
$\mathcal {L}_0(X)$
-sets with
$U_\varepsilon =X$
. If F determines a Q-partition A then
$A(x)=t(\tau )$
whenever
$x\in \widetilde {U}_\tau $
where
$T(u)=(T,t)$
. This case leads to the extension of the difference hierarchy over
$\mathcal {L}_0(X)$
to Q-partitions (for
$Q=\bar {k}$
this is described in [Reference Selivanov21, Reference Selivanov27]). -
2. For the term
$u=s_\beta (v)$
from Examples 3.4(2) and 3.10(2), any u-family has the form
$(\{U_\varepsilon,U_0,U_1,U_2,U_3,\ldots \},\{U_{\varepsilon,\varepsilon }\},\{U_{0,\varepsilon },U_{0,0},U_{0,1},\ldots \},\{U_{1,\varepsilon }\})$
where
$\{U_\varepsilon,U_0,U_1,U_2,U_3,\ldots \}$
is a monotone
$T(u')$
-family of
$\mathcal {L}_{\omega ^\beta }$
-sets with
$U_\varepsilon =X$
,
$U_{\varepsilon,\varepsilon }=\widetilde {U}_\varepsilon $
,
$\{U_{0,\varepsilon },U_{0,0},U_{0,1},\ldots \}$
is a monotone
$t_0(0)$
-family of
$\mathcal {L}_{\omega ^\beta +\omega ^\gamma }$
-sets with
$U_{0,\varepsilon }=\widetilde {U}_0$
, and
$U_{1,\varepsilon }=\widetilde {U}_1$
.
We formulate some properties of the introduced notions. The next lemma is immediate.
Lemma 3.25. Let u be a nonsingleton term and let
$A\in Q^X$
be determined by a
$u'$
-family
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
in
${\mathcal L}^{sh(u)}(X)$
.
-
1. If
$u'=F_q(u_0,\ldots )$
then the
$u_i$
-family
$(\{U_{i\sigma _0}\},\{U_{i\sigma _0\tau _1}\},\ldots )$
in
${\mathcal L}^{sh(u)}(U_i)$
determines
$A|_{U_i}$
for each
$i\geq 0$
. -
2. If
$u'=F_\alpha (u_0,\ldots )$
then the
$u_{i+1}$
-family
$(\{U_{i\sigma _0}\},\{U_{i\sigma _0\tau _1}\},\ldots )$
in
${\mathcal L}^{sh(u)}(U_{i+1})$
determines
$A|_{U_{i+1}}$
for each
$i\geq 0$
.
Let
$f:X\to Y$
be a function such that
$f^{-1}$
is a morphism from
$\mathcal {L}(Y)$
to
$\mathcal {L}(X)$
. Associate with any u-family F in
$\mathcal {L}(Y)$
the u-family
$f^{-1}(F)$
in
$\mathcal {L}(X)$
as follows: if
$u=q$
then
$f^{-1}(F)=\{X\}$
; if
$u=s_\alpha (v)$
then
$f^{-1}(F)$
is the v-family
$f^{-1}(F)$
in
$\mathcal {L}^{\omega ^\alpha }(X)$
; in the remaining cases we have
$F=(\{U_\tau \},\{F_\tau \})$
, and we set
$f^{-1}(F)=(\{f^{-1}(U_\tau )\},\{f^{-1}(F_\tau )\})$
. Clearly,
$f^{-1}(F)$
is indeed a u-family in
$\mathcal {L}(X)$
. The next lemma is immediate.
Lemma 3.26. If a u-family F in
$\mathcal {L}(Y)$
determines A then the u-family
$f^{-1}(F)$
in
$\mathcal {L}(X)$
determines
$A\circ f$
.
Now we associate with any u-family F in
$\mathcal {L}(X)$
and any
$V\subseteq X$
the u-family
$F|_V$
in the V-restriction
$\mathcal {L}(V)$
(see §3.2) as follows: if
$u=q$
then
$F|_V=\{V\}$
; if
$u=s_\alpha (v)$
then
$F|_V$
is the v-family
$F|_V$
in
$\mathcal {L}^{\omega ^\alpha }(V)$
; in the remaining cases we have
$F=(\{U_\tau \},\{F_\tau \})$
, and we set
$F|_V=(\{V\cap U_\tau \},\{F_\tau |_V\})$
. Obviously,
$F|_V$
is indeed a u-family in
$\mathcal {L}(V)$
. The next lemma is immediate by induction.
Lemma 3.27. If a u-family F in
$\mathcal {L}(X)$
determines A then the u-family
$F|_V$
in
$\mathcal {L}(V)$
determines
$A|_V$
.
Let
$\{G_i\}$
,
$G_i=(\{U^i_{\tau _0}\},\{U^i_{\tau _0\tau _1}\},\ldots )$
, be a sequence of u-families (u is a nonsingleton term) in
$\mathcal {L}(Y_i)$
,
$Y_i\subseteq X$
. Then
$G=(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
, where
$U_{\tau _0}=\bigcup _iU^i_{\tau _0}$
,
$U_{\tau _0\tau _1}=\bigcup _iU^i_{\tau _0\tau _1}\ldots $
, is a u-family in
$\mathcal {L}(Y)$
where
$Y=\bigcup _iY_i$
. The next lemma follows from Lemma 3.18.
Lemma 3.28. Let
$A\in Q^X$
. If the u-family
$G_i$
in
$\mathcal {L}(Y_i)$
determines
$A|_{Y_i}$
for each
$i\geq 0$
then the u-family G in
$\mathcal {L}(Y)$
determines
$A|_Y$
.
The next lemma is also clear.
Lemma 3.29. Let
$A\in Q^X$
,
$Y\in \mathcal {L}_0(X)\cap \check {\mathcal {L}}_0(X)$
,
$A(x)=q$
for
$x\in X\setminus Y$
, let
$A|_Y$
be determined by a u-family F in
$\mathcal {L}(Y)$
, and let
$\tilde {U}_{\tau _0\cdots \tau _m}$
be a terminating component of F with
$q=q(\tau _0,\ldots,\tau _m)$
. Then there is a u-family
$F'$
in
$\mathcal {L}(X)$
such that its
$(\tau _0,\ldots,\tau _m)$
-terminating component is
$\tilde {U}_{\tau _0\cdots \tau _m}\cup (X\setminus Y)$
, all other terminating components coincide with those of F, and
$F'$
determines A.
Let
$F=(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
and
$G=(\{V_{\tau _0}\},\{V_{\tau _0\tau _1}\},\ldots )$
be u-families in
$\mathcal {L}(X)$
. We say that G is a reduct of F if G is reduced and
$\tilde {V}_{\tau _0\cdots \tau _m}\subseteq \tilde {U}_{\tau _0\cdots \tau _m}$
for each
$(\tau _0,\ldots,\tau _m)\in \mathcal {F}(u)$
.
Lemma 3.30. Let
${\mathcal L}(X)$
be a reducible base in X and
$u\in \mathbb {T}_\sigma $
. Then any u-family F in
${\mathcal L}(X)$
has a reduct G. Moreover, if F determines A then any reduct of F determines A.
Proof. We follow the procedure of computing
$A(x)$
described above. If u is a singleton term, we set
$G=F=\{X\}$
; then
$F,G$
determine the same constant Q-partition. Otherwise, F has the form as above. Let G as above be obtained from F by repeated reductions from Lemma 3.19, so in particular
$\tilde {V}_{\tau _0\cdots \tau _m}\subseteq \tilde {U}_{\tau _0\cdots \tau _m}$
for each
$(\tau _0,\ldots,\tau _m)\in \mathcal {F}(u)$
.
For the second assertion, let F determine A and let G be a reduct of F. For any
$x\in X$
, let
$\tilde {V}_{\tau _0\cdots \tau _m}$
be the unique terminating component of G containing x. Then also
$x\in \tilde {U}_{\tau _0\cdots \tau _m}$
, hence
$A(x)=q(\tau _0,\ldots,\tau _m)$
and G determines A.⊣
The next lemma follows from the results above.
Lemma 3.31. Every u-family F in
${\mathcal L}(X)$
determines at most one Q-partition of X. Every reduced u-family G in
${\mathcal L}(X)$
determines precisely one Q-partition of X.
Proof. The second assertion follows from the remark that the terminating components of G form a partition of X. For the first assertion, let F in
${\mathcal L}(X)$
determine Q-partitions
$A,B$
of X. Let
$x\in X$
. If u is a singleton term, F determines a constant Q-partition, so in particular
$A(x)=B(x)$
. Otherwise,
$F=(\{U_\tau \},\{F_\tau \})$
as specified above. By the procedure of computing
$A(x)$
, there is a terminating component
$\tilde {U}_{\tau _0\cdots \tau _m}\ni x$
of F. By Definition 3.23,
$A(x)=q(\tau _0,\ldots,\tau _m)=B(x)$
.⊣
3.4 Infinitary fine hierarchy over a base
Here we define the Q-IFH over a given base and prove some of its properties.
Definition 3.32. For any base
$\mathcal {L}(X)$
in X, qo Q, and
$u\in \mathbb {T}_\sigma $
, let
$\widehat {\mathcal {L}}(X,u)=\bigcup \{\mathcal {L}(X,v)\mid v\trianglelefteq u\}$
where
$\mathcal {L}(X,v)$
is the set of Q-partitions of X determined by some v-family in
$\mathcal {L}(X)$
. The family
$\{\widehat {\mathcal {L}}(X,u)\}_{u\in \mathbb {T}_\sigma }$
is called the infinitary Q-fine hierarchy over
$\mathcal {L}(X)$
.
Corollary 3.33. If Q is bqo then
$(\{\widehat {\mathcal {L}}(X,u)\mid u\in \mathbb {T}_\sigma \};\subseteq )$
is bqo.
Proof. Clearly,
$u\mapsto \widehat {\mathcal {L}}(X,u)$
is a monotone surjection from bqo
$(\mathbb {T}_\sigma ;\trianglelefteq )$
onto
$(\{\widehat {\mathcal {L}}(X,u)\mid u\in \mathbb {T}_\sigma \};\subseteq )$
. Hence, the latter structure is also bqo.⊣
The algorithm of computing
$A(x)$
described above explains in which sense the Q-IFH over
$\mathcal {L}(X)$
may be considered as an “iterated difference hierarchy.” Classes
$\mathcal {L}(X,u)$
play a major technical role in the proofs below while properties of classes
$\widehat {\mathcal {L}}(X,u)$
capture more properties of the Q-Wadge hierarchy. Clearly, if Q is an antichain then
$\mathcal {L}(X,u)=\widehat {\mathcal {L}}(X,u)$
for every
$u\in \mathbb {T}_\sigma $
. By Lemma 3.3, we can equivalently denote the Q-IFH over
$\mathcal {L}(X)$
as
$\{\widehat {\mathcal {L}}(X,T)\}_{T\in \mathcal {T}_{\omega _1}(Q)}$
, as we did in Introduction. The next lemma describes the behavior of Q-IFH w.r.t. the operations on bases from §3.2.
-
1. For any
$\alpha <\omega _1$
,
$\mathcal {L}(X,s_\alpha (u))=\mathcal {L}^{\omega ^\alpha }(X,u)$
and
$\mathcal {L}(X,u)=\mathcal {L}^{sh(u)}(X,u')$
. -
2. For any
$V\subseteq X$
,
$A\in \mathcal {L}(X,u)$
implies
$A|_V\in \mathcal {L}(V,u)$
. -
3. Let u be nonsingleton and A determined by a u-family
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}(X)$
. If
$u'=F_q(u_0,\ldots )$
(resp.
$u'=F_\alpha (u_0,\ldots )$
) then
$A|_{U_i}\in \mathcal {L}(X,u_i)$
for each
$i\geq 0$
(resp.
$i\geq 1$
). -
4. Let
$A\in Q^X$
,
$u_0,u_1,\ldots \in \mathbb {T}_\sigma $
, and let
$\{U_i\}_{i\geq 0}$
be nonempty open sets not exhausting X such that
$A|_V=\lambda v.q$
(where
$V=\mathcal {N}\setminus \bigcup _iU_i$
) and
$A|_{U_i}\in \mathcal {L}(U_i,u_i)$
for all
$i\geq 0$
. Then
$A\in \mathcal {L}(X,u)$
where
$u=F_q(u_0,\ldots )$
. -
5. Let
$A\in Q^X$
,
$u_0,u_1,\ldots \in \mathbb {T}_\sigma $
, and let
$\{U_i\}_{i\geq 1}$
be nonempty open sets not exhausting X such that
$A|_V\in \mathcal {L}(X,s_\alpha (u_0))$
(where
$V=\mathcal {N}\setminus \bigcup _{i\geq 1}U_i$
) and
$A|_{U_i}\in \mathcal {L}(U_i,u_i)$
for all
$i\geq 1$
. Then
$A\in \mathcal {L}(X,u)$
where
$u=F_\alpha (u_0,\ldots )$
.
Proof. (1), (2) and (3) follow resp. from Definition 3.23, Lemma 3.27, and Lemma 3.25.
(4) Let
$A|_{U_i}\in \mathcal {L}(X,u_i)$
be determined by a
$u_i$
-family
$G_i=(\{U^i_{\tau _0}\},\{U^i_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}(U_i)$
, for each
$i\geq 0$
. By Definition 3.2,
$T(u)=q\to (T(u_0)\sqcup T(u_1)\sqcup \cdots )$
. We define the u-family
$G=(\{V_{\tau _0}\},\{V_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}(X)$
as follows:
$V_\varepsilon =X$
,
$V_{i\tau _0}=U^i_{\tau _0}$
,
$V_{i\tau _0\tau _1}=U^i_{\tau _0\tau _1}$
, and so on. Then G determines A, hence
$A\in \mathcal {L}(X,u)$
.
(5) Similar to (4).⊣
Next we discuss inclusions of levels of the Q-IFH.
-
1.
$\mathcal {L}(X,u)\subseteq \mathcal {L}(X,s_\alpha (u))$
. -
2.
$\mathcal {L}(X,q)\subseteq \mathcal {L}(X,F_q(u_0,\ldots ))$
. -
3.
$\mathcal {L}(X,u_i)\subseteq \mathcal {L}(X,F_q(u_0,\ldots ))$
for all
$i\geq 0$
. -
4.
$\mathcal {L}(X,s_\alpha (u_0))\subseteq \mathcal {L}(X,F_\alpha (u_0,\ldots ))$
. -
5.
$\mathcal {L}(X,u_{i+1})\subseteq \mathcal {L}(X,F_\alpha (u_0,\ldots ))$
for all
$i\geq 0$
. -
6. Let
$u,v\in \mathbb {T}_\sigma $
,
$\beta,\gamma <\omega _1$
, and
$\mathcal {L}^\beta (X,u)\subseteq \mathcal {L}^\gamma (X,v)$
for all X and
$\mathcal {L}(X)$
. Then
$\mathcal {L}^{\alpha +\beta }(X,u)\subseteq \mathcal {L}^{\alpha +\gamma }(X,v)$
for all
$\alpha <\omega _1,X,\mathcal {L}(X)$
.
Proof. (1) Let
$A\in \mathcal {L}(X,u)$
, then A is determined by a u-family F in
$\mathcal {L}(X)$
. By Definition 3.12, F is also a u-family in
$\mathcal {L}^{\omega ^\alpha }(X)$
, hence
$A\in \mathcal {L}^{\omega ^\alpha }(X,u)$
. By Lemma 3.34(1),
$A\in \mathcal {L}(X,s_\alpha (u))$
.
(2) and (3) follow resp. from Lemmas 3.20 and 3.34(3). Let
$F_i=G$
. For any
$\tau \in T(u)\setminus \{i\}$
, let
$F_\tau $
be the trivial reduced
$t(\tau )$
-family in
$\mathcal {L}(\emptyset )$
with empty components. By Definition 3.2, the family F determines A.
Items (4) and (5) are checked by manipulations similar to those in (2) and (3).
(6) For the base
$\mathcal {L}^\alpha (X)$
the given inclusion reads
$(\mathcal {L}^\alpha )^\beta (X,u)\subseteq (\mathcal {L}^\alpha )^\gamma (X,v)$
. By Lemma 3.13(1),
$\mathcal {L}^{\alpha +\beta }(X,u)\subseteq \mathcal {L}^{\alpha +\gamma }(X,v)$
.⊣
The main result about inclusions of levels of the Q-IFH is the following theorem.
Theorem 3.36. If Q is antichain and
$u\trianglelefteq v$
, then
$\mathcal {L}(X,u)\subseteq \mathcal {L}(X,v)$
for all
$X,\mathcal {L}(X)$
.
Proof. We argue by induction of Definition 3.1.
(1) Let
$q\trianglelefteq r$
, then
$q\leq _Qr$
, hence
$q=r$
, hence trivially
$\mathcal {L}(X,q)\subseteq \mathcal {L}(X,r)$
.
(2) Let
$q\trianglelefteq s_\alpha (u)$
, then
$q\trianglelefteq u$
, hence by induction and Lemma 3.35(1)
$\mathcal {L}(X,q)\subseteq \mathcal {L}(X,u)\subseteq \mathcal {L}(X,s_\alpha (u))$
.
(3) Let
$q\trianglelefteq F_r(u_0,\ldots )$
, then
$q\trianglelefteq r$
or
$q\trianglelefteq u_i$
for some
$i\geq 0$
, and the inclusion follows by induction and Lemma 3.35(2,3).
(4) Let
$q\trianglelefteq F_\alpha (u_0,\ldots )$
, then
$q\trianglelefteq s_\alpha (u_0)$
or
$q\trianglelefteq u_i$
for some
$i\geq 1$
, and the inclusion follows by induction and Lemma 3.35(4,5).
(5) Let
$s_\alpha (u)\trianglelefteq r$
, then
$u\trianglelefteq r$
. By induction,
$\mathcal {L}^{\omega ^\alpha }(X,u)\subseteq \mathcal {L}^{\omega ^\alpha }(X,r)=\{\lambda x.r\}$
. By Lemma 3.34(1),
$\mathcal {L}(X,s_\alpha (u))=\{\lambda x.r\}\subseteq \mathcal {L}(X,r)$
.
(6) Let
$s_\alpha (u)\trianglelefteq s_\beta (v)$
. Then (
$\alpha <\beta $
and
$u\trianglelefteq s_\beta (v)$
) or (
$\alpha =\beta $
and
$u\trianglelefteq v$
) or (
$\alpha>\beta $
and
$s_\alpha (u)\trianglelefteq v$
). In the first case, by induction we have
$\mathcal {L}(X,u)\subseteq \mathcal {L}(X,s_\beta (v))\subseteq \mathcal {L}^{\omega ^\beta }(X,v)$
. By Lemmas 3.35(6), 3.13(2) and 3.34(1),
$\mathcal {L}(X,s_\alpha (u))=\mathcal {L}^{\omega ^\alpha }(X,u)\subseteq \mathcal {L}^{\omega ^\alpha +\omega ^\beta }(X,v)=\mathcal {L}^{\omega ^\beta }(X,v)=\mathcal {L}(X,s_\beta (v))$
. In the second case, by induction we have
$\mathcal {L}(X,u)\subseteq \mathcal {L}(X,v)$
, hence
$\mathcal {L}^{\omega ^\alpha }(X,u)\subseteq \mathcal {L}^{\omega ^\beta }(X,v)$
, hence
$\mathcal {L}(X,s_\alpha (u))\subseteq \mathcal {L}(X,s_\beta (v))$
. The third case is even easier.
(7) Let
$s_\alpha (u)\trianglelefteq F_r(v_0,\ldots )$
, then
$s_\alpha (u)\trianglelefteq r$
or
$s_\alpha (u)\trianglelefteq v_i$
for some
$i\geq 0$
. The assertion follows by Lemma 3.35(2) or (3), respectively.
(8) Let
$s_\alpha (u)\trianglelefteq F_\beta (v_0,\ldots )$
, then
$s_\alpha (u)\trianglelefteq s_\beta (v_0)$
or
$s_\alpha (u)\trianglelefteq v_i$
for some
$i\geq 1$
. The assertion follows by Lemma 3.35(4) or (5), respectively.
(9) Let
$F_q(u_0,\ldots )\trianglelefteq r$
, then
$q\trianglelefteq r$
and
$u_i\trianglelefteq r$
for all
$i\geq 0$
. In this case the argument of item (5) works.
(10) Let
$F_q(u_0,\ldots )\trianglelefteq s_\alpha (v)$
, then
$q\trianglelefteq s_\alpha (v)$
and
$u_i\trianglelefteq s_\alpha (v)$
for all
$i\geq 0$
. If v is a singleton term, the argument of item (9) works, so let v be a nonsingleton term. Without loss of generality we way think that v is an F-term (otherwise,
$\mathcal {L}^{\omega ^\alpha }(X,v)=\mathcal {L}^{\omega ^\alpha +sh(v)}(X,v')$
, and we can work with the F-term
$v'$
instead of v).
Let
$A\in \mathcal {L}(X,F_q(u_0,\ldots ))$
, we have to show that
$A\in \mathcal {L}(X,s_\alpha (v))$
. Let
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
be a u-family in
$\mathcal {L}(X)$
that determines A, then
$A(x)=q$
for each
$x\in \tilde {U}_\varepsilon $
(note that
$\tilde {U}_\varepsilon \in \mathcal {L}^{\omega ^\alpha }_0(X)\cap \check {\mathcal {L}}^{\omega ^\alpha }_0(X)$
) and, by Lemma 3.25,
$A|_{U_i}$
is determined by the
$u_i$
-family
$(\{U_{i\tau _1}\},\ldots )$
in
$\mathcal {L}(U_i)$
for every
$i\geq 0$
. By induction,
$A|_{U_i}\in \mathcal {L}^{\omega ^\alpha }(U_i,v)$
for every
$i\geq 0$
, so let
$G_i=(\{V^i_{\tau _0}\},\{V^i_{\tau _0\tau _1}\},\ldots )$
be a v-family in
$\mathcal {L}^{\omega ^\alpha }(U_i)$
that determines
$A|_{U_i}$
. By Lemma 3.28, the v-family
$G=\bigcup _iG_i=(\{V_{\tau _0}\},\{V_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}^{\omega ^\alpha }(\bigcup _iU_i)$
determines
$A_{\bigcup _iU_i}$
. By Lemma 3.29, the
$s_\alpha (v)$
-family
$G'$
determines A, hence
$A\in \mathcal {L}(X,s_\alpha (v))$
.
(11) Let
$F_q(u_0,\ldots )\trianglelefteq F_r(v_0,\ldots )$
, then (
$q\trianglelefteq r$
and
$u_i\trianglelefteq F_r(v_0,\ldots )$
for all
$i\geq 0$
) or
$F_q(u_0,\ldots )\trianglelefteq v_i$
for some
$i\geq 0$
; the second case follows from Lemma 3.35(3), so consider the first case. Since Q is antichain,
$q=r$
. Let
$A\in \mathcal {L}(X,F_q(u_0,\ldots ))$
, we have to show that
$A\in \mathcal {L}(X,F_q(v_0,\ldots ))$
. Let
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
be a u-family in
$\mathcal {L}(X)$
, where
$u=F_q(u_0,\ldots )$
, that determines A, then
$A(x)=q$
for each
$x\in \tilde {U}_\varepsilon $
, and, by Lemma 3.25,
$A|_{U_i}$
is determined by the family
$(\{U_{i\tau _1}\},\ldots )$
in
$\mathcal {L}(U_i)$
for each
$i\geq 0$
. By induction,
$A|_{U_i}\in \mathcal {L}(U_i,v)$
for each
$i\geq 0$
, where
$v=F_q(v_0,\ldots )$
, so
$A|_{U_i}$
is determined by a v-family
$G_i=(\{V^i_{\tau _0}\},\{V^i_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}(U_i)$
. By Lemma 3.28, the v-family
$G=(\{V_{\tau _0}\},\{V_{\tau _0\tau _1}\},\ldots )$
in
$\mathcal {L}(\bigcup _iU_i)$
determines
$A|_{\bigcup _iU_i}$
. Correcting the v-family G by changing
$V_\varepsilon $
to X, we obtain a v-family
$G'$
in
$\mathcal {L}(X)$
that determines A. Thus,
$A\in \mathcal {L}(X,v)$
.
Items (12), (15) and (16) are checked similar to (10) and (11), item (13) similar to (9), item (14) similar to (11).⊣
We conclude this subsection with a result about the reduction property. Let the classes red-
$\mathcal {L}(X,u)$
be defined as the classes
$\mathcal {L}(X,u)$
in Definition 3.32 but with the reduced families in place of arbitrary families. Note that in many spaces the inclusion red-
$\mathcal {L}(X,u)\subset \mathcal {L}(X,u)$
is proper (e.g., this holds for
$X=P\omega $
where two nonempty open sets always have nonempty intersection). Let red-
$\widehat {\mathcal {L}}(X,u)=\bigcup \{$
red-
$\mathcal {L}(X,v)\mid v\trianglelefteq u\}$
.
Proposition 3.37. If
$\mathcal {L}(X)$
is a reducible base then
$\mathcal {L}(X,u)=$
red-
$\mathcal {L}(X,u)$
and
$\widehat {\mathcal {L}}(X,u)=$
red-
$\widehat {\mathcal {L}}(X,u)$
for each
$u\in \mathbb {T}_\sigma $
.
Proof. The inclusion
$\supseteq $
is obvious. Conversely, let
$A\in \mathcal {L}(X,u)$
, then A is determined by a u-family F in
$\mathcal {L}(X)$
. By Lemma 3.30, A is determined by a u-family G in
$\mathcal {L}(X)$
which is a reduct of F. Thus, A is in red-
$\mathcal {L}(X,u)$
. The assertion for
$\widehat {\mathcal {L}}$
follows.⊣
4 Infinitary fine hierarchies in cb
$_0$
-spaces
In this section we study the Q-IFH in cb
$_0$
-spaces. We show that some important properties are preserved by continuous open surjections while others are not, and we give the set-theoretic description of the Q-Wadge hierarchy in the Baire space. From now on all bases we discuss are the Borel bases
$\mathcal {L}(X)=\{\mathbf {\Sigma }^0_{1+\alpha }(X)\}_{\alpha <\omega _1}$
in cb
$_0$
-spaces X.
4.1 General properties
Here we collect some general properties of Q-IFH in cb
$_0$
-spaces. As we know from Lemma 3.16, most of levels of the Borel hierarchy in X have the
$\sigma $
-reduction property. By Proposition 3.37, this implies the following simpler characterization of many levels of the Q-IFH in X.
Proposition 4.1. For any cb
$_0$
-space X and any
$u\in \mathbb {T}_\sigma $
, red-
$\mathcal {L}^1(X,u)=\mathcal {L}^1(X,u)$
. If X is zero-dimensional then red-
$\mathcal {L}(X,u)=\mathcal {L}(X,u)$
for all
$u\in \mathbb {T}_\sigma $
. Similarly for
$\widehat {\mathcal {L}}(X,u)$
.
Proposition 4.2. Let
$f:X\to Y$
be a continuous function and
$u\in \mathbb {T}_\sigma $
. Then
$A\in \mathcal {L}(Y,u)$
implies
$A\circ f\in \mathcal {L}(X,u)$
, and similarly for
$\widehat {\mathcal {L}}(X,u)$
.
Proof. Let
$A\in Q^Y$
be defined by a u-family F in
$\mathcal {L}(Y)$
. Since the preimage function
$f^{-1}:P(Y)\to P(X)$
is a morphism from
$\mathcal {L}(Y)$
to
$\mathcal {L}(X)$
by Lemma 3.14,
$A\circ f$
is determined by the u-family
$f^{-1}(F)$
in
$\mathcal {L}(X)$
by Lemma 3.26. Therefore,
$A\circ f\in \mathcal {L}(X,u)$
. The assertion for
$\widehat {\mathcal {L}}(X,u)$
follows in the obvious way.⊣
Next we briefly discuss the relation of Q-IFH in X to the Wadge reducibility
$\leq _W$
of Q-partitions of X (see Introduction).
-
1. If Q is antichain (in particular,
$Q=\bar {k}$
) then the levels
$\widehat {\mathcal {L}}(X,u)$
and
$\mathcal {L}(X,u)$
are closed downwards under Wadge reducibility. -
2. For any zero-dimensional space X, a qo Q and
$u\in \mathbb {T}_\sigma $
, the level
$\widehat {\mathcal {L}}(X,u)$
is closed downwards under Wadge reducibility. -
3. For any cb
$_0$
-space X, a qo Q and
$u\in \mathbb {T}_\sigma $
, the level
$\widehat {\mathcal {L}}^1(X,u)$
is closed downwards under Wadge reducibility.
Proof. (1) Since
$\leq _Q$
is the equality on Q,
$A\leq _WB$
iff
$A=B\circ f$
for some continuous function f on X. Thus, the assertion is a particular case of Proposition 4.2 when
$X=Y$
.
(2) Let
$A\leq _WB$
via f and
$B\in \widehat {\mathcal {L}}(X,u)$
, so
$B\in \mathcal {L}(X,v)$
for some
$v\trianglelefteq u$
. Then
$C=B\circ f\in \mathcal {L}(X,v)$
by Proposition 4.2 where
$X=Y$
, and
$A(x)\leq _QC(x)$
for each
$x\in X$
. By Proposition 4.1, C is determined by a reduced v-family
$F=(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
. Any
$x\in X$
belongs to a unique terminating component
$\tilde {U}_{\tau _0\cdots \tau _m}$
with
$C(x)=q(\tau _0,\ldots,\tau _m)$
. In the syntactic tree of v, any
$q=C(x)$
is either a leaf label or the subscript of an
$F_q$
-label. Replacing any such
$C(x)$
by
$A(x)$
, we obtain a term w such that
$A\in \mathcal {L}(X,w)$
(because A is determined by F in which terminating labels are changed accordingly). It is easy to see that
$w\trianglelefteq v$
, hence
$A\in \widehat {\mathcal {L}}(X,u)$
.
(3) The argument of item (2) works.⊣
4.2 Preservation property
Here we show that all levels of the Q-IFH are preserved by continuous open surjections.
With any function
$f:X\to Y$
between cb
$_0$
-spaces we associate the function
$A\mapsto f[A]$
from
$P(X)$
to
$P(Y)$
defined by
$$ \begin{align*}f[A]=\{y\in Y\mid A\cap f^{-1}(y)\text{ is nonmeager in }f^{-1}(y)\}.\end{align*} $$
Its importance stems from Baire-category properties of cb
$_0$
-spaces recalled in §2.3. The function
$A\mapsto f[A]$
(known as the existential category quantifier, see e.g., §8.J in [Reference Kechris9]) was used e.g., in [Reference de Brecht4, Reference Saint Raymond17, Reference Selivanov27]; we changed its notation trying to make it more convenient in our context.
The next two lemmas generalize some results from [Reference de Brecht4, Reference Saint Raymond17, Reference Selivanov27]. Please distinguish
$f[A]$
and the image
$f(A)$
of A under f.
Lemma 4.4.
-
1. The function
$A\mapsto f[A]$
is a morphism from
$\mathcal {L}(X)$
to
$\mathcal {L}(Y)$
, and
$f[A]\subseteq f(A)$
for each
$A\subseteq X$
. -
2. If T is a well founded tree and
$\{U_\tau \}$
is a T-family of
$\mathbf {\Sigma }^0_{1+\alpha }(X)$
-sets then
$\{f[U_\tau ]\}$
is a T-family of
$\mathbf {\Sigma }^0_{1+\alpha }(Y)$
-sets, and
$\widetilde {f[U_\tau ]}\subseteq f[\tilde {U}_\tau ]$
for each
$\tau \in T$
.
Proof. (1) Let
$y\in f[A]$
, then
$A\cap f^{-1}(y)$
is nonmeager in
$f^{-1}(y)$
. Then
$A\cap f^{-1}(y)$
is nonempty, hence
$y\in f(A)$
and
$f[A]\subseteq f(A)$
. In particular,
$f[\emptyset ]=\emptyset $
. To show that
$f[X]=Y$
we have to check that, for any
$y\in Y$
,
$f^{-1}(y)$
is nonmeager in
$f^{-1}(y)$
, and this follows from quasi-Polishness of
$f^{-1}(y)$
. The property that
$f[\bigcup _nU_n]=\bigcup _nf[U_n]$
for every countable sequence
$\{U_n\}$
in
$P(X)$
is well known. The (nontrivial) fact that
$U\in \mathbf {\Sigma }^0_{1+\alpha }(X)$
implies
$f[U]\in \mathbf {\Sigma }^0_{1+\alpha }(Y)$
, follows from Proposition 2.3, see [Reference de Brecht4, Reference Saint Raymond17].
(2) The first assertion follows from (1), so we check the second one. Let
$y\in \widetilde {f[U_\tau ]}$
, i.e.,
$y\in f[U_\tau ]\setminus \bigcup \{f[U_{\tau '}]\mid \tau \sqsubset \tau '\in T\}$
. Then
$U_\tau \cap f^{-1}(y)$
is nonmeager in
$f^{-1}(y)$
and, for each
$\tau \sqsubset \tau '\in T$
,
$U_{\tau '}\cap f^{-1}(y)$
is meager in
$f^{-1}(y)$
. Then
$(\bigcup \{U_{\tau '}\mid \tau \sqsubset \tau '\in T\})\cap f^{-1}(y)$
is meager in
$f^{-1}(y)$
, hence
$\tilde {U}_\tau =U_\tau \setminus \bigcup \{U_{\tau '}\mid \tau \sqsubset \tau '\in T\}$
is nonmeager in
$f^{-1}(y)$
, i.e.,
$y\in f[\tilde {U}_\tau ]$
.⊣
We associate with any u-family F in
$\mathcal {L}(X)$
the u-family
$f[F]$
in
$\mathcal {L}(Y)$
by induction as follows: if u is a singleton term (hence
$F=\{X\}$
) then we set
$f[F]=\{Y\}$
; otherwise,
$u'$
is an F-term and
$F=(\{U_\tau \},\{F_\tau \})$
is a
$u'$
-family in
$\mathcal {L}^{sh(u)}(X)$
; we set
$f[F]=(\{f[U_\tau ]\},\{f[F_\tau ]\})$
which is a
$u'$
-family in
$\mathcal {L}^{sh(u)}(Y)$
, hence a u-family in
$\mathcal {L}(Y)$
.
Lemma 4.5. Let
$u\in \mathbb {T}_{\sigma }$
,
$A\in Y\to Q$
, and
$A\circ f\in \mathcal {L}(X,u)$
be determined by a u-family F in
$\mathcal {L}(X)$
. Then A is determined by the u-family
$f[F]$
in
$\mathcal {L}(X)$
.
Proof. If u is a singleton term, the assertion is obvious. Otherwise,
$u'$
is an F-term and the family F has the form
$(\{U_{\tau _0}\},\{U_{\tau _0\tau _1}\},\ldots )$
, so
$f[F]$
has the form
$(\{f[U_{\tau _0}]\},\{f[U_{\tau _0\tau _1}]\},\ldots )$
. We have to show that A is determined by
$f[F]$
, i.e., for each
$y\in Y$
,
$A(y)=q(\tau _0,\ldots,\tau _m)$
, for every terminating component
$\widetilde {f[U_{\tau _0\cdots \tau _m}]}$
of
$f(F)$
containing y. Such a component exists by induction on the rank of u (see the procedure of computing
$A(y)$
described above).
For any given
$y\in Y$
and any such component
$\widetilde {f[U_{\tau _0\cdots \tau _m}]}$
we have
$y\in f[\tilde {U}_{\tau _0\cdots \tau _m}]$
by Lemma 4.4(2), so
$y=f(x)$
for some
$x\in \tilde {U}_{\tau _0\cdots \tau _m}$
. Thus,
$A(y)=(A\circ f)(x)=q(\tau _0,\ldots,\tau _m)$
.⊣
As an immediate corollary of Lemmas 4.5 and 3.26 we obtain the following preservation property for levels of the Q-IFH.
Theorem 4.6. Let
$\mathcal {L}(X),\mathcal {L}(Y)$
be Borel bases in cb
$_0$
-spaces
$X,Y$
respectively,
$f:X\to Y$
a continuous open surjection,
$A:Y\to Q$
, and
$u\in \mathbb {T}_{\sigma }$
. Then
$A\circ f\in \mathcal {L}(X,u)$
iff
$A\in \mathcal {L}(Y,u)$
, and similarly for
$\widehat {\mathcal {L}}(X,u)$
.
Proof. Let
$A\in \mathcal {L}(Y,u)$
, then A is determined by a u-family F in
$\mathcal {L}(Y)$
. By Lemma 3.26,
$A\circ f\in \mathcal {L}(X,u)$
. Conversely, let
$A\circ f\in \mathcal {L}(X,u)$
, then
$A\circ f$
is determined by a u-family F in
$\mathcal {L}(X)$
. By Lemma 4.5, A is determined by the u-family
$f[F]$
in
$\mathcal {L}(Y)$
, hence
$A\in \mathcal {L}(Y,u)$
. The assertion for
$\widehat {\mathcal {L}}(X,u)$
follows in the obvious way.⊣
4.3 Inheritance of HK-type theorems
Here we apply the preservation theorem to show that some versions of the Hausdorff–Kuratowski theorem (which we call HK-type theorems for short) are inherited by the continuous open images.
Recall that the Hausdorff theorem in a space X says that
$\bigcup _{\beta <\omega _1}\mathbf {\Sigma }^{-1,1}_\beta (X)=\mathbf {\Delta }^0_{2}(X)$
. The difference hierarchy
$\{\mathbf {\Sigma }^{-1,1}_\beta (X)\}$
over the open sets in X is usually defined using a difference operator on the transfinite sequences of open sets (see e.g.,, [Reference Kechris9, Reference Selivanov25]). Since in this paper we promote using labeled trees instead of ordinals, we note that levels
$\mathbf {\Sigma }^{-1,1}_\beta (X)$
are easily characterized using
$\bar {2}$
-labeled trees in
$\mathcal {T}(\bar {2})$
(see the beginning of §3.1). Namely, by Proposition 4.9 in [Reference Selivanov25], there is a tree
$T_\beta \in \mathcal {T}(\bar {2})$
of rank
$\beta $
such that
$\mathbf {\Sigma }^{-1,1}_\beta (X)=\mathcal {L}(X,T_\beta )$
, and any
$T\in \mathcal {T}(\bar {2})$
is
$\trianglelefteq $
-equivalent to one of
$T_\beta,\bar {T}_\beta $
, where
$u\mapsto \bar {u}$
is the automorphism induced by
$i\mapsto 1-i$
. Thus, the Hausdorff theorem for X may be written as
$\bigcup \{\mathcal {L}(X,T)\mid T\in \mathcal {T}(\bar {2})\}=\mathbf {\Delta }^0_{2}(X)$
(in this subsection it is more convenient to work with labeled trees rather that with terms, see Lemma 3.3).
The Kuratowski theorem extends the Hausdorff theorem to any successor level of the Borel hierarchy in X (see §2.3 for the formulation of this theorem for quasi-Polish spaces). The Kuratowski theorem has a reformulation in terms of
$\bar {2}$
-labeled trees in just the same way as for the Hausdorff theorem. Namely, the tree form of the HK theorem in X looks like
$\bigcup \{\mathcal {L}(X,T)\mid T\in \mathcal {T}_\alpha (\mathcal {T}(\bar {2}))\}=\mathbf {\Delta }^0_{1+\alpha +1}(X)$
for each
$\alpha <\omega _1$
, where some notation from the end of Section 3.1 is used; in particular,
$\mathcal {T}_\alpha \circ \mathcal {T}=\mathcal {T}_{\alpha +1}$
.
The tree form of the HK-theorem readily extends to Q-partitions which yields our first example of inheritance of the HK-type theorems. We say that a cb
$_0$
-space X satisfies the HK-theorem for Q-partitions in level
$1+\alpha +1<\omega _1$
, iff
$\bigcup \{\mathcal {L}(X,T)\mid T\in \mathcal {T}_{\alpha +1}(Q)\}=\mathbf {\Delta }^0_{1+\alpha +1}(Q^X)$
. We define the qo
$\leq _{co}$
on cb
$_0$
-spaces by:
$Y\leq _{co}X$
iff there is a continuous open surjection from X onto Y.
Theorem 4.7. If a cb
$_0$
-space X satisfies the HK-theorem for Q-partitions in level
$1+\alpha +1<\omega _1$
, then so does every space
$Y\leq _{co}X$
.
Proof. Since the inclusion
$\bigcup \{\mathcal {L}(X,T)\mid T\in \mathcal {T}_{\alpha +1}(Q)\}\subseteq \mathbf {\Delta }^0_{1+\alpha +1}(Q^X)$
is easy, we check only the opposite inclusion. Let
$A\in \mathbf {\Delta }^0_{1+\alpha +1}(Q^Y)$
and let
$f:X\to Y$
be a continuous open surjection. Then
$A\circ f\in \mathbf {\Delta }^0_{1+\alpha +1}(Q^X)$
, hence
$A\circ f\in \mathcal {L}(X,T)$
for some
$T\in \mathcal {T}_{\alpha +1}(Q)$
. By Theorem 4.6,
$A\in \mathcal {L}(Y,T)$
.⊣
Our second example is concerned with a version of HK-theorem for limit levels of the Borel hierarchy. The problem of finding a construction principle for the
$\mathbf {\Delta }^0_\lambda $
-subsets of the Baire space in the case that
$\lambda $
is a positive limit countable ordinal was posed long ago by Luzin and resolved in [Reference Wadge34] as an important step to the complete description of the Wadge hierarchy. We state the inheritance property for an extension of this result from sets to Q-partitions. We say that a cb
$_0$
-space X satisfies the Wadge property for Q-partitions in a limit level
$\lambda <\omega _1$
, iff
$\bigcup \{\mathcal {L}(X,T)\mid T\in \mathcal {T}_\lambda (Q)\}=\mathbf {\Delta }^0_{\lambda }(Q^X)$
.
The next result is proved in just the same way as the previous theorem.
Theorem 4.8. If a cb
$_0$
-space X satisfies the Wadge property for Q-partitions in a limit level
$\lambda <\omega _1$
, then so does every space
$Y\leq _{co}X$
.
4.4 Characterizing
$Q$
-Wadge hierarchy in the Baire space
Here we show that the Q-IFH in the Baire space coincides with the Wadge hierarchy of Q-partitions. The structure of Wadge degrees of Borel measurable Q-partitions of
$\mathcal {N}$
was characterized in [Reference Kihara and Montalbán11] (Proposition 3.11 in §3.1). In particular, a set-theoretic characterization of the nonself-dual levels of the Q-Wadge hierarchy (with levels
$\mathcal {W}(\mathcal {N},T)$
from Introduction) was provided (Lemma 3.16 and its extensions), by defining classes
$\Sigma _T$
of Q-partitions using set-theoretic operations and showing that
$\mathcal {W}(\mathcal {N},T)=\widehat {\Sigma }_T$
for each
$T\in \mathcal {T}_{\omega _1}(Q)$
where
$\widehat {\Sigma }_T=\{A\in Q^{\mathcal {N}}\mid \exists B\in \Sigma _T(A\leq _WB)\}$
.
The definition of
$\Sigma _T$
in [Reference Kihara and Montalbán11] uses special features of the Baire space and looks a bit different from our general definition of levels of the Q-IFH. The main result of this subsection shows that these classes for the Baire space coincide. For the reader’s convenience, we cite necessary notions and results from [Reference Kihara and Montalbán11] (see also [Reference Kihara and Selivanov12]).
Any nonempty closed set C in
$\mathcal {N}$
and any Q-partition
$A:C\to Q$
induce a Q-partition
$\hat{A}:\mathcal {N}\to Q$
obtained by composing A with the canonical retraction from
$\mathcal {N}$
onto C (abusing notation, A and
$\hat{A}$
are often identified). Similarly, any
$A:U\to Q$
, where U is a nonempty open set in
$\mathcal {N}$
, may be identified with some
$\hat{A}:\mathcal {N}\to Q$
(see Observations 3.5 and 3.6 in [Reference Kihara and Montalbán11]). We recall (in a slightly different from [Reference Kihara and Montalbán11] notation of §3.1) the definition of classes
$\Sigma _T$
(in fact, we define
$\Sigma _u$
for
$u\in \mathbb {T}_\sigma $
, where
$T=T(u)$
, see Lemma 3.3, cf. Definition 3.7 and its extensions in [Reference Kihara and Montalbán11]).
Definition 4.9.
-
1.
$\Sigma _q=\{\lambda x.q\}$
. -
2.
$\Sigma _{s_\alpha (u)}$
consists of
$A\circ g$
where
$A\in \Sigma _u$
and g is a
$\mathbf {\Sigma }^0_{1+\omega ^\alpha }$
-measurable function on
$\mathcal {N}$
. -
3.
$\Sigma _{F_q(u_0,\ldots )}$
consists of
$A\in Q^{\mathcal {N}}$
such that for some pairwise disjoint nonempty open sets
$U_0,U_1,\ldots $
not exhausting
$\mathcal {N}$
we have:
$A|_V=\lambda v.q$
(where
$V=\mathcal {N}\setminus \bigcup _iU_i$
) and
$A|_{U_i}\in \Sigma _{u_i}$
for all
$i\geq 0$
. -
4.
$\Sigma _{F_\alpha (u_0,\ldots )}$
consists of
$A\in Q^{\mathcal {N}}$
such that for some pairwise disjoint nonempty open sets
$U_1,U_2,\ldots $
not exhausting
$\mathcal {N}$
we have:
$A|_V\in \Sigma _{s_\alpha (u_0)}$
(where
$V=\mathcal {N}\setminus \bigcup _{i\geq 1}U_i$
) and
$A|_{U_i}\in \Sigma _{u_i}$
for all
$i\geq 1$
.
In [Reference Kihara and Montalbán11] the following basic deep fact was established: For any countable ordinal
$\alpha $
, there is a
$\mathbf {\Sigma }^0_{1+\alpha }$
-measurable conciliatory (an important technical notion from [Reference Kihara and Montalbán11]) function
$\mathcal {U}_\alpha \colon \mathcal {N}\to \mathcal {N}$
which is universal; that is, for every
$\mathbf {\Sigma }^0_{1+\alpha }$
-measurable function
$f\colon \mathcal {N}\to \mathcal {N}$
, there is a continuous function
$g\colon \mathcal {N}\to \mathcal {N}$
such that f is equivalent to
$\mathcal {U}_\alpha \circ g$
. It was also shown that every
$\sigma $
-join-irreducible Borel function
$A\colon \mathcal {N}\to Q$
is Wadge equivalent to a conciliatory function. In fact, for any
$u\in \mathbb {T}_{\sigma }$
there is a special
$\Sigma _u$
-complete conciliatory function
$\mu (u)\colon \mathcal {N}\to Q$
defined as follows:
$\mu (q)=\lambda x.q$
;
$\mu (s_\alpha (u))=\mu (u)\circ \mathcal {U}_{\omega ^\alpha }$
;
$\mu (F_q(u_0,\ldots ))=\mu (q)\to (\mu (u_0)\sqcup \cdots )$
;
$\mu (F_\alpha (u_0,\ldots ))=\mu (s_\alpha (u_0))\to (\mu (u_1)\sqcup \cdots )$
.
Theorem 4.10. For any countable bqo Q we have
$\Sigma _u=\mathcal {L}(\mathcal {N},u)$
and
$\widehat {\Sigma }_u=\widehat {\mathcal {L}}(\mathcal {N},u)$
for every
$u\in \mathbb {T}_{\sigma }$
. Thus, in the Baire space the Q-IFH coincides with the Q-Wadge hierarchy.
Proof. It suffices to prove the first equality. Clearly,
$\Sigma _q=\mathcal {L}(\mathcal {N},q)$
for
$q\in Q$
. To prove
$\Sigma _{s_\alpha (u)}=\mathcal {L}(\mathcal {N},s_\alpha (u))$
, note that
$\Sigma _u=\mathcal {L}(\mathcal {N},u)$
by induction and
$\mathcal {L}(\mathcal {N},s_\alpha (u))=\mathcal {L}^{\omega ^\alpha }(\mathcal {N},u)$
by Lemma 3.34(1). Let
$A\circ g\in \Sigma _{s_\alpha (u)}$
where
$A\in \Sigma _u=\mathcal {L}(\mathcal {N},u)$
and g is
$\mathcal {L}^{\omega ^\alpha }(\mathcal {N})$
-measurable. By Lemmas 3.14 and 3.26,
$A\circ g\in \mathcal {L}^{\omega ^\alpha }(\mathcal {N},u)$
, as desired. Conversely, let
$A\in \mathcal {L}^{\omega ^\alpha }(\mathcal {N},u)$
. By the remarks before the theorem,
$\mu (s_\alpha (u))=\mu (u)\circ \mathcal {U}_{\omega ^\alpha }$
is Wadge complete in
$\mathcal {L}^{\omega ^\alpha }(\mathcal {N},u)$
, hence
$A=(\mu (u)\circ \mathcal {U}_{\omega ^\alpha })\circ f$
for some continuous function f on
$\mathcal {N}$
. Then
$A=\mu (u)\circ (\mathcal {U}_{\omega ^\alpha }\circ f)$
,
$\mu (u)\in \mathcal {L}(\mathcal {N},u)$
, and
$\mathcal {U}_{\omega ^\alpha }\circ f$
is
$\mathcal {L}^{\omega ^\alpha }(\mathcal {N})$
-measurable. Thus,
$A\in \Sigma _{s_\alpha (u)}$
.
In proving the equality
$\Sigma _{F_q(u_0,\ldots )}=\mathcal {L}(\mathcal {N},F_q(u_0,\ldots ))$
, by induction we can assume that
$\Sigma _{u_i}=\mathcal {L}(\mathcal {N},u_i)$
for each
$i\geq 0$
. Let
$A\in \Sigma _{F_q(u_0,\ldots )}$
, then for some pairwise disjoint nonempty open sets
$U_0,U_1,\ldots $
not exhausting
$\mathcal {N}$
we have:
$A|_V=\lambda v.q$
(where
$V=\mathcal {N}\setminus \bigcup _iU_i$
) and
$A|_{U_i}\in \Sigma _{u_i}$
for all
$i\geq 0$
. By induction,
$A|_{U_i}\in \mathcal {L}(\mathcal {N},u_i)$
for all
${i\geq 0}$
. By Lemma 3.34(4),
$A\in \mathcal {L}(\mathcal {N},F_q(u_0,\ldots ))$
. The converse inclusion follows from Lemma 3.34(3) and Definition 4.9(3). The case of
$F_\alpha $
-term is considered similarly.⊣
4.5 Infinitary fine hierarchies in quasi-Polish spaces
Here we summarise some properties of the Q-IFH in quasi-Polish spaces. For any quasi-Polish space X we fix a continuous open surjection
$\xi $
from
$\mathcal {N}$
onto X (Proposition 2.2). First we give the characterization of the Wadge hierarchy of Q-partitions announced in Introduction (for
$Q=\bar {2}$
this of course yields a characterization of the Wadge hierarchy of sets).
Theorem 4.11. Let X be a quasi-Polish space, Q a countable bqo, and
$T\in \mathcal {T}_{\omega _1}(Q)$
. Then
$\mathcal {W}(X,T)=\widehat {\mathcal {L}}(X,T)$
.
Proof. By Theorem 4.10 and Proposition 3.11,
$\mathcal {W}(\mathcal {N},T)=\widehat {\Sigma }_T=\widehat {\mathcal {L}}(\mathcal {N},T)$
. By Theorem 4.6, for any
$A:X\to Q$
we have:
$A\in \mathcal {W}(X,T)$
iff
$A\circ \xi \in \widehat {\mathcal {L}}(\mathcal {N},T)$
iff
$A\in \widehat {\mathcal {L}}(X,T)$
.⊣
Next we show that the HK-type theorems hold in any quasi-Polish space, which extends some known results. From Proposition 2.2 we know that X is a quasi-Polish space iff
$X\leq _{co}\mathcal {N}$
. This together with Theorems 4.7 and 4.8 implies the following.
Theorem 4.12. Every quasi-Polish space satisfies the HK-theorem for Q-partitions in any successor level
$1+\alpha +1<\omega _1$
of the Q-IFH, and also the Wadge property for Q-partitions in any limit level
$\lambda <\omega _1$
of the Q-IFH.
Let us summarize which properties of the Wadge hierarchy in the Baire space (see end of §2.4) hold in arbitrary quasi-Polish spaces. Property (1) holds for the hierarchies of sets and of Q-partitions for bqo Q (if Q has antichain of size 3, the property holds in the weakened bqo-form). The noncollapse property (2) does not automatically hold and requires additional investigation in any concrete space. Property (3) fails in most of natural spaces. Property (4) holds in arbitrary quasi-Polish space (note that this property is in fact an HK-type theorem); it would be interesting to investigate it for cb
$_0$
-spaces which are not quasi-Polish. By Proposition 4.3, property (5) holds for many (but not all) levels of the Q-IFH in cb
$_0$
-spaces. Property (6) does not automatically hold and requires additional investigation in any concrete space.
We conclude with an additional open question. In this paper we hopefully found a convincing set-theoretic definition of Q-Wadge hierarchy in quasi-Polish spaces, restricting our attention to Borel Q-partitions. For this the axioms of ZFC suffice. A major open question is to extend the results of this paper to a reasonable class beyond the Borel Q-partitions (perhaps even to all Q-partitions). The Wadge hierarchy for arbitrary subsets of the Baire space is well known [Reference van Wesep36] and requires suitable set-theoretic axioms alternative to ZFC. The definitions of this paper extend straightforwardly (by taking arbitrarily large ordinal
$\gamma $
in the signature
$\sigma (Q,\gamma )$
in §3.1) but beyond the Borel Q-partitions proofs could turn out different from those used in this paper. It is currently not clear which set-theoretic axioms should be used.
Acknowledgement
I am grateful to an anonymous referee for the very careful reading and several useful suggestions which helped to improve presentation. This research was supported by RFBR-JSPS Grant 20-51-50001.
