Forests describing Wadge degrees and topological Weihrauch degrees of certain classes of functions and relations

Abstract

We introduce notions of continuous strong Weihrauch reducibility and of continuous Weihrauch reducibility for functions with range in a preordered set. Then we associate with such functions certain labeled forests and trees and show that Wadge reducibility, continuous strong Weihrauch reducibility and continuous Weihrauch reducibility between such functions can be characterized by suitable reducibility relations between the associated forests when they are defined. This leads to a combinatorial description of the initial segments of these three hierarchies for those functions defined on the Baire space that have countable range in a bqo set and that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on the bqo set. Furthermore, we show that the characterization of the topological reducibility relations for bqo-valued functions can be used in order to obtain a similar characterization for the usual Wadge reducibility relation, the continuous strong Weihrauch reducibility relation, and the continuous Weihrauch reducibility relation for multi-valued functions with finite range.

Keywords

Relations Wadge reducibility continuous strong Weihrauch reducibility continuous Weihrauch reducibility labeled forests better-quasi-orders

1. Introduction

Reducibility relations are natural tools for comparing computational problems with respect to their computational complexity. In this article three topological reducibility relations are considered. They are

Wadge reducibility,

continuous strong Weihrauch reducibility, and

continuous Weihrauch reducibility

Wadge reducibility was introduced by Wadge in his thesis [24] for subsets of the Baire space

N^{N}

. Van Engelen, Miller, and Steel [22] extended it to functions defined on the Baire space and with range in a better-quasi-ordered set (bqo set). We will consider it on the one hand in this setting. On the other hand we will use the theory of represented spaces due to Weihrauch and Kreitz [13] and extended by Schröder [17] in order to introduce and study a natural Wadge reducibility relation for relations whose domain is a subset of a represented space. The notion of admissible representations [13,17] then leads to a natural Wadge reducibility relation for relations whose domain is a subset of a

{qcb}_{0}

-space. Weihrauch reducibility was introduced by Weihrauch in the late 1980s [25,26] (see also the thesis [23] supervised by Weihrauch) for sets of functions between products of the Cantor space and a discrete space. Independently, Hirsch [10] gave a similar definition for functions between arbitrary topological spaces. Gherardi and Marcone [4] suggested a computability-theoretic version of Weihrauch reducibility, defined via admissible representations. Recently, the computability-theoretic Weihrauch reducibility relation and also a stronger version, called strong Weihrauch reducibility, have received a lot of attention; for an overview see Brattka, Gherardi, and Pauly [2]. We will consider continuous versions of these two reducibility relations in the same settings as Wadge reducibility. So, on the one hand, we will consider continuous reducibility relations between relations

R \subseteq X \times Y

whose domain and range are subsets of represented spaces X and Y, and on the other hand, we will consider them for functions

f : \subseteq N^{N} \to Y

, where Y is a preorder. The case where Y is a bqo set will be particularly important.

In his PhD thesis [6–8] the author considered functions that are defined on a subset of the Baire space and that have finite discrete range (one may call them partial k-partitions if k is an upper bound for the cardinality of the range) and described the finite initial segments of the three continuous reducibility hierarchies of such functions. For the description he used certain trees that describe the discontinuities of such functions and three suitable reducibility relations between forests consisting of such trees. The result for Wadge reducibility of partial k-partitions was extended by Selivanov first to all $Δ_{2}^{0}$ -measurable k-partitions [18], later to all $Δ_{3}^{0}$ -measurable k-partitions [19], and recently by Kihara and Montalbán to all Borel measurable functions $f : N^{N} \to Y$ where Y is any bqo set [12].

In this article the results from [6–8] are extended to $Σ_{2}^{0}$ -measurable functions $f : \subseteq N^{N} \to Y$ , where Y is any bqo set and where on Y we consider the reverse Alexandroff topology in which the open subsets are exactly the downwards closed subsets. We suggest definitions of continuous strong Weihrauch reducibility and of continuous Weihrauch reducibility on the set of functions $f : \subseteq N^{N} \to Y$ where Y is any preorder. We also consider Wadge degrees. We show that, if Y is a bqo and sometimes even if Y is not a bqo, with such functions one can associate certain labeled trees and forests that describe the discontinuities of the function. We introduce three reducibility relations between such forests and show that the three continuous reducibility relations between $Σ_{2}^{0}$ -measurable functions $f : \subseteq N^{N} \to Y$ (where Y is a bqo) are described exactly by the three reducibility relations between the forests associated with the functions. In fact, the equivalence between the reducibility relations between function $f : \subseteq N^{N} \to Y$ on the one hand and the reducibility relations between the forests associated with the functions on the other hand is true whenever the forests are defined. The assumption that Y is a bqo is needed only in order to guarantee that these forests are defined and not used otherwise. We will present some examples of functions $f : \subseteq N^{N} \to Y$ where the forests are defined although Y is not a bqo.

Furthermore, we show that using the theory of admissible representations one can transfer these observations to relations (also known as multi-valued functions) $R : \subseteq X \times Y$ where X is any ${qcb}_{0}$ -space and where Y is any finite space (in the case of Weihrauch reducibility we assume that Y is a finite discrete space). An additional useful observation is that for a relation $R \subseteq X \times Y$ where X is a second countable $T_{0}$ -space the forests that describe the discontinuities of R can be defined directly in terms of R only, without any use of any admissible representation.

In the following sections we introduce some notation and some notions that we will need, many of them well-known, and some of them perhaps not that well-known. Then, in Section 4 we give general definitions of Wadge reducibility, of continuous strong Weihrauch reducibility and of continuous Weihrauch reducibility for relations $R \subseteq X \times Y$ where X and Y are represented spaces (in the case of Wadge reducibility Y can be an arbitrary set). In Section 5 we introduce corresponding continuous reducibility notions for functions $f : \subseteq X \to Y$ where X is a topological space and where Y is an arbitrary preorder. Section 6 contains a short summary of the needed notions and results from bqo theory. In Section 7 we introduce labeled trees and forests and suitable reducibility relations on them. In Section 8 we consider functions $f : \subseteq X \to Y$ where X is a second-countable topological space, where Y is a preorder, and where f has countable range. With such functions we associate certain labeled trees and forests. They do not have to be defined always, but we show that they are guaranteed to be defined if Y is a bqo. We also make some useful observations about these trees and forests. Section 9 contains the results concerning the equivalence of the reducibility relations between certain functions with range in a preordered set on the one hand and of corresponding reducibility relations between the associated forests (if they are defined) on the other hand. In Section 10 we show that the results of Section 9 imply isomorphisms between, on the one hand, the three degree structures of $Σ_{2}^{0}$ -measurable functions $f : N^{N} \to Y$ where Y is a bqo and where $Σ_{2}^{0}$ -measurability is meant with respect to the reverse Alexandroff topology on Y and, on the other hand, three corresponding degree structures of certain forests with labels in Y. In Section 11 the results from Section 9 and the theory of admissible representations are used in order to obtain similar results for multi-valued functions that are defined on a ${qcb}_{0}$ -space and that have finite range. Finally, in Section 12 we formulate several open questions.

2. Sets, relations, and functions

2.1. Sets

For a set X we denote by $P (X)$ the power set of X, that is, the set of all subsets of X: $\begin{matrix} P (X) : = {M : M \subseteq X} . \end{matrix}$ We will also need: $\begin{matrix} P {(X)}_{\neq \emptyset} : = {M : M \subseteq X and M \neq \emptyset} . \end{matrix}$

2.2. Relations and functions

Let X and Y be sets. Then $X \times Y$ is the set of all ordered pairs $(x, y)$ with $x \in X$ and $y \in Y$ . A subset $R \subseteq X \times Y$ is called a binary relation or simply a relation and sometimes a multivalued function; see Section 2.8. In the case $X = Y$ the relation R is called a relation on X. Let $R \subseteq X \times Y$ be a relation. For $M \subseteq X$ we write $R [M] : = {y \in Y : (\exists x \in M) (x, y) \in R}$ . For $x \in X$ we write $R [x] : = R [{x}]$ . The set $\begin{matrix} dom (R) : = {x \in X : (\exists y \in Y) (x, y) \in R} = {x \in X : R [x] \neq \emptyset} \end{matrix}$ is called the domain of R. The set $\begin{matrix} range (R) : = {y \in Y : (\exists x \in X) (x, y) \in R} = R [X] = ⋃_{x \in X} R [x] \end{matrix}$ is called the range of R.

The relation $R^{- 1} \subseteq Y \times X$ is defined by $R^{- 1} : = {(y, x) \in Y \times X : (x, y) \in R}$ . In case R is a relation on a set X and written ⩽, then instead of $⩽^{- 1}$ we write ⩾.

If S is a subset of X then the restriction $R |_{S}$ of R to S is defined by $R |_{S} : = R \cap (S \times Y)$ . Similarly, if T is a subset of Y then the restriction $R |^{T}$ of R to T is defined by $R |^{T} : = R \cap (X \times T)$ . Finally, if R is a relation on a set X and if $S \subseteq X$ then we write $R | S$ for $R \cap (S \times S)$ .

A relation $R \subseteq X \times Y$ is a function iff, for all $x \in dom (R)$ , the set $R [x]$ contains exactly one element. If R is a function and $x \in dom (R)$ then we write $R (x)$ for the unique element of $R [x]$ . If R is a function we usually write $R : \subseteq X \to Y$ . If R is a function with $dom (R) = X$ then we call R a total function and may omit the symbol ⊆, thus, then we may write $R : X \to Y$ . For example, the identity on X is the total function ${id}_{X} : X \to X$ defined by ${id}_{X} (x) : = x$ , for all $x \in X$ . For two sets X, Y let $Y^{X}$ be the set of all total functions $f : X \to Y$ . A relation can always be considered as a set-valued function, as follows: for sets X, Y and a relation $R \subseteq X \times Y$ we define the function $F_{R} : \subseteq X \to P {(Y)}_{\neq \emptyset}$ by $dom (F_{R}) : = dom (R)$ and $F_{R} (x) : = R [x]$ , for $x \in dom (R)$ . Let Z be a set as well. If $R : \subseteq X \times Y \to Z$ is a function then for every $x \in X$ we can define a function $R (x, \cdot) : \subseteq Y \to Z$ by $dom (R (x, \cdot)) : = {y \in Y : (x, y) \in dom (R)}$ and by $R (x, \cdot) (y) : = R (x, y)$ , for $y \in dom (R (x, \cdot))$ . Similarly, for any $y \in Y$ the function $R (\cdot, y) : \subseteq X \to Z$ is defined.

2.3. Finite and infinite sequences

Let $N : = {0, 1, 2, \dots}$ be the set of non-negative integers or natural numbers. For $n \in N$ , let $[n] : = {0, 1, \dots, n - 1}$ . For a set X and for $n \in N$ , let $X^{n} : = X^{[n]}$ be the set of all functions $s : [n] \to X$ , that is, the set of all sequences of length n of elements of X. Note that $X^{0}$ has exactly one element, the empty sequence. We write it ε, for any set X. For $n \in N$ , $s \in X^{n}$ and $i < n$ we often write $s_{i}$ instead of $s (i)$ . Let $X^{< ω} : = ⋃_{n \in N} X^{n}$ be the set of all finite sequences of elements of X. For $s \in X^{< ω}$ the unique number n with $dom (s) = [n]$ is called the length of s, and written $length (s)$ . Let $X^{N} : = {h : h : N \to X}$ be the set of all infinite sequences of elements of X. An infinite sequence $h : N \to X$ if often written in the form ${(h (n))}_{n \in N}$ or just ${(h (n))}_{n}$ . For $h \in X^{N}$ and $i \in N$ we often write $h_{i}$ instead of $h (i)$ . We say that a finite sequence $s : [m] \to X$ is a prefix of a finite sequence $t : [n] \to X$ and write $s ⊑ t$ if $s \subseteq t$ , which is equivalent to ( $m ⩽ n$ and $t |_{[m]} = s$ ). We say that a finite sequence $s : [m] \to X$ is a prefix of an infinite sequence $t : N \to X$ and write $s ⊑ t$ if $s \subseteq t$ , which is equivalent to $t |_{[m]} = s$ . In the case ( $s ⊑ t$ and $s \neq t$ ) we say that s is a proper prefix of t and abbreviate this by $s ⊏ t$ .

2.4. Relations with special properties

Let X be a set. A relation $R \subseteq X \times X$ on X is called

reflexive if, for all $x \in X$ , $(x, x) \in R$ ,

transitive if, for all $x, y, z \in S$ , if ( $(x, y) \in R$ and $(y, z) \in R$ ) then $(x, z) \in R$ ,

preorder or quasi-order if it is reflexive and transitive,

symmetric if, for all $x, y \in X$ , if $(x, y) \in R$ then $(y, x) \in R$ ,

equivalence relation if it is a preorder and symmetric,

anti-symmetric if, for all $x, y \in X$ , if ( $(x, y) \in R$ and $(y, x) \in R$ ) then $x = y$ ,

partial order if it is a preorder and anti-symmetric.

total order or linear order if it is a partial order and, for all $x, y \in X$ , ( $(x, y) \in R$ or $(y, x) \in R$ ).

If ⩽ is a preorder on a set S, then usually we use infix notation, that is, we write $x ⩽ y$ instead of $(x, y) \in ⩽$ . Furthermore, if ⩽ is a preorder on a set S then we define the relation < on X as usual by $x < y : ⟺ (x ⩽ y and not y ⩽ x)$ . Note that when ⩽ is a partial order then $x < y ⟺ (x ⩽ y and x \neq y)$ . Instead of $<^{- 1}$ we write >.

Example 2.1.
For any set X the prefix relation ⊑ on $X^{< ω}$ is a partial order.

If ⩽ is a preorder on a set X, then we define the relation ≡ on X as usual by $x \equiv y : ⟺ (x ⩽ y and y ⩽ x)$ . It is clear that ≡ is an equivalence relation. We call it the equivalence relation on X induced by the preorder ⩽. A preorder ⩽ induces the following partial order (we write it ⩽ as well) on the set of equivalence classes of the equivalence relation on X induced by ⩽: It is defined by $C ⩽ D : ⟺ x ⩽ y$ , for any equivalence classes $C, D \subseteq X$ of elements of X, where $x \in C$ and $y \in D$ are arbitrary elements of C resp. of D.

A pair $(X, ⩽)$ such that X is a set and ⩽ is a preorder resp. a partial order. resp. a linear order will be called a preordered set resp. a partially ordered set or poset resp. a linearly ordered set or totally ordered set or chain.

An element x of a preordered set $(X, ⩽)$ is called a largest element if, for all $y \in X$ , $y ⩽ x$ . An element x of a preordered set $(X, ⩽)$ is called a smallest element if, for all $y \in X$ , $x ⩽ y$ . It is clear that in a poset there can be at most one largest element and at most one smallest element. If $(X, ⩽)$ is a poset and if a largest resp. smallest element exists then we call it ${max}_{⩽} (X)$ resp. ${min}_{⩽} (X)$ .

Let X be a set, and let ⩽ be a relation on X. An element $x \in X$ is called a ⩽-upper bound of a subset $Y \subseteq X$ if, for all $y \in Y$ , $y ⩽ x$ . A subset $Y \subseteq X$ such that there exists an upper bound of Y is called ⩽-upper bounded. If ⩽ is a partial order on a set X, an element $x \in X$ is called a supremum of a subset $Y \subseteq X$ and written as ${sup}_{⩽} (X)$ if Y is ⩽-upper bounded and x is a smallest element of the set of all upper bounds of Y (remember that, if such an element exists, it is unique).

Let $(X, ⩽)$ be a preordered set. A subset $U \subseteq X$ is called upwards closed if, for all $x, y \in X$ the following holds true: if $x \in U$ and $x ⩽ y$ then $y \in U$ as well. A subset $U \subseteq X$ is called downwards closed if, for all $x, y \in X$ the following holds true: if $x ⩽ y$ and $y \in U$ and then $x \in U$ as well.

For a set X with a relation ⩽ on X and for an element $x \in X$ we use the following notation: $x^{⩽} : = {y \in X : x ⩽ y}$ . Let ⩽ be a preorder. It is clear that $x^{⩽}$ is ⩽-upwards closed. And x is a ⩽-lower bound of a subset $M \subseteq X$ if, and only if, $M \subseteq x^{⩽}$ .

Let $(X^{'}, ⩽^{'})$ be a preordered set as well. A function $f : \subseteq X \to X^{'}$ is called monotone if, for all $x, y \in dom (f)$ , if $x ⩽ y$ then $f (x) ⩽^{'} f (y)$ . We call a function $f : \subseteq X \to X^{'}$ good if it is monotone and its domain $dom (f)$ is upwards closed.
2.5. The rank function of a well-founded relation

We call a preorder ⩽ on a set X and the pair $(X, ⩽)$ well-founded if there does not exist an infinite sequence ${(x_{n})}_{n \in N}$ in X such that, for all $n \in N$ , $x_{n + 1} < x_{n}$ . For a well-founded pair $(X, ⪯)$ one can define its rank function ${rank}_{⪯} : X \to ORD$ (where $ORD$ is the class of all ordinal numbers and where in the following ⩽ is the linear order on ordinal numbers) recursively as follows: $\begin{matrix} {rank}_{⪯} (x) : = sup {{rank}_{⪯} (y) + 1 : y ≺ x}, \end{matrix}$ for $x \in X$ . The rank $rank (X, ⪯)$ of the pair $(X, ⪯)$ is defined as $\begin{matrix} rank (X, ⪯) : = sup {{rank}_{⪯} (x) + 1 : x \in X} . \end{matrix}$ Note that the cardinality of the ordinal $rank (X, ⪯)$ is at most as large as the cardinality of X.

Example 2.2.
If X is the empty set then there is only one relation ⪯ on X: the empty relation $⪯ = \emptyset$ . It is a linear order and well-founded. We obtain $rank (X, ⪯) = 0$ .

2.6. The composition of relations

Let X, Y, Z be sets. The composition of two relations $R \subseteq X \times Y$ and $S \subseteq Y \times Z$ is the relation $(S \circ R) \subseteq X \times Z$ defined as follow: for all $x \in X$ $\begin{matrix} (S \circ R) [x] : = \{\begin{matrix} \emptyset & if R [x] ⊈ dom (S), \\ S [R [x]] & if R [x] \subseteq dom (S) . \end{matrix} \end{matrix}$ Note that if $R [x] = \emptyset$ then $(S \circ R) [x] = \emptyset$ as well. Thus, $dom (S \circ R) \subseteq dom (R)$ . In the context of computability over topological structures, this kind of composition of relations was first used by Brattka [1].

Lemma 2.3.
The composition operation ∘ is associative: For sets W, X, Y, Z and relations $R \subseteq W \times X$ , $S \subseteq X \times Y$ , and $T \subseteq Y \times Z$ : $\begin{matrix} T \circ (S \circ R) = (T \circ S) \circ R . \end{matrix}$

This is well known. We omit the proof. Due to the associativity of ∘ one may omit brackets in repeated applications of ∘. Note that if $f : \subseteq X \to Y$ and $g : \subseteq Y \to Z$ are functions then their composition is again a function $g \circ f : \subseteq X \to Z$ . The composition of two monotone functions between preordered sets is a monotone function as well, and the composition of two good functions between preordered sets is a good function as well.

The product of two relations $R \subseteq X \times Y$ and $S \subseteq \tilde{X} \times \tilde{Y}$ is the relation $(R \times S) \subseteq (X \times \tilde{X}) \times (Y \times \tilde{Y})$ defined as follows: for all $x \in X$ , $\tilde{x} \in \tilde{X}$ , $y \in Y$ and $\tilde{y} \in \tilde{Y}$ , $\begin{matrix} ((x, \tilde{x}), (y, \tilde{y})) \in (R \times S) : ⟺ ((x, y) \in R and (\tilde{x}, \tilde{y}) \in S) . \end{matrix}$ Obviously, this is equivalent to $\begin{matrix} (R \times S) [(x, \tilde{x})] = R [x] \times S [\tilde{x}], \end{matrix}$ for all $x \in X$ , $\tilde{x} \in \tilde{X}$ . Note that $dom (R \times S) = dom (R) \times dom (S)$ . Furthermore, note that, if R and S are functions then $R \times S$ is a function as well.
Lemma 2.4.
Let X, Y, Z, $\tilde{X}$ , $\tilde{Y}$ , $\tilde{Z}$ be sets and $R \subseteq X \times Y$ and $S \subseteq \tilde{X} \times \tilde{Y}$ and $R^{'} \subseteq Y \times Z$ and $S^{'} \subseteq \tilde{Y} \times \tilde{Z}$ be relations. Then $(R^{'} \times S^{'}) \circ (R \times S) = (R^{'} \circ R) \times (S^{'} \circ S)$ .

We omit the proof. For any set X we define the total function ${double}_{X} : X \to X \times X$ by $\begin{matrix} double (x) : = (x, x), \end{matrix}$ for all $x \in X$ . And for relations $R \subseteq X \times Y$ and $S \subseteq X \times Z$ we define the relation $(R, S) \subseteq X \times (Y \times Z)$ by $\begin{matrix} (R, S) : = (R \times S) \circ {double}_{X} . \end{matrix}$
Lemma 2.5.

For any relation $R \subseteq X \times Y$ , $(R, R) \supseteq {double}_{Y} \circ R$ .

For any function $f : \subseteq X \to Y$ , the relation $(f, f)$ is a function as well, and $(f, f) = {double}_{Y} \circ f$ .

We omit the proof.
2.7. Refinements of a relation

A relation $S \subseteq X \times Y$ is called a refinement of a relation $R \subseteq X \times Y$ if $dom (R) \subseteq dom (S)$ and for all $x \in dom (R)$ , $S [x] \subseteq R [x]$ . Note that the refinement relation on the set of all relations $R \subseteq X \times Y$ is reflexive and transitive.

Lemma 2.6.

Let X, $\tilde{X}$ , Y, $\tilde{Y}$ be sets and $R \subseteq X \times Y$ and $S \subseteq \tilde{X} \times \tilde{Y}$ be relations. If $R^{'} \subseteq X \times Y$ is a refinement of R and $S^{'} \subseteq \tilde{X} \times \tilde{Y}$ is a refinement of S then $R^{'} \times S^{'}$ is a refinement of $R \times S$ .

Let X, Y, Z be sets and $R \subseteq X \times Y$ and $S \subseteq Y \times Z$ be relations. If $R^{'} \subseteq X \times Y$ is a refinement of R and $S^{'} \subseteq Y \times Z$ is a refinement of S then $S^{'} \circ R^{'}$ is a refinement of $S \circ R$ .

Proof.

We observe $\begin{matrix} dom (R \times S) = dom (R) \times dom (S) \subseteq dom (R^{'}) \times dom (S^{'}) = dom (R^{'} \times S^{'}) . \end{matrix}$ For all $(x, \tilde{x}) \in dom (R \times S)$ we obtain $\begin{matrix} (R^{'} \times S^{'}) [(x, \tilde{x})] = R^{'} [x] \times S^{'} [\tilde{x}] \subseteq R [x] \times S [\tilde{x}] = (R \times S) [(x, \tilde{x})] . \end{matrix}$

We have $dom (R) \subseteq dom (R^{'})$ and, for $x \in dom (R)$ , $R^{'} [x] \subseteq R [x]$ . Furthermore, we have $dom (S) \subseteq dom (S^{'})$ . We obtain $\begin{array}{rcl} dom (S \circ R) & = & {x \in dom (R) : R [x] \subseteq dom (S)} \\ \subseteq & {x \in dom (R^{'}) : R^{'} [x] \subseteq dom (S^{'})} \\ = & dom (S^{'} \circ R^{'}) \end{array}$ and, for all $x \in dom (S \circ R)$ , $\begin{matrix} (S^{'} \circ R^{'}) [x] = S^{'} [R^{'} [x]] \subseteq S^{'} [R [x]] \subseteq S [R [x]] = (S \circ R) [x] \end{matrix}$ (here we also used $S^{'} [y] \subseteq S [y]$ , for all $y \in dom (S)$ ).
□

2.8. Relations as multivalued functions

Relations can be used in order to describe computation problems. For example, given some input x from some set X, one may wish to compute some y from some set Y such that $(x, y) \in R$ where $R \subseteq X \times Y$ is a relation. In order to stress that here x is the input and y is a possible desired output, sometimes a relation $R \subseteq X \times Y$ is called multivalued function.

If a function $g : \subseteq X \to Y$ is a refinement of a function $f : \subseteq X \to Y$ , then we say also that f is a restriction of g and that g is an extension of f. Note that for any subset $M \subseteq X$ the function $f |_{M}$ that was introduced in Section 2.2 and called a restriction there is indeed a restriction in this sense.

The following lemma will be used later.

Lemma 2.7.
Let $f : \subseteq X \to Y$ be a function.
${id}_{X}$ is a refinement of the relation $f^{- 1} \circ f$ on X.

If f is injective then $f^{- 1} \circ f = {id}_{X} |_{dom (f)}$ .

The relation $f \circ f^{- 1}$ on Y is the function ${id}_{Y} |_{range (f)}$ .

If f is surjective then $f \circ f^{- 1} = {id}_{Y}$ .

Proof.

We have $dom (f^{- 1} \circ f) \subseteq X = dom ({id}_{X})$ . For all $x \in dom (f^{- 1} \circ f)$ , we observe $x \in dom (f)$ and $f (x) \in dom (f^{- 1})$ and ${id}_{X} (x) = x \in f^{- 1} [f (x)] = (f^{- 1} \circ f) [x]$ .

This is clear.

We have $dom (f \circ f^{- 1}) \subseteq Y$ . For $y \in Y$ we observe that $y \in dom (f \circ f^{- 1})$ iff $y \in dom (f^{- 1})$ and $f^{- 1} [y] \subseteq dom (f)$ . But $dom (f^{- 1}) = range (f)$ . And for all $y \in Y$ the condition $f^{- 1} [y] \subseteq dom (f)$ is satisfied anyway. Hence, $dom (f \circ f^{- 1}) = range (f)$ . Finally, for $y \in range (f)$ we observe $(f \circ f^{- 1}) [y] = f [f^{- 1} (y)] = {y}$ .

This follows directly from the previous assertion.
□

3. Some topological notions

3.1. Topological spaces

For basic topological notions the reader is referred to [11]. The following two examples of topologies will be used later.

Examples 3.1.

For any set X, the set $P (X)$ is a topology on X. It is called the discrete topology on X.

Let $(X, ⩽)$ be a preordered set. Then the set of all ⩽-downwards closed subsets of X is a topology on X. We will call it the reverse Alexandroff topology (in [5] the topology consisting of the ⩽-upwards closed subsets of X is called Alexandroff topology).

A topology τ is called second-countable if there exists a countable basis for it. A topological space $(X, τ)$ is called a $T_{0}$ -space if for all $x, y \in X$ , if $x \neq y$ , then ${U \in τ : x \in U} \neq {V \in τ : y \in V}$ . Let $(X, τ)$ be a topological space. For a subset $A \subseteq X$ its closure is the set $\begin{matrix} cl (A) : = {x \in X ∣ (\forall U \in τ) if x \in U then U \cap A \neq \emptyset} . \end{matrix}$ This set is closed. In fact, it is the intersection of all closed supersets of A. Let $(X, τ)$ be a topological space, and let $X^{'}$ be a subset of X. Then the set $τ | X^{'} : = {U \cap X^{'} ∣ U \in τ}$ is a topology on $X^{'}$ and is called the relative topology on $X^{'}$ .

Let Y be a topological space as well. A function $f : \subseteq X \to Y$ is called continuous in a point $x \in dom (f)$ if for every open subset $V \subseteq Y$ with $f (x) \in V$ there is a subset $U \subseteq dom (f)$ that is open in the relative topology of $dom (f)$ and that satisfies $x \in U$ and $f [U] \subseteq V$ . It is called discontinuous in x if it is not continuous in x. If a function $f : \subseteq X \to Y$ is continuous in a point $x \in dom (f)$ and if $g : \subseteq X \to Y$ is a restriction of f with $x \in dom (g)$ then g is continous in x as well. If Z is a topological space as well, if $f : \subseteq X \to Y$ and $g : \subseteq Y \to Z$ are functions, and if $x \in dom (f)$ is a point such that f is continuous in x, such that $f (x) \in dom (g)$ , and such that g is continuous in $f (x)$ then $g \circ f$ is continuous in x. A function $f : \subseteq X \to Y$ is called continuous if it is continuous in every point $x \in dom (f)$ . This is equivalent to demanding that for all open subsets $V \subseteq Y$ the set $f^{- 1} [V]$ is open in the relative topology of $dom (f)$ . Any restriction of a continuous function is continuous as well. The composition of two continuous functions is continuous. We say that a function $f : \subseteq X \to Y$ is continuous on a subset $Z \subset X$ if the function $f |_{Z}$ is continuous. A function $f : \subseteq X \to Y$ is called open if for all open subsets $U \subseteq X$ , the set $f [U]$ is an open subset of Y. For a topological space Y, a set X, and any subset $σ \subseteq P (X)$ , a function $f : X \to Y$ is called σ-measurable if, for any open set $V \subseteq Y$ , $f^{- 1} [V] \in σ$ . For example, if σ is a topology on X, then a function $f : X \to Y$ is σ-measurable if, and only if, it is continuous.

Let X be a metrizable space. For all countable ordinals $α ⩾ 1$ the subsets $Σ_{α}^{0} (X)$ and $Π_{α}^{0} (X)$ of $P (X)$ are defined as usual recursively by: $\begin{array}{l} Σ_{1}^{0} (X) : = {U \subseteq X : U is open}, \\ Π_{α}^{0} (X) : = {A \subseteq X : (X ∖ A) \in Σ_{α}^{0} (X)}, for α ⩾ 1, \\ Σ_{α}^{0} (X) : = {⋃_{n \in N} A_{n} : (\forall n \in N) (\exists β_{n} < α) A_{n} \in Π_{β_{n}}^{0} (X)}, for α > 1 . \end{array}$ In addition one defines $\begin{matrix} Δ_{α}^{0} (X) : = Σ_{α}^{0} (X) \cap Π_{α}^{0} (X) . \end{matrix}$
3.2. The Baire space

Let $B : = N^{N}$ be the set of all functions $p : N \to N$ , thus, of all infinite sequences of natural numbers. For $n \in N$ and $w \in N^{n}$ let $w B : = {p \in B : (\forall i < n) p (i) = w (i)}$ . Note that the sets $w B$ for $w \in N^{< ω}$ form a countable basis of the product (or Tychonov) topology on $B$ induced by the discrete topology on $N$ . In fact, they are clopen in this topology. The sets $A B : = ⋃ {w B : w \in A}$ for $A \subseteq N^{< ω}$ are the open subsets of $B$ with respect to this topology. The function $d : B \times B \to R$ defined by $\begin{matrix} d (p, q) : = \{\begin{matrix} 0 & if p = q, \\ 2^{- min {i \in N ∣ p (i) \neq q (i)}} & otherwise \end{matrix} \end{matrix}$ is a complete metric on $B$ , and the induced topology is just the product topology. The topological space $B$ with this topology is called Baire space.

We define the total bijection $⟨ \cdot, \cdot ⟩ : B^{2} \to B$ by $\begin{matrix} ⟨ \cdot, \cdot ⟩ (p, q) : = ⟨ p, q ⟩ : = p_{0} q_{0} p_{1} q_{1} p_{2} q_{2} \dots \end{matrix}$ If $ρ : \subseteq B \to X$ and $σ : \subseteq B \to Y$ are functions then we define the function $[ρ, σ] : \subseteq B \to X \times Y$ by $[ρ, σ] : = (ρ \times σ) \circ {⟨ \cdot, \cdot ⟩}^{- 1}$ .

3.3. Admissible representations

Admissible representations were introduced by Kreitz and Weihrauch [13] for second countable $T_{0}$ -spaces. Schröder extended this notion to ${qcb}_{0}$ -spaces [17]. In this section we define these notions and formulate those properties of them that we shall need later on.

Definition 3.2.
If X is a set and $ρ : \subseteq B \to X$ is a surjective function then ρ is called a representation of X. In this case we call the pair $(X, ρ)$ a represented set.
Definition 3.3.

Let X be a set and let ρ and σ be representations of X. We say that ρ is reducible to σ and write $ρ ⩽ σ$ if there exists a continuous function $F : \subseteq B \to B$ with $ρ = σ \circ F$ .

Two representations ρ and σ of a set X are called equivalent (and then we write $ρ \equiv σ$ ) if $ρ ⩽ σ$ and $σ ⩽ ρ$ .

If X is a topological space, then a representation $ρ : \subseteq B \to X$ is called admissible if ρ is continuous and for every continuous representation σ of X we have $σ ⩽ ρ$ .

It is clear that the relation ⩽ on representations of a fixed set X is a preorder. Hence, the relation ≡ on representations of a fixed set X is an equivalence relation. If for a topological space X there exists an admissible representation then all admissible representations of X are equivalent.

Let $(X, ρ)$ be a represented set. The quotient topology or final topology $τ_{ρ}$ induced by ρ on X is the family of sets $\begin{matrix} τ_{ρ} : = {U \subseteq X : ρ^{- 1} [U] is open in the relative topology on dom (ρ)} . \end{matrix}$ This is the finest topology on X such that ρ is continuous.
Lemma 3.4.
If X is a set and $ρ : \subseteq B \to X$ and $σ : \subseteq B \to X$ are equivalent representations of X then $τ_{ρ} = τ_{σ}$ .

In particular, all admissible representations of a topological space induce the same topology on the space. Kreitz and Weihrauch [13] showed that for every second countable $T_{0}$ -space there exists an admissible representation and that the final topology of any admissible representation of a second countable $T_{0}$ -space is the topology of the space. These spaces will be important for us later. Schröder [16,17] characterized those topological spaces that have an admissible representation ρ such that $τ_{ρ}$ is the topology of the space. He showed that these spaces are exactly the ${qcb}_{0}$ -spaces. A topological space $(X, τ)$ is called a ${qcb}_{0}$ -space if it is a $T_{0}$ -space and if there exist a topological space W with a countable basis and a surjection $q : W \to X$ such that $τ = {U \in P (X) : q^{- 1} [U] is an open subset of W}$ , that is, such that q is continuous and τ is the finest topology on X such that q is continuous. Note that by Lemma 3.4 the final topology of any admissible representation of a ${qcb}_{0}$ -space is the topology of the space. Lemma 3.5.
Let X, Y be topological spaces, and let $X \times Y$ be their product space with the product topology.
If $ρ : \subseteq B \to X$ and $ρ^{'} : \subseteq B \to X$ are equivalent representations of X, and if $σ : \subseteq B \to Y$ and $σ^{'} : \subseteq B \to Y$ are equivalent representations of Y, then $[ρ, σ]$ and $[ρ^{'}, σ^{'}]$ are equivalent representations of $X \times Y$ .

If $ρ : \subseteq B \to X$ and $σ : \subseteq B \to Y$ are admissible representations of X resp. of Y, then $[ρ, σ] : \subseteq B \to X \times Y$ is an admissible representation of $X \times Y$ .

3.4. Relatively continuous relations

Let $(X, ρ)$ and $(Y, σ)$ be represented sets. Let $R \subseteq X \times Y$ be a relation.

Lemma 3.6.
For a function $F : \subseteq B \to B$ the following three conditions are equivalent:
The function F is a refinement of the relation $σ^{- 1} \circ R \circ ρ$ .

The function $σ \circ F$ is a refinement of the relation $R \circ ρ$ .

For all $p \in dom (R \circ ρ)$ , $\begin{matrix} p \in dom (F) and F (p) \in dom (σ) and σ (F (p)) \in R [ρ (p)] . \end{matrix}$

The proof is straightforward. We omit it.
Definition 3.7.

A function $F : \subseteq B \to B$ is called a $(ρ, σ)$ -realizer of R if one — and then all three — of the conditions in the previous lemma are satisfied.

The relation R is called $(ρ, σ)$ -continuous if there exists a continuous $(ρ, σ)$ -realizer of R.

The following lemmas are well known. Lemma 3.8.
Let $(X, ρ)$ , $(Y, σ)$ , and $(Z, τ)$ be represented sets. If $R \subseteq X \times Y$ is $(ρ, σ)$ -continuous and $S \subseteq Y \times Z$ is $(σ, τ)$ -continuous then their composition $S \circ R \subseteq X \times Z$ is $(ρ, τ)$ -continuous.
Lemma 3.9.
If X and Y are sets, ρ and $ρ^{'}$ are equivalent representations of X, and σ and $σ^{'}$ are equivalent representations of Y then a relation $R \subseteq X \times Y$ is $(ρ, σ)$ -continuous iff it is $(ρ^{'}, σ^{'})$ -continuous.
Definition 3.10.
Let X and Y be ${qcb}_{0}$ -spaces. A relation $R \subseteq X \times Y$ is called relatively continuous iff it is $(ρ, σ)$ -continuous where ρ is an arbitrary admissible representation of X and σ is an arbitrary admissible representation of Y.
Corollary 3.11.
Let X, Y, Z be ${qcb}_{0}$ -spaces. If $R \subseteq X \times Y$ and $S \subseteq Y \times Z$ are relatively continuous relations then so is their composition $S \circ R \subseteq X \times Z$ .

4. Wadge and continuous Weihrauch reducibilities

4.1. Wadge reducibility of relations

In this section, X, $X^{'}$ and Y are sets, usually with an additional structure, and we consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ .

Definition 4.1.
Let X and $X^{'}$ be topological spaces, let Y be a set, and let $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ be relations. We say that R is naively Wadge reducible to $R^{'}$ and write $R ⩽_{0} R^{'}$ iff there exists a continuous function $I : \subseteq X \to X^{'}$ such that $R^{'} \circ I$ is a refinement of R.

Note that $R^{'} \circ I$ is a refinement of R iff, for all $x \in dom (R)$ , $\begin{matrix} x \in dom (I) and I (x) \in dom (R^{'}) and R^{'} [I (x)] \subseteq R [x] . \end{matrix}$ If R and $R^{'}$ are functions then the definition simplifies to the following one: $R ⩽_{0} R^{'}$ iff there exists a continuous function $I : \subseteq X \to X^{'}$ such that, for all $x \in dom (R)$ , $R^{'} (I (x)) = R (x)$ . If R and $R^{'}$ are characteristic functions of sets then one gets the usual notion of Wadge reducibility of sets. It is clear that $⩽_{0}$ is reflexive (the identity function ${id}_{X}$ shows $R ⩽_{0} R$ ) and it is easy to see that it is transitive (if $R ⩽_{0} R^{'}$ is shown by some continuous function I and if $R^{'} ⩽_{0} R^{″}$ is shown by some continuous function $I^{'}$ then the continous function $I^{'} \circ I$ shows $R ⩽_{0} R^{″}$ ).
Lemma 4.2.
Let $(X, ρ)$ and $(X^{'}, ρ^{'})$ be represented sets. Let Y be a set. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ . Then of the following four conditions, Conditions (1) and (4) are equivalent. If additionally $σ : \subseteq B \to Y$ is a representation of Y then all of the following four conditions are equivalent.
$R \circ ρ ⩽_{0} R^{'} \circ ρ^{'}$ .

$σ^{- 1} \circ R \circ ρ ⩽_{0} σ^{- 1} \circ R^{'} \circ ρ^{'}$ .

There exists a continuous function $I : \subseteq B \to B$ such that for any $(ρ^{'}, σ)$ -realizer $F^{'}$ of $R^{'}$ the function $F^{'} \circ I$ is a $(ρ, σ)$ -realizer of R.

There exists a $(ρ, ρ^{'})$ -continuous relation $\tilde{I} \subseteq X \times X^{'}$ such that $R^{'} \circ \tilde{I}$ is a refinement of R.

Concerning Condition (4), note that $R^{'} \circ \tilde{I}$ is a refinement of R iff, for all $x \in dom (R)$ , $\begin{matrix} x \in dom (\tilde{I}) and \tilde{I} [x] \subseteq dom (R^{'}) and R^{'} [\tilde{I} [x]] \subseteq R [x] . \end{matrix}$
Proof.
$(4) \Rightarrow (1)$ : Let $\tilde{I} \subseteq X \times X^{'}$ be a $(ρ, ρ^{'})$ -continuous relation such that $R^{'} \circ \tilde{I}$ is a refinement of R. Let $I : \subseteq B \to B$ be a continuous $(ρ, ρ^{'})$ -realizer of $\tilde{I}$ . Then $ρ^{'} \circ I$ is a refinement of $\tilde{I} \circ ρ$ . Hence, $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R^{'} \circ \tilde{I} \circ ρ$ . As this is a refinement of $R \circ ρ$ , we have shown that $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ . We have shown $R \circ ρ ⩽_{0} R^{'} \circ ρ^{'}$ .

$(1) \Rightarrow (4)$ : Let us assume that $I : \subseteq B \to B$ is a continuous function such that $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ . Let the relation $\tilde{I} \subseteq X \times X^{'}$ be defined by $\tilde{I} : = ρ^{'} \circ I \circ ρ^{- 1}$ . First we claim that I is a continuous $(ρ, ρ^{'})$ -realizer of $\tilde{I}$ . Indeed, according to Lemma 2.7(1) ${id}_{B}$ is a refinement of $ρ^{- 1} \circ ρ$ , hence, $ρ^{'} \circ I = ρ^{'} \circ I \circ {id}_{B}$ is a refinement of $ρ^{'} \circ I \circ ρ^{- 1} \circ ρ = \tilde{I} \circ ρ$ . We have shown that I is a $(ρ, ρ^{'})$ -realizer of $\tilde{I}$ . As I is continuous, the relation $\tilde{I}$ is a $(ρ, ρ^{'})$ -continuous relation. Secondly, we claim that $R^{'} \circ \tilde{I}$ is a refinement of R. Indeed, as $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ the relation $R^{'} \circ \tilde{I} = R^{'} \circ ρ^{'} \circ I \circ ρ^{- 1}$ is a refinement of $R \circ ρ \circ ρ^{- 1} = R$ (here we have used Lemma 2.7(4)).

In the rest of the proof we assume that $σ : \subseteq B \to Y$ is a representation of Y.

$(1) \Rightarrow (2)$ : Let $I : \subseteq B \to B$ be a continuous function such that $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ . Then, according to Lemma 2.6(2), $σ^{- 1} \circ R^{'} \circ ρ^{'} \circ I$ is a refinement of $σ^{- 1} \circ R \circ ρ$ .

$(2) \Rightarrow (1)$ : Let $I : \subseteq B \to B$ be a continuous function such that $σ^{- 1} \circ R^{'} \circ ρ^{'} \circ I$ is a refinement of $σ^{- 1} \circ R \circ ρ$ . Then, according to Lemma 2.6(2), $R^{'} \circ ρ^{'} \circ I = σ \circ σ^{- 1} \circ R^{'} \circ ρ^{'} \circ I$ is a refinement of $σ \circ σ^{- 1} \circ R \circ ρ = R \circ ρ$ as well (here we have used Lemma 2.7(4) again).

$(1) \Rightarrow (3)$ : Let $I : \subseteq B \to B$ be a continuous function such that $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ . Consider some $(ρ^{'}, σ)$ -realizer $F^{'}$ of $R^{'}$ . Then $σ \circ F^{'}$ is a refinement of the relation $R^{'} \circ ρ^{'}$ . Hence, $σ \circ F^{'} \circ I$ is a refinement of the relation $R^{'} \circ ρ^{'} \circ I$ . As this is a refinement of $R \circ ρ$ we conclude that $σ \circ F^{'} \circ I$ is a refinement of $R \circ ρ$ . Hence, the function $F^{'} \circ I$ is a $(ρ, σ)$ -realizer of R.

$(3) \Rightarrow (1)$ : Let $I : \subseteq B \to B$ be a continuous function such that for any $(ρ^{'}, σ)$ -realizer $F^{'}$ of $R^{'}$ the function $F^{'} \circ I$ is a $(ρ, σ)$ -realizer of R. We claim that $R^{'} \circ ρ^{'} \circ I$ is a refinement of $R \circ ρ$ . Let us consider some $p \in dom (R \circ ρ)$ . We have to show $p \in dom (I)$ and $I (p) \in dom (R^{'} \circ ρ^{'})$ and $(R^{'} \circ ρ^{'}) [I (p)] \subseteq (R \circ ρ) [p]$ . Consider first a $(ρ^{'}, σ)$ -realizer $F^{'}$ of $R^{'}$ with $dom (F^{'}) = dom (R^{'} \circ ρ^{'})$ (one can get such a realizer by starting with an arbitrary $(ρ^{'}, σ)$ -realizer of $R^{'}$ and then restricting it to $dom (R^{'} \circ ρ^{'})$ ). Then $F^{'} \circ I$ is a $(ρ, σ)$ -realizer of R, hence, $σ \circ F^{'} \circ I$ is a refinement of $R \circ ρ$ . This implies $p \in dom (σ \circ F^{'} \circ I) \subseteq dom (I)$ and $I (p) \in dom (σ \circ F^{'}) \subseteq dom (F^{'}) = dom (R^{'} \circ ρ^{'})$ . Now consider some $y \in (R^{'} \circ ρ^{'}) [I (p)]$ and let $F^{'}$ be a $(ρ^{'}, σ)$ -realizer of $R^{'}$ with $dom (F^{'}) = dom (R^{'} \circ ρ^{'})$ and with $σ (F^{'} (I (p))) = y$ (one can get such a realizer by starting with an arbitrary $(ρ^{'}, σ)$ -realizer of $R^{'}$ , then restricting it to $dom (R^{'} \circ ρ^{'})$ , and by finally redefining its value in $I (p)$ to be some $q \in dom (σ)$ with $σ (q) = y$ ). The fact that $σ \circ F^{'} \circ I$ is a refinement of $R \circ ρ$ implies $y = σ (F^{'} (I (p))) \in (R \circ ρ) [p]$ . Hence, $(R^{'} \circ ρ^{'}) [I (p)] \subseteq (R \circ ρ) [p]$ . □
Definition 4.3.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces. Let Y be a set. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ . We say that R is Wadge reducible to $R^{'}$ and write $R ⩽_{Wa} R^{'}$ iff there exists a relatively continuous relation $\tilde{I} \subseteq X \times X^{'}$ such that $R^{'} \circ \tilde{I}$ is a refinement of R.

It is straightforward to see that the relation $⩽_{Wa}$ is reflexive and transitive. Lemma 4.4.
Let Y be an arbitrary set. For two relations $R \subseteq B \times Y$ and $R^{'} \subseteq B \times Y$ the following two conditions are equivalent:
$R ⩽_{0} R^{'}$ .

$R ⩽_{Wa} R^{'}$ .

Proof.
This follows from the equivalence of the first and the fourth of the conditions in the previous lemma because the identity function ${id}_{B} : B \to B$ is an admissible representation of $B$ . □

4.2. Strong Weihrauch reducibility of relations

Definition 4.5.
Let X, $X^{'}$ , Y, $Y^{'}$ be topological spaces, and let $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ be relations.
Let $O : \subseteq Y^{'} \to Y$ be a continuous function. We write $R ⩽_{1}^{O} R^{'}$ iff $R ⩽_{0} O \circ R^{'}$ .

We write $R ⩽_{1} R^{'}$ and say that R is naively strongly Weihrauch reducible to $R^{'}$ iff there exists a continuous function $O : \subseteq Y^{'} \to Y$ such that $R ⩽_{1}^{O} R^{'}$ .

Note that $R ⩽_{0} O \circ R^{'}$ is true iff there exists a continuous function $I : \subseteq X \to X^{'}$ such that $O \circ R^{'} \circ I$ is a refinement of R. And this is the case iff, for all $x \in dom (R)$ , $\begin{matrix} x \in dom (I) and I (x) \in dom (R^{'}) and (\forall y^{'} \in R^{'} [I (x)]) (y^{'} \in dom (O) and O (y^{'}) \in R [x]) . \end{matrix}$ If R and $R^{'}$ are functions then the definition simplifies to the following one: $R ⩽_{1} R^{'}$ iff there exist continuous functions $I : \subseteq X \to X^{'}$ and $O : \subseteq Y^{'} \to Y$ such that, for all $x \in dom (R)$ , $O (R^{'} (I (x))) = R (x)$ . It is straightforward to see that $⩽_{1}$ is reflexive and transitive. If $R ⩽_{0} R^{'}$ then $R ⩽_{1}^{{id}_{Y}} R^{'}$ , hence, $R ⩽_{1} R^{'}$ .
Lemma 4.6.
Let $(X, ρ)$ , $(X^{'}, ρ^{'})$ , $(Y, σ)$ , $(Y^{'}, σ^{'})$ be represented sets. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ . The following three conditions are equivalent.
$σ^{- 1} \circ R \circ ρ ⩽_{1} {(σ^{'})}^{- 1} \circ R^{'} \circ ρ^{'}$ .

There exist continuous functions $I : \subseteq B \to B$ and $O : \subseteq B \to B$ such that for any $(ρ^{'}, σ^{'})$ -realizer $F^{'}$ of $R^{'}$ the function $O \circ F^{'} \circ I$ is a $(ρ, σ)$ -realizer of R.

There exist a $(ρ, ρ^{'})$ -continuous relation $\tilde{I} \subseteq X \times X^{'}$ and a $(σ^{'}, σ)$ -continuous relation $\tilde{O} \subseteq Y^{'} \times Y$ such that $\tilde{O} \circ R^{'} \circ \tilde{I}$ is a refinement of R.

Concerning Condition (3) note that $\tilde{O} \circ R^{'} \circ \tilde{I}$ is a refinement of R iff, for all $x \in dom (R)$ , $\begin{matrix} x \in dom (\tilde{I}) and \tilde{I} [x] \subseteq dom (R^{'}) and R^{'} [\tilde{I} [x]] \subseteq dom (\tilde{O}) and \tilde{O} [R^{'} [\tilde{I} [x]]] \subseteq R [x] . \end{matrix}$ The proof of the lemma is similar to the proof of Lemma 4.2. We omit it.
Definition 4.7.
Let X, $X^{'}$ , Y, $Y^{'}$ be ${qcb}_{0}$ -spaces. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ . If there exist relatively continuous relations $\tilde{I} \subseteq X \times X^{'}$ and $\tilde{O} \subseteq Y^{'} \times Y$ such that $\tilde{O} \circ R^{'} \circ \tilde{I}$ is a refinement of R then we say that R is strongly Weihrauch reducible to $R^{'}$ and write $R ⩽_{sW} R^{'}$ .

It is straightforward to check that $⩽_{sW}$ is reflexive and transitive. If $R ⩽_{Wa} R^{'}$ then $R ⩽_{sW} R^{'}$ .
4.3. Weihrauch reducibility of relations

Definition 4.8.
Let X, $X^{'}$ , Y, $Y^{'}$ be topological spaces, and let $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ be relations. We write $R ⩽_{2} R^{'}$ and say that R is naively Weihrauch reducible to $R^{'}$ iff there exist continuous functions $I : \subseteq X \to X^{'}$ and $O : \subseteq X \times Y^{'} \to Y$ such that $O \circ (i d_{X}, R^{'} \circ I)$ is a refinement of R.

Note that $O \circ (i d_{X}, R^{'} \circ I)$ is a refinement of R iff, for all $x \in dom (R)$ , $\begin{matrix} x \in dom (I) and I (x) \in dom (R^{'}) and (\forall y^{'} \in R^{'} [I (x)]) ((x, y^{'}) \in dom (O) and O (x, y^{'}) \in R [x]) . \end{matrix}$ If R and $R^{'}$ are functions then the definition simplifies to the following one: $R ⩽_{2} R^{'}$ iff there exist continuous functions $I : \subseteq X \to X^{'}$ and $O : \subseteq X \times Y^{'} \to Y$ such that, for all $x \in dom (R)$ , $O (x, R^{'} (I (x)) = R (x)$ . We leave it to the reader to check that $⩽_{2}$ is reflexive and transitive. If $R ⩽_{1} R^{'}$ then $R ⩽_{2} R^{'}$ .

The equivalence of the second and the third condition in the following lemma is a topological version of a computability-theoretic equivalence observed by Brattka, Gherardi and Pauly [2, Proposition 3.2.1]; compare also Gherardi and Marcone [4]. We omit the proof of the lemma.
Lemma 4.9.
Let $(X, ρ)$ , $(X^{'}, ρ^{'})$ , $(Y, σ)$ , $(Y^{'}, σ^{'})$ be represented sets. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ . The following three conditions are equivalent.
$σ^{- 1} \circ R \circ ρ ⩽_{2} {(σ^{'})}^{- 1} \circ R^{'} \circ ρ^{'}$ .

There exist continuous functions $I : \subseteq B \to B$ and $O : \subseteq B^{2} \to B$ such that for any $(ρ^{'}, σ^{'})$ -realizer $F^{'}$ of $R^{'}$ the function $O \circ ({id}_{B}, F^{'} \circ I)$ is a $(ρ, σ)$ -realizer of R.

There exist a $(ρ, [{id}_{B}, ρ^{'}])$ -continuous relation $\tilde{I} \subseteq X \times (B \times X^{'})$ and an $([{id}_{B}, σ^{'}], σ)$ -continuous relation $\tilde{O} \subseteq (B \times Y^{'}) \times Y$ such that $\tilde{O} \circ ({id}_{B} \times R^{'}) \circ \tilde{I}$ is a refinement of R.

Definition 4.10.
Let X, $X^{'}$ , Y, $Y^{'}$ be ${qcb}_{0}$ -spaces. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ . If there exist relatively continuous relations $\tilde{I} \subseteq X \times (B \times X^{'})$ and $\tilde{O} \subseteq (B \times Y^{'}) \times Y$ such that $\tilde{O} \circ ({id}_{B} \times R^{'}) \circ \tilde{I}$ is a refinement of R then we say that R is Weihrauch reducible to $R^{'}$ and write $R ⩽_{We} R^{'}$ .

It is straightforward to check that $⩽_{We}$ is reflexive and transitive. If $R ⩽_{sW} R^{'}$ then $R ⩽_{We} R^{'}$ .

Finally, let us consider the special case when both Y and $Y^{'}$ are finite discrete spaces. Lemma 4.11.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces, let $ρ : \subseteq B \to X$ and $ρ^{'} : \subseteq B \to X^{'}$ be admissible representations of X and of $X^{'}$ , respectively, and let Y, $Y^{'}$ be finite discrete spaces. We consider two relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ . Then the following conditions are equivalent.
$R ⩽_{We} R^{'}$ ,

$R \circ ρ ⩽_{2} R^{'} \circ ρ^{'}$ .

Proof.
First, we define admissible representations of the discrete spaces Y and $Y^{'}$ . Let $n : = | Y |$ be the cardinality of Y, and let $y_{0}, \dots, y_{n - 1}$ be the elements of Y in some order. Let $σ : \subseteq B \to Y$ be defined by $dom (σ) : = {p \in B : p (0) < n}$ and $σ (p) : = y_{p (0)}$ , for $p \in dom (σ)$ . Then σ is an admissible representation of Y. Let $n^{'} : = | Y^{'} |$ be the cardinality of $Y^{'}$ , and let $y_{0}^{'}, \dots, y_{n^{'} - 1}^{'}$ be the elements of $Y^{'}$ in some order. Define $σ^{'} : \subseteq B \to Y^{'}$ in the same way as σ. Then $σ^{'}$ is an admissible representation of $Y^{'}$ . According to Lemma 4.9 the first condition, $R ⩽_{We} R^{'}$ , is equivalent to
$σ^{- 1} \circ R \circ ρ ⩽_{2} {(σ^{'})}^{- 1} \circ R^{'} \circ ρ^{'}$ .
We are going to show that the second condition, Condition (2), and Condition (3) are equivalent. Let $f_{σ} : Y \to B$ be defined by $f_{σ} (y_{i}) : = i 0^{ω}$ , for $i < n$ , and let $f_{σ^{'}} : Y^{'} \to B$ be defined by $f_{σ^{'}} (y_{j}^{'}) : = j 0^{ω}$ , for $j < n^{'}$ . Then $f_{σ}$ is a continuous refinement of $σ^{- 1}$ , and $f_{σ^{'}}$ is a continuous refinement of $σ^{' - 1}$ .

$(3) \Rightarrow (2)$ : Let $I : \subseteq B \to B$ and $O : \subseteq B^{2} \to B$ be continuous functions such that $O \circ (i d_{B}, {σ^{'}}^{- 1} \circ R^{'} \circ ρ^{'} \circ I)$ is a refinement of $σ^{- 1} \circ R \circ ρ$ . We define a function $\tilde{O} : \subseteq B \times Y^{'} \to Y$ by $\tilde{O} : = σ \circ O \circ ({id}_{B} \times f_{σ^{'}})$ . This function is continuous. The relation $\begin{matrix} \tilde{O} \circ (i d_{B}, R^{'} \circ ρ^{'} \circ I) = σ \circ O \circ ({id}_{B} \times f_{σ^{'}}) \circ (i d_{B}, R^{'} \circ ρ^{'} \circ I) = σ \circ O \circ ({id}_{B}, f_{σ^{'}} \circ R^{'} \circ ρ^{'} \circ I) \end{matrix}$ is a refinement of $σ \circ O \circ ({id}_{B}, σ^{' - 1} \circ R^{'} \circ ρ^{'} \circ I)$ , and this is a refinement of $σ \circ σ^{- 1} \circ R \circ ρ = R \circ ρ$ .

$(2) \Rightarrow (3)$ : Let $I : \subseteq B \to B$ and $O : \subseteq B \times Y^{'} \to Y$ be continuous functions such that $O \circ (i d_{B}, R^{'} \circ ρ^{'} \circ I)$ is a refinement of $R \circ ρ$ . We define a function $\hat{O} : \subseteq B^{2} \to B$ by $\hat{O} : = f_{σ} \circ O \circ ({id}_{B} \times σ^{'})$ . This function is continuous. The relation $\begin{matrix} \hat{O} \circ (i d_{B}, {σ^{'}}^{- 1} \circ R^{'} \circ ρ^{'} \circ I) = f_{σ} \circ O \circ ({id}_{B} \times σ^{'}) \circ (i d_{B}, {σ^{'}}^{- 1} \circ R^{'} \circ ρ^{'} \circ I) = f_{σ} \circ O \circ (i d_{B}, R^{'} \circ ρ^{'} \circ I) \end{matrix}$ is a refinement of $f_{σ} \circ R \circ ρ$ , and this is a refinement of $σ^{- 1} \circ R \circ ρ$ . □

4.4. Examples

Example 4.12.
For any natural number $n ⩾ 2$ let the bijection ${⟨ \cdot ⟩}_{n} : B^{n} \to B$ be defined by $\begin{matrix} {⟨ p^{(0)}, \dots, p^{(n - 1)} ⟩}_{n} : = p_{0}^{(0)} \dots p_{0}^{(n - 1)} p_{1}^{(0)} \dots p_{1}^{(n - 1)} p_{2}^{(0)} \dots p_{2}^{(n - 1)} \dots, \end{matrix}$ for $p^{(0)}, \dots, p^{(n - 1)} \in B$ . We remind the reader of the abbreviation $[n] : = {0, \dots, n - 1}$ . For any natural number $n ⩾ 2$ let us define the relation ${LLPO}_{n} \subseteq B \times [n]$ by $\begin{array}{l} dom ({LLPO}_{n}) : = {0^{ω}} \cup {p \in B : (\exists i \in N) p = 0^{i} 10^{ω}}, \\ {LLPO}_{n} [{⟨ p^{(0)}, \dots, p^{(n - 1)} ⟩}_{n}] : = {i \in [n] : p^{(i)} = 0^{ω}}, \end{array}$ for all $p^{(0)}, \dots, p^{(n - 1)} \in B$ such that ${⟨ p^{(0)}, \dots, p^{(n - 1)} ⟩}_{n} \in dom ({LLPO}_{n})$ . Note that for all such $p^{(0)}, \dots, p^{(n - 1)} \in B$ either all of them are equal to $0^{ω}$ or all of them but one are equal to $0^{ω}$ , and the remaining one is of the form $0^{i} 10^{ω}$ for some $i \in N$ . In fact, $\begin{array}{l} {LLPO}_{n} [0^{ω}] = [n], \\ {LLPO}_{n} [0^{i} 10^{ω}] = [n] ∖ {i mod n}, for i \in N . \end{array}$ We claim that, for all $n ⩾ 2$ ,
${LLPO}_{n + 1} ⩽_{Wa} {LLPO}_{n}$ ,

${LLPO}_{n} ≰_{We} {LLPO}_{n + 1}$ .
Of course, this implies ${LLPO}_{n + 1} <_{We} {LLPO}_{n}$ , for all $n ⩾ 2$ , which was shown by Weihrauch [26].

Let us prove the first claim directly. Let us fix some $n ⩾ 2$ . First, we note that according to Lemma 4.4 for the first claim it is sufficient to prove ${LLPO}_{n + 1} ⩽_{0} {LLPO}_{n}$ . This is shown by the continuous function $I : \subseteq B \to B$ defined by $dom (I) : = dom ({LLPO}_{n + 1})$ and by $I (0^{ω}) : = 0^{ω}$ as well as by $\begin{matrix} I (0^{i} 10^{ω}) : = \{\begin{matrix} 0^{ω} & if i mod (n + 1) = n, \\ 0^{n \cdot i + (i mod (n + 1))} 10^{ω} & if i mod (n + 1) \in [n], \end{matrix} \end{matrix}$ for $i \in N$ . Indeed, it is straightforward to check that ${LLPO}_{n} \circ I$ is a refinement of ${LLPO}_{n + 1}$ . The other claim will be shown later in Example 11.10.
Example 4.13.
Let $⟨ \cdot, \cdot ⟩ : N^{2} \to N$ be the bijection defined by $\begin{matrix} ⟨ i, j ⟩ : = \frac{(i + j) (i + j + 1)}{2} + j, \end{matrix}$ for i, j. Let the bijection ${⟨ \cdot ⟩}_{n} : B^{N} \to B$ be defined by $\begin{matrix} ⟨ p^{(0)}, p^{(1)}, p^{(2)}, \dots ⟩ (⟨ m, n ⟩) : = p^{(m)} (n), \end{matrix}$ for $p^{(0)}, p^{(1)}, p^{(2)}, \dots \in B$ . In analogy to the relations ${LLPO}_{n}$ we can define a relation ${LLPO}_{\infty} \subseteq B \times N$ by $\begin{array}{l} dom ({LLPO}_{\infty}) : = {0^{ω}} \cup {p \in B : (\exists i \in N) p = 0^{i} 10^{ω}}, \\ {LLPO}_{\infty} [⟨ p^{(0)}, p^{(1)}, p^{(2)}, \dots ⟩] : = {i \in N : p^{(i)} = 0^{ω}}, \end{array}$ for all $p^{(0)}, p^{(1)}, p^{(2)}, \dots \in B$ such that $⟨ p^{(0)}, p^{(1)}, p^{(2)}, \dots ⟩ \in dom ({LLPO}_{\infty})$ . Note that for all such $p^{(0)}, p^{(1)}, p^{(2)}, \dots \in B$ either all of them are equal to $0^{ω}$ or all of them but one are equal to $0^{ω}$ , and the remaining one is of the form $0^{i} 10^{ω}$ for some $i \in N$ . In fact, $\begin{array}{l} {LLPO}_{\infty} [0^{ω}] = N, \\ {LLPO}_{\infty} [0^{⟨ i, j ⟩} 10^{ω}] = N ∖ {i}, for i, j \in N . \end{array}$ We claim that, for all $n ⩾ 2$ ,
${LLPO}_{\infty} ⩽_{Wa} {LLPO}_{n}$ ,

${LLPO}_{n} ≰_{We} {LLPO}_{\infty}$ .
Of course, this implies ${LLPO}_{\infty} <_{We} {LLPO}_{n}$ , for all $n ⩾ 2$ .

Let us prove the first claim directly. Let us fix some $n ⩾ 2$ . First, we note that according to Lemma 4.4 for the first claim it is sufficient to prove ${LLPO}_{\infty} ⩽_{0} {LLPO}_{n}$ . This is shown by the continuous function $I : \subseteq B \to B$ defined by $dom (I) : = dom ({LLPO}_{\infty})$ and by $I (0^{ω}) : = 0^{ω}$ as well as by $\begin{matrix} I (0^{⟨ i, j ⟩} 10^{ω}) : = \{\begin{matrix} 0^{n \cdot ⟨ i, j ⟩ + i} 10^{ω} & if i < n, \\ 0^{ω} & otherwise, \end{matrix} \end{matrix}$ for $i, j \in N$ . Indeed, it is straightforward to check that ${LLPO}_{n} \circ I$ is a refinement of ${LLPO}_{\infty}$ . The other claim will be shown later in Example 11.11.
5. Reducibility relations between functions defined on topological spaces with range in a preordered set

Let X and $X^{'}$ be topological spaces.

5.1. Wadge reducibility

Definition 5.1.
Let $(Y, ⪯)$ be a preordered set. We define a relation $⪯_{0}$ between functions from topological spaces to Y as follows. For functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y$ we define $\begin{array}{rcl} f ⪯_{0} f^{'} & : ⟺ & there exists a continuous function A : \subseteq X \to X^{'} \\ such that dom (f) \subseteq dom (f^{'} \circ A) and (\forall x \in dom (f)) f (x) ⪯ f^{'} (A (x)) . \end{array}$

It is clear that $⪯_{0}$ is reflexive and transitive. Van Engelen, Miller, and Steel [22] considered this version of Wadge reducibility for total functions f and $f^{'}$ on the Baire space. The following lemma says that this relation can be used to express the naive Wadge reducibility for functions defined in Section 4.1.
Lemma 5.2.
Let Y be a set, and let the relation ⪯ on Y be simply the equality relation. Then for any topological spaces X, $X^{'}$ and any functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y$ the following two conditions are equivalent.
$f ⩽_{0} f^{'}$ ,

$f ⪯_{0} f^{'}$ .

The proof is straightforward, and we omit it. In fact, with $⪯_{0}$ one can even express the naive Wadge reducibility relation $⩽_{0}$ between relations.
Lemma 5.3.
Let Y be a set, let X, $X^{'}$ be topological spaces, and let $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ be relations. Then the following two conditions are equivalent.
$R ⩽_{0} R^{'}$ ,

$F_{R} \supseteq_{0} F_{R^{'}}$ .

Here, the second condition is based on the functions $F_{R}$ , $F_{R^{'}}$ associated with the relations R, $R^{'}$ as in Section 2.2 and on the preordered set $(P {(Y)}_{\neq \emptyset}, \supseteq)$ . Note that in this case we write $\supseteq_{0}$ for $⪯_{0}$ . Again, the proof is straightforward, and we omit it. Corollary 5.4.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y be a set. Then for relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y$ the following two conditions are equivalent.
$R ⩽_{Wa} R^{'}$ ,

$F_{R} \circ ρ \supseteq_{0} F_{R^{'}} \circ ρ^{'}$ .

Proof.
By Lemma 4.2 the condition $R ⩽_{Wa} R^{'}$ is equivalent to $R \circ ρ ⩽_{0} R^{'} \circ ρ^{'}$ . According to Lemma 5.3 this is equivalent to $F_{R \circ ρ} \supseteq_{0} F_{R^{'} \circ ρ^{'}}$ . Finally, we observe $F_{R \circ ρ} = F_{R} \circ ρ$ and, similarly, $F_{R^{'} \circ ρ^{'}} = F_{R^{'}} \circ ρ^{'}$ . □

5.2. Strong Weihrauch reducibility

Let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets. Let $C : \subseteq Y^{'} \to Y$ be a good function.

Definition 5.5.
For functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ we define $\begin{array}{rcl} f ⪯_{1}^{C} f & : ⟺ & f ⪯_{0} C \circ f^{'} \\ ⟺ & there exists a continuous function A : \subseteq X \to X^{'} \\ such that dom (f) \subseteq dom (C \circ f^{'} \circ A) and (\forall x \in dom (f)) f (x) ⪯ C (f^{'} (A (x))) . \end{array}$

This obviously extends the Wadge reducibility introduced in Section 5.1 as, in case $(Y, ⪯) = (Y^{'}, ⪯^{'})$ , $\begin{matrix} f ⪯_{0} f^{'} ⟺ f ⪯_{1}^{{id}_{Y}} f^{'} . \end{matrix}$
Lemma 5.6.
Let X, $X^{'}$ , $X^{″}$ be topological spaces and $(Y, ⪯)$ , $(Y^{'}, ⪯^{'})$ , $(Y^{″}, ⪯^{″})$ be preordered sets. Let $f : \subseteq X \to Y$ , $f^{'} : \subseteq X^{'} \to Y^{'}$ , and $f^{″} : \subseteq X^{″} \to Y^{″}$ be functions. Let $C : \subseteq Y^{'} \to Y$ and $C^{'} : \subseteq Y^{″} \to Y^{'}$ be good functions. If $f ⪯_{1}^{C} f^{'}$ and $f^{'} ⪯_{1}^{C^{'}} f^{″}$ then $f ⪯_{1}^{C \circ C^{'}} f^{″}$ .

The proof is straightforward. We omit it.

For sets Y, $Y^{'}$ and a relation $O \subseteq Y^{'} \times Y$ let the function $C_{O} : \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ be defined by $dom (C_{O}) : = {M : \emptyset \neq M \subseteq dom (O)}$ and $C_{O} (M) : = O [M]$ , for $M \in dom (C_{O})$ . It is straightforward to see that $C_{O}$ is a good function with respect to ⊇ on $P {(Y^{'})}_{\neq \emptyset}$ and on $P {(Y)}_{\neq \emptyset}$ .
Lemma 5.7.
Let Y, $Y^{'}$ be sets, and let $O : \subseteq Y^{'} \times Y$ be a relation. Then for relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ we have $\begin{matrix} R ⩽_{0} O \circ R^{'} ⟺ F_{R} \supseteq_{1}^{C_{O}} F_{R^{'}} . \end{matrix}$

Here, the condition on the right hand side is based on the functions $F_{R}$ , $F_{R^{'}}$ associated with the relations R, $R^{'}$ as in Section 2.2 and on the preordered sets $(P {(Y)}_{\neq \emptyset}, \supseteq)$ and $(P {(Y^{'})}_{\neq \emptyset}, \supseteq)$ . In this case we write $\supseteq_{1}$ for $⪯_{1}$ , similarly as in Lemma 5.3.
Proof.
Indeed: $\begin{array}{l} R ⩽_{0} O \circ R^{'} & ⟺ F_{R} \supseteq_{0} F_{O \circ R^{'}} (due to Lemma 5.3) \\ ⟺ F_{R} \supseteq_{0} C_{O} \circ F_{R^{'}} (because of F_{O \circ R^{'}} = C_{O} \circ F_{R^{'}}) \\ ⟺ F_{R} \supseteq_{1}^{C_{O}} F_{R^{'}} (by definition of ⪯_{1}^{C_{O}}) . \end{array}$ □

Let us consider ${qcb}_{0}$ -spaces.
Corollary 5.8.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y, $Y^{'}$ be ${qcb}_{0}$ -spaces as well. Then for relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ the following two conditions are equivalent.
$R ⩽_{sW} R^{'}$ ,

There exists a relatively continuous relation $O : \subseteq Y^{'} \times Y$ such that $F_{R} \circ ρ \supseteq_{1}^{C_{O}} F_{R^{'}} \circ ρ^{'}$ .

Proof.
By definition, the condition $R ⩽_{sW} R^{'}$ is equivalent to the existence of a relatively continuous relation $O : \subseteq Y^{'} \times Y$ such that $\begin{matrix} R \circ ρ ⩽_{0} O \circ R^{'} \circ ρ^{'} . \end{matrix}$ According to Lemma 5.7 this last condition is equivalent to $\begin{matrix} F_{R \circ ρ} \supseteq_{1}^{C_{O}} F_{R^{'} \circ ρ^{'}} . \end{matrix}$ Finally, we observe $F_{R \circ ρ} = F_{R} \circ ρ$ and, similarly, $F_{R^{'} \circ ρ^{'}} = F_{R^{'}} \circ ρ^{'}$ . □

We pay special attention to the case of relations with discrete range. Corollary 5.9.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively, let Y be a ${qcb}_{0}$ -space as well, and let $Y^{'}$ be a countable discrete topological space. Then for relations $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ the following two conditions are equivalent.
$R ⩽_{sW} R^{'}$ ,

There exists a good function $C : \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ (good with respect to ⊇ on both sets) such that $F_{R} \circ ρ \supseteq_{1}^{C} F_{R^{'}} \circ ρ^{'}$ .

Proof.
According to Corollary 5.8 the first condition, $R ⩽_{sW} R^{'}$ , is equivalent to the following condition:
There exists a relatively continuous relation $O \subseteq Y^{'} \times Y$ such that $F_{R} \circ ρ \supseteq_{1}^{C_{O}} F_{R^{'}} \circ ρ^{'}$ .
Therefore, it is sufficient to show that the second condition above and this condition are equivalent.

“ $3 \Rightarrow 2$ ”: This follows from the fact, mentioned above, that for any relation $O \subseteq Y^{'} \times Y$ the induced function $C_{O} : \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ is a good function with respect to ⊇ on both sets.

“ $2 \Rightarrow 3$ ”: Let $C \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ be a good function with $F_{R} \circ ρ \supseteq_{1}^{C} F_{R^{'}} \circ ρ^{'}$ . We define a relation $O \subseteq Y^{'} \times Y$ by $dom (O) : = {y^{'} \in Y^{'} : {y^{'}} \in dom (C)}$ and $O [y^{'}] : = C ({y^{'}})$ , for $y \in dom (O)$ . As $Y^{'}$ is a countable discrete topological space, the relation O is relatively continuous. As $dom (C)$ is upwards closed, for all $M \in dom (C)$ and for all $y^{'} \in M$ we have ${y^{'}} \in dom (C)$ , hence $y^{'} \in dom (O)$ , hence, $\emptyset \neq M \subseteq dom (O)$ . This shows $dom (C) \subseteq dom (C_{O})$ . Furthermore, for all $M \in dom (C)$ , $\begin{matrix} C (M) \supseteq ⋃_{y^{'} \in M} C ({y^{'}}) = ⋃_{y^{'} \in M} O [y^{'}] = O [M] = C_{O} (M) . \end{matrix}$ Thus, the condition $F_{R} \circ ρ \supseteq_{1}^{C} F_{R^{'}} \circ ρ^{'}$ implies $F_{R} \circ ρ \supseteq_{1}^{C_{O}} F_{R^{'}} \circ ρ^{'}$ . □

5.3. Weihrauch reducibility

Let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets.

Definition 5.10.
We call a function $B : \subseteq X \times Y^{'} \to Y$ very good if
for all $x \in X$ the function $B (x, \cdot) : \subseteq Y^{'} \to Y$ is good,

for all $x \in X$ with $dom (B (x, \cdot)) \neq \emptyset$ there exists an open neighborhood U of x such that, for all $y^{'} \in dom (B (x, \cdot))$ and all $\tilde{x} \in U$ , if $(\tilde{x}, y^{'}) \in dom (B)$ then $B (\tilde{x}, y^{'}) = B (x, y^{'})$ (this means that the family of functions $B (\cdot, y^{'}) : \subseteq X \to Y$ for $y^{'} \in Y^{'}$ is equicontinuous with respect to the discrete topology on Y).

Definition 5.11.

For a good function $C : \subseteq Y^{'} \to Y$ and for functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ we define $\begin{array}{l} f ⪯_{2}^{C} f^{'} : ⟺ \\ there exist a continuous function A : \subseteq X \to X^{'} \\ and a very good function B : \subseteq X \times Y^{'} \to Y such that \\ dom (f) \subseteq dom (B \circ ({id}_{X}, (f^{'} \circ A))) and \\ (\forall x \in dom (f)) (f (x) ⪯ B (x, f^{'} (A (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in X) (if (x, y^{'}) \in dom (B) then B (x, y^{'}) = C (y^{'})) . \end{array}$

For functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ we define $\begin{matrix} f ⪯_{2} f^{'} : ⟺ f ⪯_{2}^{\emptyset} f^{'} \end{matrix}$ where ∅ is the function from $Y^{'}$ to Y with empty domain of definition.

Lemma 5.12.
Let $C : \subseteq Y^{'} \to Y$ and $\tilde{C} : \subseteq Y^{'} \to Y$ be good functions, such that $\tilde{C}$ is an extension of C. Then for two functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ , if $f ⪯_{2}^{\tilde{C}} f^{'}$ then $f ⪯_{2}^{C} f^{'}$ .

This is obvious. We omit the proof. Next, we show that the relation $⪯_{2}^{C}$ generalizes the relations $⪯_{0}$ and $⪯_{1}^{C}$ introduced in Sections 5.1 and 5.2.
Lemma 5.13.
Let X, $X^{'}$ be topological spaces and $(Y, ⪯)$ , $(Y^{'}, ⪯^{'})$ be preordered sets. Let $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ be functions.
For any good function $C : \subseteq Y^{'} \to Y$ , $\begin{matrix} f ⪯_{1}^{C} f^{'} \Rightarrow f ⪯_{2}^{C} f^{'} . \end{matrix}$

For any good function $C : \subseteq Y^{'} \to Y$ with $range (f^{'}) \subseteq dom (C)$ , $\begin{matrix} f ⪯_{1}^{C} f^{'} ⟺ f ⪯_{2}^{C} f^{'} . \end{matrix}$

In the case $(Y, ⪯) = (Y^{'}, ⪯^{'})$ , $\begin{matrix} f ⪯_{0} f^{'} ⟺ f ⪯_{2}^{{id}_{Y}} f^{'} . \end{matrix}$

Proof.

Let $A : \subseteq X \to X^{'}$ be a continuous function that shows $f ⪯_{1}^{C} f^{'}$ , that is, such that $dom (f) \subseteq dom (C \circ f^{'} \circ A)$ and $(\forall x \in dom (f)) f (x) ⪯ C (f^{'} (A (x)))$ . We define the function $B : \subseteq X \times Y^{'} \to Y$ by $dom (B) : = X \times dom (C)$ and $B (x, y^{'}) : = C (y^{'})$ , for all $(x, y^{'}) \in dom (B)$ . Then B is a very good function, and it is straightforward to see that the functions A and B show $f ⪯_{2}^{C} f^{'}$ .

Let $C : \subseteq Y^{'} \to Y$ be a good function with $range (f^{'}) \subseteq dom (C)$ . It is sufficient to show that $f ⪯_{2}^{C} f^{'}$ implies $f ⪯_{1}^{C} f^{'}$ . So, let us assume $f ⪯_{2}^{C} f^{'}$ . Let $A : \subseteq X \to X^{'}$ be a continuous function and $B : \subseteq X \times Y^{'} \to Y$ be a very good function that show this, that is, with $\begin{array}{l} dom (f) \subseteq dom (B \circ ({id}_{X}, (f^{'} \circ A))) and \\ (\forall x \in dom (f)) (f (x) ⪯ B (x, f^{'} (A (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in X) (if (x, y^{'}) \in dom (B) then B (x, y^{'}) = C (y^{'})) . \end{array}$ We claim that the function A shows $f ⪯_{1}^{C} f^{'}$ . Indeed, A is continuous. And for any $x \in dom (f)$ we have $x \in dom (f^{'} \circ A)$ and $f^{'} (A (x)) \in range (f^{'}) \subseteq dom (C)$ as well as $(x, f^{'} (A (x))) \in dom (B)$ , and $f (x) ⪯ B (x, f^{'} (A (x))) = C (f^{'} (A (x)))$ .

Let us assume $(Y, ⪯) = (Y^{'}, ⪯^{'})$ . The second assertion shows that the conditions $f ⪯_{2}^{{id}_{Y}} f^{'}$ and $f ⪯_{1}^{{id}_{Y}} f^{'}$ are equivalent. And it is clear that the conditions $f ⪯_{1}^{{id}_{Y}} f^{'}$ and $f ⪯_{0} f^{'}$ are equivalent.
□
Lemma 5.14.
Let X, $X^{'}$ , $X^{″}$ be topological spaces and $(Y, ⪯)$ , $(Y^{'}, ⪯^{'})$ , $(Y^{″}, ⪯^{″})$ be preordered sets. Let $f : \subseteq X \to Y$ , $f^{'} : \subseteq X^{'} \to Y^{'}$ , and $f^{″} : \subseteq X^{″} \to Y^{″}$ be functions. Let $C : \subseteq Y^{'} \to Y$ and $C^{'} : \subseteq Y^{″} \to Y^{'}$ be good functions.
If $f ⪯_{2}^{C} f^{'}$ and $f^{'} ⪯_{2}^{C^{'}} f^{″}$ then $f ⪯_{2}^{C \circ C^{'}} f^{″}$ .

If $(Y, ⪯) = (Y^{'}, ⪯^{'})$ then: if $f ⪯_{0} f^{'}$ and $f^{'} ⪯_{2}^{C^{'}} f^{″}$ then $f ⪯_{2}^{C^{'}} f^{″}$ .

If $(Y^{'}, ⪯^{'}) = (Y^{″}, ⪯^{″})$ then: if $f ⪯_{2}^{C} f^{'}$ and $f^{'} ⪯_{0} f^{″}$ then $f ⪯_{2}^{C} f^{″}$ .

Proof.
Due to Lemma 5.13.3 the second and the third assertion are special cases of the first assertion.

Let us prove the first assertion. Let $A : \subseteq X \to X^{'}$ be a continuous function and $B : \subseteq X \times Y^{'} \to Y$ be a very good function that show $f ⪯_{2}^{C} f^{'}$ , that is, with $\begin{array}{l} dom (f) \subseteq dom (B \circ ({id}_{X}, (f^{'} \circ A))) and \\ (\forall x \in dom (f)) (f (x) ⪯ B (x, f^{'} (A (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in X) (if (x, y^{'}) \in dom (B) then B (x, y^{'}) = C (y^{'})) . \end{array}$ Let $A^{'} : \subseteq X^{'} \to X^{″}$ be a continuous function and $B : \subseteq X^{'} \times Y^{″} \to Y^{'}$ be a very good function that show $f^{'} ⪯_{2}^{C^{'}} f^{″}$ , that is, with $\begin{array}{l} dom (f^{'}) \subseteq dom (B^{'} \circ ({id}_{X^{'}}, (f^{″} \circ A^{'}))) and \\ (\forall x^{'} \in dom (f^{'})) (f^{'} (x^{'}) ⪯ B^{'} (x^{'}, f^{″} (A^{'} (x^{'}))) and \\ (\forall y^{″} \in dom (C^{'})) (\forall x^{'} \in X^{'}) (if (x^{'}, y^{″}) \in dom (B^{'}) then B^{'} (x^{'}, y^{″}) = C^{'} (y^{″})) . \end{array}$ Let us define a function $\tilde{A} : \subseteq X \to X^{″}$ by $\tilde{A} : = A^{'} \circ A$ . Let us define a function $\tilde{B} : \subseteq X \times Y^{″} \to Y$ by $\begin{array}{l} \begin{matrix} dom (\tilde{B}) & : = {(x, y^{″}) \in X \times Y^{″} : x \in dom (A) and \\ (A (x), y^{″}) \in dom (B^{'}) and (x, B^{'} (A (x), y^{″}) \in dom (B)}, \end{matrix} \\ \tilde{B} (x, y^{″}) : = B (x, B^{'} (A (x), y^{″})), \end{array}$ for $(x, y^{″}) \in dom (\tilde{B})$ . We claim that these functions $\tilde{A}$ and $\tilde{B}$ show $f ⪯_{2}^{C^{'} \circ C} f^{″}$ . Indeed, $\tilde{A}$ is continuous. It is clear as well that for every $x \in X$ the function $\tilde{B} (x, \cdot)$ is good. Let us consider some $x \in X$ such that $dom (\tilde{B} (x, \cdot)) \neq \emptyset$ . This implies on the one hand that $dom (B (x, \cdot)) \neq \emptyset$ and on the other hand $x \in dom (A)$ and $dom (B^{'} (A (x)), \cdot) \neq \emptyset$ . Hence, there exists an open neighborhood U of x such that, for all $y^{'} \in dom (B (x, \cdot))$ and all $\tilde{x} \in U$ , if $(\tilde{x}, y^{'}) \in dom (B)$ then $B (\tilde{x}, y^{'}) = B (x, y^{'})$ . And there exists an open neighborhood $V^{'}$ of $A (x)$ such that, for all $y^{″} \in dom (B^{'} (A (x), \cdot))$ and all $x^{'} \in V^{'}$ , if $(x^{'}, y^{″}) \in dom (B^{'})$ then $B^{'} (x^{'}, y^{″}) = B^{'} (A (x), y^{″})$ . Then $\tilde{U} : = U \cap A^{- 1} [V^{'}]$ is an open neighborhood of x, and for all $y^{″} \in dom (\tilde{B} (x, \cdot)$ and all $\tilde{x} \in \tilde{U}$ we have, if $(\tilde{x}, y^{″}) \in dom (\tilde{B})$ , then $\begin{matrix} \tilde{B} (\tilde{x}, y^{″}) = B (\tilde{x}, B^{'} (A (\tilde{x}), y^{″})) = B (\tilde{x}, B^{'} (A (x), y^{″})) = B (x, B^{'} (A (x), y^{″}) = \tilde{B} (x, y^{″}), \end{matrix}$ We have shown that the function $\tilde{B}$ is very good. Next, let us consider some $x \in dom (f)$ . We wish to show that $\tilde{B} (x, f^{″} (\tilde{A} (x)))$ is defined and that $f (x) ⪯ \tilde{B} (x, f^{″} (\tilde{A} (x)))$ . Indeed, from $x \in dom (f)$ we conclude first $x \in dom (A)$ and $A (x) \in dom (f^{'})$ . And from $A (x) \in dom (f^{'})$ we conclude $A (x) \in dom (A^{'})$ and $A^{'} (A (x)) \in dom (f^{″})$ . Hence, $x \in dom (\tilde{A})$ and $\tilde{A} (x) \in dom (f^{″})$ . Furthermore, from $A (x) \in dom (f^{'})$ we obtain $(A (x), f^{″} (A^{'} (A (x)))) \in dom (B^{'})$ . Finally, as $B (x, \cdot)$ is good, $(x, f^{'} (A (x))) \in dom (B)$ , and $f^{'} (A (x)) ⪯^{'} B^{'} (A (x), f^{″} (A^{'} (A (x))))$ , we obtain $(x, B^{'} (A (x), f^{″} (A^{'} (A (x))))) \in dom (B)$ . Hence, $\tilde{B} (x, f^{″} (\tilde{A} (x))) = B (x, B^{'} (A (x)), f^{″} (A^{'} (A ((x)))))$ is defined. We obtain $\begin{matrix} f (x) ⪯ B (x, f^{'} (A (x))) ⪯ B (x, B^{'} (A (x), f^{″} (A^{'} (A (x))))) = \tilde{B} (x, f^{″} (\tilde{A} (x))) . \end{matrix}$ Finally, let us consider some $y^{″} \in dom (C \circ C^{'})$ and some $x \in X$ with $(x, y^{″}) \in dom (\tilde{B})$ . Then $y^{″} \in dom (C^{'})$ , $C^{'} (y^{″}) \in dom (C)$ , $x \in dom (A)$ , $(A (x), y^{″}) \in dom (B^{'})$ , $(x, B^{'} (A (x), y^{″})) \in dom (B)$ , and we obtain $\begin{matrix} \tilde{B} (x, y^{″}) = B (x, B^{'} (A (x), y^{″})) = B (x, C^{'} (y^{″})) = C (C^{'} (y^{″})) . \end{matrix}$ □
Corollary 5.15.
The relation $⪯_{2}$ is a preorder.
Proof.
The transitivity follows from Lemma 5.14.1. The reflexivity follows from the reflexivity of $⪯_{0}$ and from Lemma 5.13.3. □

Using $⪯_{2}$ one can express the naive Weihrauch reducibility $⩽_{2}$ for functions with finite discrete range as follows.
Lemma 5.16.
Let X, $X^{'}$ be topological spaces, let Y be a discrete topological space, and let $Y^{'}$ be a finite discrete topological space. Let ⪯ on Y and $⪯^{'}$ on $Y^{'}$ be simply the equality relation on Y respectively on $Y^{'}$ . Then for any functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ the following two conditions are equivalent.
$f ⩽_{2} f^{'}$ ,

$f ⪯_{2} f^{'}$ .

Proof.
It is sufficient to observe that a function $B : \subseteq X \times Y^{'} \to Y$ is very good if, and only if, it is continuous. □

In fact, with $⪯_{2}$ one can even express the naive Weihrauch reducibility relation $⩽_{2}$ between relations with finite discrete range.
Lemma 5.17.
Let X, $X^{'}$ be topological spaces, let Y be a discrete topological space, and let $Y^{'}$ be a finite discrete topological space. Let $R \subseteq X \times Y$ and $R^{'} \subseteq X^{'} \times Y^{'}$ be relations. Then the following two conditions are equivalent.
$R ⩽_{2} R^{'}$ ,

$F_{R} \supseteq_{2} F_{R^{'}}$ .

Here, the second condition is based on the functions $F_{R}$ , $F_{R^{'}}$ associated with the relations R, $R^{'}$ as in Section 2.2 and on the partially ordered sets $(P {(Y)}_{\neq \emptyset}, \supseteq)$ and $(P {(Y^{'})}_{\neq \emptyset}, \supseteq)$ . In this case we write $\supseteq_{2}$ for $⪯_{2}$ , similarly as before. Proof.
“ $1 \Rightarrow 2$ ”: Let $I : \subseteq X \to X^{'}$ and $O : \subseteq X \times Y^{'} \to Y$ be continuous functions such that $O \circ (i d_{X}, R^{'} \circ I)$ is a refinement of R. We define the function $A : \subseteq X^{'} \to X$ by $A : = I$ and the function $B : \subseteq X \times P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ by $\begin{array}{l} dom (B) : = {(x, M^{'}) \in X \times P {(Y^{'})}_{\neq \emptyset} : {x} \times M^{'} \subseteq dom (O)}, \\ B (x, M^{'}) : = O [{x} \times M^{'}], \end{array}$ for $(x, M^{'}) \in dom (B)$ . It is clear that A is continuous. On $P {(Y)}_{\neq \emptyset}$ and on $P {(Y^{'})}_{\neq \emptyset}$ we consider the preorder ⊇. Then it is clear that for every $x \in X$ the function $B (x, \cdot)$ is good. The facts that O is continuous and that $Y^{'}$ is a finite discrete topological space imply that B is very good. Let us consider some $x \in dom (R)$ . Then $x \in dom (I) = dom (A)$ , $A (x) = I (x) \in dom (R^{'}) = dom (F_{R^{'}})$ , ${x} \times R^{'} [I (x)] \subseteq dom (O)$ , hence $(x, F_{R^{'}} (A (x))) \in dom (B)$ , and for all $y \in R^{'} [I (x)] = F_{R^{'}} (A (x))$ we have $O (x, y) \in R [x]$ , hence $F_{R} (x) = R [x] \supseteq O [{x} \times R^{'} [I (x)]] = B (x, F_{R^{'}} (A (x)))$ .

“ $2 \Rightarrow 1$ ”: Again, on $P {(Y)}_{\neq \emptyset}$ and on $P {(Y^{'})}_{\neq \emptyset}$ we consider the preorder ⊇. Let $A : \subseteq X \to X^{'}$ be a continuous function and $B : \subseteq X \times P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ be a very good function that show $F_{R} ⪯_{2} F_{R^{'}}$ , that is, with $\begin{array}{l} dom (F_{R}) \subseteq dom (B \circ ({id}_{X}, (F_{R^{'}} \circ A))) and \\ (\forall x \in dom (F_{R})) (F_{R} (x) ⪯ B (x, F_{R^{'}} (A (x))) . \end{array}$ We define the function $I : \subseteq X \to X^{'}$ by $I : = A$ . Then I is continuous. Let $S : P {(Y)}_{\neq \emptyset} \to Y$ be a selection function, that is, a function such that, for all $M \in P {(Y)}_{\neq \emptyset}$ , $S (M) \in M$ . We define the function $O : \subseteq X \times Y^{'} \to Y$ by $\begin{array}{l} dom (O) : = {(x, y^{'}) \in X \times Y^{'} : (x, {y^{'}}) \in dom (B)}, \\ O (x, y^{'}) : = S (B (x, {y^{'}})), \end{array}$ for $(x, y^{'}) \in dom (O)$ . The fact that B is very good implies that O is continuous. We claim that $O \circ (i d_{X}, R^{'} \circ I)$ is a refinement of R. Let us consider some $x \in dom (R)$ . Remember that $dom (F_{R}) = dom (R)$ . We obtain $x \in dom (A) = dom (I)$ and $I (x) = A (x) \in dom (F_{R^{'}}) = dom (R^{'})$ . Furthermore, we obtain $(x, F_{R^{'}} (x)) \in dom (B)$ . As for all $x \in X$ the function $B (x, \cdot)$ is good this implies for all $y^{'} \in F_{R^{'}} (x) = R^{'} [x]$ that $(x, {y^{'}}) \in dom (B)$ , hence $(x, y^{'}) \in dom (O)$ , hence, ${x} \times R^{'} [I (x)] \subseteq dom (O)$ . Finally, again because $B (x, \cdot)$ is good, we obtain, for all $y^{'} \in R^{'} [I (x)]$ , $\begin{matrix} O (x, y^{'}) \in B (x, {y^{'}}) \subseteq B (x, R^{'} [I (x)]) = B (x, F_{R^{'}} (A (x))) \subseteq F_{R} (x) = R [x] . \end{matrix}$ We have shown that $O \circ (i d_{X}, R^{'} \circ I)$ is a refinement of R. □

6. Better-quasi-orders

A relation ⪯ on a set Y is called a well-quasi-order if it is a preorder and for every infinite sequence ${(y_{i})}_{i \in N}$ of elements of X there is at least one pair $i, j \in N$ of numbers with $i < j$ and $y_{i} ⪯ y_{j}$ . In particular, any well-quasi-order is well-founded. This is a natural notion, but it turned out that it does not have as good closure properties as one might hope. Nash-Williams [15] therefore introduced a slightly stronger notion, so-called better-quasi-orderings and was able to show for several preorders, for which it was unknown whether they were well-quasi-orders or not, that they are in fact even better-quasi-orders. We will need a result by Lavers [14] that strengthens a result by Nash-Williams and shows that a certain relation on forests whose nodes are labeled with elements from a better-quasi-ordered set is again a better-quasi-order. In the following we give a definition of better-quasi-orders that can easily be shown to be equivalent to the original definition by Nash-Williams [15].

For any infinite set $A \subseteq N$ let $A^{(ω)}$ denote the set of all infinite subsets of X. The mapping $\begin{matrix} {[2]}^{N} \to P (N), s \mapsto s^{- 1} (1) \end{matrix}$ is a bijection. Via this bijection, for any infinite subset $A \subseteq N$ the set $A^{(ω)}$ can be considered as a subset of ${[2]}^{N}$ . In the following we will on $A^{(ω)}$ consider always the relative topology induced by the product topology on ${[2]}^{N}$ . Let $(Y, ⪯)$ be a preordered set. On Y we consider the discrete topology. Any function $f : A^{(ω)} \to Y$ , for any $A \in N^{(ω)}$ , is called a Y-array. A Y-array $f : A^{(ω)} \to Y$ is called good if there exists a $B \in A^{(ω)}$ such that $f (B) ⪯ f (B ∖ {min (B)})$ . Otherwise it is called bad. The relation ⪯ is called a better-quasi-order (bqo for short) if every continuous Y-array is good. Then we call the pair $(Y, ⪯)$ a better-quasi-ordered set or bqo set.

Concerning the considered Y-arrays, this notion is surprisingly stable. We just remark that one arrives at the same notion if on $X^{(ω)}$ one uses the Ellentuck topology instead of the relative topology of the product topology. One might as well consider Borel measurable Y-arrays; see [21].

We will need the following assertions. All of them are well known; see, e.g., [14,21].

Lemma 6.1.

Let Y be a set, and let ⪯ and $⪯^{'}$ be two preorders on Y such that, for all $y_{1}, y_{2} \in Y$ , if $y_{1} ⪯ y_{2}$ then $y_{1} ⪯^{'} y_{2}$ . If ⪯ is a bqo then so is $⪯^{'}$ .

If $(Y, ⪯)$ is a bqo set and $Z \subseteq Y$ a subset of Y then the restriction $⪯ | Z$ of ⪯ to Z is a bqo as well.

If $(Y, ⪯)$ is a bqo set then the induced preorder ⪯ on the set of ≡-classes of elements in Y is a bqo as well.

Every finite preorder is a bqo.

Every bqo is a well-quasi-order.

For a preordered set $(Y, ⪯)$ we define a relation $⪯_{P}$ on $P (Y)$ by $\begin{matrix} A ⪯_{P} B : ⟺ (\forall a \in A) (\exists b \in B) a ⪯ b, \end{matrix}$ for $A, B \in P (Q)$ . It is clear that $⪯_{P}$ is a preorder as well.
Lemma 6.2.
If $(Y, ⪯)$ is a bqo set then $(P (Y), ⪯_{P})$ is a bqo set as well.

This is well-known as well; see [14,15,21].
7. Labeled forests and reducibilities on them

In this section we introduce labeled trees and relations $⪯_{0}$ , $⪯_{1}$ , $⪯_{1}^{C}$ , $⪯_{2}$ , and $⪯_{2}^{C}$ on labeled trees. These notions generalize correspondings notions for finite labeled trees in [6–8]. Note that in [9] a complexity-theoretic analysis of the restrictions of $⪯_{0}$ , $⪯_{1}$ , and $⪯_{2}$ to certain finite labeled trees has been carried out. Infinite labeled trees (and labeled posets) and suitable versions of $⪯_{0}$ have been considered by Selivanov in several papers, for example in [18–20].

7.1. A reducibility on labeled forests corresponding to Wadge reducibility on functions

In descriptive set theory and set theory there are various kinds of definitions of trees; see e.g. [3,11]. We will need only two special classes of trees and will use a terminology convenient for our needs. Remember that we call a subset $C \subseteq S$ of a poset $(S, ⩽)$ a chain if the restriction $⩽ | C$ of ⩽ to C is a linear order. For a subset S of $N^{< ω}$ , usually we will write the restriction $⊑ | S$ of the prefix relation ⊑ to S simply as ⊑.

Definition 7.1.

A forest is a subset S of $N^{< ω}$ such that any ⊑-chain $C \subseteq S$ is finite.

A tree is a forest S that has a ⊑-smallest element. This will be called the root of the forest and will be written $root (S) : = {min}_{⊑} (S)$

Note that we do not demand that the set S is a ⊑-downwards closed set. One could demand that, but it would make the proofs of some lemmas later on more cumbersome. If S is a subset of $N^{< ω}$ then for all $s \in S$ the set ${t \in S : t ⊑ s}$ is a chain. Remember that ⊒ is another name for the relation $⊑^{- 1}$ . Note also that for a subset S of $N^{< ω}$ the condition that any chain $C \subseteq S$ is finite is equivalent to demanding that the relation $⊒ | S$ on S is well-founded. Hence, if S is a forest then, for any $t \in S$ , the ordinal ${rank}_{⊒ | S} (t)$ of t in S is well-defined and a countable ordinal. We call it the rank of t in S and will write it ${rank}_{S} (t)$ . Let us call the ordinal $rank (S, ⊒ | S)$ the rank of the forest S. We will just write it $rank (S)$ . This is a countable ordinal as well. Note that, for any tree S, its rank $rank (S)$ is a successor ordinal (it is equal to $rank (root (S)) + 1$ ).

Let Y be a set. A labeled forest (resp. tree) with labels in Y is a pair $(S, λ)$ such that S is a forest (resp. a tree) and $λ : S \to Y$ is a function. The function λ will be called the labeling function. For any $t \in S$ the value $λ (t) \in Y$ will be called the label of t. Let $Forests (Y)$ be the set of all forests with labels in Y and let $Trees (Y)$ be the set of all trees with labels in Y. For any $F = (S, λ) \in Forests (Y)$ , we define the rank of F by $rank (F) : = rank (S)$ .
Definition 7.2.
Let $(Y, ⪯)$ be a preordered set.
Let $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y)$ be labeled forests with labels in Y. A monotone (with respect to ⊑ on S and on $S^{'}$ ) function $h : S \to S^{'}$ satisfying $\begin{matrix} (\forall s \in S) λ (s) ⪯ λ^{'} (h (s)) \end{matrix}$ is called a morphism from F to $F^{'}$ .

We define a relation $⪯_{0}$ on $Forests (Y)$ as follows. For any labeled forests F and $F^{'}$ with labels in Y, $F ⪯_{0} F^{'}$ iff there exists a morphism from F to $F^{'}$ .

It is obvious that $⪯_{0}$ is reflexive and transitive. Let $\equiv_{0}$ be the equivalence relation induced by $⪯_{0}$ on $Forests (Y)$ , let $Forestclasses (Y)$ be the set of all $\equiv_{0}$ -equivalence classes of elements of $Forests (Y)$ , and let $Treeclasses (Y)$ be the set of all $\equiv_{0}$ -equivalence classes of elements of $Trees (Y)$ . Remember that the partial order relation on $Forestclasses (Y)$ induced by $⪯_{0}$ will be denoted $⪯_{0}$ as well. For any class $F \in Forestclasses (Y)$ of labeled forests let us define its rank by $\begin{matrix} rank (F) : = min {rank (F) : F \in F} . \end{matrix}$ Again, this is always a countable ordinal.
Lemma 7.3.
Let $(Y, ⪯)$ be a preordered set. For any countable set $M \subseteq Forestclasses (Y)$ the supremum ${sup}_{⪯_{0}} (M)$ exists.
Proof.
If M is empty then the $\equiv_{0}$ -class of the empty labeled forest $(\emptyset, \emptyset)$ is the $⪯_{0}$ -supremum of M. Let us assume that M is not empty and that $M = {F_{i} : i \in I}$ , for some subset $I \subseteq N$ . For every $i \in I$ we choose a forest $(S_{i}, λ_{i}) \in F_{i}$ . We define a new forest $(S, λ)$ by $\begin{array}{l} S : = ⋃_{i \in I} {i s : s \in S_{i}}, \\ λ (i s) : = λ_{i} (s), for i \in I and s \in S_{i} . \end{array}$ It is straightforward to check that $F : = (S, λ)$ is a labeled forest with labels in Y and that the $\equiv_{0}$ -equivalence class of F is a $⪯_{0}$ -supremum of M. □
Lemma 7.4.
Let $(Y, ⪯)$ be a preordered set. For any $F \in Forestclasses (Y)$ there exists a countable set $M \subseteq Treeclasses (Y)$ with $F = {sup}_{⪯_{0}} (M)$ and with $rank (F) = sup {rank (T) : T \in M}$ .
Proof.
We choose a forest $F = (S, λ) \in F$ with $rank (F) = rank (F)$ . For each $s \in S$ , $\begin{matrix} F_{s, ⊑} : = (S \cap s^{⊑}, λ |_{S \cap s^{⊑}}) \end{matrix}$ is a labeled tree with labels in Y. Let $F_{s}$ be the treeclass of $F_{s, ⊑}$ . Then $M : = {F_{s} : s \in S}$ is a countable subset of $Treeclasses (Y)$ with $F = {sup}_{⪯_{0}} (M)$ and with $rank (F) = sup {rank (T) : T \in M}$ . □

Let $(Y, ⪯)$ be a preordered set. Let $tree : Y \times Forests (Y) \to Trees (Y)$ be the function defined as follows. For $y \in Y$ and $F = (S, λ) \in Forests (Y)$ let $tree (y, F)$ be the tree $(S^{'}, λ^{'})$ defined by: $\begin{array}{l} S^{'} : = {ε} \cup 0 S, \\ λ^{'} (ε) : = y, \\ λ^{'} (0 s) : = λ (s), for s \in S . \end{array}$ So, ε is the root of the tree and has the label y, and the labeled forest F is appended to this root.
Lemma 7.5.
Let $(Y, ⪯)$ be a preordered set. For any $y, y^{'} \in Y$ and any $F, F^{'} \in Forests (L)$ ,
if $y ⪯ y^{'}$ and $F ⪯_{0} F^{'}$ , then $tree (y, F) ⪯_{0} tree (y^{'}, F^{'})$ ,

if $y \equiv y^{'}$ and $F \equiv_{0} F^{'}$ , then $tree (y, F) \equiv_{0} tree (y, F^{'})$ .

We omit the obvious proof. This lemma allows us to define a function $treeclass : Y \times Forestclasses (Y) \to Treeclasses (Y)$ as follows: $\begin{matrix} treeclass (y, F) : = the \equiv_{0} -class of tree (y, F) where F is an arbitrary element of F, \end{matrix}$ for any $y \in Y$ and $F \in Forestclasses (Y)$ .

In the following proof we use the following notation. For a labeled forest $F = (S, λ)$ and an element $s \in S$ we define $\begin{array}{l} F_{s, ⊏} : = (S \cap s^{⊏}, λ |_{S \cap s^{⊏}}), \\ F_{s, ⊑} : = (S \cap s^{⊑}, λ |_{S \cap s^{⊑}}) . \end{array}$ Then $F_{s, ⊏}$ is a labeled forest, $F_{s, ⊑}$ is a labeled tree, $F_{s, ⊏} ⪯_{0} F_{s, ⊑}$ , and $F_{s, ⊑} \equiv_{0} tree (λ (s), F_{s, ⊏})$ .
Lemma 7.6.
Let $(Y, ⪯)$ be a preordered set. Let $T \in Treeclasses (Y)$ . Then there exist $y \in Y$ and $F \in Forestclasses (Y)$ with $T = treeclass (y, F)$ , with $F ≺_{0} T$ , and with $rank (T) = rank (F) + 1$ .
Proof.
Let us fix some tree $T \in T$ and some forest $G = (S, λ) \in T$ with $rank (G) = rank (T)$ . Then $T \equiv_{0} G$ . Let r be the root of T. The set $\begin{matrix} M : = {s \in S : there exists a morphism h from T to G with s ⊑ h (r)} \end{matrix}$ is not empty. As $(S, ⊒)$ is well-founded there exists a ⊒-minimal element $s \in M$ , that means, an element $s \in M$ such that, for all $t \in T$ , if $s ⊏ t$ then $t \notin M$ . We have $T ⪯_{0} G_{s, ⊑}$ . As $G_{s, ⊑} ⪯_{0} G \equiv_{0} T$ is clear, we obtain $T \equiv_{0} G_{s, ⊑}$ . Let $y : = λ (s)$ , and let $F$ be the $\equiv_{0}$ -class of $G_{s, ⊏}$ . Then $T = treeclass (y, F)$ . It is clear that $F ⪯_{0} T$ . If we had $T ⪯_{0} F$ then we would have $T ⪯_{0} G_{s, ⊏}$ , hence, there would be a morphism from T to $G_{s, ⊏}$ . But then there would also be a morphism g from T to G with $s ⊏ g (r)$ , which is in contradiction to the definition of s. Hence, $F ≺_{0} T$ . For the rank we obtain the following estimates. On the one hand, $T = treeclass (y, F)$ implies $rank (T) ⩽ rank (F) + 1$ . On the other hand we have $\begin{matrix} rank (F) + 1 ⩽ rank (G_{s, ⊏}) + 1 ⩽ rank (G) = rank (T) . \end{matrix}$ Together we obtain $rank (T) = rank (F) + 1$ . □

The following proposition is a corollary of a stronger result by Laver [14]. Proposition 7.7 (Laver [14]).

Let $(Y, ⪯)$ be a bqo set. Then the preorder $⪯_{0}$ on $Forests (Y)$ is a bqo.

Corollary 7.8.
Let $(Y, ⪯)$ be a bqo set. Then the partial order $⪯_{0}$ on $Forestclasses (Y)$ is a bqo.
Proof.
This follows from the previous proposition and from Lemma 6.1.3. □

7.2. A reducibility on labeled forests corresponding to Weihrauch reducibility on functions

In this section $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ are arbitrary preordered sets unless they are explicitly defined to be something else.

Definition 7.9.
Let $S \subseteq N^{< ω}$ be a forest. We call a function $o : \subseteq S \times Y^{'} \to Y$ very good if $\begin{array}{l} (\forall s \in s) o (s, \cdot) is good and \\ (\forall s_{1}, s_{2} \in S) (\forall y^{'} \in Y^{'}) (if (s_{1} ⊑ s_{2} and (s_{1}, y^{'}) \in dom (o) and (s_{2}, y^{'}) \in dom (o)) then o (s_{1}, y^{'}) = o (s_{2}, y^{'})) . \end{array}$
Definition 7.10.

Let $C : \subseteq Y^{'} \to Y$ be a good function. We define a relation $⪯_{2}^{C} \subseteq Forests (Y) \times Forests (Y^{'})$ as follows. For any labeled forests $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ , $\begin{array}{l} F ⪯_{2}^{C} F^{'} : ⟺ \\ there exist a monotone function h : S \to S^{'} and \\ a very good function o : \subseteq S \times Y^{'} \to Y such that \\ (\forall s \in S) ((s, λ^{'} (h (s)) \in dom (o) and λ (s) ⪯ o (s, λ^{'} (h (s))))) \\ and (\forall y^{'} \in dom (C)) (\forall s \in S) (if (s, y^{'}) \in dom (o) then o (s, y^{'}) = C (y^{'})) . \end{array}$

We define a relation $⪯_{2} \subseteq Forests (Y) \times Forests (Y^{'})$ as follows. For any labeled forests $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ , $\begin{matrix} F ⪯_{2} F^{'} : ⟺ F ⪯_{2}^{\emptyset} F^{'} \end{matrix}$ where ∅ is the partial function from $Y^{'}$ to Y with empty domain of definition.

First, we observe that the relation $⪯_{2}^{C}$ generalizes the relation $⪯_{0}$ introduced in Sections 7.1.
Lemma 7.11.
Let $F \in Forests (Y)$ and $F^{'} \in Forests (Y)$ be labeled forests. Then $\begin{matrix} F ⪯_{0} F^{'} ⟺ F ⪯_{2}^{{id}_{Y}} F^{'} . \end{matrix}$
Proof.
This follows directly from the definitions. □

Next, we formulate some properties of the relation $⪯_{2}^{C}$ .
Lemma 7.12.
Let $C : \subseteq Y^{'} \to Y$ and $\tilde{C} : \subseteq Y^{'} \to Y$ be good functions such that $\tilde{C}$ is an extension of C. Then for two labeled forests, $F \in Forests (Y)$ and $F^{'} \in Forests (Y^{'})$ , if $F ⪯_{2}^{\tilde{C}} F^{'}$ then $F ⪯_{2}^{C} F^{'}$ .

This is obvious. We omit the proof.
Lemma 7.13.
Let $(Y, ⪯)$ , $(Y^{'}, ⪯^{'})$ , $(Y^{″}, ⪯^{″})$ be preordered sets. Let $C : \subseteq Y^{'} \to Y$ and $C^{'} : \subseteq Y^{″} \to Y^{'}$ be good functions. Let $F \in Forests (Y)$ , $F^{'} \in Forests (Y^{'})$ , $F^{″} \in Forests (Y^{″})$ be labeled forests.
If $F ⪯_{2}^{C} F^{'}$ and $F^{'} ⪯_{2}^{C^{'}} F^{″}$ then $F ⪯_{2}^{C \circ C^{'}} F^{″}$ .

If $(Y, ⪯) = (Y^{'}, ⪯^{'})$ then: if $F ⪯_{0} F^{'}$ and $F^{'} ⪯_{2}^{C^{'}} F^{″}$ then $F ⪯_{2}^{C^{'}} F^{″}$ .

If $(Y^{'}, ⪯^{'}) = (Y^{″}, ⪯^{″})$ then: if $F ⪯_{2}^{C} F^{'}$ and $F^{'} ⪯_{0} F^{″}$ then $F ⪯_{2}^{C} F^{″}$ .

Proof.
Due to Lemma 7.11 the second and the third assertion are special cases of the first assertion.

Let us prove the first assertion. Let $F = (S, λ)$ , $F^{'} = (S^{'}, λ^{'})$ , $F^{″} = (S^{″}, λ^{″})$ . Let $h : S \to S^{'}$ be a monotone function and $o : \subseteq S \times Y^{'} \to Y$ be a very good function such that $\begin{array}{l} (\forall s \in S) ((s, λ^{'} (h (s)) \in dom (o) and λ (s) ⪯ o (s, λ^{'} (h (s))))) \\ and (\forall y^{'} \in dom (C)) (\forall s \in S) (if (s, y^{'}) \in dom (o) then o (s, y^{'}) = C (y^{'}) . \end{array}$ Let $h^{'} : S^{'} \to S^{″}$ be a monotone function and $o : \subseteq S^{'} \times Y^{″} \to Y^{'}$ be a very good function such that $\begin{array}{l} (\forall s^{'} \in S^{'}) ((s^{'}, λ^{″} (h^{'} (s^{'})) \in dom (o^{'}) and λ^{'} (s^{'}) ⪯ o^{'} (s^{'}, λ^{″} (h^{'} (s^{'}))))) \\ and (\forall y^{″} \in dom (C^{'})) (\forall s^{'} \in S^{'}) (if (s^{'}, y^{″}) \in dom (o^{'}) then o^{'} (s^{'}, y^{″}) = C^{'} (y^{″}) . \end{array}$ We define a function $\tilde{h} : S \to S^{″}$ by $\tilde{h} : = h^{'} \circ h$ . We define a function $\tilde{o} : \subseteq S \times Y^{″} \to Y$ by $\begin{array}{l} dom (\tilde{o}) : = {(s, y^{″}) \in S \times Y^{″} : (h (s), y^{″}) \in dom (o^{'}) and (s, o^{'} (h (s), y^{″})) \in dom (o)}, \\ \tilde{o} (s, y^{″}) : = o (s, o^{'} (h (s), y^{″})), \end{array}$ for $(s, y^{″}) \in dom (\tilde{o})$ . We claim that these functions $\tilde{h}$ and $\tilde{o}$ show $F ⪯^{C \circ C^{'}} F^{″}$ . Indeed, $\tilde{h}$ is monotone. It is clear as well that for every $s \in S$ the function $\tilde{o} (s, \cdot)$ is good. Let $s_{1}, s_{2} \in S$ and $y^{″} \in Y^{″}$ be with $s_{1} ⊑ s_{2}$ , with $(s_{1}, y^{″}) \in dom (\tilde{o})$ and with $(s_{2}, y^{″}) \in dom (\tilde{o})$ . Then $h (s_{1}) ⊑ h (s_{2})$ , hence, $o^{'} (h (s_{1}), y^{″}) = o^{'} (h (s_{2}), y^{″})$ , and $\begin{matrix} \tilde{o} (s_{1}, y^{″}) = o (s_{1}, o^{'} (h (s_{1}), y^{″})) = o (s_{2}, o^{'} (h (s_{2}), y^{″})) = \tilde{o} (s_{2}, y^{″}) . \end{matrix}$ Hence, $\tilde{o}$ is very good. Next, let us consider some $s \in S$ . Then $(s, λ^{'} (h (s))) \in dom (o)$ and $(h (s), λ^{″} (h^{'} (h (s)))) \in dom (o^{'})$ . As $λ^{'} (h (s)) ⪯ o^{'} (h (s), λ^{″} (h^{'} (h (s))))$ and $o (s, \cdot)$ is good, we obtain $(s, o^{'} (h (s), λ^{″} (h^{'} (h (s))))) \in dom (o)$ , hence $(s, λ^{″} (\tilde{h} (s))) \in dom (\tilde{o})$ . Furthermore, $\begin{matrix} λ (s) ⪯ o (s, λ^{'} (h (s))) ⪯ o (s, o^{'} (h (s), λ^{″} (h^{'} (h (s))))) = \tilde{o} (s, λ^{″} (\tilde{h} (s))) . \end{matrix}$ Finally, let us consider some $y^{″} \in dom (C \circ C^{'})$ and some $s \in S$ with $(s, y^{″}) \in dom (\tilde{o})$ . Then $y^{″} \in dom (C^{'})$ and $C^{'} (y^{″}) \in dom (C)$ and $(h (s), y^{″}) \in dom (o^{'})$ , hence, $o^{'} (h (s), y^{″}) = C^{'} (y^{″})$ . We obtain $\begin{matrix} \tilde{o} (s, y^{″}) = o (s, o^{'} (h (s), y^{″})) = o (s, C^{'} (y^{″})) = C (C^{'} (y^{″})) . \end{matrix}$ □
Corollary 7.14.
The relation $⪯_{2}$ is a preorder.
Proof.
The transitivity follows from Lemma 7.13.1. The reflexivity follows from the reflexivity of $⪯_{0}$ and from Lemma 7.11. □
Corollary 7.15.
Let $F, G \in Forests (Y)$ be $\equiv_{0}$ -equivalent, and let $F^{'}, G^{'} \in Forests (Y^{'})$ be $\equiv_{0}$ -equivalent.
If $C : \subseteq Y^{'} \to Y$ is a good function then: $F ⪯_{2}^{C} F^{'} ⟺ G ⪯_{2}^{C} G^{'}$ .

$F ⪯_{2} F^{'} ⟺ G ⪯_{2} G^{'}$ .

Proof.
The first assertion follows from Lemma 7.11 and from Lemma 7.13. The second assertion follows directly from the first assertion. □

Hence, for any good function $C : \subseteq Y^{'} \to Y$ the relation $⪯_{2}^{C}$ resp. the relation $⪯_{2}$ on forests induces a natural relation on $\equiv_{0}$ -classes which we denote by $⪯_{2}^{C}$ resp. by $⪯_{2}$ as well: for $F \in Forestclasses (Y)$ and $F^{'} \in Forestclasses (Y^{'})$ we define $\begin{matrix} F ⪯_{2}^{C} F^{'} : ⟺ F ⪯_{2}^{C} F^{'} \end{matrix}$ and $\begin{matrix} F ⪯_{2} F^{'} : ⟺ F ⪯_{2} F^{'} \end{matrix}$ where $F \in F$ and $F^{'} \in F^{'}$ are arbitrary representants of the $\equiv_{0}$ -classes $F$ and $F^{'}$ .
Lemma 7.16.
Let $C : \subseteq Y^{'} \to Y$ be a good function. For any countable set $M^{'} \subseteq Forestclasses (Y^{'})$ and any $T \in Treeclasses (Y)$ with $T ⪯_{2}^{C} {sup}_{⪯_{0}^{'}} (M^{'})$ there exists a forestclass $F^{'} \in M^{'}$ with $T ⪯_{2}^{C} F^{'}$ .
Proof.
We choose a tree $T = (S_{T}, λ_{T}) \in T$ . Let $M^{'} = {F_{i}^{'} : i \in I}$ , for some $I \subseteq N$ , where $F_{i}^{'} \in Forestclasses (Y^{'})$ , for all $i \in I$ . For every $i \in I$ we choose a forest $F_{i}^{'} = (S_{i}^{'}, λ_{i}^{'}) \in F_{i}^{'}$ . We define a new forest $F^{'} = (S^{'}, λ^{'})$ by $\begin{array}{l} S^{'} : = ⋃_{i \in I} {i s^{'} : s^{'} \in S_{i}^{'}}, \\ λ^{'} (i s^{'}) : = λ_{i} (s^{'}), for i \in I and s^{'} \in S_{i}^{'} . \end{array}$ In the proof of Lemma 7.3 we have seen that $F^{'} \in {sup}_{⪯_{0}^{'}} (M^{'})$ , that is, the $\equiv_{0}^{'}$ -class of $F^{'}$ is the $⪯_{0}^{'}$ -supremum of $M^{'}$ . Hence, $T ⪯_{2}^{C} F^{'}$ . Let $h : S_{T} \to S^{'}$ be a monotone map and $o : \subseteq S_{T} \times Y^{'} \to Y$ be a very good map that show $F ⪯_{2}^{C} F^{'}$ . Let $r \in S_{T}$ be the root of T. Then there is a unique $i \in N$ with $h (r) \in i S_{i}^{'}$ . This implies $h (s) \in i S_{i}^{'}$ for all $s \in S_{T}$ , hence, $T ⪯_{2}^{C} F_{i}^{'}$ , hence, $T ⪯_{2}^{C} F_{i}^{'}$ . □
Lemma 7.17.
Let $C : \subseteq Y^{'} \to Y$ be a good function. Let $M \subseteq Forestclasses (Y)$ be a countable set of forest classes and let $F^{'} \in Forestclasses (Y^{'})$ be a forest class such that $F ⪯_{2}^{C} F^{'}$ for all $F \in M$ . Then ${sup}_{⪯_{0}} (M) ⪯_{2}^{C} F^{'}$ .
Proof.
This is obvious from the construction of a forest in ${sup}_{⪯_{0}} (M)$ given in the proof of Lemma 7.3. □

The following technical statement will be used in several proofs later on.
Lemma 7.18.
Let $C : \subseteq Y^{'} \to Y$ be a good function. Let $y \in Y$ and $y^{'} \in Y^{'}$ . Let $F \in Forestclasses (Y)$ and $F^{'} \in Forestclasses (Y^{'})$ . If $\begin{matrix} treeclass (y, F) ⪯_{2}^{C} treeclass (y^{'}, F^{'}) but treeclass (y, F) ⋠_{2}^{C} F^{'} \end{matrix}$ then
there exists a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C with $y^{'} \in dom (\tilde{C})$ , with $y ⪯ \tilde{C} (y^{'})$ , and with $treeclass (y, F) ⪯_{2}^{\tilde{C}} treeclass (y^{'}, F^{'})$ ,

and in the case $y^{'} \in dom (C)$ we obtain $y ⪯ C (y^{'})$ .

Proof.
Let us fix a forest $F \in F$ and let us assume $(S, λ) = tree (y, F)$ . Second, let us fix a forest $F^{'} \in F^{'}$ and let us assume $(S^{'}, λ^{'}) = tree (y^{'}, F^{'})$ . Third, let us fix a monotone function $h : S \to S$ and a very good function $o : \subseteq S \times Y^{'} \to Y$ that show $tree (y, F) ⪯_{2}^{C} tree (y^{'}, F^{'})$ . The assumption $treeclass (y, F) ⋠_{2}^{C} F^{'}$ implies that h maps the root r of $tree (y, F)$ to the root $r^{'}$ of $tree (y^{'}, F^{'})$ . This implies $y = λ (r) ⪯ o (r, λ^{'} (h (r))) = o (r, y^{'})$ . We define an extension $\tilde{C} : \subseteq Y^{'} \to Y$ by $dom (\tilde{C}) : = dom (C) \cup {(y^{'})}^{⪯^{'}}$ and $\begin{matrix} \tilde{C} (z^{'}) : = \{\begin{matrix} C (z^{'}) & if z^{'} \in dom (C), \\ o (r, z^{'}) & if z^{'} \in {(y^{'})}^{⪯^{'}}, \end{matrix} \end{matrix}$ for $z^{'} \in dom (C) \cup {(y^{'})}^{⪯^{'}}$ . This function $\tilde{C}$ is well-defined because ${(y^{'})}^{⪯^{'}} \subseteq dom (o (r, \cdot))$ (this is due to $y^{'} \in dom (o (r, \cdot))$ and the fact that $o (r, \cdot)$ is good) and, for any $z^{'} \in dom (C) \cap {(y^{'})}^{⪯^{'}}$ , $o (r, z^{'}) = C (z^{'})$ . The function $\tilde{C}$ is good because C is good and $o (r, \cdot)$ is good. We have $y = λ (r) ⪯ o (r, λ^{'} (h (r))) = o (r, y^{'}) = \tilde{C} (y^{'})$ . Finally, it is clear that the functions h and o show even $tree (y, F) ⪯_{2}^{\tilde{C}} tree (y^{'}, F^{'})$ .

For the second assertion we just need to remember that $\tilde{C}$ is an extension of C. Hence, if $y^{'} \in dom (C)$ then $y ⪯ \tilde{C} (y^{'})$ implies $y ⪯ C (y^{'})$ . □

Finally, we show that in special cases the relation $⪯_{2}$ can be expressed in a rather compact way. Let us call a poset $(Y, ⪯)$ weakly bounded-complete if ${sup}_{⪯} (Z)$ exists for every nonempty ⪯-upper bounded subset $Z \subseteq Y$ of Y.
Lemma 7.19.
Let $(Y, ⪯)$ be a weakly bounded-complete poset, and let $(Y^{'}, ⪯^{'})$ be a preordered set. Then for $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ , the following two conditions are equivalent:
$F ⪯_{2} F^{'}$ .

There exists a monotone function $h : S \to S^{'}$ such that for every subset $M \subseteq S$ having a smallest element, if $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded then $λ [M]$ is ⪯-upper bounded.

Proof.
$(1) \Rightarrow (2)$ : Let $h : S \to S^{'}$ be a monotone function and $o : \subseteq S \times Y^{'} \to Y$ be a very good function such that $\begin{matrix} (\forall s \in S) (s, λ^{'} (h (s)) \in dom (o) and λ (s) ⪯ o (s, λ^{'} (h (s)))) . \end{matrix}$ Let us consider a subset $M \subseteq S$ with a ⊑-smallest element s such that the set $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded. Let $y^{'} \in Y$ be a $⪯^{'}$ -upper bound of $λ^{'} [h [M]]$ . Consider some $t \in M$ . We have $(t, λ^{'} (h (t))) \in dom (o)$ , hence $λ^{'} (h (t)) \in dom (o (t, \cdot))$ . As $o (t, \cdot)$ is good and $λ^{'} (h (t)) ⪯^{'} y^{'}$ we obtain $y^{'} \in dom (o (t, \cdot))$ , hence, $(t, y^{'}) \in dom (o)$ and $o (t, λ^{'} (h (t))) ⪯ o (t, y^{'})$ . Furthermore, for all $t \in M$ , we have $s ⊑ t$ , hence, $o (t, y^{'}) = o (s, y^{'})$ . Summarizing this, we obtain $\begin{matrix} λ (t) ⪯ o (t, λ^{'} (h (t))) ⪯ o (t, y^{'}) = o (s, y^{'}) . \end{matrix}$ Hence, $λ [M]$ is ⪯-upper bounded by $o (s, y^{'})$ .

$(2) \Rightarrow (1)$ : Let $h : S \to S^{'}$ be a monotone function such that for every subset $M \subseteq S$ having a smallest element, if $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded then $λ [M]$ is ⪯-upper bounded. We define a function $o : \subseteq S \times Y^{'} \to Y$ as follows. Its domain of definition is the set $dom (o) : = {(s, y^{'}) \in S \times Y^{'} : λ^{'} (h (s)) ⪯^{'} y^{'}}$ . We define an additional function $f : \subseteq S \times Y^{'} \to T$ by $dom (f) : = dom (o)$ and $\begin{matrix} f (s, y^{'}) : = min {t \in S : t ⊑ s and λ^{'} (h (t)) ⪯^{'} y^{'}}, \end{matrix}$ for $(s, y^{'}) \in dom (o)$ . Note that for every $(s, y^{'}) \in dom (o)$ we have $(f (s, y^{'}), y^{'}) \in dom (o)$ as well and $f (s, y^{'}) ⊑ s$ . For $(s, y^{'}) \in dom (o)$ , the set $\begin{matrix} M_{s, y^{'}} : = {t \in S : s ⊑ t and λ^{'} (h (t)) ⪯^{'} y^{'}} \end{matrix}$ has a smallest element, namely, s, and it has the property that $λ^{'} [h [M_{s, y^{'}}]]$ is $⪯^{'}$ -upper bounded by $y^{'}$ . Hence, by assumption the set $λ [M_{s, y^{'}}]$ is ⪯-upper bounded. We define $\begin{matrix} o (s, y^{'}) : = sup_{⪯} (λ [M_{f (s, y^{'}), y^{'}}]), \end{matrix}$ for $(s, y^{'}) \in dom (o)$ . We claim that this function o in combination with the function h has all the desired properties. It is clear that for every $s \in S$ the domain of $o (s, \cdot)$ is $⪯^{'}$ -upwards closed. For $s \in S$ and $y_{1}^{'}$ , $y_{2}^{'}$ with $(s, y_{1}^{'}) \in dom (o)$ and $(s, y_{2}^{'}) \in dom (o)$ and $y_{1}^{'} ⪯^{'} y_{2}^{'}$ we have $f (s, y_{2}^{'}) ⊑ f (s, y_{1}^{'})$ , hence, the set $M_{f (s, y_{1}^{'}), y_{1}^{'}}$ is a subset of $M_{f (s, y_{2}^{'}), y_{2}^{'}}$ . That implies that the function $o (s, \cdot)$ is monotone. Hence, it is good. Consider some $s_{1}, s_{2} \in S$ and $y^{'} \in Y^{'}$ with $s_{1} ⊑ s_{2}$ , with $(s_{1}, y^{'}) \in dom (o)$ and with $(s_{2}, y^{'}) \in dom (o)$ . Then $f (s_{1}, y^{'}) = f (s_{2}, y^{'})$ , hence, $o (s_{1}, y^{'}) = o (s_{2}, y^{'})$ . We have shown that the function o is very good. Finally, it is clear that for any $s \in S$ , $(s, λ^{'} (h (s))) \in dom (o)$ . Due to $s \in M_{f (s, λ^{'} (h (s))), λ^{'} (h (s))}$ we have $λ (s) ⪯ {sup}_{⪯} (λ [M_{f (s, λ^{'} (h (s))), λ^{'} (h (s))}]) = o (s, λ^{'} (h (s)))$ . □
Remark 7.20.
The previous lemma applies in particular to the following two cases.
When the set Y is finite and the relation ⪯ is the equality relation on Y. If $(S, λ)$ is a forest with labels in Y then for some nonempty set $M \subseteq S$ the condition that $λ (M)$ is =-upper bounded just means that $λ (M)$ contains exactly one element.

When there is some finite set Z with $(Y, ⪯) = (P {(Z)}_{\neq \emptyset}, \supseteq)$ . If $(S, λ)$ is a forest with labels in Y then for some nonempty set M the condition that $λ (M)$ is ⊇-upper bounded just means that $⋂ λ (M)$ is nonempty.

In the first of the two cases considered in Remark 7.20 the relation $⪯_{2}$ can be expressed even simpler. Corollary 7.21.
Let Y be a finite set and let ⪯ be the equality relation on Y. Let $(Y^{'}, ⪯^{'})$ be a preordered set. Then for $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ , the following two conditions are equivalent:
$F ⪯_{2} F^{'}$ .

There exists a monotone function $h : S \to S^{'}$ such that for every nonempty chain $C \subseteq S$ , if $λ^{'} [h [C]]$ is $⪯^{'}$ -upper bounded then $λ [C]$ contains exactly one element.

Proof.
The implication “ $1 \Rightarrow 2$ ” follows from the previous lemma because every nonempty ⊑-chain has a ⊑-smallest element. For the implication “ $2 \Rightarrow 1$ ” let us assume that there exists a monotone function $h : S \to S^{'}$ such that for every nonempty chain $C \subseteq S$ , if $λ^{'} [h [C]]$ is $⪯^{'}$ -upper bounded then $λ [C]$ contains exactly one element. It is sufficient to show that then for every subset $M \subseteq S$ having a smallest element, if $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded then $λ [M]$ contains exactly one element. But this is true because for every such M and for every $s \in M$ the set $C_{M, s} : = {t \in M : t ⊑ s}$ is a chain containing s, is a subset of M, and satisfies ${min}_{⊑} (C_{M, s}) = {min}_{⊑} (M)$ . Hence, the assumption implies ${λ (s)} = λ [C_{M, s}] = {λ ({min}_{⊑} (C_{M, s}))}$ , and this implies $λ (s) = λ ({min}_{⊑} (C_{M, s})) = λ ({min}_{⊑} (M))$ . We obtain $λ [M] = {λ ({min}_{⊑} (M))}$ . □
Remark 7.22.
In the case, when Y and $Y^{'}$ are finite sets and ⪯ and $⪯^{'}$ are the equality relation on Y resp. on $Y^{'}$ , then the second condition in Lemma 7.19 and Corollary 7.21 is equivalent to the following condition: there exists a monotone function $h : S \to S^{'}$ such that, for any $s_{1}, s_{2} \in S$ , if $s_{1} ⊑ s_{2}$ and $λ (s_{1}) \neq λ (s_{2})$ then $λ^{'} (h (s_{1})) \neq λ^{'} (h (s_{2}))$ .

7.3. A reducibility on labeled forests corresponding to strong Weihrauch reducibility on functions

In this section $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ are arbitrary preordered sets unless they are explicitly defined to be something else.

Definition 7.23.

Let $C : \subseteq Y^{'} \to Y$ be a good function. We define a relation $⪯_{1}^{C} \subseteq Forests (Y) \times Forests (Y^{'})$ as follows. For any labeled forests $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ , $\begin{array}{rcl} F ⪯_{1}^{C} F^{'} & : ⟺ & there exists a monotone function h : S \to S^{'} such that \\ (\forall s \in S) (λ^{'} (h (s)) \in dom (C) and λ (s) ⪯ C (λ^{'} (h (s)))) . \end{array}$

We define a relation $⪯_{1} \subseteq Forests (Y) \times Forests (Y^{'})$ as follows. For any labeled forests $F \in Forests (Y)$ and $F^{'} \in Forests (Y^{'})$ , $\begin{matrix} F ⪯_{1} F^{'} : ⟺ there exists a good function C : \subseteq Y^{'} \to Y such that F ⪯_{1}^{C} F^{'} . \end{matrix}$

First, we show that the relation $⪯_{1}^{C}$ generalizes the relation $⪯_{0}$ introduced in Section 7.1 and is a strengthening of the relation $⪯_{2}^{C}$ introduced in Section 7.2.
Lemma 7.24.
Let $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ be labeled forests.
In the case $(Y^{'}, ⪯^{'}) = (Y, ⪯)$ $\begin{matrix} F ⪯_{0} F^{'} ⟺ F ⪯_{1}^{{id}_{Y}} F^{'} . \end{matrix}$

For any good function $C : \subseteq Y^{'} \to Y$ , $\begin{matrix} F ⪯_{1}^{C} F^{'} \Rightarrow F ⪯_{2}^{C} F^{'} . \end{matrix}$

For any good function $C : \subseteq Y^{'} \to Y$ with $range (λ^{'}) \subseteq dom (C)$ , $\begin{matrix} F ⪯_{1}^{C} F^{'} ⟺ F ⪯_{2}^{C} F^{'} . \end{matrix}$

Proof.

This is clear.

Let $h : S \to S^{'}$ be a monotone function such that $\forall s \in S$ , $λ^{'} (h (s)) \in dom (C)$ and $λ (s) ⪯ C (λ^{'} (h (s)))$ . We define a function $o : \subseteq S \times Y^{'} \to Y$ by $dom (o) : = S \times dom (C)$ and by $o (s, y^{'}) : = C (y^{'})$ , for all $s \in S$ and $y^{'} \in dom (C)$ . As C is good, this function is very good. The functions h and o show $F ⪯_{2}^{C} F^{'}$ .

Let $C : \subseteq Y^{'} \to Y$ be a good function with $range (λ^{'}) \subseteq dom (C)$ . It is sufficient to show that $F ⪯_{2}^{C} F^{'}$ implies $F ⪯_{1}^{C} F^{'}$ . So let us assume $F ⪯_{2}^{C} F^{'}$ . Let $F = (S, λ)$ and $F^{'} = (S^{'}, λ^{'})$ . Let $h : S \to S^{'}$ be a monotone function and $o : \subseteq S \times Y^{'} \to Y$ be a very good function such that $\begin{array}{l} (\forall s \in S) ((s, λ^{'} (h (s)) \in dom (o) and λ (s) ⪯ o (s, λ^{'} (h (s))))) \\ and (\forall y^{'} \in dom (C)) (\forall s \in S) (if (s, y^{'}) \in dom (o) then o (s, y^{'}) = C (y^{'}) . \end{array}$ We claim that h shows $F ⪯_{1}^{C} F^{'}$ . Indeed, for all $s \in S$ we have $λ^{'} (h (s)) \in dom (C)$ and $λ (s) ⪯ o (s, λ^{'} (h (s))) = C (λ^{'} (h (s)))$ .

Lemma 7.25.

Let $(Y, ⪯)$ , $(Y^{'}, ⪯^{'})$ , and $(Y^{″}, ⪯^{″})$ be preordered sets, and let $C : \subseteq Y^{'} \to Y$ and $C^{'} : \subseteq Y^{″} \to Y^{'}$ be good functions. If forests $F \in Forests (Y)$ , $F^{'} \in Forests (Y^{'})$ , and $F^{″} \in Forests (Y^{″})$ satisfy $F ⪯_{1}^{C} F^{'}$ and $F^{'} ⪯_{1}^{C^{'}} F^{″}$ then $F ⪯_{1}^{C \circ C^{'}} F^{″}$ .

$⪯_{1}$ is reflexive and transitive.

Proof.

Let $F = (S, λ)$ , $F^{'} = (S^{'}, λ^{'})$ , $F^{″} = (S^{″}, λ^{″})$ . Let us assume that $h : S \to S^{'}$ is a monotone function such that for all $s \in S$ , $λ^{'} (h (s)) \in dom (C)$ and $λ (s) ⪯ C (λ^{'} (h (s)))$ . And let us assume that $h^{'} : S^{'} \to S^{″}$ is a monotone function such that for all $s^{'} \in S^{'}$ , $λ^{″} (h^{'} (s^{'})) \in dom (C^{'})$ and $λ^{'} (s^{'}) ⪯^{'} C^{'} (λ^{″} (h^{'} (s^{'})))$ . Then $C \circ C^{'} : \subseteq Y^{″} \to Y$ is a good function, $h^{'} \circ h : S \to S^{″}$ is a monotone function, and for all $s \in S$ we obtain $λ^{″} ((h^{'} \circ h) (s)) = λ^{″} (h^{'} (h (s))) \in dom (C^{'})$ and $\begin{matrix} λ (s) ⪯ C (λ^{'} (h (s))) ⪯ C (C^{'} (λ^{″} (h^{'} (h (s))) . \end{matrix}$

For reflexivity consider $C : = {id}_{Y}$ . The transitivity of $⪯_{1}$ follows from the first assertion.
□

Note that the first assertion shows that $F ⪯_{0} F^{'}$ implies $F ⪯_{1} F^{'}$ .
Corollary 7.26.
Let $F, G \in Forests (Y)$ be $\equiv_{0}$ -equivalent, and let $F^{'}, G^{'} \in Forests (Y^{'})$ be $\equiv_{0}$ -equivalent.
If $C : \subseteq Y^{'} \to Y$ is a good function then: $F ⪯_{1}^{C} F^{'} ⟺ G ⪯_{1}^{C} G^{'}$ .

$F ⪯_{1} F^{'} ⟺ G ⪯_{1} G^{'}$ .

Proof.
The first assertion follows from Lemma 7.24.1 and from Lemma 7.25.1. The second assertion follows directly from the first assertion. □

Hence, for any good function $C : \subseteq Y^{'} \to Y$ the relation $⪯_{1}^{C}$ resp. the relation $⪯_{1}$ on forests induces a natural relation on $\equiv_{0}$ -classes which we denote by $⪯_{1}^{C}$ resp. by $⪯_{1}$ as well: for $F \in Forestclasses (Y)$ and $F^{'} \in Forestclasses (Y^{'})$ we define $\begin{matrix} F ⪯_{1}^{C} F^{'} : ⟺ F ⪯_{1}^{C} F^{'} \end{matrix}$ and $\begin{matrix} F ⪯_{1} F^{'} : ⟺ F ⪯_{1} F^{'} \end{matrix}$ where $F \in F$ and $F^{'} \in F^{'}$ are arbitrary elements of the $\equiv_{0}$ -classes $F$ and $F^{'}$ .
Lemma 7.27.
Let $C : \subseteq Y^{'} \to Y$ be a good function. For any countable set $M^{'} \subseteq Forestclasses (Y^{'})$ and any $T \in Treeclasses (Y)$ with $T ⪯_{1}^{C} {sup}_{⪯_{0}^{'}} (M^{'})$ there exists a forestclass $F^{'} \in M^{'}$ with $T ⪯_{1}^{C} F^{'}$ .
Proof.
The proof is almost identical with the proof of Lemma 7.16. □
Lemma 7.28.
Let $C : \subseteq Y^{'} \to Y$ be a good function. Let $M \subseteq Forestclasses (Y)$ be a countable set of forest classes and let $F^{'} \in Forestclasses (Y^{'})$ be a forest class such that $F ⪯_{1}^{C} F^{'}$ for all $F \in M$ . Then ${sup}_{⪯_{0}} (M) ⪯_{1}^{C} F^{'}$ .
Proof.
This is obvious from the construction of a forest in ${sup}_{⪯_{0}} (M)$ given in the proof of Lemma 7.3. □
Lemma 7.29.
Let $C : \subseteq Y^{'} \to Y$ be a good function. Let $y \in Y$ and $y^{'} \in Y^{'}$ . Let $F \in Forestclasses (Y)$ and $F^{'} \in Forestclasses (Y^{'})$ . If $\begin{matrix} treeclass (y, F) ⪯_{1}^{C} treeclass (y^{'}, F^{'}) but treeclass (y, F) ⋠_{1}^{C} F^{'} \end{matrix}$ then $y ⪯ C (y^{'})$ .
Proof.
The proof is similar to and easier than the proof of Lemma 7.18. □

Finally we show that in special cases the relation $⪯_{1}$ can be expressed in a rather compact way.
Lemma 7.30.
Let $(Y, ⪯)$ be a weakly bounded-complete poset, and let $(Y^{'}, ⪯^{'})$ be a preordered set. Then for $F = (S, λ) \in Forests (Y)$ and $F^{'} = (S^{'}, λ^{'}) \in Forests (Y^{'})$ the following two conditions are equivalent:
$F ⪯_{1} F^{'}$ .

There exists a monotone function $h : S \to S^{'}$ such that, for all nonempty $M \subseteq S$ , if $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded then $λ [M]$ is ⪯-upper bounded.

Proof.
$(1) \Rightarrow (2)$ : Let $C : \subseteq Y^{'} \to Y$ be a good function such that $F ⪯_{1}^{C} F^{'}$ . Let $h : S \to S^{'}$ be a monotone function such that, for all $s \in S$ , $λ^{'} (h (s)) \in dom (C)$ and $λ (s) ⪯ C (λ^{'} (h (s)))$ . Let us consider a nonempty subset $M \subseteq S$ such that the set $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded. Let $y^{'} \in Y^{'}$ be a $⪯^{'}$ -upper bound of $λ^{'} [h [M]]$ . Then, for all $s \in M$ , $\begin{matrix} λ (s) ⪯ C (λ^{'} (h (s))) ⪯ C (y^{'}) . \end{matrix}$ Hence, $λ [M]$ is ⪯-upper bounded by $C (y^{'})$ .

$(2) \Rightarrow (1)$ : Let $h : S \to S^{'}$ be a monotone function such that, for all nonempty $M \subseteq S$ , if $λ^{'} [h [M]]$ is $⪯^{'}$ -upper bounded then $λ [M]$ is ⪯-upper bounded. We define a function $C : \subseteq Y^{'} \to Y$ as follows. For $y^{'} \in Y^{'}$ the set $\begin{matrix} M_{y^{'}} : = {s \in S : λ^{'} (h (s)) ⪯^{'} y^{'}} \end{matrix}$ has the property that $λ^{'} [h [M_{y^{'}}]]$ is $⪯^{'}$ -upper bounded by $y^{'}$ . Hence, if $M_{y^{'}} \neq \emptyset$ then by assumption the set $λ [M_{y^{'}}]$ is ⪯-upper bounded. In this case we define $C (y^{'}) : = {sup}_{⪯} (λ [M_{y^{'}}])$ . This function C is obviously monotone and has the domain $\begin{matrix} dom (C) = {y^{'} \in Y^{'} : M_{y^{'}} \neq \emptyset} = {y^{'} \in Y^{'} : (\exists s \in S) λ^{'} (h (s)) ⪯ y^{'}} . \end{matrix}$ It is clear that $dom (C)$ is ⪯-upwards closed. Thus, C is good. For all $s \in S$ we have $s \in M_{λ^{'} (h (s))}$ , hence, $λ^{'} (h (s)) \in dom (C)$ and $λ (s) ⪯ {sup}_{⪯} (λ [M_{λ^{'} (h (s))}]) = C (λ^{'} (h (s)))$ . Thus, the monotone function h shows $F ⪯_{1}^{C} F^{'}$ . □

The previous lemma applies in particular to the two cases exhibited in Remark 7.20. Remark 7.31.
In the case, when Y and $Y^{'}$ are finite sets and ⪯ and $⪯^{'}$ are the equality relation on Y resp. on $Y^{'}$ , then the second condition in the lemma is equivalent to the following condition: there exists a monotone function $h : S \to S^{'}$ such that, for any $s_{1}, s_{2} \in S$ , if $λ (s_{1}) \neq λ (s_{2})$ then $λ^{'} (h (s_{1})) \neq λ^{'} (h (s_{2}))$ .

8. Forests and trees associated with a function with range in a preordered set

8.1. The definition of the trees and forests

Let $(Y, ⪯)$ be a preordered set. Let X be a second countable topological space. Let $f : \subseteq X \to Y$ be a function with countable range. With f we wish to associate tree classes $T_{α} (f, x) \in Treeclasses (Y)$ , for countable ordinals α and $x \in dom (f)$ , and forest classes $F_{α} (f) \in Forestclasses (Y)$ , for countable ordinals α. We do this recursively, for any countable ordinal α, as follows.

If $T_{β} (f, x)$ is defined for all $β < α$ and all $x \in dom (f)$ then we define $\begin{matrix} F_{α} (f) : = sup_{⪯_{0}} {T_{β} (f, x) : x \in dom (f), β \in ORD, β < α} . \end{matrix}$

For any countable ordinal α and any $x \in X$ , let us call an open set $V \subseteq X$ with $x \in V$ an $(f, α)$ -neighbourhood of x if $F_{α} (f |_{V})$ is defined (by Lemma 8.1 this implies that for all open subsets $U \subseteq V$ with $x \in U$ , the forest class $F_{α} (f |_{U})$ is defined as well) and, for all open subsets $U \subseteq V$ with $x \in U$ , $F_{α} (f |_{U}) = F_{α} (f |_{V})$ . By Lemma 8.1 this implies that $F_{α} (f |_{U}) = F_{α} (f |_{V})$ , for all $(f, α)$ -neighbourhoods U of x. Thus, if there exists an $(f, α)$ -neighbourhood V of x then is makes sense to define $\begin{matrix} T_{α} (f, x) : = treeclass (f (x), F_{α} (f |_{V})) . \end{matrix}$

The following lemma justifies this definition.

Lemma 8.1.
Let α be a countable ordinal.
If $T_{β} (f, x)$ is defined for all $β < α$ and all $x \in dom (f)$ then the set ${T_{β} (f, x) : x \in dom (f), β \in ORD, β < α}$ is countable, hence, by Lemma 7.3 $F_{α} (f)$ is defined.

If $F_{α} (f)$ is defined and if $U \subseteq X$ is open then $F_{α} (f |_{U})$ is defined as well and satisfies $F_{α} (f |_{U}) ⪯_{0} F_{α} (f)$ .

If $V \subseteq X$ is an $(f, α)$ -neighbourhood of some point $x \in dom (f)$ then every open subset $U \subseteq V$ with $x \in U$ is an $(f, α)$ -neighbourhood as well.

If $U \subseteq X$ and $V \subseteq X$ are $(f, α)$ -neighbourhoods of some point $x \in dom (f)$ then $F_{α} (f |_{U}) = F_{α} (f |_{V})$ .

If, for some $x \in dom (f)$ , $T_{α} (f, x)$ is defined and if $U \subseteq X$ is open with $x \in U$ then $T_{α} (f |_{U}, x)$ is defined as well and satisfies $T_{α} (f |_{U}, x) = T_{α} (f, x)$ .

Proof.
We show this by induction over α. Let $B$ be a countable basis of the topology of X.
Let us assume that $T_{β} (f, x)$ is defined for all $β < α$ and all $x \in dom (f)$ . Then for every $x \in dom (f)$ and every $β < α$ there exists some $(f, β)$ -neighbourhood $V_{β, x}$ of x. We choose some $U_{β, x} \in B$ with $x \in U_{β, x}$ and $U_{β, x} \subseteq V_{β, x}$ . By induction hypothesis $U_{β, x}$ is an $(f, β)$ -neighbourhood of x as well and $F_{β} (f |_{U_{β, x}}) = F_{β} (f |_{V_{β, x}})$ . As $B$ is countable and there are only countably many ordinals smaller than α we conclude that the set of forest classes $F_{β} (f |_{U_{β, x}})$ for $β < α$ and $x \in dom (f)$ is countable. Finally, as the range of f is countable as well, there are only countably many tree classes of the form $treeclass (f (x), F_{β} (f |_{U_{β, x}}))$ for $β < α$ and $x \in dom (f)$ .

If $F_{α} (f)$ is defined then $T_{β} (f, x)$ is defined for all $β < α$ and all $x \in dom (f)$ . Let $U \subseteq X$ be open. By induction hypothesis all tree classes $T_{β} (f |_{U}, x)$ for $x \in dom (f) \cap U$ are defined and satisfy $T_{β} (f |_{U}, x) = T_{β} (f, x)$ . Hence, by the first assertion $F_{α} (f |_{U})$ is defined. Then it is clear that $F_{α} (f |_{U}) ⪯_{0} F_{α} (f)$ .

Let us assume that some open subset $V \subseteq X$ is an $(f, α)$ -neighbourhood of some point $x \in dom (f)$ . In particular $F_{α} (f |_{V})$ is defined. Let $U \subseteq V$ be an open subset with $x \in U$ as well. Then by the second assertion $F_{α} (f |_{U})$ is defined as well. As V is an $(f, α)$ -neighbourhood of x, we have $F_{α} (f |_{U}) = F_{α} (f |_{V})$ . Furthermore, for any open subset $W \subseteq U$ with $x \in W$ the forest class $F_{α} (f |_{W})$ is defined as well and satisfies $F_{α} (f |_{W}) = F_{α} (f |_{V})$ , hence, $F_{α} (f |_{W}) = F_{α} (f |_{U})$ . Thus, U is an $(f, α)$ -neighbourhood of x as well.

If $U \subseteq X$ and $V \subseteq X$ are $(f, α)$ -neighbourhoods of some point $x \in dom (f)$ then by the third assertion the set $U \cap V$ is an $(f, α)$ -neighbourhood of x as well, and $F_{α} (f |_{U}) = F_{α} (f |_{U \cap V}) = F_{α} (f |_{V})$ .

Let us assume that $x \in dom (f)$ is a point such that $T_{α} (f, x)$ is defined. Then there exists an $(f, α)$ -neighbourhood V of x. Let $U \subseteq X$ be open with $x \in U$ . Then by the third assertion $U \cap V$ is an $(f, α)$ -neighbourhood of x as well. By the fourth assertion we obtain $F_{α} (f |_{U \cap V}) = F_{α} (f |_{V})$ . As for all open $W \subseteq U \cap V$ with $x \in W$ we have $F_{α} (f |_{W}) = F_{α} (f |_{U \cap V})$ the set $U \cap V$ is also an $(f |_{U}, α)$ -neighbourhood of x. We obtain $T_{α} (f |_{U}, x) = treeclass (f_{U} (x), F_{α} (f |_{U \cap V})) = treeclass (f (x), F_{α} (f |_{V})) = T_{α} (f, x)$ .
□

In general, $F_{α} (f)$ and $T_{α} (f, x)$ do not need to be defined. But at least for $α = 0$ they are defined always.
Lemma 8.2.

The forest class $F_{0} (f)$ is always defined. It is the $\equiv_{0}$ -class of the empty forest.

For all $x \in dom (f)$ the tree class $T_{0} (f, x)$ is defined. It is the $\equiv_{0}$ -class of the tree consisting of only one element, its root, labeled with $f (x)$ .

Proof.
The first assertion follows from the fact that set ${T_{β} (f, x) : x \in dom (f), β \in ORD, β < 0}$ is empty. Thus, $F_{0} (f)$ is the $\equiv_{0}$ -class of the empty forest. This implies that the set X itself is an $(f, 0)$ -neighbourhood of x, for any $x \in X$ . Hence, the tree class $T_{0} (f, x)$ is equal to $treeclass (f (x), {\emptyset})$ , hence, it is the $\equiv_{0}$ -class of the tree consisting of only one element, its root, labeled with $f (x)$ . □
Proposition 8.3.
Let $(Y, ⪯)$ be a bqo set. Then, for every countable ordinal α,
$F_{α} (f)$ exists,

for every $x \in dom (f)$ there exists an $(f, α)$ -neighbourhood,

for every $x \in dom (f)$ the tree class $T_{α} (f, x)$ exists.

Proof.
We show this by induction over α. For $α = 0$ these assertions are contained already in the previous lemma and its proof. Let us consider some countable ordinal $α > 0$ .
By induction hypothesis $T_{β} (f, x)$ exists for all $β < α$ and all $x \in X$ . By Lemma 8.1 the set ${T_{β} (f, x) : β < α and x \in X}$ is countable. Hence, by Lemma 7.3 $F_{α} (f)$ is defined.

Let us fix some $x \in dom (f)$ . By the first assertion $F_{α} (f |_{V})$ exists for any open subset $V \subseteq X$ with $x \in V$ . By Corollary 7.8 the relation $⪯_{0}$ on $(Forestclasses (Y), ⪯_{0})$ is a bqo, hence, a well-quasi-order. Therefore, the nonempty set ${F_{α} (f |_{U}) : U \subseteq X is open with x \in U}$ has a $⪯_{0}$ -smallest element. Let $V \subseteq X$ be an open set with $x \in V$ and $F_{α} (f |_{V}) = {min}_{⪯_{0}} {F_{α} (f |_{U}) : U \subseteq X is open with x \in U}$ . Then V is an $(f, α)$ -neighbourhood of x.

The second assertion implies that $T_{α} (f, x)$ exists.
□

We remark that later, in Proposition 8.13, we shall formulate an interesting strengthening of the second assertion of Proposition 8.3.
Example 8.4.
Let us compute the forests describing the discontinuity of the relations ${LLPO}_{n}$ for $n ⩾ 2$ introduced in Example 4.12. Let us fix some $n ⩾ 2$ . We consider the function $F_{{LLPO}_{n}} : \subseteq B \to (P ([n]), \supseteq)$ defined by $dom (F_{{LLPO}_{n}}) = dom ({LLPO}_{n})$ and by $F_{{LLPO}_{n}} (p) : = {LLPO}_{n} [p]$ , for $p \in dom ({LLPO}_{n})$ . Note that $(P ([n]), \supseteq)$ is a bqo set. First let us consider the point $0^{i} 10^{ω}$ , for some $i \in N$ . It is clear that $T_{0} (F_{{LLPO}_{n}}, 0^{i} 10^{ω})$ is the treeclass of the one-node-tree whose only node is labeled with $[n] ∖ {(i mod n)}$ . As $0^{i} 10^{ω}$ is an isolated point of $dom (F_{{LLPO}_{n}})$ we get even $T_{0} (F_{{LLPO}_{n}}, 0^{i} 10^{ω}) = T_{α} (F_{{LLPO}_{\infty}}, 0^{i} 10^{ω})$ , for all countable ordinals α. For $0^{ω}$ one observes that $T_{1} (F_{{LLPO}_{n}}, 0^{ω})$ is the treeclass of the tree $F^{(n)} = (S^{(n)}, λ^{(n)})$ where $\begin{array}{l} S^{(n)} = {ε, 1, 2, \dots, n - 1}, \\ λ^{(n)} (ε) : = [n], \\ λ^{(n)} (i) : = [n] ∖ {i}, for i \in [n] . \end{array}$ Thus, $F^{(n)}$ consists of a root ε labeled with $[n]$ and of n sons i, for $i = 0, \dots, n - 1$ , where i is labeled with $[n] ∖ {i}$ . As $T_{1} (F_{{LLPO}_{n}}, 0^{i} 10^{ω}) ⪯_{0} T_{1} (F_{{LLPO}_{n}}, 0^{ω})$ we obtain $F_{2} (F_{{LLPO}_{n}}) = T_{1} (F_{{LLPO}_{n}}, 0^{ω})$ . By induction we conclude that even $T_{1} (F_{{LLPO}_{n}}, 0^{ω}) = T_{α} (F_{{LLPO}_{n}}, 0^{ω}) = F_{α + 1} (F_{{LLPO}_{n}})$ , for all countable ordinals $α ⩾ 1$ . See Fig. 1.
Figure 1.
A representant of $F_{2} (F_{{LLPO}_{3}})$ on the left, a representant of $F_{2} (F_{{LLPO}_{2}})$ on the right, and a morphism (dashed; see Definition 7.2) from the labeled tree on the left to the labeled tree on the right.
Example 8.5.
In Example 4.13 we introduced a relation ${LLPO}_{\infty} \subseteq B \times N$ . For this relation we consider the associated function $F_{{LLPO}_{\infty}}$ . Although the range of ${LLPO}_{\infty}$ is the subset $\begin{matrix} {N} \cup {N ∖ {i} : i \in N} \end{matrix}$ of $P (N)$ , and ⊇ is not a bqo on $range ({LLPO}_{\infty})$ (it is not even a well-quasi-order on $range ({LLPO}_{\infty})$ because the elements $N ∖ {i}$ , for $i \in N$ , are pairwise ⊇-incomparable), the trees $T_{α} (F_{{LLPO}_{\infty}}, p)$ exist, for all $p \in dom ({LLPO}_{\infty})$ and all countable ordinals α, and the forests $F_{α} (F_{{LLPO}_{\infty}})$ exist, for all countable ordinals α. Indeed, for every $p \in dom ({LLPO}_{\infty}) ∖ {0^{ω})$ there exist unique numbers $i, j \in N$ with $p = 0^{⟨ i, j ⟩} 10^{ω}$ . It is clear that $T_{0} (F_{{LLPO}_{\infty}}, 0^{⟨ i, j ⟩} 10^{ω})$ is the treeclass of the one-node-tree whose only node is labeled with $N ∖ {i}$ . As $0^{⟨ i, j ⟩} 10^{ω}$ is an isolated point of $dom (F_{{LLPO}_{n}})$ we get even $T_{0} (F_{{LLPO}_{\infty}}, 0^{⟨ i, j ⟩} 10^{ω}) = T_{α} (F_{{LLPO}_{\infty}}, 0^{⟨ i, j ⟩} 10^{ω})$ , for all countable ordinals α. For $0^{ω}$ one observes that $T_{1} (F_{{LLPO}_{\infty}}, 0^{ω})$ is the treeclass of the tree $\begin{matrix} F = ({ε, 0, 1, 2, \dots}, ⊑, λ) \end{matrix}$ where $λ (ε) : = N$ and $λ (i) : = N ∖ {i}$ , for $i \in N$ . Thus, F consists of the root ε labeled with $N$ and of countably many sons i, for $i \in N$ , of the root where i is labeled with $N ∖ {i}$ ; see Fig. 2. As $T_{1} (F_{{LLPO}_{\infty}}, 0^{⟨ i, j ⟩} 10^{ω}) ⪯_{0} T_{1} (F_{{LLPO}_{\infty}}, 0^{ω})$ we obtain $F_{2} (F_{{LLPO}_{\infty}}) = T_{1} (F_{{LLPO}_{\infty}}, 0^{ω})$ . By induction we conclude that even $T_{1} (F_{{LLPO}_{\infty}}, 0^{ω}) = T_{α} (F_{{LLPO}_{\infty}}, 0^{ω}) = F_{α + 1} (F_{{LLPO}_{\infty}})$ , for all countable ordinals $α ⩾ 1$ .

Figure 2.
A representant of $F_{2} (F_{{LLPO}_{\infty}})$ .
Example 8.6.
Let $Y : = N \cup {\infty}$ , and let ⪯ be the equality relation on Y. Then $(Y, ⪯)$ is a partially ordered set but not a well-quasi-ordered set, hence, not a bqo set. Let $\min_{d} : B \to Y$ be defined by $\begin{matrix} \min_{d} (p) : = \{\begin{matrix} min {p (i) - 1 : i \in N} & if p \neq 0^{ω}, \\ \infty & if p = 0^{ω}, \end{matrix} \end{matrix}$ for $p \in B$ . Although $(Y, ⪯)$ is not a bqo set, all forest classes $F_{α} (\min_{d})$ , for all countable ordinals α, and all tree classes $T_{α} (\min_{d}, p)$ , for all countable ordinals α and all $p \in B$ , are defined. By induction one shows for $p \neq 0^{ω}$ and $n : = \min_{d} (p)$ that, for all countable ordinals $α ⩾ n$ , the tree class $T_{α} (\min_{d}, p)$ is the tree class of the tree $\begin{matrix} ({0^{i} : i ⩽ n}, λ) with λ (0^{i}) = n - i, for i ⩽ n, \end{matrix}$ And for all countable ordinals $α ⩾ ω$ one obtains $F_{α + 1} (\min_{d}) = T_{α} (\min_{d}, 0^{ω})$ , and a representant of this tree class is the tree $\begin{matrix} ({ε} \cup {n 0^{i} : n, i \in N and i ⩽ n}, λ) with \{\begin{matrix} λ (ε) & = & \infty, \\ λ (n 0^{i}) & = & n - i, for 0 ⩽ i ⩽ n; \end{matrix} \end{matrix}$ see Fig. 3.

Figure 3.
A representant of $F_{ω + 1} (\min_{d})$ .
8.2. First properties of the trees, forests, and $(f, α)$ -neighbourhoods

In Sections 8.2 and 8.3

X, $X^{'}$ are arbitrary second countable topological spaces,

$(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ are arbitrary preordered sets,

$f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ are arbitrary functions with countable range,

$C : \subseteq Y^{'} \to Y$ is an arbitrary good function,

unless they are explicitly defined to be something else.

Lemma 8.7.

If, for some countable ordinal α, the forest class $F_{α} (f)$ exists then, for all $β ⩽ α$ , the forest class $F_{β} (f)$ exists and satisfies $F_{β} (f) ⪯_{0} F_{α} (f)$ .

If, for some $x \in dom (f)$ and for some countable ordinal α, the tree class $T_{α} (f, x)$ exists then, for all $β ⩽ α$ , the tree class $T_{β} (f, x)$ exists and satisfies $T_{β} (f, x) ⪯_{0} T_{α} (f, x)$ .

Proof.

This follows directly from the definitions.

Let us consider some $x \in dom (f)$ . Fix an $(f, α)$ -neighbourhood U of x and an $(f, β)$ -neighbourhood V of x. Then $U \cap V$ is at the same time an $(f, α)$ -neighbourhood of x and an $(f, β)$ -neighbourhood of x. As $F_{β} (f |_{U \cap V}) ⪯_{0} F_{α} (f |_{U \cap V})$ we obtain $T_{β} (f, x) ⪯_{0} T_{α} (f, x)$ as well.
□
Lemma 8.8.
For all countable ordinals α the following assertion is true. For all $x \in dom (f)$ and all countable ordinals β, if $T_{α} (f, x)$ and $F_{β} (f^{'})$ exist and satisfy $T_{α} (f, x) ⪯_{2}^{C} F_{β} (f^{'})$ then there exist a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C, a point $x^{'} \in dom (f^{'})$ and an ordinal γ with the following properties:
$γ ⩽ α$ and $γ < β$ ,

$T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{γ} (f^{'}, x^{'})$ ,

$f^{'} (x^{'}) \in dom (\tilde{C})$ and $f (x) ⪯ \tilde{C} (f^{'} (x^{'}))$ .

Proof.
We show this by induction over α. Let us fix some countable ordinal α and assume that the assertion is true for all smaller ordinals. Let us assume that, for some good function $C : \subseteq Y^{'} \to Y$ , for some functions $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ with countable range, for some $x \in dom (f)$ and for some countable ordinal β, $T_{α} (f, x)$ and $F_{β} (f^{'})$ exist and satisfy $T_{α} (f, x) ⪯_{2}^{C} F_{β} (f^{'})$ . Let $\begin{matrix} γ : = min {δ : (\exists x^{'} \in dom (f^{'})) T_{α} (f, x) ⪯_{2}^{C} T_{δ} (f^{'}, x^{'})} . \end{matrix}$ Note that due to Lemma 7.16 the set on the right hand side is not empty and that $γ < β$ . Choose some $x^{'} \in X^{'}$ with $T_{α} (f, x) ⪯_{2}^{C} T_{γ} (f^{'}, x^{'})$ . Let $V^{'}$ be an $(f^{'}, γ)$ -neighborhood of $x^{'}$ . We claim that $T_{α} (f, x) ⋠_{2}^{C} F_{γ} (f^{'} |_{V^{'}})$ . Otherwise, according to Lemma 7.16, there would exist some $z^{'} \in dom (f^{'}) \cap V^{'}$ and some $δ < γ$ with $T_{α} (f, x) ⪯_{2}^{C} T_{δ} (f^{'}, z^{'})$ . And this would contradict the definition of γ. So, we have $\begin{matrix} T_{α} (f, x) ⋠_{2}^{C} F_{γ} (f^{'} |_{V^{'}}) and T_{α} (f, x) ⪯_{2}^{C} T_{γ} (f^{'}, x^{'}) . \end{matrix}$ An application of Lemma 7.18 yields a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ with $f^{'} (x^{'}) \in dom (\tilde{C})$ , with $f (x) ⪯ \tilde{C} (f^{'} (x^{'}))$ , and with $T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{γ} (f^{'}, x^{'})$ . Finally, we wish to show $γ ⩽ α$ . For the sake of a contradiction, let us assume $α < γ$ . Then $T_{α} (f^{'}, x^{'})$ exists. It is sufficient to show $T_{α} (f, x) ⪯_{0}^{C} T_{α} (f^{'}, x^{'})$ because this contradicts the definition of γ. In fact, we will show even $T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{α} (f^{'}, x^{'})$ . Choose an $(f, α)$ -neighbourhood U of x and an $(f^{'}, α)$ -neighbourhood $U^{'}$ of $x^{'}$ . Remember that we have already shown $f (x) ⪯ \tilde{C} (f^{'} (x^{'}))$ . Hence, in order to show $T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{α} (f^{'}, x^{'})$ it is sufficient to show $F_{α} (f |_{U}) ⪯_{2}^{\tilde{C}} F_{α} (f^{'} |_{U^{'}})$ . Let us consider some $z \in U \cap dom (f)$ and some $δ < α$ . According to Lemma 7.17 it is sufficient to show $T_{δ} (f, z) ⪯_{2}^{\tilde{C}} F_{α} (f^{'} |_{U^{'}})$ . We know $\begin{matrix} T_{δ} (f, z) ⪯_{0} F_{α} (f |_{U}) ⪯_{0} T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{γ} (f^{'}, x^{'}) ⪯_{0} F_{γ + 1} (f^{'} |_{U^{'}}) . \end{matrix}$ This implies $T_{δ} (f, z) ⪯_{2}^{\tilde{C}} F_{γ + 1} (f^{'} |_{U^{'}})$ . By induction hypothesis there exist a point $z^{'} \in U^{'} \cap dom (f^{'})$ and an ordinal ζ with $ζ ⩽ δ$ , with $ζ < γ + 1$ , and with $T_{δ} (f, z) ⪯_{2}^{\tilde{C}} T_{ζ} (f^{'}, z^{'})$ . As $ζ ⩽ δ < α$ , we obtain $T_{δ} (f, z) ⪯_{2}^{\tilde{C}} T_{ζ} (f^{'}, z^{'}) ⪯_{0} F_{α} (f^{'} |_{U^{'}})$ , hence, $T_{δ} (f, z) ⪯_{2}^{\tilde{C}} F_{α} (f^{'} |_{U^{'}})$ , □

Essentially the same assertion is true if $⪯_{2}^{C}$ is replaced by $⪯_{1}^{C}$ .
Lemma 8.9.
For all countable ordinals α the following assertion is true. For all $x \in dom (f)$ and all countable ordinals β, if $T_{α} (f, x)$ and $F_{β} (f^{'})$ exist and satisfy $T_{α} (f, x) ⪯_{1}^{C} F_{β} (f^{'})$ then there exist a point $x^{'} \in dom (f^{'})$ and an ordinal γ with the following properties:
$γ ⩽ α$ and $γ < β$ ,

$T_{α} (f, x) ⪯_{1}^{C} T_{γ} (f^{'}, x^{'})$ ,

$f^{'} (x^{'}) \in dom (C)$ and $f (x) ⪯ C (f^{'} (x^{'}))$ .

Proof.
The proof is very similar to (in fact, easier than) the proof of Lemma 8.8. □
Corollary 8.10.
For all countable ordinals α, β the following assertions hold true.
If $F_{α} (f)$ and $F_{β} (f^{'})$ exist and satisfy $F_{α} (f) ⪯_{0} F_{β} (f^{'})$ , then, for all $γ ⩽ α$ , $F_{γ} (f) ⪯_{0} F_{min {γ, β}} (f^{'})$ .

For all $x \in dom (f)$ and $x^{'} \in dom (f^{'})$ , if $f (x) ⪯ f^{'} (x^{'})$ , if $T_{α} (f, x)$ and $T_{β} (f^{'}, x^{'})$ exist and satisfy $T_{α} (f, x) ⪯_{0} T_{β} (f^{'}, x^{'})$ then, for all $γ ⩽ α$ , $T_{γ} (f, x) ⪯_{0} T_{min {γ, β}} (f^{'}, x^{'})$ .

Proof.

Let us assume $F_{α} (f) ⪯_{0} F_{β} (f^{'})$ . Consider some ordinal $γ ⩽ α$ . If $β ⩽ γ$ then, by Lemma 8.7, $F_{γ} (f) ⪯_{0} F_{α} (f) ⪯_{0} F_{β} (f^{'}) = F_{min {γ, β}} (f^{'})$ . So, let us assume $γ < β$ . Then $F_{γ} (f^{'})$ exists. We wish to show $F_{γ} (f) ⪯_{0} F_{γ} (f^{'})$ . Consider some $x \in dom (f)$ and some $δ < γ$ . It is sufficient to show $T_{δ} (f, x) ⪯_{0} F_{γ} (f^{'})$ . Due to $δ < γ ⩽ α$ we know $T_{δ} (f, x) ⪯_{0} F_{α} (f) ⪯_{0} F_{β} (f^{'})$ . According to Lemma 8.8 (applied in the special case $(Y, ⪯) = (Y^{'}, ⪯^{'})$ and $C = {id}_{Y}$ ) there exist a point $x^{'} \in dom (f^{'})$ and an ordinal ζ with $ζ ⩽ δ$ , with $ζ < β$ , and with $T_{δ} (f, x) ⪯_{0} T_{ζ} (f^{'}, x^{'})$ . Due to $ζ ⩽ δ < γ$ we have $T_{ζ} (f^{'}, x^{'}) ⪯_{0} F_{γ} (f^{'})$ . We obtain $T_{δ} (f, x) ⪯_{0} F_{γ} (f^{'})$ .

We prove this by induction over α. Let us assume that for some $x \in dom (f)$ and some $x^{'} \in dom (f^{'})$ we have $f (x) ⪯ f^{'} (x^{'})$ and $T_{α} (f, x) ⪯_{0} T_{β} (f^{'}, x^{'})$ . Let γ be an ordinal with $γ ⩽ α$ . If $β ⩽ γ$ then, by Lemma 8.7, $T_{γ} (f, x) ⪯_{0} T_{α} (f, x) ⪯_{0} T_{β} (f^{'}, x^{'}) = T_{min {γ, β}} (f^{'}, x^{'})$ . So, let us assume $γ < β$ . Then $T_{γ} (f^{'}, x^{'})$ exists. We wish to show $T_{γ} (f, x) ⪯_{0} T_{γ} (f^{'}, x^{'})$ . Let $U \subseteq X$ be an open subset with $x \in U$ that is an $(f, α)$ -neighbourhood of x and an $(f, γ)$ -neighbourhood of x. As we assume $f (x) ⪯ f^{'} (x^{'})$ , it is sufficient to show $F_{γ} (f |_{U}) ⪯_{0} T_{γ} (f^{'}, x^{'})$ . Let us fix some $z \in U$ and some $δ < γ$ . It is sufficient to show $T_{δ} (f, z) ⪯_{0} T_{γ} (f^{'}, x^{'})$ . Indeed, due to $T_{δ} (f, z) ⪯_{0} F_{α} (f |_{U}) ⪯_{0} T_{α} (f, x) ⪯_{0} T_{β} (f^{'}, x^{'})$ and the induction hypothesis we obtain $T_{δ} (f, z) ⪯_{0} T_{min {δ, β}} (f^{'}, x^{'}) ⪯_{0} F_{γ} (f^{'}, x^{'})$ .
□
Example 8.11.
We note that the condition $f (x) ⪯ f^{'} (x^{'})$ in the second assertion of Corollary 8.10 cannot be omitted. Consider for example the functions $f, f^{'} : B \to P {({1, 2, 3})}_{\neq \emptyset}$ defined by $\begin{array}{l} f (p) : = \{\begin{matrix} {1, 2} & if p = 0^{ω}, \\ {2} & otherwise, \end{matrix} \\ f^{'} (p) : = \{\begin{matrix} {2, 3} & if p = 0^{ω}, \\ {2} & otherwise, \end{matrix} \end{array}$ And let ⪯ on $P {({1, 2, 3})}_{\neq \emptyset}$ be reverse inclusion, that is, $A ⪯ B : ⟺ A \supseteq B$ , for $A, B \in P {({1, 2, 3})}_{\neq \emptyset}$ . Then $T_{1} (f, 0^{ω}) ⪯_{0} T_{1} (f^{'}, 0^{ω})$ , but $T_{0} (f, 0^{ω}) ⋠_{0} T_{0} (f^{'}, 0^{ω})$ .

The next two assertions are about $(f, α)$ -neighbourhoods of a point x.
Corollary 8.12.
For all countable ordinals α, β with $β ⩽ α$ , and for all points $x \in dom (f)$ , if an open set $U \subseteq X$ is an $(f, α)$ -neighbourhood of x then it is an $(f, β)$ -neighbourhood of x as well.
Proof.
Let $U \subseteq X$ be an $(f, α)$ -neighbourhood of x. Let $V \subseteq U$ be an arbitrary open set with $x \in V$ . According to Lemmas 8.1 and 8.7 the forest classes $F_{β} (f |_{U})$ and $F_{β} (f |_{V})$ exist. It is sufficient to show $F_{β} (f |_{U}) ⪯_{0} F_{β} (f |_{V})$ . But this follows from $F_{α} (f |_{U}) ⪯_{0} F_{α} (f |_{V})$ (which is true because U is an $(f, α)$ -neighbourhood of x) and from Corollary 8.10. □

We will not make any use of the following strengthening of the second assertion of Proposition 8.3. We have included it because it is interesting in its own right. Proposition 8.13.
Let X be a second countable topological space, and let $(Y, ⪯)$ be a bqo set. Let $f : \subseteq X \to Y$ be a function with countable range, and let $x \in dom (f)$ . Then there exists an open subset $U \subseteq X$ which, for all countable ordinals β, is an $(f, β)$ -neighbourhood of x.
Proof.
Let ${(B_{n})}_{n \in N}$ be a non-increasing neighbourhood base of x, that is, a sequence of open sets in X such that $x \in B_{n}$ and $B_{n + 1} \subseteq B_{n}$ , for all n, and for every open set $U \subseteq X$ with $x \in U$ there exists an n with $B_{n} \subseteq U$ . It is sufficient to show that there exists a number n such that, for all countable ordinals β, the set $B_{n}$ is an $(f, β)$ -neighbourhood of x.

For the sake of a contradiction, let us assume that this is false. Then, for all n, there exists a countable ordinal $β_{n}$ such that $B_{n}$ is not an $(f, β_{n})$ -neighbourhood of x. We define a strictly increasing sequence ${(n_{i})}_{i \in N}$ of natural numbers recursively as follows. First, $n_{0} : = 0$ . Once $n_{0}, \dots, n_{i}$ are defined, we choose $n_{i + 1}$ so large that $n_{i + 1} > n_{i}$ and such that $B_{n_{i + 1}}$ is an $(f, β_{n_{i}})$ -neighbourhood of x (such a number $n_{i + 1}$ exists by Proposition 8.3 and by Lemma 8.1).

We claim: $\begin{array}{rcl} (8.1) & (\forall i, j) (if i < j then F_{β_{n_{i}}} (f |_{B_{n_{i}}}) ⋠_{0} F_{β_{n_{j}}} (f |_{B_{n_{j}}})) . \end{array}$ For the sake of a contradiction, let us assume that there are $i, j \in N$ with $i < j$ and $F_{β_{n_{i}}} (f |_{B_{n_{i}}}) ⪯_{0} F_{β_{n_{j}}} (f |_{B_{n_{j}}})$ . Due to Corollary 8.10 we obtain $F_{β_{n_{i}}} (f |_{B_{n_{i}}}) ⪯_{0} F_{β_{n_{i}}} (f |_{B_{n_{j}}})$ . Lemma 8.1 and the inclusion $B_{n_{j}} \subseteq B_{n_{i + 1}}$ imply $F_{β_{n_{i}}} (f |_{B_{n_{j}}}) ⪯_{0} F_{β_{n_{i}}} (f |_{B_{n_{i + 1}}})$ . Hence, we obtain $F_{β_{n_{i}}} (f |_{B_{n_{i}}}) ⪯_{0} F_{β_{n_{i}}} (f |_{B_{n_{i + 1}}})$ . But, as $B_{n_{i + 1}} \subseteq B_{n_{i}}$ is an $(f, β_{n_{i}})$ -neighbourhood of x, this implies that $B_{n_{i}}$ is an $(f, β_{n_{i}})$ -neighbourhood of x as well. Contradiction. We have proved Claim (8.1). But this claim is in contradiction to the fact that the relation $⪯_{0}$ on $Forestclasses (Y)$ is a well-quasi-order (Corollary 7.8). □

8.3. When the sequence of forests stabilizes

Lemma 8.14.
Let α be a countable ordinal.
Let $x \in dom (f)$ and $x^{'} \in dom (f^{'})$ be points such that $f^{'} (x^{'}) \in dom (C)$ and $f (x) ⪯ C (f^{'} (x^{'}))$ . If $T_{α} (f, x)$ exists and, for some $α^{'} < α$ , $T_{α^{'}} (f^{'}, x^{'})$ exists and satisfies $T_{α} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ then, for all countable ordinals β such that $T_{β} (f, x)$ exists, $T_{β} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ .

If $F_{α} (f)$ exists and, for some $α^{'} < α$ , $F_{α^{'}} (f^{'})$ exists and satisfies $F_{α} (f) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ then, for all countable ordinals β such that $F_{β} (f, x)$ exists, $F_{β} (f) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ .

The same assertions are true if $⪯_{2}^{C}$ is replaced by $⪯_{1}^{C}$ .

Proof.

We show this by induction over α. Let us fix some countable ordinal α and assume that the assertion is true for all smaller ordinals. Let us assume that $T_{α} (f, x)$ exists and, for some $α^{'} < α$ , $T_{α^{'}} (f^{'}, x^{'})$ exists and satisfies $T_{α} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ We claim that, for all countable ordinals β such that $T_{β} (f, x)$ exists, $T_{β} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ . It is clear that this claim is true for all $β ⩽ α$ . Let us prove it by induction for all countable ordinals $β ⩾ α$ . Let us fix some $β > α$ and let us assume that $T_{β} (f, x)$ exists. By induction hypothesis we can assume that for all $γ < β$ $\begin{matrix} (8.2) & T_{γ} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'}) . \end{matrix}$ Let us fix an $(f, β)$ -neighbourhood $U \subseteq X$ of x. Due to $f (x) ⪯ C (f^{'} (x^{'}))$ it is sufficient to show $F_{β} (f |_{U}) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ . Fix a point $z \in U \cap dom (f)$ and some ordinal $γ < β$ . It is sufficient to show $T_{γ} (f, z) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ . Let $U^{'}$ be an $(f^{'}, α^{'})$ -neighbourhood of $x^{'}$ . We distinguish two cases.

First case: $T_{α^{'}} (f, z) ⪯_{2}^{C} F_{α^{'}} (f^{'} |_{U^{'}})$ . By Lemma 8.8 there exist a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C, a point $z^{'} \in dom (f^{'}) \cap U^{'}$ and an ordinal $δ < α^{'}$ such that $T_{α^{'}} (f, z) ⪯_{2}^{\tilde{C}} T_{δ} (f^{'}, z^{'})$ and $f^{'} (z^{'}) \in dom (\tilde{C})$ and $f (z) ⪯ \tilde{C} (f^{'} (z^{'}))$ . Then, by induction hypothesis (remember that $α^{'} < α$ ) $T_{γ} (f, z) ⪯_{2}^{\tilde{C}} T_{δ} (f^{'}, z^{'}) ⪯_{0} F_{α^{'}} (f^{'} |_{U^{'}}) ⪯_{0} T_{α^{'}} (f^{'}, x^{'})$ , hence, $T_{γ} (f, z) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ .

Second case: $T_{α^{'}} (f, z) ⋠_{2}^{C} F_{α^{'}} (f^{'} |_{U^{'}})$ . The set U is not only an $(f, β)$ -neighbourhood of x, but by Corollary 8.12 it is an $(f, α)$ -neighbourhood of x as well. We observe: $\begin{matrix} T_{α^{'}} (f, z) ⪯_{0} F_{α} (f |_{U}) ⪯_{0} T_{α} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'}) . \end{matrix}$ Due to Lemma 7.18 we obtain $f (z) ⪯ C (f^{'} (x^{'}))$ . By Corollary 8.12 the set U is an $(f, γ)$ -neighbourhood of x as well. Let us fix some $(f, γ)$ -neighbourhood $V \subseteq U$ of z. We obtain $\begin{matrix} F_{γ} (f |_{V}) ⪯_{0} F_{γ} (f |_{U}) ⪯_{0} T_{γ} (f, x) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'}) \end{matrix}$ (the last step is due to (8.2)). Thus, we have $f (z) ⪯ C (f^{'} (x^{'}))$ and $F_{γ} (f |_{V}) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ . This implies $T_{γ} (f, z) ⪯_{2}^{C} T_{α^{'}} (f^{'}, x^{'})$ .

Let us assume that $F_{α} (f)$ exists and, for some $α^{'} < α$ , $F_{α^{'}} (f^{'})$ exists and satisfies $F_{α} (f) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ . Let us fix some countable ordinal β and let us assume that $F_{β} (f, x)$ exists. We wish to show $F_{β} (f) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ . Let us fix some $z \in dom (f)$ and some $γ < β$ . It is sufficient to prove $T_{γ} (f, z) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ . We observe $T_{α^{'}} (f, z) ⪯_{0} F_{α} (f) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ . By Lemma 8.8 there exist a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C, a point $z^{'} \in dom (f^{'})$ and an ordinal $δ < α^{'}$ such that $T_{α^{'}} (f, z) ⪯_{2}^{\tilde{C}} T_{δ} (f^{'}, z^{'})$ and $f^{'} (z^{'}) \in dom (\tilde{C})$ and $f (z) ⪯ \tilde{C} (f^{'} (z^{'}))$ . By the first assertion of the lemma we conclude $T_{γ} (f, z) ⪯_{2}^{\tilde{C}} T_{δ} (f^{'}, z^{'}) ⪯_{0} F_{α^{'}} (f^{'})$ , hence, $T_{γ} (f, z) ⪯_{2}^{C} F_{α^{'}} (f^{'})$ .

The proof of these assertions for $⪯_{1}^{C}$ instead of $⪯_{2}^{C}$ is very similar to the proof for $⪯_{2}^{C}$ .
□
Corollary 8.15.
For all countable ordinals α the following assertions are true.
If $F_{α + 1} (f)$ exists and satisfies $F_{α + 1} (f) ⪯_{0} F_{α} (f)$ then, for all countable ordinals $β ⩾ α$ such that $F_{β} (f)$ exists, $F_{β} (f) = F_{α} (f)$ .

For all $x \in dom (f)$ , if $T_{α + 1} (f, x)$ exists and satisfies $T_{α + 1} (f, x) ⪯_{0} T_{α} (f, x)$ then, for all countable ordinals $β ⩾ α$ such that $T_{β} (f, x)$ exists, $T_{β} (f, x) = T_{α} (f, x)$ .

Proof.
We prove the first assertion. The second is proved in the same way. First we note that, if $F_{α + 1} (f)$ exists then also $F_{α} (f)$ exists. Let us fix some $β ⩾ α$ and let us assume that $F_{β} (f)$ exists. By Lemma 8.7 we have $F_{α} (f) ⪯_{0} F_{β} (f)$ . By Lemma 8.14 we have $F_{β} (f) ⪯_{0} F_{α} (f)$ . Hence, $F_{β} (f) = F_{α} (f)$ . □
Example 8.16.
It is possible that for some points x the sequence of tree classes $T_{α} (f, x)$ never stabilizes but the sequence of forest classes $F_{α} (f)$ stabilizes. Consider for example the set $A : = {p \in B : p (i) = 0 for almost all i \in N}$ and the following relation $R \subseteq N^{N} \to {0, 1, 2}$ defined by $\begin{matrix} R [x] : = \{\begin{matrix} {0, 1} & if p (0) = 0 and p (1) p (2) p (3) \dots \in A \\ {1, 2} & if p (0) = 0 and p (1) p (2) p (3) \dots \notin A \\ {1} & if p (0) \neq 0 . \end{matrix} \end{matrix}$ Then we consider the function $F_{R} : B \to P {({0, 1, 2})}_{\neq \emptyset}$ and on $P {({0, 1, 2})}_{\neq \emptyset}$ the relation ⊇. For points $p \in B$ with $p (0) = 0$ the sequence of tree classes $T_{α} (F_{R}, p)$ never stabilizes, that is, that for all countable ordinals α, $T_{α} (F_{R}, p) ≺_{0} T_{α + 1} (F_{R}, p)$ . But for all countable ordinals $α ⩾ 1$ , we observe that $F_{α} (F_{R})$ is the forest class of the forest that contains only one node, labeled with ${1}$ . This last statement is even true if instead of the set A any other subset $A \subseteq B$ , Borel measurable or not, is used in the definition of R.

The following lemma will be crucial in the following section. Lemma 8.17.
Let α be a countable ordinal. If $F_{α + 2} (f)$ and $F_{α} (f^{'})$ exist then the set $\begin{matrix} {x \in dom (f) : T_{α} (f, x) ⪯_{2}^{C} F_{α} (f^{'})} \end{matrix}$ is open in the relative topology of $dom (f)$ .
Proof.
Let us assume that $F_{α + 2} (f)$ and $F_{α} (f^{'})$ exist. Then $T_{α + 1} (f, x)$ and $T_{α} (f, x)$ exist for all $x \in dom (f)$ . Let $V : = {x \in dom (f) : T_{α} (f, x) ⪯_{2}^{C} F_{α} (f^{'})}$ . If V is empty then the assertion is clear. Let us assume that V is not empty. Consider some point $x \in V$ . Then $T_{α} (f, x) ⪯_{2}^{C} F_{α} (f^{'})$ . By Lemma 8.8 there exist a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C, a point $x^{'} \in dom (f^{'})$ and an ordinal $α^{'} < α$ such that $T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{α^{'}} (f^{'}, x^{'})$ and $f^{'} (x^{'}) \in dom (\tilde{C})$ and $f (x) ⪯ \tilde{C} (f^{'} (x^{'}))$ . With Lemma 8.14 we conclude $T_{α + 1} (f, x) ⪯_{2}^{\tilde{C}} T_{α^{'}} (f^{'}, x^{'}) ⪯_{0} F_{α} (f^{'})$ , hence, $\begin{matrix} (8.3) & T_{α + 1} (f, x) ⪯_{2}^{C} F_{α} (f^{'}) . \end{matrix}$ Let $U \subseteq X$ be some $(f, α + 1)$ -neighbourhood of x. Then U is open. We claim that $U \cap dom (f) \subseteq V$ . Indeed, for all $z \in U \cap dom (f)$ we have $\begin{matrix} T_{α} (f, z) ⪯_{0} F_{α + 1} (f |_{U}) ⪯_{0} T_{α + 1} (f, x) ⪯_{2}^{C} F_{α} (f^{'}), \end{matrix}$ where the last step follows from (8.3). With Lemma 7.13 we conclude $T_{α} (f, z) ⪯_{2}^{C} F_{α} (f^{'})$ , hence, $z \in V$ . □

9. Forests describing topological reducibility degrees for functions with range in a preordered set

In the first of the two subsections in this section we formulate and prove the results that connect the Weihrauch reducibility $⪯_{2}^{C}$ with parameter C for functions f with range in preordered sets on the one hand with the reducibility $⪯_{2}^{C}$ of the associated forests $F_{α} (f)$ on the other hand. In the second subsection we deduce corresponding results for the relations $⪯_{0}$ , $⪯_{1}^{C}$ , $⪯_{1}$ , and $⪯_{2}$ . The results in this section generalize corresponding results in [6–8].

We remind the reader that by Proposition 8.3 all considered forest classes and tree classes exist if the preordered sets $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ are bqo sets.

9.1. Weihrauch reducibility with parameter

Proposition 9.1.
Let X, $X^{'}$ be second countable topological spaces, and let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets. For all countable ordinals α the following assertion is true. Let $C : \subseteq Y^{'} \to Y$ be a good function. Let $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ be functions with countable range and with $f ⪯_{2}^{C} f^{'}$ . Let $A : \subseteq X \to X^{'}$ be a continuous function and $B : \subseteq X \times Y^{'} \to Y$ be a very good function that show this, that is, with $\begin{array}{l} dom (f) \subseteq dom (B \circ ({id}_{X}, (f^{'} \circ A))) and \\ (\forall x \in dom (f)) (f (x) ⪯ B (x, f^{'} (A (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in X) (if (x, y^{'}) \in dom (B) then B (x, y^{'}) = C (y^{'})) . \end{array}$ Then,
If $F_{α} (f)$ and $F_{α} (f^{'})$ exist then $F_{α} (f) ⪯_{2}^{C} F_{α} (f^{'})$ ,

for all $x \in dom (f)$ , if $T_{α} (f, x)$ and $T_{α} (f^{'}, A (x))$ exist then $T_{α} (f, x) ⪯_{2}^{C} T_{α} (f^{'}, A (x))$ .

Proof.
We prove this by induction over α.

For $α = 0$ we observe that $F_{0} (f)$ and $F_{0} (f^{'})$ are the $\equiv_{0}$ -class of the empty forest (with labels in Y resp. in $Y^{'}$ ). Hence $F_{0} (f) ⪯_{2}^{C} F_{0} (f^{'})$ is shown by a monotone function h with empty domain and by a very good function o with empty domain.

For any $x \in dom (f)$ , $T_{0} (f, x))$ is the $\equiv_{0}$ -class of the tree F having exactly one element r, which is labeled by $f (x)$ , while $T_{0} (f^{'}, A (x))$ is the $\equiv_{0}$ -class of the tree $F^{'}$ having exactly one element $r^{'}$ , which is labeled by $f^{'} (A (x))$ . Let h be the monotone function that maps the root r of F (its only node) to the root $r^{'}$ of $F^{'}$ (its only node), and let $o : \subseteq {r} \times Y^{'} \to Y$ be defined by $dom (o) : = {r} \times f^{'} {(A (x))}^{⪯^{'}}$ and $o (r, y^{'}) : = B (x, y^{'})$ , for all $y^{'} \in f^{'} {(A (x))}^{⪯^{'}}$ (remember that $(x, f^{'} (A (x))) \in dom (B)$ and B is very good). Then h is monotone and o is very good. Furthermore, $(r, λ^{'} (h (r))) = (r, f^{'} (A (x))) \in dom (o)$ and $λ (r) = f (x) ⪯ B (x, f^{'} (A (x))) = o (r, f^{'} (A (x))) = o (r, λ^{'} (h (r)))$ . Finally, if $y^{'} \in dom (C)$ and $(r, y^{'}) \in dom (o)$ , that is, if $y^{'} \in f^{'} {(A (x))}^{⪯^{'}}$ , then $o (r, y^{'}) = B (x, y^{'}) = C (y^{'})$ .

Let us consider a countable ordinal $α > 0$ . Let us assume that $F_{α} (f)$ and $F_{α} (f^{'})$ exist. First we show $F_{α} (f) ⪯_{2}^{C} F_{α} (f^{'})$ . By induction hypothesis, for each $β < α$ and each $x \in dom (f)$ , $T_{β} (f, x) ⪯_{2}^{C} T_{β} (f^{'}, A (x))$ . As $T_{β} (f^{'}, A (x)) ⪯_{0} F_{α} (f^{'})$ is clear, by Lemma 7.13.3 we obtain $T_{β} (f, x) ⪯_{2}^{C} F_{α} (f^{'})$ . Now Lemma 7.17 implies $F_{α} (f) ⪯_{2}^{C} F_{α} (f^{'})$ .

Let us consider some $x \in dom (f)$ . Let us assume that $T_{α} (f, x)$ and $T_{α} (f^{'}, A (x))$ exist. We wish to show $T_{α} (f, x) ⪯_{2}^{C} T_{α} (f^{'}, A (x))$ . Let us fix an $(f, α)$ -neighbourhood $U \subseteq X$ of x and an $(f^{'}, α)$ -neighbourhood $U^{'} \subseteq X^{'}$ of $A (x)$ . As A is continuous the set $U \cap A^{- 1} [U^{'}]$ is open. Note that $(x, f^{'} (A (x)) \in dom (B)$ . As B is very good we have $f^{'} {(A (x))}^{⪯^{'}} \subseteq dom (B (x, \cdot))$ , and there exists an open neighbourhood $V \subseteq U \cap A^{- 1} [U^{'}]$ of x such that for all $\tilde{x} \in V$ and all $y^{'} \in f^{'} {(A (x))}^{⪯^{'}}$ , if $(\tilde{x}, y^{'}) \in dom (B)$ then $B (\tilde{x}, y^{'}) = B (x, y^{'})$ . The open set V is an $(f, α)$ -neighbourhood of x as well, hence, $F_{α} (f |_{V}) = F_{α} (f |_{U})$ . We define a function $\tilde{C} : \subseteq Y^{'} \to Y$ by $dom (\tilde{C}) : = dom (C) \cup f^{'} {(A (x))}^{⪯^{'}}$ and by $\begin{matrix} \tilde{C} (y^{'}) : = \{\begin{matrix} B (x, y^{'}) & if y^{'} \in f^{'} {(A (x))}^{⪯^{'}}, \\ C (y^{'}) & if y^{'} \in dom (C), \end{matrix} \end{matrix}$ for $y \in dom (\tilde{C})$ . This function $\tilde{C}$ is well-defined because $B (x, y^{'}) = C (y^{'})$ , for all $y^{'} \in dom (C) \cap f {(A (x))}^{⪯}$ . The function $\tilde{C}$ is an extension of the function C. We observe that the functions A and B show $f |_{V} ⪯_{2}^{\tilde{C}} f^{'} |_{U^{'}}$ . In the first part of the proof we have seen that this implies $F_{α} (f |_{V}) ⪯_{2}^{\tilde{C}} F_{α} (f^{'} |_{U^{'}})$ . We choose forests $F = (S, λ) \in F_{α} (f |_{V})$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (f^{'} |_{U^{'}})$ , a monotone function $h : S \to S^{'}$ and a very good function $o : \subseteq S \times Y^{'} \to Y$ that show $F ⪯_{2}^{\tilde{C}} F^{'}$ . Note that $tree (f (x), F) \in T_{α} (f, x)$ and $tree (f^{'} (A (x)), F^{'}) \in T_{α} (f^{'}, A (x))$ . We can extend the function h to all elements in the tree $tree (f (x), F)$ by mapping the root r of $tree (f (x), F)$ to the root $r^{'}$ of $tree (f^{'} (A (x)), F^{'})$ . Let us call this function $\tilde{h}$ . It is monotone as well. And we can extend the function o to a function $\tilde{o} : \subseteq ({r} \cup S) \times Y^{'} \to Y$ by $dom (\tilde{o}) : = dom (o) \cup ({r} \times f^{'} {(A (x))}^{⪯^{'}})$ and by $\begin{matrix} \tilde{o} (s, y^{'}) : = \{\begin{matrix} o (s, y^{'}) & if (s, y^{'}) \in dom (o), \\ B (x, y^{'}) & if s = r and y^{'} \in f^{'} {(A (x))}^{⪯^{'}} \end{matrix} \end{matrix}$ (remember that $(x, f^{'} (A (x))) \in dom (B)$ and $B (x, \cdot)$ is good). As $B (x, \cdot)$ is good, the function $\tilde{o} (r, \cdot)$ is good as well. As o is very good, $\tilde{o} (s, \cdot)$ is good for every $s \in S$ . Thus, $o (s, \cdot)$ is good for all $s \in {r} \cup S$ . Furthermore, for all $s \in S$ , if $(r, y^{'}) \in dom (\tilde{o})$ , that is, if $f^{'} (A (x)) ⪯^{'} y^{'}$ , and if $(s, y^{'}) \in dom (\tilde{o})$ , that is, if $(s, y^{'}) \in dom (o)$ , then $\begin{matrix} \tilde{o} (s, y^{'}) = o (s, y^{'}) = \tilde{C} (y^{'}) = B (x, y^{'}) = \tilde{o} (r, y^{'}) . \end{matrix}$ Hence, the function $\tilde{o}$ is very good. We claim that the monotone function $\tilde{h}$ and the very good function $\tilde{o}$ show $tree (f (x), F) ⪯_{2}^{\tilde{C}} tree (f^{'} (A (x)), F^{'})$ . First, let us consider some $t \in {r} \cup S$ . If $t \in S$ then $(t, λ^{'} (\tilde{h} (t))) = (t, λ^{'} (h (t))) \in dom (o) \subseteq dom (\tilde{o})$ and $λ (t) ⪯ o (t, λ^{'} (h (t))) = \tilde{o} (t, λ^{'} (\tilde{h} (t)))$ . If $t = r$ then $(t, λ^{'} (\tilde{h} (r))) = (r, λ^{'} (r^{'})) = (r, f^{'} (A (x))) \in dom (\tilde{o})$ and $λ (r) = f (x) ⪯ B (x, f^{'} (A (x))) = \tilde{o} (r, f^{'} (A (x))) = \tilde{o} (r, λ^{'} (\tilde{h} (r)))$ . Finally, let us consider some $y^{'} \in dom (\tilde{C})$ and some $t \in {r} \cup S$ with $(t, y^{'}) \in dom (\tilde{o})$ . If $t \in S$ then $\tilde{o} (t, y^{'}) = o (t, y^{'}) = \tilde{C} (y^{'})$ because h and o show $F ⪯_{2}^{\tilde{C}} F^{'}$ . If $t = r$ and $y^{'} \in f^{'} {(A (x))}^{⪯^{'}}$ then $\tilde{o} (t, y^{'}) = B (x, y^{'}) = \tilde{C} (y^{'})$ . We have shown $tree (f (x), F) ⪯_{2}^{\tilde{C}} tree (f^{'} (A (x)), F^{'})$ . Of course, this implies $T_{α} (f, x) ⪯_{2}^{\tilde{C}} T_{α} (f^{'}, A (x))$ , and this implies $T_{α} (f, x) ⪯_{2}^{C} T_{α} (f^{'}, A (x))$ as $\tilde{C}$ is an extension of C; compare Lemma 7.12. □

The following lemma says that if a function f defined on a subset of the Baire space is “locally” $⪯_{2}^{C}$ -reducible to a function $f^{'}$ then it is $⪯_{2}^{C}$ -reducible to $f^{'}$ . Lemma 9.2.
Let $X^{'}$ be a second-countable topological space, let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, let $C : \subseteq Y^{'} \to Y$ be a good function. Let $f : \subseteq B \to Y$ and $f^{'} : \subseteq X^{'} \to Y$ be functions with countable range. If for every $x \in dom (f)$ there exists an open set $U \subseteq B$ with $x \in U$ and with $f |_{U} ⪯_{2}^{C} f^{'}$ then $f ⪯_{2}^{C} f^{'}$ .
Proof.
Let us assume that for every $x \in dom (f)$ there exists an open set $U_{x} \subseteq B$ with $x \in U_{x}$ and with $f |_{U_{x}} ⪯_{2}^{C} f^{'}$ . For every $x \in dom (f)$ we can fix a finite prefix $w_{x} \in N^{< ω}$ of x with $w_{x} B \subseteq U_{x}$ . Then $f |_{w_{x} B} ⪯_{2}^{C} f^{'}$ . Let $\begin{matrix} W : = {v \in N^{< ω} : (\exists x \in dom (f)) v = w_{x} and (\forall x \in dom (f)) w_{x} is not a proper prefix of v} . \end{matrix}$ Then $dom (f) \subseteq W B$ and the sets $w B$ for $w \in W$ are pairwise disjoint clopen subsets of $B$ . As for each $w \in W$ we have $f |_{w B} ⪯_{2}^{C} g$ , for each $w \in W$ we can fix a continuous function $A^{(w)} : \subseteq w B \to X^{'}$ and a very good function $B^{(w)} : \subseteq w B \times Y^{'} \to Y$ such that $\begin{array}{l} dom (f |_{w B}) \subseteq dom (B^{(w)} \circ ({id}_{X}, (f^{'} \circ A^{(w)}))) and \\ (\forall x \in dom (f) \cap w B) (f (x) ⪯ B^{(w)} (x, f^{'} (A^{(w)} (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in B) (if (x, y^{'}) \in dom (B^{(w)}) then B^{(w)} (x, y^{'}) = C (y^{'})) . \end{array}$ We define the function $A : \subseteq B \to X^{'}$ by $dom (A) : = ⋃_{w \in W} dom (A^{(w)})$ and by $A (x) : = A^{(w)} (x)$ , for $x \in dom (A)$ , where w is the unique element of W with $x \in w B$ . It is obvious that A is continuous. We define the function $B : \subseteq B \times Y^{'} \to Y$ by $dom (B) : = ⋃_{w \in W} dom (B^{(w)})$ and by $B (x, y^{'}) : = B^{(w)} (x, y^{'})$ , for $(x, y^{'}) \in dom (B)$ , where w is the unique element of W with $x \in w B$ . It is obvious that B is very good. Finally, it is obvious that $\begin{array}{l} dom (f) \subseteq dom (B \circ ({id}_{X}, (f^{'} \circ A))) and \\ (\forall x \in dom (f)) (f (x) ⪯ B (x, f^{'} (A (x))) and \\ (\forall y^{'} \in dom (C)) (\forall x \in B) (if (x, y^{'}) \in dom (B) then B (x, y^{'}) = C (y^{'})) . \end{array}$ □
Proposition 9.3.
Let $X^{'}$ be a separable metric space, let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, and let $f : \subseteq B \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ be functions with countable range. Let $C : \subseteq Y^{'} \to Y$ be a good function. If there exists a countable ordinal α such that $F_{α + 1} (f)$ and $F_{α} (f^{'})$ exist and $F_{α + 1} (f) ⪯_{2}^{C} F_{α} (f^{'})$ then $f ⪯_{2}^{C} f^{'}$ .
Proof.
We are going to show this by induction over α. Let us assume that α is a countable ordinal such that $F_{α + 1} (f)$ and $F_{α} (f^{'})$ exist and $F_{α + 1} (f) ⪯_{2}^{C} F_{α} (f^{'})$ . Let us consider an arbitrary point $x_{0} \in dom (f)$ . Let U be an $(f, α)$ -neighbourhood of x. According to Lemma 9.2 it is sufficient to show the following claim: $\begin{matrix} (9.1) & f |_{U} ⪯_{2}^{C} f^{'} . \end{matrix}$

Let us prove this claim. Note that $T_{α} (f, x_{0}) ⪯_{0} F_{α + 1} (f) ⪯_{2}^{C} F_{α} (f^{'})$ . Due to Lemma 8.8 there exist a good extension $\tilde{C} : \subseteq Y^{'} \to Y$ of C, a point $x_{0}^{'} \in dom (f^{'})$ and an ordinal $β < α$ with $f^{'} (x_{0}^{'}) \in dom (\tilde{C})$ , with $f (x_{0}) ⪯ \tilde{C} (f^{'} (x_{0}^{'}))$ , and with $T_{α} (f, x_{0}) ⪯_{2}^{\tilde{C}} T_{β} (f^{'}, x_{0}^{'})$ .

Let $U^{'} \subseteq X^{'}$ be an $(f^{'}, β)$ -neighbourhood of $x_{0}^{'}$ . According to Lemma 8.17 the set $\begin{matrix} V : = {x \in dom (f) \cap U : T_{β} (f, x) ⪯_{2}^{\tilde{C}} F_{β} (f^{'} |_{U^{'}})} \end{matrix}$ is open in the relative topology of $dom (f) \cap U$ . Hence, the set $D : = (dom (f) \cap U) ∖ V$ is closed in the relative topology of $dom (f) \cap U$ . If D is empty then we have $F_{β + 1} (f |_{U}) ⪯_{2}^{\tilde{C}} F_{β} (f^{'} |_{U^{'}})$ . By induction hypothesis we obtain $f |_{U} ⪯_{2}^{\tilde{C}} f^{'}$ . As $dom (C) \subseteq dom (\tilde{C})$ and, for all $y^{'} \in dom (C)$ , $C (y^{'}) = \tilde{C} (y^{'})$ , this implies $f |_{U} ⪯_{2}^{C} f^{'}$ . Therefore, for the rest of the proof we assume $D \neq \emptyset$ .

For each $x \in D \subseteq dom (f) \cap U$ we have on the one hand $\begin{matrix} T_{β} (f, x) ⪯_{0} F_{α} (f |_{U}) ⪯_{0} T_{α} (f, x_{0}) ⪯_{2}^{\tilde{C}} T_{β} (f^{'}, x_{0}^{'}) . \end{matrix}$ On the other hand, for each $x \in D$ we have $T_{β} (f, x) ⋠_{2}^{\tilde{C}} F_{β} (f^{'} |_{U^{'}})$ . The second assertion of Lemma 7.18 tells us $f (x) ⪯ \tilde{C} (f^{'} (x_{0}^{'}))$ .

The set V is the disjoint union of the clopen (in the relative topology of $dom (f) \cap U$ ) sets $\begin{matrix} V_{n} : = {x \in V : d (x, D) = 2^{- n}}, \end{matrix}$ for $n \in N$ . For each $n \in N$ and each $x \in V_{n}$ we have $T_{β} (f, x) ⪯_{2}^{\tilde{C}} F_{β} (f^{'} |_{U^{'}})$ . This implies $\begin{matrix} F_{β + 1} (f |_{V_{n}}) = sup_{⪯_{0}} {T_{β} (f, x) : x \in dom (f) \cap V_{n}} ⪯_{2}^{\tilde{C}} F_{β} (f^{'} |_{U^{'}}) = F_{β} (f^{'} |_{U^{'} \cap B (x_{0}^{'}, 2^{- n})}) \end{matrix}$ (the equality $F_{β} (f^{'} |_{U^{'}}) = F_{β} (f^{'} |_{U^{'} \cap B (x_{0}^{'}, 2^{- n})})$ is true because both $U^{'}$ and its subset $U^{'} \cap B (x_{0}^{'}, 2^{- n})$ are $(f^{'}, β)$ -neighbourhoods of $x_{0}^{'}$ ). By induction hypothesis we obtain $f |_{V_{n}} ⪯_{2}^{\tilde{C}} f^{'} |_{U^{'} \cap B (x_{0}^{'}, 2^{- n})}$ . Let $A_{n} : \subseteq V_{n} \to U^{'} \cap B (x_{0}^{'}, 2^{- n})$ be a continuous function and $B_{n} : \subseteq V_{n} \times Y^{'} \to Y$ be a very good function that show this, that is, such that $\begin{array}{l} dom (f) \cap V_{n} \subseteq dom (B_{n} \circ ({id}_{B}, (f^{'} \circ A_{n}))) and \\ (\forall x \in dom (f) \cap V_{n}) (f (x) ⪯ B_{n} (x, f^{'} (A_{n} (x))) and \\ (\forall y^{'} \in dom (\tilde{C})) (\forall x \in B) (if (x, y^{'}) \in dom (B_{n}) then B_{n} (x, y^{'}) = \tilde{C} (y^{'})) . \end{array}$ We define a function $A : \subseteq B \to X^{'}$ by $dom (A) : = dom (f) \cap U$ and $\begin{matrix} A (x) : = \{\begin{matrix} x_{0}^{'} & if x \in D, \\ A_{n} (x) & if x \in V_{n}, for some n \in N . \end{matrix} \end{matrix}$ It is clear that this function A is continuous. Furthermore, we define a function $B : \subseteq B \times Y^{'} \to Y$ by $dom (B) : = (D \times f^{'} {(x_{0}^{'})}^{⪯^{'}}) \cup ⋃_{n \in N} dom (B_{n})$ and by $\begin{matrix} B (x, y^{'}) : = \{\begin{matrix} \tilde{C} (y^{'}) & if x \in D and y^{'} \in f^{'} {(x_{0}^{'})}^{⪯^{'}}, \\ B_{n} (x, y^{'}) & otherwise, where n is the unique number with (x, y^{'}) \in dom (B_{n}), \end{matrix} \end{matrix}$ It is clear that $B (x, \cdot)$ is good, for every $x \in B$ with $dom (B (x, \cdot)) \neq \emptyset$ . In order to show that B is very good we still need to show that for all $x \in B$ with $dom (B (x, \cdot)) \neq \emptyset$ there exists an open neighborhood U of x such that, for all $y^{'} \in dom (B (x, \cdot))$ and all $\tilde{x} \in U$ , if $(\tilde{x}, y^{'}) \in dom (B)$ then $B (\tilde{x}, y^{'}) = B (x, y^{'})$ . It is clear that this is the case for all $x \in V$ . We still need to show it for $x \in D$ . But for $x \in D$ and $y^{'} \in Y^{'}$ such that $(x, y^{'}) \in dom (B)$ we have $y^{'} \in f^{'} {(A (x_{0}))}^{⪯^{'}}$ and, for any $\tilde{x} \in B$ with $(\tilde{x}, y^{'}) \in dom (B)$ , either $B (\tilde{x}, y^{'}) = \tilde{C} (y^{'}) = B (x, y^{'})$ (in the case $\tilde{x} \in D$ ) or $B (\tilde{x}, y^{'}) = B_{n} (\tilde{x}, y^{'}) = \tilde{C} (y^{'}) = B (x, y^{'})$ , for some $n \in N$ (in the case $\tilde{x} \in V_{n}$ ). Thus B is a very good function.

We claim that these functions A and B show $f |_{U} ⪯_{2}^{\tilde{C}} f^{'}$ . First, let us consider some $x \in dom (f) \cap U$ . If $x \in V_{n}$ then $f (x) ⪯ B_{n} (x, f^{'} (A_{n} (x))) = B (x, f^{'} (A (x)))$ . If $x \in D$ then $f (x) ⪯ \tilde{C} (f^{'} (x_{0}^{'})) = B (x, f^{'} (x_{0}^{'})) = B (x, f^{'} (A (x)))$ . Finally, let us consider some $y^{'} \in dom (\tilde{C})$ and some $x \in B$ with $(x, y^{'}) \in dom (B)$ . If $(x, y^{'}) \in dom (B_{n})$ then $B (x, y^{'}) = B_{n} (x, y^{'}) = \tilde{C} (y^{'})$ . If $x \in D$ and $y^{'} \in f^{'} {(x_{0}^{'})}^{⪯^{'}}$ then $B (x, y^{'}) = \tilde{C} (y^{'})$ . We have proved $f |_{U} ⪯_{2}^{\tilde{C}} f^{'}$ . As $dom (C) \subseteq dom (\tilde{C})$ and, for all $y^{'} \in dom (C)$ , $C (y^{'}) = \tilde{C} (y^{'})$ , this implies $f |_{U} ⪯_{2}^{C} f^{'}$ . □
Theorem 9.4.
Let $X^{'}$ be a separable metric space, let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, and let $f : \subseteq B \to Y$ and $f^{'} : \subseteq X^{'} \to Y$ be functions with countable range. Let $C : \subseteq Y^{'} \to Y$ be a good function. If α is a countable ordinal such that $F_{α + 1} (f)$ and $F_{α} (f^{'})$ exist and such that $F_{α + 1} (f) = F_{α} (f)$ then the following two conditions are equivalent:
$F_{α} (f) ⪯_{2}^{C} F_{α} (f^{'})$ ,

$f ⪯_{2}^{C} f^{'}$ .

Proof.
This follows directly from Proposition 9.1 and Proposition 9.3. □

9.2. Wadge, strong Weihrauch, and Weihrauch reducibility

The following proposition is a version of Proposition 9.1 for Wadge, strong Weihrauch, and Weihrauch reducibility.

Proposition 9.5.
Let X, $X^{'}$ be second countable topological spaces, and let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets. Let $f : \subseteq X \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ be functions with countable range. Let $A : \subseteq X \to X^{'}$ be a continuous function.
Let $C : \subseteq Y^{'} \to Y$ be a good function. If $f ⪯_{1}^{C} f^{'}$ and if A shows this then:

if $F_{α} (f)$ and $F_{α} (f^{'})$ exist then $F_{α} (f) ⪯_{1}^{C} F_{α} (f^{'})$ ,

for all $x \in dom (f)$ , if $T_{α} (f, x)$ and $T_{α} (f^{'}, A (x))$ exist then $T_{α} (f, x) ⪯_{1}^{C} T_{α} (f^{'}, A (x))$ .

Let $i \in {0, 1, 2}$ . If $f ⪯_{i} f^{'}$ (in the case $i = 0$ we additionally assume $(Y, ⪯) = (Y^{'}, ⪯^{'})$ ) and if A shows this in the cases $i \in {0, 1}$ resp. if A and a very good function $B : \subseteq X \times Y^{'} \to Y$ show this in the case $i = 2$ , then:

if $F_{α} (f)$ and $F_{α} (f^{'})$ exist then $F_{α} (f) ⪯_{i} F_{α} (f^{'})$ ,

for all $x \in dom (f)$ , if $T_{α} (f, x)$ and $T_{α} (f^{'}, A (x))$ exist then $T_{α} (f, x) ⪯_{i} T_{α} (f^{'}, A (x))$ .

Proof.

The proof of these assertions is very similar to (in fact easier than) the proof of Proposition 9.1. It is left to the reader.

According to Lemmas 5.13.3 and 7.24 the assertion for $i = 0$ is a special case of Proposition 9.1: it is the case $(Y, ⪯) = (Y^{'}, ⪯^{'})$ and $C = {id}_{Y}$ .

The case $i = 1$ follows directly from the first assertion.

Finally, the case $i = 2$ is the special case $C = \emptyset$ of Proposition 9.1, that is, the case where $C : \subseteq Y^{'} \to Y$ is the function with empty domain of definition.
□

The following proposition is a version of Proposition 9.3 for Wadge, strong Weihrauch, and Weihrauch reducibility.
Proposition 9.6.
Let $X^{'}$ be a separable metric space, let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, and let $f : \subseteq B \to Y$ and $f^{'} : \subseteq X^{'} \to Y^{'}$ be functions with countable range.
Let $C : \subseteq Y^{'} \to Y$ be a good function. If there exists a countable ordinal α such that $F_{α + 1} (f)$ and $F_{α} (f^{'})$ exist and $F_{α + 1} (f) ⪯_{1}^{C} F_{α} (f^{'})$ then $f ⪯_{1}^{C} f^{'}$ .

Let $i \in {0, 1, 2}$ . If there exists a countable ordinal α such that $F_{α + 1} (f)$ and $F_{α} (f^{'})$ exist and $F_{α + 1} (f) ⪯_{i} F_{α} (f^{'})$ (in the case $i = 0$ we additionally assume $(Y, ⪯) = (Y^{'}, ⪯^{'})$ ) then $f ⪯_{i} f^{'}$ .

Proof.

The proof of this assertion is very similar to (in fact easier than) the proof of Proposition 9.3. It is also straightforward to formulate and prove a version of Lemma 9.2 for $⪯_{1}^{C}$ instead of $⪯_{2}^{C}$ . The details are left to the reader.

According to Lemmas 5.13.3 and 7.11 the assertion for $i = 0$ is a special case of Proposition 9.3: it is the case $(Y, ⪯) = (Y^{'}, ⪯^{'})$ and $C = {id}_{Y}$ .

The case $i = 1$ follows directly from the first assertion.

Finally, the case $i = 2$ is the special case $C = \emptyset$ of Proposition 9.3, that is, the case where $C : \subseteq Y^{'} \to Y$ is the function with empty domain of definition.
□

If X is a second-countable topological space, $(Y, ⪯)$ a bqo set, and $f : \subseteq X \to Y$ a function with countable range then, due to Lemma 8.7 and Corollary 8.15, there is the following dichotomy:
Either $F_{β} (f) ≺_{0} F_{β + 1} (f)$ , for all countable ordinals β,

or there is a (uniquely determined) countable ordinal α such that $F_{β} (f) ≺_{0} F_{β + 1} (f)$ , for all ordinals $β < α$ , and $F_{β} (f) = F_{β + 1} (f)$ , for all ordinals $β ⩾ α$ .
In Proposition 10.5 we shall formulate a sufficient condition ensuring that the second of these two cases is true. Theorem 9.7.
Let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, Let $f : \subseteq B \to Y$ be a function with countable range such that there exists a countable ordinal α such that $F_{α + 1} (f)$ exists and $F_{α + 1} (f) = F_{α} (f)$ . Let $X^{'}$ be a separable metric space. Let $f^{'} : \subseteq X^{'} \to Y^{'}$ be a function with countable range such that $F_{α} (f^{'})$ exists.
Let $C : \subseteq Y^{'} \to Y$ be a good function. Then the following two conditions are equivalent:

$F_{α} (f) ⪯_{1}^{C} F_{α} (f^{'})$ ,

$f ⪯_{1}^{C} f^{'}$ .

Let $i \in {0, 1, 2}$ . In the case $i = 0$ we additionally assume $(Y, ⪯) = (Y^{'}, ⪯^{'})$ . Then the following two conditions are equivalent:

$F_{α} (f) ⪯_{i} F_{α} (f^{'})$ ,

$f ⪯_{i} f^{'}$ .

Proof.
This follows directly from Proposition 9.5 and Proposition 9.6. □
Corollary 9.8.
Let $(Y, ⪯)$ and $(Y^{'}, ⪯^{'})$ be preordered sets, Let $f : \subseteq B \to Y$ be a function with countable range such that there exists a countable ordinal α such that $F_{α + 1} (f)$ exists and $F_{α + 1} (f) = F_{α} (f)$ . Let $X^{'}$ be a separable metric space. Let $f^{'} : \subseteq X^{'} \to Y^{'}$ be a function with countable range such that there exists a countable ordinal $α^{'}$ such that $F_{α^{'} + 1} (f)$ exists and $F_{α^{'} + 1} (f) = F_{α^{'}} (f)$ . Let $i \in {0, 1, 2}$ . In the case $i = 0$ we additionally assume $(Y, ⪯) = (Y^{'}, ⪯^{'})$ . Then the following two conditions are equivalent:
$F_{α} (f) ⪯_{i} F_{α^{'}} (f^{'})$ ,

$f ⪯_{i} f^{'}$ .

Proof.
This follows from Theorem 9.7 and Corollary 8.15. □

10. The degree hierarchies of $Σ_{2}^{0}$ -measurable functions with countable range in a BQO set

In this section we consider functions defined on the Baire space $B$ and with countable range in a bqo set $(Y, ⪯)$ . We show that the initial segments of the Wadge degrees, strong Weihrauch degrees, and Weihrauch degrees of such functions that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y are isomorphic to the $⪯_{0}$ -, $⪯_{1}$ -, and $⪯_{2}$ -degrees of forests with labels in Y.

10.1. Functions, forests and their ranks

First we give an upper estimate of the ranks of the forest classes and tree classes associated with a function. Then we show that for every forest class $F \in Forestclasses (Y)$ there exists a function that has a maximal associated forest class and such that this forest class is $F$ .

Proposition 10.1.
Let X be a second countable topological space, let $(Y, ⪯)$ be a preordered set. Let $f : \subseteq X \to Y$ be a function with countable range. Then, for all countable ordinals α,
If $F_{α} (f)$ exists then $rank (F_{α} (f)) ⩽ α$ ,

for all $x \in dom (f)$ , if $T_{α} (f, x)$ exists then $rank (T_{α} (f, x)) ⩽ α + 1$ .

Proof.
We prove both assertions by induction over α.

Let us first consider the case $α = 0$ . For any function f, the class $F_{0} (f)$ is the class of the empty forest, which has rank 0. And for any point $x \in dom (f)$ , the class $T_{0} (f, x)$ is the class of the tree that consists of only one node, labeled with $f (x)$ . This tree has rank 1.

We come to the case $α > 0$ . Let us assume that $F_{α} (f)$ exists. By definition we have $\begin{matrix} F_{α} (f) = sup_{⪯_{0}} {T_{β} (f, x) : x \in dom (f), β \in ORD, β < α} . \end{matrix}$ By induction hypothesis, for all $β < α$ , we have $rank (T_{β} (f, x)) ⩽ β + 1 ⩽ α$ . Hence, $rank (F_{α} (f)) ⩽ α$ as well.

For the second assertion, let us consider some $x \in dom (f)$ such that $T_{α} (f, x)$ exists. Let U be an $(f, α)$ -neighbourhood of x. Then $\begin{matrix} T_{α} (f, x) = treeclass (f (x), F_{α} (f |_{U})) . \end{matrix}$ By the first assertion, $rank (F_{α} (f |_{U})) ⩽ α$ . Let $F \in F_{α} (f |_{U})$ be a forest with $rank (F) = rank (F_{α} (f |_{U}))$ . Then $tree (f (x), F) \in T_{α} (f, x)$ . We obtain $\begin{matrix} rank (T_{α} (f, x)) ⩽ rank (tree (f (x), F)) = rank (F) + 1 = rank (F_{α} (f |_{U}) + 1 ⩽ α + 1 . \end{matrix}$ □

We remind the reader once again that all forest classes $F_{α} (f)$ , for countable ordinals α, and all tree classes $F_{α} (f, x)$ , for $x \in dom (f)$ and for countable ordinals α, exist if the preordered set $(Y, ⪯)$ is a bqo set; see Proposition 8.3. In the rest of this section we will consider only this case.
Proposition 10.2.
Let X be a second countable topological space, let $(Y, ⪯)$ be a bqo set. Let $F \in Forestclasses (Y)$ , and set $α : = rank (F)$ . Then there exists a function $f : \subseteq B \to Y$ with the following properties:
if $F$ is the forest class of the empty forest then $dom (f) = \emptyset$ ; otherwise f is total.

f is $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y.

For all $β ⩾ α$ , $F_{β} (f) = F (f)$ .

For all $p \in dom (f)$ there exists an ordinal $β < α$ such that for all countable ordinals $γ ⩾ β$ , $T_{γ} (f, p) = T_{β} (f, p)$ .

Note that any function $f : B \to Y$ that is $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y has countable range; see, e.g., [21]. So, a function $f : B \to Y$ is $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y if, and only if, it has countable range and $f^{- 1} [y]$ is a $Δ_{2}^{0}$ -subset of $B$ , for every $y \in Y$ . Proof.
We prove this by induction over $⪯_{0}$ on $Forestclasses (Y)$ (remember that by Corollary 7.8 the relation $⪯_{0}$ on $Forestclasses (Y)$ is a bqo, hence, well-founded).

The set $Forestclasses (Y)$ has a $⪯_{0}$ -smallest element: the class of the empty forest. So, first let us consider the case where $F$ is the class of the empty forest. Then $rank (F) = 0$ . For f one can take the function with empty domain of definition. It has all four properties.

Now, let $F \in Forestclasses (Y)$ be the class of some nonempty labeled forest. According to Lemma 7.4 there exists a countable set $M \subseteq Treeclasses (Y)$ with $F = {sup}_{⪯_{0}} (M)$ and with $rank (F) = sup {rank (T) : T \in M}$ . As $F$ is not the empty forest, the set M cannot be empty. Therefore, we can fix some total numbering of the elements of M (repetitions are allowed): $M = {G_{i} : i \in N}$ . We set $α_{i} : = rank (G_{i})$ . Then $α = sup {α_{i} : i \in N}$ . We distinguish two cases.

First case: There does not exist a $⪯_{0}$ -largest element in M, that is, there does not exist an i such that, for all j, $G_{j} ⪯_{0} G_{i}$ . In this case, for each i we have $G_{i} ≺_{0} F$ . Note that for each i the forest class $G_{i}$ is the class of a tree, and therefore not the class of the empty forest. Hence, by induction hypothesis, for each i, there exists a total $Δ_{2}^{0}$ -measurable function $f_{i} : B \to Y$ such that $G_{i} = F_{α_{i}} (f_{i}) = F_{α_{i} + 1} (f_{i})$ and such that for all $p \in B$ there exists an ordinal $β < α_{i}$ such that for all ordinals $γ ⩾ β$ , $T_{γ} (f_{i}, p) = T_{β} (f_{i}, p)$ . Note that due to $α_{i} ⩽ α$ and Corollary 8.15.1 this implies $G_{i} = F_{α} (f_{i}) = F_{α + 1} (f_{i})$ . We define a total function $f : B \to Y$ by $\begin{matrix} f (p) : = f_{p (0)} (p (1) p (2) p (3) \dots), \end{matrix}$ for all $p \in B$ . It is clear that f is $Δ_{2}^{0}$ -measurable and that $F = F_{α} (f) = F_{α + 1} (f)$ . Finally, let us consider some $p \in B$ . We set $p^{'} : = p (1) p (2) p (3) \dots \in B$ . We observe that for all countable ordinals γ, $T_{γ} (f, p) = T_{γ} (f_{p (0)}, p^{'})$ . There exists a countable ordinal $β < α_{i} ⩽ α$ such that for all ordinals $γ ⩾ β$ , $T_{γ} (f_{p (0)}, p^{'}) = T_{β} (f_{p (0)}, p^{'})$ , hence, $T_{γ} (f, p) = T_{β} (f, p)$ ,

Second case: There exists a $⪯_{0}$ -largest element in M, that is, there exists an i such that, for all j, $G_{j} ⪯_{0} G_{i}$ . Then $F \equiv_{0} G_{i}$ , hence, $F = G_{i}$ is a tree class. According to Lemma 7.6 there exist $y \in Y$ and $H \in Forestclasses (Y)$ with $F = treeclass (y, H)$ , with $H ≺_{0} F$ , and with $rank (F) = rank (H) + 1$ . Let $β : = rank (H)$ . Thus, $α = β + 1$ .

If $H$ is the class of the empty forest then $F$ is the class of the tree consisting of just one node, labeled with y. In particular, $α = rank (F) = 1$ . In this case we define $f : B \to Y$ by $\begin{matrix} f (p) : = y, \end{matrix}$ for all $p \in B$ . It is clear that this function f has all four properties, in particular $F = F_{1} (f) = F_{2} (f) = T_{0} (f, p) = T_{1} (f, p)$ , for all $p \in B$ .

Let us assume that $H$ is not the class of the empty forest. By induction hypothesis, there exists a $Δ_{2}^{0}$ -measurable function $h : B \to Y$ with $\begin{matrix} H = F_{β} (h) = F_{β + 1} (h) \end{matrix}$ and such that for each $p \in B$ there exists an ordinal $γ < β$ such that for all countable ordinals $δ ⩾ γ$ , $T_{δ} (f, p) = T_{γ} (f, p)$ . We define $f : B \to Y$ by $\begin{array}{l} f (0^{ω}) : = y, \\ f (0^{n} k p) : = h (p), for all n ⩾ 0, all k > 0, and all p \in B . \end{array}$ It is clear that f is $Δ_{2}^{0}$ -measurable. It is clear as well that, for all countable ordinals γ, for all $n ⩾ 0$ , for all $k > 0$ and all $p \in B$ , $T_{γ} (f, 0^{n} k p) = T_{γ} (h, p)$ . This implies on the one hand that for each $p \in B ∖ {0^{ω}}$ there exists an ordinal $γ < β < α$ such that for all countable ordinals $δ ⩾ γ$ , $T_{δ} (f, p) = T_{γ} (f, p)$ . On the other hand, it implies that for every open set U with $0^{ω} \in U$ and all countable ordinals γ, $\begin{matrix} F_{γ} (f |_{U}) = sup_{⪯_{0}} ({T_{δ} (f, 0^{ω}) : δ < γ} \cup {F_{γ} (h)}) . \end{matrix}$ Using this, one proves by induction over γ that, for all countable ordinals γ, $T_{γ} (f, 0^{ω}) = treeclass (y, F_{γ} (h))$ . In particular we obtain $\begin{matrix} T_{β} (f, 0^{ω}) = treeclass (y, F_{β} (h)) = treeclass (y, H) = F = treeclass (y, F_{β + 1} (h)) = T_{β + 1} (f, 0^{ω}) . \end{matrix}$ Finally we obtain $F_{α} (f) = F_{β + 1} (f) = F_{β + 2} (f) = F_{α + 1} (f) = F$ . □

10.2. When the sequences of trees stabilize

Lemma 10.3.
Let X be a second countable topological space, let $(Y, ⪯)$ be a bqo set. Let $f : \subseteq X \to Y$ be a function with countable range. The following two conditions are equivalent.
For every $x \in dom (f)$ there exists a countable ordinal $α_{x}$ with $T_{α_{x} + 1} (f, x) = T_{α_{x}} (f, x)$ .

There exists a countable ordinal α such that for all $x \in dom (f)$ , $T_{α + 1} (f, x) = T_{α} (f, x)$ .

Proof.
The direction $(2) \Rightarrow (1)$ is trivial. We prove the direction $(1) \Rightarrow (2)$ . Let $B$ be a countable basis of the topology on X. Let us assume that for every $x \in dom (f)$ there exists a countable ordinal $α_{x}$ with $T_{α_{x} + 1} (f, x) = T_{α_{x}} (f, x)$ . For every $x \in dom (f)$ we fix an $(f, α_{x} + 2)$ -neighborhood $U_{x} \in B$ of x. Then the set $\begin{matrix} U : = {U_{x} : x \in dom (f)} \end{matrix}$ is a subset of $B$ and, hence, countable. It is a covering of $dom (f)$ . For every $U \in U$ we define $\begin{matrix} α_{U} : = min {α_{x} : x \in dom (f) and U_{x} = U} + 1 . \end{matrix}$ Then $α_{U}$ is a countable ordinal. The ordinal number $α : = sup {α_{U} : U \in U}$ is countable as well. We claim that, for all $x \in dom (f)$ , $\begin{matrix} T_{α + 1} (f, x) = T_{α} (f, x) . \end{matrix}$ Let us fix some $x \in dom (f)$ . According to Lemma 8.7.4 it is clear that $T_{α} (f, x) ⪯_{0} T_{α + 1} (f, x)$ . We still wish to show that $T_{α + 1} (f, x) ⪯_{0} T_{α} (f, x)$ . Let $U : = U_{x}$ . By Corollary 8.15 and Lemma 8.7 it is sufficient to show $T_{α_{U} + 1} (f, x) ⪯_{0} T_{α_{U}} (f, x)$ . For this in turn it is sufficient to show $F_{α_{U} + 1} (f |_{U}) ⪯_{0} F_{α_{U}} (f |_{U})$ . But this is true. If we let $\tilde{x}$ be a point in $U \cap dom (f)$ with $U_{\tilde{x}} = U$ and $α_{U} = α_{\tilde{x}} + 1$ , we obtain indeed $\begin{matrix} F_{α_{U} + 1} (f |_{U}) = F_{α_{\tilde{x}} + 2} (f |_{U_{\tilde{x}}}) ⪯_{0} T_{α_{\tilde{x}} + 2} (f, \tilde{x}) = T_{α_{\tilde{x}}} (f, \tilde{x}) ⪯_{0} F_{α_{\tilde{x}} + 1} (f |_{U_{\tilde{x}}}) = F_{α_{U}} (f |_{U}) \end{matrix}$ (here we used Corollary 8.15.1). □

For the proof of the central result in this subsection, Proposition 10.5, we need the notion of a meager set, for which the reader is referred to [11]. The following result is due to Baire.
Lemma 10.4.
Let X be a metrizable topological space, and let Y be a second-countable topological space. Let $f : X \to Y$ be a $Σ_{2}^{0}$ -measurable function. Then the set ${x \in X ∣ f is discontinuous in x}$ of the points in which f is discontinuous is a meager $Σ_{2}^{0}$ -subset of X.

For the proof see [11, (24.14)], where the assertion is stated under the additional assumption that Y is metrizable. But this assumption is not needed. Proposition 10.5.
Let $(Y, ⪯)$ be a bqo set. Let X be a Polish space and let $f : X \to Y$ be a function with countable range that is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y. Then there exists a countable ordinal α such that, for all $x \in X$ , $T_{α + 1} (f, x) = T_{α} (f, x)$ , and, hence, $F_{α + 2} (f) = F_{α + 1} (f)$ .
Proof.
It is clear that the condition “for all $x \in X$ , $T_{α + 1} (f, x) = T_{α} (f, x)$ ” implies $F_{α + 2} (f) = F_{α + 1} (f)$ . According to Lemma 8.7.4 for all ordinals α and all $x \in X$ , $T_{α} (f, x) ⪯_{0} T_{α + 1} (f, x)$ . We have to show that there exists a countable ordinal α such that, for all $x \in X$ , $T_{α + 1} (f, x) ⪯_{0} T_{α} (f, x)$ . In the following, by $ω_{1}$ we denote the first uncountable ordinal.

With any function $f : X \to Y$ we associate the following set $\begin{matrix} S (f) : = {T_{α} (f, x) : x \in X and α < ω_{1}} \subseteq Treeclasses (Y) . \end{matrix}$ We remind the reader that the partial order $⪯_{0}$ on $Treeclasses (Y)$ is a bqo by Corollary 7.8 and Lemma 6.1.2 and that the relation $⪯_{0, P} : = {(⪯_{0})}_{P}$ on $P (Treeclasses (Y))$ is a bqo as well by Lemma 6.2.

For the sake of a contradiction, let us assume that the assertion is false. Then there exists a function $f : X \to Y$ defined on a Polish space X with countable range that is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y and such that there does not exist a countable ordinal α with $(\forall x \in X) T_{α + 1} (f, x) ⪯_{0} T_{α} (f, x)$ . Let us fix such a function with $⪯_{0, P}$ -minimal set $S (f)$ (that means, there does not exist any function $f^{'} : X^{'} \to Y$ with the following five properties: (1) $X^{'}$ is a Polish space, (2) the range of $f^{'}$ is countable, (3) $f^{'}$ is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y, (4) there does not exist a countable ordinal $α^{'}$ with $(\forall x^{'} \in X^{'}) T_{α^{'} + 1} (f^{'}, x^{'}) ⪯_{0} T_{α} (f^{'}, x^{'})$ , (5) $S (f^{'}) ≺_{0, P} S (f)$ ). According to Lemma 10.3 the set $\begin{matrix} A : = {x \in X : (\forall α < ω_{1}) T_{α} (f, x) ≺_{0} T_{α + 1} (f, x)} \end{matrix}$ is not empty. For an arbitrary $T \in Treeclasses (Y)$ the set $\begin{matrix} B_{T} : = {x \in X : (\exists β < ω_{1}) T ⪯_{0} T_{β} (f, x)} \end{matrix}$ is a closed subset of X.

Claim 1: For all $T \in S (f)$ and all $x \in cl (A)$ $\begin{matrix} (10.1) & (\exists β < ω_{1}) T ⪯_{0} T_{β} (f, x) . \end{matrix}$

Proof: Let us consider some $T \in S (f)$ . First we observe that since $X ∖ B_{T}$ is open, for all $β < ω_{1}$ and all $x \in X ∖ B_{T}$ we have $T_{β} (f |_{X ∖ B_{T}}, x) = T_{β} (f, x)$ . On the one hand, $S (f |_{X ∖ B_{T}}) \subseteq S (f)$ , hence, $S (f |_{X ∖ B_{T}}) ⪯_{0, P} S (f)$ . On the other hand, $T \in S (f)$ , but there does not exist any $T^{'} \in S (f |_{X ∖ B_{T}})$ with $T ⪯_{0} T^{'}$ . Hence, $S (f |_{X ∖ B_{T}}) ≺_{0, P} S (f)$ . Note that $X ∖ B_{T}$ is a Polish space itself and that the function $f |_{X ∖ B_{T}} : X ∖ B_{T} \to Y$ has countable range and is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y. Thus, by the choice of f we conclude that the function $f |_{X ∖ B_{T}}$ has the property that there exists a countable ordinal α such that, for all $x \in X ∖ B_{T}$ , $T_{α + 1} (f |_{X ∖ B_{T}}, x) = T_{α} (f |_{X ∖ B_{T}}, x)$ . Hence, for all $x \in X ∖ B_{T}$ , $T_{α + 1} (f, x) = T_{α} (f, x)$ . We conclude that $A \cap (X ∖ B_{T}) = \emptyset$ , hence, $A \subseteq B_{T}$ . As $B_{T}$ is closed, we even obtain $cl (A) \subseteq B_{T}$ . But that implies Claim 1.

Claim 2: The set A is a closed subset of X.

Proof: Let us assume that A is not closed. Then there exist a point $x_{0} \in cl (A) ∖ A$ and an $α < ω_{1}$ with $T_{α + 1} (f, x_{0}) = T_{α} (f, x_{0})$ . Let us fix an arbitrary point $x_{1} \in A$ . By applying Claim 1 to $T : = T_{α} (f, x_{0})$ and to $x_{1}$ we conclude that there exists some $β < ω_{1}$ with $\begin{matrix} T_{α} (f, x_{0}) ⪯_{0} T_{β} (f, x_{1}) . \end{matrix}$ And by applying Claim 1 to $T : = T_{β + 1} (f, x_{1})$ and to $x_{0}$ we conclude that there exists some $γ < ω_{1}$ with $\begin{matrix} T_{β + 1} (f, x_{1}) ⪯_{0} T_{γ} (f, x_{0}) . \end{matrix}$ But, due to Corollary 8.15.1, $T_{γ} (f, x_{0}) ⪯_{0} T_{α} (f, x_{0})$ . Putting all of this together we obtain $\begin{matrix} T_{α} (f, x_{0}) ⪯_{0} T_{β} (f, x_{1}) ⪯_{0} T_{β + 1} (f, x_{1}) ⪯_{0} T_{γ} (f, x_{0}) ⪯_{0} T_{α} (f, x_{0}) . \end{matrix}$ This implies $T_{β} (f, x_{1}) = T_{β + 1} (f, x_{1})$ in contradiction to $x_{1} \in A$ . We have proved Claim 2.

As A is closed, for all $x \in X ∖ A$ and all $α < ω_{1}$ we have $T_{α} (f |_{X ∖ A}, x) = T_{α} (f, x)$ . And for all $x \in X ∖ A$ there exists some countable ordinal $α_{x}$ with $T_{α_{x} + 1} (f, x) = T_{α_{x}} (f, x)$ . We obtain $T_{α_{x} + 1} (f |_{X ∖ A}, x) = T_{α_{x}} (f |_{X ∖ A}, x)$ . By applying Lemma 10.3 to $f |_{X ∖ A}$ we conclude that there exists some $α < ω_{1}$ such that, for all $x \in X ∖ A$ , $T_{α + 1} (f, x) = T_{α} (f, x)$ .

Claim 3: The function $f |_{A} : A \to Y$ is discontinuous in every point of A.

Proof: For the sake of a contradiction let us assume that there exists some point $x_{0} \in A$ such that $f |_{A}$ is continuous in $x_{0}$ . Let $U \subseteq X$ be an open set with $x_{0} \in A$ and such that, for all $x \in U \cap A$ , $f (x) ⪯ f (x_{0})$ . Let $U_{x_{0}} \subseteq U$ be an $(f, α + 1)$ -neighbourhood of $x_{0}$ . Then for $x \in U_{x_{0}} ∖ A$ we have $\begin{matrix} T_{α + 1} (f, x) = T_{α} (f, x) ⪯_{0} F_{α + 1} (f |_{U_{x_{0}}}) ⪯_{0} T_{α + 1} (f, x_{0}) . \end{matrix}$ And for $x \in U_{x_{0}} \cap A$ and some $(f, α + 1)$ -neighbourhood $U_{x} \subseteq U_{x_{0}}$ of x we have $F_{α + 1} (f |_{U_{x}}) ⪯_{0} F_{α + 1} (f |_{U_{x_{0}}})$ and $f (x) ⪯ f (x_{0})$ , hence, $T_{α + 1} (f, x) ⪯_{0} T_{α + 1} (f, x_{0})$ . Thus, for all $x \in U_{x_{0}}$ we have $T_{α + 1} (f, x) ⪯_{0} T_{α + 1} (f, x_{0})$ . That implies $F_{α + 2} (f |_{U_{x_{0}}}) ⪯_{0} T_{α + 1} (f, x_{0})$ , hence, $T_{α + 2} (f, x_{0}) ⪯_{0} T_{α + 1} (f, x_{0})$ in contradiction to $x_{0} \in A$ . We have proved Claim 3.

We have shown that the set $A \subseteq X$ is a nonempty closed subset of X. Hence, it is a Polish space as well, thus, by the Baire Category Theorem non-meager in itself. Furthermore, we have shown that the function $f |_{A} : A \to Y$ is discontinuous in every point of A. Then also the function $g : = (f |_{A}) |^{range (f)} : A \to range (f)$ is discontinuous in every point of A. As f is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y the function g is $Σ_{2}^{0}$ -measurable with respect to the relative topology on A and the relative topology on $range (f)$ . Remember that $range (f)$ is countable. The sets ${x \in range (f) : x ⩽ y}$ for $y \in range (f)$ form a countable basis of the relative topology on $range (f)$ induced by the reverse Alexandroff topology. Hence, according to Lemma 10.4 the set of points of discontinuity of g should be a meager subset of A. Contradiction! □

10.3. The hierarchies for functions with countable range that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology

For a preordered set $(Y, ⪯)$ let $E_{Y}$ denote the $\equiv_{0}$ -class of the empty forest with labels in Y. For a set M and an equivalence relation ≡ on M let $M_{\equiv}$ denote the set of ≡-equivalence classes of elements of M. The following theorem generalizes a corresponding result [6–8] by the author for the finite initial segments of the $⪯_{i}$ -degree structures of partial k-partitions $f : \subseteq B \to [k]$ , for some $k ⩾ 2$ . For the reducibility relation $⪯_{0}$ this result was extended by Selivanov [18] to all $Δ_{2}^{0}$ -measurable k-partitions $f : B \to [k]$ , again by Selivanov [19] to all $Δ_{3}^{0}$ -measurable k-partitions [19], and by Kihara and Montalbán [12] to all Borel measurable functions $f : B \to Y$ where Y is any bqo set. For the extension beyond $Δ_{2}^{0}$ -measurable functions both Selivanov [19] and Kihara and Montalbán [12] used more complicated trees whose labels are trees themselves — this can be iterated. While the method used in [18] is quite similar to the one in [6–8], the procedure in the two papers [19] and [12] is very different from ours.

Theorem 10.6.
Let $(Y, ⪯)$ be a bqo set. For $i = 0, 1, 2$ the following partially ordered sets are isomorphic.
the $⪯_{i}$ -degree structure of the total functions $f : B \to Y$ that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y and that have countable range,

the $⪯_{i}$ -degree structure of the total functions $f : B \to Y$ that are $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y,

$({(Forestclasses (Y) ∖ {E_{Y}})}_{\equiv_{i}}, ⪯_{i})$ .

Of course, in “ $⪯_{i}$ -degree structure” the relation $⪯_{i}$ is the one introduced in Section 5, while in “ $({(Forestclasses (Y) ∖ {E_{Y}})}_{\equiv_{i}}, ⪯_{i})$ ” the relation $⪯_{i}$ is the one introduced in Section 7. Proof.
According to Proposition 10.5 for every function $f : B \to Y$ with countable range that is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y there exists a smallest countable ordinal $α_{f}$ such that, for all $x \in X$ , $T_{α_{f}} (f, x) = T_{α_{f} + 1} (f, x)$ . For later purposes we note that this implies $F_{α_{f} + 1} (f) = F_{α_{f} + 2} (f)$ . In fact, according to Corollary 8.15 it implies even for all $β ⩾ α_{f} + 1$ , $F_{α_{f} + 1} (f) = F_{β} (f)$ .

Let $F_{0}$ be the function that maps any such function f to the forestclass $F_{α_{f} + 1} (f)$ , and let $F_{i}$ for $i = 1, 2$ denote the function that maps any such function f to the $\equiv_{i}$ -class of $F_{α_{f} + 1} (f)$ . If follows from Lemma 7.24.1 that $F_{1}$ is well-defined, and it follows from Lemma 7.11 that $F_{2}$ is well-defined. We claim that for $i = 0, 1, 2$ the function $F_{i}$ induces an isomorphism between the
$⪯_{i}$ -degree structure of the functions $f : B \to Y$ with countable range that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y and the

$⪯_{i}$ -degree structure of the functions $f : B \to Y$ that are $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y
on the one hand and the partial order $({(Forestclasses (Y) ∖ {E_{Y}})}_{\equiv_{i}}, ⪯_{i})$ on the other hand. It follows from Propositions 10.1 and 10.2 that even the range of the restriction of $F_{0}$ to the set of functions $f : B \to Y$ that are $Δ_{2}^{0}$ -measurable with respect to the discrete topology on Y is equal to ${(Forestclasses (Y) ∖ {E_{Y}})}_{\equiv_{0}}$ . This immediately implies that also for $i = 1, 2$ the range of the restriction of $F_{i}$ to the same set of functions is equal to ${(Forestclasses (Y) ∖ {E_{Y}})}_{\equiv_{i}}$ . Finally, for $i = 0, 1, 2$ and for all functions $f, f^{'} : B \to Y$ with countable range that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y Corollary 9.8 says: $\begin{matrix} f ⪯_{i} f^{'} ⟺ F_{α_{f} + 1} (f) ⪯_{i} F_{α_{f^{'}} + 1} (f^{'}) . \end{matrix}$ □
Example 10.7.
We give an example of a function $f : B \to Y$ that is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y but not $Σ_{2}^{0}$ -measurable (and therefore also not $Δ_{2}^{0}$ -measurable) with respect to the discrete topology on Y. Let $Y : = {a, b}$ be a set consisting of exactly two different elements, and let the relation ⪯ on Y be defined by $⪯ : = {(a, a), (b, b), (a, b)}$ . Then ⪯ is a finite partial order, hence, a bqo. Let $S : = {p \in B : p (i) = 0 for almost all i \in N}$ . Let $f : B \to Y$ be defined by $\begin{matrix} f (p) : = \{\begin{matrix} a & if p \in S, \\ b & if p \notin S . \end{matrix} \end{matrix}$ The set $S = f^{- 1} [{a}]$ is a $Σ_{2}^{0}$ -subset of $B$ . Hence, f is $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y. But its complement, the set $B ∖ S = f^{- 1} [{b}]$ is not a $Σ_{2}^{0}$ -subset of $B$ . Hence, f is not $Σ_{2}^{0}$ -measurable with respect to the discrete topology on Y. Finally, let us calculate the tree classes and forest classes associated with f. We observe that for all $p \in B ∖ S$ , $T_{0} (f, p) = T_{1} (f, p)$ , and a representant of this treeclass is the one-node tree whose only node is labeled with b. For all $p \in S$ we have $T_{0} (f, p) ≺_{0} T_{1} (f, p) = T_{2} (f, p)$ , a representant of the tree class $T_{0} (f, p)$ is the one-node tree whose only node is labeled with a while a representant of the tree class $T_{1} (f, p)$ is the one-node tree whose only node is labeled with b. Thus, $F_{1} (f) = F_{2} (f)$ , and a representant of the forest class $F_{1} (f)$ is again the one-node tree whose only node is labeled with b.

11. Forests describing topological reducibility degrees for relations with finite range

In this section we apply the results from Section 9 to relations $R \subseteq X \times Y$ with finite Y and deduce characterizations of Wadge reducibility $⩽_{Wa}$ , strong Weihrauch reducibility $⩽_{sW}$ and Weihrauch reducibility $⩽_{Wa}$ between such relations R by corresponding relations between forests associated with the relations R.

11.1. Forests and trees and admissible representations

First we show that equivalent representations lead to identical associated forest classes.

Lemma 11.1.
Let X be a set with two equivalent representations $ρ : \subseteq B \to X$ and $σ : \subseteq B \to X$ . Let $(Y, ⪯)$ be a bqo set. Then for all countable ordinals α and all functions $f : \subseteq X \to Y$ with countable range, $F_{α} (f \circ ρ) = F_{α} (f \circ σ)$ .
Proof.
That ρ and σ are equivalent means $ρ ⩽_{0} σ$ and $σ ⩽_{0} ρ$ . This implies $f \circ ρ ⪯_{0} f \circ σ$ and $f \circ σ ⪯_{0} f \circ ρ$ . Now the assertion follows directly from the $i = 0$ case of the second assertion of Proposition 9.5. □

The following proposition shows that, in the case of a second countable $T_{0}$ -space X, the forest class that describes the topological degree of a relation $R \subseteq X \times Y$ can be computed directly from R, without using any admissible representation of X. Proposition 11.2.
Let X be a second countable $T_{0}$ -spac. Let $ρ : \subseteq B \to X$ be an admissible representation of X. Let $(Y, ⪯)$ be a bqo set. Then for all countable ordinals α and all functions $f : \subseteq X \to Y$ with countable range, $F_{α} (f \circ ρ) = F_{α} (f)$ .
Proof.
Let $f : \subseteq X \to Y$ be a function with countable range. It is well known [13] that there exists an open admissible representation $σ : \subseteq B \to X$ . As ρ and σ are equivalent, by Lemma 11.1 we have $F_{α} (f \circ ρ) = F_{α} (f \circ σ)$ , for all countable ordinals. Therefore, it is sufficient to show $F_{α} (f \circ σ) = F_{α} (f)$ , for all countable ordinals. By induction over α we shall prove the following assertions:
For all open $U \subseteq B$ , $F_{α} ((f \circ σ) |_{U}) = F_{α} (f |_{σ [U]})$ ,

for all $p \in dom (f \circ σ)$ , $T_{α} (f \circ σ, p) = T_{α} (f, σ (p))$ .

For $α = 0$ these assertions follow from Lemma 8.1. Let us assume $α > 0$ . We obtain: $\begin{array}{rcl} F_{α} ((f \circ σ) |_{U}) & = & sup_{⪯_{0}} {T_{β} ((f \circ σ) |_{U}, p) : p \in dom (f \circ σ) \cap U, β < α}, \\ = & sup_{⪯_{0}} {T_{β} (f \circ σ, p) : p \in dom (f \circ σ) \cap U, β < α}, \\ = & sup_{⪯_{0}} {T_{β} (f, σ (p)) : p \in dom (f \circ σ) \cap U, β < α}, \\ = & sup_{⪯_{0}} {T_{β} (f, x) : x \in dom (f) \cap σ [U], β < α}, \\ = & F_{α} (f |_{σ [U]}) . \end{array}$ Let us consider some $p \in dom (f \circ σ)$ and set $x : = σ (p)$ . Let $V \subseteq X$ be an $(f, α)$ -neighbourhood of x. As σ is continuous the set $σ^{- 1} (V)$ is an open neighbourhood of p. Let $U \subseteq σ^{- 1} (V)$ be an $(f \circ σ, α)$ -neighbourhood of p. Then $σ [U] \subseteq V$ is an $(f, α)$ -neighbourhood of x as well, hence, $F_{α} (f |_{σ [U]}) = F_{α} (f |_{V})$ . We obtain $\begin{array}{rcl} T_{α} (f \circ σ, p) & = & treeclass (f (σ (p)), F_{α} ((f \circ σ) |_{U})) \\ = & treeclass (f (x), F_{α} (f |_{σ [U]})) \\ = & treeclass (f (x), F_{α} (f |_{V})) \\ = & T_{α} (f, x) . \end{array}$ This ends the proof by induction. Finally, consider $U : = B$ . □

11.2. Wadge reducibility

Remember that for a relation $R : \subseteq X \times Y$ by $F_{R}$ we denote the function $F_{R} : \subseteq X \to P {(Y)}_{\neq \emptyset}$ defined by $dom (F_{R}) : = dom (R)$ and $F_{R} (x) : = R [x]$ , for all $x \in dom (R)$ . In the following, on $P {(Y)}_{\neq \emptyset}$ we always consider the relation ⊇.

Theorem 11.3.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y be a finite set. Let $R \subseteq X \times Y$ be a relation such that there exists a countable ordinal α such that $F_{α} (F_{R} \circ ρ) = F_{α + 1} (F_{R} \circ ρ)$ . Then for any relation $R^{'} : \subseteq X^{'} \times Y$ the following two conditions are equivalent.
$R ⩽_{Wa} R^{'}$ ,

$F_{α} (F_{R} \circ ρ) \supseteq_{0} F_{α} (F_{R^{'}} \circ ρ^{'})$ .
If X, $X^{'}$ are even second countable $T_{0}$ -spaces then here one can replace $F_{α} (F_{R} \circ ρ)$ by $F_{α} (F_{R})$ , $F_{α + 1} (F_{R} \circ ρ)$ by $F_{α + 1} (F_{R})$ , and $F_{α} (F_{R^{'}} \circ ρ^{'})$ by $F_{α} (F_{R^{'}})$ .

Remember that by Lemma 11.1 the forest classes $F_{α} (F_{R} \circ ρ)$ etc. do not depend on the choice of the admissible representations ρ, $ρ^{'}$ .
Proof.
Let us note again that, because Y is finite, the partially ordered set $(P {(Y)}_{\neq \emptyset}, \supseteq)$ is a bqo set. The last assertion in the theorem follows directly from Proposition 11.2. We can apply the case $i = 0$ of the second assertion of Theorem 9.7 to the functions $F_{R} \circ ρ$ and $F_{R^{'}} \circ ρ^{'}$ and conclude that the condition $F_{α} (F_{R} \circ ρ) \supseteq_{0} F_{α} (F_{R^{'}} \circ ρ^{'})$ is equivalent to $F_{R} \circ ρ \supseteq_{0} F_{R^{'}} \circ ρ^{'}$ . By Corollary 5.4 this is equivalent to $R ⩽_{Wa} R^{'}$ . □

In the following corollary we consider the special case when the relations are actually functions, and we are content with considering second-countable $T_{0}$ -spaces. Corollary 11.4.
Let X, $X^{'}$ be second-countable $T_{0}$ -spaces. Let Y be a finite set. Let the relation ⪯ on Y be simply the equality relation. Let $f : \subseteq X \to Y$ be a function such that there exists a countable ordinal α with $F_{α} (f) = F_{α + 1} (f)$ . Let $f^{'} : \subseteq X^{'} \to Y$ be a function as well. Choose forests $F = (S, λ) \in F_{α} (f)$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (f^{'})$ . Then the following three conditions are equivalent.
$f ⩽_{Wa} f^{'}$ ,

$F_{α} (f) ⪯_{0} F_{α} (f^{'})$ ,

There exists a monotone function $h : S \to S^{'}$ that preserves the labels of the nodes.

Proof.
As the proof of Theorem 11.3, but with Lemma 5.2 and Lemma 4.2 instead of Corollary 5.4. □

11.3. Strong Weihrauch reducibility

First we consider relations with range in a finite $T_{0}$ -space. In the following, on $P {(Y)}_{\neq \emptyset}$ and on $P {(Y^{'})}_{\neq \emptyset}$ we always consider the relation ⊇.

Theorem 11.5.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y, $Y^{'}$ be finite $T_{0}$ -spaces. Let $R \subseteq X \times Y$ be a relation such that there exists a countable ordinal such that $F_{α} (F_{R} \circ ρ) = F_{α + 1} (F_{R} \circ ρ)$ . Then for any relation $R^{'} \subseteq X^{'} \times Y^{'}$ the following two conditions are equivalent.
$R ⩽_{sW} R^{'}$ ,

There exists a relatively continuous relation $O \subseteq Y^{'} \times Y$ such that $F_{α} (F_{R} \circ ρ) \supseteq_{1}^{B_{O}} F_{α} (F_{R^{'}} \circ ρ^{'})$ .

Remember that by Lemma 11.1 the forest classes $F_{α} (F_{R} \circ ρ)$ etc. do not depend on the choice of the admissible representations ρ, $ρ^{'}$ . Of course, if X and $X^{'}$ are second-countable $T_{0}$ -spaces then one can apply here Proposition 11.2 in a similar manner as in Theorem 11.3.
Proof.
According to Corollary 5.8 the first condition, $R ⩽_{sW} R^{'}$ , is equivalent to the existence of a relatively continuous relation $O \subseteq Y^{'} \times Y$ such that $F_{R} \circ ρ \supseteq_{1}^{B_{O}} F_{R^{'}} \circ ρ^{'}$ . According to the first assertion of Theorem 9.7 this is equivalent to the existence of a relatively continuous relation $O \subseteq Y^{'} \times Y$ such that $F_{α} (F_{R} \circ ρ) \supseteq_{1}^{B_{O}} F_{α} (F_{R^{'}} \circ ρ^{'})$ . □

Next we consider the more special case when the range is finite and discrete.
Theorem 11.6.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y, $Y^{'}$ be finite discrete spaces. Let $R \subseteq X \times Y$ be a relation such that there exists a countable ordinal such that $F_{α} (F_{R} \circ ρ) = F_{α + 1} (F_{R} \circ ρ)$ . Let $R^{'} \subseteq X^{'} \times Y^{'}$ be a relation. Choose $F = (S, λ) \in F_{α} (F_{R} \circ ρ)$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (F_{R^{'}} \circ ρ^{'})$ . Then the following three conditions are equivalent.
$R ⩽_{sW} R^{'}$ ,

$F_{α} (F_{R} \circ ρ) \supseteq_{1} F_{α} (F_{R^{'}} \circ ρ^{'})$ ,

There exists a monotone function $h : S \to S^{'}$ such that for all nonempty $M \subseteq S$ , if $⋂_{m \in M} λ (m) = \emptyset$ then $⋂_{m \in M} λ^{'} (h (m)) = \emptyset$ .

Proof.
“ $(1) \Leftrightarrow (2)$ ”: The condition $F_{α} (F_{R} \circ ρ) \supseteq_{1} F_{α} (F_{R^{'}} \circ ρ^{'})$ is equivalent to the existence of a good function $C : \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ (good with respect to ⊇ on both sets) such that $F_{α} (F_{R} \circ ρ) \supseteq_{1}^{C} F_{α} (F_{R^{'}} \circ ρ^{'})$ . According to the first assertion of Theorem 9.7 the condition $F_{α} (F_{R} \circ ρ) \supseteq_{1}^{C} F_{α} (F_{R^{'}} \circ ρ^{'})$ is equivalent to $F_{R} \circ ρ \supseteq_{1}^{C} F_{R^{'}} \circ ρ^{'}$ Finally, according to Corollary 5.9, the existence of a good function $C : \subseteq P {(Y^{'})}_{\neq \emptyset} \to P {(Y)}_{\neq \emptyset}$ such that $F_{R} \circ ρ \supseteq_{1}^{C} F_{R^{'}} \circ ρ^{'}$ is equivalent to the condition $R ⩽_{sW} R^{'}$ .

“ $(2) \Leftrightarrow (3)$ ”: The condition $F_{α} (F_{R}) \supseteq_{1} F_{α} (F_{R^{'}})$ is equivalent to $F \supseteq_{1} F^{'}$ . As $(P {(Y)}_{\neq \emptyset}, \supseteq)$ is a weakly bounded-complete poset Lemma 7.30 tells us that this is equivalent to the existence of a monotone function $h : S \to S^{'}$ such that, for all nonempty $M \subseteq T$ , if $λ^{'} [h [M]]$ is ⊇-upper bounded then $λ [M]$ is ⊇-upper bounded. But for a nonempty set $M \subseteq S$ , the set $λ [M]$ is ⊇-upper bounded if, and only if, $⋂_{m \in M} λ (m) \neq \emptyset$ , and the set $λ^{'} [h [M]]$ is ⊇-upper bounded if, and only if, $⋂_{m \in M} λ^{'} (h (m)) \neq \emptyset$ . □

In the following corollary we consider the special case when the relations are actually functions, and we are content with considering second-countable $T_{0}$ -spaces. Corollary 11.7.
Let X, $X^{'}$ be second-countable $T_{0}$ -spaces. Let Y, $Y^{'}$ be finite discrete spaces. Let the relations ⪯ resp. $⪯^{'}$ on Y resp. $Y^{'}$ be simply the equality relation. Let $f : \subseteq X \to Y$ be a function such that there exists a countable ordinal such that $F_{α} (f) = F_{α + 1} (f)$ . Let $f^{'} : \subseteq X^{'} \to Y^{'}$ be a function as well. Choose $F = (S, λ) \in F_{α} (f)$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (f^{'})$ . Then the following three conditions are equivalent:
$f ⩽_{sW} f^{'}$ ,

$F_{α} (f) ⪯_{1} F_{α} (f^{'})$ ,

There exists a monotone function $h : S \to S^{'}$ such that for all elements $s_{1}, s_{2} \in S$ , if $λ (s_{1}) \neq λ (s_{2})$ then $λ^{'} (h (s_{1})) \neq λ^{'} (h (s_{2}))$ .

Proof.
First, one should apply Proposition 11.2. Next, one observes that for a function f and some $x \in dom (f)$ , $F_{f} (x) = {f (x)}$ and that the relation ⊇ restricted to sets containing exactly one element boils down to equality, that is, ${y_{1}} \supseteq {y_{2}} ⟺ y_{1} = y_{2}$ . Thus, we can identify $F_{f}$ with f, and we can identify the set of one-element subsets of Y together with the relation ⊇ with the set Y together with the equality relation. Now Theorem 11.6 implies the equivalence of the first two conditions. The equivalence of the second and the third condition follows from Remark 7.31. □

11.4. Weihrauch reducibility

Again, in the following, on $P {(Y)}_{\neq \emptyset}$ and on $P {(Y^{'})}_{\neq \emptyset}$ we always consider the relation ⊇.

Theorem 11.8.
Let X, $X^{'}$ be ${qcb}_{0}$ -spaces with admissible representations ρ, $ρ^{'}$ , respectively. Let Y, $Y^{'}$ be finite discrete spaces. Let $R \subseteq X \times Y$ be a relation such that there exists a countable ordinal such that $F_{α} (F_{R} \circ ρ) = F_{α + 1} (F_{R} \circ ρ)$ . Let $R^{'} \subseteq X^{'} \times Y^{'}$ be a relation. Choose $F = (S, λ) \in F_{α} (F_{R} \circ ρ)$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (F_{R^{'}} \circ ρ^{'})$ . Then the following three conditions are equivalent.
$R ⩽_{We} R^{'}$ ,

$F_{α} (F_{R} \circ ρ) \supseteq_{2} F_{α} (F_{R^{'}} \circ ρ^{'})$ ,

There exists a monotone function $h : S \to S^{'}$ such that for all nonempty $M \subseteq S$ having a smallest element, if $⋂_{m \in M} λ (m) = \emptyset$ then $⋂_{m \in M} λ^{'} (h (m)) = \emptyset$ .
If X, $X^{'}$ are even second countable $T_{0}$ -spaces then here one can replace $F_{α} (F_{R} \circ ρ)$ by $F_{α} (F_{R})$ , $F_{α + 1} (F_{R} \circ ρ)$ by $F_{α + 1} (F_{R})$ , and $F_{α} (F_{R^{'}} \circ ρ^{'})$ by $F_{α} (F_{R^{'}})$ .

Remember that by Lemma 11.1 the forest classes $F_{α} (F_{R} \circ ρ)$ etc. do not depend on the choice of the admissible representations ρ, $ρ^{'}$ .
Proof.
First we note that, because Y is finite, the partially ordered set $(P {(Y)}_{\neq \emptyset}, \supseteq)$ is a bqo set. The last assertion in the theorem follows directly from Proposition 11.2.

“ $1 \Leftrightarrow 2$ ”: We can apply the case $i = 2$ of the second assertion of Theorem 9.7 to the functions $F_{R} \circ ρ$ and $F_{R^{'}} \circ ρ^{'}$ and conclude that the condition $F_{α} (F_{R} \circ ρ) \supseteq_{2} F_{α} (F_{R^{'}} \circ ρ^{'})$ is equivalent to $F_{R} \circ ρ \supseteq_{2} F_{R^{'}} \circ ρ^{'}$ . We already mentioned that $F_{R} \circ ρ = F_{R \circ ρ}$ and, similarly, $F_{R^{'}} \circ ρ^{'} = F_{R^{'} \circ ρ^{'}}$ . Thus, the condition $F_{R} \circ ρ \supseteq_{2} F_{R^{'}} \circ ρ^{'}$ is equivalent to $F_{R \circ ρ} \supseteq_{2} F_{R^{'} \circ ρ^{'}}$ . According to Lemma 5.17 this condition is equivalent to $R \circ ρ ⩽_{2} R^{'} \circ ρ^{'}$ . Finally, by Lemma 4.11 this is equivalent to $R ⩽_{We} R^{'}$ .

“ $2 \Leftrightarrow 3$ ”: Note that for any finite set Y the preordered set $(P {(Y)}_{\neq \emptyset}, \supseteq)$ is a weakly bounded complete poset. Hence, the equivalence of Conditions 2 and 3 follows from Lemma 7.19 and Remark 7.20. □

In the following corollary we consider the special case when the relations are actually functions, and we are content with considering second-countable $T_{0}$ -spaces. Corollary 11.9.
Let X, $X^{'}$ be second-countable $T_{0}$ -spaces. Let Y, $Y^{'}$ be finite discrete spaces. Let the relations ⪯ resp. $⪯^{'}$ on Y resp. $Y^{'}$ be simply the equality relation. Let $f : \subseteq X \to Y$ be a function such that there exists a countable ordinal such that $F_{α} (f) = F_{α + 1} (f)$ . Let $f^{'} : \subseteq X^{'} \to Y^{'}$ be a function as well. Choose $F = (S, λ) \in F_{α} (f)$ and $F^{'} = (S^{'}, λ^{'}) \in F_{α} (f^{'})$ . Then the following three conditions are equivalent.
$f ⩽_{We} f^{'}$ ,

$F_{α} (f) ⪯_{2} F_{α} (f^{'})$ ,

There exists a monotone function $h : S \to S^{'}$ such that for all elements $s_{1}, s_{2} \in S$ , if ( $λ (s_{1}) \neq λ (s_{2})$ and $s_{1} ⊑ s_{2}$ ) then $λ^{'} (h (s_{1})) \neq λ^{'} (h (s_{2}))$ .

Proof.
The proof is very similar to the proof of Corollary 11.7. One applies Proposition 11.2, Theorem 11.8, and Remark 7.22. □

11.5. Examples

Example 11.10.
This example is a continuation of Examples 4.12 and 8.4. In Example 4.12 we defined a continuous function I such that ${LLPO}_{n} \circ I$ is a refinement of ${LLPO}_{n + 1}$ . Thus, it shows $F_{{LLPO}_{n + 1}} \supseteq_{0} F_{{LLPO}_{n}}$ . Hence, according to the $i = 0$ case of the second assertion of Proposition 9.5, it implies $T_{1} (F_{{LLPO}_{n + 1}}, 0^{ω}) \supseteq_{0} T_{1} (F_{{LLPO}_{n}}, 0^{ω})$ and also $F_{2} (F_{{LLPO}_{n + 1}}) \supseteq_{0} F_{2} (F_{{LLPO}_{n}})$ . Indeed, by following the construction underlying the proof of Proposition 9.1 one may say that I induces the monotone function $h : S^{(n + 1)} \to S^{(n)}$ defined by $\begin{array}{l} h (ε) : = ε, \\ h (n) : = ε, \\ h (i) : = i, for i \in [n] . \end{array}$ It has the property $λ^{(n + 1)} (s) \supseteq λ^{(n)} (h ((s)))$ , for all $s \in S^{(n + 1)}$ . Thus, it shows $F^{(n + 1)} \supseteq_{0} F^{(n)}$ ; see Fig. 1 in Section 8.1.

We still wish to show ${LLPO}_{n} ≰_{We} {LLPO}_{n + 1}$ , for $n ⩾ 2$ . We wish to apply Theorem 11.8. For the sake of a contradiction, let us assume ${LLPO}_{n} ⩽_{We} {LLPO}_{n + 1}$ . Then, according to Theorem 11.8, there exists a monotone function $h : S^{(n)} \to S^{(n + 1)}$ such that for all nonempty $M \subseteq S^{(n)}$ having a smallest element, if $⋂_{m \in M} λ^{(n)} (m) = \emptyset$ then $⋂_{m \in M} λ^{(n + 1)} (h (m)) = \emptyset$ . In fact, there is only one set $M \subseteq S^{(n)}$ having a smallest element with $⋂_{m \in M} λ^{(n)} (m) = \emptyset$ ; this is the set $M = S^{(n)}$ . As h is monotone, the range of h can contain at most n of the $n + 1$ sons $0 i$ , for $i = 0 \dots, n$ , of 0 in the tree $F^{(n + 1)}$ . So, let us fix a number $i \in [n + 1]$ with $0 i \in S^{(n + 1)} ∖ range (h)$ . We obtain $\begin{matrix} ⋂_{m \in S^{(n)}} λ^{(n + 1)} (h (m)) \supseteq ⋂_{m^{'} \in S^{(n + 1)} ∖ {0 i}} λ^{(n + 1)} (m^{'}) = {i} \neq \emptyset . \end{matrix}$ This is a contradiction. We have shown ${LLPO}_{n} ≰_{We} {LLPO}_{n + 1}$ .
Example 11.11.
This example is a continuation of Examples 4.13 and 8.5. We still wish to show ${LLPO}_{n} ≰_{We} {LLPO}_{\infty}$ , for $n ⩾ 2$ . Let us fix some $n ⩾ 2$ . Remember that in Example 4.13 we have already shown ${LLPO}_{\infty} ⩽_{Wa} {LLPO}_{n}$ . If for some $n ⩾ 2$ , ${LLPO}_{n} ⩽_{We} {LLPO}_{\infty}$ were true then we would have $\begin{matrix} {LLPO}_{n} ⩽_{We} {LLPO}_{\infty} ⩽_{Wa} {LLPO}_{n + 1}, \end{matrix}$ thus, ${LLPO}_{n} ⩽_{We} {LLPO}_{n + 1}$ , which is not true, as we have seen in Example 4.12.

But we can also prove the claim by computing the forests describing the discontinuity of ${LLPO}_{\infty}$ and by using the theorems proved in this section. In fact, in Example 8.5 we have seen that all tree classes $T_{α} (F_{{LLPO}_{\infty}}, p)$ for $p \in dom ({LLPO}_{\infty})$ and all countable ordinals α, all forest classes $F_{α} (F_{{LLPO}_{\infty}})$ , for all countable ordinals α, exist, although the range of ${LLPO}_{\infty}$ with the relation ⊇ is not a bqo set, and we have computed them. One can show the claim ${LLPO}_{n} ≰_{We} {LLPO}_{\infty}$ in the same way as we have shown the claim ${LLPO}_{n} ≰_{We} {LLPO}_{n + 1}$ in Example 11.10.
12. Open problems

We would like to conclude this paper with some open problems.

Let $(Y, ⪯)$ be a bqo set, and let $i \in {0, 1, 2}$ . In Theorem 10.6 we showed that the $⪯_{i}$ -degree structures for functions $f : B \to Y$ that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on Y and that have countable range, are isomorphic to the $⪯_{i}$ -degree structures of the forest classes of nonempty forests labeled with elements from Y. For $i = 0$ and k-partitions this result has already been extended by Selivanov [19] to $Δ_{3}^{0}$ -measurable k-partitions [19], and by Kihara and Montalbán [12] to all Borel measurable functions $f : B \to Y$ where Y is any bqo set. It is very likely that a similar extension is possible also for $i = 1$ and $i = 2$ . In fact, I expect that the definition of the tree classes and forest classes associated with functions in Section 8.1 can be extended to arbitrary Borel measurable function $f : B \to Y$ , of course, using trees labeled with trees, and iterating this, and that the results proved in Section 9 can be extended as well.

While this would certainly be interesting, it would still mainly cover only functions with range in a bqo set (and some exceptional other functions) and only relations with a rather restricted range, e.g., with a finite discrete range. Furthermore, for applications the relations $⩽_{Wa}$ , $⩽_{sW}$ , and $⩽_{We}$ for multivalued functions between topological spaces are probably more interesting than the relations $⪯_{0}$ , $⪯_{1}$ , and $⪯_{2}$ for functions with range in preordered sets. Therefore, it would be interesting to obtain similar characterizations of these reducibility relations for (multivalued) functions with more general range. A first result in this direction for Weihrauch reducibility of functions with countable discrete range can be found in [8].

There are a lot of operators on multi-valued functions that are important in the theory of Weihrauch degrees; see [2]. It might be interesting to analyze what effect they have on the tree classes and forest classes associated with multi-valued functions when they are applied to multi-valued functions.

One may of course try to compute the tree classes and forest classes associated with multi-valued functions appearing in the practice of computing. They provide a kind of combinatorial description of the discontinuities of computation problems. It would be interesting to see whether this description turns out to be useful for understanding better the discontinuities of computation problems and for implementing algorithms for them.

References

Brattka, Computability over topological structures, in: Computability and Models,

S.B.

Cooper and

S.S.

Goncharov, eds, Kluwer Academic Publishers, New York, 2003, pp. 93–136. doi:10.1007/978-1-4615-0755-0_5.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, arXiv.orgarXiv:1707.03202v4 (2018).

K.J.

Devlin, Fundamentals of Contemporary Set Theory, Springer, Berlin, 1979. doi:10.1007/978-1-4684-0084-7.

Gherardi and

Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame Journal of Formal Logic50(4) (2009), 393–425. doi:10.1215/00294527-2009-018.

Goubault-Larrecq, Non-Hausdorff Topology and Domain Theory, Cambridge University Press, Cambridge, 2013. doi:10.1017/CBO9781139524438.

Hertling, A topological complexity hierarchy of functions with finite range, Technical report, 223, Centre de recerca matematica, Institut d’estudis catalans, Barcelona, 1993, Workshop on Continuous Algorithms and Complexity.

Hertling, Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, Informatik Berichte, 152, FernUniversität Hagen, Hagen, 1993.

Hertling, Unstetigkeitsgrade von Funktionen in der effektiven Analysis, PhD thesis, Fachbereich Informatik, FernUniversität Hagen, 1996.

Hertling and

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

Brattka,

Diener and

Spreen, eds, Ontos Mathematical Logic, Walter de Gruyter, Boston, 2014, pp. 165–190.

10.

M.D.

Hirsch, Applications of topology to lower bound estimates in computer science, in: From Topology to Computation: Proceedings of the Smalefest, Springer-Verlag, New York, 1993, pp. 395–418, Papers presented at the conference “From topology to computation: Unity and diversity in the mathematical sciences” held at the University of California at Berkeley, USA, August 5-9, 1990 in honor of Stephen Smale’s 60th birthday. doi:10.1007/978-1-4612-2740-3_37.

11.

A.S.

Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Vol. 156, Springer-Verlag, 1995. doi:10.1007/978-1-4612-4190-4.

12.

Kihara and

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

13.

Kreitz and

Weihrauch, Theory of representations, Theoretical Computer Science38 (1985), 35–53. doi:10.1016/0304-3975(85)90208-7.

14.

Laver, Better-quasi-orderings and a class of trees, in: Studies in Foundations and Combinatorics, Adv. Math., Suppl. Stud., Vol. 1, 1978, pp. 31–48.

15.

C.S.J.A.

Nash-Williams, On well-quasi-ordering infinite trees, Proc. Camb. Philos. Soc.61 (1965), 697–720. doi:10.1017/S0305004100039062.

16.

Schröder, Admissible representations for continuous computations, PhD thesis, Fachbereich Informatik, FernUniversität Hagen, 2002.

17.

Schröder, Extended admissibility, Theoretical Computer Science284(2) (2002), 519–538. doi:10.1016/S0304-3975(01)00109-8.

18.

V.L.

Selivanov, Hierarchies of

Δ_{2}^{0}

-measurable k-partitions, Mathematical Logic Quarterly53(4–5) (2007), 446–461. doi:10.1002/malq.200710011.

19.

V.L.

Selivanov, Extending Wadge theory to k-partitions, in: Unveiling Dynamics and Complexity,

Kari,

Manea and

Petre, eds, Lecture Notes in Computer Science, Vol. 10307, Springer, Cham, 2017, pp. 387–399, 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. doi:10.1007/978-3-319-58741-7_36.

20.

V.L.

Selivanov, Towards a descriptive theory of

{cb}_{0}

-spaces, Math. Structures Comput. Sci.27(8) (2017), 1553–1580. doi:10.1017/S0960129516000177.

21.

S.G.

Simpson, BQO theory and Fraissés conjecture, in: R. Mansfield and G. Weitkamp: Recursive Aspects of Descriptive Set Theory. With a Chapter by Stephen Simpson, Oxford University Press, Oxford, 1985, pp. 124–138.

22.

van Engelen,

A.W.

Miller and

Steel, Rigid Borel sets and better quasiorder theory, in: Logic and Combinatorics, Contemp. Math., Vol. 65, 1987, pp. 199–222, Proc. AMS-IMS-SIAM Conf., Arcata/Calif. 1985.

23.

von Stein, Vergleich nicht konstruktiv lösbarer Probleme in der Analysis, 1989, Diplomarbeit, Fakultät für Informatik, FernUniversität Hagen.

24.

W.W.

Wadge, Reducibility and determinateness on the Baire space, PhD thesis, University of California, Berkeley, 1984.

25.

Weihrauch, The degrees of discontinuity of some translators between representations of the real numbers, Informatik Berichte, 129, FernUniversität Hagen, Hagen, 1992.

26.

Weihrauch, The TTE-interpretation of three hierarchies of omniscience principles, Informatik Berichte, 130, FernUniversität Hagen, Hagen, 1992.

Forests describing Wadge degrees and topological Weihrauch degrees of certain classes of functions and relations

Abstract

Keywords

1. Introduction

2. Sets, relations, and functions

2.1. Sets

2.2. Relations and functions

2.3. Finite and infinite sequences

2.4. Relations with special properties

Example 2.2. If X is the empty set then there is only one relation ⪯ on X: the empty relation ⪯ = ∅ . It is a linear order and well-founded. We obtain rank ( X , ⪯ ) = 0 . 2.6. The composition of relations

3.1. Topological spaces

3.3. Admissible representations

4.1. Wadge reducibility of relations

5.1. Wadge reducibility

7.1. A reducibility on labeled forests corresponding to Wadge reducibility on functions

Corollary 7.8. Let ( Y , ⪯ ) be a bqo set. Then the partial order ⪯ 0 on Forestclasses ( Y ) is a bqo. Proof. This follows from the previous proposition and from Lemma 6.1.3. □ 7.2. A reducibility on labeled forests corresponding to Weihrauch reducibility on functions

8.1. The definition of the trees and forests

9.1. Weihrauch reducibility with parameter

10.1. Functions, forests and their ranks

11.1. Forests and trees and admissible representations

References

Example 2.2.
If X is the empty set then there is only one relation ⪯ on X: the empty relation $⪯ = \emptyset$ . It is a linear order and well-founded. We obtain $rank (X, ⪯) = 0$ .

2.6. The composition of relations

Corollary 7.8.
Let $(Y, ⪯)$ be a bqo set. Then the partial order $⪯_{0}$ on $Forestclasses (Y)$ is a bqo.
Proof.
This follows from the previous proposition and from Lemma 6.1.3. □

7.2. A reducibility on labeled forests corresponding to Weihrauch reducibility on functions