Non-collapse of the effective Wadge hierarchy

Abstract

We study the recently suggested effective Wadge hierarchy in effective spaces, concentrating on the non-collapse property. Along with hierarchies of sets, we study hierarchies of k-partitions which are interesting on their own. In particular, we establish sufficient conditions for the non-collapse of the effective Wadge hierarchy and apply them to some concrete spaces, including the discrete space of natural numbers, the Baire space, and the Cantor space. While the latter two cases are obtained by easy effectivization of the corresponding topological result by T. Kihara and A. Montalban, the first case needs a different technique and is certainly the main technical result of this paper.

Keywords

Effective space computable quasi-Polish space effective Wadge hierarchy fine hierarchy non-collapse property

1. Introduction

Hierarchies are basic tools for calibrating objects according to their complexity, hence the non-collapse of a natural hierarchy is fundamental for understanding the corresponding notion of complexity. A lot of papers investigate the non-collapse property in different contexts, see e.g. [29] for a survey of hierarchies relevant to those studied in this paper.

The Wadge hierarchy (WH), which is fundamental for descriptive set theory (DST), was developed for the Baire space $N$ , first for the case of sets [39], then for k-partitions [33], and recently for the Q-valued Borel functions on $N$ , for any better quasiorder Q [17]. A convincing extension of the Q-Wadge hierarchy to arbitrary topological spaces was developed in [26] (see also [23,32] where some relevant ideas were suggested independently). In [35] we introduced and studied the effective Wadge hierarchy (EWH) in effective spaces as an instantiation of the fine hierarchy (FH) [29]. Here we concentrate on the non-collapse property of the EWH. As in [35], along with the EWH of sets we consider the EWH of k-partitions for $k > 2$ (sets correspond to 2-partitions).

The non-collapse of EWH is highly non-trivial already for the discrete space $N$ of natural numbers. In fact, for the case of sets it follows from the results on the non-collapse of the FH of arithmetical sets introduced in [27]; m-degrees of complete sets in levels of this hierarchy are among the “natural m-degrees” studied recently in [16]. The case of k-partitions with $2 < k ⩽ ω$ was also considered in [27] where many useful technical facts were obtained, but the non-collapse property for $k > 2$ was not established and even formulated because at that time we did not have a convincing notion of a hierarchy of k-partitions (introduced only in [30,32]). In the present paper, we prove some additional facts which, together with the results in [27], imply the non-collapse of EWH of k-partitions in $N$ . We show that all levels of this hierarchy have complete k-partitions which are also natural in the sense of [16].

We also prove the non-collapse of EWH in $N$ , providing an effective version for the fundamental result in [17]; modulo the result in [17], our proofs for $N$ are easy. Along with the spaces $N$ and $N$ , which are central in computability theory, we discuss the non-collapse of EWH for other spaces which became popular in computable analysis and effective DST. The preservation property of the EWH established in [26,35] implies that the non-collapse property is inherited by the (effective) continuous open surjections which suggests a method for proving non-collapse. Unfortunately, this method is less general than the dual inheritance method for the Hausdorff–Kuratowski property [26,35] which completely reduces this property in (computable) quasi-Polish spaces to that in the Baire space. Nevertheless, the method suggested here provides some insight which enables e.g. to see that the non-collapse of (effective) WH is hard to prove in every (computable) quasi-Polish space where it holds.

The FH (as also most of the objects related to the WH) has inherent combinatorial complexity resulting in rather technical notions and involved proofs. To make the paper more readable, we cite several known results and recall all principal definitions, often with making new observations and giving additional details. These efforts make this paper reasonably self-contained. With papers [17,27,30,35] at hand, the reader will certainly have everything to understand the remaining technical details from scratch.

In Section 2, along with routine preliminaries, we give a rather detailed treatment of the so called iterated h-preorders which serve as the notation system for the EWH of k-partitions. In Section 3 we recall necessary definitions and facts about the EWH. In Section 4 we define some versions of the non-collapse property and relate them to the preservation property. While for hierarchies of sets the non-collapse property is defined in the obvious standard way, for hierarchies of k-partitions with $k > 2$ the situation is more subtle since we meet some variants of non-collapse which are not visible in the case $k = 2$ . We carefully define these versions and prove relations between them, as well as their preservation properties. Hopefully, this provides tools which could be of use for investigating the non-collapse property in concrete spaces.

In Section 5 we prove the main technical results of this paper, including the non-collapse of the EWH in $N$ . In particular, these results complete the previous partial results from [27]. The results are purely computability theoretic and do not use topological notions at all. This provides for the readers interested in computability but not in topology the option to escape the topological part of the paper, by reading only Sections 2, 3, 4 (restricted to the FH of arithmetical k-partitions), and 5.

In Section 6 we establish the non-collapse of the EWH of k-partitions in the Baire space, the domain of finite and infinite strings, and some related spaces. Although proofs in this section are short (due to the possibility to refer to some notions and proofs in [17]), the formulations are new and hopefully interesting because they provide (as well as the results in Section 5) effective versions for the results in [17]. We conclude in Section 7 with a short discussion of possible future work.

2. Preliminaries

In this section we recall some notation, notions and facts used throughout the paper. 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, $\overline{C} = X ∖ C$ is the complement of $C \subseteq X$ in X. The domain and range of a function f are denoted respectively by $dom (f)$ and $r n g (f)$ .

2.1. Effective hierarchies

Here we briefly recall some notation and terminology about effective hierarchies in effective spaces. More details may be found e.g. in [31].

All (topological) spaces in this paper are countably based $T_{0}$ (cb₀-spaces, for short). An effective cb₀-space is a pair $(X, β)$ where X is a cb₀-space, and $β : ω \to P (X)$ is a numbering of a base in X such that there is a uniformly c.e. sequence ${A_{i j}}$ of c.e. sets with $β (i) \cap β (j) = ⋃ β (A_{i j})$ where $β (A_{i j})$ is the image of $A_{i j}$ under β. We simplify $(X, β)$ to X if β is clear from the context. The effectively open sets in X are the sets $⋃ β (W)$ , for some c.e. set $W \subseteq N$ . The standard numbering ${W_{n}}$ of c.e. sets [24] induces a numbering of the effectively open sets. The notion of effective cb₀-space allows to define e.g. computable and effectively open functions between such spaces [31,40].

Among effective cb₀-spaces are: the discrete space $N$ of natural numbers, the Euclidean spaces $R^{n}$ , the Scott domain $P ω$ (see [1] for information about domains), the Baire space $N = N^{N}$ , the Baire domain $ω^{⩽ ω}$ of finite and infinite strings over ω with the Scott topology, the Cantor space $2^{ω}$ of binary infinite strings, the Cantor domains $n^{⩽ ω}$ , $2 ⩽ n < ω$ , of finite and infinite strings over ${0, \dots, n - 1}$ with the Scott topology; all these spaces come with natural numberings of bases. The space $N$ is trivial topologically but very interesting for computability theory.

Quasi–Polish spaces (introduced in [7]) are important for DST and have several characterisations. Effectivizing one of them we obtain the following notion identified implicitly in [31] and explicitly in [8,14]: a computable quasi-Polish space is an effective cb₀-space $(X, β)$ such that there exists a computable effectively open surjection from $N$ onto $(X, β)$ . Most spaces of interest for computable analysis and effective DST, in particular the aforementioned ones, are computable quasi-Polish.

Effective hierarchies of sets were studied by many authors, see e.g. [3–5,11,21,31]. We use standard $Σ, Π, Δ$ -notation, with suitable indices, for notation of levels of hierarchies of sets. Let ${Σ_{1 + n}^{0} (X)}_{n < ω}$ be the effective Borel hierarchy (we consider in this paper mostly finite levels), and ${Σ_{1 + n}^{- 1, m} (X)}_{n}$ (with $Σ^{- 1, 1}$ usually simplified to $Σ^{- 1}$ ) be the effective Hausdorff difference hierarchy over $Σ_{m}^{0} (X)$ in arbitrary effective cb₀-space X. Note that ${Σ_{1 + n}^{0} (N)}_{n < ω}$ coincides with the arithmetic hierarchy. We do not repeat standard definitions but mention that the effective hierarchies come with standard numberings of all levels, so we can speak e.g. about uniform sequences of sets in a given level. We use definitions based on set operations (see e.g. [31]); there is also an equivalent approach based on the Borel codes [15,18]. E.g., $Σ_{1}^{0} (X)$ is the class of effectively open sets in X, $Σ_{2}^{- 1} (X)$ is the class of differences of $Σ_{1}^{0} (X)$ -sets, and $Σ_{2}^{0} (X)$ is the class of effective countable unions of $Σ_{2}^{- 1} (X)$ -sets.

Levels of effective hierarchies are denoted in the same manner as levels of the corresponding classical hierarchies, using the lightface letters $Σ, Π, Δ$ instead of the boldface $Σ, Π, Δ$ used for the classical hierarchies [15,21]. The classical hierarchies are discussed below in parallel with the effective ones, since the tools of investigation are similar.

In fact, any lightface notion in this paper will have a classical boldface counterpart, as is standard in DST. In particular, recall that a function $f : X \to Y$ is $Σ_{2}^{0}$ -measurable if $f^{- 1} (B) \in Σ_{2}^{0}$ for each $B \in Σ_{1}^{0} (Y)$ . The corresponding lightface version is as follows: A function $f : X \to Y$ between effective cb₀-spaces is $Σ_{2}^{0}$ -measurable if $f^{- 1} (B) \in Σ_{2}^{0} (X)$ for each $B \in Σ_{1}^{0} (Y)$ , effectively on the indices. Every $Σ_{2}^{0}$ -measurable function is of course $Σ_{2}^{0}$ -measurable.

The Wadge reducibility on subsets of a space X is the many-one reducibility by continuous functions on X; it is denoted by $⩽_{W}$ (or, more precisely, by $⩽_{W}^{X}$ ). The effective Wadge reducibility on subsets of an effective cb₀-space X is the many-one reducibility by computable functions on X; it is denoted by $⩽_{e W}$ (or, more precisely, by $⩽_{e W}^{X}$ ). The effective Wadge reducibility on subsets of $N$ coincides with the usual m-reducibility [24]. The (effective) Wadge reducibility is extended to k-partitions $A, B$ in a straightforward way: a function f on X reduces A to B, if $A = B \circ f$ .

2.2. Preorders and semilattices

We assume the reader to be familiar with the standard terminology and notation related to partially ordered sets (posets) and preorders. Recall that a semilattice is a structure $(S; ⊔)$ with binary operation ⊔ such that $(x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)$ , $x ⊔ y = y ⊔ x$ and $x ⊔ x = x$ , for all $x, y, z \in S$ . By ⩽ we denote the induced partial order on S: $x ⩽ y$ iff $x ⊔ y = y$ . The operation ⊔ can be recovered from ⩽ since $x ⊔ y$ is the supremum of $x, y$ w.r.t. ⩽. The semilattice is distributive if $x ⩽ y ⊔ z$ implies that $x = y^{'} ⊔ z^{'}$ for some $y^{'} ⩽ y$ and $z^{'} ⩽ z$ . All semilattices considered in this paper are distributive (sometimes after adjoining a new smallest element denoted by ⊥). A semilattice $(S; ⊔, ⩽)$ is a d-semilattice if it becomes distributive after adjoining to S a new smallest element ⊥; below we usually abbreviate $S \cup {⊥}$ to $S_{⊥}$ .

An element x of the semilattice S is join-reducible if it can be represented as the supremum of two elements strictly below x. Element x is join-irreducible if it is not join-reducible. We denote by $I (S; ⊔, ⩽)$ the set of non-smallest join-irreducible elements of a semilattice $(S; ⊔, ⩽)$ . If S is distributive then x is join-irreducible iff $x ⩽ y ⊔ z$ implies that $x ⩽ y$ or $x ⩽ z$ . By a decomposition of a non-smallest element x we mean a representation $x = x_{0} ⊔ \dots ⊔ x_{n}$ where the components $x_{i}$ are join-irreducible and pairwise incomparable (a smallest element may be considered as the supremum of the empty family of join-irreducible elements). Such a decomposition is canonical if it is unique up to a permutation of the components. Clearly, if S is a well founded semilattice then any non-smallest element $x \in S$ has a decomposition, and if S is distributive then x has a canonical decomposition.

To simplify notation, we often apply the terminology about posets to preorders meaning the corresponding quotient-poset. Similarly, the term “semilattice” will also be applied to structures $(S; ⊔, ⩽)$ where ⩽ is a preorder on S such the quotient-structure under the induced equivalence relation ≡ is a “real” semilattice with the partial order induced by ⩽ (thus, we avoid precise but more complicated terms like “pre-semilattice”). We call preorders (or pre-semilattices) $P, Q$ equivalent (in symbols, $P ≃ Q$ ) if their quotient-posets (resp., quotient-semilattices) are isomorphic. For subsets $A, B \subseteq S$ of a preorder $(S; ⩽)$ we write $A \equiv B$ if every element of A is equivalent to some element of B and vice versa. This terminology is especially convenient in the situation (which is typical below) when one operation ⊔ on S induces the pre-semilattice structure for several preorders on S.

We associate with any poset Q the preorder $(Q^{*}; ⩽^{*})$ where $Q^{*}$ is the set of non-empty finite subsets of Q, and $S ⩽^{*} R$ iff $\forall s \in S \exists r \in R (s ⩽ r)$ . Let $Q^{⊔}$ be the quotient-poset of $(Q^{*}; ⩽^{*})$ and ⊔ be the operation of supremum in S induced by the operation of union in $Q^{*}$ . Then $Q^{⊔}$ is a d-semilattice the join-irreducible elements of which coincide with the elements induced by the singleton sets in $Q^{*}$ (the new smallest element ⊥ corresponds to the empty subset of Q); thus, $(I (Q^{⊔}); ⩽^{*}) ≃ Q$ . Any element of $Q_{⊥}^{⊔}$ has a canonical decomposition. If Q is well founded then so is also $Q^{⊔}$ . The construction $Q \mapsto Q^{⊔}$ is a functor from the category of preorders to the category of semilattices (see [34] for additional details). We will use the following easy fact.

Proposition 1.
Let $f : Q \to I (S)$ be a monotone function from a poset Q to the set of join-irreducible elements of a semilattice S. Then there is a unique semilattice homomorphism $f^{⊔} : Q^{⊔} \to S$ extending f. If f is an embedding and S is distributive then $f^{⊔}$ is an embedding.

2.3. Labeled trees and forests

In this section we recall a notation system for levels of the FH of k-partitions introduced in [30], with some additions and new facts.

Let $ω^{*}$ be the set of finite strings of natural numbers including the empty string ε. By a tree we mean a nonempty initial segment of $(ω^{*}; ⊑)$ where ⊑ is the prefix relation. A tree T is normal if $τ (i + 1) \in T$ implies $τ i \in T$ . The rank of a finite tree is the length of a longest chain in the tree.

It is often useful to consider “abstract” trees (i.e., posets with a smallest element, in which the predecessors of any element are linearly ordered) along with the “concrete” trees defined above. Obviously, any finite abstract tree is isomorphic to a normal tree above. In some definitions below we implicitly use this obvious relation between “abstract” and “concrete” trees. This slightly abuses notation but simplifies intuitive understanding of the definitions.

For any finite tree T and any $τ \in T$ , define the tree $T (τ) = {σ \in ω^{*} ∣ τ \cdot σ \in T}$ where · is the concatenation of strings (often omitted). Then any non-singleton finite tree T is determined by the singleton tree ${ε}$ and the finite trees $T (i)$ , $i \in T$ of lesser tree ranks than T, so $T = {ε} \cup ⋃_{i \in T} i \cdot T (i)$ . We will use this representation in the proofs by induction on ranks. By a forest we mean an initial segment of $(ω^{*} ∖ {ε}; ⊑)$ . Note that there is a unique empty forest, and for any forest F there is a unique tree T with $F = T ∖ {ε}$ . Any non-empty forest F is isomorphic to the disjoint union of trees $F (i)$ , $i \in ω \cap F$ .

Next we recall notation related to iterated labeled forests from [30]. Let $(Q; ⩽)$ be a preorder; abusing notation we often denote it just by Q. A Q-tree is a pair $(T, t)$ consisting of a finite normal tree $T \subseteq ω^{*}$ , and a labeling $t : T \to Q$ . Let $T (Q)$ (resp. $F (Q)$ ) denote the set of all finite Q-trees (resp. Q-forests). The h-preorder $⩽_{h}$ on $T (Q)$ is defined as follows: $(T, t) ⩽_{h} (V, v)$ , if there is a monotone function $f : (T; ⊑) \to (V; ⊑)$ satisfying $\forall τ \in T (t (τ) ⩽ v (f (τ)))$ . For any $q \in Q$ , let $s (q) = ({ε}, q)$ be the singleton tree labeled by q. Then $q ⩽_{Q} r$ iff $s (q) ⩽_{h} s (r)$ . Note that $(T, t) ⩽_{h} s (r)$ iff $t (τ) ⩽_{Q} r$ for all $τ \in T$ , $s (q) ⩽_{h} (V, v)$ iff $q ⩽_{Q} v (σ)$ for some $σ \in V$ , and, if both $T, V$ are non-singleton then $T ⩽_{h} V$ iff ( $t (ε) ⩽_{Q} v (ε)$ and $T (i) ⩽_{h} V$ for all $i \in ω \cap T$ ) or ( $t (ε) ≰_{Q} v (ε)$ and $T ⩽_{h} V (j)$ for some $j \in ω \cap T$ ). This characterises the relation $⩽_{h}$ by induction on the tree rank. The construction $Q \mapsto T (Q)$ may be considered as an endofunctor on the category of preorders (see [34] for details); then s becomes a natural transformation from the identity endofunctor to $T$ .

By Section 2.2, s induces the semilattice homomorphism $s^{⊔}$ from $Q^{⊔}$ into $T {(Q)}^{⊔}$ (note that the latter semilattice is naturally isomorphic to $F (Q)$ ); we often simplify $s^{⊔}$ to s. The elements of $T {(Q)}^{⊔}$ are naturally identified with the finite Q-labeled forests, and $I (F (Q); ⊔, ⩽_{h}) \equiv_{h} T (Q)$ . Along with the operation ⊔, there is a natural binary operation · on $F (Q)$ defined as follows: $F \cdot G$ is the labeled forest obtained from F by putting a copy of G above every leaf of F. Clearly, $F ⊔ G ⩽_{h} F \cdot G$ and $(F \cdot G) \cdot H = F \cdot (G \cdot H)$ . For any $(F, t) \in T {(Q)}^{⊔}$ , let $r (F) = ⨆ {t (τ) ∣ τ \in F}$ . Then $r : F (Q) \to Q^{⊔}$ is a semilattice homomorphism such that $r (s (x)) \equiv x$ for every $x \in Q$ . The relation ⩽ on $Q^{⊔}$ induces the relation $⩽^{'}$ on $F (Q)$ as follows: $F ⩽^{'} G$ iff $r (F) ⩽ r (G)$ . Clearly, r induces an equivalence of semilattices $(F (Q); ⊔, ⩽^{'})$ and $Q^{⊔}$ , $I (F (Q); ⊔, ⩽^{'}) \equiv^{'} s (Q)$ , and the relations $⩽, ⩽^{'}$ coincide on $s (Q)$ .

By a minimal Q-forest we mean a Q-forest not h-equivalent to a Q-forest of lesser cardinality. The next characterization of the minimal Q-forests was obtained in [30], Proposition 8.3.

Proposition 2.

Any singleton Q-forest is minimal.

A non-singleton Q-tree $(T, t)$ is minimal iff the Q-forest $T ∖ {ε}$ is minimal, $\forall i \in ω \cap T (t (i) ≰ t (ε))$ , and if $ω \cap T = {0}$ then $t (0), t (ε)$ are incomparable.

A Q-forest having at least two Q-trees is minimal iff all its Q-trees are minimal and pairwise incomparable under $⩽_{h}$ .

Minimal forests are often useful to simplify proofs. E.g., if F is minimal and consists of trees $F_{0}, \dots, F_{n}$ then $F \equiv_{h} F_{0} ⊔ \dots ⊔ F_{n}$ is automatically a canonical decomposition. It is easy to see that two minimal h-equivalent Q-forests are isomorphic, and that Proposition 2 induces a unary function min on $F (Q)$ such that $min (F)$ is a minimal Q-forest equivalent to F (computing of such $min (F)$ may be called minimization of F).

The function min may be “computed” by induction on $| F |$ as follows: if $| F | = 1$ , set $min (F) = F$ ; if F consists of trees $T_{0}, \dots, T_{n}$ , $n > 0$ , then delete all trees which are h-below some other tree, and minimize (by induction) all the remaining trees; if F is a tree and $| F | > 1$ , then compute $F_{1} = t (ε) \cdot min (F ∖ {ε})$ , delete from the resulting tree $F_{1}$ all nodes $τ \neq ε$ with $\forall σ (ε ⊏ σ ⊑ τ \to t (σ) ⩽ t (ε))$ to obtain the tree $F_{2}$ , compute $F_{3} = t (ε) \cdot min (F_{2} ∖ {ε})$ , and delete the root in $F_{3}$ whenever $ω \cap F_{3} = {0}$ and $t (ε) ⩽ t (0)$ .

Note that the labels of $min (F)$ are among the labels of F, $min (F)$ is a tree whenever F is a tree, and F is join-irreducible iff $min (F)$ is a tree. If the structure $(Q; ⩽)$ is computably presentable then the previous paragraph becomes a real algorithm for computing $min (F)$ from a given F.

Define the sequence ${T_{m} (Q)}_{m < ω}$ of preorders by induction on m as follows: $T_{0} (Q) = Q$ and $T_{m + 1} (Q) = T (T_{m} (Q))$ ; the preorder on $T_{m} (Q)$ is denoted by $⩽_{h}$ (for $m = 0$ we identify $⩽_{h}$ with $⩽_{Q}$ ). For any $m < ω$ , we have the preorder embedding $s : T_{m} (Q) \to T_{m + 1} (Q)$ which is sometimes convenient to denote $s_{m}$ . Setting $F_{m} (Q) = T_{m} {(Q)}^{⊔}$ , we obtain sequences ${F_{m} (Q)}$ of semilattices, and $s : F_{m} (Q) \to F_{m + 1} (Q)$ , $r : F_{m + 1} (Q) \to F_{m} (Q)$ of homomorphisms such that $r (s (x)) \equiv_{h} x$ for every $x \in F_{m} (Q)$ . For all $n ⩽ m$ , we define a preorder $⩽^{n}$ on $F_{m} (Q)$ by induction: $⩽^{0}$ is $⩽_{h}$ and, for $n < m$ , $F ⩽^{n + 1} G$ iff $r (F) ⩽^{n} r (G)$ . For all $p ⩽ m$ , we define a binary operation $\cdot^{p}$ on $F_{m + 1} (Q)$ by induction: $F \cdot^{0} G = F \cdot G$ and, for $p < m$ , $F \cdot^{p + 1} G = s (r (F) \cdot^{p} r (G))$ .

We collect some properties of the introduced objects in the following proposition where $I (F_{m} (Q); ⊔, ⩽^{n})$ is abbreviated to $I_{n} (F_{m} (Q))$ and $s^{n}$ is the n-th iteration of s, i.e. $s^{0}$ is the identity and $s^{n + 1} = s \circ s^{n}$ .
Proposition 3.

For all m and $n ⩽ m$ we have: $(F_{m} (Q); ⊔, ⩽^{n})$ is a d-semilattice, $I_{n} (F_{m} (Q)) \equiv^{0} s^{n} (T_{m - n} (Q))$ , and the relations $⩽^{0}, \dots, ⩽^{n}$ coincide on $s^{n} (T_{m - n} (Q))$ .

For all $p ⩽ m$ and $F, G, H \in F_{m + 1} (Q)$ we have: $s (r (F \cdot^{0} G)) \equiv^{0} F ⊔ G$ , $s (r (F \cdot^{p + 1} G)) \equiv^{0} F \cdot^{p} G$ for $p < m$ , and $(F \cdot^{p} G) \cdot^{p} H \equiv^{0} F \cdot^{p} (G \cdot^{p} H)$ .

Proof.
All assertions follow by induction from the corresponding definitions and facts above, so we consider only the associativity of $\cdot^{p}$ , as an example. For $p = 0$ the assertion is clear, so we assume it for $\cdot^{p}$ , $p < m$ , and check it for $\cdot^{p + 1}$ : $\begin{array}{l} (F \cdot^{p + 1} G) \cdot^{p + 1} H & = s (r (F) \cdot^{p} r (G)) \cdot^{p + 1} H = s (r s (r (F) \cdot^{p} r (G)) \cdot^{p} r (H)) \\ \equiv^{0} s ((r (F) \cdot^{p} r (G)) \cdot^{p} r (H)) \equiv^{0} s (r (F) \cdot^{p} (r (G) \cdot^{p} r (H))) \\ \equiv^{0} s (r (F) \cdot^{p} r s (r (G) \cdot^{p} r (H))) \equiv^{0} s (r (F) \cdot^{p} r (G \cdot^{p + 1} H)) = F \cdot^{p + 1} (G \cdot^{p + 1} H) . \end{array}$ □

The sets $T_{m} (Q)$ , $m ⩾ 0$ , are pairwise disjoint but, identifying $q \in Q$ with the corresponding singleton tree $s (q)$ , we may think that $T_{0} (Q) \subseteq T_{1} (Q)$ and, moreover, $T_{0} (Q) \subseteq T_{1} (Q) \subseteq \dots \subseteq T_{ω} (Q)$ and $T_{ω} (Q)$ has an induced preorder also denoted by $⩽_{h}$ . In a similar way we may think that $F_{ω} (Q)$ is a smallest structure containing any $F_{m} (Q)$ , $m < ω$ , as a substructure. This informal construction from some of my previous papers can be made precise (on the cost of additional technical details) by using the known fact that the category of preorders has arbitrary colimits. Since we need the precise construction in Section 5, we briefly recall some details of this construction.

Namely, we consider $T_{ω} (Q)$ as the colimit of the sequence of morphisms $g_{m} : T_{m} (Q) \to T_{m + 1} (Q)$ defined by induction as follows: $g_{0} = s$ , and $g_{m + 1} (T, t) = (T, g_{m} \circ t)$ . For any $T \in T_{ω} (Q)$ , let $g (T) = g_{m} (T)$ where m is the unique integer with $T \in T_{m} (Q)$ . Then g is a function on $T_{ω} (Q) = ⋃_{m} T_{m} (Q)$ (where the summands are pairwise disjoint). Let ⩽ be the smallest preorder on $T_{ω} (Q)$ such that $g (T) \equiv T$ for every $T \in T_{ω} (Q)$ , and $T ⩽ V$ for all $T, V \in T_{m} (Q)$ with $T ⩽_{h} V$ . Then the inclusions $T_{0} (Q) \subseteq T_{1} (Q) \subseteq \dots \subseteq T_{ω} (Q)$ hold up to ≡ (intuitively, ⩽ coincides with $⩽_{h}$ above). In checking this one has to use functions $g_{m, n}$ , $m ⩽ n < ω$ , defined by $g_{m, n} = g_{n - 1} \circ \dots \circ g_{m}$ (for $m = n$ , $g_{m, m}$ is the identity function on $T_{m} (Q)$ ); thus, $g_{m, n}$ is an embedding of $(T_{m} (Q); ⩽_{h})$ into $(T_{n} (Q); ⩽_{h})$ .

A similar construction in the category of (pre-)semilattices yields the structure $F_{ω} (Q)$ as the colimit of semilattice embeddings $g_{m, n}^{⊔} : (F_{m} (Q); ⊔, ⩽_{h}) \to (F_{n} (Q); ⊔, ⩽_{h})$ . The supremum operation ⊔ on $F_{ω} (Q)$ is defined by $F ⊔ G = g_{m, p} (F) ⊔_{p} g_{n, p} (G)$ where $p = max {m, n}$ , $F \in F_{m} (Q)$ , and $G \in F_{n} (Q)$ . One easily checks that $F ⩽ F^{'}$ and $G ⩽ G^{'}$ imply $F ⊔ F^{'} ⩽ G ⊔ G^{'}$ , hence $(F_{ω} (Q); ⊔, ⩽)$ is a d-semilattice equivalent to $T_{ω} {(Q)}^{⊔}$ that contains $(F_{m} (Q); ⊔, ⩽_{h})$ , $m < ω$ , as a substructure and satisfies $I (F_{ω} (Q); ⊔, ⩽) \equiv T_{ω} (Q)$ .

The functions and relations defined before Proposition 3 on $T_{m} (Q)$ and $F_{m} (Q)$ , $m < ω$ , are extended to $T_{ω} (Q)$ and $F_{ω} (Q)$ in the natural way. For any $T \in T_{ω} (Q)$ , let $s (T) = s_{m} (T)$ where m is the unique number with $T \in T_{m} (Q)$ . Then s is a unary function on $T_{ω} (Q)$ that is monotone w.r.t. ⩽ (because $g (s (T)) \equiv s (g (T))$ ) and extends all $s_{m}$ . It has the following properties: $s (q) \equiv q$ for $q \in Q$ , $T < s (T)$ for every $T \in T_{ω} (Q)$ with $\forall q \in Q (T ≢ q)$ , and $T ⩽ V$ iff $s (T) ⩽ s (V)$ for $T, V \in T_{ω} (Q)$ . The function s is extended to the semilattice embedding $s^{⊔} : F_{ω} (Q) \to F_{ω} (Q)$ which for simplicity is also denoted by s. The binary operation · on $F_{ω} (Q)$ is defined by $F \cdot G = g_{m, p} (F) \cdot_{p} g_{n, p} (G)$ where $p = max {m, n}$ , $F \in F_{m} (Q)$ , and $G \in F_{n} (Q)$ . One easily checks that $F ⩽ F^{'}$ and $G ⩽ G^{'}$ imply $F \cdot F^{'} ⩽ G \cdot G^{'}$ , $F ⊔ G ⩽ F \cdot G$ , and $(F \cdot G) \cdot H \equiv F \cdot (G \cdot H)$ .

For any $F \in F_{m} (Q)$ , let $r (F) = r_{m} (F)$ for $m > 0$ and $r (F) = F$ otherwise. Then r is a unary function on $F_{ω} (Q)$ that is monotone w.r.t. ⩽ (because $g (r (T)) \equiv r (g (T))$ ) and extends all $r_{m}$ . Furthermore, it is a semilattice epimorphism from $(F_{ω} (Q); ⊔, ⩽)$ onto itself such that $r (s (F)) \equiv F$ for every $F \in F_{ω} (Q)$ . Using this function r, we can define, for any $n < ω$ , relations $⩽^{n}$ and operations $\cdot^{n}$ on $F_{ω} (Q)$ by induction as follows: $⩽^{0}$ is $⩽_{h}$ , $F ⩽^{n + 1} G$ iff $r (F) ⩽^{n} r (G)$ , $F \cdot^{0} G = F \cdot G$ , and $F \cdot^{n + 1} G = s (r (F) \cdot^{n} r (G))$ . The next proposition follows from Proposition 3.
Proposition 4.

For any $n < ω$ we have: $(F_{ω} (Q); ⊔, ⩽^{n})$ is a d-semilattice, and the relations $⩽^{0}, \dots, ⩽^{n}$ coincide on $s^{n} (T_{ω} (Q)) \equiv^{0} I (F_{ω} (Q); ⊔, ⩽^{n})$ .

For any $p < ω$ and $F, G, H \in F_{ω} (Q)$ we have: $r (F \cdot^{0} G) \equiv^{0} F ⊔ G$ , $r (F \cdot^{p + 1} G) \equiv^{0} F \cdot^{p} G$ , and $(F \cdot^{p} G) \cdot^{p} H \equiv^{0} F \cdot^{p} (G \cdot^{p} H)$ .

The preorder Q is a well quasiorder (WQO) if it has neither infinite descending chains nor infinite antichains. A famous Kruskal’s theorem implies that if Q is WQO then $(T_{Q}; ⩽_{h})$ is WQO. It follows that any preorder $T_{m} (Q)$ , $m < ω$ , is WQO. It can be shown that the colimit preorder $(T_{ω} (Q); ⩽)$ (hence also $(T_{ω} (Q); ⩽^{n})$ for every $n < ω$ ) is a WQO. The preorders $(F_{ω} (Q); ⩽^{n})$ , $n < ω$ , are also WQOs.

Below we will mainly deal with the particular case $Q = \bar{k}$ of antichain of size $2 ⩽ k ⩽ ω$ (thus, $\bar{ω}$ is the poset ω all of whose elements are pairwise incomparable). In this case $T_{m} (\bar{k}) ⊑ T_{m + 1} (\bar{k})$ (i.e. the quotient-poset of $T_{m} (\bar{k})$ is an initial segment of the quotient-poset of $T_{m + 1} (\bar{k})$ ). Note that $T_{ω} (\bar{k})$ is WQO for $k < ω$ , $T_{ω} (\bar{ω})$ is well founded but not WQO, and $T_{ω} (\bar{2}) ⊑ T_{ω} (\bar{3}) ⊑ \dots ⊑ T_{ω} (\bar{ω}) = ⋃ {T_{ω} (\bar{k}) ∣ 2 ⩽ k ⩽ ω}$ . For $k = 2$ , the quotient-poset of $(T_{ω} (\bar{2}); ⩽_{h})$ has order type $\bar{2} \cdot ε_{0}$ (see Proposition 8.28 in [30]).

Initial segments of $(F_{1} (\bar{k}); ⩽_{h})$ for $k = 2, 3$ are depicted below, see Fig. 1 and Fig. 2.1
¹
I thank Anton Zhukov for the help with making the pictures.

Figure 1.
An initial segment of $(F_{1} (\bar{2}); ⩽_{h})$ .

Note that while $F_{1} (\bar{2})$ is semi-well-ordered with rank ω, $F_{1} (\bar{k})$ for $k > 2$ is a wqo of rank ω having antichains of arbitrary finite size. The whole structure $F_{ω} (\bar{2})$ is also semi-well-ordered but with larger rank $ε_{0}$ (see Proposition 8.28 in [30]). This structure is isomorphic to the FH of arithmetical sets in [27,28] mentioned in the Introduction. The triangle levels (induced by trees) correspond to the “non-self-dual” Σ- and Π-levels of this hierarchy. More precisely, the Σ-levels (resp. Π-levels) correspond to (hereditary) 0-rooted (resp., 1-rooted) trees. According to Fig. 2, the preorder $F_{1} (\bar{k})$ for $k > 2$ is much more complicated than for $k = 2$ . Nevertheless, the (generalised) non-self-dual levels of the corresponding FHs of k-partitions will again correspond to trees (depicted as triangles).

Figure 2.
An initial segment of $(F_{1} (\bar{3}); ⩽_{h})$ .

We conclude this subsection by defining minimal iterated k-forests $F \in F_{ω} (\bar{k})$ . The definition is by induction on the unique m with $F \in F_{m} (\bar{k})$ . For $m = 0$ , F is minimal, if among its “trees” (which are of the form i, $i < k$ ) there are no repetitions. For $m > 0$ , F is minimal, if it is a minimal $F_{m - 1} (\bar{k})$ -forest in the sense of Proposition 2, and all labels of F are minimal iterated k-forests. As for the Q-forests, there is again a unary function min on $F_{ω} (\bar{k})$ which minimizes iterated k-forests. It is computed in the obvious way: For $m = 0$ , $min (F)$ is obtained from F by deleting repetitions of “trees”; for $m > 0$ , $min (F)$ is obtained from F by minimizing F as a $F_{m - 1} (\bar{k})$ -forest, and then by minimizing all labels of the obtained forest.
3. Effective Wadge hierarchy

We warn the reader that our definition of EWH (taken from [26]) below uses set operations instead of the Wadge reducibility the reader could expect to see, having in mind the definition from [39]. The Wadge reducibility (and especially the effective Wadge reducibility) leads to complex degree structures in non-zero-dimensional spaces which hide the hierarchy (see [26,35] for more detailed discussions), so it cannot be used to define the (effective) WH in a broad enough context. The set-theoretic definition of the FH of sets (which coincides with the EWH in $N$ , as defined below) was first introduced in [28] and then extensively studied in different contexts (see [29] for a partial survey). The extension of the FH to k-partitions was first introduced in [30]. The term “EWH” is justified by the fact that this hierarchy is a finitary effective case of the Wadge hierarchy in arbitrary spaces suggested in [35].

The complexity of the Wadge (and Weihrauch) degree was the reason why a coarser and more useful definition of Weihrauch reducibility (and of Wadge reducibility) makes essential use of admissible representations in [6,12], as well as in our approach [26,35] to (effective) Wadge hierarchy.

Since the EWH is just a special case of the FH, we first recall in this section some information about the latter from [30,35], and then specialize it to obtain the EWH.

Recall that a class $C \subseteq P (X)$ has the reduction property if for any $C_{0}, C_{1} \in C$ there are disjoint $R_{0}, R_{1} \in C$ such that $R_{0} \subseteq C_{0}, R_{1} \subseteq C_{1}$ , and $R_{0} \cup R_{1} = C_{0} \cup C_{1}$ . Note that if $C \subseteq P (X)$ has the reduction property and is closed under finite unions and intersections then for any finite sequence $C_{0}, \dots, C_{n} \in C$ there are pairwise disjoint $R_{0} \dots, R_{n} \in C$ such that $R_{i} \subseteq C_{i}$ for every $i ⩽ n$ , and $R_{0} \cup \dots \cup R_{n} = C_{0} \cup \dots \cup C_{n}$ ; we call such $(R_{0} \dots, R_{n})$ a reduct of $(C_{0}, \dots, C_{n})$ .

By a base in a set X we mean a sequence $L (X) = {L_{n}}_{n < ω}$ of subsets of $P (X)$ such that any $L_{n}$ is closed under union and intersection, contains $\emptyset, X$ , and $A \in L_{n}$ implies that $A, X ∖ A \in L_{n + 1}$ . The base $L (X)$ is reducible if every of its levels $L_{n}$ has the reduction property.

With any base $L (X)$ we associate some other bases as follows. For any $m < ω$ , let $L^{m} (X) = {L_{m + n} (X)}_{n}$ ; we call this base m-shift of $L (X)$ . For any $U \in L_{0}$ , let $L (U) = {L_{n} (U)}_{n < ω}$ where $L_{n} (U) = {U \cap S ∣ S \in L_{n} (X)}$ ; we call this base in U the U-restriction of $L (X)$ .

We define the FH not only of subsets of X but also of k-partitions $A : X \to \bar{k}$ , $1 < k < ω$ . Note that 2-partitions of X are essentially subsets of X. For any finite tree $T \subseteq ω^{< ω}$ and any T-family ${U_{τ}}$ of subsets of X, we define the T-family ${{\tilde{U}}_{τ}}$ of subsets of X by ${\tilde{U}}_{τ} = U_{τ} ∖ ⋃ {U_{τ^{'}} ∣ τ ⊏ τ^{'} \in T}$ . The T-family ${U_{τ}}$ is monotone if $U_{τ} \supseteq U_{τ^{'}}$ for all $τ ⊑ τ^{'} \in T$ . We associate with any T-family ${U_{τ}}$ the monotone T-family ${U_{τ}^{'}}$ by $U_{τ}^{'} = ⋃_{τ^{'} ⊒ τ} U_{τ^{'}}$ . A T-family ${V_{τ}}$ is reduced if it is monotone and satisfies $V_{τ i} \cap V_{τ j} = \emptyset$ for all $τ i, τ j \in T$ . Obviously, for any reduced T-family ${V_{τ}}$ the components ${\tilde{V}}_{τ}$ are pairwise disjoint.

We will use the following technical notions. The first one is the notion “F is a T-family in $L (X)$ ” defined by induction as follows: if $T \in T_{0} (\bar{k})$ then $F = {X}$ ; if $(T, t) \in T_{m + 1} (\bar{k})$ then $F = ({U_{τ}}, {F_{τ}})$ where ${U_{τ}}$ is a monotone T-family of $L_{0}$ -sets with $T_{ε} = X$ and, for each $τ \in T$ , $F_{τ}$ is a $t (τ)$ -family in $L^{1} ({\tilde{U}}_{τ})$ . The version of this notion “F is a reduced T-family in $L (X)$ ” is obtained by taking the reduced T-families in place of the monotone ones. The second is the relation “a T-family F in $L (X)$ determines $A : X \to \bar{k}$ ” defined by induction as follows: if $T \in T_{0} (\bar{k})$ , $T = i < k$ (so $F = {X}$ ), then F determines the constant partition $A = λ x . i$ ; if $(T, t) \in T_{m + 1} (\bar{k})$ (so F is of the form $({U_{τ}}, {F_{τ}})$ ) then F determines the k-partition A such that $A |_{{\tilde{U}}_{τ}} = B_{τ}$ for every $τ \in T$ , where $B_{τ} : {\tilde{U}}_{τ} \to \bar{k}$ is the k-partition of ${\tilde{U}}_{τ}$ determined by $F_{τ}$ . Note that a family can determine at most one k-partition, and a reduced family determines precisely one k-partition (see [35] for additional details).

As explained in [26], the T-family F that determines A provides a mind-change algorithm for computing $A (x)$ (see Section 3 of [35] for additional details). We are ready to give a precise definition of the FH of k-partitions over $L (X)$ .

Definition 5.
The FH of k-partitions over $L (X)$ is the family ${L (X, T)}_{T \in T_{ω} (\bar{k})}$ of subsets of $k^{X}$ where $L (X, T)$ is the set of $A : X \to \bar{k}$ determined by some T-family in $L (X)$ . Let red- $L (X, T)$ denote the set of $A : X \to \bar{k}$ determined by some reduced T-family in $L (X)$ .

As shown in [30], $T ⩽_{h} S$ implies $L (X, T) \subseteq L (X, S)$ , hence $({L (X, T) ∣ T \in T_{ω} (\bar{k})}; \subseteq)$ is WQO. The FH of sets obtained from this construction for $k = 2$ is even semi-well-ordered since the quotient-poset of $(T_{ω} (\bar{2}); ⩽_{h})$ has order type $\bar{2} \cdot ε_{0}$ (see Definition 8.27 and Proposition 8.28 in [30]).

The FH of k-partitions over the effective Borel base $L (X) = {Σ_{1 + n}^{0} (X)}$ in an effective cb₀-space X is written as ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ and called the effective Wadge hierarchy in X. For $k = 2$ the structure of levels degenerates to the semi-well-ordered structure which enables the $Σ, Π$ -notation for them. The EWH of sets subsumes many hierarchies including those mentioned in Section 2.

The corresponding boldface FH ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ over the finite Borel base $L (X) = {Σ_{1 + n}^{0} (X)}$ is written as ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ and is called finitary Wadge hierarchy in X. It forms a small but important fragment of the whole (infinitary) Wadge hierarchy of k-partitions in X (which is constructed from the whole Borel hierarchy by taking countable well-founded trees T in place of the finite trees T). The latter hierarchy, which may be defined in arbitrary spaces, was introduced and studied in [26]. For the effective and boldface versions we have the obvious inclusions $Σ (X, T) \subseteq Σ (X, T)$ . In this paper we stick to levels of EWH corresponding to finite trees; the levels corresponding to computable well-founded trees (briefly discussed in [35]) are important on their own and we plan to investigate them in a separate publication.

We collect some simple properties of the EWH which are either contained in [30,35] or easily follow from the definitions. As above, the effective Borel base ${Σ_{1 + n}^{0} (X)}$ in X is sometimes abbreviated to $L$ .
Proposition 6.

$T ⩽_{h} V$ implies $Σ (X, T) \subseteq Σ (X, V)$ , hence $({Σ (X, T) ∣ T \in T_{ω} (\bar{k})}; \subseteq)$ is WQO for $k < ω$ and is well founded for $k = ω$ .

If $L$ is reducible then $L (X, T) =$ red- $L (X, T)$ for every $T \in T_{ω} (\bar{k})$ .

If $(T, t) \in T_{m + 1} (\bar{k})$ is a non-singleton normal tree, $ω \cap T = {i ∣ i < p}$ , and $A \in L^{n} (X, T)$ is determined by a T-family $({U_{τ}}, {F_{τ}})$ in $L^{n} (X)$ , then $A |_{\overline{U}} \in L^{n + 1} (\overline{U}, t (ε))$ , where $U = U_{0} \cup \dots \cup U_{p - 1}$ , and $A |_{U_{i}} \in L^{n} (U_{i}, T (i))$ for each $i < p$ .

Let $A \in k^{X}$ , T be as in the previous item and $V_{0}, \dots, V_{p - 1}$ be pairwise disjoint $L_{n}$ -sets such that $A |_{V_{i}} \in L^{n} (V_{i}, T (i))$ for $i < p$ , and $A |_{\overline{V}} \in L^{n + 1} (\overline{V}, t (ε))$ where $V = V_{0} \cup \dots \cup V_{p - 1}$ . Then $A \in L^{n} (X, T)$ .

Any level $Σ (X, T)$ is closed downwards under the effective Wadge reducibility on $k^{X}$ .

In [26,35] the following preservation property for levels of the (effective) WH was established (cf. this property with Proposition 11.2 and the results in Section 11.2 of [12]).
Proposition 7.
Let $f : Y \to X$ be a computable effectively open surjection between effective cb ₀ -spaces. Then, for all $T \in T_{ω} (\bar{k})$ and $A \in k^{X}$ , we have: $A \in Σ (X, T)$ iff $A \circ f \in Σ (Y, T)$ . Similarly for the boldface versions and continuous open surjections between cb ₀ -spaces.

The FH of sets over an arbitrary base $L$ is a sequence ${S_{α}}_{α < ε_{0}}$ , $ε_{0} = sup {ω, ω^{ω}, ω^{ω^{ω}}, \dots}$ , of subsets of $P (X)$ . It subsumes many refinements of the base $L$ . In particular $L_{0} = S_{1}$ , $L_{1} = S_{ω}$ , $L_{2} = S_{ω^{ω}}$ , $L_{3} = S_{ω^{ω^{ω}}}, \dots$ , ${S_{n}}_{n < ω}$ is the difference hierarchy over $L_{0}$ , ${S_{ω^{n + 1}}}_{n < ω}$ is the difference hierarchy over $L_{1}$ , ${S_{ω^{ω^{n + 1}}}}_{n < ω}$ is the difference hierarchy over $L_{2}$ , and so on.

The FH over the effective Borel base ${Σ_{1 + n}^{0} (X)}$ in X will sometimes be denoted by ${Σ_{α} (X)}_{α < ε_{0}}$ and called the EWH of sets in X. The corresponding boldface sequence ${Σ_{α} (N)}_{α < ε_{0}}$ forms a small but important fragment of the classical Wadge hierarchy in the Baire space. The EWH ${Σ_{α} (N)}_{α < ε_{0}}$ of sets in $N$ coincides with the FH of arithmetical sets ${Σ_{α}}_{α < ε_{0}}$ introduced in [27].
4. Non-collapse property

Here we establish some general facts about the non-collapse property. First we carefully define natural versions of this property.

We say that EWH ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ does not collapse at level T if $Σ (X, T) ⊈ Σ (X, V)$ for each $V \in T_{ω} (\bar{k})$ with $T ≰_{h} V$ ; the hierarchy strongly does not collapse at level T if $Σ (X, T) ⊈ ⋃ {Σ (X, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ . We say that ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ (strongly) does not collapse if it (strongly) does not collapse at any level $T \in T_{ω} (\bar{k})$ .

Note that for the case of sets $k = 2$ these definitions are equivalent to the standard definition of non-collapse in DST (Σ-levels are distinct from the corresponding Π-levels), and the strong version is equivalent to the non-strong one. Thus, the strong versions are not visible for $k = 2$ .

Proposition 8.

The EWH ${Σ (X, T)}$ does not collapse iff the quotient-poset of $(T_{ω} (\bar{k}); ⩽_{h})$ is isomorphic to $({Σ (X, T) ∣ T \in T_{ω} (\bar{k})}; \subseteq)$ .

If the EWH in X does not collapse at level T and $Σ (X, T)$ has a complete element w.r.t. the effective Wadge reducibility then the hierarchy strongly does not collapse at level T.

If the EWH in X does not collapse and every of its levels has a complete element w.r.t. the effective Wadge reducibility then the hierarchy strongly does not collapse.

Proof.
(1) Obvious from the definition.

(2) Let A be effective Wadge complete in $Σ (X, T)$ and let $V \in T_{ω} (\bar{k})$ satisfy $T ≰_{h} V$ ; it suffices to show that $A \notin Σ (X, V)$ . Since the hierarchy does not collapse at level T, there is $B \in Σ (X, T) ∖ Σ (X, V)$ . Since A is complete in $Σ (X, T)$ , we have $B ⩽_{e W}^{X} A$ . Since $Σ (X, V)$ is closed downwards under $⩽_{e W}^{X}$ by Proposition 6(5), we get $A \notin Σ (X, V)$ .

(3) Follows from (2). □

The non-collapse for the boldface versions are defined in the same way, and the analogue of the previous proposition holds for them with essentially the same proof, including the version for infinitary FH.

In the effective case, there are also the following uniform versions of non-collapse property which relate EWH to the corresponding WH. The EWH ${Σ (X, T)}$ uniformly does not collapse at level T if $Σ (X, T) ⊈ Σ (X, V)$ for each $V \in T_{ω} (\bar{k})$ with $T ≰_{h} V$ . The EWH ${Σ (X, T)}$ uniformly does not collapse if it uniformly does not collapse at every level. The hierarchy strongly uniformly does not collapse at level T if $Σ (X, T) ⊈ ⋃ {Σ (X, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ . The hierarchy strongly uniformly does not collapse if $Σ (X, T) ⊈ ⋃ {Σ (X, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ for all $T \in T_{ω} (\bar{k})$ .

The following analogue of Proposition 8 holds for the uniform version, essentially with the same proof.
Proposition 9.

If the EWH in X uniformly does not collapse at level T and $Σ (X, T)$ has a complete element w.r.t. $⩽_{e W}^{X}$ which is also Wadge complete in $Σ (X, T)$ then the hierarchy strongly uniformly does not collapse at level T.

If the EWH in X uniformly does not collapse and every of its levels has an element with the properties described in (1) then the hierarchy strongly uniformly does not collapse.

The next assertion follows from the inclusions between levels.
Proposition 10.
For any effective cb ₀ -space X we have: if ${Σ (X, T)}$ (strongly) uniformly does not collapse (at level T) then both ${Σ (X, T)}$ and ${Σ (X, T)}$ (strongly) do not collapse (at level T).

For cb₀-spaces X and Y, let $X ⩽_{c o} Y$ mean that there is a continuous open surjection f from Y onto X. For effective cb₀-spaces X and Y, let $X ⩽_{e c o} Y$ mean that there is a computable effectively open surjection f from Y onto X. Clearly, both $⩽_{e c o}$ and $⩽_{c o}$ are preorders, and the first preorder is contained in the second. The non-collapse property is inherited w.r.t. these preorders:
Proposition 11.

If $X ⩽_{c o} Y$ and ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ (strongly) does not collapse (at level T) then ${Σ (Y, T)}$ (strongly) does not collapse (at level T). The same holds for the infinitary version of WH in X.

If $X ⩽_{e c o} Y$ and ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ (strongly) does not collapse (at level T) then ${Σ (Y, T)}$ (strongly) does not collapse (at level T). The same holds for the uniform version of non-collapse property.

Proof.
All assertions follow from the definitions and the preservation property, so consider only the finitary version in item (1). Let $X ⩽_{c o} Y$ via $f : Y \to X$ , and ${Σ (X, T)}$ does not collapse at level T. We have to show that $Σ (Y, T) ⊈ Σ (Y, V)$ for any fixed $V \in T_{ω} (\bar{k})$ with $T ≰_{h} V$ . Choose $A \in Σ (X, T) ∖ Σ (X, V)$ . By Proposition 7 we get $A \circ f \in Σ (Y, T) ∖ Σ (Y, V)$ . □
Corollary 12.

If X is quasi-Polish and ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ (strongly) does not collapse (at level T) then ${Σ (N, T)}$ (strongly) does not collapse (at level T). The same holds for the infinitary version of the WH.

If X is computable quasi-Polish and ${Σ (X, T)}_{T \in T_{ω} (\bar{k})}$ (strongly) does not collapse (at level T) then ${Σ (N, T)}$ (strongly) does not collapse (at level T). The same holds for the uniform version.

If X is the product of a sequence ${X_{n}}$ of nonempty cb ₀ -spaces, and the finitary WH ${Σ (X_{n}, T)}$ (strongly) does not collapse (at level T) for some $n < ω$ , then ${Σ (X, T)}$ (strongly) does not collapse (at level T). The same holds for the infinitary version of the WH.

If X is the product of a uniform sequence ${X_{n}}$ of nonempty effective cb ₀ -spaces, and ${Σ (X_{n}, T)}$ (strongly) does not collapse (at level T) for some $n < ω$ , then ${Σ (X, T)}$ (strongly) does not collapse (at level T). The same holds for the uniform version.

Proof.
(1) Follows from Proposition 11(1) since X is quasi-Polish iff $X ⩽_{c o} N$ .

(2) Follows from Proposition 11(2) since X is computable quasi-Polish iff $X ⩽_{e c o} N$ .

(3) Follows from Proposition 11(1) since $X_{n} ⩽_{c o} X$ .

(4) Follows from Proposition 11(2) since $X_{n} ⩽_{e c o} X$ . □

Although the assertion (1) is void (because the infinitary WH in $N$ strongly does not collapse [17,39]), it is of some methodological interest because it shows that proving the non-collapse of WH in any quasi-Polish space is at least as complicated as proving it in $N$ , and the proof of the latter fact is highly non-trivial. The same applies to item (2) but this assertion is non-void because the non-collapse of EWH in $N$ was open until this paper, to my knowledge.

In the remaining sections we give prominent examples of spaces with the non-collapse property. A good strategy to obtain broad classes of such spaces is to make them as low as possible w.r.t. $⩽_{c o}, ⩽_{e c o}$ , and use the preservation property.
5. Effective Wadge hierarchy in $N$

In this section we discuss the EWH of k-partitions in $N$ , for any fixed number k satisfying $2 ⩽ k ⩽ ω$ . This hierarchy coincides with the FH of arithmetical k-partitions of ω first considered in [27]. In particular, we prove that the EWH of k-partitions in $N$ strongly does not collapse.

5.1. Complete numberings

Here we recall some information on precomplete and complete numberings from [10,19], their strong relativizations introduced in [27], and prove some additional facts. The properties formulated in this subsection are crucial for proving the main results below. We apologize for using in this subsection one rather non-standard notation. Namely, following A.I. Mal’cev [19], by ϰ we denote the Kleene numbering of the computable partial (c.p.) functions. Much more standard notation for ϰ is of course φ [24]; we chose the less standard notation because it was used in the paper [27] which is often cited below.

First we fix some notation and recall some notions of computability theory (we refer the reader to [10,19,24] for additional details). In particular, $⩽_{T}$ denotes the Turing reducibility on $P (ω)$ (and also on $k^{ω}$ for each $2 ⩽ k < ω$ ), $⩽_{m}$ denotes the many-one reducibility on $P (ω)$ , and $\equiv_{T}$ , $\equiv_{m}$ denote the corresponding equivalence relations. As usual, by ${Σ_{1 + n}^{0}}_{n < ω}$ we denote the arithmetical hierarchy of subsets of ω. As is well known, every level $Σ_{1 + n}^{0}$ has the reduction property.

If the contrary is not specified explicitly, by a (partial) function we mean a (partial) function from ω to ω, and by a set we mean a subset of ω. For a partial function ψ, by $ψ (x) ↓$ (resp. by $ψ (x) ↑$ ) we denote the fact that $x \in dom (ψ)$ (resp. $x \notin dom (ψ)$ ). It is sometimes useful to identify a partial function ψ with the total function $ψ : ω \to ω \cup {⊥}$ , where ⊥ is a new element such that $ψ (x) = ⊥$ iff $ψ (x) ↑$ .

By a numbering we mean any function ν with $dom (ν) = ω$ , and by a numbering of a set S – a numbering ν with $r n g (ν) = S$ . A numbering μ is reducible to a numbering ν (in symbols, $μ ⩽ ν$ ) if there is a computable total function f with $μ = ν \circ f$ . Note that ⩽ and $⩽_{m}$ coincide on $2^{ω}$ . For any $h \in ω^{ω}$ , $⩽^{h}$ denotes the h-relativization of the reducibility relation. The induced equivalence relations are denoted by ≡ and $\equiv^{h}$ , respectively.

Associate with any numberings $μ, ν$ and $ν_{k}$ $(k < ω)$ the numberings $μ \oplus ν$ , $μ \otimes ν$ and $⨁_{k} ν_{k}$ , called respectively the join of μ and ν, the product of μ and ν, and the infinite join of $ν_{k}$ $(k < ω)$ , and defined as follows: $\begin{matrix} (μ \oplus ν) (2 n) = μ n, (μ \oplus ν) (2 n + 1) = ν n, (μ \otimes ν) ⟨ x, y ⟩ = (μ x, ν y), (⨁_{k} ν_{k}) ⟨ x, y ⟩ = ν_{x} (y) . \end{matrix}$

Here $⟨ \cdot, \cdot ⟩$ is a standard computable bijection between $ω \times ω$ and ω; let $l, r$ be total computable functions such that $n = ⟨ l (n), r (n) ⟩$ for every $n < ω$ . Similar notation is used for coding longer tuples. The operations $\oplus, \otimes, ⨁$ are applicable to sets (by identifying sets with characteristic functions considered as numberings). Iteration of ⊕ may be of course used to define join $ν = ν_{0} \oplus \dots \oplus ν_{p - 1}$ of every finite sequence of numberings $ν_{0}, \dots, ν_{p - 1} = ⨁_{i < p} ν_{p}$ , $p > 0$ . We will use the following technically convenient syntactic version of this join: $ν (x) = ν_{i} (a)$ where a is the quotient and $i = rest (x, p)$ is the remainder of the division of x by p, i.e. $x = p \cdot a + i$ .

Let ϰ denote the usual computable numbering of the computable partial (c.p.) functions. Note that $\tilde{ϰ} = ⨁_{k} ϰ_{k}$ is the standard universal c.p. function. By $ϰ^{h}$ we denote the h-relativization of ϰ to any oracle $h \in ω^{ω}$ , and by $h^{'} = dom (ϰ^{h})$ – the Turing jump of h which may be considered as an operator on $k^{ω}$ for every $2 ⩽ k ⩽ ω$ .

For any oracle $h \in ω^{ω}$ , a numbering ν is called h-precomplete, if for any h-computable partial (h-c.p.) function ψ there is a total computable function t (called a ν-totalizer of ψ) such that $ν t (x) = ν ψ (x)$ for $x \in dom (ψ)$ . For $h = \emptyset$ , h-precomplete numberings are called precomplete. Note that if ν is precomplete and ${ψ_{n}}$ is a uniform sequence of c.p. functions then there is a uniform sequence ${t_{n}}$ of ν-totalizers for them. The precomplete numberings are just the numberings satisfying an effective version of the Kleene recursion theorem. A numbering ν is h-complete (w.r.t. $a \in r n g (ν)$ ), if for every h-c.p. function ψ there is a computable function t (called a ν-totalizer of ψ w.r.t. a) such that $ν t (x) = ν ψ (x)$ for $ψ (x) ↓$ and $ν t (x) = a$ for $ψ (x) ↑$ . It is known that if $μ, ν$ are h-precomplete (resp. h-complete) then so is also $μ \otimes ν$ .

A relativization of the known property that any precomplete numbering is join-irreducible (see e.g. [10]) shows that if $ν ⩽^{h} ν_{1} \oplus ν_{2}$ and ν is h-precomplete then $ν ⩽^{h} ν_{1}$ or $ν ⩽^{h} ν_{2}$ ; we will refer to this fact as the join-irreducibility property of h-precomplete numberings. Note that the constant numberings $λ n . s$ , $s \in S$ , are precisely the numberings in $S^{ω}$ which are h-complete for every oracle h. Let $S_{⊥}^{ω}$ be obtained from $S^{ω}$ by adjoining a new element ⊥ such that $⊥ <^{h} ν$ for all $h \in ω^{ω}$ and $ν \in S^{ω}$ .

Proposition 13.

The structure $(S_{⊥}^{ω}; \oplus, ⩽^{h})$ is a distributive semilattice.

Any h-precomplete numbering $ν : ω \to S$ is join-irreducible in $(S_{⊥}^{ω}; \oplus, ⩽^{h})$ .

For any h-precomplete numberings $μ, ν$ we have: $μ ⩽^{h} ν$ iff $μ ⩽ ν$ .

For any finite families ${μ_{i}}$ and ${ν_{j}}$ of h-precomplete numberings we have: $⨁_{i} μ_{i} ⩽^{h} ⨁_{j} ν_{j}$ iff $⨁_{i} μ_{i} ⩽ ⨁_{j} ν_{j}$ .

Proof.
Items (1) and (2) are relativizations of known facts [10], item (3) is clear from the definition of h-precompleteness ν (in fact, the assertion is true for arbitrary numbering μ). For item (4), using items (1)–(3), we obtain: $⨁_{i} μ_{i} ⩽^{h} ⨁_{j} ν_{j}$ iff $\forall i (μ_{i} ⩽^{h} ⨁_{j} ν_{j})$ iff $\forall i \exists j (μ_{i} ⩽^{h} ν_{j})$ iff $\forall i \exists j (μ_{i} ⩽ ν_{j})$ iff $⨁_{i} μ_{i} ⩽ ⨁_{j} ν_{j}$ . □

The Kleene numbering ϰ and its relativization $ϰ^{h}$ are the most important for this section; $ϰ^{h}$ is h-complete w.r.t. the empty function, and the universal h-c.p. function ${\tilde{ϰ}}^{h} : ω \to ω_{⊥}$ is h-complete w.r.t. ⊥. The Kleene recursion theorem for $ϰ \otimes ϰ$ is known as the double recursion theorem: for any uniformly computable sequences ${g_{x}}$ , ${h_{x}}$ of partial functions there is e such that $g_{e} = ϰ_{l (e)}$ and $h_{e} = ϰ_{r (e)}$ .

For any $s \in S$ and $h \in ω^{ω}$ , we defined in [27] the unary operation $p_{s}^{h}$ on $S^{ω}$ , which modifies and relativises the completion operation from [10], as follows: $[p_{s}^{h} (ν)] (x) = s$ if ${\tilde{ϰ}}^{h} (x) ↑$ and $[p_{s}^{h} (ν)] (x) = ν {\tilde{ϰ}}^{h} (x)$ otherwise. Next we recall an operation which, for $k = 2$ , is a natural combination of these operations and Turing jump.
Definition 14.
For $μ, ν \in S^{ω}$ and $h \in ω^{ω}$ , let $G (μ, ν, h) = ⨁_{n < ω} p_{ν (n)}^{h} (μ)$ . In other words, we have: $[G (μ, ν, h)] ⟨ n, x ⟩ = ν (n)$ for ${\tilde{ϰ}}^{h} (x) ↑$ and $[G (μ, ν, h)] ⟨ n, x ⟩ = μ {\tilde{ϰ}}^{h} (x)$ for ${\tilde{ϰ}}^{h} (x) ↓$ .

The function $G : S^{ω} \times S^{ω} \times ω^{ω} \to S^{ω}$ , introduced in [27], is crucial for this section. Its relations to the EWH in $N$ is explained by the fact that, as also levels of this hierarchy, the operation is defined by using a relativized mind-change construct uniformly on oracles.

The next proposition collects some facts from Propositions 1–3 in [27]. Item (7), formulated here in a slightly modified form, obviously remains true.
Proposition 15.

$G (μ, ⨁_{n < ω} ν_{n}, h) \equiv ⨁_{n} G (μ, ν_{n}, h)$ .

$μ ⩽ G (μ, ν, h)$ , $ν ⩽ G (μ, ν, h)$ , $G (μ, ν, h) ⩽^{h^{'}} μ \oplus ν$ .

If $μ ⩽^{h} μ_{1}$ then $G (μ, ν, h) ⩽ G (μ_{1}, ν, h)$ .

If $μ ⩽^{g} μ_{1}$ and $h^{'} ⩽_{T} g$ then $G (μ, ν, h) ⩽^{g} G (μ_{1}, ν, h)$ .

If $ν ⩽^{g} ν_{1}$ then $G (μ, ν, h) ⩽^{g} G (μ, ν_{1}, h)$ .

If $h ⩽_{T} h_{1}$ then $G (μ, ν, h) ⩽ G (μ, ν, h_{1})$ .

For all $f, g, h \in ω^{ω}$ we have: if $f = g = λ n . m$ for some $m < ω$ then $G (f, g, h) = λ n . m$ , otherwise $G (f, g, h) \equiv_{T} f \oplus g \oplus h^{'}$ .

If μ is $h^{'}$ -complete and $ν ⩽^{h^{'}} μ$ then $G (μ, ν, h) \equiv μ$ .

If ν is h-complete w.r.t. $s \in S$ then so is $G (μ, ν, h)$ .

$G (μ, G (ν, ξ, h), h) \equiv G (G (μ, ν, h), ξ, h)$ .

If $h^{'} ⩽_{T} g$ then $G (μ, G (ν, ξ, h), g) \equiv G (G (μ, ν, g), G (μ, ξ, g), h)$ .

If $g^{'} ⩽_{T} h$ then $G (μ, G (ν, ξ, h), g) ⩽ G (μ \oplus ν, ξ, h)$ .

The next assertion, proved by arguments close to those in [27], is formally new here. The item (4) in this assertion is an extended version of the join-irreducibility property of h-precomplete numberings. Proposition 16.

If $μ ⩽^{h^{'}} ν$ and ν is $h^{'}$ -complete then $G (μ \oplus μ_{1}, ν, h) \equiv G (μ_{1}, ν, h)$ .

If ν is $h^{'}$ -complete then $G (G (μ, ν, h) \oplus μ_{1}, ν, h) \equiv G (μ \oplus μ_{1}, ν, h)$ .

If μ (resp. ν) is $h^{'}$ -complete then $λ ν . G (μ, ν, h)$ (resp. $λ μ . G (μ, ν, h)$ ) is a closure operator on $(S^{ω}; ⩽)$ (resp. on $(S^{ω}; ⩽^{h})$ ).

If $G (μ, ν, h) ⩽^{h} G (μ_{1}, ν_{1}, h)$ and ν is $h^{'}$ -precomplete then $ν ⩽ ν_{1}$ or $G (μ, ν, h) ⩽ μ_{1}$ .

Proof.
(1) By Proposition 15(3), it suffices to show that $G (μ \oplus μ_{1}, ν, h) ⩽ G (μ_{1}, ν, h)$ . Let u be an $h^{'}$ -computable function with $μ = ν \circ u$ , $ω_{i} = {2 x + i ∣ x < ω}$ for $i < 2$ , and let $\begin{matrix} f_{1} ⟨ m, x ⟩ = \{\begin{matrix} m, & if {\tilde{ϰ}}^{h} (x) ↑ \lor {\tilde{ϰ}}^{h} (x) ↓ \in ω_{1}, \\ u (\frac{{\tilde{ϰ}}^{h} (x)}{2}), & if {\tilde{ϰ}}^{h} (x) ↓ \in ω_{0} . \end{matrix} \end{matrix}$ Then $f_{1} ⩽_{T} h^{'}$ , hence $ν \circ f_{1} = ν \circ f$ for some computable function f. Let g be a computable function such that $\begin{matrix} {\tilde{ϰ}}^{h} g (x) = \{\begin{matrix} ↑, & if {\tilde{ϰ}}^{h} (x) ↑ \lor {\tilde{ϰ}}^{h} (x) ↓ \in ω_{0}, \\ \frac{{\tilde{ϰ}}^{h} (x) - 1}{2}, & if {\tilde{ϰ}}^{h} (x) ↓ \in ω_{1} . \end{matrix} \end{matrix}$ Then the computable function $⟨ m, x ⟩ \mapsto ⟨ f ⟨ m, x ⟩, g (x) ⟩$ reduces $G (μ \oplus μ_{1}, ν, h)$ to $G (μ_{1}, ν, h)$ .

(2) By Proposition 15(2) and 15(3), it suffices to check that $G (G (μ, ν, h) \oplus μ_{1}, ν, h) ⩽ G (μ \oplus μ_{1}, ν, h)$ . Let $\begin{matrix} f_{1} ⟨ m, x ⟩ = \{\begin{matrix} m, & if {\tilde{ϰ}}^{h} (x) ↑ \lor {\tilde{ϰ}}^{h} (x) ↓ \in ω_{1}, \\ l (\frac{\tilde{ϰ} h (x)}{2}), & if {\tilde{ϰ}}^{h} (x) ↓ \in ω_{0} . \end{matrix} \end{matrix}$ Then $f_{1} ⩽_{T} h^{'}$ , hence $ν \circ f_{1} = ν \circ f$ for some computable function f. Let g be a computable function satisfying $\begin{matrix} {\tilde{ϰ}}^{h} g (x) = \{\begin{matrix} ↑, & if {\tilde{ϰ}}^{h} (x) ↑ \lor ({\tilde{ϰ}}^{h} (x) ↓ \in ω_{0} \land {\tilde{ϰ}}^{h} r (\frac{{\tilde{ϰ}}^{h} (x)}{2}) ↑), \\ 2 {\tilde{ϰ}}^{h} r (\frac{{\tilde{ϰ}}^{h} (x)}{2}), & if ({\tilde{ϰ}}^{h} (x) ↓ \in ω_{0} \land {\tilde{ϰ}}^{h} r (\frac{{\tilde{ϰ}}^{h} (x)}{2}) ↓), \\ {\tilde{ϰ}}^{h} (x), & if {\tilde{ϰ}}^{h} (x) ↓ \in ω_{1} . \end{matrix} \end{matrix}$ Then the computable function $⟨ m, x ⟩ \mapsto ⟨ f ⟨ m, x ⟩, g (x) ⟩$ reduces $G (G (μ, ν, h) \oplus μ_{1}, ν, h)$ to $G (μ \oplus μ_{1}, ν, h)$ .

(3) Recall that a closure operator on a preorder $(Q; ⩽)$ is a monotone function $f : Q \to Q$ such that $x ⩽ f (x)$ and $f (f (x)) ⩽ f (x)$ . The monotonicity and the property $x ⩽ f (x)$ for the operators in the assertion are contained in Proposition 15. It remains to check that $G (μ, G (μ, ν, h), h) ⩽ G (μ, ν, h)$ for an $h^{'}$ -complete μ, and $G (G (μ, ν, h), ν, h) ⩽^{h} G (μ, ν, h)$ for an $h^{'}$ -complete ν. By Proposition 15(2), $G (μ, μ, h) ⩽^{h^{'}} μ$ . Since μ is $h^{'}$ -complete, we get $G (μ, μ, h) ⩽ μ$ . By item (1) and Proposition 15(3) and 15(10) we obtain $G (μ, G (μ, ν, h), h) \equiv G (G (μ, μ, h), ν, h) ⩽ G (μ, ν, h)$ .

It remains to check the assertion for ν. As above, $G (ν, ν, h) ⩽ ν$ . By Proposition 15(5) and 15(10), we obtain $G (G (μ, ν, h), ν, h) \equiv G (μ, G (ν, ν, h), h) ⩽ G (μ, ν, h)$ .

(4) Let f be an h-computable function that reduces $G (μ, ν, h)$ to $G (μ_{1}, ν_{1}, h)$ and let $\begin{matrix} Y_{x} = {y ∣ {\tilde{ϰ}}^{h} r f ⟨ ϰ_{l (x)} (y), ϰ_{r (x)} (y) ⟩ ↓} . \end{matrix}$ Since the set $Y_{x}$ is h-c.e. uniformly in x, there are uniform sequences ${φ_{x}}, {ψ_{x}}$ of h-c.p. functions such that $ψ_{x}$ is a bijection between a (unique) initial segment of ω and $Y_{x}$ , and $φ_{x} = ψ_{x}^{- 1}$ . Let ${\bar{φ}}_{x} (y) = φ_{x} (y)$ for $y \in Y_{x}$ and ${\bar{φ}}_{x} (y) = y$ otherwise, then ${\bar{φ}}_{x} ⩽_{T} h^{'}$ uniformly in x. Since ν is $h^{'}$ -precomplete, there is a uniform sequence ${u_{x}}$ of computable total functions such that $ν \circ l \circ {\bar{φ}}_{x} = ν \circ u_{x}$ . Since ${\tilde{ϰ}}^{h}$ is h-complete, there is a uniform sequence ${v_{x}}$ of total computable functions such that ${\tilde{ϰ}}^{h} \circ r \circ φ_{x} = {\tilde{ϰ}}^{h} \circ v_{x}$ . By the double recursion theorem, there is e such that $u_{e} = ϰ_{l (e)}$ and $v_{e} = ϰ_{r (e)}$ .

It suffices to show that if $Y_{e}$ is finite then $ν ⩽ ν_{1}$ , else $G (μ, ν, h) ⩽ μ_{1}$ . Let first $Y_{e}$ be finite. For any $z = ⟨ z_{1}, z_{2} ⟩ \in ω ∖ Y_{e}$ with ${\tilde{ϰ}}^{h} (z_{2}) ↑$ we have $ν (z_{1}) = G (μ, ν, h) (z)$ . Since $φ_{e} (z) ↑$ , we have ${\tilde{ϰ}}^{h} v_{e} (z) ↑$ , hence $G (μ, ν, h) ⟨ u_{e} (z), v_{e} (z) ⟩ = ν u_{e} (z) = ν l {\bar{φ}}_{e} (z) = ν l (z) = ν (z_{1})$ . Therefore, $\begin{matrix} ν (z_{1}) = G (μ, ν, h) ⟨ u_{e} (z), v_{e} (z) ⟩ = G (μ, ν, h) ⟨ ϰ_{l (e)} (z), ϰ_{r (e)} (z) ⟩ = ν_{1} l f ⟨ u_{e} (z), v_{e} (z) ⟩, \end{matrix}$ so $ν ⩽ ν_{1}$ .

Let now $Y_{e}$ be infinite, then $φ_{e} : Y_{e} \to ω$ is a bijection and $φ_{e} ψ_{e} (m) = m$ for every $m < ω$ . Setting $y = ψ_{e} (m)$ , we obtain $ν l φ_{e} (y) = ν u_{e} (y)$ and $μ {\tilde{ϰ}}^{h} r φ_{e} (y) = μ {\tilde{ϰ}}^{h} v_{e} (y)$ , hence $\begin{array}{l} G (μ, ν, h) (m) & = G (μ, ν, h) φ_{e} (y) = G (μ, ν, h) ⟨ u_{e} (y), v_{e} (y) ⟩ \\ = G (μ_{1}, ν_{1}, h) f ⟨ ϰ_{l (e)} (y), ϰ_{r (e)} (y) ⟩ = μ_{1} {\tilde{ϰ}}^{h} f ⟨ u_{e} ψ_{e} (m), v_{e} ψ_{e} (m) ⟩ . \end{array}$ Thus, $G (μ, ν, h) ⩽ μ_{1}$ . □

5.2. An algebra of k-partitions of ω

For $S = \bar{k}$ , $2 ⩽ k ⩽ ω$ , the operation G from Definition 14 becomes a ternary operation on $k^{ω}$ . Let $A_{k}$ be the subalgebra of $(k^{ω}; \oplus, G)$ generated by the constant functions $i = λ x . i$ , $i < k$ . Here we prove a series of facts about this subalgebra which relates it to the structure of iterated k-forests.

Let $T_{k}$ be the set of variable-free terms of signature $σ_{k} = {i, \oplus, G ∣ i < k}$ , then $A_{k} = {u ∣ u \in T_{k}}$ where u is the value of u in $(k^{ω}; σ_{k})$ . Let $0^{(0)} = 0$ and $0^{(n + 1)} = G (0, 1, 0^{(n)})$ , then ${0^{(n)}}$ essentially coincides with the usual iterations of Turing jump starting with $0$ , see Proposition 15(7). The following fact characterizes the quotient-poset of $(A_{k}; ⩽_{T})$ .

Fact 1.
Given $u \in T_{k}$ , one can compute $n = n (u)$ with $u \equiv_{T} 0^{(n)}$ . Therefore, $A_{k} \equiv_{T} {0^{(n)} ∣ n < ω}$ and hence $(A_{k}; ⩽_{T}) ≃ (ω; ⩽)$ .
Proof.
Define $n (u)$ by induction on (the rank of) u as follows: $n (i) = 0$ for every $i < k$ , $n (u_{1} \oplus u_{2}) = max (n (u_{1}), n (u_{2}))$ , $n (G (u_{1}, u_{2}, u_{3})) = 0$ if $u_{1} = u_{2} = i$ for some $i < k$ and $n (G (u_{1}, u_{2}, u_{3})) = max (n (u_{1}), n (u_{2}), n (u_{3}) + 1)$ otherwise. By Proposition 15(7), the function $u \mapsto n (u)$ works. □

For any $n < ω$ we define the binary operation $\cdot^{n}$ on $k^{ω}$ by $ν \cdot^{n} μ = G (μ, ν, 0^{(n)})$ ; note that $A_{k}$ is closed under these operations. Let $T_{k}^{}$ be the set of variable-free terms of signature $σ_{k}^{} = {i, \oplus, \cdot^{n} ∣ i < k, n < ω}$ .
Fact 2.
Given $u \in T_{k}$ , one can compute $u^{} \in T_{k}^{}$ with $u \equiv u^{}$ , and vice versa. In particular,* $A_{k} \equiv {u ∣ u \in T_{k}^{}}$ .
Proof.
Define $u \mapsto u^{}$ by induction on u as follows: $i^{} = i$ for every $i < k$ , ${(u_{1} \oplus u_{2})}^{} = u_{1}^{} \oplus u_{2}^{}$ , and $G {(u_{1}, u_{2}, u_{3})}^{} = u_{2}^{} \cdot^{n} u_{1}^{}$ where $n = n (u_{3})$ is from Fact 1. By items (3,5,6) of Proposition 15, $u \equiv u^{}$ for every $u \in T_{k}$ . The opposite direction (computing from any given $u \in T_{k}^{}$ some $v \in T_{k}$ with $u \equiv v$ ) is considered similarly. □

From now on we will work with the signature $σ_{k}^{}$ and its subsignatures. We abbreviate $⩽^{0^{(n)}}$ to $⩽^{n}$ , so in particular $⩽^{0} = ⩽$ . For any $n < ω$ , let $A_{k}^{n} = {ν \in A_{k} ∣ ν ⩽_{T} 0^{(n)}}$ . By Fact 1, $A_{k}^{n} = {u ∣ n (u) ⩽ n}$ . We give a more constructive characterization of $A_{k}^{n}$ . Let $T_{k}^{n}$ be the set of variable-free terms of $σ_{k}^{n} = {i, \oplus, \cdot^{p} ∣ i < k, p < n}$ , then $⋃_{n} T_{k}^{n} = T_{k}^{}$ .
Fact 3.
We have:* $A_{k}^{n} \equiv {u ∣ u \in T_{k}^{n}}$ .
Proof.
The inclusion ⊇ follows from the proof of Fact 1. For the converse, it suffices to prove by induction on $u \in T_{k}^{}$ that if $u \in A_{k}^{n}$ then $u \equiv u^{}$ for some $u^{} \in T_{k}^{n}$ . If $u = i$ or $u = u_{1} \oplus u_{2}$ , we respectively set $u^{} = i$ or $u^{} = u_{1}^{} \oplus u_{2}^{}$ . Now let $u = u_{1} \cdot^{p} u_{2}$ . If $p < n$ , we can set $u^{} = u_{1}^{} \cdot^{p} u_{2}^{}$ . Finally, let $n ⩽ p$ . If $u_{1} = u_{2} = i$ for some $i < k$ , we set $u^{} = i$ . The remaining case is not possible because in this case $n (u) ⩾ p + 1 > n$ by Fact 1, hence $0^{(n + 1)} ⩽_{T} u$ and $u \notin A_{k}^{n}$ . □

We define the family ${f_{m}^{n}}_{n < ω}$ of functions $f_{m}^{n} : T_{m} (\bar{k}) \to T_{k}^{}$ by induction on m as follows. Let $f_{0}^{n} (i) = i$ for all $i < k, n < ω$ . It remains to define $f_{m + 1}^{n}$ from $f_{m}^{n + 1}$ . Let $(T, t) \in T_{m + 1} (\bar{k}) = T (T_{m} (\bar{k}))$ . If T is singleton we set $f_{m + 1}^{n} (T) = f_{m}^{n + 1} (t (ε))$ , otherwise we set $\begin{matrix} f_{m + 1}^{n} (T) = f_{m}^{n + 1} (t (ε)) \cdot^{n} (⨁ {f_{m + 1}^{n} (T (i)) ∣ i \in ω \cap T}), \end{matrix}$ using induction on the rank of T. We also define functions $f_{m}^{n} : T_{m} (\bar{k}) \to A_{k}$ by $f_{m}^{n} = e v \circ f_{m}^{n}$ where $e v : T_{k}^{} \to A_{k}$ is the evaluation function $e v (u) = u$ .
Fact 4.
For* $T, V \in T_{m} (\bar{k})$ we have: $f_{m}^{n} (T)$ is $0^{(n)}$ -complete, and $T ⩽_{h} V$ iff $f_{m}^{n} (T) ⩽ f_{m}^{n} (V)$ .
Proof.
The $0^{(n)}$ -completeness of $f_{m}^{n} (T)$ follows by induction on m from the definition and Proposition 15(9). The second fact is checked by induction on m and the ranks of trees $(T, t)$ and $(V, v)$ . For $m = 0$ the assertion is obvious, so let $T, V \in T_{m + 1} (\bar{k})$ . Let first T be singleton, then $f_{m + 1}^{n} (T) = f_{m}^{n + 1} (t (ε))$ , which we temporarily denote by ν, is $0^{(n + 1)}$ -complete. By the definition, $f_{m + 1}^{n} (V)$ is the value of some ${\oplus, \cdot^{n}}$ -term $u (x_{1}, \dots, x_{p})$ whose variables take values in ${f_{m}^{n + 1} (t (σ)) ∣ σ \in V}$ . Since $ν_{1} \cdot^{n} μ_{1} \equiv^{n + 1} ν_{1} \oplus μ_{1}$ , $f_{m + 1}^{n} (V)$ is $\equiv^{n + 1}$ -equivalent to the finite join of values $f_{m}^{n + 1} (t (σ))$ for $σ \in V$ . Since $f_{m}^{n + 1} (t (ε))$ is $0^{(n + 1)}$ -complete, by the relativised join-irreducible property of precomplete numberings we obtain that $T ⩽_{h} V$ iff $t (ε) ⩽_{h} v (σ)$ for some $σ \in V$ iff $f_{m}^{n + 1} (t (ε)) ⩽^{n} f_{m}^{n + 1} (v (σ))$ for some $σ \in V$ iff $f_{m + 1}^{n} (T) ⩽ f_{m + 1}^{n} (V)$ .

Now let V be singleton, then $f_{m + 1}^{n} (V) = f_{m}^{n + 1} (v (ε))$ , which we temporarily denote by μ, is $0^{(n + 1)}$ -complete. By the definition, $f_{m + 1}^{n} (T)$ is the value of some ${\oplus, \cdot^{n}}$ -term $u (x_{1}, \dots, x_{p})$ whose variables take values in ${f_{m}^{n + 1} (t (τ)) ∣ τ \in T}$ . By Proposition 15(8) we have $μ \cdot^{n} μ \equiv μ$ (and of course also $μ \oplus μ \equiv μ$ ). Therefore, $T ⩽_{h} V$ iff $t (τ) ⩽_{h} v (ε)$ for all $τ \in T$ iff $f_{m}^{n + 1} (t (τ)) ⩽ μ$ for all $τ \in T$ iff $f_{m + 1}^{n} (T) ⩽ f_{m + 1}^{n} (V)$ .

Finally, let both T and V be non-singletons. If $t (ε) ⩽ v (ε)$ then $f_{m}^{n + 1} (t (ε)) ⩽ f_{m}^{n + 1} (v (ε))$ and therefore we have: $T ⩽_{h} V$ iff $T (i) ⩽ V$ for all $i \in ω \cap T$ iff $f_{m + 1}^{n} (T (i)) ⩽ f_{m + 1}^{n} (V)$ for all $i \in ω \cap T$ iff $f_{m + 1}^{n} (T) ⩽ f_{m}^{n + 1} (v (ε)) \cdot^{n} f_{m + 1}^{n} (V)$ iff $f_{m + 1}^{n} (T) ⩽ f_{m + 1}^{n} (V)$ (the latter equivalence uses Proposition 15(8) and 15(10)). If $t (ε) ≰ v (ε)$ then $f_{m}^{n + 1} (t (ε)) ≰ f_{m}^{n + 1} (v (ε))$ and therefore we have: $T ⩽_{h} V$ iff $T ⩽ V (j)$ for some $j \in ω \cap V$ iff $f_{m + 1}^{n} (T) ⩽ f_{m + 1}^{n} (V (j))$ for some $j \in ω \cap V$ iff $f_{m + 1}^{n} (T) ⩽ f_{m + 1}^{n} (V)$ (the latter equivalence uses Proposition 13(1,2)) and Proposition 16(4)). □

Using Proposition 1, we extend the function $f_{m}^{n} : T_{m} (\bar{k}) \to T_{k}^{}$ to a function $f_{m}^{n} : F_{m} (\bar{k}) \to T_{k}^{}$ (denoted for simplicity by the same name) by $f_{m}^{n} (T_{0} ⊔ \dots ⊔ T_{p}) = f_{m}^{n} (T_{0}) \oplus \dots \oplus f_{m}^{n} (T_{p})$ where $T_{i}$ are trees. We also define functions $f_{m}^{n} : F_{m} (\bar{k}) \to A_{k}$ by $f_{m}^{n} = e v \circ f_{m}^{n}$ , as above. In the next fact we use the operation · on forests defined before Proposition 2.
Fact 5.
For all $F, G \in F_{m} (\bar{k})$ we have: $F ⩽_{h} G$ iff $f_{m}^{n} (F) ⩽^{n} f_{m}^{n} (G)$ , $f_{m}^{n} (F ⊔ G) \equiv^{n} f_{m}^{n} (F) \oplus f_{m}^{n} (G)$ , and $f_{m}^{n} (F \cdot G) \equiv^{n} f_{m}^{n} (F) \cdot^{n} f_{m}^{n} (G)$ .
Proof.
The first and second assertions follow from Proposition 1 and Fact 4. For the third assertion, we use induction on the cardinality of F. Let first $F = T$ be a tree. If T is singleton, the assertion holds by the definition of $f_{m}^{n}$ . Otherwise, using the induction, the associativity of · (Proposition 3(2)) and of $\cdot^{n}$ (which holds by Proposition 15(10)) and abbreviating $f_{m}^{n}$ to f, we obtain: $\begin{array}{l} f (T \cdot G) & = f (({ε} \cdot (T ∖ {ε}) \cdot G) = f ({ε} \cdot (T ∖ {ε} \cdot G)) = f ({ε}) \cdot^{n} f (T ∖ {ε}) \cdot G) \\ \equiv^{n} f ({ε}) \cdot^{n} (f (T ∖ {ε}) \cdot^{n} f (G)) \equiv^{n} (f ({ε}) \cdot^{n} f (T ∖ {ε}) \cdot^{n} f (G) \equiv^{n} f (T) \cdot^{n} f (G) . \end{array}$

Let now F be not a tree, then $F \equiv_{h} F_{1} ⊔ F_{2}$ for some $F_{1}, F_{2} \in F_{m} (\bar{k})$ of lesser cardinalities than F. Using the induction, the second assertion of Fact 5, the right distributivity of · w.r.t. ⊔ (see the end of Section 2.3) and of $\cdot^{n}$ w.r.t. ⊕ (which is essentially Proposition 15(1)), we obtain: $\begin{array}{l} f (F \cdot G) & \equiv^{n} f ((F_{1} ⊔ F_{2}) \cdot G) \equiv^{n} f ((F_{1} \cdot G) ⊔ (F_{2} \cdot G)) \equiv^{n} f (F_{1} \cdot G) \oplus f (F_{2} \cdot G) \\ \equiv^{n} (f (F_{1}) \cdot^{n} f (G)) \oplus (f (F_{2}) \cdot^{n} f (G)) \equiv^{n} (f (F_{1}) \oplus f (F_{2})) \cdot^{n} f (G) \equiv^{n} f (F) \cdot^{n} f (G) . \end{array}$ □

Define a function $f^{n} : F_{ω} (\bar{k}) \to A_{k}$ by $f^{n} (F) = f_{m}^{n} (F)$ where $m < ω$ is the unique number with $F \in F_{m} (\bar{k})$ , and abbreviate $f^{0}$ to f. By Fact 5 and the results in Section 2.3, $f^{n}$ induces an isomorphic embedding of the quotient-structure of $(F_{ω} (\bar{k}); ⊔, ⩽_{h})$ under $\equiv_{h}$ into the quotient-structure of $(A_{k}; \oplus, ⩽^{n})$ under $\equiv^{n}$ . These embeddings play a crucial role in the proofs of main results of this paper in the next subsection.
Remark 17.
In the remaining part of the current subsection we show that these embeddings are even isomorphisms which is interesting on its own and may be used to describe the presentation complexity of these structures. Since some of the remaining proofs are tedious and make no influence on the main non-collapse theme of this paper, the rest of this subsection may be skipped without any damage for the main theme.

We define the unary functions s and r on $T_{k}^{}$ by induction on terms as follows: $s (i) = r (i) = i$ , $s (u_{1} \oplus u_{2}) = s (u_{1}) \oplus s (u_{2})$ , $r (u_{1} \oplus u_{2}) = r (u_{1}) \oplus r (u_{2})$ , $s (u_{1} \cdot^{p} u_{2}) = s (u_{1}) \cdot^{p + 1} s (u_{2})$ , $r (u_{1} \cdot^{0} u_{2}) = r (u_{1}) \oplus r (u_{2})$ , $r (u_{1} \cdot^{p + 1} u_{2}) = r (u_{1}) \cdot^{p} r (u_{2})$ . The next fact is obvious (the last assertion holds because the term $f_{m}^{n} (F)$ has no entries of $\cdot^{0}$ ).
Fact 6.
We have:* $r (s (u)) = u$ , $s (T_{k}^{n}) \subseteq T_{k}^{n + 1}$ , $r (T_{k}^{n + 1}) \subseteq T_{k}^{n}$ , and $s (r (f_{m}^{n} (F))) = f_{m}^{n} (F)$ for $n > 0$ .

The next two facts describe relationships of operations s and r (on the labeled forests and on the terms) to the functions $f_{m}^{n}$ .
Fact 7.
For any $F \in F_{m} (\bar{k})$ we have: $s (f_{m}^{n} (F)) = f_{m}^{n + 1} (F)$ and $r (f_{m}^{n + 1} (F)) = f_{m}^{n} (F)$ .
Proof.
Since all $s, r, f_{m}^{n}$ respect ⊔ and ⊕, it suffices to check this for the case when $F = (T, t)$ is a tree. We argue by induction on m. For $m = 0$ the assertion is clear since $F = i < k$ , so let $m > 0$ . If T is singleton then $s (f_{m}^{n} (F)) = s (f_{m - 1}^{n + 1} (t (ε))) = f_{m - 1}^{n + 2} (t (ε)) = f_{m}^{n + 1} (F)$ and $r (f_{m}^{n + 1} (F)) = r (f_{m - 1}^{n + 2} (t (ε))) = f_{m - 1}^{n + 1} (t (ε)) = f_{m}^{n} (F)$ . Otherwise, by induction on the rank of T we have: $\begin{matrix} s (f_{m}^{n} (F)) = s (f_{m - 1}^{n + 1} (t (ε)) \cdot^{n} ⨁_{i} f_{m}^{n} (T (i))) = f_{m - 1}^{n + 2} (t (ε)) \cdot^{n + 1} ⨁_{i} f_{m}^{n + 1} (T (i)) = f_{m}^{n + 1} (F) \end{matrix}$ and $\begin{matrix} r (f_{m}^{n + 1} (F)) = r (f_{m - 1}^{n + 2} (t (ε)) \cdot^{n + 1} ⨁_{i} f_{m}^{n + 1} (T (i))) = f_{m - 1}^{n + 1} (t (ε)) \cdot^{n} ⨁_{i} f_{m}^{n} (T (i)) = f_{m}^{n} (F) . \end{matrix}$ □
Fact 8.
For all $F \in F_{m} (\bar{k})$ and $G \in F_{m + 1} (\bar{k})$ we have: $s (f_{m}^{n} (F)) = f_{m + 1}^{n} (s (F))$ , $r (f_{m + 1}^{0} (G)) = f_{m}^{0} (r (G))$ , and $e v (r (f_{m + 1}^{n} (G))) \equiv e v (f_{m}^{n} (r (G)))$ for $n > 0$ .
Proof.
The first equality follows from the equality $f_{m + 1}^{n} (s (F))) = f_{m}^{n + 1} (F)$ (which holds by the definition of $f_{m + 1}^{n}$ ) and by the first assertion of Fact 7.

For the second equality it suffices to show that, for every tree $F = (T, t) \in T_{m} (\bar{k})$ , we have $r (f_{m + 1}^{0} (F)) = f_{m}^{0} (r (F))$ , and similarly for the third assertion for every tree $G = (T, t) \in T_{m + 1} (\bar{k})$ . We argue by induction on the rank of T. If T is singleton, i.e. $T = s (V)$ for some $V \in T_{m} (\bar{k})$ then $r (f_{m + 1}^{n} (T)) = r (f_{m}^{n + 1} (V))$ and $f_{m}^{n} (r (T)) = f_{m}^{n} (r (s (V))) = f_{m}^{n} (V)$ , so the equalities hold by Fact 7. If T is not singleton then we have $\begin{array}{l} f_{m}^{n} (r (T)) & = f_{m}^{n} (t (ε) ⊔ ⨆_{i} r (T (i))) = f_{m}^{n} (t (ε)) \oplus ⨁_{i} f_{m}^{n} (r (T (i))) and \\ r (f_{m + 1}^{n} (T)) & = r (f_{m}^{n + 1} (t (ε)) \cdot^{n} ⨁_{i} f_{m + 1}^{n} (T (i))) . \end{array}$ For $n = 0$ the latter expression is equal to $r (f_{m}^{1} (t (ε)) \oplus ⨁_{i} r (f_{m + 1}^{0} (T (i)))$ which, by the second assertion of Fact 7 and by induction hypothesis, is equal to $f_{m}^{0} (t (ε)) \oplus ⨁_{i} f_{m + 1}^{0} (T (i))$ , which is equal to $f_{m}^{0} (r (T))$ by the equality above. For $n > 0$ the expression is equal to $r (f_{m}^{n + 1} (t (ε))) \cdot^{n - 1} ⨁_{i} r (f_{m + 1}^{n} (T (i)))$ and, by Proposition 15(2), we get $\begin{matrix} e v (r (f_{m}^{n + 1} (t (ε))) \cdot^{n - 1} ⨁_{i} r (f_{m + 1}^{n} (T (i))) \equiv^{n} e v (r (f_{m}^{n + 1} (t (ε))) \oplus ⨁_{i} r (f_{m + 1}^{n} (T (i)))) \end{matrix}$ which equals to the $0^{(n)}$ -complete numbering $e v (f_{m}^{n} (r (T)))$ ; this yields the third equality. □

The assignment $f_{m}^{n} (F) \mapsto f_{m + 1}^{n} (s (F))$ defines a multifunction from $B_{m}^{n} = f_{m}^{n} (F_{m} (\bar{k}))$ into $B_{m + 1}^{n}$ which for simplicity is denoted (formally not correctly) also by s. From Fact 8 it follows that s induces a function on the $\equiv^{n}$ -classes. Similarly, let $r : B_{m + 1}^{n} \to B_{m}^{n}$ be the function on $\equiv^{n}$ -classes corresponding to the assignment $f_{m + 1}^{n} (F) \mapsto f_{m}^{n} (r (F))$ . Fact 9.
For all $F, G \in F_{m} (\bar{k})$ and $p < m$ we have:

$f_{m}^{n} (F) ⩽^{n} f_{m}^{n} (G)$ iff $f_{m + 1}^{n} (s (F)) ⩽^{n + 1} f_{m + 1}^{n} (s (G))$ iff $f_{m + 1}^{n} (s (F)) ⩽^{0} f_{m + 1}^{n} (s (G))$ ;

$f_{m}^{n} (F) \cdot^{n + p + 1} f_{m}^{n} (G) \equiv^{n} f_{m}^{n} (s r (F)) \cdot^{n + p + 1} f_{m}^{n} (s r (G))$ ;

$f_{m}^{n} (F) ⩽^{n + p + 1} f_{m}^{n} (G)$ iff $f_{m - 1}^{n} (r (F)) ⩽^{n + p} f_{m - 1}^{n} (r (G))$ .
Proof.
Let $F = T_{0} ⊔ \dots ⊔ T_{q}$ and $G = V_{0} ⊔ \dots ⊔ V_{l}$ be minimal forests decomposed to trees. Then $F ⩽_{h} G$ iff $s (F) ⩽_{h}^{'} s (G)$ iff $s (F) ⩽_{h} s (G)$ by Section 2.3, and $f_{m + 1}^{n} (s (F)) = ⨁_{i} f_{m}^{n + 1} (T_{i})$ and $f_{m + 1}^{n} (s (G)) = ⨁_{j} f_{m}^{n + 1} (V_{j})$ by the definition of $f_{m + 1}^{n} (s (F))$ . Since any $f_{m}^{n + 1} (V_{j})$ is $0^{(n + 1)}$ -complete by Fact 4, the first assertion follows from Proposition 13.

For $n > 0$ the second assertion follows from Fact 6 (because $s (r (f_{m}^{n} (F))) = f_{m}^{n} (F)$ and similarly for G), so let $n = 0$ . Let t and g be the labelings of F and G, resp. By the definition of $f_{m}^{0}$ , $f_{m}^{0} (F)$ (resp. $f_{m}^{0} (G)$ ) is a term of signature ${\oplus, \cdot^{0}}$ from $f_{m - 1}^{1} (t (τ))$ , $τ \in F$ (resp. from $f_{m - 1}^{1} (g (σ))$ , $σ \in G$ ). By items (2) and (12) of Proposition 15, $\begin{matrix} f_{m}^{0} (F) \cdot^{p + 1} f_{m}^{0} (G) \equiv^{0} (⨁_{τ} f_{m - 1}^{1} (t (τ))) \cdot^{p + 1} ⨁_{σ} f_{m - 1}^{1} (g (σ))) . \end{matrix}$ On the other hand, since $s r (f_{m - 1}^{1} (t (τ))) = f_{m - 1}^{1} (t (τ))$ , $s r f_{m}^{0} (F)$ (resp. $s r f_{m}^{0} (G)$ ) is a term of signature ${\oplus}$ from $f_{m - 1}^{1} (t (τ))$ , $τ \in F$ (resp. from $f_{m - 1}^{1} (g (σ))$ , $σ \in G$ ). Therefore, $\begin{matrix} s r (f_{m}^{0} (F)) \cdot^{p + 1} s r (f_{m}^{0} (G)) \equiv^{0} (⨁_{τ} f_{m - 1}^{1} (t (τ))) \cdot^{p + 1} ⨁_{σ} f_{m - 1}^{1} (g (σ))), \end{matrix}$ completing the proof of the second assertion.

By the first assertion, the third assertion follows from: $f_{m}^{n} (F) ⩽^{n + p + 1} f_{m}^{n} (G)$ iff $f_{m}^{n} (s r (F)) ⩽^{n + p + 1} f_{m}^{n} (s r (G))$ . This follows from the argument of the preceding paragraph (for n in place of 0) which shows that $f_{m}^{n} (F) \equiv^{n + p + 1} f_{m}^{n} (s r (F))$ , and similarly for G. □
Fact 10.
For all $F, G \in F_{m} (\bar{k})$ and $p < m$ we have: $f_{m}^{n} (F \cdot^{p} G) \equiv^{n} f_{m}^{n} (F) \cdot^{n + p} f_{m}^{n} (G)$ .
Proof.
We argue by induction on p. For $p = 0$ the assertion holds by Fact 5, so let $p + 1 < m$ and let the assertion hold for $\cdot^{p}$ . Using the functions $s, r$ from Section 2.3, the corresponding functions on $\equiv^{n}$ -classes defined above, Facts 8 and 9, the induction hypothesis, and Proposition 3(2), we obtain: $\begin{array}{l} f_{m}^{n} (F \cdot^{p + 1} G) & = f_{m}^{n} (s (r (F) \cdot^{p} r (G))) \equiv^{n} s (f_{m - 1}^{n} (r (F) \cdot^{p} r (G))) \\ \equiv^{n} s (f_{m - 1}^{n} (r (F)) \cdot^{n + p} f_{m - 1}^{n} (r (G)))) \equiv^{n} s (r (f_{m}^{n} (F)) \cdot^{n + p} r (f_{m}^{n} (G))) \\ \equiv^{n} s (r (f_{m}^{n} (F))) \cdot^{n + p + 1} s (r (f_{m}^{n} (G)))) \equiv^{n} f_{m}^{n} (F) \cdot^{n + p + 1} f_{m}^{n} (G) . \end{array}$ □
Fact 11.
The function $f_{m}^{n}$ induces an isomorphism between the quotient-structure of the structure $(F_{m} (\bar{k}); ⊔, \cdot^{0}, \dots, \cdot^{m - 1}, ⩽^{0}, \dots, ⩽^{m})$ under $\equiv_{h}$ and the quotient-structure of $(A_{k}^{n + m}; \oplus, \cdot^{n}, \dots, \cdot^{n + m - 1}, ⩽^{n}, \dots, ⩽^{n + m})$ under $\equiv^{n}$ .
Proof.
By Fact 5, $f_{m}^{n} : F_{m} (\bar{k}) \to B_{m}^{n}$ is a semilattice embedding of $(F_{m} (\bar{k}); ⊔, ⩽_{h})$ into $(A_{k}; \oplus, ⩽^{n})$ . By the definition of $f_{m}^{n}$ , any $f_{m}^{n} (F)$ is a term of signature ${\oplus, \cdot^{0}, \dots, \cdot^{m - 1}}$ from $i < k$ (in case $m = 0$ the multiplications are absent). By the definition of $f_{m}^{n}$ , any $f_{m}^{n} (F)$ is the value of a variable-free term of signature ${i, \oplus, \cdot^{n}, \dots, \cdot^{n + m - 1} ∣ i < k}$ . By Fact 3, $B_{m}^{n} \subseteq A_{k}^{n + m}$ , i.e. $f_{m}^{n} : F_{m} (\bar{k}) \to A_{k}^{n + m}$ .

We show that $B_{m}^{n} \equiv^{n} A_{k}^{n + m}$ , i.e. $f_{m}^{n}$ is an isomorphism between the quotient-structures of $(F_{m} (\bar{k}); ⊔, ⩽_{h})$ and $(A_{k}^{n + m}; \oplus, ⩽^{n})$ . Let $T_{k}^{n, m}$ be the set of variable-free terms of signature $σ_{k}^{n, m} = {i, \oplus, \cdot^{p} ∣ i < k, n ⩽ p < n + m}$ . Note that $T_{k}^{0, m} = T_{k}^{m}$ and $T_{k}^{n, m} \subseteq T_{k}^{n + m}$ . By Fact 3, it suffices to show that, given $u \in T_{k}^{n + m}$ , one can compute $u^{} \in T_{k}^{n, m}$ with $u \equiv^{n} u^{}$ . We define $u \mapsto u^{}$ by induction on u as follows: $i^{} = i$ for every $i < k$ , ${(u_{1} \oplus u_{2})}^{} = u_{1}^{} \oplus u_{2}^{}$ , ${(u_{1} \cdot^{p} u_{2})}^{} = u_{1}^{} \cdot^{p} u_{2}^{}$ for $p ⩾ n$ , and ${(u_{1} \cdot^{p} u_{2})}^{} = u_{1}^{} \oplus u_{2}^{}$ for $p < n$ . For the first two cases the assertion is clear, so it suffices to check that ${(u_{1} \cdot^{p} u_{2})}^{} \equiv^{n} u_{1}^{} \cdot^{p} u_{2}^{}$ . By induction we have $u_{1} \equiv^{n} u_{1}^{}$ and $u_{2} \equiv^{n} u_{2}^{}$ . For $p ⩾ n$ we get $u_{1}^{} \cdot^{p} u_{2}^{} \equiv^{n} {(u_{1} \cdot u_{2})}^{}$ by items (3) and (5) of Proposition 15. For $p < n$ we have $u_{1}^{} \cdot^{p} u_{2}^{} \equiv^{n} u_{1}^{} \oplus u_{2}^{*} =$ by Proposition 15(2) which imply the desired property.

By Fact 10, the function $f_{m}^{n}$ respects the corresponding multiplications, so it remains to show that it also respects the corresponding preorders. This is by induction on p. The induction base holds by Fact 4. The inductive step follows from the third assertion in Fact 9: $F ⩽^{p + 1} G$ iff $r (F) ⩽^{p} r (G)$ iff $f_{m - 1}^{n} (r (F)) ⩽^{n + p} f_{m - 1}^{n} (r (G))$ iff $f_{m}^{n} (F) ⩽^{n + p + 1} f_{m}^{n} (G)$ . □

5.3. Main results

Here we apply the results of the previous subsection to deduce basic facts about the EWH of k-partitions in $N$ .

Theorem 18.
For any $T \in T_{ω} (\bar{k})$ we have $Σ (N, T) = {B \in k^{ω} ∣ B ⩽ f (T)}$ , i.e. $f (T)$ is complete in $Σ (N, T)$ w.r.t. the reducibility of numberings ⩽.
Proof.
It suffices to show that for any $n ⩾ 0$ and any normal $T \in T_{m} (\bar{k})$ we have $L^{n} (N, T) = {B ∣ B ⩽ f_{m}^{n} (T)}$ . Since the base $L = {Σ_{1 + n}^{0} (N)}$ is reducible, by Proposition 6(2) it suffices to check the equality with red- $L^{n} (N, T)$ in place of $L^{n} (N, T)$ . By induction on m we show that the equality holds for all n and T. For $m = 0$ the equality holds because both of its parts coincide with ${i}$ where $T = i < k$ . It remains to consider the case $(T, t) \in T_{m + 1} (\bar{k})$ , assuming the assertion to hold for m.

If T is singleton then $f_{m + 1}^{n} = f_{m}^{n + 1}$ and, by the definition of FH in Section 3, $L^{n} (N, T) = L^{n + 1} (N, t (ε))$ which implies the equality. If T is non-singleton and $p > 0$ satisfies $ω \cap T = {i ∣ i < p}$ then $f_{m + 1}^{n} (T) = f_{m}^{n + 1} (t (ε)) \cdot^{n} (⨁_{i < p} f_{m + 1}^{n} (T (i)))$ . For abbreviation, we denote $A = f_{m + 1}^{n} (T)$ , $ν = f_{m}^{n + 1} (t (ε))$ , and $μ = ⨁_{i < p} μ_{i}$ where $μ_{i} = f_{m + 1}^{n} (T (i))$ ; thus, we have to show $L^{n} (N, T) = {B ∣ B ⩽ A}$ . By induction on the rank of T, ν is complete in $L^{n + 1} (N, t (ε))$ and $μ_{i}$ is complete in $L^{n} (N, T (i))$ for every $i < p$ . By the definition of $\cdot^{n}$ in Section 5.2 and Definition 14 we have: if $φ (r (x)) ↑$ then $A (x) = ν (l (x))$ else $A (x) = μ φ (r (x))$ , where $φ = {\tilde{ϰ}}^{0^{(n)}}$ .

We first check that $A \in L^{n} (N, T)$ . Let $V = {x ∣ y = φ (r (x)) ↓}$ and $V_{i} = {x ∣ rest (y, p) = i}$ for every $i < p$ . Then $V = V_{0} \cup \dots \cup V_{p - 1}$ and $V_{i}$ are pairwise disjoint $Σ_{n + 1}^{0}$ -sets, hence $A = A |_{\overline{V}} \cup A |_{V_{0}} \cup \dots \cup A |_{V_{p - 1}}$ . For $x \in \overline{V}$ we have $A (x) = ν (l (x))$ , hence $A |_{\overline{V}} = (ν \circ l) |_{\overline{V}}$ by Proposition 6(5). Since $ν \in L^{n + 1} (N, t (ε))$ , we have $ν \circ l \in L^{n + 1} (N, t (ε))$ by Proposition 6(5), hence $A |_{\overline{V}} \in L^{n + 1} (\overline{V}, t (ε))$ by Proposition 6(3). Since any $μ_{i}$ , $i < p$ , is a $0^{(n)}$ -complete numbering and $φ \circ r$ is a $0^{(n)}$ -c.p. function, $φ \circ r$ has a computable $μ_{i}$ -totalizer $g_{i}$ . Thus, $A (x) = μ_{i} (g_{i} (x))$ for each $x \in V_{i}$ . Arguing as above and taking into account that $μ_{i} \in L^{n} (N, T (i))$ , we deduce that $A |_{V_{i}} \in L^{n} (V_{i}, T (i))$ . By Proposition 6(4), $A \in L^{n} (N, T)$ . By Proposition 6(5), $L^{n} (N, T) \supseteq {B ∣ B ⩽ A}$ .

It remains to check that any $B \in$ red- $L^{n} (N, T)$ is reducible to A. Let B be determined by a reduced T-family $({U_{τ_{0}}}, {F_{τ_{0}}})$ in $L^{n} (N)$ . By Proposition 6(3), $B |_{\overline{U}} \in L^{n + 1} (\overline{U}, t (ε))$ and $B |_{U_{i}} \in L^{n} (U_{i}, T (i))$ for each $i < p$ , where $U = U_{0} \cup \dots \cup U_{p - 1}$ . By induction, $B |_{\overline{U}} ⩽ ν$ and $B |_{U_{i}} ⩽ μ_{i}$ for each $i < p$ ; let g and $g_{i}$ be corresponding computable reductions. Let $h (x) = ⟨ g (x), v (x) ⟩$ where v is a computable function such that $φ (v (x)) ↑$ for $x \notin U$ and $φ (v (x)) = p \cdot g_{i} (x) + i$ for $x \in U_{i}$ , $i < p$ . Then h is a computable reduction of B to A. □

Theorem 18, Fact 4, and Proposition 8(3) immediately imply the following result.
Theorem 19.
The EWH ${Σ (N, T)}_{T \in T_{ω} (\bar{k})}$ strongly does not collapse.

Since $N$ is discrete, the WH ${Σ (N, T)}$ collapses to very low levels (in fact, it has finitely many distinct levels), the formulation of Theorem 19 cannot be improved to the strong uniform version.

Fact 11 and Proposition 4 imply the following interesting result:
Corollary 20.

The function $f^{n}$ induces an isomorphism between the quotient-structure of the structure $(F_{ω} (\bar{k}); ⊔, \cdot^{0}, \cdot^{1}, \dots, ⩽^{0}, ⩽^{1}, \dots)$ under $\equiv_{h}$ and the quotient-structure of $(A_{k}; \oplus, \cdot^{n}, \cdot^{n + 1}, \dots, ⩽^{n}, ⩽^{n + 1}, \dots)$ under $\equiv^{n}$ .

The function $f = f^{0}$ induces an isomorphism between the quotient-structure of $(F_{ω} (\bar{k}); ⊔, \cdot^{0}, \cdot^{1}, \dots, ⩽^{0}, ⩽^{1}, \dots)$ under $\equiv_{h}$ and the quotient-structure of $(A_{k}; \oplus, \cdot^{0}, \cdot^{1}, \dots, ⩽^{0}, ⩽^{1}, \dots)$ under ≡.

The quotient-semilattices of $(A_{k}; \oplus, ⩽)$ and $(F_{ω} (\bar{k}); ⊔, ⩽_{h})$ are isomorphic.

The next corollary would be hard to prove without the established isomorphisms.
Corollary 21.

The quotient-structure of $(A_{k}; \oplus, \cdot^{0}, \cdot^{1}, \dots, I, ⩽^{0}, ⩽^{1}, \dots)$ under ≡ is computably presentable, where I is the unary relation which is true precisely on the join-irreducible elements of $(A_{k}; \oplus, ⩽^{0})$ .

All the quotient-semilattices of $(A_{k}; \oplus, ⩽^{n})$ , $n < ω$ , are isomorphic to each other, and are computably presentable.

Proof.
(1) For the signature ${\oplus, \cdot^{0}, \cdot^{1}, \dots, ⩽^{0}, ⩽^{1}, \dots}$ without I, the assertion follows from the previous theorem and the easy fact that the structure $(F_{ω} (\bar{k}); ⊔, \cdot^{0}, \cdot^{1}, \dots, ⩽^{0}, ⩽^{1}, \dots)$ is computably presentable. For the whole signature, it suffices to check that the corresponding relation I of the iterated k-forests is computable. This follows from the remarks about minimal forests after Proposition 2 and at the end of Section 2.3.

(2) The isomorphism follows from Fact 11 because all semilattices are isomorphic to the quotient-semilattice of $(F_{ω} (\bar{k}); ⊔, ⩽_{h})$ . The computable presentability follows from (1). □

The structure $({Σ (N, T) ∣ T \in T_{ω} (\bar{k})}; \subseteq)$ (that is isomorphic to the quotient-poset of $(T_{ω} (\bar{k}); ⩽_{h})$ ) is rather complicated for $k ⩾ 3$ and very easy (isomorphic to $\bar{2} \cdot ε_{0}$ ) for $k = 2$ . It makes sense to look for a natural substructure of $({Σ (N, T) ∣ T \in T_{ω} (\bar{k})}; \subseteq)$ similar to the structure of levels of the FH of sets. In fact, this substructure was identified already in [27]. We briefly recall it below.

In the terminology of the present paper, it looks as $({Σ (N, T_{α, i}) ∣ i < k, α < ε_{0}}; \subseteq)$ where $T_{α, i} = T_{α, i}^{0}$ and $T_{α, i}^{n} \in T_{ω} (\bar{k})$ ( $n < ω, i < k, α < ε_{0}$ ) are defined by induction on α as follows: $T_{0, i}^{n} = i$ ; $T_{ω^{γ}, i}^{n} = T_{γ, i}^{n + 1}$ for $γ > 0$ ; $T_{β + 1, i}^{n} = i \cdot ⨆_{j < k} T_{β, j}^{n}$ for all $β < ε_{0}$ , and $T_{β + ω^{γ}, i}^{n} = T_{ω^{γ}, i}^{n} \cdot (⨆_{j < k} T_{β, j}^{n})$ for $γ > 0$ and β of the form $β = ω^{γ} \cdot β_{1} > 0$ .
5.4. Additional remarks

For the sake of completeness, in this subsection we briefly mention some recent results which concern two aspects of the FH of arithmetical k-partitions.

The first aspect is about possible improvements of Corollary 21. Since the structures in Corollary 21 are computably presentable, it is natural to look for easier (say, polynomial-time) presentations of these structures, or, equivalently, of the isomorphic structures of iterated k-labeled forests. This issue was first addressed in [13] and recently developed in [2]. In particular, the following fact was established. For any $n < ω$ , let $I_{n}$ be the unary relation on $F_{ω} (\bar{k})$ true precisely on the elements which induce join-irreducible elements in the quotient semilattice of $(F_{ω} (\bar{k}); ⊔, ⩽^{n})$ .

Theorem 22 ([2]).

The structure $(F_{ω} (\bar{k}); ⊔, ⩽_{h})$ has a polynomial-time presentation in which the relations $I_{n}, ⩽^{n}$ and the operations $\cdot^{n}$ from Section 2.3 are polynomial-time computable for every n.

Surprisingly, the presentation in [2] uses a very natural coding and is really feasible (in fact, the structure in the latter theorem is in fact presentable in cubic time, and all the mentioned functions and relations are also computable in cubic time w.r.t. this presentation).

The next immediate corollary of the latter theorem considerably improves Corollary 21. For any $n < ω$ , let $I_{n}$ be the unary relation on $A_{k}$ true precisely on the elements which induce join-irreducible elements in the quotient semilattice of $(A_{k}; \oplus, ⩽^{n})$ .

Corollary 23.
The structure $(A_{k}; \oplus, ⩽)$ has a polynomial-time presentation in which the relations $I_{n}, ⩽^{n}$ and the operations $\cdot^{n}$ are polynomial-time computable for every n.

The second aspect is about possible improvements of the non-collapse property from Theorem 19. Restricted to the FH of arithmetical sets ${Σ_{α}}_{α < ε_{0}}$ , this theorem states that any non-zero level of this hierarchy is proper w.r.t. m-reducibility, i.e., it contains a set (namely, the m-complete set in this level) which is not m-equivalent to sets from all lesser levels. In this context Turing reducibility is of course more interesting, but observe that the m-complete sets do not witness the properness w.r.t. Turing equivalence. The precise formulation of this question is: characterise the levels of the FH which are proper w.r.t. Turing equivalence.

This question remained open for many years (except the well known Turing properness of all levels $Σ_{n} = Σ_{n}^{- 1}$ , $n < ω$ , of the Ershov hierarchy). Only recently new non-trivial results were obtained in [36,37]. Namely, the Turing properness of several levels from $Δ_{3}^{0} ∖ Δ_{2}^{0}$ (i.e., for $ω < α < ω^{ω}$ ) was proved, and a plausible conjecture describing the Turing proper levels was formulated.

Recently the authors of [36,37] have completely characterised the Turing proper levels from $Δ_{3}^{0}$ , confirming the conjecture from [36] for such levels (these results are still unpublished). This extends the facts about Turing properness of the Ershov hierarchy and suggests, in my opinion, the “right” way to extend the local Turing degree theory from $Δ_{2}^{0}$ to $Δ_{3}^{0}$ . Along with the FH, the concept of CEA-degrees seems fundamental for such an extension of the local theory.

In [20], using a more involved proof, it was shown that the level $Σ_{ω^{ω} + 2}$ is Turing proper which is the first step beyond $Δ_{3}^{0}$ , but the complete solution of the Turing properness problem is not yet achieved.
6. EWH in some other spaces

In this section we illustrate the method of Proposition 11 by proving the non-collapse of EWH and WH in some other concrete spaces.

We start with observing that Theorem 19 implies the non-collapse of EWH in some spaces, e.g.:

Corollary 24.
Let $X = X_{0} ⊔ X_{1} ⊔ \dots$ be the disjoint union of a uniform sequence ${X_{n}}$ of nonempty effective cb ₀ -spaces. Then the EWH ${Σ (X, T)}$ strongly does not collapse.
Proof.
For $x \in X$ , let $g (x)$ be the unique number n with $x \in X_{n}$ . Then $g : X \to N$ is a computable effectively open surjection. By Theorem 11 and Proposition 12, ${Σ (X, T)}$ strongly does not collapse. □

In particular, Corollary 24 applies to $N ≃ N ⊔ N ⊔ \dots$ which shows that ${Σ (N, T)}$ strongly does not collapse. The properties of witnesses for strong non-collapse obtained in this way have very low topological complexity: e.g., the witnesses for the Baire space are clopen (a k-partition A is clopen if $A^{- 1} (i)$ is clopen for each $i < k$ ). Therefore, these witnesses cannot be used to show the strongly uniform non-collapse property of the EWH in $N$ . We conclude the paper by showing the strongly uniform non-collapse of the EWHs in some spaces related to $N$ . These results follow easily from the results in [17] by observing that their effective versions hold.

First we consider the domain $ω^{⩽ ω}$ . For this space, the result is obtained by some observations and additions to the proofs in [17], so let us recall some information from that paper. Let $\hat{ω} = ω \cup {p}$ be obtained from ω by adjoining a new element p; we endow $\hat{ω}$ with the discrete topology. For $x \in {\hat{ω}}^{ω}$ , let $δ (x) \in ω^{⩽ ω}$ be obtained from x by deleting all entries of $p$ . A function $f : {\hat{ω}}^{ω} \to {\hat{ω}}^{ω}$ (resp. $A : {\hat{ω}}^{ω} \to \bar{k}$ ) is conciliating if $δ \circ f = f^{} \circ δ$ (resp. $A = A^{} \circ δ$ ) for some (unique) $f^{} : ω^{⩽ ω} \to ω^{⩽ ω}$ (resp. $A^{} : ω^{⩽ ω} \to \bar{k}$ ). The function f is initializable if, for every $τ \in {\hat{ω}}^{< ω}$ , there is a continuous function $h_{τ} : {\hat{ω}}^{ω} \to {\hat{ω}}^{ω}$ such that $δ (f (x)) = δ (f (τ h_{τ} (x)))$ for all $x \in {\hat{ω}}^{ω}$ . In Proposition 2.15 from [17], an initializable $Σ_{2}^{0}$ -measurable conciliating function $U : {\hat{ω}}^{ω} \to {\hat{ω}}^{ω}$ was constructed which is universal in the sense that for every $Σ_{2}^{0}$ -measurable conciliating function $V : {\hat{ω}}^{ω} \to {\hat{ω}}^{ω}$ there is a continuous function $h : {\hat{ω}}^{ω} \to {\hat{ω}}^{ω}$ such that $δ \circ V = δ \circ U \circ h$ .
Theorem 25.

The WH ${Σ (ω^{⩽ ω}, T)}_{T \in T_{ω} (\bar{k})}$ strongly does not collapse. Similarly for the infinitary WH.

The EWH ${Σ (ω^{⩽ ω}, T)}_{T \in T_{ω} (\bar{k})}$ strongly uniformly does not collapse.

Proof.
(1) For notation simplicity, we only consider the finitary case, in the infinitary case the argument is the same. The Definition 3.1.4 in [17], using the induction on trees and the universal function $U$ , associates with any tree T a conciliating $Ω_{T} : {\hat{ω}}^{ω} \to \bar{k}$ . By the results in Section 3.3 of [17], $Ω_{T}$ is in $Σ ({\hat{ω}}^{ω}, T) ∖ ⋃ {Σ ({\hat{ω}}^{ω}, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ . As the function δ is a continuous open surjection and $Ω_{T} = Ω_{T}^{} \circ δ$ , we get $Ω_{T}^{} \in Σ (ω^{⩽ ω}, T) ∖ ⋃ {Σ (ω^{⩽ ω}, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ by Proposition 7, completing the proof.

(2) Inspecting the proof of Proposition 2.15 (resp. Lemma 2.11) in [17] shows that $U$ and $U^{}$ are in fact $Σ_{2}^{0}$ -measurable. Inspecting the proof of Lemma 2.15 in [17] shows that $Ω_{T}$ is in $Σ ({\hat{ω}}^{ω}, T)$ . Clearly, δ is a computable effectively open surjection. Thus, $Ω_{T}^{}$ is in $Σ (ω^{⩽ ω}, T) ∖ ⋃ {Σ (ω^{⩽ ω}, V) ∣ V \in T_{ω} (\bar{k}), T ≰_{h} V}$ by Proposition 7, completing the proof. □

This theorem and Proposition 12 imply some new information on the EWH in Baire and Cantor spaces: Theorem 26.
The EWHs ${Σ (N, T)}$ and ${Σ (C, T)}_{T \in T_{ω} (\bar{k})}$ strongly uniformly do not collapse.
Proof.
As δ is a computable effectively open surjection, ${Σ ({\hat{ω}}^{ω}, T)}$ strong uniformly does not collapse by Theorem 25 and Proposition 11. As ${\hat{ω}}^{ω}$ is effectively homeomorpic to $N$ , the first assertion follows.

For the second assertion, consider the Cantor domain $n^{⩽ ω}$ , $n ⩾ 2$ , in place of $ω^{⩽ ω}$ . A slight modification of the notions from the beginning of this section apply to $n^{⩽ ω}$ . Also, a slight modification of the proof of Theorem 25 shows that it remains true for $n^{⩽ ω}$ . As in the previous paragraph, ${Σ ({\hat{n}}^{ω}, T)}$ strong uniformly does not collapse. Since ${\hat{n}}^{ω}$ is effectively homeomorpic to ${(n + 1)}^{ω}$ , and thus to $C$ , this implies the second assertion. Note that the spaces $n^{⩽ ω}$ for distinct n are not homeomorphic. □

7. Conclusion

In this paper we suggested notions and developed tools to study the non-collapse property of the (effective) Wadge hierarchy in (computable) quasi-Polish spaces. We also established the non-collapse of this hierarchy in some concrete spaces. Since the Wadge hierarchy subsumes many other natural hierarchies, our methods and results also apply to these hierarchies.

Unfortunately, our results and methods do not directly apply to many concrete important spaces, e.g. to the Scott domain $P ω$ and to the intervals of $R$ . Not surprisingly, proving the non-collapse of the (effective) Wadge hierarchy in these and many other spaces of interest heavily depends on the topology of a concrete space. Nevertheless, we hope that the methods and results of this paper suggest how one could attempt to attack the non-collapse problems in concrete important spaces.

Recently, some new interesting results about the structure of Wadge degrees in $P ω$ were obtained in [9,38]. Although the structure of Wadge degrees in non-zero-dimensional spaces is typically much more complicated than the structure of Wadge hierarchy, its study seems to be interesting and rewarding. The structure of effective Wadge degrees is complicated even in zero-dimensional spaces, and it was not investigated in the literature until recently (except the structure of m-degrees of sets of natural numbers which is well studied in the classical computability theory). In [22] some basic facts about the effective Wadge degrees in the Baire space were obtained. A similar study for other natural spaces seems also interesting.

Especially interesting and relevant to the classical computability theory is the problem of characterising the levels of the fine hierarchy of arithmetical sets which are proper w.r.t. Turing equivalence (see Section 5.4 for more details).

Footnotes

Acknowledgements

I am grateful to the anonymous referees for the careful reading and many helpful suggestions which certainly improved the text.

The work of V. Selivanov is supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. This work is a journal version of the conference paper [] which is essentially extended by adding precise definitions, proofs of auxiliary facts, and complete proofs of the main technical results.

References

Abramsky and

Jung, Domain theory, in: Handbook of Logic in Computer Science , Vol. 3, Oxford, 1994, pp. 1–168.

P.E.

Alaev and

V.L.

Selivanov, Complexity issues for the iterated h-preorders, in: DCFS 2021 ,

Y.-S.

Han and

S.-K.

Ko, eds, LNCS, Vol. 13037, 2021, pp. 1–12.

Becher and

Grigorieff, Borel and Hausdorff hierarchies in topological spaces of Choquet games and their effectivization, Mathematical Structures in Computer Science 25(7) (2015), 1490–1519. doi:10.1017/S096012951300025X.

Becher and

Grigorieff, Wadge hardness in Scott spaces and its effectivization, Mathematical Structures in Computer Science 25(7) (2015), 1520–1545. doi:10.1017/S0960129513000248.

Brattka, Effective Borel measurability and reducibility of functions, Mathematical Logic Quarterly 51(1) (2005), 19–44. doi:10.1002/malq.200310125.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability ,

Brattka and

Hertling, eds, Springer, Cham, 2021, pp. 367–417. doi:10.1007/978-3-030-59234-9_11.

de Brecht, Quasi–Polish spaces, Annals of pure and applied logic 164 (2013), 356–381. doi:10.1016/j.apal.2012.11.001.

de Brecht,

Pauly and

Schröder, Overt choice, Computability 9(3–4) (2020), 169–191. doi:10.3233/COM-190253.

Duparc and

Vuilleumier, The Wadge order on the Scott domain is not a well-quasi-order, The Journal of Symbolic Logic 85(1) (2020), 300–324. doi:10.1017/jsl.2019.51.

10.

Ershov Yu, in: Theory of Numberings , Moscow, Nauka, 1977, (in Russian).

11.

Hemmerling, The Hausdorff–Ershov hierarchy in Euclidean spaces, Arch. Math. Logic 45 (2006), 323–350. doi:10.1007/s00153-005-0317-8.

12.

Hertling, Forests describingWadge degrees and topological Weihrauch degrees of certain classes of functions and relations, Computability 9(3–4) (2020), 249–307. doi:10.3233/COM-190255.

13.

Hertling and

V.L.

Selivanov, Complexity issues for preorders on finite labeled forests, in: Logic, Computation, Hierarchies ,

Brattka,

Diener and

Spreen, eds, Ontos Publishing, de Gruiter, Boston-Berlin, 2014, pp. 165–190. doi:10.1515/9781614518044.165.

14.

Hoyrup,

Rojas,

Selivanov and

Stull, Computability on quasi-Polish spaces, in: Proc. of DCFS-2019 , LNCS, Vol. 11612, Springer, Berlin, 2019, pp. 171–183.

15.

A.S.

Kechris, Classical Descriptive Set Theory , Graduate Texts in Mathematics, Vol. 156, Springer, New York, 1995.

16.

Kihara and

Montalbán, The uniform Martin’s conjecture for many-one degrees, Trans. Amer. Math. Soc. 370(12) (2018), 9025–9044. doi:10.1090/tran/7519.

17.

Kihara and

Montalbán, On the structure of the Wadge degrees of bqo-valued Borel functions, Trans. Amer. Math. Soc. 371(11) (2019), 7885–7923. doi:10.1090/tran/7621.

18.

Louveau, Recursivity and compactness, in: Higher Set Theory ,

G.H.

Muller and

D.S.

Scott, eds, Lecture Notes in Mathematics, Vol. 669, Springer, Heidelberg, 1978, pp. 303–337. doi:10.1007/BFb0103106.

19.

A.I.

Mal’cev, Algorithms and Recursive Functions , Groningen, Wolters–Noordhoff, 1970.

20.

A.G.

Melnikov,

V.L.

Selivanov and

M.M.

Yamaleev, Turing reducibility in the fine hierarchy, Annals of Pure and Applied Logic171(7) (2020). doi:10.1016/j.apal.2019.102766.

21.

Y.N.

Moschovakis, Descriptive Set Theory , North Holland, Amsterdam, 2009.

22.

Motto Ros, Bad Wadge-like reducibilities on the Baire space, Fundamenta Mathematicae 224(1) (2014), 67–95. doi:10.4064/fm224-1-4.

23.

Pequignot, A Wadge hierarchy for second countable spaces, Archive for Mathematical Logic 54.5–6 (2015), 659–683. doi:10.1007/s00153-015-0434-y.

24.

RogersJr., Theory of Recursive Functions and Effective Computability , McGraw-Hill, New York, 1967.

25.

Selivanov, Non-collapse of the effective Wadge hierarchy, De Mol 12813 (2021), 407–416.

26.

Selivanov, A Q-Wadge hierarchy in quasi-Polish spaces, The Journal of Symbolic Logic 87(2) (2022), 732–757. doi:10.1017/jsl.2020.52.

27.

V.L.

Selivanov, Hierarchies of hyperarithmetical sets and functions, Algebra and Logic 22 (1983), 473–491. doi:10.1007/BF01978879.

28.

V.L.

Selivanov, Fine hierarchies of arithmetical sets and definable index sets, Trudi Mat. Inst. SO AN USSR 12 (1989), 165–185, (Russian).

29.

V.L.

Selivanov, Fine hierarchies and m-reducibilities in theoretical computer science, Theoretical Computer Science 405 (2008), 116–163. doi:10.1016/j.tcs.2008.06.031.

30.

V.L.

Selivanov, Fine hierarchies via Priestley duality, Annals of Pure and Applied Logic 163 (2012), 1075–1107. doi:10.1016/j.apal.2011.12.029.

31.

V.L.

Selivanov, Towards the effective descriptive set theory, in: Proc. CiE 2015 , LNCS, Vol. 9136, Springer, Berlin, 2015, pp. 324–333.

32.

V.L.

Selivanov, Towards a descriptive theory of cb₀-spaces, Mathematical Structures in Computer Science. 28(8) (2017), 1553–1580, Earlier version:

arXiv:1406.3942v1

[Math.GN] 16 June 2014.

33.

V.L.

Selivanov, Extending Wadge theory to k-partitions, in: CiE 2017 ,

Kari,

Manea and

Petre, eds, LNCS, Vol. 10307, Springer, Berlin, 2017, pp. 387–399.

34.

V.L.

Selivanov, Q-Wadge degrees as free structures, Computability 9 (2020), 327–341. doi:10.3233/COM-180241.

35.

V.L.

Selivanov, Effective Wadge hierarchy in computable quasi-Polish spaces, Siberian Electronic Mathematical Reports 18(1) (2021), 121–135, arXiv:1910.13220v2. doi:10.33048/semi.2021.18.010.

36.

V.L.

Selivanov and

M.M.

Yamaleev, Turing degrees in refinements of the arithmetical hierarchy, Algebra and Logic 57(3) (2018), 222–236. doi:10.1007/s10469-018-9495-4.

37.

V.L.

Selivanov and

M.M.

Yamaleev, Extending Cooper’s theorem to

Δ_{3}^{0}

Turing degrees, Computability 7 (2018), 289–300. doi:10.3233/COM-180085.

38.

Vuilleumier, Continuous Reductions on the Scott Domain and Decomposability Conjecture, PhD Thesis, University of Lausanne and University of Paris, 2021.

39.

Wadge, Reducibility and Determinateness in the Baire Space, PhD thesis, University of California, Berkely, 1984.

40.

Weihrauch, Computable Analysis , Springer, Berlin, 2000.