# Ordinal measures of the set of finite multisets

Isa Vialard

► To cite this version:

Isa Vialard. Ordinal measures of the set of finite multisets. MFCS 2023, Aug 2023, Bordeaux, France. 10.4230/LIPIcs.hal-04287405

HAL Id: hal-04287405

https://hal.science/hal-04287405v1

Submitted on 15 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Ordinal measures of the set of finite multisets

Isa Vialard ORCID

Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, 91190, Gif-sur-Yvette France

**Abstract**

Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and mathematics. In this article we focus on a common data structure in programming, finite multisets of some well partial order. There are two natural orders one can define on the set of finite multisets of a partial order: the multiset embedding and the multiset ordering. Though the maximal order type of these orders is already known, other ordinal invariants remain mostly unknown. Our main contributions are expressions to compute compositionally the width of the multiset embedding and the height of the multiset ordering. Furthermore, we provide a new ordinal invariant useful for characterizing the width of the multiset ordering.

**2012 ACM Subject Classification** Theory of computation → Complexity theory and logic; Theory of computation → Logic and verification; Theory of computation → Proof theory; Theory of computation → Program reasoning

**Keywords and phrases** Well-partial order, finite multisets, termination, program verification

**Digital Object Identifier** 10.4230/LIPIcs...

**Related Version** https://arxiv.org/abs/2302.09881

## Introduction

**Measuring partial orders** is useful in many domains, from set theory to proof theory, including infinitary combinatorics, program verification, rewriting theory, proof automation and many more.

There are intuitive notions of measure for a partial order when it is finite: its cardinal obviously, but also its height (the length of a maximal chain) or its width (the length of a maximal antichain). Similar notions exist for infinite partial orders, as long as they are *well partial orders* (*wpo*), i.e., well-founded partial orders with no infinite antichains [10, 12]. Two such notions are the *ordinal height*, which is the order type of a maximal chain, and the *maximal order type* (*mot*), which is the order type of a maximal linearisation, a notion introduced by De Jongh and Parikh in order to measure hierarchies of functions [6]. These are transfinite measures, hence we call them *ordinal invariants*. Kříž and Thomas introduced alternative characterizations for *mot* and ordinal height, which naturally led to the definition of a third ordinal invariant, *ordinal width* [11]. Less studied than its counterparts, the width of a *wpo* relates to its antichains, even though it cannot be defined as the order type of a maximal antichain. While exploring techniques for program termination, Blass and Gurevich rediscovered these characterizations with a game-theoretical point of view [4].

Ordinal invariants of *wpos* have also been used to prove complexity bounds. In the last decade there has been a flurry of complexity results for the verification of well-structured transition systems (wsts), i.e., transition systems whose set of configurations is a *wpo* and whose transitions respect this ordering [5]. When a wsts is based on a *wpo X* of maximal order type $\omega^\alpha$, one can expect the complexity of coverability to be in $H_{\omega^\alpha}$ in the Hardy hierarchy, or in $F_\alpha$ in the fast-growing hierarchy [9]. This bound can be refined by looking at controlled antichains instead of controlled bad sequences [14], thus bounding complexity with width instead of maximal order type.
XX:2 Ordinal measures of the set of finite multisets

**Computing ordinal invariants compositionally.** Many wpos underlying wsts are built from classical operations on simpler wpos whose invariants are known. This has spurred new interest in measuring the ordinal invariants of various well-ordered data structures: De Jongh and Parikh computed the mot of the disjoint sum and the Cartesian product of wpos [6]. Schmidt then computed the mot of word embedding and homeomorphic tree embedding on a wpo [13]. Abraham and Bonnet pursued this line of study by computing the height of Cartesian product, but also the width of disjoint sum and lexicographic product [1]. For a complete survey of these results see [8], where Džamonja et al. computed the ordinal invariants of the lexicographic product, but also the height of the multiset word and tree embeddings.

**Finite multisets:** In this article, we study the ordinal invariants of the set of finite multisets. Multisets, also called “bags”, a common data structure in computer science. Informally, a finite multiset over a set $X$ is a finite subset of $X$ where an element can appear finitely many times. For instance, $\langle a, a, b \rangle$ denote the multiset where $a$ appears twice and $b$ once. One can see the set of finite multisets on a wpo as the set of finite words quotiented by the equivalence relation “equality up to some permutation”. It comes down to describing a multiset as a word where the order of terms is irrelevant. A finite multiset can be represented by a function from $X$ to $\mathbb{N}$ with finite support, which associates its multiplicity with each element.

Two orderings are classically defined on the finite multisets of any ordered set. The first one is the *multiset ordering*, which often appears in rewriting theory and automation of termination proofs [7]. The other, less-known, ordering is the *multiset embedding*, or term ordering as it is called in [15]. It was presented by Aschenbrenner and Pong as a natural extension of the embedding order over finite words [3].

Some invariants of these two orderings have already been measured: Van der Meeren, Rathjen, and Weiermann [15] built on [17] to compute the mot of the set of finite multisets on a wpo $X$ ordered with the multiset ordering, and provided a new proof for the expression of the mot of the multiset embedding computed in [18]. Džamonja et al. [8] proved that the height of the multiset embedding is equal to the height of the set of finite words ordered with word embedding. It is noteworthy that these three results give expressions that are functional in (i.e., can be expressed as a function of) the mot and height of $X$. However, the height of the multiset ordering still needs to be determined, and the width remains unstudied for both orderings.

**Our contributions:** In this article, we provide functional expressions for the width of the multiset embedding (Theorem 2.1) and the height of the multiset ordering (Theorem 3.1).

We further show that the width of the multiset ordering cannot be expressed as a function of the three ordinal invariants (Example 3.2). Nonetheless, we get around this issue by introducing a fourth ordinal invariant, the *friendly order type* (Definition 3.3), in which the width of the multiset ordering is functional (Theorem 3.4). We then proceed to investigate and compute this new ordinal invariant.

# 1 Definitions and state of the art

## 1.1 Width, height and maximal order type

A sequence $x_1, \dots, x_n, \dots$ on a partial order ($X, \le_X$) is *good* when there exist $i < j$ such that $x_i \le_X x_j$, otherwise it is a *bad* sequence. An *antichain* is a sequence whose elements are pairwise incomparable.
A well partial order (wpo) is a partial order that has no infinite bad sequences. Equivalently, a wpo is a partial order that is both well-founded (i.e. no infinite strictly decreasing sequences) and has no infinite antichains.

Let $(X, \le_X)$ be a wpo. We often write just $X$ when $\le_X$ is understood. The trees $\text{Bad}(X)$, $\text{Dec}(X)$ and $\text{Ant}(X)$ are defined as the sets of bad sequences, strictly decreasing sequences, and antichains of $X$, respectively, ordered by inverse prefix order (a sequence is smaller than its prefixes) ([11, 8]). The finiteness of bad sequences, strictly decreasing sequences and antichains in a wpo implies that these trees are well-founded. Therefore, one can define a notion of rank on these trees: a sequence has rank 0 when it cannot be extended; otherwise its rank is the smallest ordinal strictly larger than the ranks of its extensions. The rank of a tree is the rank of the empty sequence (which is the root of the tree).

The maximal order type (or mot) of $X$, denoted by $o(X)$, is defined as the rank of $\text{Bad}(X)$. Similarly, the height $h(X)$ and the width $w(X)$ of $X$ are defined as the ranks of $\text{Dec}(X)$ and $\text{Ant}(X)$, respectively. Together, $o(X)$, $h(X)$ and $w(X)$ are called the ordinal invariants of $X$.

For any wpo $X$, $\text{Dec}(X)$ and $\text{Ant}(X)$ are subtrees of $\text{Bad}(X)$. Thus $h(X) \le o(X)$ and $w(X) \le o(X)$.

Let $x \perp y$ denote that $x$ and $y$ are incomparable. For a relation $*$ among $\{\ge, <, \perp\}$, we define the residual $X_{*x}$ as $\{y \in X : y * x\}$. This definition can be extended to subsets $S \subseteq X: X_{*S} \stackrel{\text{def}}{=} \{y \in X : \forall x \in S, y * x\}$.

**Example 1.1.** In Figure 1, you can see the residuals at $x = (4,6)$ of $\mathbb{N} \times \mathbb{N}$ ordered component-wise.

<figure><img src="image_2.png" /><figcaption>Figure 1 Residuals of $\mathbb{N}^2$ at (4, 6).</figcaption></figure>

Since the rank of the empty sequence is the smallest ordinal strictly larger than the ranks of the sequences of length 1, the definitions of mot, height and width can be reformulated inductively through the following residual equations:

$$o(X) = \sup_{x \in X} (o(X_{\ge x}) + 1) \qquad (\text{Res-o})$$

$$h(X) = \sup_{x \in X} (h(X_{< x}) + 1) \qquad (\text{Res-h})$$

$$w(X) = \sup_{x \in X} (w(X_{\perp x}) + 1) \qquad (\text{Res-w})$$

With these equations we can compute easily the ordinal invariants of $\mathbb{N}^2$. For instance, observe that $(\mathbb{N}^2_{<x})$ is finite for any $x \in \mathbb{N}^2$, so its height is finite but can be arbitrarily big. Hence $h(\mathbb{N}^2) = \omega$.
XX:4 Ordinal measures of the set of finite multisets

1.2 Ordinal arithmetic

123

124

125

126

127

128

129

130

We suppose well-known the notions of sum, product, subtraction, natural sum, natural product on ordinals, denoted with $+, -, \oplus, \otimes$ [2]. However, let us recall some definitions and notations that might be less familiar to the reader.

An ordinal $\alpha$ is *indecomposable* iff for any $\delta, \gamma < \alpha$, we have $\delta \oplus \gamma < \alpha$. Equivalently, $\alpha$ is indecomposable when there is an ordinal $\beta$ such that $\alpha = \omega^\beta$. $\alpha$ is an *e-number* when $\alpha = \omega^\alpha$.

The Hessenberg-based product $\alpha \odot \beta$ is defined inductively as follows [1]:

131

132

$$ \alpha \odot 0 = 0, \quad \alpha \odot (\beta + 1) = (\alpha \odot \beta) \oplus \alpha, \quad \alpha \odot \beta = \sup\{\alpha \odot \gamma : \gamma < \beta\} \text{ for limit } \beta. $$

This definition ensures that $\alpha \cdot \beta \le \alpha \odot \beta \le \alpha \otimes \beta$.

133

134

135

For any ordinal $\alpha = \omega^{\alpha_1} + \dots + \omega^{\alpha_n}$, let $\hat{\alpha} \stackrel{\text{def}}{=} \omega^{\alpha'_1} + \dots + \omega^{\alpha'_n}$, where $\alpha'_i$ is $\alpha_i + 1$ when $\alpha_i$ is the sum of an e-number and a finite ordinal, otherwise $\alpha'_i = \alpha_i$.

136

$$ \text{For any ordinals } \alpha, \beta, \text{ let } \alpha \hat{\oplus} \beta \stackrel{\text{def}}{=} \sup\{\alpha' \oplus \beta' : \alpha' < \alpha, \beta' < \beta\}. $$

1.3 Ordinal invariants of basic data structures

137

138

139

140

141

For any wpos $P, Q$, the *disjoint sum* $P \sqcup Q$ is the disjoint union of $P$ and $Q$ ordered such that elements of $P$ and $Q$ cannot be compared together, whereas the *direct sum* $P + Q$ is the disjoint union of $P$ and $Q$ ordered such that for all $p \in P, q \in Q, p \le q$. For a family of wpos $(A_i)_{i<\alpha}$, let $\Sigma_{i<\alpha} A_i$ denote the direct sum of the $A_i$s along the ordinal $\alpha$.

142

143

144

The Cartesian product $P \times Q$ is the set of pairs $(p, q) \in P \times Q$ where elements are compared component-wise. The lexicographic product of $P$ along $Q$, written $P \cdot Q$, has the same support as $P \times Q$, with a different ordering: $(p, q) \le_{P \cdot Q} (p', q')$ iff $q <_Q q'$, or $q = q'$ and $p \le_P p'$.

145

146

147

148

Sums and products are the most basic operations on wpos one can find. Their ordinal invariants are easy to compute compositionally (see Table 1), with the notable exception of the width of the Cartesian product which cannot be expressed as a function of the ordinal invariants its factors [16].

<table><caption>Table 1 How to compute ordinal invariants compositionally, [8]. See Section 1.2 for definitions of $\hat{\oplus}$ and $\odot$</caption><thead><tr><th>Space X</th><th>M.O.T. o(X)</th><th>Height h(X)</th><th>Width w(X)</th></tr></thead><tbody><tr><td>A &sqcup; B</td><td>o(A) &oplus; o(B)</td><td>max(h(A), h(B))</td><td>w(A) &oplus; w(B)</td></tr><tr><td>A + B</td><td>o(A) + o(B)</td><td>h(A) + h(B)</td><td>max(w(A), w(B))</td></tr><tr><td>A &times; B</td><td>o(A) &otimes; o(B)</td><td>h(A) &oplus; h(B)</td><td>(Not functional)</td></tr><tr><td>A &middot; B</td><td>o(A) &middot; o(B)</td><td>h(A) &middot; h(B)</td><td>w(A) &odot; w(B)</td></tr></tbody></table>

1.4 Comparing wpos

149

150

151

A widely-used and intuitive relation between wpos is the *reflection relation*. A mapping between wpos $f: (A, \le_A) \to (B, \le_B)$ is a *reflection* if $f(x) \le_B f(y)$ implies $x \le_A y$, i.e. it is
a morphism from $(A, \leq_A)$ to $(B, \leq_B)$ Let $A \leftrightarrow B$ denote that there is a reflection from $A$ to $B$.

However, in this article, we prefer to use the stronger notions of augmentations and substructures.

**Definition 1.2 (Substructure, augmentation).** A wpo $(A, \leq_A)$ is a substructure of a wpo $(B, \leq_B)$ whenever $A \subseteq B$ and $\leq_A$ is the restriction of $\leq_B$ to $A$. This relation is written $A \leq_{st} B$. Similarly $(A, \leq_A)$ is an augmentation of $(B, \leq_B)$ whenever $A = B$ and $\leq_B \subseteq \leq_A$. We write this relation $A \geq_{aug} B$.

Obviously, $A \leq_{st} B$ or $A \geq_{aug} B$ imply $A \leftrightarrow B$.

We often abuse these notations and write $A \leq_{st} B$ (resp. $B \leq_{aug} A$) to mean that $A$ is isomorphic to a substructure (resp. an augmentation) of $B$.

We denote by $A \equiv B$ that $(A, \leq_A)$ is isomorphic to $(B, \leq_B)$.

In this article, when we consider a subset $Y$ of a wpo $X$, it is understood that $Y \leq_{st} X$, i.e. $Y$ is ordered with $\leq_X$ restricted to the subset.

These notions of augmentations and substructures allow us to compare the ordinal invariants of wpos.

**Lemma 1.3.** Let $A$ and $B$ be wpos.

If $A \leq_{st} B$ then $i(A) \leq i(B)$ for $i \in \{o, h, w\}$.

If $A \geq_{aug} B$ then $o(A) \leq o(B)$ and $w(A) \leq w(B)$. However $h(A) \geq h(B)$.

The substructure and augmentation relations are monotonous through most operations on wpos. For instance, if $A \leq_{st} A'$, then $A \times B \leq_{st} A' \times B$.

An ordinal, as defined by Von Neumann, is the linear wpo that contains all smaller ordinals. Thus augmentations and substructures relations can also be used to compare directly ordinals to wpos. The following result is well-known:

**Proposition 1.4.** For any wpo $X$, $h(X)$ and $o(X)$ are the largest ordinals such that $h(X) \leq_{st} X$ and $o(X) \geq_{aug} X$.

## 1.5 Orderings on the set of finite multisets

We assume familiarity with finite multisets and the associated operations as used in [17]: union, intersection and subtraction, denoted by $\cup, \cap$ and $\setminus$, respectively. Let $(x_1, \dots, x_n)$ denote the finite multiset that contains the elements $x_1, \dots, x_n$ (they do not have to be distinct). For any $k \in \mathbb{N}$, $m \times k$ means the union of $k$ copies of $m$. Let $|m|$ denote the number of elements of a multiset $m$.

There are two main orderings classically defined on the set of finite multisets $M(X)$ of a partial order $X$:

**Definition 1.5 (Multiset embedding [18]).** The multiset embedding on $M(X)$, also known as the term ordering, is defined as:

$m \leq_{\diamond} m'$ iff there exists $f : m \to m'$ injective such that for any $x \in m$, $x \leq f(x)$.

**Definition 1.6 (Multiset ordering [17]).** The multiset ordering on $M(X)$ is defined as:

$$m \leq_r m' \iff m = m' \text{ or } \forall x \in m \setminus (m \cap m'), \exists y \in m' \setminus (m \cap m'), x < y.$$

We write $M^{\diamond}(X)$ for $(M(X), \leq_{\diamond})$ and $M^r(X)$ for $(M(X), \leq_r)$.

The multiset ordering and the multiset embedding are both augmentations of the word embedding on $X^*$ the set of finite words on $X$. Therefore, according to Higman's lemma [10],
XX:6 Ordinal measures of the set of finite multisets

$M^{\diamond}(X)$ and $M^r(X)$ are wpos when $X$ is. Moreover $M^{\diamond}(X) \le_{\text{aug}} M^r(X)$, as was observed
by Aschenbrenner and Pong [3].

Observe that if $X$ is a linear ordering, then $M^r(X)$ is linear, while $M^{\diamond}(X)$ is not as long
as $X$ has more than two elements.

► **Proposition 1.7** (Transformation equations). For any wpos $A$ and $B$,

$$
M^*(A \sqcup B) \equiv M^*(A) \times M^*(B) \text{ for } * \in \{\diamond, r\}, \qquad (\text{Trans-1})
$$

$$
M^r(A + B) \equiv M^r(A) \cdot M^r(B), \qquad (\text{Trans-2})
$$

$$
M^{\diamond}(A + B) \le_{\text{aug}} M^{\diamond}(A) \cdot M^{\diamond}(B). \qquad (\text{Trans-3})
$$

**Lemma 1.8** (Width of $M(X)$ on $\Gamma_k$). For any $k < \omega$, we denote by $\Gamma_k$ the wpo that contains $k$ incomparable elements. Then $\mathbf{w}(M^{\diamond}(\Gamma_k)) = \mathbf{w}(M^r(\Gamma_k)) = \omega^{k-1}$.

**Proof.** Since $M^{\diamond}(\Gamma_1) \equiv M^r(\Gamma_1) \equiv \omega$, Equation (Trans-1) tells us that $M^{\diamond}(\Gamma_k)$ and $M^r(\Gamma_k)$ are both isomorphic to the $k$-fold Cartesian product $\omega \times \dots \times \omega$. This special case of the width of a Cartesian product is known [16]: $\mathbf{w}(\omega \times \dots \times \omega) = \omega^{k-1}$. $\quad \blacksquare$

The augmentation and substructure relations are monotone with respect to the multiset ordering and multiset embedding:

**Proposition 1.9.** Let $A, B$ be two wpos. Then $A \le_{st} B$ implies $M^{\diamond}(A) \le_{st} M^{\diamond}(B)$ and $M^r(A) \le_{st} M^r(B)$. Moreover, $A \ge_{aug} B$ implies that $M^{\diamond}(A) \ge_{aug} M^{\diamond}(B)$ and $M^r(A) \ge_{aug} M^r(B)$.

Ordinal invariants of the set of finite multisets

Van der Meeren, Rathjen and Weiermann computed the mot of $M^{\diamond}(X)$ and $M^r(X)$.

**Theorem 1.10** (Mot of multiset embedding [15, 18]). For any wpo $X$, $o(M^{\diamond}(X)) = \omega^{\widehat{o(X)}}$.

**Theorem 1.11** (Mot of multiset ordering [15, 17]). For any wpo $X$, $o(M^r(X)) = \omega^{o(X)}$.

Observe that $\omega^{o(X)} \le \omega^{\widehat{o(X)}}$, as one would expect since $M^r(X) \ge \text{aug} M^{\diamond}(X)$. Furthermore, we expect that $\mathbf{w}(M^r(X)) \le \mathbf{w}(M^{\diamond(X)})$, while $\mathbf{h}(M^r(X)) \ge \mathbf{h}(M^{\diamond(X)})$.

**Theorem 1.12** (Height of the multiset embedding [8]). Let $X$ be a wpo.

Then $\mathbf{h}(M^{\diamond}(X)) = \mathbf{h}^{*}(X)$, where

$$
\mathbf{h}^*(X) \stackrel{\text{def}}{=} \begin{cases} \mathbf{h}(X) & \text{if } \mathbf{h}(X) \text{ is infinite and indecomposable,} \\ \mathbf{h}(X) \cdot \omega & \text{otherwise.} \end{cases}
$$

1.6 A tool to compute the width: Quasi-incomparable subsets

Of all three ordinal invariants, the width is the less studied, since it has been introduced
more recently, and also the hardest invariant to study for lack of tools.

A powerful tool to analyse the width of a wpo is the notion of quasi-incomparable subsets of a wpo, which was first introduced in [16] for the Cartesian product of several ordinals.

For any subsets $Y, Z$ of $X$, let $Y \perp Z$ denote that for every $y \in Y, z \in Z, y \perp z$.

**Definition 1.13.** Let $A$ be a wpo, and $A_1, \dots, A_n$ be $n$ subsets of $A$. Then $(A_i)_{1 \le i \le n}$ is a quasi-incomparable family of subsets of $A$ iff for any $i < n$, for any finite $Y \subseteq A_1 \cup \dots \cup A_i$, there exists $A'_{i+1} \subseteq A_{i+1}$ such that $A'_{i+1} \perp Y$ and $A'_{i+1} \equiv A_{i+1}$.
This definition is slightly more restrictive than the one in [16], which only required that $w(A'_{i+1}) = w(A_{i+1})$.

The idea behind these quasi-incomparable subsets is that sometimes one can slice a wpo $A$ into simpler subsets $A_1, \dots, A_n$ whose width is known, such that $Ant(A_n) + \dots + Ant(A_1)$ is embedded in $Ant(A)$. Intuitively, it means that one can combine antichains of $A_1, \dots, A_n$ into one antichain of $A$.

This entails a practical relation between the widths of $A$ and its subsets:

**Lemma 1.14 ([16]).** Let $(A_i)_{i \le n}$ be a quasi-incomparable family of subsets of $A$. Then $w(A) \ge w(A_n) + \dots + w(A_1)$.

## 2 Ordinal width of the multiset embedding

In this section we compute the width of $M^{\diamond}(X)$ for any wpo $X$, which happens to be functional in the width of $X$:

**Theorem 2.1 (Width of the multiset embedding).** For any wpo $X$, $w(M^{\diamond}(X)) = \omega^{\omega(X)-1}$. (See Section 1.2 for the definition of $\hat{\alpha}$.)

It is already known that, in some cases, the width of the multiset embedding reaches its mot.

**Lemma 2.2 ([8]).** If $o(X)$ is infinite and indecomposable, $w(M^{\diamond}(X)) = o(M^{\diamond}(X))$.

We focus for now on the set of finite multisets on a linear wpo, i.e., an ordinal. Let us treat first the case of successor ordinals.

**Lemma 2.3.** For any successor ordinal $\alpha = \beta + 1$, $w(M^{\diamond}(\alpha)) \ge w(M^{\diamond}(\beta)) \cdot \omega$.

**Proof.** We denote with $M^{\diamond}_{>k}(X)$ the subset $\{ m \in M^{\diamond}(X) : |m| > k \}$ for any $k \in \mathbb{N}$ of $M^{\diamond}(X)$ for any wpo $X$, for any $k < \omega$.

Let $m_n \stackrel{\text{def}}{=} \langle \beta \rangle \times n$ for any $n \in \mathbb{N}$. According to Equation (Res-w),

$$ \begin{aligned} w(M^{\diamond}(\alpha)) &= \sup\{ w(M^{\diamond}(\alpha)_{\perp m}) + 1 : m \in M^{\diamond}(\alpha) \} \\ &\ge \sup\{ w(M^{\diamond}(\alpha)_{\perp m_n}) + 1 : n \in \mathbb{N} \}. \end{aligned} $$

Let $M_k \stackrel{\text{def}}{=} \{ \langle \beta \rangle \times (n-k) \cup m : m \in M^{\diamond}_{>k}(\beta) \}$ for $k \in [1, n]$. These subsets of $M^{\diamond}(\alpha)$ are actually subsets of $M^{\diamond}(\alpha)_{\perp m_n}$: for all $m \in M_k$, $m \perp m_n$ since $|m| > |m_n|$. Observe also that for any $k \in [1, n]$, $M_k \equiv M^{\diamond}(\beta)$.

Moreover, $(M_k)_{k \in [1, n]}$ is a quasi-incomparable family of subsets of $M^{\diamond}(\alpha)_{\perp m_n}$: for any $i < n$, for any finite $Y \subset M_1 \cup \dots \cup M_i$, let $s(Y) = \max\{|m|, m \in Y\}$. Observe that $M_{i+1}$ contains $M_{i+1} \cap M^{\diamond}_{>s(Y)}(\beta)$ which is incomparable to $Y$, and isomorphic to $M_{i+1}$.

Therefore, $w(M^{\diamond}(\alpha)_{\perp m_n}) \ge w(M_n) + \dots + w(M_1) = w(M^{\diamond}(\beta)) \cdot n$ according to Lemma 1.14. Thus $w(M^{\diamond}(\alpha)) \ge \sup\{ w(M^{\diamond}(\beta) \cdot n + 1 : n \in \mathbb{N}) \} = w(M^{\diamond}(\beta)) \cdot \omega$. ◀

**Lemma 2.4.** For any infinite ordinal $\alpha$, $w(M^{\diamond}(\alpha)) = o(M^{\diamond}(\alpha))$.

**Proof.** We already know that $w(M^{\diamond}(\alpha)) \le o(M^{\diamond}(\alpha))$. We prove the lower bound by induction on $\alpha$:

■ If $\alpha$ is indecomposable, see Lemma 2.2.
XX:8 Ordinal measures of the set of finite multisets

267 ■ If $\alpha = \beta + 1$, then according to Lemma 2.3,

$$
\begin{align*}
\mathbf{w}(M^{\diamond}(\alpha)) &\ge \mathbf{w}(M^{\diamond}(\beta)) \cdot \omega \\
&= \mathbf{o}(M^{\diamond}(\beta)) \cdot \omega && \text{by induction hypothesis,} \\
&= \omega^{\beta+1} = \omega^{\beta+1} = \mathbf{o}(M^{\diamond}(\alpha)) && \text{according to Theorem 1.10.}
\end{align*}
$$

270

272 ■ If $\alpha = \beta + \omega^\rho$ with $\beta, \omega^\rho < \alpha$ and $\rho > 0$, then according to the transformation equation
273 Trans-3, $M^\circ(\alpha) \le_{\text{aug}} M^\circ(\beta) \cdot M^\circ(\omega^\rho)$. Hence according to Lemma 1.3 and Table 1,

$$
\begin{align*}
\mathbf{w}(M^{\diamond}(\alpha)) &\ge \mathbf{w}(M^{\diamond}(\beta)) \odot \mathbf{w}(M^{\diamond}(\omega^{\rho})) \\
&= \mathbf{o}(M^{\diamond}(\beta)) \odot \mathbf{o}(M^{\diamond}(\omega^{\rho})) && \text{by induction hypothesis,} \\
&= \omega^{\beta} \odot \omega^{\omega^{\rho}} = \omega^{\alpha} \\
&= \mathbf{o}(M^{\diamond}(\alpha)) && \text{according to Theorem 1.10.} \blacksquare
\end{align*}
$$

276

277

279 We can now prove that Lemma 2.4 generalizes to non-linear wpos.

280 ▶ Lemma 2.5. If $\mathbf{o}(X)$ is infinite then $\mathbf{w}(M^{\diamond}(X)) = \mathbf{o}(M^{\diamond}(X))$.

**Proof.** Let $\alpha = \mathbf{o}(X)$. Then $X \le_{\text{aug}} \alpha$ from Proposition 1.4, hence $M^{\diamond}(X) \le_{\text{aug}} M^{\diamond}(\alpha)$
according to Lemma 1.3 and Proposition 1.9. Thus

$$
\mathbf{w}(M^{\diamond}(\alpha)) \leq \mathbf{w}(M^{\diamond}(X)) \leq \mathbf{o}(M^{\diamond}(X)).
$$

281 Now $\mathbf{o}(M^{\diamond}(X)) = \omega^{\alpha} = \mathbf{o}(M^{\diamond}(\alpha))$ according to Theorem 1.10. Now with Lemma 2.4
282 $\mathbf{w}(M^{\diamond}(\alpha)) = \mathbf{o}(M^{\diamond}(\alpha))$, hence $\mathbf{w}(M^{\diamond}(X)) = \mathbf{o}(M^{\diamond}(X))$. $\quad \blacksquare$

283

We can also compute the width of $M^{\diamond}(X)$ when $X$ is a finite wpo:

284 ▶ Lemma 2.6. If $\mathbf{o}(X)$ is finite, then $\mathbf{w}(M^{\diamond}(X)) = \omega^{\mathbf{o}(X)-1}$.

Proof. Let $k = \mathbf{o}(X)$. Then $\Gamma_k \le_{\text{aug}} X \le_{\text{aug}} k$, hence $\mathbf{w}(M^{\diamond}(\Gamma_k)) \ge \mathbf{w}(M^{\diamond}(X)) \ge$
$\mathbf{w}(M^{\diamond}(k))$ thanks to Lemma 1.3. According to Lemma 1.8, $\mathbf{w}(M^{\diamond}(\Gamma_k)) = \omega^{k-1}$, and
according to Lemma 2.3 applied $(k-1)$ times, $\mathbf{w}(M^{\diamond}(k)) \ge \mathbf{w}(M^{\diamond}(1)) \cdot \omega^{k-1} = \omega^{k-1}$.
Therefore $\mathbf{w}(M^{\diamond}(X)) = \omega^{k-1} = \omega^{\mathbf{o}(X)-1}$. $\blacksquare$

286

287

288

289

This section's main result follows directly from Lemmas 2.5 and 2.6.

**Proof of Theorem 2.1.** If $\mathbf{o}(X)$ is finite, then $\mathbf{o}(\widetilde{X}) - 1 = \mathbf{o}(X) - 1$. On the other hand, if
$\mathbf{o}(X)$ is infinite, then $\mathbf{o}(\widetilde{X}) - 1 = \mathbf{o}(\widetilde{X})$. $\blacksquare$

290

291

292

3 Ordinal height and width of the multiset ordering

292

For the height of $M^r(X)$, we obtain a result similar to Theorem 1.11.

293

294 ▶ Theorem 3.1 (Height of the multiset ordering). Let $X$ be a wpo.

295

$$
\text{Then } h(M^r(X)) = \omega^{h(X)}.
$$

296

Proof. Observe that the multiset ordering of any linear ordering is also linear. Thus, for
any ordinal $\alpha$, $M^r(\alpha)$ is isomorphic to $\omega^\alpha$ (the function $\langle x_1, \dots, x_n \rangle \mapsto \omega^{x_1} \oplus \dots \oplus \omega^{x_n}$ is
an isomorphism).

297

298

According to Proposition 1.4, $X \ge_{\text{st}} h(X)$, and thus $M^r(X) \ge_{\text{st}} M^r(h(X)) = \omega^{h(X)}$
(Proposition 1.9). Therefore $h(M^r(X)) \ge \omega^{h(X)}$ according to Lemma 1.3. See the proof of
the upper bound in Appendix A. $\blacksquare$

299

300

301

302
The width of the multiset ordering is harder to compute, as $w(M^r(X))$ is not functional in the ordinal invariants of $X$. The following example exhibits two wpos $X_1$ and $X_2$, with identical ordinal invariants, such that $w(M^r(X_1)) \neq w(M^r(X_2))$.

**Example 3.2.** Let $H \stackrel{\text{def}}{=} \Sigma_{n<\omega}\Gamma_n$. An interesting property of $H$ is that $w(H) = h(H) = o(H) = \omega$. Since $M^r(H) \geq_{\text{st}} M^r(\Gamma_n)$, then $\omega^{n-1} \leq w(M^r(H)) \leq o(M^r(H)) = \omega^\omega$ for all $n < \omega$ according to Lemma 1.8 and Theorem 1.11. Hence $w(M^r(H)) = \omega^\omega$.

Consider $X_1 = H + H$ and $X_2 = H + \omega$, two wpos with the same ordinal invariants: $o(X_i) = h(X_i) = \omega \cdot 2$ and $w(X_i) = \omega$ for $i \in \{1, 2\}$. According to Equation (Trans-2) and Table 1, $w(M^r(X_1)) = w(M^r(H)) \odot w(M^r(H)) = \omega^\omega \odot \omega^\omega = \omega^{\omega \cdot 2}$ and $w(M^r(X_2)) = w(M^r(H)) \odot w(M^r(\omega)) = \omega^\omega \odot 1 = \omega^\omega$.

Fortunately, we uncovered a new ordinal invariant, defined similarly to the usual invariants, in which the width of the multiset ordering is functional.

**Definition 3.3 (Friendly order type).** A bad sequence is open-ended if it is empty or of the form $sx$ where $s$ is an open-ended sequence and $x$ has a "friend" 1 in the residual $X_{\ge s}$, i.e., an element incomparable to $x$. For any wpo $X$, let $\text{Bad}_{\perp}(X)$ be the subtree of $\text{Bad}(X)$ which contains all open-ended bad sequences. As $\text{Bad}_{\perp}(X)$ is a substructure of $\text{Bad}(X)$, it has a rank that we denote by $o_{\perp}(X)$ the friendly order type of $X$ (or fot).

This definition can be expressed as the following residual equation:

$$o_{\perp}(X) = \sup_{x \in X, X_{\perp} \neq \emptyset} (o_{\perp}(X_{\perp}x) + 1) \qquad (\text{Res-f})$$

**Theorem 3.4.** For any wpo $X$, $w(M^r(X)) = \omega^{o_{\perp}(X)}$

**Proof.** See Appendix B. The proof of Theorem 3.4 is quite technical, and relies on the notion of quasi-incomparable subsets. ◀

# 4 Computing the friendly order type

Like the usual ordinal invariants, the fot can be computed compositionally for some basic operations on wpos:

**Proposition 4.1.** For any non empty wpo $A, B$,

1. $o_{\perp}(A + B) = o_{\perp}(A) + o_{\perp}(B)$,

2. $o_{\perp}(A \sqcup B) = 1 + (o(A) - 1) \oplus (o(B) - 1)$,

**Proof.** 1. For any sequences $s_A, s_B$ in $\text{Bad}_{\perp}(A), \text{Bad}_{\perp}(B)$, the concatenation $s_B s_A$ is a sequence of $\text{Bad}_{\perp}(A + B)$. Furthermore, any sequence of $\text{Bad}_{\perp}(A + B)$ is of this form.

2. For any two sequences $s_1, s_2$, let $s_1 \sqcup s_2$ denote the set of sequences obtained through shuffling $s_1, s_2$ together (e.g. $abcad \in aba \sqcup cd$). Let $x_A, x_B$ be two minimal elements of $A$ and $B$. For any sequences $s_A, s_B$ in $\text{Bad}(A \setminus \{x_A\}), \text{Bad}(B \setminus \{x_B\})$, for any $s \in s_A \sqcup s_B$, we know that $s$ and $sx_A$ and $sx_B$ are in $\text{Bad}_{\perp}(A \sqcup B)$. Reciprocally, from any $s \in \text{Bad}_{\perp}(A \sqcup B)$, there is a partition $s_A \in \text{Bad}(A), s_B \in \text{Bad}(B)$ such that $s \in s_A \sqcup s_B$. Furthermore, the natural sum of the ranks of $s_A$ in $\text{Bad}(A)$ and $s_B$ in $\text{Bad}(B)$ is strictly positive. Suppose for contradiction sake that $s_A$ and $s_B$ have rank 0 in $\text{Bad}(A)$ and $\text{Bad}(B)$. Let $s = s'x$. Then $(A \sqcup B)_{\ge s} = \emptyset$ and in particular $x$ has no friend in $(A \sqcup B)_{\ge s'}$. Thus $s \notin \text{Bad}_{\perp}(A \sqcup B)$, contradiction. ◀

<footnote n="1">¹ Can one be friend with one's superior or inferior? No. Your true friends are those you cannot (and do not have to) compare yourselves with.</footnote>
XX:10 Ordinal measures of the set of finite multisets

Observe how friendly order type behaves similarly to mot. It is not unusual to have fot coincides with mot, for instance $o_{\perp}(\omega \sqcup \omega) = o(\omega \sqcup \omega)$ (Proposition 4.1).

To bring this new ordinal invariant closer to familiar grounds, we bound the fot of a wpo X with the mot of a special subset of X, the stripped subset.

**Definition 4.2 (Stripped subset).** The stripped subset of a wpo X, denoted by $\text{str}(X)$, is X without its friendless elements:

$$ \text{str}(X) \stackrel{\text{def}}{=} \{ x \in X : X_{\perp x} \neq \emptyset \}. $$

Since $\text{Bad}_{\perp}(X)$ is a subtree of $\text{Bad}(\text{str}(X))$, we know that $o_{\perp}(X) \le o(\text{str}(X))$. Here is an example where this inequality is strict:

**Example 4.3.** Let $X = \omega \sqcup \{\spadesuit\}$. Here $\text{str}(X) = X$, so $o(\text{str}(X)) = \omega + 1$. However, in $\text{Bad}_{\perp}(X)$, the singleton $\spadesuit$ has rank 0, and the singleton $n$ for any $n \in \omega$ has rank $n$. Therefore $o_{\perp}(X) = \omega < o(\text{str}(X))$.

Let us show that $o(\text{str}(X))$ also appears in a lower bound on $o_{\perp}(X)$, by introducing an alternative characterisation of fot as the mot of a specific subset.

A maximal linearisation is a monotonic function from a wpo X onto $o(X)$.

**Definition 4.4 (Friendly subset).** A subset $X'$ of X is friendly if there exist a maximal linearisation $\ell: X' \to o(X')$ such that for any bad sequence $s = x_1, \dots, x_n$ in $X'$ verifying $\ell(x_1) > \dots > \ell(x_n)$, $s$ is open-ended. We say that $\ell$ witnesses the friendly condition.

Observe that every friendly subset of X is a substructure of $\text{str}(X)$.

For any ordinal $\alpha$, let

$$ \delta(\alpha) \stackrel{\text{def}}{=} \begin{cases} \alpha & \text{if } \alpha \text{ is limit,} \\ \gamma + \lfloor n/2 \rfloor & \text{if } \alpha = \gamma + n \text{ with } \gamma \text{ limit and } n < \omega. \end{cases} $$

**Theorem 4.5 (Alternative characterisation of $o_{\perp}(X)$).** Let X be a wpo. There exists a friendly subset $X'$ of X which maximizes $o(X')$, and $o_{\perp}(X) = o(X')$. Furthermore, $\delta(o(\text{str}(X))) \le o_{\perp}(X) \le o(\text{str}(X))$.

**Proof.** See proof in Appendix C.

**Example 4.6 (Following on Example 3.2).** Remember that $H \stackrel{\text{def}}{=} \sum_{n<\omega} \Gamma_n$. Thus $\text{str}(H) = \sum_{2 \le n < \omega} \Gamma_n$, and $o(\text{str}(H)) = o(H) = \omega$. Consider $X_1 = H+H$ and $X_2 = H+\omega$. Observe that $\text{str}(X_1) = \text{str}(H) + \text{str}(H)$ whereas $\text{str}(X_2) = \text{str}(H)$. Therefore, according to Theorem 4.5, $o_{\perp}(X_1) = \omega \cdot 2$ and $o_{\perp}(X_2) = \omega$.

**Corollary 4.7.** For any wpo X, if $o(X)$ is limit and $o(\text{str}(X)) = o(X)$, then $o_{\perp}(X) = o(X)$.

The conditions in Corollary 4.7 are often satisfied:

**Proposition 4.8.** For any wpo non-empty X, $o_{\perp}(M^{\diamond}(X)) = o(M^{\diamond}(X))$.

**Proof.** Observe that $M^{\diamond}(X) = M^{\diamond}(X) \setminus \{\emptyset\}$. Thus $o(\text{str}(M^{\diamond}(X))) = o(M^{\diamond}(X)) - 1 = o(M^{\diamond}(X))$ (Theorem 1.10). We conclude with Corollary 4.7.
<table><caption>Table 2 Ordinal invariants of the set of finite multisets.</caption><thead><tr><th>Invariants</th><th>Multiset embedding of X</th><th>Multiset ordering of X</th></tr></thead><tbody><tr><td>Mot <i>o</i></td><td>ω<sup>o(X̂)</sup></td><td>ω<sup>o(X)</sup></td></tr><tr><td>Height <i>h</i></td><td><i>h</i><sup>*</sup>(X)</td><td>ω<sup><i>h</i>(X)</sup></td></tr><tr><td>Width <i>w</i></td><td>ω<sup>o(X̂)-1</sup></td><td>ω<sup>o<sub>⊥</sub>(X)</sup></td></tr></tbody></table>

Conclusion

Table 2 sums up this article's contributions (in the gray cases) amidst the former state of the art.

These results are part of a more general research program (see [8, 16]) aimed at measuring more precisely and more effectively the complexity of wpos used in well-structured systems, termination proofs, and other algorithmic applications.

Investigating the friendly order type is a subject for further research: How does it relate to other concepts? Can it be computed compositionally for more operations? Can we define a class of wpos where friendly order type always coincides with mot?

References

1. U. Abraham and R. Bonnet. Hausdorff's theorem for posets that satisfy the finite antichain property. *Fund. Math.*, 159(1):51-69, 1999. doi:10.4064/fm-159-1-51-69.

2. H. J. Altman. Intermediate arithmetic operations on ordinal numbers. *Mathematical Logic Quarterly*, 63(3-4):228-242, 2017. doi:10.1002/malq.201600006.

3. M. Aschenbrenner and Wai Yan Pong. Orderings of monomial ideals. *Fundamenta Mathematicae*, 181(1):27-74, 2004.

4. A. Blass and Y. Gurevich. Program termination and well partial orderings. *ACM Trans. Computational Logic*, 9(3):1-26, 2008. doi:10.1145/1352582.1352586.

5. R. Bonnet, A. Finkel, S. Haddad, and F. Rosa-Velardo. Ordinal theory for expressiveness of well-structured transition systems. *Information and Computation*, 224:1-22, 2013. doi:10.1016/j.ic.2012.11.003.

6. D. H. J. de Jongh and R. Parikh. Well-partial orderings and hierarchies. *Indag. Math.*, 39(3):195-207, 1977. doi:10.1016/1385-7258(77)90067-1.

7. N. Dershowitz and Z. Manna. Proving termination with multiset orderings. *Communications of the ACM*, 22(8):465-476, 1979. doi:10.1145/359138.359142.

8. M. Džamonja, S. Schmitz, and Ph. Schnoebelen. On ordinal invariants in well quasi orders and finite antichain orders. In P. Schuster, M. Seisenberger, and A. Weiermann, editors, *Well Quasi-Orders in Computation, Logic, Language and Reasoning*, volume 53 of *Trends in Logic*, chapter 2, pages 29-54. Springer, Berlin/Heidelberg, Germany, 2020. doi:10.1007/978-3-030-30229-0_2.

9. D. Figueira, S. Figueira, S. Schmitz, and Ph. Schnoebelen. Ackermannian and primitive-recursive bounds with Dickson's lemma. In *Proc. 26th IEEE Symp. Logic in Computer Science (LICS 2011)*, Toronto, Canada, June 2011, pages 269-278. IEEE Comp. Soc. Press, 2011. doi:10.1109/LICS.2011.39.

10. G. Higman. Ordering by divisibility in abstract algebras. *Proc. London Math. Soc.* (3), 2(7):326-336, 1952. doi:10.1112/plms/s3-2.1.326.
XX:12 Ordinal measures of the set of finite multisets

11 I. Kříž and R. Thomas. Ordinal types in Ramsey theory and well-partial-ordering theory. In J. Nešetřil and V. Rödl, editors, Mathematics of Ramsey Theory, volume 5 of Algorithms and Combinatorics, pages 57–95. Springer, Berlin/Heidelberg, Germany, 1990. doi:10.1007/978-3-642-72905-8_7.

408

409

410

411

12 J. B. Kruskal. Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture. Trans. Amer. Math. Soc., 95(2):210–225, 1960. doi:10.2307/1993287.

412

413

13 D. Schmidt. Well-partial orderings and their maximal order types. In P. Schuster, M. Seisenberger, and A. Weiermann, editors, Well Quasi-Orders in Computation, Logic, Language and Reasoning, volume 53 of Trends in Logic, chapter 12, pages 351–391. Springer, 2020. doi:10.1007/978-3-030-30229-0_13.

414

415

416

417

14 S. Schmitz. The parametric complexity of lossy counter machines. In Proc. 46th Int. Coll. Automata, Languages, and Programming (ICALP 2019), Patras, Greece, July 2019, volume 132 of Leibniz International Proceedings in Informatics, pages 129:1–129:15, Dagstuhl, Germany, 2019. Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2019.129.

418

419

420

421

15 J. Van der Meeren, M. Rathjen, and A. Weiermann. Well-partial-orderings and the big Veblen number. Archive for Mathematical Logic, 54(1-2):193–230, 2015. doi:10.1007/s00153-014-0408-5.

422

423

424

16 I. Vialard. On the cartesian product of well-orderings. arXiv:2202.07487 [cs.LO], February 2022. Submitted for publication. URL: http://arxiv.org/abs/2202.07487.

425

426

17 A. Weiermann. Proving termination for term rewriting systems. In Proc. 5th Workshop on Computer Science Logic (CSL '91), Berne, Switzerland, Oct. 1991, volume 626 of Lecture Notes in Computer Science, pages 419–428. Springer, 1991. doi:10.1007/BFb0023786.

427

428

429

18 A. Weiermann. A computation of the maximal order type of the term ordering on finite multisets. In Proc. 5th Conf. Computability in Europe (CiE 2009), Heidelberg, Germany, July 2009, volume 5635 of Lecture Notes in Computer Science, pages 488–498. Springer, 2009. doi:10.1007/978-3-642-03073-4_50.

430

431

432

433

A Proof of Theorem 3.1

434

We write $m \stackrel{\not m}{\le} r m'$ (resp. $m \stackrel{\not m}{<} m'$, $m \stackrel{\not m}{\perp} m'$) when $m \cap m' \ne \emptyset$ and $m \le_r m'$ (resp $m < m'$, $m \perp m'$). With these new notations, the multiset ordering can be reformulated as follows

435

436

► **Definition A.1 (Multiset ordering (reformulated))**. $M^r(X) = (M(X), \le_r)$ is ordered with the multiset ordering: $m \le_r m'$ iff there exists $m_1, m_1', m_2$ such that $m = m_1 \cup m_2$, $m' = m_1' \cup m_2$, and $m_1 \stackrel{\not m_1'}{<} m_2'$.

437

438

439

► **Lemma A.2.** Let $A = \cup_{i \le n} A_i$ a set partitioned in $n$ subsets, for some $n \in \mathbb{N}$. Let $\le_A$ a well-partial ordering on $A$, and $\le_{A_i}$ the same ordering restricted to the subset $A_i$ for $i \le n$. Then

$$h(A, \le_A) \le \bigoplus_{i \le n} h(A_i, \le_{A_i}).$$

440

441

442

**Proof.** From any decreasing sequence $s$ on $A$, one can extract a decreasing sequence $s_i$ by restricting $s$ to $A_i$ for any $i \le n$. By induction on the rank of $s$ in $Dec(A)$, one shows that $rk(s) \le \bigoplus_{i \le n} rk(s_i)$. ◀

<figure><img src="image_3.png" /></figure>

Proof of Theorem 3.1. We prove the upper bound by induction on $h(X)$. If $h(X) = 0$ then $X = \emptyset$ and $h(M^r(\emptyset)) = 1 = \omega^0$.

443

444
Suppose that $X$ is not empty. For any non-empty multiset $m \in M^r(X)$, the residual $M^r(X)_{<m}$ can be partitioned as follows:

445

446

447

448

$$M^r(X)_{<m} = \bigcup_{m_1+m_2=m, m_1 \neq \emptyset} \{m' + m_2 : m' \stackrel{\emptyset}{<} m_1\}.$$

449

450

451

452

Note that this union is a partition of the support of $M^r(X)_{<m}$, it does not say anything on the order between the elements of the subsets in the union.

For any non-empty multiset $m$, we define $S_m \stackrel{\text{def}}{=} (\cap_{x \in m} X_{\ge x}) \cap (\cup_{x \in m} X_{<x})$ a subset of $X$. Thus for any multiset $m'$ in $M^r(X)$, $m' \stackrel{\emptyset}{<} m$ iff $m' \in M^r(S_m)$. Therefore:

453

454

$$M^r(X)_{<m} = \bigcup_{m_1+m_2=m, m_1 \neq \emptyset} \{m' + m_2 : m' \in M^r(S_{m_1})\}.$$

Observe that $h(S_{m_1}) < h(X)$ by definition of $S_{m_1}$. Hence by induction hypothesis $h(M^r(S_{m_1})) \le \omega^{h(S_{m_1})} < \omega^{h(X)}$. Moreover, $\omega^{h(X)}$ is indecomposable. Hence according to Lemma A.2:

455

$$h(M^r(X)_{<m}) \le \bigoplus_{m_1+m_2=m, m_1 \neq \emptyset} h(M^r(\cup_{x \in m_1} X_{<x})) < \omega^{h(X)}.$$

Therefore $h(M^r(X)) \le \omega^{h(X)}$ according to Equation (Res-h).

◀

## B Proof of Theorem 3.4

456

First we prove intermediary lower and upper bounds on the width of the multiset ordering.

457

► Lemma B.1. Let $X$ be a wpo. Then

$$\mathbf{w}(M^r(X)) \ge \sup_{x \in X, n < \omega} \mathbf{w}(M^r(X)_{\perp\langle x \rangle}) \cdot n + 1$$

458

459

460

461

**Proof.** This proof follows the same structure as the proof of Lemma 2.3: We study the residual of $M^r(X)$ which contains every element incomparable to some multiset of the form $\langle x \rangle \times n$, and slice this residual into a family of quasi-incomparable subsets.

According to Equation (Res-w),

462

463

464

$$\begin{aligned} w(M^r(X)) &= \sup_{m \in M^r(X)} \mathbf{w}(M^r(X)_{\perp m}) + 1 \\ &\ge \sup_{x \in X, n < \omega} \mathbf{w}(M^r(X)_{\perp \langle x \rangle \times n}) + 1. \end{aligned}$$

465

466

467

468

For all $k \in [1, n]$, let $M_k = \{ \langle x \rangle \times (n-k) \cup m : m \in M^r(X)_{\perp\langle x \rangle} \}$. Observe that $M_k \equiv M^r(X)_{\perp\langle x \rangle}$ for any $k \in [1, n]$, and for all $m \in M_k$, $m \perp \langle x \rangle \times n$. We claim that $(M_k)_{k \in [1, n]}$ is a quasi-incomparable family of subsets of $M^r(X)_{\perp\langle x \rangle \times n}$: Let $i < n$ and $Y$ a finite subset of $M_1 \cup \dots \cup M_i$. We define $m_Y$ and $M'_{i+1}$ as

469

$$m_Y \stackrel{\text{def}}{=} \bigcup_{j \le i} \bigcup_{m \in (M_j \cap Y)} (m \setminus (\langle x \rangle \times (n-j))),$$

470

$$M'_{i+1} \stackrel{\text{def}}{=} \{ \langle x \rangle \times (n - i - 1) \cup m_Y \cup m : m \in M^r(X)_{\perp \langle x \rangle} \}.$$

471

Observe that $M'_{i+1}$ is an isomorphic subset of $M_{i+1}$, and $Y \perp M'_{i+1}$.

472

Therefore according to Lemma 1.14, $\mathbf{w}(M^r(X)_{\perp\langle x \rangle \times n}) \ge \mathbf{w}(M^r(X)_{\perp\langle x \rangle}) \cdot n$. ▶

◀
XX:14 Ordinal measures of the set of finite multisets

► Lemma B.2. Let $X$ be a wpo. Then

$$ w(M^r(X)) \leq \sup_{x \in X, n < \omega} w(M^r(X)_{\perp\langle x \rangle}) \otimes n + 1 $$

474 **Proof.** By definition, for any multisets $m, m' \in M^r(X)$, $m \perp m'$ means that $m \neq m'$ and there exists $m_1, m'_1, m_2$ such that $m = m_1 \cup m_2$, $m' = m'_1 \cup m_2$ and $m_1 \perp m'_1$.

475 Therefore, the residual $M^r(X)_{\perp m}$ can be partitioned as an augmentation of a disjoint union:

$$ M^r(X)_{\perp m} \geq_{\text{aug}} \bigsqcup_{m_1+m_2=m, m_1 \neq \emptyset} \{ m'_1 + m_2 : m' \in M^r(X), m'_1 \perp m_1 \}, $$

478 which can be reformulated into

$$ M^r(X)_{\perp m} \geq_{\text{aug}} \bigsqcup_{m_1 \subseteq m, m_1 \neq \emptyset} M^r(X)_{\perp m_1} $$

479 where $M^r(X)_{\perp m_1}$ is the residual $\{ m' \in M^r(X) : m' \perp m_1 \}$.

480 Let us observe this residual: $m' \perp m_1$ means that $m'$ and $m_1$ are disjoint and there exists $x \in m_1$ such that for all $y' \in m'$, $x \not\perp y'$, and there exists $x' \in m'$ such that for all $y \in m_1$, $x' \not\perp y$. In particular $x' \not\perp x$. Hence $m' \perp m_1$ implies there exists $x \in m_1$ such that $\langle x \rangle \perp m'$, which is equivalent to $\langle x \rangle \perp m'$. Therefore the support of $M^r(X)_{\perp m_1}$ is included in a union on $x \in m_1$ of residuals $M^r(X)_{\perp \langle x \rangle}$. With an augmentation we get a disjoint union:

$$ M^r(X)_{\perp m_1} \leq_{\text{st}} \geq_{\text{aug}} \bigsqcup_{x \in m_1} M^r(X)_{\perp \langle x \rangle} $$

$$ \text{Hence according to Table 1, } M^r(X)_{\perp m} \leq \bigoplus_{m_1 \subseteq m, m_1 \neq \emptyset} \bigoplus_{x \in m_1} w(M^r(X)_{\perp \langle x \rangle}) . $$

Let $x \in m$ such that $w(M^r(X)_{\perp \langle x \rangle})$ is maximal. Then $w(M^r(X)_{\perp m}) \leq w(M^r(X)_{\perp \langle x \rangle}) \otimes n$ for some $n < \omega$. Hence according to Equation (Res-w),

$$ w(M^r(X)) = \sup_{m \in M^r(X)} w(M^r(X)_{\perp m}) + 1 \leq \sup_{x \in X, n < \omega} w(M^r(X)_{\perp \langle x \rangle}) \otimes n + 1. \quad \blacksquare $$

485 The bounds provided in Lemmas B.1 and B.2 actually match. Furthermore, they can be reformulated in such a way that the residual on $M^r(X)$ boils down to a residual on $X$:

487 ► Lemma B.3. For any non-linear wpo $X$,

488 $w(M^r(X)) = \sup\{ w(M^r(X_{\geq x})) \cdot \omega : x \in X, X_{\perp x} \neq \emptyset \}$. \qquad (W)

489 **Proof.** For any ordinal $\alpha$, $\sup_{n<\omega}(\alpha \cdot n + 1) = \sup_{n<\omega}(\alpha \otimes n + 1) = \alpha \cdot \omega$. Hence according to Lemmas B.1 and B.2, $w(M^r(X)) = \sup_{x \in X}(w(M^r(X)_{\perp \langle x \rangle}) \cdot \omega)$.

490 Let $x \in X$. If $X_{\perp x} = \emptyset$, then $M^r(X)_{\perp \langle x \rangle} = \emptyset$. Otherwise let $y \in X_{\perp x}$. Observe that, for any $m \in M^r(X_{\geq x})$, $m \cup \langle y \rangle \perp \langle x \rangle$. Hence

$$ \{ \langle y \rangle \cup m : m \in M^r(X_{\geq x}) \} \leq_{\text{st}} M^r(X)_{\perp \langle x \rangle} \leq_{\text{st}} M^r(X_{\geq x}) . $$

491 Therefore $w(M^r(X)_{\perp \langle x \rangle}) = w(M^r(X_{\geq x}))$ if $X_{\perp x} \neq \emptyset$, otherwise $w(M^r(X)_{\perp \langle x \rangle}) = 0$. ◀
**Proof of Theorem 3.4.** If $X$ is linear, $\text{Bad}_{\perp}(X)$ only contains the empty sequence, hence $\mathbf{o}_{\perp}(X) = 0$ and $\mathbf{w}(\text{Mulr}(X) = 1$. Otherwise, observe that Equation (W) is quite similar to Equation (Res-f) in its structure. Thus $\mathbf{w}(M^r(X)) = \omega^{\mathbf{o}_{\perp}(X)}$ follows directly from Equation (W).

### C Proof of Theorem 4.5

**► Lemma C.1.** For any wpo $X$, for any maximal linearisation $\ell : \text{str}(X) \to \mathbf{o}(\text{str}(X))$, there exists a friendly subset $X'$ such that $\ell$ restricted to $X'$ verifies the friendly condition, and $\mathbf{o}(X') \ge \delta(\mathbf{o}(\text{str}(X)))$.

**Proof.** We claim that for any $\beta \le \mathbf{o}(\text{str}(X))$, there exists $X_{\beta} \subseteq \ell^{-1}(\{ \gamma : \gamma < \beta \})$ a friendly subset of $X$ where $\ell$ restricted to $X_{\beta}$ verifies the friendly condition, such that $\mathbf{o}(X_{\beta}) \ge \delta(\beta)$. In this proof, when we say that a subset is friendly, it is always implied that $\ell$ restricted to this subset witnesses the friendly condition.

We build the subsets $(X_{\beta})_{\beta \le \mathbf{o}(\text{str}(X))}$ as follows:

- $X_0 = \emptyset$,

- For $\gamma$ limit, $X_{\gamma} = \bigcup_{\beta < \gamma} X_{\beta}$,

- For any $\beta$, $X_{\beta+1} = X_{\beta} \cup \ell^{-1}(\beta)$ if friendly, otherwise $X_{\beta+1} = X_{\beta}$.

First observe that $X_{\beta}$ is friendly for any $\beta \le \mathbf{o}(\text{str}(X))$. Indeed, $X_0$ is friendly, and since for any $\beta < \beta'$, $X_{\beta} \subseteq X_{\beta'}$, then the union $\bigcup_{\beta < \gamma} X_{\beta}$ for $\gamma$ limit is friendly by induction.

Let us prove the claim $\mathbf{o}(X_{\beta}) \ge \delta(\beta)$, by showing that for any $\beta + 2 \le \mathbf{o}(\text{str}(X))$, we have $\mathbf{o}(X_{\beta+2}) > \mathbf{o}(X_{\beta})$. Let $x = \ell^{-1}(\beta')$ and $x' = \ell^{-1}(\beta' + 1)$. Assume for the sake of contradiction that $X_{\beta+2} = X_{\beta}$. This means that neither $X_{\beta} \cup \{x\}$ nor $X_{\beta} \cup \{x'\}$ are friendly. Hence there exists $y, y' \in X_{\beta}$ such that for any $z \in X$, we have $z \perp y \implies z \ge x$ and $z \perp y' \implies z \ge x$. Now because of $\ell$ we know that $x \not\ge x'$ and $y, y' \not\ge x, x'$. Since $y, y' \in \text{str}(X)$, then $X_{\perp y}$ and $X_{\perp y'}$ are both non-empty, so actually $x \perp y$ and $x' \perp y'$. And since $x \not\ge x'$, we know $y' < x$. Therefore $x \perp x'$, hence $y < x'$. Which leads to a contradiction on the relationship between $y$ and $y'$.

For any friendly subset $X'$, $\mathbf{o}(X') \le \mathbf{o}(\text{str}(X))$, and there exist $X'$ such that $\mathbf{o}(X') \ge \delta(\mathbf{o}(\text{str}(X)))$. Therefore there exists a friendly subset $X'$ which maximizes $\mathbf{o}(X')$.

**Proof of Theorem 4.5.** We say that a bad sequence $x_1, \dots, x_n$ respects a maximal linearisation $\ell$ when $\ell(x_1) > \dots > \ell(x_n)$. Let $X'$ be a friendly subset of $X$ and $\ell$ a maximal linearisation of $X'$ that verifies the friendly condition. Observe that $\text{Bad}(X')$ restricted to sequences that respect $\ell$ has for rank $\mathbf{o}(X')$, and is embedded in $\text{Bad}_{\perp}(X)$. Hence $\mathbf{o}_{\perp}(X) \ge \mathbf{o}(X')$.

We prove the upper bound by induction on $\mathbf{o}_{\perp}(X)$. If $\mathbf{o}_{\perp}(X) = 0$ then the only friendly subset of $X$ is the empty set. Now suppose that $\mathbf{o}_{\perp}(X) > 0$. For any $x \in \text{str}(X)$, by induction hypothesis on $X_{\not\ge x}$, there exists a friendly subset $X'$ of $X_{\not\ge x}$, with a maximal linearisation $\ell$ which verifies the friendly condition, such that $\mathbf{o}(X') \ge \mathbf{o}_{\perp}(X_{\not\ge x})$. We extend $\ell$ to the subset $X' \cup \{x\}$ of $X$, such that $\ell(x) = \mathbf{o}(X')$. Now $\ell$ is a maximal linearisation of $X' \cup \{x\}$ which verifies the friendly condition, therefore $\mathbf{o}(X' \cup \{x\})$ is a friendly subset of $X$ and $\mathbf{o}(X' \cup \{x\}) > \mathbf{o}_{\perp}(X_{\not\ge x})$. Let $X'$ be a friendly subset of $X$ which maximizes $\mathbf{o}(X')$. Then for any $x \in \text{str}(X)$, $\mathbf{o}_{\perp}(X_{\not\ge x}) < \mathbf{o}(X')$. Therefore $\mathbf{o}_{\perp}(X) \le \mathbf{o}(X')$ according to Equation (Res-f).