Q-Wadge degrees as free structures

Abstract

A natural extension of the Wadge hierarchy is obtained if we consider k-partitions (or even Q-partitions for a countable better quasiorder Q) of the Baire space instead of sets (i.e., 2-partitions). Natural initial segments of the Q-Wadge hierarchy were recently characterised in terms of the so called h-quasiorder on suitably iterated Q-labeled countable well founded forests. Though these characterisations are natural and constructive, their definitions are rather long and technical. In this paper, we find clear shorter characterizations as (reducts of) a kind of free structures satisfying some natural axioms. Informally, we provide short and clear axiomatisations of the initial segments.

Keywords

Wadge degree better quasiorder semilattice labeled forest free structure

1. Introduction

For subsets A, B of the Baire space $N = ω^{ω}$ , A is Wadge reducible to B ( $A ⩽_{W} B$ ), if $A = f^{- 1} (B)$ for some continuous function f on $N$ . The quotient-poset of the preorder $(P (N); ⩽_{W})$ under the induced equivalence relation $\equiv_{W}$ on the power-set of $N$ is called the structure of Wadge degrees in $N$ . W. Wadge [20] characterised the structure of Wadge degrees of Borel sets (i.e., the quotient-poset of $(Δ_{1}^{1} (N); ⩽_{W})$ ) up to isomorphism. In particular, this quotient-poset is well-founded and has no 3 pairwise incomparable elements. The Wadge hierarchy subsumes many classical hierarchies of sets, including the Borel hierarchy and the Hausdorff difference hierarchy.

A natural extension of the Wadge hierarchy is the extension from the case of subsets of $N$ to the case of functions $A : N \to Q$ to an arbitrary quasiorder Q. We identify such functions with Q-partitions of $N$ of the form ${A^{- 1} (q)}_{q \in Q}$ in order to stress a close relation of them to k-partitions (obtained when $Q = \bar{k} = {0, \dots, k - 1}$ is an antichain with k-elements) studied by several authors. For Q-partitions A and B, let $A ⩽_{W} B$ mean that there is a continuous function f on $N$ such that $A (x) ⩽_{Q} B (f (x))$ for each $x \in N$ . We call the corresponding equivalence classes Q-Wadge degrees. The case of sets corresponds to the case of 2-partitions.

Let $Δ_{1}^{1} (Q^{N})$ be the set of Borel Q-partitions A (those for which $A^{- 1} (q) \in Δ_{1}^{1} (N)$ for all $q \in Q$ ). A celebrated theorem of van Engelen, Miller and Steel (see Theorem 3.2 in [18]) implies that if Q is a countable better quasiorder (bqo) then $W_{Q} = (Δ_{1}^{1} (Q^{N}); ⩽_{W})$ is a bqo. Although this theorem gives an important information about the quotient-poset of $W_{Q}$ , it is far from a characterisation.

Many efforts (see e.g. [3,12,14,16] and references therein) to characterise the quotient-poset of $W_{Q}$ were devoted to the k-partitions of $N$ . Our approach in [12,14,16] to this problem was to characterise the initial segments $(Δ_{α}^{0} (k^{N}); ⩽_{W})$ for bigger and bigger ordinals $2 ⩽ α < ω_{1}$ where $Δ_{α}^{0}$ are the delta-levels of the Borel hierarchy [4]. To achieve this, we defined the structures of iterated labeled forests with the so called h-quasiorder and discovered useful properties of some natural operations on the iterated labeled forests. In this way, we characterised the quotient poset of $(Δ_{α}^{0} (k^{N}); ⩽_{W})$ for $α = 2, 3$ [11,14,16].

An important progress was recently achieved in [5] where a full characterisation for arbitrary $α < ω_{1}$ and Q is obtained, based on the (suitably extended) iterated labeled forests and on computability theory. Interestingly, these characterizations give new information even for the case of 2-partitions (i.e., subsets of the Baire space) and they look very different from the classical ones. For more complicated Q-partitions, even for k-partitions with $k ⩾ 3$ , the forest characterizations are in fact the only known so far.

Though the forest characterizations are very natural and constructive, their definitions are rather long and technical. In this paper, we attempt to find clear shorter characterizations. To achieve this goal, we formulate some natural axioms for theories in signatures expanding the signature and axioms of σ-semilattices (i.e., upper semilattices with countable supremums). Then we show that many initial segments of $W_{Q}$ (including $W_{Q}$ itself) are (reducts of) free structures of suitable such theories. Informally, in this way we obtain a kind of axiomatizations for the initial segments of $W_{Q}$ . More precisely, for every “closed enough” initial segment of $W_{Q}$ we find a corresponding theory with the property described above. Bigger initial segments correspond to theories with bigger signatures and sets of axioms.

Though our axiomatic characterisations are much shorter than the forest characterisations, our proofs in fact essentially use the forest characterisations. The proof ideas are very similar to the standard ideas of universal algebra where free and finitely presented structures play a noticeable role. We cannot use the results of universal algebra directly because there people work with operations of finite arity while here countable supremums are deeply involved. Our proofs are rather easy, compared with the forest characterisations of Q-Wadge degrees [5,16].

After recalling some preliminaries in the next section, in Section 3 we explain our approach on the simple example of σ-semilattices which suffice to characterise the quotient poset of $(Δ_{α}^{0} (Q^{N}); ⩽_{W})$ for $α = 1$ . In the three subsequent sections we expand this approach and get axiomatic characterisations for $α = 2, ω$ , and $ω^{γ}$ , for any non-zero countable ordinal γ. In Section 7 we briefly discuss a finitary version of our approach (where the usual semilattices are taken in place of σ-semilattices).

The idea to use free and finitely presented structures to characterise the Wadge degrees of k-partitions first appeared in [11] where we sketched characterisations equivalent to those in Section 4.

2. Preliminaries

2.1. Baire space, trees and forests

We use the standard set-theoretic notation, in particular we identify the set of natural numbers with the first infinite ordinal ω. The first uncountable ordinal is denoted by $ω_{1}$ . Let $N = ω^{ω}$ be the set of all infinite sequences of natural numbers (i.e., of functions $x : ω \to ω$ ). Let $ω^{*}$ be the set of finite sequences of elements of ω, including the empty sequence ε. For $σ, τ \in ω^{*}$ and $x \in N$ , we write $σ ⊑ τ$ (resp. $σ ⊑ x$ ) to denote that σ is an initial segment of τ (resp. of x). By $σ x = σ \cdot x$ we denote the concatenation of σ and x, and by $σ \cdot N$ the set of all extensions of σ in $N$ . For $x \in N$ , we write $x = x (0) x (1) \dots$ where $x (i) \in ω$ for each $i < ω$ . For $x \in N$ and $n < ω$ , $x [n] = x (0) \dots x (n - 1)$ is the initial segment of x of length n.

By endowing $N$ with the product of the discrete topologies on ω, we obtain the so-called Baire space. The product topology coincides with the topology generated by the collection of sets of the form $σ \cdot N$ for $σ \in ω^{*}$ . Working in the Baire space often involves trees. A tree is a non-empty set $T \subseteq ω^{*}$ which is closed downwards under the prefix order ⊑. A leaf of T is a maximal element of $(T; ⊑)$ . A path through a tree T is an element $x \in N$ such that $x [n] \in T$ for each $n \in ω$ . For any tree T, the set $[T]$ of paths through T is closed in $N$ . A tree T is well founded if $[T] = \emptyset$ .

Along with the trees, we often use non-empty well founded forests of the form $T ∖ {ε}$ where T is a tree. The “concrete” trees and forests defined above are sufficient for defining the h-preorders in the sequel, though in the existing literature [5,11] people often work with “abstract” well founded countable trees and forests. It is easy to see that any “abstract” tree or forest is isomorphic to a suitable “concrete” one. This obvious observation sometimes simplifies definitions of natural operations on trees and forests.

2.2. Ordinals, quasiorders, semilattices

We assume the reader to be acquainted with the notion of ordinal (see e.g. [7]). Ordinals are denoted by $α, β, γ, ξ, η, \dots$ . Every ordinal α is the set of all smaller ordinals, in particular $k = {0, 1, \dots, k - 1}$ for each $k < ω$ , and $ω = {0, 1, 2, \dots}$ . We use some well-known facts about the ordinal arithmetic. As usual, $α + β$ , $α \cdot β$ and $α^{β}$ denote the ordinal addition, multiplication and exponentiation of α and β, respectively.

We use some standard notation and terminology on partially ordered sets (posets) which may be found e.g. in [2]. Recall that a quasiorder (qo) is a structure $(P; ⩽)$ satisfying the axioms of reflexivity $\forall x (x ⩽ x)$ and transitivity $\forall x \forall y \forall z (x ⩽ y \land y ⩽ z \to x ⩽ z)$ . We often denote qo $(P; ⩽)$ just by P, in which case we can denote the corresponding relation as $⩽_{P}$ .

Partial order (poset) is a qo satisfying the antisymmetry axiom $\forall x \forall y (x ⩽ y \land y ⩽ x \to x = y)$ . Linear order is a partial order satisfying the connectivity axiom $\forall x \forall y (x ⩽ y \lor y ⩽ x)$ .

Any partial order ⩽ on P induces the relation of strict order < on P defined by $a < b \leftrightarrow a ⩽ b \land a \neq b$ and called the strict order related to ⩽. The relation ⩽ can be restored from <, so we may safely apply the terminology on partial orders also to the strict orders. Any subset of a poset P may be considered as a poset with the induced partial order.

It is well known that any qo $(P; ⩽)$ induces the partial order $(P^{*}; ⩽^{*})$ called the quotient poset of P. The set $P^{*}$ is the quotient set of P under the equivalence relation defined by $a \equiv b \leftrightarrow a ⩽ b \land b ⩽ a$ ; it consists of the equivalence classes $[a] = {x ∣ x \equiv a}$ , $a \in P$ . The partial order $⩽^{*}$ is defined by $[a] ⩽^{*} [b] \leftrightarrow a ⩽ b$ . To avoid complex notation, we sometimes abuse terminology about posets by applying it also to qo’s; in such cases we just mean the corresponding quotient poset of the qo. For quasiorders P and Q, let $P ≃ Q$ mean that the quotient posets of P and Q are isomorphic.

A qo $(P; ⩽)$ is well founded if it has no infinite descending chains. In this case there are a unique ordinal $rk (P)$ and a unique rank function ${rk}_{P}$ from P onto $rk (P)$ satisfying $a < b \to rk (a) < rk (b)$ . It is defined by induction ${rk}_{P} (x) = sup {{rk}_{P} (y) + 1 ∣ y < x}$ . The ordinal $rk (P)$ is called the rank (or height) of P, and the ordinal ${rk}_{P} (x)$ is called the rank of $x \in P$ in P. Note that a tree T is well founded in the sense of the previous subsection iff $(T; ⊒)$ (reverse prefix relation) is well founded. Note also that the ordinals may be considered as the order types of well orders, i.e., of well founded linear orders.

A well quasiorder (wqo) is a qo that has neither infinite descending chains nor infinite antichains. Although the wqo’s are closed under many natural finitary constructions like forming finite labeled words or trees, they are not always closed under important infinitary constructions. Nevertheless, it turns out possible to find a natural subclass of wqo’s, called better quasiorders (bqo’s) which contains most of the “natural” wqo’s (in particular, all finite qo’s) and has strong closure properties also for many infinitary constructions. The notion of bqo is due to C. Nash-Williams [8] (see also [5,17]). We omit the definition of bqo because it is a bit technical and is used only in formulations. For well and better partial orders we use abbreviations wpo and bpo, respectively.

In the sequel we often deal with semilattices expanded by some additional operations. Recall that semilattice is a structure $(S; ⊔)$ with binary operation ⊔ such that $(x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)$ , $x ⊔ y = y ⊔ x$ and $x ⊔ x = x$ , for all $x, y, z \in S$ . By ⩽ we denote the induced partial order on S: $x ⩽ y$ iff $x ⊔ y = y$ . The operation ⊔ can be recovered from ⩽ since $x ⊔ y$ is the supremum of x, y w.r.t. ⩽.

By σ-semilattice we mean a semilattice where also supremums $⨆ y_{j} = y_{0} ⊔ y_{1} ⊔ \dots$ of countable sequences of elements $y_{0}, y_{1}, \dots$ exist. Sometimes we denote semilattices (and σ-semilattices) as $(S; ⩽, ⊔)$ meaning that ⩽ is the induced partial order. Note that the operation of countable supremum is associative, commutative, and depends only on the set of its arguments, so it is also correct to use notation like $⨆ Y$ where $Y = {y_{0}, \dots}$ .

Element x of a σ-semilattice S is σ-join-reducible if it can be represented as the countable supremum of some elements strictly below x. Element x is σ-join-irreducible if it is not σ-join-reducible. As stressed in [11], the σ-join-irreducible elements play a central role in the study of Wadge degrees of k-partitions, and the same applies to Q-Wadge degrees for a countable bqo Q. We will return to σ-semilattices in Section 3.

2.3. Tree calculus

For any qo Q, a Q-tree is a pair $(T, t)$ consisting of a well founded tree $T \subseteq ω^{*}$ and a labeling $t : T \to Q$ . Let $T (Q)$ be the set of Q-trees quasi-ordered by the relation: $(T, t) ⩽_{h} (V, v)$ iff there is a monotone function $φ : T \to V$ with $\forall x \in T (t (x) ⩽_{Q} v (φ (x)))$ . Let $T^{⊔} (Q)$ be defined similarly but with forests (i.e., the sub-qo $T ∖ {ε}$ of a tree T) in place of trees. As follows from Laver’s theorem, if Q is bqo then so are also $T (Q)$ and $T^{⊔} (Q)$ , hence $T$ is an operator on the class BQO of all bqo’s. This operator was introduced in [11] and turned out useful (together with some of its iterates) for characterising some initial segments of $W_{Q}$ (we warn the reader that operator $T$ is denoted $\tilde{T}$ in [11]). As observed in [11,14], $T^{⊔} (Q)$ is a σ-semilattice (the countable supremum operation ⨆ is the disjoint union of labeled forests). The σ-join-irreducible elements of $T^{⊔} (Q)$ are precisely those h-equivalent to the elements of $T (Q)$ .

Next we recall iterations of $T$ from [14,16]. For any $q \in Q$ , let $s (q)$ be the singleton tree labeled by q, then $s : Q \to T (Q)$ is an embedding of qo’s. Identifying q with $s (q)$ , we may think that Q is a substructure of $T (Q)$ . We iterate the operator $T$ as follows: $T^{0} (Q) = Q$ , $T^{α + 1} (Q) = T (T^{α} (Q))$ , and $T^{λ} (Q) = ⋃_{α < λ} T^{α} (Q)$ for a limit ordinal λ. Then ${T^{α} (Q)}$ is an increasing sequence of bqo’s. Since all our trees are countable, $T^{ω_{1}} (Q)$ is a fixed point of this iteration procedure. The function s is naturally extended to a function s on $T^{ω_{1}}$ such that $q = s (q)$ , $T ⩽_{h} s (T)$ , and $T ⩽_{h} V$ iff $s (T) ⩽_{h} s (V)$ . This iteration procedure was extended in [5] by considering operations ${(s_{α})}_{α < ω_{1}}$ in place of just one function s (to unify and simplify notation, we use the notation $s_{α} (T)$ instead of the notation ${⟨ T ⟩}^{ω^{α}}$ in [5]). The idea of the iteration may be described as follows: First take the ( $ω_{1}$ st) fixed point $T_{ω} : = T^{ω_{1}}$ closed under $s_{0} = s$ ; then add new $s_{1}$ which enumerates fixed points for $s_{0}$ in the sense that $s_{0} (s_{1} (T)) \equiv_{h} s_{1} (T)$ , and take the ( $ω_{1}$ st) fixed point $T_{ω^{2}}$ closed under $s_{0}$ and $s_{1}$ . Continue this Veblen-like procedure to produce ${(T_{ω^{α}}; s_{α})}_{α < ω_{1}}$ .

We now give the precise inductive definition of ${(T_{ω^{α}}, T_{ω^{α}}^{⊔})}_{α < ω_{1}}$ formalizing the idea described in the previous paragraph. In [5, Definition 3.19], $T_{ω^{α}}^{⊔} (Q)$ is defined as a set of terms in the language consisting of constant symbols $s_{α} (q)$ for $q \in Q$ , a 2-ary function symbol ·, an ω-ary function symbol ⨆, and unary function symbols $s_{β}$ for $β < α$ : Every constant symbol is a singleton term, and every singleton term is a tree term. If ${(S_{i})}_{i \in ω}$ is a sequence of tree terms, then $⨆_{i} S_{i}$ is a forest term. If S is a singleton term and F is a forest term, then $S \cdot F$ is a tree term. If T is a tree term, then $s_{β} (T)$ is a singleton term for any $β < α$ . Then $T_{ω^{α}} (Q)$ is the set of all tree terms, and $T_{ω^{α}}^{⊔} (Q)$ is the set of all tree and forest terms. Finally, let $T_{ω_{1}} (Q) = ⋃_{α < ω_{1}} T_{ω^{α}} (Q)$ , and similarly for $T_{ω_{1}}^{⊔} (Q)$ .

As in [5, Definition 3.20], we inductively define a qo $⩽_{h}$ on $T_{ω_{1}}^{⊔} (Q)$ as follows: For $p, q \in Q$ and $α < ω_{1}$ , $p \equiv_{h} s_{α} (p)$ , and $p ⩽_{h} q$ iff $p ⩽_{Q} q$ . For singletons $s_{α} (U)$ and $s_{β} (V)$ , $s_{α} (U) ⩽_{h} s_{β} (V)$ is equivalent to $U ⩽_{h} V$ if $α = β$ ; to $s_{α} (U) ⩽_{h} V$ if $α > β$ ; and to $U ⩽_{h} s_{β} (V)$ if $α < β$ . For singletons A, C and forests B, D (where the empty forests are allowed, cf. [5, Definition 3.20]), define $A \cdot B ⩽_{h} C \cdot D$ if either $A ⩽_{h} C$ and $B ⩽_{h} C \cdot D$ , or $A ≰_{h} C$ and $A \cdot B ⩽_{h} D$ . Moreover, $B = ⨆_{i} B_{i} ⩽_{h} C \cdot D$ iff $B_{i} ⩽_{h} C \cdot D$ for any i, and $A \cdot B ⩽_{h} D = ⨆_{i} D_{i}$ iff $A \cdot B ⩽_{h} D_{i}$ for some i. Again, $T_{ω_{1}}^{⊔} (Q)$ is a σ-semilattice the σ-join-irreducible elements of which are precisely those h-equivalent to the elements of $T_{ω_{1}} (Q)$ .

See also [6 ,9 ,15] for additional information on the h-qo, in particular on a comparison of definitions in [14,16] with those in [5] which look a bit different at first glance.

2.4. Some categorical notions

Here we briefly recall some categorical notions related to that of a free structure. We assume the reader to be acquainted with basic notions of category theory like category, functor and natural transformation.

An object I of a category C is initial if for any object C of C there is a unique morphism from I to C. If the initial object exists then it is unique up to C-isomorphism.

Definition 1.
An adjunction between categories C and D is a triple $(F, U, η)$ consisting of functors $F : C \to D$ , $U : D \to C$ and a natural transformation $η : 1_{C} \to U \circ F$ such that for all $C \in C$ , $D \in D$ and $f : C \to U (D)$ there exists a unique $g : F (C) \to D$ with $f = U (g) \circ η_{C}$ . Functors F and U are called resp. left and right adjoints while η is called the unit of the adjunction.

Note that the condition above induces an isomorphism between ${Hom}_{D} (F (C), D)$ and ${Hom}_{C} (C, U (D))$ for all $C \in C$ , $D \in D$ . We took this version of definition of adjoint functors from p. 180 of [1] because it straightforwardly generalises definitions of free structures which one often meets in the literature on universal algebra. In this context, U is a naturally defined “forgetful” functor and $F (C)$ is a free D-structure generated by C.

In this paper, C will be the category $PO$ of posets (with monotone functions as morphisms) or a suitable full subcategory of $PO$ , D the category $σ SL$ of σ-semilattices (with functions preserving the countable supremums as morphisms) or a suitable modification of $σ SL$ , and U the “forgetful” functor that forgets all the structure except the underlying partial order. The functor F will depend on the precise definition of the involved categories.

Along with free structures, in the literature on universal algebra one often meets finitely (or infinitely) presented structures satisfying a given set of identities (called also equalities). Such a structure $⟨ X ∣ R ⟩$ of some signature ρ is usually specified by a set X of “generators” and a set R of “relations” (which are atomic formulas of signature ρ expanded by the elements of X treated as new constant symbols). The structure $⟨ X ∣ R ⟩$ which (if exists) is unique up to isomorphism, is a structure of the expanded signature $ρ_{X}$ (so there is an interpreting function $f : X \to ⟨ X ∣ R ⟩$ ). The structure $⟨ X ∣ R ⟩$ is generated by $f (X)$ and has the following universality property: for any $ρ_{X}$ -structure D satisfying all the formulas in R there is a unique homomorphism $g : ⟨ X ∣ R ⟩ \to D$ which extends f. The existence of $⟨ X ∣ R ⟩$ is not always guaranteed but in many cases it does exist.

In this paper we will use some variants of the notion of (infinitely) presented structure defined as initial objects of suitable categories. To explain the relation of free objects to adjunctions we note that, for any object C of C, the pair $(F (C), η_{C})$ is an initial object in the category C-D whose objects are pairs $(D, f)$ such that D is an object of D and $f : C \to U (D)$ is a C-morphism, and whose morphisms $g : (D, f) \to (D^{'}, f^{'})$ are the D-morphisms $g : D \to D^{'}$ with $f^{'} = U (g) \circ f$ . For our versions of free and infinitely presented structures, we will use similar initial objects, for suitable versions of the category C-D.

Clearly, $(F, U, η)$ is an adjunction iff the “free object” $F (C)$ exists for any object C “uniformly” in the sense that F is a functor and $η : 1_{C} \to U \circ F$ is a natural transformation.
3. σ-Semilattices

In this section we give simple examples of free structures related to Wadge degrees. These examples will be subsequently developed and modified in the next sections.

3.1. Free σ-semilattices

Let $PO$ be the category of posets with the monotone functions as morphisms. Let $σ SL$ be the category of σ-semilattices with the functions preserving countable supremums, as morphisms. Let $U : σ SL \to PO$ be the forgetful functor.

Theorem 2.
The functor U has a left adjoint $F_{σ} : PO \to σ SL$ .
Proof.
Associate with any poset Q the qo $(Q^{}; ⩽^{})$ where $Q^{}$ is the set of non-empty countable subsets of Q with the so called domination qo* defined by: $S ⩽^{} R$ iff $\forall s \in S \exists r \in R (s ⩽ r)$ . Let $F_{σ} (Q)$ be the quotient-poset of $(Q^{}; ⩽^{})$ . Let ⨆ be the operation of countable supremum in $F_{σ} (Q)$ induced by the operation of countable union in $Q^{}$ . Then $F_{σ} (Q)$ is a σ-semilattice, so $F_{σ}$ maps the objects of $PO$ to those of $σ SL$ . For a morphism $f : P \to Q$ , let $F_{σ} (f) : F_{σ} (P) \to F_{σ} (Q)$ be the function induced by the image function $A \mapsto f (A)$ on $P^{}$ . We see that $F_{σ}$ is a functor from $PO$ to $σ SL$ .

The function $η_{Q} (q) = {q}$ is an injection of Q into $Q^{}$ that induces a natural transformation $η : 1_{PO} \to U \circ F_{σ}$ .

It remains to check that for any σ-semilattice $(S; ⨆)$ and any monotone $f : Q \to U (S)$ there is a unique $g : F_{σ} (Q) \to S$ with $f = U (g) \circ η_{Q}$ . It is easy to see that we can take the morphism g induced by $A \mapsto ⨆ f (A)$ , $A \in Q^{}$ . □

For any poset Q, we call $F_{σ} (Q)$ the free σ-semilattice generated by Q. To make notation more compatible with that of some other papers, we sometimes denote $F_{σ} (Q)$ as $Q^{⊔}$ .

From well known facts of bqo-theory, if Q is bpo then so is also ${UF}_{σ} (Q)$ . Thus, if we consider the full subcategories $BPO$ and $σ BSL$ of resp. $PO$ and $σ SL$ formed by the objects which are bpo’s, we obtain the corresponding restricted adjunction (denoted for simplicity by $(F_{σ}, U, η)$ again).

Note that, in general, $Q^{⊔}$ is a σ-semilattice without zero (i.e., a smallest element). There is an obvious modification of Theorem 2 for σ-semilattices with zero. The corresponding free object $Q_{⊥}^{⊔}$ is obtained from $Q^{⊔}$ by adjoining a new smallest element ⊥ (in our case, ⊥ is the equivalence class of empty subset of Q adjoined to $Q^{}$ ).
3.2. Distributive and well founded σ-semilattices

The well known notion of a distributive semilattice is straightforwardly extended to that of a distributive σ-semilattice. A σ-semilattice $(S; ⩽, ⨆)$ is distributive if the condition $x ⩽ y_{0} ⊔ y_{1} ⊔ \dots$ (also for countable supremums) implies that $x = x_{0} ⊔ x_{1} ⊔ \dots$ for some $x_{i} ⩽ y_{i}$ .

Proposition 3.
An element x of a distributive σ-semilattice $(S; ⩽, ⨆)$ is σ-join-irreducible iff the condition $x ⩽ y_{0} ⊔ y_{1} ⊔ \dots$ implies that $x ⩽ y_{i}$ for some i.
Proof.
Let x be σ-join-irreducible and $x ⩽ y_{0} ⊔ y_{1} ⊔ \dots$ . By distributivity, $x = x_{0} ⊔ x_{1} ⊔ \dots$ for some $x_{i} ⩽ y_{i}$ . By σ-join-irreducibility, $x ⩽ x_{i}$ for some i, hence $x ⩽ y_{i}$ for some i. The opposite direction is obvious. □

Most of σ-semilattices considered in this paper are close to distributive ones. A simple example is the structure $Q_{⊥}^{⊔}$ from the end of the previous subsection.
Proposition 4.
For any poset Q, $Q_{⊥}^{⊔}$ is a distributive σ-semilattice.
Proof.
We work with the qo $Q^{} ⊔ {\emptyset}$ from the proof of Theorem 2 (which now consists of all countable subsets of Q, including the empty set). Let $x ⩽ y_{0} ⊔ y_{1} ⊔ \dots$ where $x = [X]$ and $y_{i} = [Y_{i}]$ , i.e. $X ⩽^{} Y_{0} \cup Y_{1} \cup \dots$ . Then $X = X_{0} \cup X_{1} \cup \dots$ where $X_{i} = {x \in X ∣ \exists y \in Y_{i} (x ⩽ y)}$ . Thus, $x = x_{0} ⊔ x_{1} ⊔ \dots$ and $x_{i} ⩽ y_{i}$ where $x_{i} = [X_{i}]$ , so $Q_{⊥}^{⊔}$ is distributive. □

The second example is the following assertion which is close to the corresponding observations in [11,16] for $Q = \bar{k}$ and easy to check. The ω-ary operation ⨁ on $Q^{N}$ is defined by $⨁_{n} A_{n} (i \cdot x) = A_{i} (x)$ .
Proposition 5.
For any poset Q, the quotient structure of $(Q_{⊥}^{N}; ⩽_{W}, ⨁)$ is a distributive σ-semilattice.

In this paper, most of the σ-semilattices $(S; ⩽, ⨆)$ considered below are well founded (i.e., ⩽ is well founded). We show that in such σ-semilattices any non-zero element x has a decomposition $x = x_{0} ⊔ x_{1} ⊔ \dots$ to σ-join-irreducible elements $x_{i}$ . If such a decomposition is unique up to the domination equivalence $\equiv^{}$ in $S^{}$ then we call it canonical decomposition. Proposition 6.
Let $(S; ⩽, ⨆)$ be a well founded σ-semilattice. Then any non-zero element x has a decomposition, and if S is distributive then x has a canonical decomposition.
Proof.
We define a tree T and a labeling $t : T \to S$ by constructing their restrictions $T_{n}$ , $t_{n}$ to $ω^{⩽ n}$ for each n. Let $T_{0} = {ε}$ and $t (ε) = x$ . The tree $T_{n + 1}$ is obtained from $T_{n}$ by adding the nodes $τ i$ for each leaf τ of $T_{n}$ such that $t (τ)$ is σ-join-reducible, and by defining $t (τ i) = y_{i}$ , where $y_{0}, y_{1}, \dots$ is a sequence of elements of S such that $t (τ) = y_{0} ⊔ y_{1} ⊔ \dots$ and $y_{i} < t (τ)$ . By this construction, for any $τ \in T = ⋃_{n} T_{n}$ we have: τ is a leaf of T iff $t (τ)$ is σ-join-irreducible).

Since $t (τ i) < t (τ)$ for each $τ i \in T$ and S is well founded, T is also well founded. Let $ρ_{0}, ρ_{1}, \dots$ be an enumeration of all leafs of T and $x_{i} = t (ρ_{i})$ . Then $x = x_{0} ⊔ x_{1} ⊔ \dots$ and every $x_{i}$ is σ-join-irreducible, so we have a desired decomposition.

Let now S be distributive and $x = y_{0} ⊔ y_{1} ⊔ \dots$ be another decomposition of x; we have to show that ${x_{0}, \dots} \equiv^{*} {y_{0}, \dots}$ . By symmetry, it suffices to show that $\forall i \exists j (x_{i} ⩽ y_{j})$ . For any i we have $x_{i} ⩽ y_{0} ⊔ y_{1} ⊔ \dots$ . Since $x_{i}$ is σ-join-irreducible, by Proposition 3 $x_{i} ⩽ y_{j}$ for some j. □

3.3. Relation to Q-Wadge degrees

We are ready to characterise a simple initial segment of Q-Wadge degrees as a free structure.

Proposition 7.
For any countable bpo Q, the quotient poset of $(Δ_{1}^{0} (Q^{N}); ⩽_{W})$ is isomorphic to the ⩽-reduct ${UF}_{σ} (Q)$ of the initial object of Q- $σ SL$ .
Proof.
By the proof of Theorem 2 it suffices to show that ${UF}_{σ} (Q) ≃ (Δ_{1}^{0} (Q^{N}); ⩽_{W})$ , i.e. $(Δ_{1}^{0} (Q^{N}); ⩽_{W}) ≃ Q^{}$ . Associate with any $A \in Δ_{1}^{0} (Q^{N})$ the image $A (N) \in Q^{}$ , then A may be considered as a proper $A (N)$ -partition (a Q-partition C is proper if all of its components $C^{- 1} (q)$ are nonempty). Then $A ⩽_{W} B$ iff $A (N) ⩽^{} B (N)$ . Indeed, if $A ⩽_{W} B$ via f then $A (x) ⩽ B (f (x))$ for each $x \in N$ , hence $A (N) ⩽^{} B (N)$ . Conversely, let $A (N) ⩽^{} B (N)$ , then for some $g : A (N) \to B (N)$ we have $\forall q \in A (N) (q ⩽ g (q))$ . For any $q \in A (N)$ , choose $y_{q} \in N$ with $B (y_{q}) = g (q)$ . Now define a function f on $N$ by $f (x) = y_{A (x)}$ , then $A (x) ⩽ B (f (x))$ for each $x \in N$ . Since for each $Y \subseteq N$ the set $f^{- 1} (Y)$ is the union of some sets $A^{- 1} (q) \in Δ_{1}^{0} (N)$ , $q \in Q$ , and Q is countable, $f^{- 1} (Y) \in Σ_{1}^{0} (N)$ . Therefore, f is continuous and $A ⩽_{W} B$ .

It remains to check that for any non-empty $R \subseteq Q$ there is $A \in Δ_{1}^{0} (Q^{N})$ with $A (N) \equiv^{} R$ . Clearly, we can take $A = ⨁ {λ x . r ∣ r \in R}$ . □

4. τ-Semilattices

In this section we expand the signature ${⨆}$ of σ-semilattices to the signature $τ = {⨆, \cdot}$ (where · is a binary function symbol) and extend the axioms of σ-semilattices to some axioms of signature τ the models of which we call τ-semilattices.

4.1. Definition and examples

By τ-semilattice we mean a structure S of signature $τ = {⨆, \cdot}$ such that $(S, ⨆)$ is a σ-semilattice and · is a binary associative monotone operation (thus, $(x \cdot y) \cdot z = x \cdot (y \cdot z)$ and $x ⩽ x^{'} \land y ⩽ y^{'} \to x \cdot y ⩽ x^{'} \cdot y^{'}$ ) satisfying the additional axioms $x ⊔ y ⩽ x \cdot y$ and $(⨆ x_{i}) \cdot y = ⨆ (x_{i} \cdot y)$ . We describe some basic examples of τ-semilattices.

The operator $T$ (as well as $T^{⊔}$ ) on BQO introduced in Section 2.3 induces an operator on $BPO$ which we also denote by $T$ . It is easy to check (for $Q = \bar{k}$ this was shown in [11]) that the σ-semilattice $T^{⊔} (Q)$ with a new bottom element ⊥ (representing the empty forest) is distributive. By Proposition 6, if Q is bpo, any element of this σ-semilattice has a canonical decomposition to σ-join-irreducible elements of (the quotient-poset of) $T^{⊔} (Q)$ . Moreover, the σ-join-irreducible elements are precisely those h-equivalence classes which contain Q-trees (for $Q = \bar{k}$ this again was shown in [11]).

For any $F, G \in T^{⊔} (Q)$ , let $F \cdot G$ be the Q-forest obtained from F by inserting a copy of G above every leaf of F (for finite labeled forests, this is a standard operation in computer science). It is easy to see that this operation is monotone (i.e., $F ⩽_{h} F^{'} \land G ⩽_{h} G^{'} \to F \cdot G ⩽_{h} F^{'} \cdot G^{'}$ ), in particular it is correctly defined on the equivalence classes. One also easily checks that $\begin{matrix} F ⊔ G ⩽_{h} F \cdot G, (F \cdot G) \cdot H \equiv_{h} F \cdot (G \cdot H), and (⨆ F_{i}) \cdot G \equiv_{h} ⨆ (F_{i} \cdot G) . \end{matrix}$ Thus, we obtain the following examples of τ-semilattices.

Proposition 8.
For any bpo Q, the quotient structure $F_{τ} (Q)$ of $(T^{⊔} (Q); ⩽_{h}, ⨆, \cdot)$ is a τ-semilattice the σ-join-irreducible elements of which are precisely the h-equivalence classes $[T]$ , $T \in T (Q)$ . The corresponding σ-semilattice $F_{τ} {(Q)}_{⊥}$ is distributive. Any element of $F_{τ} (Q)$ has a canonical decomposition.

4.2. Q-Presented τ-semilattices

Here we show that the structure $F_{τ} (Q)$ from the previous subsection may be considered as a Q-presented τ-semilattice satisfying the identities $q \cdot q = q$ and $q ⊔ r = r$ for all $q, r \in Q$ , $q ⩽ r$ (in the algebraic-style notation, one could write $F_{τ} (Q) = ⟨ Q ∣ R_{τ} ⟩$ where $R_{τ} = {q ⊔ r = r, q \cdot q = q ∣ q, r \in Q, q ⩽ r}$ ).

Let $BPO$ be the category of bpo’s (with monotone functions as morphisms), $τ BSL$ be the category of τ-semilattices such that ⩽ is a bpo (whose morphisms are the functions preserving ⨆, ·), and $U : τ BSL \to BPO$ be the forgetful functor. For any bpo Q and any $q \in Q$ , let $η_{Q} (q)$ be the singleton tree labeled by q (more precisely, the h-equivalence class of this tree). Clearly, $η_{Q} : Q \to {UF}_{τ} (Q)$ is an embedding of posets.

Theorem 9.
The triple $(F_{τ}, U, η)$ is an adjunction between $BPO$ and $τ BSL$ .
Proof.
First we show that $(F_{τ} (Q), η_{Q})$ is an initial object of the category Q- $τ BSL$ for any bpo Q. Clearly, $(F_{τ} (Q), η_{Q})$ is an object of Q- $τ BSL$ , so it remains to show that for any object $(H, h)$ of Q- $τ BSL$ there is a unique $τ BSL$ -morphism $g : F_{τ} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . The uniqueness follows from the equality $h = U (g) \circ η_{Q}$ (hence g is uniquely defined on the image $η_{Q} (Q)$ ) and the easy fact that $F_{τ} (Q)$ is generated (using the operations ⨆, ·) from $η_{Q} (Q)$ (hence g is uniquely defined also on the rest of $F_{τ} (Q)$ ).

It remains to construct a $τ BSL$ -morphism $g : F_{τ} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . First we associate with any well founded Q-tree $(T, t)$ a function $g_{T} : T \to H$ by induction on the rank of elements in $(T; ⊒)$ as follows: if τ is a leaf of T (i.e., a minimal element of $(T; ⊒)$ ) then $g_{T} (τ) = ht (τ)$ , otherwise $g_{T} (τ) = ht (τ) \cdot ⨆ {g_{T} (τ n) ∣ τ n \in T}$ . From monotonicity of ·, properties of supremum, and the axiom $x ⊔ y ⩽ x \cdot y$ we see that $g_{T} (τ) ⩽ g_{T} (σ)$ whenever $σ ⊑ τ \in T$ .

Next we check by induction on the ranks of well founded Q-trees $(T, t)$ and $(V, v)$ that $T ⩽_{h} V$ implies $g_{T} (ε) ⩽ g_{V} (ε)$ . Let $φ : T \to V$ be a monotone function such that $t (τ) ⩽ v φ (τ)$ for each $τ \in T$ . If $ε ⊏ φ (ε)$ then by induction we have $g_{T} (ε) ⩽ g_{V} (φ (ε)) ⩽ g_{V} (ε)$ . Otherwise, consider the Q-tree $W = φ^{- 1} (ε) \subseteq T$ . By the definition of h-qo, $t (σ) ⩽ v (ε)$ for all $σ \in W$ . By the definition of $g_{W}$ and monotonicity of ·, $g_{W} (ε) ⩽ hv (ε) \cdot hv (ε) = hv (ε)$ . For any $τ \in T ∖ W$ we by induction have $g_{T} (τ) ⩽ ⨆ {g_{V} (n) ∣ n \in V \cap ω}$ . By monotonicity of ·, we obtain $g_{T} (ε) ⩽ g_{V} (ε)$ .

This implies that the function $T \mapsto g_{T} (ε)$ is correctly defined on the h-equivalence classes, and we can correctly define a monotone function g from the σ-join-irreducible elements of $F_{τ} (Q)$ to H by $g ([T]) = g_{T} (ε)$ . We can extend this function to the σ-join-reducible elements of $F_{τ} (Q)$ as follows: for any such $x \in F_{τ} (Q)$ we set $g (x) = g (x_{0}) ⊔ g (x_{1}) ⊔ \dots$ where $x = x_{0} ⊔ x_{1} ⊔ \dots$ is a canonical decomposition of x. Since the canonical decomposition is unique up to the domination quasiorder and g is monotone on the σ-join-irreducible elements, g is correctly defined on the whole set $F_{τ} (Q)$ and preserves countable supremums. Obviously, we also have $h = U (g) \circ η_{Q}$ .

It remains to show that $g (x \cdot y) = g (x) \cdot g (y)$ for all $x, y \in F_{τ} (Q)$ . Let first $x = [T]$ be σ-join-irreducible and let $y = [G]$ . If T is singleton then $g (x \cdot y) = ht (ε) \cdot g (G) = g (x) \cdot g (y)$ . Otherwise, $T \cdot G \equiv_{h} ({ε} \cdot K) \cdot G \equiv_{h} {ε} \cdot (K \cdot G)$ where $K = T ∖ {ε}$ , hence (again using induction on the rank of T) $\begin{matrix} g (x \cdot y) = ht (ε) \cdot g (K \cdot G) = ht (ε) \cdot (g (K) \cdot g (G)) = (ht (ε) \cdot g (K)) \cdot g (G) = g (x) \cdot g (y) . \end{matrix}$ If x is σ-join-reducible then for a canonical decomposition $x = x_{0} ⊔ x_{1} ⊔ \dots$ we have $\begin{array}{rcl} g (x \cdot y) & = & g ((x_{0} ⊔ x_{1} ⊔ \dots) \cdot y) = g (x_{0} \cdot y ⊔ x_{1} \cdot y ⊔ \dots) = g (x_{0} \cdot y) ⊔ g (x_{1} \cdot y) ⊔ \dots \\ = & g (x_{0}) \cdot g (y) ⊔ g (x_{1}) \cdot g (y) ⊔ \dots = (g (x_{0}) ⊔ g (x_{1}) ⊔ \dots) \cdot g (y) = g (x) \cdot g (y) . \end{array}$

Next we show that the map $F_{τ}$ extends to a functor from $BPO$ to $τ BSL$ , and η is a natural transformation of $1_{BPO}$ to $U \circ F_{τ}$ . We have to define $F_{τ} (f)$ for each $BPO$ -morphism $f : P \to Q$ . Clearly, $(F_{τ} (Q), η_{Q} \circ f)$ is an object of P- $τ BSL$ . Since $(F_{τ} (P), η_{P})$ is an initial object of P- $τ BSL$ , there is a unique $τ BSL$ -morphism $g : F_{τ} (P) \to F_{τ} (Q)$ such that $η_{Q} \circ f = U (g) \circ η_{P}$ . Thus, we can take $F_{τ} (f) = g$ and $F_{τ}$ is a functor.

It is easy to see that $F_{τ} (f)$ is induced by the function $(G, g) \mapsto (G, f \circ g)$ from $T^{⊔} (P)$ to $T^{⊔} (Q)$ . This implies that η is a natural transformation from $1_{BPO}$ to $U \circ F_{τ}$ . By remarks in Section 2.4, $(F_{τ}, U, η)$ is an adjunction. □

4.3. Relation to Q-Wadge degrees

We are ready to characterise a new initial segment of Q-Wadge degrees as a free structure. The characterisation immediately follows from Theorem 9 and the forest characterisation of the initial segment.

Corollary 10.
For any countable bpo Q, the quotient poset of $(Δ_{2}^{0} (Q^{N}); ⩽_{W})$ is isomorphic to the ⩽-reduct ${UF}_{τ} (Q)$ of the initial object of the category Q- $τ BSL$ .
Proof.
By Theorem 9, it suffices to show that $(Δ_{2}^{0} (Q^{N}); ⩽_{W}) ≃ (T^{⊔} (Q); ⩽_{h})$ , and this was shown in [5,12]. □

5. $τ_{s}$ -Semilattices

In this section we expand the signature τ to the signature $τ_{s} = τ ⊔ {I, s}$ (where I is a unary predicate symbol and s is a unary function symbol) and extend the axioms of τ-semilattices to some axioms of signature $τ_{s}$ , the models of which we call $τ_{s}$ -semilattices.

5.1. Definition and examples

By $τ_{s}$ -semilattice we mean a structure S of signature $τ_{s}$ such that $(S, ⨆, \cdot)$ is a τ-semilattice, I is a unary relation and s is a unary function on the interpretation $I \subseteq S$ of I in S satisfying the following axioms: $\begin{array}{l} \forall x \in I (s (x) \in I \land x ⩽ s (x) = s (x) \cdot s (x)), \\ \forall x, y (I (x) \to I (x \cdot y)), \forall x, y \in I (x ⩽ y \leftrightarrow s (x) ⩽ s (y)) . \end{array}$ We describe some basic examples of $τ_{s}$ -semilattices.

The iterated operators $T^{α}$ on BQO introduced in Section 2.3 induce corresponding operators on $BPO$ which we also denote by $T^{α}$ , $α ⩽ ω_{1}$ . Let $T^{1 + α, ⊔} (Q)$ be the set of non-empty forests obtained from the trees in $T^{1 + α} (Q)$ by deleting the root. These sets are closed under the operation of countable disjoint union $⨆_{n} F_{n} = F_{0} ⊔ F_{1} ⊔ \dots$ of labeled forests.

By induction on α we can define a binary operation · on $T^{1 + α, ⊔} (Q)$ in the same way as in Section 4.1. Similar to that subsection one shows (using the induction on α) that the quotient structure of $(T^{1 + α, ⊔} (Q); ⨆, \cdot)$ is a τ-semilattice.

The set $J_{1 + α} (Q)$ of σ-join-irreducible elements of the corresponding σ-semilattice coincides with the set of h-equivalence classes of trees in $T^{1 + α} (Q)$ , and the σ-semilattices become distributive if we adjoin a new bottom element to them.

Finally, we interpret the predicate symbol I as the set $J (Q) = ⋃_{α} J_{α} (Q)$ of σ-join-irreducible elements in the quotient structure of $(T^{ω_{1}, ⊔} (Q); ⨆, \cdot)$ . In this way we obtain the following.

Proposition 11.
For any bpo Q, the quotient structure $F_{τ_{s}} (Q)$ of $(T^{ω_{1}, ⊔} (Q); ⨆, \cdot, I, s)$ is a $τ_{s}$ -semilattice the σ-join-irreducible elements of which are precisely the h-equivalence classes of trees $T \in T^{ω_{1}} (Q)$ . The corresponding σ-semilattice $F_{τ_{s}} {(Q)}_{⊥}$ is distributive. Any element of $F_{τ_{s}} (Q)$ has a canonical decomposition.

The structure $F_{τ_{s}} (Q)$ has some other interesting properties, e.g. the following characterisation of fixed points of the operation s on $J (Q)$ . Proposition 12.
For any bpo Q we have: ${x \in J (Q) ∣ s (x) = x} = {η_{Q} (q) ∣ q \in Q}$ .
Proof.
The inclusion from right to left is obvious. For the converse inclusion, it suffices to check by induction on α that if $T \in T^{α} (Q)$ and $s (T) \equiv_{h} T$ then $T \equiv_{h} q$ for some $q \in Q$ . For $α = 0$ this is obvious, and for a limit α this is immediate by induction. So let $α = β + 1$ . Since T is equivalent to a singleton tree, $T \equiv_{h} s (V)$ for some $V \in T^{β} (Q)$ . Then $s (T) \equiv_{h} s (V)$ , hence $T \equiv_{h} V$ and the assertion follows by induction on α. □

5.2. Q-Presented $τ_{s}$ -semilattices

Here we show that the structure $F_{τ_{s}} (Q)$ from the previous subsection may be considered as a Q-presented $τ_{s}$ -semilattice satisfying the identities $q = s (q)$ , $I (q)$ , and $q ⊔ r = r$ for all $q, r \in Q$ , $q ⩽ r$ (in the algebraic-style notation, one could write $F_{τ_{s}} (Q) = ⟨ Q ∣ R_{τ_{s}} ⟩$ where $R_{τ_{s}} = {q ⊔ r = r, q = s (q), I (q) ∣ q, r \in Q, q ⩽ r}$ ).

Let $BPO$ be the category of bpo’s (with monotone functions as morphisms), $τ_{s} BSL$ be the category of $τ_{s}$ -semilattices such that ⩽ is a bpo (whose morphisms are the functions preserving ⨆, ·, I, s), and $U : τ_{s} BSL \to BPO$ be the forgetful functor. For any bpo Q and any $q \in Q$ , let $η_{Q} (q)$ be the singleton tree labeled by q (more precisely, the h-equivalence class of this tree). Clearly, $η_{Q} : Q \to {UF}_{τ_{s}} (Q)$ is an embedding of posets.

Theorem 13.
The triple $(F_{τ_{s}}, U, η)$ is an adjunction between $BPO$ and $τ_{s} BSL$ .
Proof.
First we show that $(F_{τ} (Q), η_{Q})$ is an initial object of the category Q- $τ BSL$ for any bpo Q. Clearly, $(F_{τ_{s}} (Q), η_{Q})$ is an object of Q- $τ_{s} BSL$ , so it remains to show that for any object $(H, h)$ of Q- $τ_{s} BSL$ there is a unique $τ_{s} BSL$ -morphism $g : F_{τ_{s}} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . The uniqueness follows from the equality $h = U (g) \circ η_{Q}$ (hence g is uniquely defined on the image $η_{Q} (Q)$ ) and the easy fact that $F_{τ_{s}} (Q)$ is generated (using the operations ⨆, ·, s) from $η_{Q} (Q)$ (hence g is uniquely defined also on the rest of $F_{τ_{s}} (Q)$ ).

It remains to construct a $τ_{s} BSL$ -morphism $g : F_{τ_{s}} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . First we define by induction on $α < ω_{1}$ functions $g^{α} : T^{α} (Q) \to H$ such that $g^{0} = h$ , $g^{α}$ for $α > 0$ preserves ⨆, · and extends $g^{β}$ ( $β < α$ ) modulo h-equivalence.

For $α = 1$ we have $T^{1} (Q) = T (Q)$ , hence we can define $g^{1}$ as the function $T \mapsto g_{T} (ε)$ from the proof of Theorem 9. For limit ordinals α it suffices to take union. For $α = β + 1 > 1$ we set $g^{α} (T) = g_{T} (ε)$ where $g_{T} : T \to H$ is the following modification of the corresponding function from the proof of Theorem 9: if τ is the leaf of T then $g_{T} (τ) = {sg}^{β} t (τ)$ , otherwise $g_{T} (τ) = {sg}^{β} t (τ) \cdot ⨆ {g_{T} (τ n) ∣ τ n \in T}$ (note that $t (τ) \in T^{β} (Q)$ ).

By induction we see that $g^{α}$ has the desired properties. For any $x = [T] \in F_{τ_{s}} (Q)$ , $T \in T^{ω_{1}} (Q)$ , we set $g (x) = g^{β} (T)$ where β is the least ordinal below $ω_{1}$ with $T \in T^{β}$ . Then g is correctly defined and preserves ⨆, ·. It also preserves s by the definitions of $g_{T}$ in the previous paragraph.

It remains to check that g also preserves the predicate I. By the interpretation of I in $F_{τ_{s}} (Q)$ , we have to show that $g ([T]) \in I_{H}$ for all $α < ω_{1}$ and $T \in T^{α} (Q)$ where $I_{H}$ is the interpretation of I in H. For $α = 0$ this reduces to $h (q) \in I_{H}$ for each $q \in Q$ . This holds because the identity $I (q)$ is true in H. Let now $α = β + 1$ , then $g (t (τ)) \in I_{H}$ for each $τ \in T$ by induction. By the axioms of $τ_{s}$ -semilattices related to I, the set $I_{H}$ is closed under the operations s and $(x_{0}, x_{1}, \dots) \mapsto x_{0} \cdot (x_{1} ⊔ \dots)$ . By the definition of $g^{α}$ above, $g (T) \in I_{H}$ .

As in Section 4.2 we show that the map $F_{τ_{s}}$ extends to a functor from $BPO$ to $τ_{s} BSL$ , and η is a natural transformation of $1_{BPO}$ to $U \circ F_{τ_{s}}$ . □

5.3. Relation to Q-Wadge degrees

We are ready to characterise a new initial segment of Q-Wadge degrees as a free structure. The characterisation immediately follows from Theorem 13 and the forest characterisation of the initial segment.

Corollary 14.
For any countable bpo Q, the quotient poset of $(Δ_{ω}^{0} (Q^{N}); ⩽_{W})$ is isomorphic to the ⩽-reduct ${UF}_{τ_{s}} (Q)$ of the initial object of the category Q- $τ_{s} BSL$ .
Proof.
By Theorem 13, it suffices to show that $(Δ_{ω}^{0} (Q^{N}); ⩽_{W}) ≃ (T^{ω_{1}, ⊔} (Q); ⩽_{h})$ , and this was shown in [5] (see also [14,16] for some particular cases with a bit different proof). □

6. $τ_{γ}$ -Semilattices

In this section we expand the signature $τ_{s}$ (more precisely, its syntactic version $τ_{1} = τ_{s_{0}}$ ) to the signature $τ_{γ} = τ \cup {I, s_{α} ∣ α < γ}$ (where γ is a non-zero ordinal and $s_{α}$ are distinct unary function symbols) and extend the axioms of τ-semilattices to some axioms of signature $τ_{γ}$ the models of which we call $τ_{γ}$ -semilattices.

6.1. Definition and examples

For any positive ordinal $γ > 0$ , a $τ_{γ}$ -semilattice is a structure S of signature $τ_{γ}$ such that S is a $τ_{s_{α}}$ -semilattice for each $α < γ$ , and $s_{α} (s_{β} (x)) = s_{β} (x)$ for all $α < β < γ$ , $x \in I$ . The last axiom is the only one relating the operations $s_{α}$ for different α.

From the axioms it follows that for all $α < β < γ$ and $x, y \in I$ we have: $s_{α} (x) ⩽ s_{β} (y)$ iff $x ⩽ s_{β} (y)$ . Indeed, the implication from left to right follows from $x ⩽ s_{α} (x)$ and the transitivity of ⩽. Conversely, let $x ⩽ s_{β} (y)$ . By monotonicity of $s_{α}$ , $s_{α} (x) ⩽ s_{α} (s_{β} (y))$ . Since $α < β$ , $s_{α} (s_{β} (y)) = s_{β} (y)$ .

We describe some basic examples of $τ_{γ}$ -semilattices which are based on the iterated operators $T_{ω^{γ}}$ on BQO introduced in Section 2.3. These operators induce corresponding operators on $BPO$ which we also denote by $T_{ω^{γ}}$ . As in Section 5.1, let $T_{ω^{γ}}^{⊔} (Q)$ be the set of non-empty forests obtained from the trees in $T_{ω^{γ}} (Q)$ by deleting the root. This set is closed under the operation of countable disjoint union $⨆_{n} F_{n} = F_{0} ⊔ F_{1} ⊔ \dots$ of labeled forests. We can also define a binary operation · on $T_{ω^{γ}}^{⊔} (Q)$ in the same way as in Section 4.1. Similar to that subsection one shows that the quotient structure of $(T_{ω^{γ}}^{⊔} (Q); ⨆, \cdot)$ is a τ-semilattice.

The set $J_{γ} (Q)$ of σ-join-irreducible elements of the corresponding σ-semilattice $(T_{ω^{γ}}^{⊔} (Q); ⨆)$ coincides with the set of h-equivalence classes of trees in $T_{ω^{γ}} (Q)$ , and the σ-semilattice becomes distributive if we adjoin a new bottom element to it. Since the operations $s_{α}$ are monotone w.r.t. the h-qo, they correctly denote operations on $J_{γ} (Q)$ which we again denote by $s_{α}$ .

Finally, we interpret the predicate symbol I in the quotient structure of $(T_{ω^{γ}}^{⊔} (Q); ⨆, \cdot)$ as the set $J_{γ} (Q)$ of σ-join-irreducible elements. In this way we obtain the following.

Proposition 15.
For any bpo Q, the quotient structure $F_{τ_{γ}} (Q)$ of $(T_{ω^{γ}}^{⊔} (Q); ⩽_{h}, ⨆, \cdot, I, s_{α})$ is a $τ_{γ}$ -semilattice the σ-join-irreducible elements of which are precisely the h-equivalence classes $[T]$ , $T \in T_{ω^{γ}} (Q)$ . The corresponding σ-semilattice $F_{τ_{γ}} {(Q)}_{⊥}$ is distributive. Any element of $F_{τ_{γ}} (Q)$ has a canonical decomposition.

The structure $F_{τ_{γ}} (Q)$ has some other interesting properties, e.g. the following characterisation of fixed points of the operation $s_{α}$ on $J_{γ} (Q)$ which extends Proposition 12. Proposition 16.
For all bpo Q, positive ordinal γ, and $α < γ$ we have: ${x \in J_{γ} (Q) ∣ s_{α} (x) = x} = {η_{Q} (q), s_{α + 1} (y) ∣ q \in Q, y \in J_{γ} (Q)}$ (thus, for $α + 1 = γ$ we have ${x \in J_{γ} (Q) ∣ s_{α} (x) = x} = η_{Q} (Q)$ ).

6.2. Q-Presented $τ_{γ}$ -semilattices

Here we show that the structure $F_{τ_{γ}} (Q)$ from the previous subsection may be considered as a Q-presented $τ_{γ}$ -semilattice satisfying the identities $q = s_{α} (q)$ , $I (q)$ and $q ⊔ r = r$ for all $q, r \in Q$ , $q ⩽ r$ , and $α < γ$ (in the algebraic-style notation, one could write $F_{τ_{γ}} (Q) = ⟨ Q ∣ R_{τ_{γ}} ⟩$ where $R_{τ_{γ}} = {q ⊔ r = r, q = s_{α} (q), I (q) ∣ q, r \in Q, q ⩽ r, α < γ}$ ).

Let $BPO$ be the category of bpo’s (with monotone functions as morphisms), $τ_{γ} BSL$ be the category of $τ_{γ}$ -semilattices such that ⩽ is a bpo (whose morphisms are the functions preserving ⨆, ·, I, $s_{α}$ ), and $U : τ_{γ} BSL \to BPO$ be the forgetful functor. For any bpo Q and any $q \in Q$ , let $η_{Q} (q)$ be the singleton tree labeled by q (more precisely, the h-equivalence class of this tree). Clearly, $η_{Q} : Q \to {UF}_{τ_{γ}} (Q)$ is an embedding of posets.

Theorem 17.
The triple $(F_{τ_{γ}}, U, η)$ is an adjunction between $BPO$ and $τ_{γ} BSL$ .
Proof.
First we show that $(F_{τ_{γ}} (Q), η_{Q})$ is an initial object of the category Q- $τ_{γ} BSL$ for any bpo Q. Clearly, $(F_{τ_{γ}} (Q), η_{Q})$ is an object of Q- $τ_{γ} BSL$ , so it remains to show that for any object $(H, h)$ of Q- $τ_{γ} BSL$ there is a unique $τ_{γ} BSL$ -morphism $g : F_{τ_{γ}} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . The uniqueness follows from the given equality $h = U (g) \circ η_{Q}$ (hence g is uniquely defined on the image $η_{Q} (Q)$ ) and the easy fact that $F_{τ_{γ}} (Q)$ is generated (using the operations ⨆, ·, $s_{α}$ ) from $η_{Q} (Q)$ (hence g is uniquely defined also on the rest of $F_{τ_{γ}} (Q)$ ).

It remains to construct a $τ_{γ} BSL$ -morphism $g : F_{τ_{γ}} (Q) \to H$ with $h = U (g) \circ η_{Q}$ . First we define by induction on γ a monotone function $g_{γ}$ from $(T_{ω^{γ}} (Q); ⩽_{h})$ to $(H; ⩽)$ which preserves $s_{α}$ for $α < γ$ and satisfies $g_{δ} (T) = g_{γ} (T)$ for all $0 < δ < γ$ and $T \in T_{ω^{δ}} (Q)$ .

For $γ = 1$ we have $T^{ω_{1}} (Q) ≃ T_{ω^{1} (Q)}$ , hence we can let $g_{1}$ be the function constructed in the proof of Theorem 13.

Let now $γ = δ + 1 > 1$ . By induction, we already have a function $g_{δ} : T_{ω^{δ}} (Q) \to H$ . We define operators $V^{α}$ on $BQO$ by induction on α as follows: $\begin{matrix} V^{0} (Q) = T_{ω^{δ}} (Q), V^{α + 1} (Q) = T_{ω^{δ}} (s_{δ} (V^{α} (Q))), and V^{λ} (Q) = ⋃_{α < λ} V^{α} (Q) \end{matrix}$ for a limit ordinal λ. Clearly, the sequence ${V^{α} (Q)}$ is ascending and any member of the sequence is contained in $T_{ω_{γ}} (Q)$ . Since $V^{ω_{1}} (Q)$ is closed under all $s_{β}$ , $β < γ$ , we have $V^{ω_{1}} (Q) = T_{ω^{γ}} (Q)$ and this set is a fixed point of the described process.

Repeating the proof of Theorem 13 (with s replaced by $s_{δ}$ in the case of successor ordinal $α + 1$ ) we define by induction on $α < ω_{1}$ functions $f_{α} : V^{α} (Q) \to H$ with the properties similar to those of $g_{δ}$ . Defining $g_{γ}$ as (essentially) the union of functions $f_{α}$ , we obtain the desired function $g_{γ}$ .

A similar construction works for a limit ordinal γ. By induction, for each $δ < γ$ we have functions $g_{δ} : T_{ω^{δ}} (Q) \to H$ (for all $0 < δ < γ$ ) with the specified properties. Define an operator $G$ on $BQO$ by $G (Q) = ⋃ {T_{ω^{δ}} (Q) ∣ 0 < δ < γ}$ , then we have a corresponding function $f : G (Q) \to H$ . Now define operators $G^{α}$ on $BQO$ by induction on α as follows: $\begin{matrix} G^{0} (Q) = G (Q), G^{α + 1} (Q) = G (⋃ {s_{δ} (G_{α} (Q)) ∣ δ < γ}), and G^{λ} (Q) = ⋃_{α < λ} G^{α} (Q) \end{matrix}$ for a limit ordinal λ. Mutatis mutandis, the above argument works for the sequence ${G^{α} (Q)}$ in place of ${V^{α} (Q)}$ .

Similar to the proof of Theorem 13 we can now define a function $g : F_{τ_{γ}} (Q) \to H$ with $h = U (g) \circ η_{Q}$ that respects the functions ⨆, ·, $s_{α}$ .

It remains to check that g also preserves the predicate I. By the interpretation of I in $F_{τ_{γ}} (Q)$ , we have to show that $I_{H} (g ([T]))$ for all $T \in T_{ω^{γ}}$ where $I_{H}$ is the interpretation of I in H. This holds because the identity $I (q)$ is true in H and, by the axioms of $τ_{γ}$ -semilattices, the set $I_{H}$ is closed under the operations $s_{α}$ and $(x_{0}, x_{1}, \dots) \mapsto x_{0} \cdot (x_{1} ⊔ \dots)$ . By the definition of $g_{α}$ above, $g (T) \in I_{H}$ .

As in Section 5.2 we show that the map $F_{τ_{γ}}$ extends to a functor from $BPO$ to $τ_{γ} BSL$ , and η is a natural transformation of $1_{BPO}$ to $U \circ F_{τ_{γ}}$ . □

6.3. Relation to Wadge degrees

We are ready to characterise some new initial segments of Q-Wadge degrees as a free structure. The characterisations immediately follow from Theorem 17 and the forest characterisations of the initial segments.

Corollary 18.
Let Q be a countable bpo and γ be a non-zero countable ordinal. Then the quotient poset of $(Δ_{ω^{γ}}^{0} (Q^{N}); ⩽_{W})$ is isomorphic to the ⩽-reduct ${UF}_{τ_{γ}} (Q)$ of the initial object of the category Q- $τ_{γ} BSL$ , and the quotient poset of $(Δ_{ω_{1}}^{0} (Q^{N}); ⩽_{W})$ is isomorphic to the ⩽-reduct ${UF}_{τ_{ω_{1}}} (Q)$ of the initial object of the category Q- $τ_{ω_{1}} BSL$ .
Proof.
By Theorem 17, it suffices to show that $(Δ_{ω^{γ}}^{0} (Q^{N}); ⩽_{W}) ≃ (T_{ω^{γ}}^{⊔} (Q); ⩽)$ , and this was shown in [5]. The same for the second assertion. □

7. The finitary case

Here we briefly discuss finitary versions of some results described above. The “finitary” versions are obtained from the “infinitary” ones considered above by restricting countable supremums to binary ones, and by taking finite trees and forests instead of countable ones.

While the infinitary versions are closely related to the Q-Wadge degrees, the finitary ones are closely related to the so called fine hierarchy (which is arguably the finitary abstract version of the Wadge hierarchy, see e.g. [13] and references therein) and its variants. In the context of Wadge degrees, the fine hierarchy is a very small but useful fragment of the Wadge degrees.

Since the finitary case is effective, one could also put some effectivity restrictions on the involved bpo’s (a quite reasonable option would be to restrict oneself to the finite posets Q). Most of the results in fact hold if we extend bpo’s to wpo’s, so we will formulate them in the full generality. The proofs of the finitary versions are easier than those of infinitary ones because we can now use some known facts about free and finitely presented structures.

We give a couple of examples of the finitary versions. The finitary version of Theorem 2 looks as follows. Let $SL$ be the category of semilattices and $U : SL \to PO$ be the forgetful functor.

Proposition 19.
The functor U has a left adjoint $F : PO \to SL$ .
Proof hint.
Consider the variant of $(Q^{}; ⩽^{})$ restricted to finite subsets of Q. □

Similarly to the infinitary case, the semilattice $F (Q)$ with an additional bottom element is distributive (in the usual sense). A restricted version of the last result is obtained if we restrict $PO$ to its full subcategory $WPO$ of wpo’s and $SL$ to its full subcategory $WSL$ of semilattices which are wpo’s under the induced partial order.

Finitary versions of some other results in Section 3 also make sense. Now we speak about the usual join-irreducible elements of semilattices instead of σ-join irreducuble ones. A decomposition $x = x_{0} ⊔ \dots ⊔ x_{n}$ to join-irreducible elements is now finite and the components $x_{i}$ are required to be pairwise incomparable. Such a decomposition is canonical if it is unique up to a permutation of the components. The finitary version of e.g. Proposition 6 looks as follows.
Proposition 20.
Let $(S; ⩽, ⊔)$ be a well founded semilattice. Then any non-zero element $x \in S$ has a decomposition, and if S is distributive then x has a canonical decomposition.

The finitary version of Theorem 9 looks as follows. By $f τ$ -semilattice we mean a semilattice with additional binary operation · that satisfies the finitary versions of the axioms of τ-semilattices. Let $f τ WSL$ be the category of $f τ$ -semilattices which are wpo’s under the induced partial order (with the usual homomorphisms as morphisms), and let $U : f τ WSL \to WPO$ be the forgetful functor.
Proposition 21.
For any wpo Q, the category Q- $f τ WSL$ has an initial object (e.g., we can take the Q-presented structure $⟨ Q ∣ R_{τ} ⟩$ which exists because the $f τ$ -semilattices are axiomatised by quasiidentities). The functor U has a left adjoint.

An initial object may also be constructed as in the proof of Theorem 9 where finite trees and forests are taken instead of the countable ones. Such objects were used in [10] (for $Q = \bar{k}$ ) where the difference hierarchy of k-partitions was developed.

The finitary version of Theorem 13 looks as follows. By $f τ_{s}$ -semilattice we mean a structure $(S; ⊔, \cdot, I, s)$ such that $(S, ⊔, \cdot)$ is an $f τ$ -semilattice, I is a unary relation and s is a unary function satisfying the remaining axioms of $τ_{s}$ -semilattices. Let $f τ_{s} WSL$ be the category of $f τ_{s}$ -semilattices which are wpo’s under the induced partial order (with the usual homomorphisms as morphisms), and let $U : f τ_{s} WSL \to WPO$ be the forgetful functor.
Proposition 22.
For any wpo Q, the category Q- $f τ_{s} WSL$ has an initial object (e.g., we can take the Q-presented structure $⟨ Q ∣ R_{τ_{s}} ⟩$ which exists because $f τ_{s}$ -semilattices are axiomatised by quasiidentities). The functor U has a left adjoint.

An initial object may also be constructed as in the proof of Theorem 13 where finite trees and forests are taken instead of the countable ones (in the finitary case, the sequence ${T^{α} (Q})$ from Section 5 stabilises at level ω). Such objects were used in [14] (for $Q = \bar{k}$ ) where the fine hierarchy of k-partitions was developed. Remark 23.
The standard algebraic constructions of the Q-presented structures consist in taking suitable quotients of the syntactic $f τ$ - or $f τ_{s}$ -structures formed by the terms without variables in the signature expanded by the elements of Q as new constants. Though this construction might at first glance look different from our constructions using labeled trees and forests, both constructions are in fact equivalent because the involved labeled trees and forests are a possible way (well known in computer science) to denote the corresponding terms.

8. Conclusion

In this paper we obtained axiomatic characterisations of several initial segments of the Borel Q-Wadge degrees which were previously characterised using iterated Q-labeled forests. A major open question in this field is to characterise natural initial segments of the Q-Wadge degrees beyond the Borel Q-partitions (including the structure of all Q-Wadge degrees).

For 2-partitions such characterisations are well known [19] and require suitable set-theoretic axioms alternative to those of ZFC. Section 6 suggests that the $τ_{γ}$ -semilattices for $γ > ω_{1}$ could provide reasonable characterisations of natural initial segments of Q-Wadge degrees beyond the Borel Q-partitions.

Footnotes

Acknowledgements

I am grateful to two anonymous referees for the careful reading and useful remarks which helped to improve the text.

The author was supported by the Regional Mathematical Center of Kazan Federal University.

References

Awodey, Category Theory, Clarendon, Oxford, 2006.

B.A.

Davey and

H.A.

Priestley, Introduction to Lattices and Order, Cambridge, 1994.

Hertling, Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, in: Informatik-Berichte, Vol. 152, Fernuniversität Hagen, 1993.

A.S.

Kechris, Classical Descriptive Set Theory, Springer, New York, 1995.

Kihara and

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

Kihara and

Selivanov, Wadge-like degrees of Borel bqo-valued functions, 2019, arXiv:1909.10835v1.

Kuratowski and

Mostowski, Set Theory, North Holland, 1967.

C.St.J.A.

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

Selivanov, Q-Wadge hierarchy in quasi-Polish spaces, 2019, arXiv:1911.02758v1.

10.

V.L.

Selivanov, Boolean hierarchies of partitions over reducible base, Algebra and Logic43(1) (2004), 44–61. doi:10.1023/B:ALLO.0000015130.31054.b3.

11.

V.L.

Selivanov, The quotient algebra of labeled forests modulo h-equivalence, Algebra and Logic46(2) (2007), 120–133. doi:10.1007/s10469-007-0011-5.

12.

V.L.

Selivanov, Hierarchies of

Δ_{2}^{0}

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

13.

V.L.

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

14.

V.L.

Selivanov, Towards a descriptive theory of cb0-spaces, Mathematical Structures in Computer Science.28(8) (2017), 1553–1580. doi:10.1017/S0960129516000177.

15.

V.L.

Selivanov, Well quasiorders and hierarchy theory, in: Well Quasiorders in Computation, Logic, Language and Reasoning,

P.M.

Schuster,

Seisenberger and

Weiermann, eds, Series Trends in Logic, Springer, 2020, pp. 271–320, arXiv:1809.02941. doi:10.1007/978-3-030-30229-0_10.

16.

V.L.

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

Kari,

Manea and

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

17.

S.G.

Simpson , Bqo-theory and Fraïssé conjecture, in: Recursive Aspects of Descriptive Set Theory,

Mansfield ,

Weitkamp , eds, Oxford University Press, New York, 1985, Chapter 9.

18.

van Engelen,

Miller and

Steel, Rigid Borel sets and better quasiorder theory, Contemporary mathematics65 (1987), 199–222. doi:10.1090/conm/065/891249.

19.

Van Wesep, Wadge degrees and descriptive set theory, Lecture Notes in Mathematics689 (1976), 151–170.

20.

W.W.

Wadge, Reducibility and determinateness in the Baire space, PhD thesis, University of California, Berkely, 1984.