# On the width of the cartesian product of ordinals

Isa Vialard

► To cite this version:

Isa Vialard. On the width of the cartesian product of ordinals. 2023. hal-04287427

HAL Id: hal-04287427

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

Preprint 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
# On the width of the cartesian product of ordinals

Isa Vialard

*LMF, Université Paris-Saclay, ENS Paris-Saclay, CNRS, Gif-sur-Yvette, France.

Corresponding author(s). E-mail(s): isavialard@free.fr;

## Abstract

The ordinal invariants, i.e., maximal order type, height, and width, are measures of a well quasi-ordering (wqo) based on the ordinal rank of the trees of its bad sequences, strictly decreasing sequences, and antichain sequences, respectively. Complex wqos are often built from simpler wqos through basic constructions such as disjoint sum, direct sum, cartesian product, and higher-order constructions like powerset or sequences. One main challenge is to compute the ordinal invariants of such wqos compositionally. This article focuses on the width of the cartesian product of wqos, for which no general formula is known. The particular case of the cartesian product of two ordinals has already been solved (Abraham, Order 4, 1987). We generalize this study and compute the width of the cartesian product of finitely many ordinals. To this end, we develop new tools for proving lower bounds on the width of wqos. Finally, we leverage our main result to compute the width of a generic family of elementary wqos that is closed under cartesian product.

**Keywords:** Width of wqos, Ordinal invariants, Antichain rank, Cartesian product of wqos

## Statements and Declarations

* Funding: This work was supported by ANR project BRAVAS (grant ANR-17-CE40-0028) and the École Polytechnique AMX program.
2 *On the width of the cartesian product of ordinals*

* Competing interests: The author has no relevant financial or non-financial interests to disclose.

* Availability of data and materials: Our manuscript contains no associated data.

* Code availability: Our manuscript contains no associated code.

# 1 Introduction

For a finite poset, and more generally a finite quasi-order (qo), there are intuitive notions of dimension that play a paramount role in combinatorics and algorithmics: the cardinal of the qo, but also its height (the cardinal of its longest chain) and its width (the cardinal of its longest antichain, i.e., subset of pairwise incomparable elements).

With some provisions, these invariants can be extended to infinite posets: If a qo is *well-founded* (or WF), we define its *ordinal height* as the rank of the tree of strictly decreasing sequences. If a qo is FAC (it only has finite antichains), we define its *ordinal width* as the rank of the trees of antichain sequences, i.e, sequences of pairwise incomparable elements. If a qo is both WF and FAC, then it is called a *well quasi-order* (wqo)[1]. Equivalently, a wqo is a qo that has no infinite bad sequence (a sequence $(x_i)_i$ is bad if for all $i < j$, $x_i \not\le x_j$). A wqo has a height, a width, and also a maximal order type [2], defined as the rank of the trees of bad sequences. Wqos can alternatively be defined as posets that do not have infinite bad sequences.

There is a rich theory of wqos [3, 4], where these *ordinal invariants* are used to measure complexity. De Jongh and Parikh [2] and Schmidt [5] initiated the study of maximal order type, for use in proof theory. Kříž and Thomas [6] later introduced ordinal width for infinitary combinatorics. Abraham and Bonnet [7] computed ordinal height and width for several constructions such as cartesian and direct products. Blass and Gurevich [8] then contributed to the study of ordinal invariants for program verification. Maximal order type was also used in [9] for expressiveness results.

In the study of *well-structured transition systems* (WSTS), i.e., computational systems whose set of configurations is a wqo and whose transitions are monotonic with respect to the order, some upper bound results on complexity rely on the length of controlled bad sequences of configurations [10, 11]), which in turn depends on the maximal order type of the underlying wqo. Schmitz refined this technique with controlled antichains whose length depends on width instead [12].

A recent survey article by Džamonja et al. [13] shows that we do not always know how to compute the width of wqos, even in the apparently simple case of a cartesian product. This gap is unfortunate since the cartesian product is the most common and basic data structure in computer science. However, the special case of the width of the cartesian product of two linear well-founded orders, i.e., two ordinals, was solved by Abraham [14].
This article extends [14] by computing the width of the cartesian product of
$n$ ordinals, for any $n < \omega$. As explained in Section 2.6, the method of residuals
relies on specifics of the case $n = 2$, which are lost in case $n = 3$ and beyond.
Our method consequently develops new tools to provide refined lower bounds
on ordinal width.

**1.1 Outline of the article**

Section 2 introduces definitions, notations and recalls known results, mostly
following [13, 14]. Section 3 introduces the notion of quasi-incomparability
(Definition 3.1) and proves lower bound results for the ordinal width of wqos
(Lemmas 3.2 and 3.6, Corollary 3.10).

Section 4 gradually progresses toward our main result, computing the width of the cartesian products of several ordinals: In Theorem 4.3 we give the width of the product of indecomposable ordinals. With Theorem 4.6 we build from this result to compute the width of the product of infinite ordinals. Section 4.3 extends this result by adding finite ordinals to the product. For completeness, Section 4.4 recalls a classical result for the cartesian product of finite ordinals.

In Section 5 we leverage our main result to find a sufficient condition for
which the width of the cartesian product of ordinals reaches its maximal order
type (Theorem 5.2). We then use it to compute the width of the cartesian
product of a family of well-behaved wqos, obtained through basic operations
on ordinals, called *elementary wqos* (Definition 5.3).

**2 Measuring well quasi-orders**

**2.1 Ordinal invariants**

For any wqo ($A, \le_A$) (we write just $A$ when the ordering relation is under-
stood), $\mathit{Inco}(A)$ (resp. $\mathit{Dec}(A)$ and $\mathit{Bad}(A)$) is the tree of antichain sequences
(rsp. strictly decreasing sequences, bad sequences) of $A$ ordered by inverse
prefix order ([6]): the empty sequence is the root, and if $s$ is the maximal strict
prefix of $t$, then $t$ is a *child* of* $s$.

Observe that, since $A$ is a wqo (hence FAC and WF), the trees $\mathit{Inco}(A)$, $\mathit{Dec}(A)$ and $\mathit{Bad}(A)$ do not have infinite branches: they are well-founded.
However, they can be infinitely branching.

Classically, one ascribes an *ordinal rank* to any node of a well-founded tree
*T* from leaves to root. Let *s* ∈ *T* be a node: if *s* is maximal, then *r*(*s*) def= 0.
otherwise *r*(*s*) def= sup{*r*(*t*) + 1 | *t* is a child of* *s*}. Since *T* can be infinitely
branching, *r*(*s*) is an ordinal. The rank of *T* is defined as the rank of its root.

**Definition 2.1.** The *width* $w(A)$, the *height* $h(A)$, and the *maximal order type* $o(A)$ of a wqo $A$ are the ranks of $\mathit{Inco}(A)$, $\mathit{Dec}(A)$, and $\mathit{Bad}(A)$, respectively. Together, they are called the *ordinal invariants* of $A$.
4 On the width of the cartesian product of ordinals

**Example 2.2.** For any ordinal $\alpha > 0$, $o(\alpha) = h(\alpha) = \alpha$, and $w(\alpha) = 1$.

**Example 2.3.** For any $n < \omega$, let $\Gamma_n$ denote a set of $n$ incomparable elements.
Then $o(\Gamma_n) = w(\Gamma_n) = n$, and $h(\Gamma_n) = 1$.

Since antichain sequences and strictly decreasing sequences are bad sequences, $\text{Inco}(A)$ and $\text{Dec}(A)$ are substructures of $\text{Bad}(A)$. Hence:

**Lemma 2.4.** For all wqo $A$, $w(A) \leq o(A)$ and $h(A) \leq o(A)$.

A linearisation of a quasi-order ($A, \leq$) is a linear quasi-order ($A, \preceq$) with
same support such that for any elements $x, y \in A$, $x \leq y \implies x \preceq y$, and
$x < y \implies x < y$.

**Remark 2.5.** Maximal order type $o(A)$ was historically defined as the order type of a maximal linearisation of a wqo $A$ ([2]). Height $h(A)$ can similarly be defined as the order type of a maximal chain of $A$ [15]. However width cannot be defined as the order type of a maximal antichain sequence. Fortunately Definition 2.1 provides us with an homogeneous definition for all three invariants.

**2.2 On ordinal arithmetic**

We suppose well-known the notions of sum and product on ordinals (see any
textbook like [16] for a fully detailed introduction). However, let us recall
succinctly some definitions and properties that might be less familiar to the
reader.

**Definition 2.6 (Cantor normal form).** Any ordinal $\alpha$ can be expressed in *Cantor normal form*, or CNF, as $\alpha = \sum_{i<n} \omega^{\alpha_i}$, where $\alpha_0 \ge \alpha_1 \ge \cdots \ge \alpha_{n-1}$ are the *exponents* of $\alpha$. This expression is unique.

**Definition 2.7 (Ordinal operations).** For any ordinals $\alpha, \beta$ with $\alpha = \sum_{i<n} \omega^{\alpha_i}$ and $\beta = \sum_{i<m} \omega^{\beta_i}$ in CNF,

* The natural sum $\alpha \oplus \beta$ is $\gamma = \sum_{i<n+m} \omega^{\gamma_i}$ with $\gamma_0 \ge \cdots \ge \gamma_{n+m-1}$ being a reordering of $\alpha_0, \dots, \alpha_{n-1}, \beta_0, \dots, \beta_{m-1}$.

* The natural product $\alpha \otimes \beta$ is $\bigoplus_{i<n,j<m} \omega^{\alpha_i \otimes \beta_j}$.

* If $\beta \le \alpha$, then the subtraction $\alpha - \beta$ is the unique ordinal $\gamma$ such that $\beta + \gamma = \alpha$.

Let us recall that an ordinal $\alpha$ is *indecomposable* when for all $\beta, \delta < \alpha$, we have $\beta + \delta < \alpha$. Equivalently, indecomposable ordinals are ordinals of the form $\omega^\beta$ with $\beta$ any ordinal.

**Proposition 2.8 (Properties of ordinal operations).** For any ordinals $\alpha, \alpha', \beta, \beta'$ with CNF $\alpha = \sum_{i<n} \omega^{\alpha_i} > 0$ and $\beta = \sum_{i<m} \omega^{\beta_i} > 0$,
1. $\beta + \alpha = \alpha \text{ iff } \alpha_0 > \beta_0$. In particular, $1 + \alpha = \alpha \text{ iff } \alpha \text{ is infinite.}$

2. If $\alpha \ge \beta$ then $\alpha - \beta = \alpha \text{ iff } \alpha_0 > \beta_0$. In particular, $\alpha - 1 = \alpha \text{ iff } \alpha \text{ is infinite.}$

3. $\alpha + \beta \le \alpha \oplus \beta$.

4. $\alpha + \beta = \alpha \oplus \beta \text{ iff } \alpha_n \ge \beta_0$. In particular, $\alpha + n = \alpha \oplus n \text{ for any } n < \omega$.

5. $\alpha \cdot \beta \le \alpha \otimes \beta$.

6. If $\alpha$ is indecomposable and $\beta < \omega^\omega$, then $\alpha \cdot \beta = \alpha \otimes \beta$.

7. $\alpha \oplus \beta < \alpha' \oplus \beta'$ if $(\alpha, \beta) < (\alpha', \beta')$ component-wise.

8. $\alpha \otimes \beta < \alpha' \otimes \beta'$ if $(\alpha, \beta) < (\alpha', \beta')$ component-wise.

9. If $\beta \le \alpha < \alpha'$ then $\alpha - \beta < \alpha' - \beta$.

## 2.3 Combining wqos

Wqos are often obtained through operations on smaller wqos.

For any wqos $A, B$, the disjoint sum, denoted with $A \sqcup B$, is defined as the order $\leq_{\sqcup}$ on the disjoint union of $A$ and $B$ such that for all $x, y \in A \cup B$, $x \leq_{\sqcup} y$ iff $x \leq_A y$ or $x \leq_B y$.

The direct sum $\Sigma_{i<\alpha} A_i$ along an ordinal $\alpha$ is the order $\leq_+$ on the disjoint union of a family of wqos $(A_i)_{i<\alpha}$ such that for any $i, j < \alpha$ for any $x \in A_i, y \in A_j, x \leq_+ y$ iff $i < j$ or $i = j \wedge x \leq_{A_i} y$. If $\alpha = 2$ then $\Sigma_{i<\alpha} A_i$ can be written $A_0 + A_1$.

The cartesian product $A \times B$ is ordered component-wise: for all $x_A, y_A \in A$ and $x_B, y_B \in B$, $(x_A, x_B) \leq_\times (y_A, y_B)$ iff $x_A \leq_A y_A$ and $x_B \leq_B y_B$.

Finally, $A^*$ denotes the star operation, i.e., the set of finite sequences of $A$ ordered with the embedding order: For any finite words $u = u_1 \dots u_n$ and $v = v_1, \dots, v_m$, $u \leq_{A^*} v$ iff there is an injective function $f: [1, n] \to [1, m]$ such that for all $i \in [1, n]$, $u_i \leq_A v_{f(i)}$.

It is useful to be able to compute ordinal invariants compositionally. The state of the art on such invariants computation can be found in [13]: we recall in Table 1 the results that will be useful for us, using abbreviated notations defined in Fig. 1.

<table><caption>**Table 1** How to compute ordinal invariants compositionally, [13].</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*, A &ne; &empty;</td><td>&omega;<sup>&omega;(o(A)<sup>&pm;</sup>)</sup></td><td>h<sup>*</sup>(A)</td><td>o(A*) if o(A) > 2</td></tr></tbody></table>

Observe that in Table 1 the ordinal invariants of a wqo are given as a function of the invariants of its sub-expressions. However, the width of a cartesian
6 On the width of the cartesian product of ordinals

<caption>Fig. 1 Definition of the notations used in Table 1.</caption>

$$ \alpha \oplus \beta \stackrel{\text{def}}{=} \sup\{ \alpha' \oplus \beta' \mid \alpha' < \alpha, \beta' < \beta \} $$

$$ \alpha^{\pm} \stackrel{\text{def}}{=} \begin{cases} \alpha - 1 & \text{if } \alpha \text{ is finite,} \\ \alpha + 1 & \text{if } \alpha = \epsilon + n \text{ with } \omega^{\epsilon} = \epsilon \text{ and } n < \omega, \\ \alpha & \text{otherwise.} \end{cases} $$

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

product $A \times B$ cannot be expressed as a function of the invariants of A and B, as embodied by the following example.

**Example 2.9.** Let $H \stackrel{\text{def}}{=} \sum_{n<\omega} \Gamma_n$, $A_1 \stackrel{\text{def}}{=} H + \omega$ and $A_2 \stackrel{\text{def}}{=} H + H$. Thus $A_1$ and $A_2$ have the same ordinal invariants. However $w(A_1 \times \omega) \ne w(A_2 \times \omega)$.

We will come back on this example at the end of Section 3 as we do not have the tools yet to efficiently compute ordinal invariants.

## 2.4 Comparing wqos

When computing ordinal invariants, we frequently want to compare a wqo with a simpler one. There are standard notions that we can use:

**Definition 2.10.** Let $(A, \le_A), (B, \le_B)$ be two wqos.

A is an augmentation of B if the carrier sets A, B are equal and $\le_B \subseteq \le_A$. We denote this by $A \ge_{\text{aug}} B$.

A is a substructure of B if the carrier set A is a subset of B and $\le_A$ is $\le_B$ restricted to A. We denote this by $A \le_{\text{st}} B$.

We use the notation $A \equiv B$ when $(A, \le_A)$ is isomorphic to $(B, \le_B)$, i.e., when there is a bijection between A and B that preserves the order. We often abuse terminology and say that A is a substructure (resp. an augmentation) when A is isomorphic to a substructure (resp. an augmentation).

**Example 2.11.** For any ordinals $\alpha \le \beta$, $\alpha \le_{\text{st}} \beta$.

**Example 2.12.** For any ordinal $n < \omega$, $\Gamma_n \le_{\text{aug}} n$.

**Example 2.13.** For any wqos A, B, $A \sqcup B \le_{\text{aug}} A + B$.

The following lemma is a direct consequence of Remark 2.5:
**Lemma 2.14.** For any wpo A, the height and m.o.t. of A are the largest ordinals $\alpha, \beta$ such that such that $\alpha \le_{st} A$ and $\beta \ge_{aug} A$.

These notions are very useful in order to find bounds on ordinal invariants:

**Lemma 2.15.** For all wqos A, B,

* If $A \le_{st} B$, then $f(A) \le f(B)$ for $f = w, o, h$.

* If $A \ge_{aug} B$, then $f(A) \le f(B)$ for $f = w, o$.

*Proof* If $A \le_{st} B$, then $Inco(A), Dec(A)$, and $Bad(A)$ are subtrees of $Inco(B), Dec(B)$, and $Bad(B)$, respectively. Similarly, if $A \ge_{aug} B$, then all antichains or bad sequences of A are antichains or bad sequences of B. $\square$

Notice that the disjoint and direct sums, the cartesian and direct products, and the star operation are monotonic with respect to both substructures and augmentations.

## 2.5 Residual Characterization

For any quasi-order $A$, $x \in A$, and a relation symbol $* \in \{\perp, <, >, \leq, \geq\}$, we define the $*-\text{residual of } A$ at $x$ as

$$A_{*x} \stackrel{\text{def}}{=} \{y \in A : y * x\},$$

seen as a substructure or a subset of A depending on context. We generalize this notion to subsets $Y \subseteq A$:

$$A_{*Y} \stackrel{\text{def}}{=} \bigcap_{x \in Y} A_{*x}.$$

If $Y = \emptyset$, let $A_{*Y} \stackrel{\text{def}}{=} A$.

If A is a wqo, then its residuals are wqos too. Their ordinal invariants are smaller than or equal to the invariants of A (see Lemma 2.15).

Residuals are essential in the computation of ordinal invariants, given:

$$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})$$

These formulas can be seen as a reformulation of Definition 2.1. We can use them to inductively compute the ordinal invariants of A: this is called the *method of residuals*.
8 On the width of the cartesian product of ordinals

## 2.6 Cartesian product of two ordinals

Abraham ([14]) used the method of residuals to compute the width of the cartesian product of two ordinals. Extending this result is what motivated this article. Let us recall the main steps of his proof:

Let $\alpha, \beta$ be two ordinals. According to Eq. (Res-w),

$$w(\alpha \times \beta) = \sup_{(x_1, x_2) \in \alpha \times \beta} \left( w((\alpha \times \beta)_{\perp(x_1, x_2)}) + 1 \right) . \quad (1)$$

Fix $(x_1, x_2) \in \alpha \times \beta$. Then for any $(y_1, y_2) \in \alpha \times \beta$, $(x_1, x_2) \perp (y_1, y_2)$ if and only if $x_1 < y_1$ and $x_2 > y_2$, or $x_1 > y_1$ and $x_2 < y_2$. In Fig. 2, the ordinals $\alpha$ and $\beta$ are represented through vertical lines, and an element $(x_1, x_2)$ of the cartesian product as a segment from $x_1$ to $x_2$. Thus, elements incomparable to $(x_1, x_2)$ correspond to segments intersecting $(x_1, x_2)$.

Thus the residual $(\alpha \times \beta)_{\perp(x_1, x_2)}$ is a disjoint union:

$$(\alpha \times \beta)_{\perp(x_1, x_2)} \equiv \alpha_{<x_1} \times \beta_{>x_2} \sqcup \alpha_{>x_1} \times \beta_{<x_2}.$$

<figure><img src="image_2.png" /><figcaption>**Fig. 2** Residual of $\alpha \times \beta$ at $(x_1, x_2)$ as a disjoint union.</figcaption></figure>

Observe that $\alpha_{<x_1}$ is isomorphic to $x_1$, and $\alpha_{>x_1}$ to $\alpha - (x_1 + 1)$. The same reasoning applies to $\beta_{<x_2}$ and $\beta_{>x_2}$. Using Table 1 we rewrite Eq. (1) as:

$$w(\alpha \times \beta) = \sup_{\substack{x_1 < \alpha \\ x_2 < \beta}} \left( w(x_1 \times (\beta - x_2)) \oplus w((\alpha - x_1) \times x_2) + 1 \right).$$

This equality leads us by induction to the main result of [14] (slightly transformed here as to express in one formula what was given as separate results for different cases):

**Theorem 2.16** (Lemma 3.2 and Theorem 3.4 of [14]). For any infinite ordinals $\alpha = \omega^{\alpha_0} \cdot a + \rho$ and $\beta = \omega^{\beta_0} \cdot b + \sigma$, where $\alpha_0, \rho, \beta_0, \sigma$ are ordinals such
that $\rho < \omega^{\alpha_0}$ and $\sigma < \omega^{\beta_0}$, and $0 < a, b < \omega$, the width of $\alpha \times \beta$ is computed inductively as:

$$w(\alpha \times \beta) = \omega^{\eta} \cdot (a + b - 1) + [w(\omega^{\alpha_0} \times \sigma) \oplus w(\omega^{\beta_0} \times \rho)],$$

$$\text{with } \eta = 1 + ((\alpha_0 - 1) \oplus (\beta_0 - 1)).$$

To illustrate how computing the width of the product of $n$ ordinals is substantially more complex than the case $n = 2$, let us show why the same proof structure as in [14] does not allow us to conclude for the product of $n = 3$ ordinals. Let $X = \alpha_1 \times \alpha_2 \times \alpha_3$ and $x = (x_1, x_2, x_3) \in X$. We can express the residual $X_{\perp x}$ as an union of subsets.

However, unlike the case $n = 2$, this union of disjoint subsets cannot be seen as a disjoint sum of wqos. For instance, observe that the subsets $(> x_1) \times (> x_2) \times (< x_3)$ and $(> x_1) \times (< x_2) \times (< x_3)$ have comparable elements (see Fig. 3). One can see the residual as an augmentation of a disjoint union, but this only gives us an upper bound on $w(X)$, without a matching lower bound.

<figure><img src="image_3.png" /><figcaption>Fig. 3 Two parts of the residual of $\alpha_1 \times \alpha_2 \times \alpha_3$ at $(x_1, x_2, x_3)$ that have comparable elements.</figcaption></figure>

This observation motivated the development of tools to prove refined lower bounds on the width of the cartesian product.

# 3 Lower bound toolbox

## 3.1 Quasi-incomparability

We write $B \perp C$ with $B$ and $C$ two subsets of a wqo $A$ when $b \perp_A c$ for any $b \in B, c \in C$. We say $A_1, \dots, A_m$ is an *incomparable* family of subsets of $A$ when $A_i \perp A_j$ in $A$ for any $i \neq j$. Observe that, for an incomparable family, we have $A \ge_{st} \bigsqcup_i A_i$ thus $w(A) \ge \bigoplus_i w(A_i)$. What we would like is to obtain a similar result with a weaker condition on the $A_i$s: Quasi-incomparability.
10 On the width of the cartesian product of ordinals

**Definition 3.1** (Quasi-incomparability). Let $A$ be a wqo, and $A_1, \dots, A_m$ be subsets of $A$. Then $A_1, \dots, A_m$ is a quasi-incomparable family of subsets of $A$ if for any $i \in [1, m]$, for every finite set $Y \subseteq A_1 \cup \dots \cup A_{i-1}$, there exists $A'_i \subseteq A_i$ such that $A'_i \perp Y$ and $w(A'_i) = w(A_i)$.

Note that the notion of quasi-incomparable family is sensitive to the way we number the $A_i$: $A_1, \dots, A_m$ being a quasi-incomparable family of subsets of $A$ does not mean that $A_m, \dots, A_1$ is one too.

Since $A$ is FAC, it implies that the $A_i$s are disjoint: Imagine a quasi-incomparable family of subsets $A_1, A_2$ such that there is some $x \in A_1 \cap A_2$. Then $w(A_2) \ge 1 + w(A_{2\perp x})$ through Eq. (Res-w). Following the definition of quasi-incomparability, there exists $A'_2 \subseteq A_2$ such that $A'_2 \perp \{x\}$ and $w(A'_2) = w(A_2)$. Hence $w(A_2) \ge 1 + w(A_2)$, we reach a contradiction.

**Lemma 3.2** (Width lower bound for quasi-incomparable families).

Let $A_1, \dots, A_m$ be a quasi-incomparable family of subsets of $A$. Then $w(A) \ge w(A_m) + \dots + w(A_1)$.

*Proof* By induction on $m$. If $m=1$, $w(A) \ge w(A_1)$ because $A_1 \le_{\text{st}} A$. Assume now $m>1$. Let $Y$ be a finite subset of $A_1$. By definition, for all $i \in [2, m]$, there exists $A'_i \subseteq A_i \cap A_{\perp Y}$ such that $w(A'_i) = w(A_i)$. Since $A'_i \le_{\text{st}} A_i \cap A_{\perp Y} \le_{\text{st}} A_i$, we deduce that $w(A_i \cap A_{\perp Y}) = w(A_i)$.

We claim that $(A_i \cap A_{\perp Y})_{i \in [2, m]}$ is a quasi-incomparable family of $A_{\perp Y}$: Since $(A_i)_{i \in [1, m]}$ is a quasi-incomparable family of subsets of $A$, for any $i \in [2, m]$, for every finite set $Y' \subseteq (A_2 \cup \dots \cup A_{i-1}) \cap A_{\perp Y}$, there exists $A''_i \subseteq A_i$ such that $A''_i \perp (Y \cup Y')$ and $w(A''_i) = w(A_i) = w(A_i \cap A_{\perp Y})$. Therefore by induction hypothesis, $w(A_{\perp Y}) \ge w(A_m) + \dots + w(A_2)$.

Let $r_A$ and $r_{A_1}$ be the rank functions of $\text{Inco}(A)$ and $\text{Inco}(A_1)$ respectively. Note that $\text{Inco}(A_1)$ is a subtree of $\text{Inco}(A)$. For any antichain $Y \in \text{Inco}(A_1)$, $r_A(Y) = w(A_{\perp Y}) \ge w(A_m) + \dots + w(A_2)$. This means that every antichain of rank 0 in $\text{Inco}(A_1)$ has rank $w(A_{\perp Y}) \ge w(A_m) + \dots + w(A_2)$ in $\text{Inco}(A)$ at least. Hence for any antichain $Y$ in $\text{Inco}(A_1)$, by induction on $r_{A_1}(Y)$, we have $r_A(Y) = w(A_{\perp Y}) \ge w(A_m) + \dots + w(A_2) + r_{A_1}(Y)$. Therefore $w(A) = r_A(\emptyset) \ge w(A_m) + \dots + w(A_2) + r_{A_1}(\emptyset) = w(A_m) + \dots + w(A_1)$.

□

This result will be a cornerstone for Sections 4.2 and 4.3, but we can already use it to prove a nifty lower bound in the case of self-residual wqos.

## 3.2 Lower bound for self-residual wqos

**Definition 3.3** (Self-residual). Let $A$ be a quasi-order. Then $A$ is self-residual if for any $x \in A$, $A \not\subseteq x$ contains an isomorphic copy of $A$.

**Remark 3.4.** If $A$ is self-residual, then for all finite $Y \subseteq A$, $A \not\subseteq Y$ contains an isomorphic copy of $A$ (by induction on the size of $Y$).
The notion of self-residual is compatible with the cartesian product: if $A$ and $B$ are self-residual wqos, then $A \times B$ is self-residual.

**Example 3.5.** Any infinite indecomposable ordinal $\alpha$ is self-residual: for any $x < \alpha$, $\alpha \not\le x \equiv \alpha - (x+1) = \alpha$, because $x+1 < \alpha$. Furthermore, the cartesian product of $n$ infinite indecomposable ordinals is self-residual.

Here is an application of Lemma 3.2 that will be useful in Section 4.1. Let us write $B \cdot k$ for the direct sum of $k$ copies of $B$.

**Lemma 3.6.** Let $A, B$ be two wqos such that $A$ is self-residual. Then $w(A \times (B \cdot k)) \ge w(A \times B) \cdot k$.

*Proof* Let $B_1, \dots, B_k$ be disjoint copies of $B$, and $B \cdot k = B_k + \dots + B_1$. We claim that $(A \times B_i)_{i \in [1, k]}$ is a quasi-incomparable family of subsets of $A \times (B \cdot k)$:

Fix $j \in [1, k-1]$ and $Y \subset (A \times B_1) \cup \dots \cup (A \times B_j)$ finite (Fig. 4 illustrates the case $j=2$). We want to find a subset $C$ of $A \times B_{j+1}$ isomorphic to $A \times B_{j+1}$ such that $C \perp Y$. Let $\text{proj}_A(Y) \stackrel{\text{def}}{=} \{a \in A \mid (a,b) \in Y \text{ for some } b \in B_1 \cup \dots \cup B_j\}$. Since $A$ is self-residual, $A_{\le \text{proj}_A(Y)}$ contains an isomorphic copy of $A$, hence $w(A_{\le \text{proj}_A(Y)} \times B_{j+1}) = w(A \times B_{j+1})$. For any $(a,b) \in A_{\le \text{proj}_A(Y)} \times B_{j+1}$ and $(a',b') \in Y$, we know that $a \not\le_A a'$ and $b <_{B \cdot k} b'$, thus $(a,b) \perp (a',b')$. Hence $A_{\le \text{proj}_A(Y)} \times B_{j+1} \perp Y$.

<figure><img src="image_4.png" /><figcaption>**Fig. 4** All elements $(a,b)$ of $A_{\le \text{proj}_A(Y)} \times (B_k + \dots + B_3)$ are incomparable with $Y \subseteq A \times (B_2 + B_1)$.</figcaption></figure>

Therefore $(A \times B_i)_{i \in [1, n]}$ is a quasi-incomparable family in $A \times (B \cdot k)$, so according to Lemma 3.2,
12 On the width of the cartesian product of ordinals

$$ w \left( A \times \left( \sum_{i=k}^{1} B_i \right) \right) \geq \sum_{i=k}^{1} w(A \times B_i) = w(A \times B) \cdot k. \quad \square $$

**Remark 3.7.** When $w(A \times B)$ is indecomposable, this lower bound is tight: $A \times (B \cdot k) \geq_{\text{aug}} A \times B \times \Gamma_k$, so $w(A \times (B \cdot k)) \leq w(A \times B) \otimes k = w(A \times B) \cdot k$ through 2.8.6.

## 3.3 Lower bound for transferable wqos

[13] introduces a notion less restrictive than self-residuality : transferability.

**Definition 3.8.** A wqo $A$ is transferable if $w(A_{\leq Y}) = w(A)$ for any finite $Y \in A$.

**Theorem 3.9 (Theorem 4.16 of [13]).** Suppose that $A$ is a transferable wqo and $\beta$ is an ordinal. Then $w(A \times \beta) \geq w(A) \cdot \beta$.

From this lemma, we deduce a more general result which we will use in Section 4.1.

**Corollary 3.10.** Suppose that $A$ is a transferable wqo and $B$ any wqo. Then $w(A \times B) \geq w(A) \cdot o(B)$.

*Proof* According to Lemma 2.14, $B \leq_{\text{aug}} o(B)$. Therefore $w(A \times B) \geq w(A \times o(B)) \geq w(A) \cdot o(B)$. $\square$

Let us show how Corollary 3.10 can be combined with the method of residuals or Lemma 2.4 to compute the width of simple examples:

We note $A^{\times n} \stackrel{\text{def}}{=} A \times \dots \times A$ the cartesian product of $n$ copies of a wqo $A$.

**Proposition 3.11.** $w(\omega^{\times n}) = \omega^{n-1}$ for $n \geq 1$.

*Proof* Case $n = 1$: $w(\omega) = 1$.

If $n > 1$, then $\omega^{\times n}$ is a cartesian product of $n$ indecomposable ordinals so it is self-residual hence transferable. Thus according to Corollary 3.10 $w(\omega^{\times n}) \geq w(\omega) \cdot o(\omega^{\times (n-1)}) = \omega^{n-1}$.

Let us prove the upper bound by induction on $n$, initialized in $n = 1$: Assume $w(\omega^{\times n}) = \omega^{n-1}$ for some $n$. Let $m = (m_0, \dots, m_n)$ be any element of $\omega^{\times (n+1)}$, $m' = (m_1, \dots, m_n)$. We know $(\omega^{\times n})_{<m'}$ is finite, so there exists $k < \omega$ such that $k \geq_{\text{aug}} (\omega^{\times n})_{<m'}$. Then:

$$ (\omega^{\times(n+1)})_{\perp m} \geq_{\text{aug}} (<m_0) \times (\omega^{\times n})_{>m'} \sqcup (>m_0) \times (\omega^{\times n})_{<m'} \sqcup \{m_0\} \times (\omega^{\times n})_{\perp m'} \\ \geq_{\text{aug}} \Gamma_{m_0} \times \omega^{\times n} \sqcup \omega \times \Gamma_k \sqcup (\omega^{\times n})_{\perp m'}. $$
Therefore by induction hypothesis $\mathbf{w}(\omega_{\perp m}^{\times(n+1)}) \le \omega^{n-1} \cdot m_0 \oplus k \oplus \gamma$ with $\gamma < \omega^{n-1}$, hence $\mathbf{w}(\omega_{\perp m}^{\times(n+1)}) < \omega^n$.

Thus following Eq. (Res-w): $\mathbf{w}(\omega^{\times(n+1)}) = \sup_m \{\mathbf{w}(\omega_{\perp m}^{\times(n+1)}) + 1\} \le \omega^n$. $\square$

**Proposition 3.12.** $\mathbf{w}((\omega^\omega)^{\times n}) = \omega^{\omega \cdot n}$ for $n \ge 2$.

*Proof* Observe that, as a cartesian product of $n$ indecomposable ordinals, $(\omega^\omega)^{\times n}$ is self-residual hence transferable.

The case $n=2$ is an application of Theorem 2.16. If $n > 2$:

$$ \begin{aligned} \mathbf{w}((\omega^\omega)^{\times n}) &\le \mathbf{o}((\omega^\omega)^{\times n}) = \omega^{\omega \cdot n} \quad \text{according to Lemma 2.4,} \\ \mathbf{w}((\omega^\omega)^{\times n}) &\ge \mathbf{w}(\omega^\omega \times \omega^\omega) \cdot \mathbf{o}((\omega^\omega)^{\times(n-2)}) = \omega^{\omega \cdot 2} \cdot \omega^{\omega \cdot (n-2)} = \omega^{\omega \cdot n} \end{aligned} $$

according to Corollary 3.10 and Table 1. $\square$

Let us revisit Example 2.9:

**Example 2.9.** Let $H \stackrel{\text{def}}{=} \sum_{n<\omega} \Gamma_n$, $A_1 \stackrel{\text{def}}{=} H + \omega$ and $A_2 \stackrel{\text{def}}{=} H + H$. Thus $A_1$ and $A_2$ have the same ordinal invariants. However $\mathbf{w}(A_1 \times \omega) \ne \mathbf{w}(A_2 \times \omega)$.

*Proof* Observe that $H$ is self-residual thus transferable and $\mathbf{w}(H) = \mathbf{o}(H) = \mathbf{h}(H) = \omega$. Therefore according to Table 1, $\mathbf{w}(A_i) = \omega$ and $\mathbf{o}(A_i) = \mathbf{h}(A_i) = \omega \cdot 2$ for $i \in \{1, 2\}$.

According to Proposition 3.11, $\mathbf{w}(\omega \times \omega) = \omega$. And $\mathbf{w}(H \times \omega) = \omega^2$, thanks to Lemma 2.4 and Corollary 3.10.

Since $A_1 \ge \text{aug}(H \sqcup \omega)$, $\mathbf{w}(A_1 \times \omega) \le \mathbf{w}(H \times \omega) \oplus \mathbf{w}(\omega \times \omega) = \omega^2 \oplus \omega$. Furthermore, $(\omega \times \omega, H \times \omega)$ is a quasi-incomparable family of subsets of $A_1 \times \omega$: For any finite subset $Y$ of $\omega \times \omega$, let $k = \max\{n \mid (m, n) \in Y\}$. Then $H \times \{n \in \omega \mid n > k\}$ is isomorphic to $H \times \omega$ and incomparable to $Y$. Hence according to Lemma 3.2, $\mathbf{w}(A_1 \times \omega) = \omega^2 + \omega$. Similarly, $\mathbf{w}(A_2 \times \omega) = \omega^2 \cdot 2 \ne \mathbf{w}(A_1 \times \omega)$. $\square$

# 4 Width of the cartesian product of ordinals

The next three subsections build on each other, and culminate with Theorem 4.14 which computes the width of the product of several ordinals when at least two are infinite. The fourth subsection is independent and recalls a result which solves the width of the product of finite ordinals.

## 4.1 Product of indecomposable ordinals

This section computes the width of the product of $n$ indecomposable ordinals, for any $2 \le n < \omega$. Recall the case $n=2$ from Theorem 2.16:

$\mathbf{w}(\omega^{\alpha_1} \times \omega^{\alpha_2}) = \omega^\eta$ with $\eta = 1 + ((\alpha_1 - 1) \oplus (\alpha_2 - 1))$ for any ordinals $\alpha_1, \alpha_2 > 0$.
14 On the width of the cartesian product of ordinals

**Remark 4.1.** For any ordinals $\alpha \ge \beta$, according to Propositions 2.8.1 and 2.8.2, $1 + ((\alpha - 1) \oplus (\beta - 1)) = \alpha \oplus (\beta - 1)$.

**Lemma 4.2.** Let $X = \omega^{\alpha_1} \times \dots \times \omega^{\alpha_n}$, with $2 \le n \le \omega$ and $\alpha_1, \dots, \alpha_n$ infinite ordinals. Then $w(X) = \omega^{\alpha_1 \oplus \dots \oplus \alpha_n}$.

*Proof* We know from Lemma 2.4 and Table 1 that $w(X) \le o(X) = \omega^{\alpha_1 \oplus \dots \oplus \alpha_n}$. Observe that $X \le_{\text{aug}} \omega^{\alpha_1} \times o(\omega^{\alpha_2} \times \dots \times \omega^{\alpha_n}) = \omega^{\alpha_1} \times \omega^{\alpha_2 \oplus \dots \oplus \alpha_n}$. Therefore according to Theorem 2.16, $w(X) \ge \omega^{\eta}$ with $\eta = 1 + ((\alpha_1 - 1) \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)) = \alpha_1 \oplus \dots \oplus \alpha_n$ through Propositions 2.8.1 and 2.8.2. $\square$

**Theorem 4.3.** Let $X = \omega^{\alpha_1} \times \dots \times \omega^{\alpha_n}$, with $2 \le n < \omega$ and $\alpha_1 \ge \dots \ge \alpha_n$ ordinals. Then $w(X) = \omega^{\eta}$ with $\eta = 0$ if $\alpha_2 = \dots = \alpha_n = 0$, otherwise $\eta = \alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)$.

*Proof* Let $k \le n$ be the integer such that $\alpha_1 \ge \dots \ge \alpha_k > 0 = \alpha_{k+1} = \dots = \alpha_n$. If $k \le 1$, then $X \equiv \omega^{\alpha_1}$ so $w(X) = 1$. Otherwise $k \ge 2$, and $X \equiv \omega^{\alpha_1} \times \dots \times \omega^{\alpha_k}$. Observe that $\alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_k) - 1) = \alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)$. Hence we assume without loss of generality that $k = n$.

Case $n = 2$ is given by Theorem 2.16 and Remark 4.1.

If $\alpha_1, \dots, \alpha_n$ are infinite, then according to Lemma 4.2, $w(X) = \omega^{\alpha_1 \oplus \dots \oplus \alpha_n} = \omega^{\alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)}$ through Proposition 2.8.2.

Otherwise remember that $\omega^{\alpha_1} \times \dots \times \omega^{\alpha_j}$ is self-residual for all $j \le n$ hence transferable.

If $\alpha_2, \dots, \alpha_n$ are finite, then according to Corollary 3.10

$$ 
\begin{aligned}
w(X) &\ge w(\omega^{\alpha_1} \times \omega^{\alpha_2}) \cdot o(\omega^{\alpha_3} \times \dots \times \omega^{\alpha_n}) \\
&= \omega^{(\alpha_1 \oplus (\alpha_2 - 1)) + (\alpha_3 \oplus \dots \oplus \alpha_n)} \quad (\text{Theorem 2.16 and Table 1}), \\
&= \omega^{\alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)} \quad (\text{Proposition 2.8.4}).
\end{aligned}
$$

Similarly if $\alpha_1, \dots, \alpha_k$ are infinite and $\alpha_{k+1}, \dots, \alpha_n$ finite for $2 \le k < n$, then according to Corollary 3.10 and Lemma 4.2:

$$ w(X) \ge w(\omega^{\alpha_1} \times \dots \times \omega^{\alpha_k}) \cdot o(\omega^{\alpha_{k+1}} \times \dots \times \omega^{\alpha_n}) = \omega^{\alpha_1 \oplus \dots \oplus \alpha_n} = \omega^{\alpha_1 \oplus ((\alpha_2 \oplus \dots \oplus \alpha_n) - 1)}. $$

Thus $w(X) \ge \omega^{\eta}$.

Now we prove the upper bound by induction on $(\alpha_1, \dots, \alpha_n)$ with the cartesian product ordering:

The induction is initialized with $w(\omega^{\times n}) = \omega^{n-1}$ from Proposition 3.11.

Let $x = (x_1, \dots, x_n)$ be an element of $X$. For all $i \in [1, n]$ there exists $0 \le \alpha'_i < \alpha_i$ and $m_i \in \omega$ such that $x_i \le \omega^{\alpha'_i} \cdot m_i < \omega^{\alpha_i}$. The residual $X_{\perp x}$ is a substructure of an augmentation of a disjoint sum of terms of the form $\left( \times_{i \in I} (< x_i) \right) \times \left( \times_{i \notin I} (\ge x_i) \right)$ with $I \subset [1, n], I \ne \emptyset$. Observe that:

$$ \left( \times_{i \in I} (< x_i) \right) \times \left( \times_{i \notin I} (\ge x_i) \right) \le_{\text{st}} \left( \times_{i \in I} \omega^{\alpha'_i} \cdot m_i \right) \times \left( \times_{i \notin I} \omega^{\alpha_i} \right) $$
$$ \geq_{\text{aug}} \left( \times_{i \in I} \omega^{\alpha'_i} \times \Gamma_{m_i} \right) \times \left( \times_{i \notin I} \omega^{\alpha_i} \right), $$

therefore

$$ w(X_{\perp x}) \leq \bigoplus_{I \subseteq [1, n], I \neq \emptyset} w \left( \left( \times_{i \in I} \omega^{\alpha'_i} \right) \times \left( \times_{i \notin I} \omega^{\alpha_i} \right) \right) \cdot \prod_{i \in I} m_i . $$

By induction hypothesis, $w \left( \left( \times_{i \in I} \omega^{\alpha'_i} \right) \times \left( \times_{i \notin I} \omega^{\alpha_i} \right) \right) = \omega^{\eta'},$ with $\eta' < \alpha_1 \oplus (\alpha_2 \oplus \cdots \oplus \alpha_n - 1)$ according to Remark 4.4.

Therefore $w(X) \leq \omega^{\alpha_1 \oplus (\alpha_2 \oplus \cdots \oplus \alpha_n - 1)}$ through Eq. (Res-w). $\square$

**Remark 4.4.** According to Propositions 2.8.7 and 2.8.9, for any ordinals $\alpha_1, \dots, \alpha_n, \beta_1, \dots, \beta_n$ with $2 \leq n < \omega$, if $(\alpha_1, \dots, \alpha_n) < (\beta_1, \dots, \beta_n)$ component-wise then $\alpha_1 \oplus ((\alpha_2 \oplus \cdots \oplus \alpha_n) - 1) < \beta_1 \oplus ((\beta_2 \oplus \cdots \oplus \beta_n) - 1)$.

**Corollary 4.5.** If $\alpha_1$ and $\alpha_2$ are infinite, then $\alpha_1 \oplus ((\alpha_2 \oplus \cdots \oplus \alpha_n) - 1) = \alpha_1 \oplus \cdots \oplus \alpha_n$, hence $w(X) = o(X)$ according to Table 1. Otherwise $w(X) < o(X)$.

## 4.2 Product of infinite ordinals

This section extends our result on the width of the product of indecomposable ordinals (Theorem 4.3) to the width of the product of infinite ordinals (Theorem 4.6).

Let $X = \alpha_1 \times \cdots \times \alpha_n$ be a cartesian product of $n$ infinite ordinals $(\alpha_i)_{1 \leq i \leq n}$. For any $i \in [1, n]$, $\alpha_i$ is written as $\sum_{j<l_i} \omega^{\alpha_{i,j}}$ in CNF, i.e. $\alpha_{i,0} \geq \cdots \geq \alpha_{i,l_i-1}$.

We partition $X$ into disjoint subsets we call *slices*: let $Sl(X) \stackrel{\text{def}}{=} l_1 \times \cdots \times l_n$ be the set of *slice indices*. For any $s = (s(1), \dots, s(n)) \in Sl(X)$, we define the slice $X_s$ as

$$ X_s \stackrel{\text{def}}{=} \times_{i \in [1, n]} X_{s,i} $$

where $X_{s,i}$ is the interval of $\alpha_i$ whose elements are bigger than or equal to $\sum_{j \leq s(i)-1} \omega^{\alpha_{i,j}}$ (or 0 if $s(i) = 0$) and strictly smaller than $\sum_{j \leq s(i)} \omega^{\alpha_{i,j}}$.

Observe that $X_s$ is isomorphic to $\times_{i \in [1, n]} \omega^{\alpha_{i,s(i)}}$. Therefore we know $w(X_s)$

through Theorem 4.3.

We say $s \in Sl(X)$ is *grounded* if there exists $k \in [1, n]$ such that $s(k) = 0$. Let $Gr(X) \stackrel{\text{def}}{=} \{s \in Sl(X) \mid \exists k \in [1, n], s(k) = 0\}$ the set of grounded slice indices. We denote the cardinal of $Gr(X)$ with $L = \prod l_i - \prod (l_i - 1)$.

**Theorem 4.6.** Let $X = \alpha_1 \times \cdots \times \alpha_n$ be a cartesian product of $n$ infinite ordinals. Then

$$ w(X) = \bigoplus_{s \in Gr(X)} w \left( \times_{i \in [1, n]} \omega^{\alpha_{i,s(i)}} \right). \qquad (2) $$
16 On the width of the cartesian product of ordinals

<figure><img src="image_5.png" /><figcaption>Fig. 5 Slices and grounded slices: $X = (\omega^\omega + \omega) \times (\omega \cdot 3) \times (\omega^3 + \omega^2 + 1)$, $X_s$ and $X_t$ for $s = (1, 0, 2)$, $t = (1, 2, 0)$ are both grounded.</figcaption></figure>

We will first prove the upper bound $w(X) \le \bigoplus_{s \in Gr(X)} w(X_s)$, then the lower bound $w(X) \ge \bigoplus_{s \in Gr(X)} w(X_s)$.

Proof of the upper bound of Theorem 4.6

For any slices $s, t \in Sl(X)$, we write $s \prec t$ if and only if for all $i \in [1, n]$, $s(i) < t(i)$. Observe that, for any $s, t$ such that $s \prec t$:

* for any $x \in X_s$, $x' \in X_t$, we have $x <_X x'$.

* for any $i \in [1, n]$, $\alpha_{i,s(i)} \ge \alpha_{i,t(i)}$, therefore $w(X_s) \ge w(X_t)$ according to Theorem 4.3 and Remark 4.4.

We define a surjective function $g: Sl(X) \to Gr(X)$ which maps any slice index to a grounded slice index:

$$g(s)(i) \stackrel{\text{def}}{=} s(i) - k \text{ with } k = \min_{i \in [1, n]} s(i).$$

This surjection has interesting properties:

If $s$ is grounded then $g(s) = s$, otherwise $g(s) \prec s$. Thus $w(X_s) \le w(X_{g(s)})$.

For any distinct $s, t \in Sl(X)$, such that $g(s) = g(t)$, $s \prec t$ or $s \succ t$.

Thus $X$ is an augmentation of the disjoint sum of direct sums of slices grouped by image through $g$, as illustrated in Fig. 6:

$$X \geq_{\text{aug}} \bigcup_{s \in Gr(X)} \sum_{s' \in g^{-1}(s)} X_{s'}. $$

Therefore, according to Table 1,

$$w(X) \le \bigoplus_{s \in Gr(X)} \max_{s' \in g^{-1}(s)} w(X_{s'}) = \bigoplus_{s \in Gr(X)} w(X_s).$$

□
<figure><img src="image_6.png" /><figcaption>Fig. 6 Relations between slices when $Sl(X) = 3 \times 3$.</figcaption></figure>

We need to introduce a few notations before proving the lower bound of Theorem 4.6.

For any finite subset $Y$ of $X$, we define $\xi(Y, i)$ as the maximum of the $i$-th components of elements of $Y$ which are less than $\omega^{\alpha_{i,0}}$:

$$ \xi(Y, i) \stackrel{\text{def}}{=} \max \{y(i) + 1 \mid y \in Y, y(i) < \omega^{\alpha_{i,0}}\}. $$

We define a function $\text{trim}$ which given a slice $X_s$ and a finite subset of $X$ outputs a subset of $X_s$:

$$ \text{trim}(X_s, Y) \stackrel{\text{def}}{=} \times_{i \in [1, n]} \text{trim}(X_{s,i}, Y), $$

where

$$ \text{trim}(X_{s,i}, Y) \stackrel{\text{def}}{=} \begin{cases} \{\delta \in X_{s,i} \mid \xi(Y, i) \le \delta\} & \text{if } s(i) = 0, \\ X_{s,i} & \text{otherwise.} \end{cases} $$

**Lemma 4.7.** For any finite set $Y \in X$, and any slice index $s \in Sl(X)$, $\text{trim}(X_s, Y)$ is isomorphic to $X_s$.

*Proof* For any $i \in [1, n]$, $\text{trim}(X_{s,i}, Y)$ is isomorphic to $X_{s,i}$: If $s(i) > 0$ then $\text{trim}(X_{s,i}, Y) = X_{s,i}$. Otherwise $s(i) = 0$ and $\text{trim}(X_{s,i}, Y) = \{\delta \in X_{s,i} \mid \xi(Y, i) \le \delta\} \equiv \omega^{\alpha_{i,0}} - \xi(Y, i)$. Since $\alpha_i$ is infinite, $\omega^{\alpha_{i,0}}$ is infinite indecomposable, and $\xi(Y, i) < \omega^{\alpha_{i,0}}$ since $Y$ is finite and $\omega^{\alpha_{i,0}}$ limit. Therefore $\omega^{\alpha_{i,0}} - \xi(Y, i) = \omega^{\alpha_{i,0}} \equiv X_{s,i}$. $\square$

**Lemma 4.8.** Let $s_1, \dots, s_L$ be a linearisation of $(\text{Gr}(X), \le_X)$ (i.e., a reordering such that $s_1 \not\ge \dots \not\ge s_L$ component-wise). Then $(X_{s_i})_{1 \le i \le L}$ is a quasi-incomparable family of subsets of $X$.
18 On the width of the cartesian product of ordinals

<figure><img src="image_7.png" /><figcaption>Fig. 7 $\text{trim}(X_s, Y)$, for $s = (1, 1, 0)$, is incomparable to $Y$</figcaption></figure>

*Proof* Fix $k \in [2, L]$ and $Y$ a finite subset of $X_{s_1} \cup \cdots \cup X_{s_{k-1}}$. Then we define $X'_{s_k} \subseteq X_{s_k}$ as $\text{trim}(X_{s_k}, Y)$. According to Lemma 4.7, $X'_{s_k}$ is isomorphic to $X_{s_k}$ hence $\mathbf{w}(X'_{s_k}) = \mathbf{w}(X_{s_k})$.

Let us show $X'_{s_k} \perp Y$: We pick $x \in X'_{s_k}$, $y \in Y$ two elements of $X$. There exists $j < k$ such that $y \in X_{s_j}$. Since $s_1, \dots, s_L$ is a linearisation of $\text{Gr}(X)$, $s_j \not\le s_k$. Therefore there exists $i_1 \in [1, n]$ such that $s_j(i_1) > s_k(i_1)$, hence $y(i_1) > x(i_1)$. Since $s_j$ is grounded, there exists $i_2 \in [1, n]$ such that $s_j(i_2) = 0$. If $s_k(i_2) > 0$ then $x(i_2) \ge \omega^{\alpha_{i_1, 0}} > y(i_2)$. otherwise $x(i_2) \ge \xi(Y, i_2) > y(i_2)$. Therefore $x \perp y$.

□

**Lemma 4.9.** There exists a linearisation $s_1, \dots, s_L$ of $(\text{Gr}(X), \le_X)$ such that $\mathbf{w}(X_{s_L}) + \dots + \mathbf{w}(X_{s_1}) = \bigoplus_{s \in \text{Gr}(X)} \mathbf{w}(X_s)$.

*Proof* According to Theorem 4.3, $\mathbf{w}(X_s)$ can be written under the form $\mathbf{w}(X_s) = \omega^{\eta_s}$ for some ordinal $\eta_s$. Observe that for any distinct grounded slices $s, s'$, $\eta_s < \eta_{s'}$ implies that $s_i \not\le s_j$ according to Remark 4.4. Therefore there exists a linearisation $s_1, \dots, s_L$ such that $\eta_{s_1} \le \dots \le \eta_{s_L}$, which means that $\mathbf{w}(X_{s_L}) + \dots + \mathbf{w}(X_{s_1}) = \bigoplus_{s \in \text{Gr}(X)} \mathbf{w}(X_s)$.

□

*Proof of the lower bound of Theorem 4.6*

Let $s_1, \dots, s_L$ be a linearisation of $(\text{Gr}(X), \le_X)$ such that $\mathbf{w}(X_{s_L}) + \dots + \mathbf{w}(X_{s_1}) = \bigoplus_{s \in \text{Gr}(X)} \mathbf{w}(X_s)$. Such an ordering exists according to Lemma 4.9. According to Lemma 4.8, $(X_{s_j})_{j \in [1, L]}$ is a quasi-incomparable family, hence according to Lemma 3.2,

$$ \mathbf{w}(X) \ge \mathbf{w}(X_{s_L}) + \dots + \mathbf{w}(X_{s_1}) = \bigoplus_{s \in \text{Gr}(X)} \mathbf{w}(X_s). $$

□
We can rewrite Eq. (2) from Theorem 4.6 in a way that makes our result easier to compare with Theorem 2.16.

**Theorem 4.10** (Inductive expression of $\mathbf{w}(X)$). Let $X = \alpha_1 \times \cdots \times \alpha_n$ be a cartesian product of $n$ infinite ordinals. For $i \in [1, n]$, let $\alpha_i = \omega^{\alpha_{i,0}} \cdot a_i + \sigma_i$ where $\alpha_{i,0}$ and $\sigma_i$ are ordinals such that $\sigma_i < \omega^{\alpha_{i,0}}$, and $0 < a_i < \omega$. Then

$$ \mathbf{w}(X) = \bigoplus_{\emptyset \neq I \subseteq [1, n]} \mathbf{w}(X_I) \otimes \left( \prod_{i \in I} a_i - \prod_{i \notin I} (a_i - 1) \right), $$

$$ \text{where } X_I \stackrel{\text{def}}{=} \left( \bigotimes_{i \in I} \omega^{\alpha_{i,0}} \right) \times \left( \bigotimes_{i \notin I} \sigma_i \right) \text{ for all } I \subseteq [1, n], I \neq \emptyset. $$

As expected, when $n = 2$ this is exactly Abraham's formula (Theorem 2.16).

*Proof* For all $i \in [1, n]$, each $\alpha_i$ can be written uniquely as $\sum_{j<l'_i} \omega^{\alpha'_{i,j}} \cdot a_{i,j}$ with $\alpha'_{i,0} > \cdots > \alpha'_{i,l'_i-1}$. Let $Sl'(X) \stackrel{\text{def}}{=} l'_1 \times \cdots \times l'_n$ and let $Gr'(X)$ be the grounded slices of $Sl'(X)$. For any $s \in Gr'(X)$ there are exactly $k_s$ slices $t$ in $Gr(X)$ such that $\alpha_{i,t(i)} = \alpha'_{i,s(i)}$ for every $i \in [1, n]$, with

$$ k_s \stackrel{\text{def}}{=} \left( \prod_{s(i)=0} a_{i,0} - \prod_{s(i)=0} (a_{i,0}-1) \right) \cdot \prod_{s(i)>0} a_{i,s(i)} . $$

Let $X'_s = \times_{i \in [1, n]} \omega^{\alpha'_{i,s(i)}}$ for any $s \in Sl'(X)$. Then

$$ \bigoplus_{s \in Gr(X)} \mathbf{w}(X_s) = \bigoplus_{s \in Gr'(X)} \mathbf{w}(X'_s) \otimes k_s, $$

Similarly, for any $I \in [1, n], I \neq \emptyset$,

$$ \mathbf{w}(X_I) = \bigoplus_{s \in Gr'(X), s(i)=0 \text{ iff } i \in I} \mathbf{w}(X'_s) \otimes \prod_{i \notin I} a_{i,s(i)}. $$

Hence

$$ \mathbf{w}(X) = \bigoplus_{\emptyset \neq I \subseteq [1, n]} \mathbf{w}(X_I) \otimes \left( \prod_{i \in I} a_i - \prod_{i \notin I} (a_i - 1) \right) \text{ as claimed.} $$

□

## 4.3 Product of ordinals where at least one is infinite

This section extends our result on the width of the product of infinite ordinals (Theorem 4.6) to the width of the product of finite and infinite ordinals (Theorem 4.14).

**Lemma 4.11.** Let $A$ be a wqo, and $n < \omega$. Then $\mathbf{w}(A \times \Gamma_n) = \mathbf{w}(A) \otimes n$.
20 On the width of the cartesian product of ordinals

Proof Observe that $A \times \Gamma_n \equiv A \sqcup \dots \sqcup A$ the disjoint sum of $n$ copies of $A$. Therefore $\mathbf{w}(A \times \Gamma_n) = \mathbf{w}(A) \oplus \dots \oplus \mathbf{w}(A) = \mathbf{w}(A) \otimes n$. $\square$

**Lemma 4.12.** For $X$ a cartesian product of finitely many indecomposable ordinals, and $k < \omega$, $\mathbf{w}(X \times k) = \mathbf{w}(X) \otimes k$

Proof Since $X \times k \geq \text{aug} \times \Gamma_k$, according to Lemma 4.11 $\mathbf{w}(X \times k) \leq \mathbf{w}(X) \otimes k$. On the other hand, $X$ is transferable hence $\mathbf{w}(X \times k) \geq \mathbf{w}(X) \cdot k$ with Corollary 3.10. According to Theorem 4.3 $\mathbf{w}(X)$ is indecomposable, therefore $\mathbf{w}(X) \cdot k = \mathbf{w}(X) \otimes k$ through Proposition 2.8.6. $\square$

**Lemma 4.13.** Let $X$ be a cartesian product of finitely many infinite ordinals, and $k < \omega$. There exists a linearisation $s_1, \dots, s_L$ of $(Gr(X), \leq_X)$ such that $(X_{s_i} \times k)_{i \in [1, L]}$ is a quasi-incomparable family of subsets of $X \times k$, and $\mathbf{w}(X_{s_L} \times k) + \dots + \mathbf{w}(X_{s_1} \times k) = \mathbf{w}(X) \otimes k$.

Proof According to Lemma 4.9, there exists a linearisation $s_1, \dots, s_L$ of $(Gr(X), \leq_X)$ such that $\mathbf{w}(X_{s_L}) + \dots + \mathbf{w}(X_{s_1}) = \bigoplus_{s \in Gr(X)} \mathbf{w}(X_s)$. We claim that $(Z_i)_{i \in [1, L]} \stackrel{\text{def}}{=} (X_{s_i} \times k)_{i \in [1, L]}$ is a quasi-incomparable family of subsets of $X \times k$: For any $i \in [2, L]$, for any finite $Y \in Z_1 \cup \dots \cup Z_{i-1}$, we define $Y'$ as the projection of $Y$ on $X$. According to Lemmas 4.7 and 4.8, $(X_{s_i})_{i \in [1, L]}$ is a quasi-incomparable family, and there exists $X'_{s_i} \subseteq X_{s_i}$ such that $X'_{s_i} \perp Y'$ and $X'_{s_i} \equiv X_{s_i}$. Let $Z'_i = X'_{s_i} \times k \subseteq Z_i$. Then $Z'_i \perp Y$ and $Z'_i \equiv Z_i$ so $\mathbf{w}(Z'_i) = \mathbf{w}(Z_i)$.

For all $s \in Gr(X)$, $\mathbf{w}(X_s \times k) = \mathbf{w}(X_s) \otimes k$ according to Lemma 4.12. Thus,

$$ \mathbf{w}(Z_L) + \dots + \mathbf{w}(Z_1) = \left( \bigoplus_{s \in Gr(X)} \mathbf{w}(X_s) \right) \otimes k = \mathbf{w}(X) \otimes k, $$

according to Theorem 4.6. $\square$

**Theorem 4.14.** For $X$ an infinite ordinal or a cartesian product of finitely many infinite ordinals, and $k_1, \dots, k_m < \omega$,

$$ \mathbf{w}(X \times k_1 \times \dots \times k_m) = \mathbf{w}(X) \otimes \prod_{i \leq n} k_i $$

Proof Let $k = \prod_{i \leq n} k_i$. We know that $X \times k_1 \times \dots \times k_m \geq \text{aug} \times \Gamma_k$ so by Lemma 4.11 we know that $\mathbf{w}(X \times k_1 \times \dots \times k_m) \leq \mathbf{w}(X) \otimes k$.

If $X$ is an infinite ordinal, then $X \geq_{\text{st}} \omega \times k_1 \times \dots \times k_n$ and $\omega$ is transferable, hence according to Corollary 3.10 $\mathbf{w}(X) \geq \mathbf{w}(\omega) \cdot \mathbf{o}(k_1 \times \dots \times k_n) = k$.

If $X$ is a cartesian product of infinite ordinals, then observe that $X \times k_1 \times \dots \times k_m \leq_{\text{aug}} X \times (\prod_{i \leq n} k_i)$. Therefore $\mathbf{w}(X \times k_1 \times \dots \times k_m) \geq \mathbf{w}(X \times (\prod_{i \leq n} k_i)) \geq \mathbf{w}(X) \otimes (\prod_{i \leq n} k_i)$ according to Lemmas 3.2 and 4.13. $\square$
## 4.4 Product of finite ordinals

The case of the cartesian product of finite ordinals is a finite poset, thus its width coincides with the length of its largest antichain. For the sake of completeness, we recall a classical result that characterizes its width.

Let $k_1, \dots, k_n > 0$ be $n$ finite ordinals, and $p_1, \dots, p_n$ some distinct prime numbers. Observe that $X \stackrel{\text{def}}{=} k_1 \times \dots \times k_n$ is isomorphic to the poset of the divisors of $p_1^{k_1-1} \dots p_n^{k_n-1}$ ordered by divisibility. Therefore, according to Theorem 1 of [17]:

**Theorem 4.15.** Let $X \stackrel{\text{def}}{=} k_1 \times \dots \times k_n$ be a cartesian product of finite ordinals. Then $w(X) = |A|$, with

$$A = \{ (m_1, \dots, m_n) \in X \mid \sum m_i = \left\lfloor \frac{1}{2} \sum (k_i - 1) \right\rfloor \}$$

a maximal antichain of X.

# 5 Application to the cartesian product of wqos

We computed the width of the cartesian product of any number of ordinals. Let us now demonstrate how this result can be extended to the cartesian product of more complex wqos.

## 5.1 When width coincides with maximal order type

In view of $w((\omega^\omega)^{\times n}) = o((\omega^\omega)^{\times n})$ (Proposition 3.12), one wonders if more generally $w(X)$ reaches $o(X)$ when $X$ is a cartesian product of ordinals, for instance when the ordinals are large enough? It turns out that we can exactly characterize the cartesian products of ordinals such that width and m.o.t. coincide:

**Theorem 5.1.** Let $Z = \alpha_1 \times \dots \times \alpha_n \times k_1 \times \dots \times k_m$ with $n, m < \omega$ and $n > 0$, such that $\alpha_1, \dots, \alpha_n$ are infinite ordinals, and $0 < k_1, \dots, k_m < \omega$. Now $w(Z) = o(Z)$ if and only if there exist:

* $i \in [1, n]$ such that $\alpha_i$ is infinite indecomposable, and

* $j_1 \neq j_2 \in [1, n]$ such that the Cantor normal forms of $\alpha_{j_1}$ and $\alpha_{j_2}$ only have infinite exponents (i.e., can be written as $\omega^\omega \cdot \beta$ with $\beta$ any ordinal).

Note that $i$ can be equal to $j_1$ or $j_2$.

*Proof* Let $X = \alpha_1 \times \dots \times \alpha_n$ with $\alpha_i$ written $\sum_{j<l_i} \omega^{\alpha_{i,j}}$ in CNF for any $i \in [1, n]$. We will reuse the notations $Sl(X)$ and $Gr(X)$.

According to Theorem 4.14, $w(Z) = w(X) \otimes k_1 \otimes \dots \otimes k_m$, and $o(Z) = o(X) \otimes k_1 \otimes \dots \otimes k_m$ according to Table 1. Therefore $w(Z) = o(Z)$ if and only if $w(X) = o(X)$.
22 On the width of the cartesian product of ordinals

We express $\mathbf{o}(X)$ in a form that allow us to compare it easily to $\mathbf{w}(X)$:

$$
\begin{align*}
\mathbf{o}(X) &= \bigotimes_{i \in [1, n]} \alpha_i \quad \text{according to Table 1} \\
&= \bigoplus_{s \in \mathrm{Sl}(X)} \left( \bigotimes_{i \in [1, n]} \omega^{\alpha_{i,s(i)}} \right) \quad \text{by distributivity} \\
&= \bigoplus_{s \in \mathrm{Sl}(X)} \mathbf{o}(X_s),
\end{align*}
$$

and

$$
\mathbf{w}(X) = \bigoplus_{s \in \mathrm{Gr}(X)} \mathbf{w}(X_s) \quad \text{according to Theorem 4.6.}
$$

According to Lemma 2.4, for every slice $s \in \mathrm{Sl}(X)$, $0 < \mathbf{w}(X_s) \le \mathbf{o}(X_s)$. Moreover $\mathrm{Gr}(X) \subseteq \mathrm{Sl}(X)$. Therefore $\mathbf{w}(X) = \mathbf{o}(X)$ if and only if $\mathrm{Gr}(X) = \mathrm{Sl}(X)$ and $\mathbf{w}(X_s) = \mathbf{o}(X_s)$ for any $s \in \mathrm{Sl}(X)$.

* $\mathrm{Gr}(X) = \mathrm{Sl}(X)$ iff there are no ungrounded slices, i.e., there exists $i \in [1, n]$ such that $l_i = 1$. Thus there exists $i$ such that $\alpha_i$ is indecomposable.

* According to Corollary 4.5, $\mathbf{w}(X_s) = \mathbf{o}(X_s)$ is true if and only if there exist $j_1 \neq j_2$ such that $\alpha_{j_1,s(j_1)}$ and $\alpha_{j_2,s(j_2)}$ are both infinite. In particular, for the top slice $s: j \mapsto l_j - 1$, there exist $j_1 \neq j_2$ such that $\alpha_{j_1,l_{j_1}-1}$ and $\alpha_{j_2,l_{j_2}-1}$ are both infinite, and therefore all exponents of $\alpha_{j_1}$ and $\alpha_{j_2}$ are infinite.

□

What is interesting with this result is that it can be extended to the
cartesian product of any wqos:

**Theorem 5.2.** Let $A_1, \dots, A_n$ be a family of wqos. If there exist $i, j_1 \neq j_2 \in [1, n]$ such that $\mathbf{o}(A_i)$ is infinite indecomposable, and $\mathbf{o}(A_{j_1})$ and $\mathbf{o}(A_{j_2})$ only have infinite exponents, then $\mathbf{w}(A_1 \times \dots \times A_n) = \mathbf{o}(A_1) \otimes \dots \otimes \mathbf{o}(A_n)$.

*Proof* According to Lemma 2.4,

$$
\mathbf{w}(A_1 \times \dots \times A_n) \leq \mathbf{o}(A_1) \otimes \dots \otimes \mathbf{o}(A_n).
$$

On the other hand $A_1 \times \cdots \times A_n \le_{\mathrm{aug}} \mathbf{o}(A_1) \times \cdots \times \mathbf{o}(A_n)$ through Lemma 2.14,
thus:

$$
\begin{align*}
\mathbf{w}(A_1 \times \cdots \times A_n) &\ge \mathbf{w}(\mathbf{o}(A_1) \times \cdots \times \mathbf{o}(A_n)) \\
&= \mathbf{o}(\mathbf{o}(A_1) \times \cdots \times \mathbf{o}(A_n)) \quad \text{according to Theorem 5.1,} \\
&= \mathbf{o}(A_1) \otimes \cdots \otimes \mathbf{o}(A_n).
\end{align*}
$$

□

5.2 A family of well-behaved wqos

**Definition 5.3.** The family of *elementary* wqos is the smallest family of wqos that contains $\emptyset$ and is closed by disjoint sum, cartesian product and star operation.
**Remark 5.4.** This family contains $\emptyset^*$ which is isomorphic to the singleton $\Gamma_1$, and $(\emptyset^*)^*$ which is isomorphic to $\omega$. Since it is closed by disjoint sum, it contains also $\Gamma_k$ modulo isomorphism for all $k < \omega$.

The maximal order type and height of any elementary wqo are already well-known (see Table 1). To show how powerful a tool Theorem 5.2 is, we will apply it to compute their width.

We can easily compute the width of a wqo under the star operation, or of a disjoint sum of wqos (see Table 1). Moreover, observe that the cartesian product distributes over the disjoint sum: $A \times (B \sqcup C) = (A \times B) \sqcup (A \times C)$. Therefore we can restrict our study to elementary wqos of the form $A_1^* \times \dots \times A_n^*$ with $A_1, \dots, A_n$ elementary wqos.

**Lemma 5.5.** If $A \neq \emptyset$ then $A^*$ is transferable.

*Proof* For any $u \in A^*$, for any $a \in A$, $A_{\le u}^*$ contains $\{uav|v \in A^*\}$, which is isomorphic to $A^*$. Therefore $A^*$ is self-residual, hence transferable. □

**Remark 5.6.** By Table 1, if $o(A) > 1$, then $o(A^*)$ verifies the conditions described in Theorem 5.2: $o(A^*)$ is infinite indecomposable, and its normal form only have infinite exponents.

This property of $A^*$ will prove useful thanks to the following theorem, which generalises Theorem 5.1 to the cartesian products of $n$ wqos:

Let $X = A_1^* \times \dots \times A_n^*$ with $n \ge 2$ and $A_i \neq \emptyset$ elementary for all $i \le n$. W.l.o.g we assume that $o(A_1) \ge \dots \ge o(A_n)$. Let us compute $w(X)$:

* If $o(A_1) > 1$ and $o(A_2) > 1$, then the conditions of Theorem 5.2 are fulfilled, and $w(X) = o(X)$.

* If $o(A_1) > 1$ and for all $i > 1$, $o(A_j) = 1$ then $A_i \equiv \Gamma_1$ and $A_i^* \equiv \omega$. Thus $X \equiv A_1^* \times \omega^{\times(n-1)}$. According to Lemma 2.4, $w(X) \le o(X)$, and since $A_i^*$ is transferable:

$$ 
\begin{align*}
w(A_1^* \times \omega^{\times n}) &\ge w(A_1^*) \cdot o(\omega^{\times n}) && \text{according to Corollary 3.10,} \\
&= o(A_1^*) \cdot \omega^n && \text{according to Table 1,} \\
&= o(A_1^*) \otimes \omega^n && \text{according to Proposition 2.8.6,} \\
&= o(A_1^* \times \omega^{\times n}), &&
\end{align*} 
$$

which we know how to compute with Table 1.

* Otherwise, $A_i \equiv \Gamma_1$ for all $i \in [1, n]$, hence $X \equiv \omega^{\times n}$. According to Proposition 3.11, $w(\omega^{\times n}) = \omega^{n-1}$ for all $n \ge 1$.

Therefore we know how to measure the width of any elementary wqos.
# 6 Conclusion

We successfully computed the width of the cartesian product of finitely many ordinals (see Theorems 4.3, 4.6, 4.14 and 4.15).

Furthermore, we provide a sufficient condition on a cartesian product of wqos for when width equals maximal order type (see Theorem 5.2). We use this result to compute the width of a generic family of elementary wqos.

The techniques developed here, such as the notion of quasi-incomparability, can help target other open questions on wqo width, for instance, how to compute the width of the finite powerset or the set of multisets over known wqos. Extending the definition of elementary wqos with other classical operations would go a long way toward computing the ordinal invariants of most wqos met in real problems.

# Acknowledgments

The research described in this article started with a master internship supervised by Ph. Schnoebelen. It has also benefited from numerous discussions and suggestions from M. Džamonja, S. Halfon, and S. Schmitz. We also thank the reviewers for their thorough feedback.

# References

[1] Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) **2**(7), 326-336 (1952). https://doi.org/10.1112/plms/s3-2.1.326

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

[3] Milner, E.C.: Basic WQO- and BQO-theory. In: Rival, I. (ed.) Graphs and Order. NATO ASI Series C, vol. 147, pp. 487-502. Springer, Dordrecht (1985). https://doi.org/10.1007/978-94-009-5315-4_14

[4] Schuster, P., Seisenberger, M., Weiermann, A. (eds.): Well Quasi-Orders in Computation, Logic, Language and Reasoning. Trends in Logic, vol. 53. Springer, Berlin/Heidelberg, Germany (2020). https://doi.org/10.1007/978-3-030-30229-0_2

[5] Schmidt, D.: Well-partial orderings and their maximal order types. Habilitationsschrift, Heidelberg (1979)

[6] Kříž, I., Thomas, R.: Ordinal types in Ramsey theory and well-partial-ordering theory. In: Nešetřil, J., Rödl, V. (eds.) Mathematics of Ramsey Theory. Algorithms and Combinatorics, vol. 5, pp. 57-95.
Springer, Berlin/Heidelberg, Germany (1990). https://doi.org/10.1007/978-3-642-72905-8_7

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

[8] Blass, A., Gurevich, Y.: Program termination and well partial orderings. ACM Trans. Computational Logic 9(3), 1–26 (2008). https://doi.org/10.1145/1352582.1352586

[9] Bonnet, R., Finkel, A., Haddad, S., Rosa-Velardo, F.: Ordinal theory for expressiveness of well-structured transition systems. Information and Computation 224, 1–22 (2013). https://doi.org/10.1016/j.ic.2012.11.003

[10] Haase, Ch., Schmitz, S., Schnoebelen, Ph.: The power of priority channel systems. Logical Methods in Comp. Science 10(4:4) (2014). https://doi.org/10.2168/LMCS-10(4:4)2014

[11] Haddad, S., Schmitz, S., Schnoebelen, Ph.: The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets. In: Proc. 27th IEEE Symp. Logic in Computer Science (LICS 2012), Dubrovnik, Croatia, June 2012, pp. 355–364 (2012). https://doi.org/10.1109/LICS.2012.46

[12] Schmitz, S.: The parametric complexity of lossy counter machines. In: Proc. 46th Int. Coll. Automata, Languages, and Programming (ICALP 2019), Patras, Greece, July 2019. Leibniz International Proceedings in Informatics, vol. 132, pp. 129–112915. Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.129

[13] Džamonja, M., Schmitz, S., Schnoebelen, Ph.: On ordinal invariants in well quasi orders and finite antichain orders. In: Schuster, P., Seisenberger, M., Weiermann, A. (eds.) Well Quasi-Orders in Computation, Logic, Language and Reasoning. Trends in Logic, vol. 53, pp. 29–54. Springer, Berlin/Heidelberg, Germany (2020). Chap. 2. https://doi.org/10.1007/978-3-030-30229-0_2

[14] Abraham, U.: A note on Dilworth's theorem in the infinite case. Order 4(2), 107–125 (1987). https://doi.org/10.1007/BF00337691

[15] Wolk, E.S.: Partially well ordered sets and partial ordinals. Fund. Math. 60(2), 175–186 (1967). https://doi.org/10.4064/fm-60-2-175-186
26 *On the width of the cartesian product of ordinals*

[16] Holz, M., Steffens, K., Weitz, E.: Introduction to Cardinal Arithmetic. Modern Birkhäuser Classics. Springer, Berlin/Heidelberg, Germany (1999). https://doi.org/10.1007/978-3-0346-0330-0

[17] de Bruijn, N.G., van Ebbenhorst Tengbergen, C., Kruyswijk, D.: On the set of divisors of a number. Nieuw Archief voor Wiskunde, serie 2 **23**, 191–193 (1951)