2.1 Orders and maps

We start by looking at qos in general and various kinds of maps between them.

We usually identify both the qo and its underlying set by the same symbol, for example Q in the above definition, with the meaning clear from context.

Note that, unlike a partial-order (po) the relation $\le $ may not be anti-symmetric: $x \le y \land y \le x \land x \neq y$ is possible. The distinction is not very important, since taking the quotient of a qo under the equivalence relation $x \equiv y$ iff $(x \le y) \land (y \le x)$ transforms it into a po.

Sometimes it is useful to look at a subset $P \subseteq Q$ of a qo $(Q,\le )$ , in which case the qo $(P, \le \upharpoonright _{P \times P})$ is called an induced suborder of Q.

We often compare qos by defining maps between their underlying sets such that the orderings of the domain and the codomain are related in some sense. In the following, let us fix two arbitrary qos $(P,\le _P)$ and $(Q,\le _Q)$ .

When a map is an order-embedding, the domain and range of the map are essentially the same qos, modulo renaming of elements and equivalences. For the following definition, assume P and Q to be pos, that is, satisfying anti-symmetry.

The condition of surjectivity has to be modified slightly to make it work for qos. Recall that, for $x,y \in Q$ , $x \equiv _Q y$ iff $(x \le _Q y) \land (y \le _Q x)$ . (Here we use subscripts to differentiate $\equiv _Q$ and $\equiv _P$ .)

The two definitions are almost the same: if f and g are modified to be maps between $P/{\equiv _P}$ and $Q/{\equiv _Q}$ (i.e., their respective quotients under the equivalence relations $\equiv _P$ and $\equiv _Q$ ), then they are both order-isomorphisms in the sense of Definition 2.3, and functional inverses of each other.

The notion of being order-isomorphic is transitive via function composition of the associated maps.

2.2 Well-quasi-orders

The central notion of our study is the concept of a well-quasi-order (wqo).

The notion of a well-partial-order (wpo) is analogous. If the po in question is a total order, we call it a well-order. The canonical examples of well-orders are, of course, the ordinals.

Wqos have the so-called finite basis property; that is, any non-empty subset S of a wqo Q has a finite non-zero number of minimal elements. This easily follows from the definition above, and is in fact equivalent to it.

The property of being a wqo is quite well-behaved when it comes to order-reflecting maps. Fix arbitrary qos $(P, \le _P)$ and $(Q, \le _Q)$ .

Thus, order-reflecting maps are very useful tools in the study of wqos, in particular, by reducing the question of one qo being a wqo to known, often simpler, examples.

2.3 Ordinal invariants

There is a third characterization of wqos in terms of their linearizations, which we shall use heavily in this article.

Note that $(Q, \le ^+) \hookrightarrow (Q, \le )$ with the identity map, thus if Q is a wqo then so are all of its linearizations.

Since linearizations of qos may not satisfy anti-symmetry, we implicitly take the quotient under equivalence when describing them as well-orders.

All well-orders have an associated order type, defined to be the unique ordinal that they are order-isomorphic to. A natural object to study in the context of wqos, thus, is the following.

The study of maximal order types of wqos was initiated by de Jongh and Parikh [Reference de Jongh and Parikh9], where they also show that the maximal order type is in fact a maximum (i.e., it is attained as the order type of some linearization). A comprehensive survey is contained in the habilitation thesis of Schmidt [Reference Schmidt, Schuster, Seisenberger and Weiermann20]; it also contains the erroneous calculation of $o(s^F_\alpha (Q))$ , which this article tries to partially resolve.

Another equivalent characterization is the following.

This helps us state one of the most useful tools in the calculation of maximal order types.

As before, this lets us give upper bounds for the maximal order type of a wqo under consideration, with the help of a potentially larger but better understood wqo.

The maximal order type of a wqo can also be studied inductively by certain downwards-closed sets generated by its elements.

The following theorem is one of the main results in [Reference de Jongh and Parikh9].

There are two other ordinal measures of a given wqo that are also studied: the height and the width. Together with the maximal order type, these three are referred to as the ordinal invariants of the wqo. Their definitions are also given inductively by narrowing the definition of the downward-closed sets.

Clearly, for a wqo Q and some $x \in Q$ , the sets $L_<(x)$ and $L_{\mathrel {\bot }}(x)$ are subsets of $L(x)$ , and thus the height and width are at most the maximal order type. The maximal order type, though, is bounded above by their natural product, giving the following elegant set of inequalities.

This was originally shown in [Reference Kříž, Thomas, Nešetřil and Rödl10, Theorem 4.13]; a self-contained proof can also be found in [Reference Džamonja, Schmitz, Schnoebelen, Schuster, Seisenberger and Weiermann4, Theorem 3.8].

It is not difficult to see that, if two wqos P and Q are equivalent, then all three of their ordinal invariants are equal.

As a rule of thumb, for most classes of wqos that are studied, the maximal order type ends up being a multiplicatively indecomposable ordinal with the height being relatively small, and thus—by the inequalities above—the width equal to the maximal order type.

2.4 Examples

The simplest examples of wqos are finite qos, since any infinite sequence of elements will necessarily contain repetitions. Let us fix notations for finite chains and antichains.

Ordinals, and well-orders in general, are trivially wqos.

In order to define more complicated qos, we can construct them from multiple simpler qos. There are many constructions that are commonly used, but the disjoint union and Cartesian product are the most relevant.

Let us fix arbitrary qos $(P,\le _P)$ and $(Q,\le _Q)$ .

Both constructions preserve the property of being a wqo: if P and Q are wqos then so are $P \sqcup Q$ and $P \times Q$ . Their maximal order types can be described using the maximal order types of P and Q [Reference de Jongh and Parikh9].

Recall that the natural sum and natural product of ordinals (also referred to as the Hessenberg sum and Hessenberg product) are both commutative, unlike regular ordinal sum and product. A precise definition can be found in [Reference de Jongh and Parikh9].

3.1 Finite leaf-labelled trees

Figure 1

Examples of finite leaf-labelled trees.

Figure 1 Long description

The diagram is divided into two panels labeled A and B.

Panel A, titled The two types of vertices in T sub f (Q), contains two sub-diagrams.

- On the left, under the label Leaf vertices, is a single dot with the letter q below it. Underneath q is the mathematical expression (for all q in Q).

- On the right, under the label Internal vertices, is a root node at the top connected by four downward-sloping lines to four dashed triangles. The triangles are labeled from left to right as tau sub 0, tau sub 1, an ellipsis (three dots), and tau sub k minus 1.

Panel B, titled A tree in T sub f (2) of height 4, shows a specific tree structure.

- It begins at a single root node at the top.

- From the root, two branches descend.

- The left branch descends through three vertical segments and four nodes, ending at a leaf labeled 0.

- The right branch descends to a node that splits again. The left sub-branch of this split ends at a leaf labeled 1. The right sub-branch descends one more level to a leaf labeled 0.

- The total vertical height from the root to the lowest leaf is 4 units.

For the rest of the section, let us fix an arbitrary non-empty qo $(Q,\le _Q)$ . Unless stated otherwise, Q is not necessarily a wqo.

As of now, in the above definition, we have not used the ordering on the set of labels Q. This will come into play in the comparison of two leaf-labelled trees.

We use this notion of tree homomorphisms to define an ordering on the collection of finite leaf-labelled tree.

It is obvious from the definition that $\le _T$ is reflexive. If $h \colon v(\tau _0) \to v(\tau _1)$ and $h' \colon v(\tau _1) \to v(\tau _2)$ are tree homomorphisms from $\tau _0$ to $\tau _1$ and $\tau _1$ to $\tau _2$ , respectively, then it easy to check that $h' \circ h \colon v(\tau _0) \to v(\tau _2)$ is a tree homomorphism from $\tau _0$ to $\tau _2$ . Thus $\le _T$ is transitive as well, and $(\mathsf {T_f}(Q), \le _T)$ is a qo. See Figure 2 for examples.

Figure 2

Examples of tree homomorphisms.

Figure 2 Long description

Panel (A) displays two rooted trees. The left tree has a root branching into two paths: a left leaf labeled 1 and a right path with two nodes ending in leaf 0. Dotted arrows map nodes from the left tree to a single-path tree on the right, which has four nodes ending in leaf 2. A curved dotted arrow also maps leaf 1 and leaf 0 of the first tree to leaf 2 of the second. Panel (B) shows two separate trees. The first tree has a root with a left leaf labeled 1 and a right path of four nodes ending in leaf 0. The second tree has a root with a left path of two nodes ending in leaf 1 and a right path of three nodes ending in leaf 0.

This qo is a variant of Kruskal’s tree ordering (introduced in Section 2.4.3), which is defined via the notion of homeomorphic embeddings.

The condition, also called infimum preservation, is the only addition in comparison to the earlier tree homomorphisms. Note that it automatically makes the map injective.

Technically speaking, Kruskal’s tree ordering is usually defined on finite trees with both internal and leaf labels. Adapted to the above qo, Kruskal proved the following eponymous tree theorem [Reference Kruskal11].

Bounds for the maximal order type of this ordering (for a slightly more general collection of trees) were given by Schmidt in her survey [Reference Schmidt, Schuster, Seisenberger and Weiermann20].

It is quite easy to see that $(\mathsf {T_f}(Q), \le _T) \hookrightarrow (\mathsf {T_f}(Q), \le _K)$ , which immediately gives us the following theorem.

The notion of quasi-ordering trees via the existence of tree homomorphisms was introduced by Montalbán [Reference Montalbán16], and studied further with Marcone [Reference Marcone and Montalbán14], in the context of so-called signed trees. Specifically, their collection of trees were finite trees with internal vertices labelled by $\bar {2}$ , for which they calculated the precise maximal order type (of $\varphi (2,0)$ ). Friedman and Weiermann [Reference Friedman and Weiermann7] generalized their construction to consider finite trees with internal vertices and leaf vertices labelled by disjoint qos; in their notation, $\mathsf {T_f}(Q)$ would be denoted by $\mathbb {T}(1,Q)$ . They calculate upper and lower bounds for the maximal order types of these wqos, but their lower bounds are quite loose. In the next section, we state the precise value of the maximal order type of $\mathsf {T_f}(Q)$ as a function of $o(Q)$ ; in particular, by improving their lower bound.

An inductive definition of $\le _T$ will be quite useful for the upcoming sections.

It is an easy exercise to show that the two definitions of $\le _T$ are equivalent.

Compare this inductive definition of $\le _T$ with the finite powerset operator $\mathsf {P_f}$ (see Definition 2.25). Informally, the set of leaf-labelled trees $\mathsf {T_f}(Q)$ can be thought of as the closure of $Q \cup \mathsf {P_f}(Q) \cup \mathsf {P_f}(\mathsf {P_f}(Q)) \cup \mathsf {P_f}(\mathsf {P_f}(\mathsf {P_f}(Q))) \cup \cdots $ under a suitable ordering. An explicit correspondence that we will often use is the following.

3.2 Maximal order types

Since the set of leaf-labelled trees $\mathsf {T_f}(Q)$ is a wqo when Q is a wqo, we would like to calculate the maximal order type $o(\mathsf {T_f}(Q))$ as some function of $o(Q)$ .

When Q contains only a single element, this calculation is quite easy. It also serves as a good moment to introduce notation for non-branching trees with a single leaf vertex, whose only parameters are their height and the label on the leaf vertex.

This gives us the maximal order type when the qo Q only has one equivalence class.

The value of $o(\mathsf {T_f}(2))$ , however, is not so obvious. As we shall see, there is a great jump in complexity as soon as there are just two non-equivalent elements.

In order to calculate $o(\mathsf {T_f}(Q))$ for some arbitrary wqo Q, we shall first find appropriate upper bounds for its value, then prove that they serve as a lower bound as well.

3.2.1 Upper bounds

The usual way to show upper bounds for the maximal order type of wqos is by studying the structure of the sets $L(x)$ defined by its elements (recall Definition 2.16 and Theorem 2.17). Instead of calculating their precise maximal order types, they are embedded into simpler wqos using order-reflecting maps, whose order types are easier to describe.

The upper bounds for the value of $o(\mathsf {T_f}(Q))$ will be given using the epsilon numbers $\varepsilon _\alpha $ , with $\alpha $ ranging over the ordinals. The epsilon numbers enumerate the fixed-points of $\omega \text {-exponentiation}$ : that is, every epsilon number $\varepsilon $ satisfies $\omega ^\varepsilon = \varepsilon $ . This enumeration is, of course, strictly increasing.

In particular, the first epsilon number $\varepsilon _0$ is the supremum of the ordinals $\{ \omega , \omega ^\omega , \omega ^{\omega ^\omega }, \omega ^{\omega ^{\omega ^\omega }}, \dots \}$ .

The choice of epsilon numbers as the upper bound is because of their closure properties, which we state without proof.

Proposition 3.13. Let $\varepsilon $ be an epsilon number, and $\delta , \gamma < \varepsilon $ be two arbitrary ordinals smaller than $\varepsilon $ . Then:

1. (1) $\varepsilon $ is closed under $\omega \text {-exponentiation}$ : $\omega ^\delta < \varepsilon $ .

2. (2) $\varepsilon $ is closed under finite sums: $\delta + \gamma < \varepsilon $ .

3. (3) $\varepsilon $ is closed under finite products: $\delta \cdot \gamma < \varepsilon $ .

Ordinals closed under finite sums and products are called additively indecomposable ordinals and multiplicatively indecomposable ordinals, respectively.

The enumeration of the epsilon numbers also has fixed points: ordinals $\delta $ satisfying the equality $\varepsilon _\delta = \delta $ . This causes a problem because of the following inequality.

Proposition 3.14. Given a non-empty wqo Q, $o(\mathsf {T_f}(Q))> o(Q)$ .

Proof Consider $L(\cdot {0}^2)$ , where $0$ is any minimal element of Q. Clearly it contains all the leaf vertices, and thus $o(Q) \leq l(\cdot {0}^2) < o(\mathsf {T_f}(Q))$ .

Thus, the upper bound cannot be given by a function with fixed points, so we modify the enumeration of the epsilon numbers slightly.

Definition 3.15. The fixed-point-free epsilon function $\bar \varepsilon $ is defined as follows:

$$ \begin{align*}\bar\varepsilon(\alpha) = \begin{cases} \varepsilon_{\alpha+1}, & \text{if } \alpha = \gamma + n \text{ for some } \gamma \text{ and } n < \omega \text{ such that } \varepsilon_{\gamma} = \gamma, \\ \varepsilon_{\alpha}, & \text{otherwise.} \end{cases}\end{align*} $$

We can now define the function we will use to upper bound the value of $o(\mathsf {T_f}(Q))$ .

Definition 3.16. Let g be a function from ordinals to ordinals defined as follows:

$$ \begin{align*}g(\alpha) = \begin{cases} 0, & \alpha = 0, \\ \omega, & \alpha = 1,\\ \bar\varepsilon(-2 + \alpha), & \alpha \geq 2. \end{cases} \end{align*} $$

Another way to describe the function g is as follows. Let $g(0) = 0$ . Then, $g(\alpha )$ for $\alpha> 0$ is the least ordinal strictly greater than $\alpha $ and $g(\beta )$ for any $\beta < \alpha $ such that $g(\alpha )$ is closed under 2-exponentiation: for any $\gamma < g(\alpha )$ , $2^{\gamma } < g(\alpha )$ . Note that g is fixed-point-free.

The change from $\omega \text {-exponentiation}$ to 2-exponentiation is to incorporate $\omega $ into the sequence. Recall that $2^\omega = \omega $ and thus $\omega $ is also a fixed point of 2-exponentiation, and the rest of the fixed points of 2-exponentation and $\omega \text {-exponentiation}$ coincide.

The function g inherits the closure properties of the epsilon numbers, while being fixed-point-free and strictly increasing. Since these properties are crucial to the calculation of the upper bound, let us restate them as a proposition.

Proposition 3.17. The function g satisfies the following properties:

1. (1) Every ordinal in $\text {range}(g)$ is closed under 2-exponentiation, finite sums, and finite products.

2. (2) g is fixed-point-free: for any ordinal $\alpha $ , $\alpha \neq g(\alpha )$ .

3. (3) g is strictly increasing: for ordinals $\alpha < \beta $ , $g(\alpha ) < g(\beta )$ .

This finally lets us state and prove the upper bound for arbitrary wqos.

Proposition 3.18. Given a non-empty wqo $(Q,\le _Q)$ , $o(\mathsf {T_f}(Q)) \leq g(o(Q))$ .

Proof We induct on the order type $o(Q)$ . For the rest of the proof, we denote $L_{\mathsf {T_f}(Q)}(\tau )$ by $L(\tau )$ for $\tau \in \mathsf {T_f}(Q)$ , and keep the subscript for $L_Q(x)$ for $x \in Q$ .

The case for $o(Q) = 1$ is immediate. Consider an arbitrary wqo Q with $o(Q)> 1$ , with the statement holding for all smaller wqos. We show by induction on the height $ht(\tau )$ that $o(L(\tau)) < g(o(Q))$ for all $\tau \in \mathsf {T_f}(Q)$ .

Let $\tau $ be a leaf vertex, that is, $\tau = \cdot {x}$ for some $x \in Q$ . If x is the minimum element of Q then $L(\tau ) = \emptyset $ , so assume otherwise. A tree $\sigma $ belongs to $L(\tau )$ iff there is no leaf vertex $\cdot {y} \in v(\sigma )$ such that $x \le _Q y$ , and hence all the leaf vertices of $\sigma $ are labelled by elements of $L_Q(x) \subset Q$ . Thus $L(\tau ) \cong \mathsf {T_f}(L_Q(x))$ , and

$$ \begin{align*}o(L(\tau)) \leq o(\mathsf{T_f}(L_Q(x))) \leq g(o(L_Q(x))) < g(o(Q)) \end{align*} $$

since $o(L_Q(x)) < o(Q)$ and g is a strictly monotonic function.

Otherwise, let $\tau = \cdot (\tau _i)_{i<k}$ with $k<\omega $ . Every leaf vertex $\cdot {x}$ for $x \in Q$ belongs to $L(\tau )$ by definition. On the other hand, let $\sigma \in L(\tau )$ be a tree $\cdot (\sigma _j)_{j<l}$ . Since $\tau \not \le _T \sigma $ , there is a $\tau _i$ with $i<k$ such that for every $\sigma _j$ with $j<l$ we have $\tau _i \not \le _T \sigma _j$ . In this case $\sigma $ can be described as a member of $\mathsf {P_f}(L(\tau _i))$ (recall Lemma 3.10).

Thus,

$$ \begin{align*}L(\tau) \hookrightarrow \{\cdot{x} \mathop{\mid} x \in Q\} \sqcup \bigsqcup_{i<k} \mathsf{P_f}(L(\tau_i)).\end{align*} $$

Then,

$$ \begin{align*} o(L(\tau)) & \leq o(Q) \oplus \bigoplus_{i<k} o(\mathsf{P_f}(L(\tau_i))) \\ & \leq o(Q) \oplus \bigoplus_{i<k} 2^{o(L(\tau_i)),} \end{align*} $$

where we get the bounds on the order types using Proposition 2.24 and Lemma 2.26.

We know that $o(Q) < g(o(Q))$ , by Proposition 3.17. Since $ht(\tau _i) < ht(\tau )$ , we can apply the induction hypothesis to get $o(L(\tau _i)) < g(o(Q))$ for each $i<k$ . By Proposition 3.17, we also know that $g(o(Q))$ is closed under finite sums and $2\text {-exponentation}$ . Thus, we get $o(L(\tau )) < g(o(Q))$ .

Since $o(\mathsf {T_f}(Q)) = \sup _{\tau \in \mathsf {T_f}(Q)}o(L(\tau ))$ , we get the upper bound $o(\mathsf {T_f}(Q)) \leq g(o(Q))$ .

Remark 3.19. The proof is, unsurprisingly, quite similar to the one presented in [Reference Friedman and Weiermann7, Lemma 6.4]. However, when $o(Q)$ is finite, their upper bound is slightly looser: if $o(Q) = k < \omega $ , their upper bound would give $o(\mathsf {T_f}(Q)) \leq \varepsilon _k$ instead of the sharper $o(\mathsf {T_f}(Q)) \leq \varepsilon _{k-2}$ (or $\omega $ when $k=1$ ) proved above.

3.2.2 Lower bounds

Our next goal is to show that the function g also works as a lower bound for the maximal order type. We do so by considering the width instead, and show a lower bound for $w(\mathsf {T_f}(Q))$ . For that, we will use the connection to finite powersets along with the exponential growth provided by Lemma 2.27.

First, let us revisit the connection to finite powersets in the context of this section.

Lemma 3.20. For any non-empty wqo Q, $o(\mathsf {T_f}(Q)) = o(\mathsf {P_f}(\mathsf {T_f}(Q)))$ and $w(\mathsf {T_f}(Q)) = w(\mathsf {P_f}(\mathsf {T_f}(Q)))$ .

Proof This follows from Lemma 3.10, since the map $\tau \mapsto \cdot (\tau )$ is an order-embedding from $\mathsf {T_f}(Q)$ to $(\mathsf {T_f}(Q) \setminus \{ \cdot {q} \mathop{\mid} q \in Q \}) = \overline {\mathsf {T_f}}(Q)$ , and $\overline {\mathsf {T_f}}(Q) \cong \mathsf {P_f}(\mathsf {T_f}(Q))$ .

Now, using Lemma 2.27, we can already state something quite strong.

Lemma 3.21. Let Q be a non-empty wqo. If $w(\mathsf {T_f}(Q))> \omega $ , then $w(\mathsf {T_f}(Q))$ is an epsilon number.

Proof Let $w(\mathsf {T_f}(Q)) \geq \alpha> \omega $ . By Lemma 2.27, $w(\mathsf {P_f}(\mathsf {T_f}(Q))) \geq 2^\alpha $ . Then, since $w(\mathsf {P_f}(\mathsf {T_f}(Q))) = w(\mathsf {T_f}(Q))$ by Lemma 3.20, $w(\mathsf {T_f}(Q)) \geq 2^\alpha $ . Thus $w(\mathsf {T_f}(Q))$ is closed under 2-exponentiation, and since the fixed points of 2-exponentation and $\omega $ -exponentiation greater than $\omega $ coincide, it is also closed under $\omega $ -exponentation.

Finally, consider an arbitrary wqo Q and its maximal order type $o(Q)$ . Clearly, $\mathsf {T_f}(o(Q)) \hookrightarrow \mathsf {T_f}(Q)$ by lifting the map for $o(Q) \hookrightarrow Q$ . This implies that $o(\mathsf {T_f}(o(Q))) \leq o(\mathsf {T_f}(Q))$ , so any lower bound for $o(\mathsf {T_f}(o(Q)))$ is also a lower bound for $o(\mathsf {T_f}(Q))$ . Thus, for this section, it will suffice to consider only well-orders as labels.

The first non-trivial calculation is for the case of two labels.

Lemma 3.22. $w(\mathsf {T_f}(2)) \geq \omega + 1$ .

Proof Let $\omega ^2_{\text {desc}}$ be an induced suborder of $\omega \times \omega $ consisting of the set of all tuples $(i,j)$ with $j < i < \omega $ . We will show that $\omega ^2_{\text {desc}}$ can be order-embedded into $\mathsf {T_f}(2)$ .

Clearly $\omega ^2_{\text {desc}}$ is a wqo. In fact, its maximal order type is also $\omega ^2$ , since for any fixed $k \in \omega $ we can show that $\omega \cdot k \hookrightarrow \omega ^2_{\text {desc}}$ (by mapping $\omega \cdot j + i < \omega \cdot k$ for $j < k$ and $i < \omega $ to the tuple $(i+k, j) \in \omega ^2_{\text {desc}}$ ). The width of $\omega ^2_{\text {desc}}$ is at least $\omega $ since we can construct arbitrarily long antichains of the form $\{(2k,0), (2k-1,1), (2k-2,2), \dots , (k+1,k-1)\}$ for any finite $k> 0$ .

Let $h \colon \omega ^2_{\text {desc}} \to \mathsf {T_f}(2)$ be defined as follows (see Figure 3). Fix $(i,j) \in \omega ^2_{\text {desc}}$ with $i> j$ . Then, $h((i,j)) = \cdot (\cdot {0}^{i+3},\cdot (\cdot {1},\cdot {0}^{j+2}))$ . This tree does not collapse: $\cdot {0}^{i+3} \not \le _T \cdot (\cdot {1},\cdot {0}^{j+2})$ since $ht(\cdot {0}^{i+3}) = i + 2> j + 2 = ht(\cdot (\cdot {1},\cdot {0}^{j+2}))$ , and $\cdot (\cdot {1},\cdot {0}^{j+2}) \not \le _T \cdot {0}^{i+3}$ since $\cdot {0}^{i+3}$ has no leaf vertex labelled by $1$ .

Figure 3

The map $h \colon \omega ^2_{\text {desc}} \to \mathsf {T_f}(2)$ for arbitrary $(i,j) \in \omega ^2_{\text {desc}}$ , and an example of the tree $h((2,1))$ .

Figure 3 Long description

The image contains two panels showing binary tree structures.

Left Panel: A tree starting from a single root node at the top. It splits into two branches. The left branch leads to a dashed triangle labeled dot 0 super i plus 3. The right branch splits again into two sub-branches. The left sub-branch ends at a leaf node labeled 1. The right sub-branch leads to a dashed triangle labeled dot 0 super j plus 2.

Right Panel: A more detailed tree structure representing h((2,1)). From the root node at the top, the left path descends through five intermediate nodes to a leaf node labeled 0. The right path from the root descends to a node that splits. The left split from this node descends to a leaf node labeled 1. The right split from this node descends through three intermediate nodes to a leaf node labeled 0.

It is easy to see that $(i_0,j_0) \le (i_1,j_1)$ iff $h((i_0,j_0)) \le _T h((i_1,j_1))$ , and thus h is an order-embedding. The tree $\cdot {1}^4$ is incomparable with the range of h (since the minimum height of a tree in its range, specifically $h((1,0))$ , is at least 4), and thus $w(\mathsf {T_f}(2)) \geq \omega + 1$ .

Corollary 3.23. $o(\mathsf {T_f}(2)) \geq w(\mathsf {T_f}(2)) \geq \varepsilon _0 = g(2)$ .

Proof By Lemmas 3.21 and 3.22, $w(\mathsf {T_f}(2))$ is an epsilon number. The smallest epsilon number is $\varepsilon _0$ , and thus the statement follows.

We now generalize the proof for ordinals $\gamma> 2$ , with the only problematic case being the fixed points of the enumeration of the epsilon numbers (i.e., for $\gamma = \varepsilon _\gamma $ ).

Lemma 3.24. For any ordinal $\gamma> 2$ , $o(\mathsf {T_f}(\gamma )) \geq w(\mathsf {T_f}(\gamma )) \geq \bar \varepsilon (-2 + \gamma ) = g(\gamma )$ .

Proof We prove this by induction on $\gamma $ , with $\gamma = 2$ being the base case. We have already shown that $o(\mathsf {T_f}(2)) \geq w(\mathsf {T_f}(2)) \geq \varepsilon _0$ .

Let $\gamma = \alpha + 1$ be a successor ordinal, with $o(\mathsf {T_f}(\alpha )) \geq w(\mathsf {T_f}(\alpha )) \geq \bar \varepsilon (-2 + \alpha )$ by the induction hypothesis. Let $S := \{ \cdot (\tau )\mathop{\mid} \tau \in \mathsf {T_f}(\alpha ) \}$ . Clearly $S \cong \mathsf {T_f}(\alpha )$ . All of its members are incomparable with the leaf vertex  $\cdot {\alpha }$ , that is, $S \subset L_{\mathrel {\bot }}(\cdot {\alpha })$ . Thus, the width of $S \cup \{ \cdot {\alpha } \}$ as an induced suborder of $\mathsf {T_f}(\alpha +1)$ is at least $\bar \varepsilon (-2 + \alpha ) + 1$ .

By Lemma 3.21, $w(\mathsf {T_f}(\alpha + 1))$ is an epsilon number larger than $\bar \varepsilon (-2 + \alpha ) + 1$ . Thus, by definition, $w(\mathsf {T_f}(\alpha + 1)) \geq \bar \varepsilon (-2 + \alpha + 1)$ and we are done.

Let $\gamma> 0$ be a limit ordinal such that $\varepsilon _\gamma \neq \gamma $ . For any $\alpha < \gamma $ , $\mathsf {T_f}(\alpha ) \subset \mathsf {T_f}(\gamma )$ and by the induction hypothesis $w(\mathsf {T_f}(\gamma )) \geq \bar \varepsilon (-2 + \alpha )$ . Thus, $o(\mathsf {T_f}(\gamma )) \geq w(\mathsf {T_f}(\gamma )) \geq \sup _{\alpha <\gamma }\bar \varepsilon (-2 + \alpha ) = \varepsilon _\gamma $ . Since $\gamma $ is not a fixed point of the enumeration of the epsilon numbers, we have $\bar \varepsilon (-2 + \gamma ) = \varepsilon _\gamma $ and we are done.

Finally, let $\gamma> 0$ be a limit ordinal such that $\varepsilon _\gamma = \gamma $ . Now the previous argument no longer applies, so we take the help of the qo of finite multisets $M(\gamma )$ to escape the fixed-point. Our goal is to embed $M(\gamma )$ into some small subset of $\mathsf {T_f}(\gamma )$ .

It is a folklore result that $M(\beta ) \cong \mathsf {P_f}(\beta \times \omega )$ for any well-order $\beta $ .Footnote ² For concreteness, here is a proof sketch.

Subproof

Let $\beta> 0$ be a well-order. Given a multiset $m \in M(\beta )$ , map it to the set $s \in \mathsf {P_f}(\beta \times \omega )$ defined as

$$ \begin{align*}s = \{ (\delta_i, n_i) \mid \delta_i \in m, n_i = |\{ \delta' \in m \mid \delta' \geq \delta_i \}| - 1\}.\end{align*} $$

On the other hand, let $s \in \mathsf {P_f}(\beta \times \omega )$ , and let $s' = \{ (\delta _i, n_i) \}_{i<k}$ be the maximal antichain in s such that, for $i<j<k$ , $\delta _i> \delta _j$ , and $n_i < n_j$ . Map it to the multiset $m \in M(\beta )$ that has $n_0+1$ copies of $\delta _0$ , and $(n_i - n_{i-1})$ copies of $\delta _i$ for $0 < i < k$ . These two maps witness $M(\beta ) \cong \mathsf {P_f}(\beta \times \omega )$ in the sense of Definition 2.4.

Back to $\mathsf {T_f}(\gamma )$ . Map an element $(\alpha , k) \in \gamma \times \omega $ to the tree $\cdot (\cdot {\alpha }, \cdot {0}^{2+k}) \in \mathsf {T_f}(\gamma )$ . Let the range of this map be $S \subset \mathsf {T_f}(\gamma )$ . Clearly this is an order-embedding, and $(S,\le _T) \cong \gamma \times \omega $ . We can now use Lemma 3.10 to get $\bar {S} \cong \mathsf {P_f}(\gamma \times \omega ) \cong M(\gamma )$ . Thus, $o(\bar {S}) = o(M(\gamma )) = \omega ^{\widehat \gamma }$ by Lemma 2.29, where $\omega ^{\widehat \gamma } = \omega ^{\gamma + 1} = \gamma \cdot \omega> \gamma $ . Since $\gamma $ is an epsilon number and thus an additively indecomposable ordinal, we can use [Reference Džamonja, Schmitz, Schnoebelen, Schuster, Seisenberger and Weiermann4, Theorem 4.27] to also get $w(\bar {S}) = o(\bar {S})> \gamma $ .

Again, by Lemma 3.21, $w(\mathsf {T_f}(\gamma ))$ is an epsilon number strictly greater than $\gamma = \varepsilon _\gamma $ , and the least such epsilon number is $\varepsilon _{\gamma +1}$ . By definition $\bar \varepsilon (\gamma ) =\varepsilon _{\gamma +1}$ and thus $w(\mathsf {T_f}(\gamma )) \geq \bar \varepsilon (\gamma )$ .

This completes the proof.

By combining Lemma 3.12, Corollary 3.23, and Lemma 3.24, we get the following proposition.

Proposition 3.25. For any ordinal $\gamma> 0$ , $o(\mathsf {T_f}(\gamma )) \geq w(\mathsf {T_f}(\gamma )) \geq g(\gamma )$ .

Remark 3.26. Specifically for leaf-labelled trees, and with our notation, the lower bound stated in [Reference Friedman and Weiermann7, Lemma 6.5] is the following:

$$ \begin{align*}o(\mathsf{T_f}(Q \sqcup 1)) \geq \omega^{o(Q)}.\end{align*} $$

This is much weaker than the lower bound proved above: for example, if $Q = \delta $ for some ordinal $\delta \geq \omega $ , we get $o(\mathsf {T_f}(Q \sqcup 1)) \geq \bar \varepsilon (\delta + 1)$ .

3.2.3 Results

We can now finally combine the results of the previous two sections to give the precise value of the maximal order type of $\mathsf {T_f}(Q)$ .

Theorem 3.27. Given a non-empty wqo $(Q,\le )$ , $o(\mathsf {T_f}(Q)) = w(\mathsf {T_f}(Q)) = g(o(Q))$ , where $g(1) = \omega $ and $g(\alpha ) = \bar \varepsilon (-2 + \alpha )$ for $\alpha \geq 2$ .

Proof We get $w(\mathsf {T_f}(Q)) \leq o(\mathsf {T_f}(Q)) \leq g(o(Q))$ from Proposition 3.18.

Since $o(Q) \hookrightarrow Q$ , we get $g(o(Q)) \leq w(\mathsf {T_f}(o(Q))) \leq o(\mathsf {T_f}(o(Q))) \leq o(\mathsf {T_f}(Q))$ from Proposition 3.25. On the other hand, any incomparable trees in $\mathsf {T_f}(o(Q))$ are also necessarily incomparable trees in $\mathsf {T_f}(Q)$ (since $o(Q) \hookrightarrow Q$ via a surjective map, modulo equivalence classes), and so $w(\mathsf {T_f}(o(Q))) \leq w(\mathsf {T_f}(Q))$ as well.

We get the statement of the theorem by combining both sets of inequalities.

Unfortunately, the methods used in Section 3.2.2 to prove the lower bound are not immediately formalizable in $\mathsf {RCA_0}$ , with the main blocker being the proof of Lemma 2.27. It is not too difficult to modify it for our purposes, but it is a bit tedious and out of scope for this article. Instead, let us take a blunter approach.

For a linear order $(\Omega , \leq )$ , let $(\varepsilon _\Omega , \preceq )$ be the linear order consisting of:

1. (1) constants $0$ , $\omega $ , and $\varepsilon _\alpha $ for $\alpha \in \Omega $ , with $0 \prec \omega \prec \varepsilon _\alpha $ for all $\alpha \in \Omega $ ;

2. (2) terms $\langle t_0, t_1, \dots , t_{k-1} \rangle $ whenever $t_0 \succ t_1 \succ \dots \succ t_{k-1} \in \varepsilon _\Omega $ , ordered lexicographically by $\preceq $ (and $t_0 \neq \omega $ and $t_0 \neq \varepsilon _\alpha $ for any $\alpha \in \Omega $ when $k = 1$ );

3. (3) for constant c and term $t = \langle t_0, t_1, \dots , t_{k-1} \rangle $ , if $c \preceq t_0$ then $c \prec t$ , and if $t_0 \prec c$ then $t \prec c$ .

This is intended to be a notation system for the epsilon numbers with terms in base-2 normal form. A more precise definition can be found in, for example, [Reference Freund6, Definition 3.3], which has terms in base- $\omega $ normal form; the correspondence between them is straightforward.

Now, let us prove a weaker—but more useful—lower bound for $o(\mathsf {T_f}(Q))$ .

Theorem 3.28. In $\mathsf {RCA_0}$ , $\varepsilon _\Omega \hookrightarrow \mathsf {T_f}(2 \cup \Omega )$ (where $0 < 1 < \alpha $ for $\alpha \in \Omega $ in $2 \cup \Omega $ ).

Proof sketch

Let any term $t \in \varepsilon _\Omega $ such that $t \prec \omega $ be called finite (including the constant $0$ ). We can map finite terms to their value $v(t)$ in $\mathbb {N}$ .

We inductively define a map $h \colon \varepsilon _\Omega \to \mathsf {T_f}(2 \cup \Omega )$ as follows:

1. (1) For a finite term t with $v(t) = n$ , $h(t) = \cdot (\cdot {1}, \cdot {0}^{n+2})$ .

2. (2) $h(\omega ) = \cdot {1}^3$ and $h(\varepsilon _\alpha ) = \cdot {\alpha }$ for $\alpha \in \Omega $ .

3. (3) For a term $t = \langle t_0, t_1, \dots , t_{k-1}, \dots , t_{k+l-1} \rangle $ such that $t_f = \langle t_k, \dots , t_{k+l-1} \rangle $ is finite with $v(t_f) = n$ , let $\tau _i = \cdot (h(t_i), \cdot {0}^{m_i})$ with $m_i = \sum _{j=0}^{i} (ht(h(t_j)) + 2)$ for every $i < k$ , and $\tau _f = \cdot (h(t_f), \cdot {0}^{m_f})$ with $m_f = m_k + n + 4$ . Then $h(t) = \cdot (\tau _0, \tau _1, \dots , \tau _{k-1}, \tau _f)$ . (If $l = 0$ , ignore $t_f$ and $\tau _f$ .)

The map h is order-reflecting; this can be readily verified by case analysis.

We can now use this to derive some reverse mathematical corollaries. Recall that the proof-theoretic ordinal of an arithmetical theory is, informally, the supremum of the order types of computably definable linear orders that are provably well-orders. Simply by using two comparable labels, we get a statement which is independent of $\mathsf {ACA_0}$ , whose proof-theoretic ordinal is well-known to be $\varepsilon _0$ . This is a remarkable jump in arithmetical strength, given that $o(\mathsf {T_f}(1))$ is only $\omega $ , and we do not even require any incomparable elements.

Corollary 3.29. The statement “ $\mathsf {T_f}(2)$ is a wqo” is not provable in $\mathsf {ACA}_0$ .

For linear orders $\Omega $ that are infinite and have a definable successor function, we have $2 \cup \Omega \hookrightarrow \Omega $ . Thus, we can get similar independence results for the theories $\mathsf {ACA}'$ and $\mathsf {ACA}$ , whose proof-theoretic ordinals are $\varepsilon _\omega $ and $\varepsilon _{\varepsilon _0}$ , respectively, using appropriate wqos.

There has been a line of research studying the reverse-mathematical strength of so-called well-ordering principles: statements of the form “if $\Omega $ is a well-order, then so is $\mathsf {F}(\Omega )$ ,” where $\mathsf {F}$ is some specific operator on linear orders. The following theorem was proved in [Reference Marcone, Schuster, Seisenberger and Weiermann13] as well as [Reference Afshari and Rathjen2], using computability-theoretic and proof-theoretic methods, respectively.

Theorem 3.30. Over $\mathsf {RCA}_0$ , the statement “if $\Omega $ is a well-order, then so is $\varepsilon _{\Omega }$ ” is equivalent to $\mathsf {ACA}^+_0$ .

This leads to the following equivalence, barring some details.

Theorem 3.31. Over $\mathsf {RCA_0}$ , the statement “if $(Q,\le )$ is a wqo, then $\mathsf {T_f}(Q)$ is also a wqo” is equivalent to $\mathsf {ACA^+_0}$ .

Proof sketch

The forward direction follows from Theorems 3.28 and 3.30.

It remains to show that the statement “ $(Q,\le )$ is a wqo implies $\mathsf {T_f}(Q)$ is a wqo” can be proven in $\mathsf {ACA^+_0}$ . The classical approach to attain this sort of formalization would be via the notion of reifications (see [Reference Simpson23, Section 4]). Given a reification of Q by $\alpha $ , it is not too difficult to use the techniques in the proof of Proposition 3.18 to show a reification of $\mathsf {T_f}(Q)$ by $\varepsilon _{\alpha +1}$ . We instead sketch a different proof.

We reason in $\mathsf {ACA_0^+}$ , and assume that Q is a wqo while $\mathsf {T_f}(Q)$ is not. It is known that $\mathsf {ACA^+_0}$ proves, for a finite number of arbitrary sets, the existence of a countable coded $\omega $ -model of $\mathsf {ACA_0}$ containing those sets (e.g., see [Reference Afshari and Rathjen2, Lemma 3.4]). Let $\mathcal {M}$ be an $\omega $ -model of $\mathsf {ACA_0}$ containing Q and an infinite bad sequence of $\mathsf {T_f}(Q)$ . Our goal is to show that $\mathcal {M}$ thinks that in fact $\mathsf {T_f}(Q)$ is a wqo, and thus reach a contradiction.

For this, we consider a family of suborders of Q generated by bad sequences of Q: containing, for a bad sequence $\sigma = \langle q_0, q_1, \dots , q_{k-1} \rangle $ , the set

$$ \begin{align*}L(\sigma) = \{q \in Q \mathop{\mid} \forall i < k. \, \, q_i \not\le q\},\end{align*} $$

with the family ordered by inclusion. This is clearly definable in $\mathcal {M}$ , and since Q is a wqo, the inclusion order is well-founded. Note that $L(\langle \rangle ) = Q$ .

From the analysis in Section 3.2.1, for any $\tau \in \mathsf {T_f}(L(\sigma ))$ , $L(\tau )$ being a wqo is implied by $\mathsf {T_f}(L(\sigma + \langle q_0 \rangle )), \dots , \mathsf {T_f}(L(\sigma + \langle q_k \rangle ))$ being wqos (where $q_0,\dots ,q_k$ are the labels of the leaf vertices of $\tau $ ), along with closure properties of $\mathsf {P_f}$ and $\sqcup $ ; this holds in $\mathsf {ACA_0}$ . Since assertions that $\mathsf {T_f}(L(\sigma ))$ is a wqo in $\mathcal {M}$ , for any $\sigma $ , are arithmetical, we can prove that all $\mathsf {T_f}(L(\sigma ))$ are wqos according to $\mathcal {M}$ (and hence also $\mathsf {T_f}(Q)$ ) by an instance of transfinite induction that is formalizable in $\mathsf {ACA^+_0}$ .

4.1 Transfinite sequences

We first introduce some basic definitions and facts about transfinite sequences.

We can define a few simple operations on transfinite sequences—namely those of concatenation and exponentiation—which we shall be using in the upcoming sections.

Definition 4.3. Given sequences $\sigma $ and $\tau $ over Q, their concatenation $\sigma + \tau $ is a transfinite sequence of length $|\sigma | + |\tau |$ such that

$$ \begin{align*}(\sigma + \tau)(\iota) = \begin{cases} \sigma(\iota), & \iota < |\sigma|\\ \tau(-|\sigma| + \iota), & |\sigma| \leq \iota < |\sigma| + |\tau|. \end{cases}\end{align*} $$

Essentially, $\sigma + \tau $ is the sequence obtained by placing a copy of $\tau $ after a copy of $\sigma $ .

Essentially, $\sigma ^\alpha $ is the sequence obtained by concatenating “ $\alpha $ many” copies of $\sigma $ . This is more concrete when $\alpha $ is some finite k: $\sigma ^k$ is simply $\sigma + \sigma + \dots + \sigma $ (k many times).

In order to form a qo from these collections of transfinite sequences, we now define a way of comparing them by way of sequence embeddings.

The qo $\preceq $ respects lengths of sequences: if $\sigma \preceq \tau $ then $|\sigma | \leq |\tau |$ ; or equivalently, if $|\sigma | \not \leq |\tau |$ then $\sigma \not \preceq \tau $ .

This lets us define qos $(s(Q),\preceq )$ and $(s_\alpha (Q), \preceq )$ (for any non-zero ordinal $\alpha $ ) of transfinite sequences over a qo Q, of arbitrary length and of length strictly less than $\alpha $ , respectively, ordered by sequence embeddability. As usual, we will identify both the qos and the underlying sets by $s(Q)$ and $s_\alpha (Q)$ when there is no ambiguity.

The restriction to $\alpha = \omega $ is quite well known.

It is known that the Higman ordering over Q is a wqo whenever Q itself is a wqo, with a well-defined maximal order type based on the maximal order type of Q [Reference Higman8, Reference de Jongh and Parikh9]. Thus, it is natural to ask whether the same holds for any $\alpha $ . Unfortunately, Rado showed that things fall apart at the very first step [Reference Rado19, Theorem 2].

Fortunately, there is a way to salvage the situation by focusing on transfinite sequences of finite range.

This leads us to the required generalization of the result for the Higman ordering.

This theorem was proved by Nash-Williams [Reference Nash-Williams17] as a broad generalization of existing results for specific $\alpha $ . The proof assumes the existence of a bad sequence of elements of $s^F_\alpha (Q)$ , showing that it leads to a contradiction. The tools that are used—in particular the so-called thin sets—are the precursors of what would become the theory of better-quasi-orders. Of course, as mentioned before, there are no known methods to extract information about the maximal order type of $s^F_\alpha (Q)$ from this proof.

A more constructive proof was given earlier by Erdös and Rado [Reference Erdös and Rado5] for ordinals less than $\omega ^\omega $ .

Schmidt [Reference Schmidt, Schuster, Seisenberger and Weiermann20, Section 3.3] proposed non-trivial upper bounds for the maximal order type of $s^F_\alpha (Q)$ for any $\alpha $ , but her proof has a fatal flaw.Footnote ³ Specifically, in the proof of Theorem 3.6 for case $\alpha \in \{\beta , \beta +1 \}$ , the sequence g that is constructed may no longer have finite range.

In the remainder of this section, we consider the case for $\alpha = \omega ^\omega $ , that is, the qo $s^F_{\omega ^\omega }(Q)$ , as a generalization of the result by Erdös and Rado, and calculate its maximal order type as a function of the maximal order type of Q. As mentioned above, this serves as partial progress towards calculating $o(s^F_\alpha (Q))$ for any $\alpha $ , left open after Schmidt’s erroneous proof.

4.2 Indecomposable transfinite sequences

In order to study arbitrary transfinite sequences, we first consider a particularly uniform subset of $s(Q)$ .

It readily follows that the length of any indecomposable sequence must be an additively indecomposable ordinal of the form $\omega ^\alpha $ for some $\alpha $ . Note that sequences of the form $\sigma ^\omega $ are always indecomposable, with length $|\sigma | \cdot \omega $ .

Indecomposable sequences are very well behaved when it comes to embeddability in yet another sense.

This proposition can be generalized in a straightforward manner.

In order to study the qos $s^F_\alpha (Q)$ we define the following induced suborder consisting only of indecomposable sequences.

Since $i^F_\alpha (Q)$ is an induced suborder of $s^F_\alpha (Q)$ , by Nash-Williams’ theorem, $i^F_{\omega ^\omega }(Q)$ is a wqo whenever Q is a wqo. Our goal, in the following sections, is to compute the maximal order type of $i^F_{\omega ^\omega }(Q)$ in terms of the maximal order type of Q.

4.3 Correspondence with finite leaf-labelled trees

In this section we show that the qos $i^F_{\omega ^\omega }(Q)$ and $\mathsf {T_f}(Q)$ are equivalent (in the sense of Definition 2.4), which would let us simply reuse the results for $o(\mathsf {T_f}(Q))$ from Section 3.2.

The route from leaf-labelled trees to indecomposable sequences is relatively straightforward.

As mentioned before, any sequence of the form $\sigma ^\omega $ is an indecomposable sequence. By a simple induction, if $ht(\tau ) = n$ then $|f(\tau )| = \omega ^n < \omega ^\omega $ . Additionally, the range of $f(\tau )$ is the set of labels on the leaf vertices of $\tau $ (and hence finite). Thus, the map f is well-defined.

The route from indecomposable sequences to leaf-labelled trees is a bit more hairy. First, we need to define a way to further decompose indecomposable sequences.

Definition 4.19. For an indecomposable sequence $\sigma \in i^F_\alpha (Q)$ , the set of its cofinal factors is denoted by $\text {factors}(\sigma )$ and is defined as

$$ \begin{align*}\text{factors}(\sigma) = \{ \tau \in i^F_{|\sigma|}(\text{range}(\sigma)) \mathop{\mid} \tau^\omega \preceq \sigma \}.\end{align*} $$

Unfortunately, while it is clear that the range of g consists of finite leaf-labelled trees, it is not clear that it is a total function: $g(\sigma )$ is not defined if $\text {factors}(\sigma )$ is not a finite set. Our goal is to show that this cannot happen for indecomposable sequences with finite range.

For analysing the embedding g, it will be helpful to have some notation for sequences of an exact specified length.

Proof We induct on n. For $n = 0$ , $s^F_{=1}(Q) = i^F_{=1}(Q) \cong Q$ , and $s^F_\omega (Q) = Q^*$ consists of finite sequences, thus both statements are trivial.

For any $n> 0$ , statement (2) holds by a simple induction on the length of an arbitrary $\sigma \in s_{\omega ^{n+1}}^F(Q)$ . If $|\sigma | = \omega ^m$ for $m < n+1$ (i.e., $\sigma \in s_{=\omega ^m}^F(Q)$ ), then by combining the induction hypothesis for statements (1) and (2), $\sigma $ can be decomposed as $\sigma _0 + \sigma _1 + \cdots + \sigma _{k-1} + \sigma _k$ , where $\sigma _i \in i^F_{\omega ^m}(Q)$ for $i < k$ and $\sigma _k \in i^F_{=\omega ^m}(Q)$ . Otherwise, if $|\sigma | = \alpha + \omega ^m < \omega ^{n+1}$ , where $\omega ^m$ is the smallest ordinal in the Cantor normal form of $|\sigma |$ , we induct on the prefix of length $\alpha $ and apply the previous reasoning to the tail of length $\omega ^m$ .

Now we focus on statement (1). Let $n = 1$ . Consider a sequence $\sigma \in s_{=\omega }^F(Q)$ of length $\omega $ , and define $P := \text {range}(\sigma )$ . By assumption, $i_\omega ^F(P) \cong P$ is a wqo (and also trivially, since P is finite). Define $P_{\mathit {cf}} \subset P$ to be the elements of P that occur cofinally in $\sigma $ . More precisely,

$$ \begin{align*}P_{\mathit{cf}} := \{ p \in P \mathop{\mid} \forall i.\, \exists j> i.\,\, \sigma(j) = p \}.\end{align*} $$

$P_{\mathit {cf}}$ cannot be empty, since otherwise every $p \in P = \text {range}(\sigma )$ would have a largest index where it occurs; since P is finite, this would contradict $|\sigma | = \omega $ . If $P = P_{\mathit {cf}}$ , then clearly $\sigma \in i_{=\omega }^F(Q)$ . Assume otherwise, and let $m := 1 + \max _{i < \omega } \sigma (i) \in P \setminus P_{\mathit {cf}}$ .

Let $\sigma _0 := \langle \sigma (0), \sigma (1), \dots , \sigma (m-1) \rangle $ be a proper prefix of $\sigma $ of length m, and $\sigma _1$ be the proper tail of $\sigma $ starting at index m. By definition, $\sigma _0 \in s_{\omega }^F(Q)$ , and since all elements that occur in $\sigma $ after the index m occur cofinally, $\sigma _1 \in i_{=\omega }^F(Q)$ . This completes the decomposition.

Now we generalize this proof. Let $n> 1$ . Consider a sequence $\sigma \in s_{=\omega ^n}^F(Q)$ , and define $P := \text {range}(\sigma )$ . We can consider $\sigma $ as a sequence $\sigma _0 + \sigma _1 + \dots $ of length $\omega $ of elements of $s_{=\omega ^{n-1}}^F(P)$ . (Note that this may not be representable as an element of $s_{=\omega }^F(s_{=\omega ^{n-1}}^F(P))$ since the range is not necessarily finite!)

By induction hypothesis, each $\sigma _i$ can be decomposed as $\sigma _{i0} + \cdots + \sigma _{i{(k-1)}} + \sigma _{ik}$ of elements of $i_{\omega ^{n-1}}^F(P)$ and $i_{=\omega ^{n-1}}^F(P)$ , and thus as elements of $i_{\omega ^n}^F(Q)$ . So, consider $\sigma = \tau _0 + \tau _1 + \cdots $ as a sequence $(\tau _i)_{i \in \omega }$ of length $\omega $ of elements of $i_{\omega ^n}^F(P)$ .

Since P is finite, $i_{\omega ^n}^F(P)$ is a wqo by assumption. Define a certain set of indices I as

$$ \begin{align*}I := \{ i < \omega \mathop{\mid} \forall j> i. \,\, \tau_i \not\preceq \tau_j \}.\end{align*} $$

Clearly, for indices $i_0, i_1 \in I$ with $i_0 < i_1$ , we have $\tau _{i_0} \not \preceq \tau _{i_1}$ . If $|I| = \omega $ , we would have a bad sequence $(\tau _i)_{i \in I}$ of elements of $i_{\omega ^n}^F(P)$ , which we assumed to be a wqo. Thus, $|I| < \omega $ .

Let $m := 1 + \max I$ if I is non-empty, and $m := 0$ otherwise. By the definition of I, for any $i \geq m$ there exists $j> i$ such that $\tau _i \preceq \tau _j$ . This implies that we can make the index j arbitrarily large: for any $l \geq 0$ , there exists such a $j> i + l$ ; since we can use the property to get an ascending sequence $\tau _i = \tau _{i_0} \preceq \tau _{i_1} \preceq \cdots \tau _{i_l} \preceq \tau _{i_{l+1}}$ with $i_{l+1}> i + l$ . Thus $\langle \tau _{m}, \tau _{m+1}, \dots \rangle $ is an indecomposable sequence of elements of $i_{\omega ^n}^F(P)$ .

Let $\sigma _0 := \tau _0 + \tau _1 + \cdots + \tau _{m-1}$ be a prefix of $\sigma $ if $m \neq 0$ , and let $\sigma _1 := \tau _{m} + \tau _{m+1} + \cdots $ be the tail of $\sigma $ starting at index m (as a sequence of elements of $i^F_{\omega ^n}(Q)$ ). If $m = 0$ then $\sigma = \sigma _1$ and $\sigma \in i^F_{=\omega ^n}(Q)$ . Otherwise, $\sigma _0 \in s_{\omega ^n}^F(Q)$ , and since $\omega ^n$ is an additively indecomposable ordinal, $|\sigma _1| = \omega ^n$ and $\sigma _1 \in i^F_{=\omega ^n}(Q)$ . This completes the proof.

Just like before, it will be helpful to have some notation for trees of bounded and fixed heights, as counterparts to $i^F_{\omega ^n}(Q)$ and $i^F_{=\omega ^n}(Q)$ .

Since we have shown that both f and g are well-defined and order-embeddings between $i^F_{\omega ^\omega }(Q)$ and $\mathsf {T_f}(Q)$ , we are finally ready to state the main theorem of this section.

Proof By Lemma 4.18 and Proposition 4.25, the maps $f \colon \mathsf {T_f}(Q) \to i^F_{\omega ^\omega }(Q)$ and $g \colon i^F_{\omega ^\omega }(Q) \to \mathsf {T_f}(Q)$ are both well-defined order-embeddings. By Remark 2.5, it suffices to show either of the two properties in Definition 2.4. Thus we show the following: for any $\sigma \in i^F_{\omega ^\omega }(Q)$ , $f(g(\sigma )) \equiv \sigma $ , by induction on the length of $\sigma $ .

For $\sigma \in i^F_{=1}(Q)$ the statement follows from definition. So, let $\sigma \in i^F_{=\omega ^n}(Q)$ for $n> 0$ , with the statement assumed to hold for any sequence in $i^F_{\omega ^n}(Q)$ .

Let $\text {factors}(\sigma ) = \{ \sigma _0, \sigma _1, \dots , \sigma _{k-1} \}$ for some $k < \omega $ . By definition,

$$ \begin{align*} g(\sigma) &= \cdot(g(\sigma_0), g(\sigma_1), \dots, g(\sigma_{k-1})) \text{, and} \\ f(g(\sigma)) &= (f(g(\sigma_0)) + f(g(\sigma_1)) + \cdots + f(g(\sigma_{k-1})))^\omega. \end{align*} $$

We know that $\text {factors}(\sigma ) \subset i^F_{\omega ^n}$ . By induction hypothesis, for each $i < k$ , $f(g(\sigma _i)) \equiv \sigma _i$ . Thus, $f(g(\sigma )) \equiv (\sigma _0 + \sigma _1 + \cdots + \sigma _{k-1})^\omega $ . In the proof of Proposition 4.25 we showed that $\sigma \equiv (\sigma _0 + \sigma _1 + \cdots + \sigma _{k-1})^\omega $ , and hence $f(g(\sigma )) \equiv \sigma $ and we are done.

4.4 Maximal order types

With the help of the correspondence between leaf-labelled trees and indecomposable sequences, we can simply reuse the maximal order types which were proved in Theorem 3.27.

The maximal order type for arbitrary transfinite sequences is obviously bounded below by the maximal order type of indecomposable sequences. From Proposition 4.22, we can derive a loose upper bound $o(s^F_{\omega ^n}(Q)) \leq o(i^F_{\omega ^n}(Q)^*)$ for wqo Q and finite $n < \omega $ . However, we can do better if we collectively consider all sequences of length less than $\omega ^\omega $ .

Proof First, a trivial case: when $|Q| = o(Q) = 1$ , clearly $s^F_{\omega ^\omega }(Q) = i^F_{\omega ^\omega }(Q) = \omega $ . The rest of the proof assumes that $o(Q)> 1$ .

Every sequence $\sigma \in s^F_{\omega ^\omega }(Q)$ is embeddable in some indecomposable sequence $\sigma _{\mathit {in}} \in i^F_{\omega ^\omega }(Q)$ : in particular, it holds for $\sigma _{\mathit {in}} = \sigma ^\omega $ . We say that $i^F_{\omega ^\omega }(Q)$ is a majorizing subset of $s^F_{\omega ^\omega }(Q)$ .

To simplify notation, for any $\sigma \in s^F_{\omega ^\omega }(Q)$ , let $L(\sigma ) := L_{s^F_{\omega ^\omega }(Q)}(\sigma )$ ; and when $\sigma \in i^F_{\omega ^\omega }(Q)$ , let $L_{\mathit {in}}(\sigma ) := L_{i^F_{\omega ^\omega }(Q)}(\sigma )$ .

For any $\sigma _0, \sigma _1 \in s^F_{\omega ^\omega }(Q)$ , if $\sigma _0 \preceq \sigma _1$ then $L(\sigma _0) \subset L(\sigma _1)$ and $o(L(\sigma _0)) \leq o(L(\sigma _1))$ . Thus, we get

(1) $$ \begin{align} o(s^F_{\omega^\omega}(Q)) &= \sup_{\sigma \in s^F_{\omega^\omega}(Q)} o(L(\sigma))\nonumber \\ &= \sup_{\sigma_{\mathit{in}} \in i^F_{\omega^\omega}(Q)} o(L(\sigma_{\mathit{in}})). \end{align} $$

We are not done yet, since $L(\sigma _{\mathit {in}})$ in the equation is with respect to the qo $s^F_{\omega ^\omega }(Q)$ and not $i^F_{\omega ^\omega }(Q)$ .

Pick an arbitrary $\sigma _{\mathit {in}} \in i^F_{\omega ^\omega }(Q)$ and consider any $\tau \in s^F_{\omega ^\omega }(Q)$ . By Proposition 4.22, we know that we can decompose $\tau $ as $\tau = \tau _0 + \tau _1 + \cdots + \tau _{k-1}$ where every $\tau _i \in i^F_{\omega ^\omega }(Q)$ for $i < k < \omega $ . If $\sigma _{\mathit {in}} \preceq \tau $ then from Proposition 4.15 there is some $i < k$ such that $\sigma _{\mathit {in}} \preceq \tau _i$ . Thus, if $\sigma _{\mathit {in}} \not \preceq \tau $ then $\sigma _{\mathit {in}} \not \preceq \tau _i$ for all $i < k$ . Thus

$$ \begin{align*}L(\sigma_{\mathit{in}}) \hookrightarrow (L_{\mathit{in}}(\sigma_{\mathit{in}}))^*.\end{align*} $$

By definition, $o(L_{\mathit {in}}(\sigma _{\mathit {in}})) < o(i^F_{\omega ^\omega }(Q))$ . Since we assumed that $o(Q)> 1$ , $o(i^F_{\omega ^\omega }(Q))$ is an epsilon number and hence closed under $\omega \text {-exponentiation}$ . Thus,

$$ \begin{align*} o(L(\sigma_{\mathit{in}})) &\leq o(L_{\mathit{in}}(\sigma_{\mathit{in}}))^* \\ &\leq \omega^{\omega^{o(L_{\mathit{in}}(\sigma_{\mathit{in}})) + 1}} \\ &< o(i^F_{\omega^\omega}(Q)). \end{align*} $$

The bounds for $o(Q^*)$ (i.e., the Higman order over Q) can be found in [Reference Schmidt, Schuster, Seisenberger and Weiermann20, Theorem 2.9]. This shows that

$$ \begin{align*}\sup_{\sigma_{\mathit{in}} \in i^F_{\omega^\omega}(Q)} o(L(\sigma_{\mathit{in}})) \leq o(i^F_{\omega^\omega}(Q))\end{align*} $$

and, by Equation (1), we are done.

Let us restate the results for the maximal order type of $s^F_{\omega ^\omega }(Q)$ in isolation.