# Well-Quasi-Ordering and Embeddability of Relational Structures

Maurice Pouzet

► To cite this version:

Maurice Pouzet. Well-Quasi-Ordering and Embeddability of Relational Structures. Order. A Journal on the Theory of Ordered Sets and its Applications, In press, 10.1007/s11083-024-09664-y. hal-04361204

HAL Id: hal-04361204

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

Submitted on 22 Dec 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
# WELL-QUASI-ORDERING AND EMBEDDABILITY OF RELATIONAL STRUCTURES

MAURICE POUZET

† *To the memory of Roland Fraïssé.*

**ABSTRACT.** At the end of the forties, Fraïssé, following Cantor, Hausdorff and Sierpinski, highlighted the role of the embeddability quasi-order in the theory of relations. Since then, many results illustrating this role have been obtained (a large account was included in Fraïssé's book *Theory of Relations*). In this paper, I present a selection of results centered on the notion of well-quasi-order (wqo). I mention several problems on wqo and hereditary classes of relational structures; some of these problems go back to the seventies.

## INTRODUCTION

This paper is about relational structures, like posets and graphs, and the embeddability quasi-order. We will present a selection of notions and results collected on the road opened by Roland Fraïssé. The basic notions are those of embeddability, hereditary classes, ages and bounds, the results being mostly about hereditary classes, particularly on those which are well-quasi-ordered (wqo for short) or even better-quasi-ordered (bqo). We will mention problems, some going back to the seventies, on wqo and hereditary classes of relational structures. The concepts presented here have an infinitistic nature, but the emphasis is put on the comparison of finite structures by embeddability or by set inclusion, rather than the comparison of infinite structures. Few comparability results on infinite substructures are summarized in Subsection 2.1 and in Section 8. An important area of the theory of relations is the reconstruction of relational structures (in particular, of finite structures) as introduced by Roland Fraïssé and developed by Gérard Lopez and his collaborators. The latter is not covered in this paper and we refer the interested reader to [76, 78, 46].

A relational structure $R$ is *embeddable* in a relational structure $R'$ if $R$ is isomorphic to an induced substructure of $R'$. This defines a quasi-order on the class of relational structures. At the end of the forties, Fraïssé, following the work of Cantor, Hausdorff and Sierpinski, highlighted the role of this quasi-order in the theory of relations. For example, he conjectured that the class of countable chains is well-quasi-ordered (wqo) under embeddability, a conjecture positively solved by Laver [118] in the early seventies with the use of the theory of better-quasi-ordering (bqo), a far reaching strengthening of the notion of wqo, invented by Nash-Williams [139]. Fraïssé also noted that basic notions about ordered sets (posets) like initial segments, ideals, chains and antichains have a direct counterpart in terms of relational structures. For example, a class $\mathcal{C}$ of structures is *hereditary* if it contains every structure which can be embedded into some member of $\mathcal{C}$. Clearly, hereditary classes are initial segments of the class of relational structures quasi-ordered by embeddability. If $R$ is a relational structure, the *age* of $R$ is the set $\text{Age}(R)$ of finite restrictions of $R$ considered up to isomorphy. This is an ideal of the poset made of finite structures considered up to isomorphy and ordered by embeddability. As shown by Fraïssé in the fifties, every countable ideal has this form. Several results concerning hereditary classes of relational structures and based on their order properties have been then obtained. Recent years have seen a renewed interest for the study of hereditary classes made of finite structures and notably for their profile. The *profile* of a hereditary class $\mathcal{C}$ of finite structures considered up to isomorphy is the function $\varphi_{\mathcal{C}}$ which counts for every nonnegative integer $n$ the number of members of $\mathcal{C}$

<footnote>Date: December 22, 2023.</footnote>

<footnote n="2000">2000 Mathematics Subject Classification. 03 C13, 03 C52, 05 A16, 05 C30, 20 B27.</footnote>

<footnote>*Key words and phrases.* Relational structures, ages, counting functions, oligomorphic groups, age algebra, Ramsey theorem, well-quasi-ordering, cellular graphs, tournaments.</footnote>
on $n$ elements. General counting results as well as exact results for graphs, tournaments, ordered graphs and permutations have been obtained, with a particular emphasis on jumps in the growth of the profile.

The content of this paper following this introduction is divided into nine sections. In the first one, I present the notions of order and topology on which our approach is based. Due to the survey nature of this paper, I slowly introduce the basic notions of the theory of relations, like relational structure, homomorphism, isomorphism, giving several examples, like graphs, posets, hypergraphs, words, permutations and bichains, metric spaces, codings of permutation groups. In the following section, I introduce the quasi-order of embeddability and compare isomorphy to equimorphy. Next, I introduce hereditary classes, ages, bounds, and the link with model theory via universal classes. I illustrate these notions with several examples. Then, in Section 3, I consider a classification of hereditary classes based on the notion of well-foundedness. It leads to the notions of wqo and better-quasi-ordering (bqo). I present some of the major results and problems about wqo hereditary classes and ages. Notably, I discuss the use of order and topological means (for example, height, ordinal length, Cantor-Bendixson and Vietoris ranks). In Section 4, I discuss the preservation of well-quasi-order by labelling. There are several notions, some could be equivalent. When they hold, this has some strong consequences, notably on the finiteness of bounds of hereditary classes. In Section 5, I present a classification of hereditary classes and ages of small height. The main result is used in Section 3 and appears also in Section 6. In Section 6, I present the profile of a class of finite relational structures. I discuss the effect of the wqo character of the class under consideration on its profile (for example, a description of hereditary classes of small growth). In Section 7, I look at the number of wqo hereditary classes. With the use of uniformly recurrent sequences I report on the fact [143] that the number of wqo hereditary classes of permutation graphs has the cardinality of the continuum. Looking at the links with the notion of primality, I present the notions of minimal prime structures and describe minimal prime hereditary classes of graphs, such a description is based on a result of Chudnovski et al [40]. In Section 8, I discuss how Laver's theorem on scattered chains could be extended to other classes of structures. A brief section ends the paper. Only some proof are given, preferably the simpler ones in order to give a feeling of the subject. Some proofs given did not yet appear in a refereed journal.

This work is the third, after [156, 157], of a survey nature that I wrote concerning wqo classes of relational structures. It is dedicated to the memory of Roland Fraïssé. Without him and the contribution of many other people, colleagues as well as students, this text would not exist. They are cited in the text and in the references. I thank them very much.

This paper is an outgrowth of the presentations made in the Mini-symposium 38 "Well-quasi-ordering: from theory and applications", Hamburg, September 21-25, 2015¹ and in the seminar "Well-quasi-Orders in Computer Science", Dagstuhl, January 17-22, 2016². I would like to thank Professor Monika Seisenberger and the organisers for their warm hospitality. The conference "Algebras, Graphs and Ordered Sets" (ALGOS 2020), Nancy, August 26 - 28, 2020, gave me yet another opportunity to present this subject. I warmly thank Miguel Couceiro, the general chair, and the organizers for their kind attention. I also wish to express my gratitude to both editors of this volume, Dwight Duffus and Miguel Couceiro, for their tireless work on this paper.

# 1. THE FRAMEWORK

Several notions about quasi-orders, or rather orders, like initial segments, ideals and antichains, yield natural classes of relational structures. In fact, initial segments and ideals of the collection $\Omega_\mu$ of finite relational structures of a given signature $\mu$, quasi-ordered by embeddability, are the basic objects on which relies any combinatorial or model theoretic study of finite relational structures. Besides, many concrete classes of structures fall into these categories. Also, there is an interplay between properties of subclasses of $\tilde{\Omega}_\mu$, the class of all structures of signature $\mu$, and their traces on $\Omega_\mu$. In a lesser extent, ordered topological

<footnote n="1">¹http://www.cs.swan.ac.uk/ccc2015/Hamburg.html</footnote>

<footnote n="2">²http://www.dagstuhl.de/16031</footnote>
spaces arise in this context. Some of the basic notions needed are recalled below. The notion of well-quasi-order, quite central in this study, will be presented in Section 3.

1.1. **Quasi-ordered sets, ordered sets, chains and antichains, wellfoundedness, initial segments, ideals, final segments, filters.** A reflexive and transitive relation $\rho$ on a set $V$ is a quasi-order, the pair $P := (V, \rho)$ is a quasi-ordered set (quoset); if in addition $\rho$ is antisymmetric, $P$ is a (partially) ordered set (poset). If $P$ is a poset or a quoset, we denote by $x \le y$ the fact that $(x, y) \in \rho$. The dual of $P := (V, \rho)$ is the quoset $P^{\text{dual}} := (V, \rho^{-1})$ where $\rho^{-1} := \{(x, y) : (y, x) \in \rho\}$. The distinction between quasi-order and order is (in part) a matter of convenience. Indeed, if a set $V$ is endowed with a quasi-order, denoted by $\leq$, the binary relation $\equiv$, defined on $V$ by $x \equiv y$ if $x \leq y$ and $y \leq x$, is an equivalence relation. The image of the quasi-order on the quotient set $V/\equiv$ is an order and $(V, \leq)$ is the lexicographical sum of the equivalence classes indexed by the quotient, denoted by $(V, \leq)/\equiv$. So the properties of the quasi-order reduces to those of the quotient. In the sequel, We will mostly work with posets.

Let $P := (V, \leq)$ be a poset. Two elements $x, y \in V$ are comparable if either $x \leq y$ or $y \leq x$. A subset $A$ of $P$ is a chain if any two elements $x, y \in A$ are comparable. On the opposite, $A$ is an antichain if distinct elements $x, y$ of $A$ are incomparable. The poset $P$ is well-founded if every nonempty subset has a minimal element; if this is the case, the height $h(x, P)$ of an element $x \in V$ is the ordinal defined by transfinite induction by the formula:

$$ (1.1) \qquad h(x, P) := \sup\{h(y, P) + 1 : y \in V, y < x\}. $$

The height of $P$ is $h(P) := \sup\{h(y, P) + 1 : y \in V\}$. For each ordinal $\alpha < h(P)$ the $\alpha$-level of $P$ is the set $P_\alpha := \{x \in V : h(x, P) = \alpha\}$. The poset $P$ is level-finite if each of its levels is finite. König's theorem asserts that: every well-founded level-finite poset contains a chain going through all the levels. If $P := (V, \leq)$ is a poset, a subset $I$ of $V$ is an initial segment of $P$ if $x \in V$ and $y \in I$ with $x \leq y$ imply $x \in I$. If $A$ is a subset of $P$, the set $\downarrow A := \{x \in V : x \leq y$ for some $y \in A\}$ is the least initial segment containing $A$, we say that it is generated by $A$; if $A = \{y\}$, Set $\downarrow y$ instead of $\downarrow \{y\}$, this is the principal initial segment of $P$ generated by $y$. An initial segment $I$ is finitely generated if $I = \downarrow A$ for some finite subset $A$ of $V$. Denote by down($P$) the set of principal initial segments of $P$. Denote by $\mathbf{I}_<^\omega(P)$ the set of finitely generated initial segments of $P$. The set $\mathbf{I}(P)$ of initial segments of $P$, once ordered by set inclusion, is a complete lattice, the join being the union and the meet being the intersection. Among complete lattices, $\mathbf{I}(P)$ is characterized by the fact that it is completely distributive and generated by its completely join-irreducible elements. The order on $\mathbf{I}(P)$ determines the order on $P$ since the completely join-irreducible elements of $\mathbf{I}(P)$ are the principal initial segments of $P$. An ideal of $P$ is any nonempty initial segment $I$ which is up-directed (that is for every pair $x, y \in P$ there is an upper bound $z \in I$, that is, satisfying $x, y \leq z$). As it is well known, ideals of $P$ coincide with the join-irreducible members of the lattice $\mathbf{I}(P)$, that is the nonempty initial segments $I$ such that $I = I' \cup I''$ implies $I = I'$ or $I = I''$. Denote by $\mathbf{Id}(P)$ the set of ideals of $P$. Note that if $P$ is a quasi-ordered set, initial segments are simply the inverse images of initial segments of the quotient $V/\equiv$. Final segments, resp., principal final segments, of $P$ can be defined as initial segments, resp., principal initial segments, of $V$ equipped with the dual order $\geq$. Set $\uparrow A := \{x \in V : x \geq y$ for some $y \in A\}$. Denote by $\uparrow y$ the principal final segment generated by an element $y \in V$. Denote by up($P$), resp., by $\mathbf{F}_<^\omega(P)$, resp., $\mathbf{F}(P)$, the set, ordered by inclusion, of principal final segments, resp., finitely generated final segments, resp., final segments of $P$. Filters can be defined as ideals of the dual of $P$. Denote by $\mathbf{Fi}(P)$ the set of filters of $P$. Every antichain $A$ yields two initial segments, namely $P \setminus \uparrow A$ and $\downarrow A$; and $A$ can be recovered by looking respectively at the minimal elements of $\uparrow A$ and at the maximal elements of $\downarrow A$. If $P$ is well-founded or dually well-founded then every initial segment is determined by an antichain.

The study of initial segments and ideals has many similarities with the study of varieties in ring theory, hereditary classes playing the role of ideals in ring theory and ideals the role of irreducible ideals. In particular chain conditions, and more precisely well-quasi-order, play an important role. These aspects were noted by Malcev, as well as Robinson and Fraïssé [129] [177], [76]. More recently, Cameron, introducing the algebra of an age [31], gave extra support to this approach. In the sequel, We will illustrate the role of initial segments and ideals, introducing other order theoretic notions when needed.
**1.2. Topology and order; scattered ordered sets and scattered topological spaces.** A topological space is called *scattered* if every nonempty subset has at least an isolated point. The *Cantor-Bendixson procedure* begins with a topological space *X* and associates to each ordinal number *α* a subspace *X*<sup>(*α*)</sup>, the *α*<sup>th</sup>-derivative of *X*, defined as follows: *X*<sup>(0)</sup> := *X*, *X*<sup>(*α*)</sup> := {*x* ∈ *X*<sup>(*β*)</sup> : *x* is not isolated in *X*<sup>(*β*)</sup>} if *α* is a successor ordinal, *α* = *β* + 1, and *X*<sup>(*α*)</sup> := ⋂{*X*<sup>(*β*)</sup> : *β* < *α*} otherwise. An element *x* ∈ *X* has *rank* *α*, denoted by *rank*(*x*, *X*) := *α* if:

$$
(1.2) \qquad x \in X^{(\alpha)} \setminus X^{(\alpha+1)}.
$$

Since the $X^{(\alpha)}$'s are subsets of $X$, there is an ordinal $\beta$ such that $X^{(\alpha)} = X^{(\beta)}$ for every $\alpha \ge \beta$. The least ordinal $\beta$ for which this property holds is the *Cantor-Bendixson rank* of $X$, denoted by $\text{rank}(X)$. Then, the space $X$ is scattered if and only if $X^{(\text{rank}(X))} = \emptyset$. Also, if a scattered space is compact, its rank is a successor ordinal; denote by $\text{rank}^{-}(X)$ the predecessor of that ordinal, that is the largest ordinal $\beta$ such that the derivative $X^{(\beta)}$ is nonempty. Let us note that a compact space with a countable base is scattered if and only if it is countable. Identifying the powerset $\wp(V)$ of a set $V$ with $2^V$, we may view it as a topological space. A basis of open sets consists of subsets of the form $[F, V \setminus H) := \{X \in \wp(V) : F \subseteq X \subset V \setminus H\}$, where $F, H$ are finite subsets of $V$. Recall that $\wp(V)$ with this topology is a compact totally disconnected space, in brief a *Stone space*.

The topological notion of scatteredness is related to the notion of scatteredness for posets. Recall that a poset is *order scattered* if it does not embed a copy of the chain of the rational numbers. Duality between Boolean algebras and Stone spaces provides examples of this relationship, a basic result due to Day (1967) [48] asserting that a *Boolean algebra*, viewed as a *poset*, is *order scattered* if and only if its *Stone space* is *topologically scattered*. Duality, as extended by Priestley [171, 172, 47], involves sets equipped with a topology and an order. A *Priestley space* can be viewed as a collection $\mathcal{F}$ of subsets of a set $V$, ordered by set inclusion, the topology on $\mathcal{F}$ being induced by the product topology on the powerset $\wp(V)$, with the additional requirement that $\mathcal{F}$ is closed. The fundamental duality result is that if $T$ is a bounded distributive lattice, its *spectrum*, *Spec*($T$), the collection of prime filter of $T$, once equipped with the inclusion order and the topology induced by the product topology is a Priestley space. In turn, the collection of clopen subsets of *Spec*($T$) is order isomorphic to $T$. Recall that a bounded distributive lattice is order scattered if and only if its spectrum is topologically scattered.

A basic example of a Priestley space is the collection I(P) of initial segments of a poset P equipped with the topology inherited from the product topology on the power set and set inclusion order. We recall that if P is a poset, then I(P) and Id(I<sub>ω</sub>(P)) are isomorphic as Priestley spaces, a basic fact about algebraic lattices, see [89]. In particular, if κ is a cardinal and P := [κ]<sup>ω</sup> is the set, ordered by inclusion, consisting of finite subsets of κ then Id(P) is isomorphic to ℘(κ), the power set of κ ordered by set inclusion.

We also recall the following result (see Theorem 1.1, p.211 and Proposition 2.2, p. 215 of [39]).

**Theorem 1.1.** A poset *P* contains a subset isomorphic to [*κ*]<sup>*ω*</sup> if and only if *Id*(*P*) contains a subset isomorphic to ℘(*κ*).

Note also that $\mathbf{I}(P)$ is topologically scattered if and only if it is order scattered (see [76], 6.7.4, p. 187; see also [135] for an extension to algebraic lattices). The set $\mathbf{I}(P)$ is topologically closed in the powerset $\wp(V)$. In general, $\mathbf{Id}(P)$ is not. But, the topological closures in $\wp(V)$ of $\mathbf{down}(P)$ and $\mathbf{Id}(P)$ are the same. A poset $P$ is *up-closed* if every intersection of two members of $\mathbf{up}(P)$ is a finite union (possibly empty) of members of $\mathbf{up}(P)$. We recall below the following result (Corollary 2.7 and Proposition 2.8 of [14]).

**Proposition 1.2.** The following properties for a poset $P := (V, \le)$ are equivalent:

(i) $\mathrm{Id}(P)$ is topologically closed in $\wp(V)$;

(ii) $\mathbf{F}_{<\omega}(P)$ ordered by set inclusion is a bounded distributive lattice;

(iii) $P \in \mathbf{F}_{<\omega}(P)$ and $P$ is up-closed.

The tail algebra of a poset $P := (V, \le)$ is the Boolean subalgebra $Tailalg(P)$ of the Boolean algebra $(\wp(V), \cap, \cup, -, \emptyset, V)$ generated by $\mathbf{up}(P)$. According to J.D. Monk (Chap. 2, p.40 of [136]), this notion
is due to G. Brenner. Denote by $Taillat(P)$ the bounded sublattice of $(\wp(V), \cup, \cap, \emptyset, P)$, generated by $up(P)$. We recall Theorem 2.1 of [14].

**Theorem 1.3.** Let $P := (V, \leq)$ be a poset. The topological closure $\overline{down}(P)$ of $down(P)$ in $\wp(V)$ is homeomorphic to the Stone space of $Tailalg(P)$. With the order of set inclusion added, $\overline{down}(P)$ is isomorphic to the Priestley space of the lattice $Taillat(P)$.

As an illustration we present:

**Proposition 1.4.** If $P$ is a poset satisfying one of the conditions of Proposition 1.2 then $Taillat(P) = F_{<\omega}(P)$ while $Id(P)$ (with the inclusion order and the topology) is the spectrum of $Taillat(P)$. In particular, if $P$ is countable then the following conditions are equivalent: $Id(P)$ is countable, $Id(P)$ is topologically scattered, $F_{<\omega}(P)$ is order scattered.

Note that $Id(P)$ can be countable and $I(P)$ can be uncountable. For a simple example, let $Q$ be the cartesian product of the chains $\mathbb{N}$ and $\underline{3} := \{0, 1, 2\}$. Let $P$ be the poset obtained by deleting the comparabilities between vertices of the form $(x, 1)$ and $(y, 1)$. This poset is a countable lattice (not distributive) satisfying the conditions of Proposition 1.2. It contains only two infinite ideals, hence $Id(P)$ is countable. Since $P$ contains an infinite antichain, $I(P)$ is uncountable.

### 1.3. Basics on relational structures.

**1.3.1.** *The objects and their morphisms: relational structures, homomorphisms, isomorphisms.* Let $m$ be a nonnegative integer. An $m$-ary relation with domain, or base, $V$ is a subset $\rho$ of $V^m$. The pair $R := (V, \rho)$ is a relational structure. We set $V(R) := V$. The cardinality of $R$, denoted by $|R|$, is the cardinality of $V(R)$. If $R := (V, \rho)$ and $R' := (V, \rho')$ are two $m$-ary relational structures, a map $f: V \to V'$ is a homomorphism of $R$ into $R'$ if:

$$ (1.3) \qquad (x_1, \dots, x_m) \in \rho \text{ implies } (f(x_1), \dots, f(x_m)) \in \rho' $$

for all $(x_1, \dots, x_m) \in V^m$.

An isomorphism of $R$ onto $R'$ is any bijective map $f$ from $V$ to $V'$ such that $f$ and its inverse $f^{-1}$ are homomorphisms of $R$ into $R'$ and of $R'$ into $R$ respectively. That is, $f$ is bijective and:

$$ (1.4) \qquad (x_1, \dots, x_m) \in \rho \text{ if and only if } (f(x_1), \dots, f(x_m)) \in \rho' $$

for all $(x_1, \dots, x_m) \in V^m$.

More generally, a relational structure is any pair $R := (V, (\rho_i)_{i \in I})$ made of a set $V$, the domain of $R$ (called the base in Fraïssé's book), also denoted by $V(R)$, and a family $(\rho_i)_{i \in I}$ of $m_i$-ary relations $\rho_i$ on $V$. The family $\mu := (m_i)_{i \in I}$ is the arity or signature of $R$. If $I$ is finite then we say that the signature is finite.

If $R := (V, (\rho_i)_{i \in I})$ and $R' := (V', (\rho'_i)_{i \in I})$ are two relational structures with the same signature $\mu$, a map $f: V \to V'$ is a homomorphism of $R$ into $R'$ if $f$ is a homorphism of $(V, \rho_i)$ into $(V', \rho'_i)$ for each $i \in I$, that is,

$$ (1.5) \qquad (x_1, \dots, x_{m_i}) \in \rho_i \text{ implies } (f(x_1), \dots, f(x_{m_i})) \in \rho'_i $$

for all $(x_1, \dots, x_{m_i}) \in V^{m_i}$ and $i \in I$.

An isomorphism of $R$ onto $R'$ is any bijective map $f$ from $V$ to $V'$ such that $f$ and its inverse $f^{-1}$ are homomorphisms of $R$ into $R'$ and of $R'$ into $R$ respectively. That is,

$$ (1.6) \qquad (x_1, \dots, x_{m_i}) \in \rho_i \text{ if and only if } (f(x_1), \dots, f(x_{m_i})) \in \rho'_i $$

for all $(x_1, \dots, x_{m_i}) \in V^{m_i}$ and $i \in I$. Two relational structures $R$ and $R'$ are isomorphic, and we write $R \simeq R'$, if there is an isomorphism $f$ from $R$ onto $R'$. We also say that they have the same “isomorphism type”. The isomorphism type of a relational structure is a formal object $\tau(R)$ such that a relational structure $R'$ is isomorphic to $R$ if and only if $\tau(R') = \tau(R)$. In some situations, isomorphism types have a concrete representation.
In the sequel, relational structures are considered up to isomorphism, that is, no distinction is made between relational structures that are isomorphic. But behind this is a noteworthy question: *How does one recognize that two structures R and R' are isomorphic?* For countable structures, there is a test involving infinitary sentences, but not much is really known. The question for finite structures has retained a lot of attention. The problem of deciding whether two graphs (undirected, no loops) on $n$ vertices are isomorphic or not, is not classified: it is in the class NP, but it is not known if it can be solved in polynomial time (in the number of vertices). In 2015, L. Babai announced that this problem can be solved in quasi-polynomial time, that is in time $\exp(O(\log(n)^{O(1)}))$ [7] (see also the exposition in [92]).

### 1.3.2. Restriction, local isomorphism and embeddability: a way of comparing structures.
To a class of structures and a type of morphism, one may associate a quasi-order on the structures of that class, saying that a structure $R$ is smaller than a structure $R'$ if there is some morphism of the given type from $R$ to $R'$. And one may look at properties of this quasi-order as well as the influence of some well studied properties of quasi-orders, like well-quasi-ordering, on the properties of the class of structures under consideration. This has been done for the class of (irreflexive) graphs with graph homomorphisms and with graph minors. Many important results have been obtained, see the book of Hell and Nešetřil [93] for graph homomorphisms and of Robertson and Seymour [176] for graph minors, notably the well-quasi-ordering of the class of finite graphs under the minor quasi-ordering, a result of first order magnitude.

This paper is devoted to classes of relational structures where the homomorphisms are embeddings. This approach, started by Fraïssé, led to several developments, some are mentioned in his book [76]. This approach is based on the following definitions.

The *restriction* of an $m$-ary relation $\rho$ to a subset $A$ of its domain $V$ is the relation $\rho|_{A} := \rho \cap A^m$.
The *substructure induced* by a relational structure $R := (V, (\rho_i)_{i \in I})$ on a subset $A$ of $V$, simply called the *restriction* of $R$ to $A$, is the relational structure $R \upharpoonright_A := (A, (\rho_i|_A)_{i \in I})$. A *local isomorphism* of $R$ is any isomorphism between two restrictions of $R$. A *embedding* from $R$ to $R'$ is any isomorphism $f$ of $R$ onto the restriction of $R'$ to the image of $V$. A relational structure $R$ is *embeddable* into a relational structure $R'$, with the same signature $\mu$, and we set $R \leq R'$, if $R$ is isomorphic to a restriction of $R'$.

We will denote by $\Omega_\mu$ the class of finite relational structures of signature $\mu$ and by $\tilde{\Omega}_\mu$ the class of all structures of signature $\mu$. If this causes no confusion, we will denote by $\emptyset$ the relational structure of signature $\mu$ and empty domain. The paper is about $\Omega_\mu$, and in a lesser extent about $\tilde{\Omega}_\mu$, quasi-ordered by embeddability. Before entering into details, we first consider some examples.

## 1.4. A collection of examples.
For $m = 1, 2, 3$, an $m$-ary relation $\rho$ is *unary*, *binary*, *ternary*, respectively. When needed, we will identify $\rho$ with its characteristic function. Hence, $\rho$ can be viewed as a map from $V^m$ to $\{0, 1\}$. If $m = 1$, a unary relation on $V$ can be identified with a subset of $V$.

### 1.4.1. Directed graphs, posets, ordered structures.
If $\rho$ is a binary relation, the pair $(R := (V, \rho))$ is a *directed graph*; the elements of $V$ are its *vertices*, pairs $(x, x) \in \rho$ are its *loops* and pairs $(x, y) \in \rho$ with $x \neq y$ its *arcs*. If $\rho$ is irreflexive and symmetric, it can be identified with the set $E(\rho)$ of pairs $\{x, y\}$ such that $(x, y) \in \rho$. The pair $(V, E(\rho))$ is then an *undirected graph*, or simply a *graph*; the elements of $E(\rho)$ are its *edges*. The *complement* of an undirected graph $G := (V, E)$ is the graph $G^{\text{comp}} := (V, [V]^2 \setminus E)$. If $R$ and $R'$ are two graphs, a homomorphism from $R$ to $R'$ is called a *graph homomorphism*, this is a map which maps every edge on an edge or a loop. As indicated in Subsection 1.1, if $\rho$ is reflexive and transitive, $R := (V, \rho)$ is a *quasi-ordered set* (quoset); if in addition $\rho$ is antisymmetric, $R$ is a (partially) *ordered set* (poset). If $R$ is a poset or a quoset, we denote by $x \leq y$ the fact that $(x, y) \in \rho$. A homomorphism $f$ from a poset $R$ into a poset $R'$ is an *order preserving map*, that is, it satisfies $f(x) \leq f(y)$ for all $x \leq y$ in $V(R)$. Note that we may view reflexive directed graphs and irreflexive directed graphs as similar objects, but the homomorphisms can be quite different.

Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure. When all the relations $\rho_i$, $i \in I$, are binary, we have a *binary relational structure*, (*binary structure* for short). We also said that $R$ is a binary structure if all the $\rho_i$'s are binary or unary. If one of the relations $\rho_i$ in $R := (V, (\rho_i)_{i \in I})$ is a linear order, we have an *ordered relational structure*.
*structure.* A structure which has the form $R := (V, \leq, \rho_1, \dots, \rho_k)$, where $k$ is a nonnegative integer, $\leq$ is a linear order on the set $V$ and each $\rho_i$ is a binary relation on $V$, is an *ordered binary structure of type k*. Basic examples of ordered binary structures are *chains* ($k = 0$), *bichains* ($k = 1$ and $\rho_1$ is a linear order on $V$) and *ordered directed graphs* ($k = 1$). In the latter case, if $\rho_1$ is an irreflexive and symmetric binary relation on $V$, then we just say *ordered graphs*.

One may ask about the need to consider relations of arity larger than two, several relations on the same set, and particularly infinitely many. Examples speak for themselves and an additional reason to consider relational structures made of infinitely many relations is that they can sometimes provide easy to get counterexamples.

**1.4.2. Hypergraphs.** A hypergraph is a pair $\mathcal{H} := (V, \mathcal{E})$ where $\mathcal{E}$ is a collection of subsets of $V$; members of $V$ are the *vertices* of $\mathcal{H}$, whereas members of $\mathcal{E}$ are the *hyperedges*. We denote by $V(\mathcal{H})$, respectively, $\mathcal{E}(\mathcal{H})$, the sets of vertices, respectively, hyperedges, of a hypergraph $\mathcal{H}$; we denote by $v(\mathcal{H})$, respectively, $e(\mathcal{H})$, the cardinality of $V(\mathcal{H})$, respectively, $\mathcal{E}(\mathcal{H})$. Let $\mathcal{P}(K)$ be the set of subsets of $K$. For $K$ a subset of $V$, the hypergraph induced by $\mathcal{H}$ on $K$ is $\mathcal{H}_{\vdash K} = (K, \mathcal{E} \cap \mathcal{P}(K))$. Let $h$ be an integer; the hypergraph $\mathcal{H}$ is $h$-uniform (or $h$-regular) if all its edges have size $h$ (for instance every graph is a 2-uniform hypergraph). We make the convention that a hypergraph with no hyperedge is $h$-uniform for every $h$.

Let $\mathcal{H} := (V, \mathcal{E})$ and $\mathcal{H}' := (V', \mathcal{E}')$ be two hypergraphs. An *isomorphism* from $\mathcal{H}$ onto $\mathcal{H}'$ is any bijective map $f$ from $V$ onto $V'$ such that the natural extension $\bar{f}$ to $\mathcal{P}(V)$ induces a bijective map from $\mathcal{E}$ onto $\mathcal{E}'$. A *homomorphism* from $\mathcal{H}$ into $\mathcal{H}'$ is any map $f$ from $V$ onto $V'$ which transforms every hyperedge $E \in \mathcal{E}$ into a hyperedge $f(E) \in \mathcal{E}'$. To each $h$-uniform hypergraph $\mathcal{H} := (V, \mathcal{E})$ we may associate the $h$-ary relational structure $R_{\mathcal{H}} := (V, \rho_{\mathcal{E}})$ where $\rho_{\mathcal{E}} := \{(x_1, \dots, x_h) : \{x_1, \dots, x_h\} \in \mathcal{E}\}$. Doing so, a map from $V$ to $V'$ is a homomorphism of $\mathcal{H}$ into $\mathcal{H}'$ if and only if this is a homomorphism of $R_{\mathcal{H}}$ into $R_{\mathcal{H}}'$.

Several examples of hypergraphs come from geometry. For instance, *Steiner triple systems*, which are 3-uniform hypergraphs such that each pair of distinct vertices belongs to exactly one hyperedge.

**1.4.3. Words.** Let $A$ be a set. Considering $A$ as an *alphabet* whose members are *letters*, we write a word $\alpha$ with a mere juxtaposition of its letters as $\alpha = a_0a_1\cdots a_{n-1}$ where $a_i$ are letters from $A$ for $0 \le i < n$. The integer $n$ is the *length* of the word $\alpha$ and is denoted by $|\alpha|$. Hence, we identify letters with words of length 1. Let $A^*$ be the set of all words on the alphabet $A$. Once equipped with the concatenation of words, $A^*$ is a monoid, whose neutral element is the empty word $\square$. In fact, $A^*$ is the *free monoid generated by A*. Ordered with the *subword ordering*, $A^*$ becomes an ordered monoid, this order being defined as follows: if $\alpha$ and $\beta$ are two elements in $A^*$ such that $\alpha := a_0\cdots a_{n-1}$ and $\beta := b_0\cdots b_{m-1}$ then $\alpha \le \beta$ if there is an injective and increasing map $h$ from $\{0, \dots, n-1\}$ to $\{0, \dots, m-1\}$ such that for each $i$, $0 \le i \le n-1$, we have $a_i = b_{h(i)}$. We can code each word $\alpha := a_0\cdots a_{n-1}$ by the unary ordered structure $L_\alpha := (\{0, n-1\}, \le, (\chi_a)_{a\in A})$ where $\le$ is the natural order on $\{0, \dots, n-1\}$ and $\chi_a$ is the unary relation $\chi_a := \{i \in \{0, \dots, n-1\} : a_i = a\}$. With this coding, a word $\alpha$ is a subword of the word $\beta$ if and only if $L_\alpha$ is embeddable in $L_\beta$. If $A$ is ordered, the *Higman ordering* on $A^*$ consists of replacing the condition $a_i = b_{h(i)}$ in the subword ordering by $a_i \le b_{h(i)}$. With this order, $A^*$ is the *ordered monoid generated by the poset A*. If $U := (\{0, \dots, n-1\}, \le, (\rho_i)_{i<k})$ is an ordered unary structure, we may encode it by the word $w_U := U(0)\cdots U(j)\cdots U(n-1)$, with $U(j) := \{i < k : j \in \rho_i\}$, on the alphabet $A := \mathcal{P}(\{0, \dots, k-1\})$ ordered by set inclusion. With this encoding, there is an injective homomorphism from $U$ into $U'$ if and only if $w_U \le w_{U'}$ for the Higman ordering. Another order - the *factor ordering* - can be introduced in a similar way. Let $C_\alpha$ be obtained from $L_\alpha$ by replacing the order relation on $\{1, \dots, n\}$ by the oriented path $C$, defined by $(x, y) \in C$ if $y = x + 1$. Then $\alpha$ is a *factor* of $\beta$ (that is, $\beta$ is the concatenation product $\beta' \cdot \alpha \cdot \beta''$) if and only if $C_\alpha$ embeds in $C_\beta$.

The study of words and languages (alias sets of words) is at the carrefour of several disciplines (for instance, combinatorics, langage theory and symbolic dynamics). Some important results in language theory use logical techniques applied to words viewed as relational structures (see, for example, the book of Thomas [195]).
1.4.4. *Permutations, bichains, permutation graphs.* Let $n$ be a nonnegative integer. Let $\mathfrak{S}_n$ be the set of permutations on $[n] := \{1, \dots, n\}$ and $\mathfrak{S} := \bigcup_{n \in \mathbb{N}} \mathfrak{S}_n$. An order relation on $\mathfrak{S}$ is defined as follows: the permutation $\pi$ of $[n]$ contains the permutation $\sigma$ of $[k]$ and one writes $\sigma \le \pi$ if some subsequence of $\pi$ of length $k$ is order isomorphic to $\sigma$. More precisely, $\sigma \le \pi$ if there exist integers $1 \le x_1 < \dots < x_k \le n$ such that for $1 \le i, j \le k$:

$$ \sigma(i) < \sigma(j) \text{ if and only if } \pi(x_i) < \pi(x_j). $$

For example, $\pi := 391867452$ contains $\sigma := 51342$, as it can be seen by considering the subsequence $91672$ (equals to $\pi(2), \pi(3), \pi(5), \pi(6), \pi(9)$).

A subset $\mathfrak{C}$ of $\mathfrak{S}$ is called *hereditary* if $\sigma < \pi \in \mathfrak{C}$ implies $\sigma \in \mathfrak{C}$. Its counting function, referred to as its *profile*, is $\varphi_{\mathfrak{C}}(n) := |\mathfrak{C} \cap \mathfrak{S}_n|$.

The *Stanley-Wilf conjecture* asserted that if $\mathfrak{C} \neq \mathfrak{S}$ then $\varphi_{\mathfrak{C}}(n)$ drops from $\varphi_{\mathfrak{S}}(n) = n!$ to exponential growth, that is, $\varphi_{\mathfrak{C}}(n) < c^n$ for every $n$ for some constant $c$ depending on the class $\mathfrak{C}$. The conjecture was proved to be true in 2004 by Marcus and Tardös [132]. Since then a huge literature has appeared about the study of hereditary classes of permutations. An emphasis was put on hereditary classes of finite permutation graphs and a classification of these classes, notably in terms of their profile. The role of the notions of primality and of well-quasi-order has been particularly investigated, see [107, 200].

Thanks to Cameron [35] such a study fits in the framework of the theory of relations. Indeed, a *bichain* is a binary relational structure $B := (V, (L', L''))$ made of a set $V$ and two linear orders $L'$ and $L''$ on $V$. To a permutation $\sigma$ of $[n] := \{1, \dots, n\}$, associate the *bichain* $C_{\sigma} := ([n], \leq, \leq_{\sigma})$ where $\leq$ is the natural order on $[n]$ and $\leq_{\sigma}$ the linear order defined by $x \leq_{\sigma} y$ if and only if $\sigma(x) \leq \sigma(y)$.

**Lemma 1.5.** (1) If $B := (V, (L', L''))$ is a finite bichain, then $B$ is isomorphic to a bichain $C_{\sigma}$ for a unique $\sigma$ on $[V]$.

(2) If $\sigma$ and $\pi$ are two permutations, then $\sigma \leq \pi$ if and only if $C_{\sigma} \leq C_{\pi}$.

This fact indicates that permutations can be viewed as isomorphism types of bichains. Furthermore, to hereditary classes of permutations correspond hereditary classes of bichains. For a study of some hereditary classes of permutations in terms of bichains, see [35, 140, 142].

Recall that a graph $G := (V, E)$ is a *permutation graph* if there is a total order $\leq$ on $V$ and a permutation $\sigma$ of $V$ such that the edges of $G$ are the pairs $\{x, y\} \in [V]^2$ which are reversed by $\sigma$. To a bichain $R := (V, (\leq', \leq''))$, we may associate the intersection order $o(R) := (V, \leq' \cap \leq'')$ and to $o(R)$ its comparability graph. An order of the form $o(R)$ is called *two-dimensional*. A graph is the comparability graph of a two-dimensional poset if and only if it is also the incomparability graph of a two-dimensional poset [59]. If the graph is finite, this amounts to the fact that this is a permutation graph. To a hereditary class of bichains corresponds a hereditary class of two dimensional orders and to a hereditary class of finite two-dimensional orders, a hereditary class of permutation graphs.

Several studies have been made on hereditary classes of finite permutation graphs which are well-quasi-ordered (for example, [24], [109], [108], [124] [125]).

1.4.5. *Metric spaces.* Recall that a *metric space* is a set $E$ endowed with a *distance function*, that is, a map $d$ from $E \times E$ in the set $\mathbb{R}^+$ of nonnegative real numbers such that $d(x, y) = 0$ if and only if $x = y$, and for every $x, y, z \in E$,

$$ d(x, y) = d(y, x) \quad \text{and} \quad d(x, y) \leq d(x, z) + d(z, y). $$

Part of the study of metric spaces deals with *contractions*, also called *non-expansive maps*. A map $f$ from a metric space $(E, d)$ into a metric space $(E', d')$ is a *contraction* if $d'(f(x), f(y)) \leq d(x, y)$ for all $x, y \in E$. Let $\mathbb{Q}_*^+$ be the set of positive rational numbers. To a metric space $(E, d)$ let us associate the binary structure $R_d := (E, (\delta_r)_{r \in \mathbb{Q}_*^+})$, where $\delta_r := \{(x, y) \in E \times E : d(x, y) \leq r\}$. Due to the density of $\mathbb{Q}_*^+$ in $\mathbb{R}^+$, we trivially have:

**Lemma 1.6.** A map $f$ from a metric space $(E, d)$ to a metric space $(E', d')$ is a contraction if and only if this is a relational homomorphism from $R_d$ to $R_{d'}$. In particular, $f$ is an isometry of metric spaces if and only if $f$ is an isomorphism of binary structures.
In fact, metric spaces, orders and graphs fit in the same frame. See the survey [101] and for some specific
results on ordinary metric spaces viewed as relational structures, see [53, 54].

1.4.6. *Permutation groups.* Let $G$ be a group of permutations on a set $V$; let $\bar{G}$ be the topological adherence of $G$ into $\mathfrak{S}(V)$, the group of all permutations of $V$, equipped with the topology induced by the product topology on $V^V$, $V$ being equipped with the discrete topology. Then $\bar{G}$ is a group, called the *closure* of $G$. If $\bar{G} = G$ then $G$ is *closed*. It is easy to see that:

**Lemma 1.7.** *Given a permutation group $G$ on a set $V$, there is a relational structure $R$ on $V$ such that the two following statements are equivalent.*

(a) Every isomorphism $f$ from a finite restriction of $R$ onto another extends to an automorphism of $R$;

(b) Aut($R$) = $\bar{G}$.

Structures satisfying condition (a) are called *homogeneous* (or *ultrahomogeneous*). They are now considered as one of the basic objects in model theory. Their ages are called *Fraïssé classes* after their characterization by Fraïssé in 1954.

If $G$ is a permutation group acting on a set $V$, the *orbital profile* of $G$ is the function $\theta_G$ which counts for each nonnegative integer $n$ the number, possibly infinite, of orbits of the $n$-element subsets of $V$. In many cases the coding of $G$ by some relational structure $R := (V, (\rho_i)_{i \in I})$ requires $I$ to be infinite, even if $\theta_G(n)$ is finite for each nonnegative integer $n$.

Groups for which $\theta_G(n)$ is always finite are called *oligomorphic* by Cameron. Their study is a whole subject by itself, see Cameron's book [30]. Oligomorphic groups are relevant to model theory due to the following result of Ryll-Nardzewski.

**Theorem 1.8.** Let $G$ act on a denumerable set $V$ and $R$ be a relational structure such that $AutR = \bar{G}$. Then $G$ is oligomorphic if and only if the complete theory of $R$ is $\aleph_0$-categorical.

A lot of work has been made on infinite permutation groups and relational structures. Due to the work of Kechris, Pestov and Todorcevic in 2005 [104] the last fifteen years have seen a renewed interest in homogeneous structures, Polish groups and Ramsey theory.

Another motive for considering the orbital profile of a permutation group is provided by this example of Cameron [30]. Let $k$ be a nonnegative integer and $\mathfrak{S}$ be a permutation group of $\{1, \dots, k\}$. Let $Inv(\mathfrak{S})$ be the algebra of polynomials in the variables $X_1, \dots, X_k$ which are invariant under the action of $\mathfrak{S}$ (for instance, think about symmetric polynomials). A fundamental result of invariant theory of the nineteen century asserts that this algebra is finitely generated, an upper bound on the degree of the generators being given by Noether. Now, let $G$ be the group of permutations on the product $\{1, \dots, k\} \times \mathbb{N}$ in such a way that one can permute the “columns” according to $\mathfrak{S}$ and permute abitrarily the elements of these columns (this group is the wreath product of $\mathfrak{S}$ and $\mathfrak{S}(\mathbb{N}))$. Each orbit of an $n$-element subset for this group corresponds to a homogeneous polynomial of degree $n$, hence the generating series associated to the orbital profile of $G$ is the Hilbert series of the algebra $Inv(\mathfrak{S})$. This gives a basic example of a permutation group whose orbital profile is bounded by a polynomial. But there are others: a description is given in Falque’s thesis [66]. In Section 6 we consider profiles bounded by polynomials, the algebra of an age invented by Cameron which extends the notion of the algebra of invariants, and we mention the solution by Falque and Thiéry [67] of a conjecture of Cameron and of Macpherson.

## 2. COMPARISON OF RELATIONAL STRUCTURES BY EMBEDDABILITY

In this section we set the fundamental notions of the theory of relations like embeddability, hereditary classes, ages, and bounds. We present the links with universal classes studied in model theory. Hereditary classes which are level-finite play a prominent role in our study. The finiteness of the level can be expressed in terms of profile. For a given hereditary class $\mathfrak{C}$ of finite structures, the *profile* of $\mathfrak{C}$ is the function $\varphi_{\mathfrak{C}}$ which counts for each integer $n$ the number (possibly infinite) $\varphi_{\mathfrak{C}}(n)$ of elements of the $n$-th level of $\mathfrak{C}$. We devote Section 6 to this notion. A test for its finiteness is given in Lemma 6.7. We start this section with the comparison between isomorphy and equimorphy.
**2.1. Embeddability, equimorphy, isomorphy and a glimpse at infinite structures.** The embeddability relation defines a quasi-order on the class of all relational structures. This quasi-order is not an order, two relational structures $R$ and $R'$ such that $R \leq R'$ and $R' \leq R$ do not need to be equal (they may have different domains). We say that they are *equimorphic* or that one is a *sibling* of the other and we set $R \equiv R'$ if $R$ and $R'$ embed in each other. Trivially, if $R$ and $R'$ are isomorphic, then they are equimorphic. Furthermore, if $R$ and $R'$ are equimorphic and one is finite, then they must be isomorphic. So the embeddability relation induces an ordering on the set $\Omega_\mu$ of finite relational structures with signature $\mu$ ($\mu := (m_i)_{i \in I}$), these structures being considered up to isomorphism.

Generally, one cannot expect equimorphic structures to necessarily be isomorphic. However, the famous Cantor-Bernstein-Schröder Theorem (see [76]) states that this is the case for structures in a language with pure equality: if there is an injection from one set into the other and vice-versa, then there is a bijection between these two sets. The same situation occurs in other structures such as vector spaces, where embeddings are linear injective maps. But as expected, it is generally not the case that equimorphic structures are isomorphic. For example, the chain $\mathbb{Q}$ of rational numbers is equimorphic to the chain $1 + \mathbb{Q}$ obtained from $\mathbb{Q}$ by adding a least element, but it is not isomorphic to $1 + \mathbb{Q}$.

The behavior of equimorphy introduces a distinction between the study of infinite structures and the study of the finite ones. The following question was formulated by Thomassé [196] circa 2000.

**Question 1.** Let $R$ be a countable relation. Is the number of siblings of $R$, counted up to isomorphy, 1, $\aleph_0$ or $2^{\aleph_0}$?

This question is related to the Bonato and Tardif conjecture [17] of 2006 asserting that for every infinite tree (acyclic and connected graph) $T$, the number of trees which are siblings of $T$ is either 1 or infinite. Indeed, if a connected graph $G$ is not equimorphic to the graph $G \oplus 1$ obtained from $G$ by adding an isolated vertex, then every sibling of $G$ is connected. Hence, for a tree $T$ not equimorphic to $T \oplus 1$, the Bonato-Tardif conjecture and Thomassé's question are equivalent (the last one being limited to asking if the number of sibling is one or infinite).

I learned in 2021 from Claude Laflamme that these conjectures and questions were negatively solved by Atsushi Tateno, a student of Alex Scott, who defended his thesis in Oxford in 2008. The author constructed a tree $T$ with only one tree equimorphic but not isomorphic to $T$. Since that tree $T$ does not embed $T \oplus 1$, this answers negatively Thomassé's question. In addition it settles, in the negative, a conjecture of Tyomkin [199] asserting that if a locally finite tree has a proper sibling, then it has infinitely many siblings unless it is a ray (a one way infinite path). In [1], the authors revisit the example of Tateno and prove that Thomassé's question has a negative answer for posets.

Bonato and Tardif [17] proved their conjecture for rayless trees. Their result was extended to rayless graphs by Bonato, Bruns, Diestel and Sprüssel [18]. Laflamme, Pouzet and Sauer [114] in 2017 proved that Bonato-Tardif conjecture holds for trees not embedding the binary tree. Laflamme, Pouzet and Woodrow [116] proved that Thomassé's conjecture holds for chains while Laflamme, Pouzet, Sauer and Woodrow [115] proved that an $\aleph_0$-categorical relational structure has one or infinitely many siblings. Braunfeld and Laskowski improved this result, proving that a countable universal structure has 1, $\aleph_0$ or $2^{\aleph_0}$ siblings ([21], Corollary 7.3, p.23). Hahn, Pouzet and Woodrow [90] proved that countable cographs have one or infinitely many siblings.

The proofs involve several ingredients, among those, the notion of well-quasi-order plays an important role. To illustrate, we give below some information about Laflamme, Pouzet and Woodrow results on chains [116]. Denote by $sib(C)$ the number of chains, up to isomorphism, that are equimorphic to $C$.

**Theorem 2.1.** If $C$ is a chain, then $sib(C)$ is equal to 1 or it is infinite. If $C$ is countable then $sib(C)$ is equal to 1, $\aleph_0$ or $2^{\aleph_0}$.

**2.1.1. Examples.** We give below a sequence of simple properties.

* A chain is *well ordered* if every nonempty subset has a least element. *Ordinals* are order types of well ordered chains. As it is well known, $sib(C) = 1$, for every ordinal or reverse ordinal.
More generally, we have the following result.

**Proposition 2.2.** If $C$ is a finite sum of ordinals and reverse ordinals, then $sib(C) = 1$.

The converse is false, for example, $sib(\omega \cdot \omega^* + \omega^2) = 1$, where $\omega^*$ is the dual of the chain $\omega$.

* A chain is *scattered* if it does not embed the chain of rational numbers. As is well known, a countable chain $C$ is equimorphic to $\mathbb{Q}$ if and only if it embeds $\mathbb{Q}$; also $sib(C) = 2^{\aleph_0}$ for such a chain.

* A chain $C$ or its order type is a *surordial* (a notion due to Jullien and Slater [100, 187]) if for each $x \in C$ the final segment $\uparrow x$ generated by $x$ is well ordered. Equivalently, the chain $1 + \omega^*$ (obtained by adding a least element to the chain of negative integers) does not embed into $C$. As it turns out, scattered chains $C$ with few ($< 2^{\aleph_0}$) siblings are finite sums of surordinals and their reverses. However, there are uncountable dense chains $C$ such that $sib(C) = 1$, and one such construction is owed to Dushnik and Miller (see [179]).

The proof of Proposition 2.2 illustrates the notion of wellfoundedness. Let $n$ be the least integer such that $C$ has a decomposition as a sum of $n$ ordinals or reverse ordinals. Choose a decomposition $C := \sum_{i<n} C_i$ minimal in the sense that if $C := \sum_{i<n} C'_i$ is another decomposition with $C'_i \le C_i$ for $i < n$ then $C'_i$ is equimorphic to $C_i$ for all $i < n$. Since ordinals are well ordered under embeddability, such a decomposition exists. Now consider any chain $C' \equiv C$. Since $C' \le C$, $C'$ must be of the form $C' := \sum_{i<n} C'_i$ with $C'_i \le C_i$ for all $i < n$. Since $C \le C'$, the same argument yields that $C := \sum_{i<n} C''_i$ with $C''_i \le C'_i$ for all $i < n$. Since $C'_i \le C_i$ we have $C''_i \le C_i$. From the minimality of the decomposition of $C$, we have $C''_i \equiv C_i$ hence $C'_i \equiv C_i$. This yields $C'_i \simeq C_i$ thus $C' \simeq C$.

The proof of Theorem 2.1 uses the fact that the class of surordinals is well-founded under embeddability, a result of Jullien [100] obtained before Laver [118] proved that the class of countable unions of scattered chains is well-founded and in fact wqo.

**2.2. The poset of finite structures.** Let $\Omega_\mu$ be the collection of all finite relational structures with signature $\mu := (m_i)_{i \in I}$. The quasi-order of embeddability between members of $\Omega_\mu$ induces an equivalence relation whose classes are isomorphic types of members of $\Omega_\mu$. Hence, this quasi-order induces an ordering on the quotient set $\tilde{\Omega}_\mu := \Omega_\mu / \simeq$. For simplicity, we will not hesitate to denote this poset by $\Omega_\mu$. Not much is known about this poset. Our first problem is:

**Problem 1.** Find a characterization in order theoretic terms of $\Omega_\mu$.

We state below some simple facts pertaining to this problem.

(a) The poset $\Omega_\mu$ decomposes into levels labelled by nonnegative integers, the $n$-th level consists of the isomorphic types of $n$-element structures of signature $\mu$ (in particular, the level 0 consists of the least element, denoted 0, of $\Omega_\mu$). In fact, $\Omega_\mu$ is *ranked* by the cardinality function, that is, if $T \le T' \in \Omega_\mu$, then $T$ is covered by $T'$ if and only if $|T'| = |T| + 1$. Hence, maximal chains between two isomorphic types have the same length.

(b) If the level of $T \in \Omega_\mu$ is $n$, that is, $T$ is a $n$-element structure, then $\text{Age}(T)$, the age of $T$, has cardinality at most $2^n$.

(c) The third fact is linked to the notion of semimodularity. Let us recall that a poset $P$ is *up-semimodular* if the covering relation $<$ satisfies the following property:

$$ (2.1) \qquad \forall x, y, z (x < y \text{ and } x < z \text{ and } y \neq z \text{ imply } \exists t (y < t \text{ and } z < t)). $$

Note the condition $y \neq z$. The poset $P$ is *down-semimodular* if its dual is *up-semimodular*. The up-semimodularity is a consequence of the property of amalgamation. We recall that a class $\mathcal{C}$ of structures is *amalgamable* if for every pair of embeddings $f: T \to U, f': T \to U'$ with $T, U, U' \in \mathcal{C}$ there are $T' \in \mathcal{C}$ and two embeddings $g: U \to T', g': U' \to T'$ such that $g \circ f = g' \circ f'$. It is then obvious that if
a hereditary subclass (see the definition below) of $\Omega_\mu$ is amalgamable, then it is up-semimodular. Since $\Omega_\mu$ is amalgamable [76], we obtain the following lemma.

**Lemma 2.3.** *As a poset, $\Omega_\mu$ is both down- and up-semimodular.*

(d) If the index set $I$ of the signature $\mu$ is finite, then the levels of $\Omega_\mu$ are finite, hence $\Omega_\mu$ is countably infinite. If each structure $R$ is made of unary relations, it can be replaced by its domain $V(R)$ labelled by a map $f$ from $V(R)$ into the power set $2^I$; if $I$ is finite, then the structure of $\Omega_\mu$ is not too difficult to grasp. Some details are given in Proposition 2.22 below.

A combinatorial property of $\Omega_\mu$ linked to semimodularity is given in Lemma 2.10 below. As for every poset, $\Omega_\mu$ is determined up to isomorphy by the set of its initial segments. These initial segments are hereditary classes that we introduce next.

**2.3. Hereditary classes.** A class $\mathcal{C}$ of structures is *hereditary* if it contains every structure that can be embedded into some member of $\mathcal{C}$. Hence, hereditary classes are initial segments of the class of relational structures quasi-ordered by embeddability.

Let us start with examples of hereditary classes of finite structures.

**Examples 2.4.** The following classes of finite structures are hereditary:

(1) chains;

(2) posets;

(3) ordered forests (two elements which have a upper bound are comparable);

(4) posets coverable by at most $n$ chains, where $n$ is a fixed nonnegative integer;

(5) posets of Dushnik-Miller dimension at most $n$;

(6) posets of jump-number at most $n$ (the order can be made linear by adding at most $n$ comparabilities);

(7) graphs;

(8) comparability graphs;

(9) planar graphs;

(10) $n$-colourable graphs;

(11) perfect graphs (graphs such that the chromatic number of every induced subgraph is the size of the largest clique of that subgraph).

The most important problem about a class $\mathcal{C}$ of finite structures is to decide whether a finite relational structure $R$ belongs to $\mathcal{C}$ or not. When $\mathcal{C}$ is hereditary, this question leads to the notion of bound.

**2.4. Bounds.** A bound of a hereditary class $\mathcal{C}$ of finite structures is any element of $\Omega_\mu \cup \mathcal{C}$ that is minimal w.r.t. embeddability. Hence, $R$ is a bound of $\mathcal{C}$ if $R \notin \mathcal{C}$ while $R_{-x} \in \mathcal{C}$ for every $x \in V(R)$. We denote by $\text{Bound}(\mathcal{C})$ the set of bounds of $\mathcal{C}$ within the signature $\mu$, these bounds being considered up to isomorphy.

Given a class $\mathfrak{B}$ of finite structure of $\Omega_\mu$, set $\text{Forb}(\mathfrak{B}) := \{R \in \Omega_\mu : S \notin R \text{ for every } S \in \mathfrak{B}\}$. Clearly, $\text{Forb}(\mathfrak{B})$ is a hereditary class of $\Omega_\mu$. In fact, every hereditary class of $\Omega_\mu$ is of this form.

**Lemma 2.5.** Each hereditary class $\mathcal{C}$ included in $\Omega_\mu$ is determined by its bounds. More precisely, $\mathcal{C} = \text{Forb}(\mathfrak{B})$ where $\mathfrak{B} := \text{Bound}(\mathcal{C})$.

As a consequence, if the cardinality of the bounds of $\mathcal{C}$ is bounded by some integer $k$ and the signature is finite, then there is a polynomial algorithm (in time $n^k$) to decide whether an $n$-element relation belongs to $\mathcal{C}$. If the cardinality of bounds is unbounded, the decision problem can be solved in polynomial time, is NP-complete or is intractable.

**Examples 2.6.** The bounds of the class of finite

(1) chains are one of the following: the empty relation on a singleton; the complete binary relation on a 2-element set; the direct sum of two loops; or, a 3-element oriented cycle with a loop at every vertex;

(2) posets are the bounds of chains excluding the direct sum of two loops and including a 3-element directed path with a loop at every vertex;
(3) ordered forests are the bounds of the collection of posets plus the connected 3-element poset with two minimal;
s;

(4) posets which can be covered by $n$ chains are those of posets and an $(n+1)$-element antichain (by
the famous theorem of Dilworth [57]);

(5) posets of jump number at most $n$ are the bounds of chains if $n=0$. For $n=1$ add to the bounds of posets, the ordinal sum of two antichains; for $n=2$ the bounds have been determined by Habib and Rival, they have at most 9 elements; for $n \ge 3$ they have at most $(n+2)!$ elements, El-Zahar, Schmerl [63].

(6) posets of Dushnik-Miller dimension at most $n$ form an infinite set for $n \ge 2$. The bounds for $n=2$ have been described by Kelly [105] and independently by Trotter and Moore [198]. The decision problem is polynomial for $n=2$. For $n \ge 3$, it is NP-complete Yannakakis [203];

(7) graphs are a loop and an arc without any loop;

(8) planar graphs form an infinite set: each bound can be described by means of Kuratowski's theorem;

(9) comparability graphs form an infinite set: they have been completely described by Gallai [84] (the
list includes all odd cycles of length at least 5 and the complements of cycles of length at least 5);

(10) $n$-colourable graphs form an infinite set: this is known only for $n \le 2$ (the bounds are the odd cycles); for $n \ge 3$, $n$-colorability is NP-complete, see Garey and Johnson [85];

(11) perfect graphs are the odd cycles of length at least 5 and their complements. This result by Chudnovsky, Seymour, Robertson and Thomas [41] answers positively the strong perfect graph conjecture stated by Berge [15].

2.5. **Ages.** The *age* of a relational structure *R* is the set *Age*(*R*) of restrictions of *R* to finite subsets of its domain, these restrictions being considered up to isomorphism. Any age is an ideal of Ω<sub>μ</sub>, that is a nonempty initial segment of Ω<sub>μ</sub> which is up-directed. One of the most basic results of the theory of relations asserts that the converse (almost) holds. The proof illustrates the role of the embeddability ordering.

**Theorem 2.7.** (Fraïssé, 1954) Every countable ideal of Ω_μ is the age of a countable relational structure.

**Proof.** Let $\mathcal{C}$ be a countable ideal. Then $\mathcal{C}$ contains either a greatest element $t$ or a chain $C$ of type $\omega$, say $t_0 \le t_1 \le \dots \le t_n \le \dots$, which is cofinal in $\mathcal{C}$ (that is, $\downarrow C = \mathcal{C}$). This is a purely order-theoretic fact. To prove it, suppose that $\mathcal{C}$ has no greatest element, and consider an enumeration of the elements of $\mathcal{C}$ in a sequence $c_0, \dots, c_n, \dots$. Define $t_0 := c_0$ and $t_n$ being defined, $t_{n+1}$ be an upper bound of $t_n$ and $c_{n+1}$. Now, with this fact at hand, if $\mathcal{C}$ has a greatest element $t$, then it is the age of any relational structure of type $t$. Otherwise, construct a sequence $R_0, R_1, \dots, R_n, \dots$ of relational structures such that, for each nonnegative integer $n$, $R_n$ has type $t_n$ and $R_n$ is a restriction of $R_{n+1}$. Let $R_\infty := \bigcup_{n\ge 0} R_n$. Then, clearly $\mathcal{C}$ is the age of $R_\infty$. $\square$

**Theorem 2.8.** Let $\mathcal{C}$ be an infinite ideal of finite structures or an infinite hereditary class of finite structures which is level-finite. Then $\mathcal{C}$ contains a countable age.

**Proof.** It suffices to show that $\mathcal{C}$ contains a countable ideal and then to apply Theorem 2.7. In fact, if $\mathcal{C}$ is an ideal, the proof of Theorem 2.7 yields a strictly increasing sequence $t_0 < t_1 < \dots < t_n$ of elements of $\mathcal{C}$. It generates an ideal which is countable since $\downarrow t_n$ is finite for each $n$. If $\mathcal{C}$ is infinite and level-finite it has infinitely many levels. König's Theorem asserts that $\mathcal{C}$ contains an infinite chain going through all the levels. This chain generates an ideal. Since each principal initial segment is finite, this ideal is countable. $\square$

**Proposition 2.9.** If the signature $\mu$ is finite, $\Omega_\mu$ is level-finite and hence countable. Thus every ideal of $\Omega_\mu$ is the age of a countable structure. Moreover, no matter whether $\mu$ is finite or not, $\Omega_\mu$ is an ideal and in fact an age.

**Proof.** For the first part of the proposition, apply Theorem 2.7. For the second part, define the direct sum of two structures $R := (V, (\rho_i)_{i \in I})$ and $R' := (V', (\rho'_i)_{i \in I})$ of signature $\mu$ as the relational structure $R \oplus R'$, defined on the union of their bases supposed disjoint, and made of the relations $\rho_i \cup \rho'_i$ for $i \in I$. Then the age of the direct sum of all members of $\Omega_\mu$ is equal to $\Omega_\mu$. $\square$
This result extends.

**Lemma 2.10.** (1) For every $R, R' \in \Omega_\mu$ the final segment ($\uparrow R) \cap (\uparrow R'$) is a union of final segments of the form $\uparrow T$ where $|T| \le |R| + |R'|$.

(2) If some $n_j$ of $\mu := (n_i)_{i \in I}$ is at least 2, then for every $S \in \Omega_\mu \setminus \{0\}$ the collection $\Omega_\mu \setminus \uparrow S$ is an age.

**Proof.** (1). The direct sum $T := R \oplus R'$ of $R$ and $R'$ belongs to $\uparrow R \cap \uparrow R'$ and $|T| \le |R| + |R'|$. If $U$ is any member of $\uparrow R \cap \uparrow R'$ select $F, F'$ such that $U \downarrow_F$ is isomorphic to $R$ and $U \downarrow_{F'}$ is isomorphic to $R'$. Then $T := U \downarrow_{F \cup F'} \in \uparrow R \cap \uparrow R'$ and $|T| \le |R| + |R'|$.

(2). Since $S$ is nonempty, $\Omega_\mu \setminus \uparrow S$ is nonempty. We then have two possible cases:

Case 1. $S$ does not decompose into a direct sum $R \oplus R'$ with $R, R'$ nonempty. In this case, $\Omega_\mu \setminus \uparrow S$ is the age of the direct sum of all members of $\Omega_\mu \setminus \uparrow S$.

Case 2. $S$ decomposes. Let $j$ be such that $\rho_j$ is at least binary. In this case, we use a construction based on the negation of a relation. If $\rho$ is a $n$-ary relation on a set $V$, we set $\neg \rho := V^n \setminus \rho$. Define the $\neg j$-direct sum of two structures $R := (V, (\rho_i)_{i \in I})$ and $R' := (V', (\rho'_i)_{i \in I})$ of signature $\mu$ as the relational structure $R \oplus_{\neg j} R'$, defined on the union of their bases supposed disjoint, and made of the relations $\rho_i \cup \rho'_i$ for $i \in I \setminus \{j\}$ and $\neg (\neg \rho_j \cup \neg \rho'_j)$ for $i := j$. Then $\Omega_\mu \setminus \uparrow S$ is the age of the $\neg j$-direct sum of all members of $\Omega_\mu \setminus \uparrow S$. $\square$

Note that if $\Omega_\mu$ consists only of unary relations and $S := (\{0,1\}, \{0\})$, then $\Omega \setminus \uparrow S$ is not an age. Indeed, the restrictions of $S$ to $\{0\}$ and to $\{1\}$ belong to $\Omega \setminus \uparrow S$ but every common extension embeds $S$.

**2.5.1. Ages and ideals.** An ideal of $\Omega_\mu$ is representable if it is the age of some relational structure of signature $\mu$. According to Theorem 2.7, countable ideals are representable. But, provided that the signature contains infinitely many integers at least equal to 2, $\Omega_\mu$ contains ideals that are not representable. For example, consider the relational structure $D := (\mathbb{R}, (\delta_r)_{r \in \mathbb{Q}^+})$ on $\mathbb{R}$, such that for each $r \in \mathbb{Q}$, $\delta_r(x, y) = +$ if and only if $|x - y| \le r$.

Denote by $\tau(D_{\uparrow F})$ the isomorphic type of a restriction of $D$ to a finite subset $F$ of $\mathbb{R}$ and let $\mathfrak{A} := \{\tau(D_{\uparrow F}) : F \in [\mathbb{R}]^{<\omega}$ such that $\delta_1(x, y) = -$ for all distinct $x, y \in F\}$.

**Proposition 2.11.** $\mathfrak{A}$ is an ideal included in $\text{Age}(D)$ and there is no relational structure $M$ such that $\text{Age}(M) = \mathfrak{A}$.

**Proof.** Let $M := (V, (\rho_r)_{r \in \mathbb{Q}^+})$, be a relational structure with the same arity as $D$. Set

$$d_M(x, y) := \inf\{r \in \mathbb{Q}^+ : \rho_r(x, y) = +\}.$$

Then $d_M$ is a distance on $V$ provided that $\tau(M_{\uparrow F}) \in \text{Age}(D)$ for every $F \in [V]^{<\omega}$. Moreover, a map $f$ with $\text{dom}(f) \subseteq V$, $\text{range}(f) \subseteq \mathbb{R}$ is a local isomorphism from $M$ to $D$ if and only if this is an isometry. From this observation follows, in particular, that $\mathfrak{A}$ is up-directed with cardinality $2^{\aleph_0}$. On the other hand, for every $F \in [\mathbb{R}]^{<\omega}$ such that $\tau(D_{\uparrow F}) \in \mathfrak{A}$, the diameter of $F$ is greater than $|F| - 1$. Hence, if $\text{Age}(M) \subseteq \mathfrak{A}$, then a ball $B(x, r)$ in $(V, d)$ cannot contain more than $2r + 1$ elements. Each ball in $V$ being finite, $V$ is countable, hence $\text{Age}(M) \neq \mathfrak{A}$. $\square$

We note that [56] contains several examples, including the one above, of nonrepresentable ideals.

**2.6. Universal classes.** Classes of models of universal theories provide examples of hereditary classes. In recalling the background, we follow Fraïssé [75], particularly his notion of free operator, except for the notion of universal class (for him universal classes are finitely axiomatizable). To a given signature $\mu := (m_i)_{i \in I}$, associate a language consisting of predicate symbols $\rho_i$ of arity $m_i$ for each $i \in I$, variables, equality. A first-order sentence (in the language associated with the signature $\mu$) is *universal* whenever it is logically equivalent to a sentence of the form $\forall x_1 \dots \forall x_n \varphi(x_1, \dots, x_n)$ where $\varphi(x_1, \dots, x_n)$ is a formula built with the variables $x_1, \dots, x_n$, the logical connectives $\neg, \vee, \wedge$ and predicates $=$, $\rho_i, i \in I$. The sentence is *existential* if its negation is equivalent to a universal one. A theory is a consistent set $T$ of sentences, closed under deduction and conjunction; the theory $T$ is *axiomatized by a set A of sentences* if $T$ is the closure of $A$. If $A$ consists of universal sentences, $T$ is *universal*. We denote by $T_\forall$ the set of universal sentences which belong to a theory $T$. The class $\text{Mod}(U)$ of models of a set $U$ of universal sentences is said *universal* too.
Tarski-Vaught theorem (See [76], section 5.10. Universal classes, p.161, and also [193, 201]) asserts that if the signature $\mu$ is finite, each universal class is determined by a hereditary class of finite structures and, more importantly, that class has only finitely many bounds if and only if the former is finitely axiomatizable.

In more precise terms:

**Theorem 2.12.** Let $\mu$ be a finite signature. A class $\mathcal{D}$ of structures of signature $\mu$ is universal if and only if $\mathcal{D}$ is the class of structures $R$ such that $\text{Age}(R) \subseteq \mathcal{C}$ for some hereditary class $\mathcal{C}$ of finite structures. Furthermore, the universal theory of $\mathcal{D}$ is finitely axiomatizable if and only if the class $\mathcal{C}$ has only finitely many bounds.

This result is based on a simple observation. If $R := (V, (\rho_i)_{i \in I})$ is a relational structure on $n$ elements and if $I$ is finite, one may associate an existential sentence $\theta_R := \exists x_1 \dots \exists x_n \psi_R(x_1, \dots, x_n)$ where $\psi_R(x_1, \dots, x_n)$ is a formula with no quantifier that describes $R$ in such a way that a relational structure $S$ satisfies $\theta_R$ if and only if $R$ embeds in $S$. With this observation, if $\mathcal{C}$ and $\mathcal{D}$ are as above, the collection of sentences $\neg\theta_R$ where $R$ is any bound of $\mathcal{C}$ provides an axiomatization of $\mathcal{D}$ by universal sentences. If the set of bounds is finite, the axiomatization is finite; as it turns out, the converse holds [75].

Universal sentences provide a syntactical approach to universal classes. A natural object associated to universal sentences is the Boolean algebra made of Boolean combinations of universal sentences, considered up to elementary equivalence. This Boolean algebra is isomorphic to the Boolean algebra generated by the set of $\text{Mod}(\varphi)$ where $\varphi$ runs through universal sentences, or in more concrete terms, generated by the set $\{\text{Forb}(R) : R \in \Omega_\mu\}$. An equivalent object is the Stone space of this algebra. We give a partial description. The key result is the following proposition together with Theorem 1.3.

**Proposition 2.13.** If a hereditary class $\mathcal{C}$ of $\Omega_\mu$ is level-finite then:

(1) $\mathcal{C}$ is up-closed;

(2) $\text{Id}(\mathcal{C})$ is topologically closed in $\text{I}(\mathcal{C})$;

(3) $\text{Id}(\mathcal{C})$ with the topology induced by the product topology is the Stone space dual of the Boolean algebra generated by $\text{up}(\mathcal{C})$.

**Proof.** (1). Since $\mathcal{C}$ is level-finite it follows from (1) of Lemma 2.10 that $\mathcal{C}$ is up-closed.

(2). With (1) and the fact that $\mathcal{C}$ has a least element, Proposition 1.2 asserts that the set $\text{Id}(\mathcal{C})$ is a closed subset of $\wp(V)$, hence of $\text{I}(\mathcal{C})$.

(3). Apply Theorem 1.3.

□

If $\mu$ is finite, $\Omega_\mu$ is level-finite and thus, (3) applies. Since $\text{up}(\Omega_\mu)$ is (dually) isomorphic to $\{\text{Forb}(R) : R \in \Omega_\mu\}$ one gets Proposition 2.9 of [14].

**Theorem 2.14.** If $\mu$ is finite then the set $\text{Id}(\Omega_\mu)$, equipped with the topology induced by the product topology, is the dual of the Boolean algebra made of Boolean combinations of universal sentences, considered up to logical equivalence.

Thus, from Theorem 2.14 the tail algebra $\text{Tailalg}(\Omega_\mu)$ provides an alternative description of the algebra made of Boolean combinations of universal sentences (see [150] [162] for more details on this correspondence).

Instead of Boolean algebras, one may prefer to consider lattices. Proposition 2.13 above yields:

**Corollary 2.15.** If $\mu$ is finite, then the set of hereditary classes of $\Omega_\mu$ having finitely many bounds is closed under finite intersections and finite unions, hence is a distributive lattice dually isomorphic to $\text{Taillat}(\Omega_\mu)$.

**2.6.1. Reducts.** If the signature is infinite, one needs the notion of *reduct*. Let $\mu := (m_i)_{i \in I}$ be a family of nonnegative integers. Let $I' \subseteq I$ and denote the restriction of $\mu$ to $I'$ by $\mu_{\upharpoonright I'}$. For a $\mu$-ary relational structure $R := (V, (\rho_i)_{i \in I})$, the $I'$-reduct of $R$ is the $\mu_{\upharpoonright I'}$-ary relational structure $R^{\upharpoonright I'} := (V, (\rho_i)_{i \in I'})$. The *reduct-closure* of a class $\mathcal{C}$ of relational structures with signature $\mu$ is the class $\widehat{\mathcal{C}}$ of $R$ with signature $\mu$ such
that for each finite $I' \subseteq I$ there is some $R' \in \mathfrak{C}$ such that $R'^{\upharpoonright I'} = R'^{\upharpoonright I''}$. A class $\mathfrak{C}$ is said to be reduct-closed if $\tilde{\mathfrak{C}} = \mathfrak{C}$. If the signature $\mu$ is finite, every class is reduct-closed.

**Proposition 2.16.** Let $\mathfrak{C}$ be a hereditary class of finite structures.

(1) If $\mathfrak{C}$ is level-finite, then $\mathfrak{C}$ is reduct-closed.

(2) If $\mathfrak{C}$ is reduct-closed, then the class $\tilde{\mathfrak{C}}$ of structures $R$ such that $\text{Age}(R) \subseteq \mathfrak{C}$ is reduct-closed.

**Proof.** (1). We prove that $\tilde{\mathfrak{C}} = \mathfrak{C}$. Let $S := (V(S), (\rho_i)_{i \in I}) \in \tilde{\mathfrak{C}}$. For every finite subset $I'$ of $I$ there is some member $S(I') \in \mathfrak{C}$ such that $S^{\upharpoonright I'} = S(I')^{\upharpoonright I''}$. Let $n := |V(S)|$. Since $\mathfrak{C}$ is level-finite, there are only finitely many $S(I') \in \mathfrak{C}$, hence there is some finite $I' \subseteq I$ such that $S(I') = S(I'')$ for every finite $I''$ containing $I'$. This implies that $S = S(I')$, hence $S \in \mathfrak{C}$ as required.

(2). We prove that $\tilde{\mathfrak{C}} = \tilde{\mathfrak{C}}$. Let $R := (V(R), (\rho_i)_{i \in I}) \in \tilde{\mathfrak{C}}$. We need to prove that $R \in \tilde{\mathfrak{C}}$, that is $R \upharpoonright_{V'} \in \mathfrak{C}$ for every finite $V' \subseteq V(R)$. Since $\mathfrak{C}$ is reduct-closed, this means that for every finite subset $I' \subseteq I$ there is some $S(I') \in \mathfrak{C}$ with domain $V'$ such that $S(I') = R \upharpoonright_{V'}$. Since $R \in \tilde{\mathfrak{C}}$ there is some $R(I') \in \tilde{\mathfrak{C}}$ such that $R^{\upharpoonright I'} = R(I')^{\upharpoonright I''}$. It suffices to set $S(I') := R(I')^{\upharpoonright I'_{V'}}$. $\square$

From this result, it follows that if we use the compactness theorem of first-order logic within the class $\tilde{\mathfrak{C}}$ associated to a reduct-closed hereditary class $\mathfrak{C}$, the result we obtain belongs to $\tilde{\mathfrak{C}}$. Several examples illustrate this observation. Provided that we consider only reduct-closed classes of finite structures, the above characterization of universal classes given in Theorem 2.12 holds. Also, note that independently of the cardinality of the signature, every ideal that consists of the collection of finite models of a set of universal sentences is the age of some relational structure. For another illustration, see Proposition 5.24.

**2.6.2.** *A construction of universal classes.* We reproduce here some properties of free interpretability developed by Fraïssé in [75, 76]. Let $\mu$ and $\nu$ be two signatures (possibly distinct). A $\mu$-ary relational structure $S$ is freely interpretable in a $\nu$-ary relational structure $R$ if $R$ and $S$ have the same base and every local isomorphism of $R$ is a local isomorphism of $S$. A map $\mathcal{P}$ from the class of $\mu$-ary relational structures into the class of $\nu$-ary relational structures is a free operator if $\mathcal{P}(R)$ is freely interpretable by $R$, for every $\mu$-ary relational structure $R$.

**Lemma 2.17.** A map $\mathcal{P}$ from the class of $\mu$-ary relational structures into the class of $\nu$-ary relational structures is a free operator if and only if for every $\mu$-ary relational structure $R$:

(1) $\mathcal{P}(R)$ has the same domain as $R$;

(2) $\mathcal{P}(R \upharpoonright A) = \mathcal{P}(R) \upharpoonright A$; and

(3) every automorphism of $R$ is an automorphism of $\mathcal{P}(R)$.

**Lemma 2.18.** Let $R$ and $S$ be two relational structures with the same base $V$ and signatures $\mu$ and $\nu$, respectively. Then:

(1) $S$ is freely interpretable by $R$ if and only if there is some free operator $\mathcal{P}$ such that $\mathcal{P}(R) = S$;

(2) if $\mu$ is finite, $\mathcal{P}(R) = S$ for some free operator, and $S'$ is such that $\text{Age}(S') \subseteq \text{Age}(S)$, then there is an $R'$ such that $\mathcal{P}(R') = S'$ and $\text{Age}(R') \subseteq \text{Age}(R)$.

**Proof.** (1) This is a basic result, see [76], 9.3.1, pp. 247-248.

(2) The proof illustrates the importance of compactness. Let $\mu := (m_i)_{i \in I}$, $V'$ be the domain of $S'$ and $U_\mu(V') := \Pi_{i \in I} 2^{(V')^{m_i}}$. By definition, $U_\mu(V')$ is the set of $\mu$-ary relational structures $R'$ with domain $V'$. This set has a topological structure for which it is compact. (Equip $2 := \{0,1\}$ with the discrete topology and the set $2^{(V')^{m_i}}$ with the product topology; since $U_\mu(V')$ is a product, we can equip it with the product topology.) For every finite subset $F$ of $V'$, let $\mathcal{U}_F$ be the subset of $U_\mu(V')$ made of $\mu$-ary relational structures $R'$ on $V'$ such that $\mathcal{P}(R'_{\upharpoonright F}) = S'_{\upharpoonright F}$. It can be checked that the sets of the form $\mathcal{U}_F$ are closed and nonempty, hence their intersection is nonempty. Then one checks that any member of this intersection yields the required $R'$.

Illustrations are given by the following theorem and by Lemma 5.36. $\square$
**Theorem 2.19.** The image of a universal class over a finite language by a free operator is a universal class.

**Proof.** Let $\mathcal{C}$ be a universal class made of $\mu$-ary relational structures and $\mathcal{P}$ be a free operator that maps each $\mu$-ary relational structure to a $\nu$-ary relational structure. Let $\mathfrak{D} := \mathcal{P}(\mathcal{C})$. Due to (2) of Lemma 2.18 above, $\mathfrak{D}$ is a hereditary class. To conclude that $\mathfrak{D}$ is a universal class, it suffices to prove that if $S$ is a $\nu$-ary relational structure on a set $V$, then there is some $R \in \mathcal{C}$ such that $\mathcal{P}(R) = S$ provided that for every finite $F \subseteq V$, $S \upharpoonright F \in \mathcal{P}(\mathcal{C})$. This is just (2) of Lemma 2.18. $\square$

Here are several universal classes obtained by this process.

**Examples 2.20.**

(1) The class of ordered sets of order-dimension at most $n$: to $(V, \leq_1, \dots, \leq_n)$ associate $(V, \cap_{i \leq n} \leq_i)$.

(2) The class of posets coverable by at most $n$ chains, $n \in \mathbb{N}$.

(3) The class of comparability graphs.

(4) The class of $n$-colorable graphs, for each $n \in \mathbb{N}$. This is a famous result of de Bruijn-Erdös [49].

Note that the hypothesis that the signature is finite in Lemma 2.18 (2) is needed. Indeed, if a graph $G$ has chromatic number $\kappa_0$, it is freely interpretable by $G$ with $\kappa_0$ unary relations defining a covering of $G$ in independent sets, a graph $G'$ with a smaller age than $G$ may have a larger chromatic number.

**2.7. The number of hereditary classes of finite structures.** We may ask how many hereditary classes of finite structures there are. The first result that I saw in this direction was in Mal'cev [129].

**Lemma 2.21.** There are uncountably many hereditary classes of finite graphs.

**Proof.** Let $C_n$ be the $n$-vertex cycle. The family of these cycles for $n \geq 3$ forms an antichain for embeddability since $C_n$ is not embeddable in $C_m$ for $m \neq n$. For each subset $X$ of the set $\mathbb{N}$ of nonnegative integers, the collection $\mathcal{C}_X$ of graphs $G$ embeddable into some $C_{n+3}$, for some $n \in X$, is by construction a hereditary class. Now, if $X \neq X'$, then $\mathcal{C}_X \neq \mathcal{C}_{X'}$. This provides as many classes as subsets of $\mathbb{N}$.

Alternatively, for each subset $X$ of the powerset $\wp(\mathbb{N})$, the collection $\mathcal{C}_{\neg X}$ of graphs $G$ in which no $C_{n+3}$, $n \in X$, is embeddable is a hereditary class and in fact a universal class. The trace of $\mathcal{C}_{\neg X}$ on the class $\mathfrak{G}$ of finite graphs is a hereditary subclass. This class is up-directed, since it contains the direct sum of any of two of its members, thus it is an age. Hence, we get a continuum number of ages. $\square$

Building on Lemma 2.21, we get:

**Proposition 2.22.** Let $\mu := (m_i)_{i \in I}$ be a signature and $\kappa := \max\{\kappa_0, 2^{|I|}\}$. Then $|\Omega_\mu| = \kappa$ and, as a poset, $\Omega_\mu$ is embeddable in $[\kappa]^{<\omega}$, the collection of finite subsets of $\kappa$ ordered by set inclusion. If $I$ is infinite or $m_j \geq 2$, for some $j \in I$, then $\Omega_\mu$ is equimorphic to $[\kappa]^{<\omega}$. Otherwise, $\Omega_\mu$ is equimorphic to the power set $\mathbb{N}^{2^{|I|}}$ ordered componentwise.

**Proof.** First, let us see that $|\Omega_\mu| = \kappa$. Suppose that $I$ is infinite. Then $\Omega_\mu$ has the same cardinality as $2^{|I|}$. Indeed, a relational structure of signature $\mu$ and domain $V$ is an element of $\Pi_{i \in I} 2^{V^{m_i}}$. If $V$ is finite, with $n$ elements, this gives $2^{|I|}$ structures; since each isomorphy class is finite, the number of isomorphic types is $2^{|I|}$. Since $\Omega_\mu$ is the union of countably many levels and each level (except level 0) has cardinality $2^{|I|}$, $\Omega_\mu$ has cardinality $2^{|I|}$. Suppose that $I$ is finite. In this case, $\kappa = \kappa_0$, each level of $\Omega_\mu$ is finite, hence $\Omega_\mu$ is countably infinite. The embeddability of $\Omega_\mu$ in $[\kappa]^{<\omega}$ follows from the fact that for each $\tau \in \Omega_\mu$, the subset $\downarrow \tau := \{\tau' \in \Omega_\mu : \tau' \leq \tau\}$ of $\Omega_\mu$ is finite (it has cardinality at most $2^{|\tau|}$, where $\tau$ is the number of elements of the domain of any representative of $\tau$). Indeed, as for every poset, the map $\downarrow$ defines an embedding of $\Omega_\mu$ in $[\Omega_\mu]^{<\omega}$. This proves the first assertion.

Now, suppose that $I$ is infinite. Then $\kappa = 2^{|I|}$. Since the cardinality of the set of members of $\Omega_\mu$ on a one element set is $2^{|I|} = \kappa$ there is a set $V$ of cardinality $\kappa$ and a relational structure $R$ of signature $\mu$ based on $V$ such that all its restrictions to singletons are pairwise non-isomorphic. If we associate to each finite subset $F$ of $V$ the restriction $R_{\upharpoonright F}$ we get an embedding of $[V]^{<\omega}$ in $\Omega_\mu$. Hence, $\Omega_\mu$ is equimorphic
to $[\Omega_\mu]^{<\omega}$. If $I$ is finite, we suppose first that $\mu$ consists only of the integer 2. As in the proof of Lemma 2.21, let $(C_{n+3})_{n\in\mathbb{N}}$ be the family of cycles of length at least 3. To each finite subset $F$ of $\mathbb{N}$ associate $\bigoplus_{n\in F} C_{n+3}$, the direct sum of the $C_{n+3}$ for $n \in F$ and observe that this defines an embedding from $[\mathbb{N}]^{<\omega}$ in the collection $\mathcal{G}$ of finite graphs, hence in $\Omega_\mu$. Suppose next that there is some $j \in I$ such that $m_j \ge 2$. To each finite graph $G := (V, E)$ associate the relational structure $R_G := (V, (\rho_i)_{i\in I})$ where $\rho_i := \emptyset$ if $i \ne j$ and $\rho_j := \{(x_1, \dots, x_{m_j}) \in V^{m_j} : (x_1, x_2) \in E\}$ if $i = j$. This defines an embedding of $\mathcal{G}$ in $\Omega_\mu$. Since $[\mathbb{N}]^{<\omega}$ embeds in $\mathcal{G}$, it embeds in $\Omega_\mu$. Hence, these two posets are equimorphic.

Finally, suppose $I$ finite, $I := \{1, \dots, k\}$, and that $m_i = 1$ for $i \in I$. We may represent each finite $R \in \Omega_\mu$ by a finite multiset over $2^k$. Indeed to $R := (V, (\rho_i)_{i=1,\dots,k})$ we may associate $(V, \chi_R)$ where $\chi_R$ is the map from $V$ into $2^k$ defined by setting $\chi_R(x) := (\rho_i(x))_{i=1,\dots,k}$. Next, to $(V, \chi_R)$ we may associate its frequency $F_R := (n_s)_{s\in 2^k}$ where $n_s$ is the number of elements $x$ of $V$ such that $\chi_R(x) = s$. These frequencies are members of the power $P := \mathbb{N}^{2^k}$ that we can order componentwise. One can check that $R \le R'$ if and only if $F_R \le F'_R$. Hence, $\Omega_\mu$ is equimorphic to $P$. The result follows. $\square$

As mentioned in Subsection 1.2, if $P$ is a poset, then the poset $\mathbf{I}(P)$ of initial segments of $P$ ordered by set inclusion is order isomorphic to $\mathbf{Id}(\mathbf{I}_{<\omega}(P))$. Applying this to the set $\mathbb{N}$ of nonnegative integers ordered by the equality relation, we get that the powerset $\wp(\mathbb{N})$ ordered by set inclusion is isomorphic to $\mathbf{Id}([\mathbb{N}]^{<\omega})$. This added to Proposition 2.22 yields:

**Lemma 2.23.** If the maximum of the signature $\mu := (m_i)_{i\in I}$ is at least 2 and $I$ is finite, then the set $\mathbf{Id}(\Omega_\mu)$ of ages of $\Omega_\mu$, ordered by set inclusion, is equimorphic to the powerset $\wp(\mathbb{N})$ ordered by set inclusion.

**Proof.** According to Proposition 2.22, $\Omega_\mu$ is equimorphic to $[\mathbb{N}]^{<\omega}$. It follows that $\mathbf{Id}(\Omega_\mu)$ is equimorphic to $\mathbf{Id}([\mathbb{N}]^{<\omega})$ which in turn is isomorphic to $\wp(\mathbb{N})$. Since $I$ is finite, the ages of $\Omega_\mu$ constitute ideals which completes the proof. $\square$

Dickson's lemma asserts that a finite cartesian product of copies of the chain $\mathbb{N}$ ordered componentwise contains no infinite antichain. Hence, from Proposition 2.22, we get:

**Corollary 2.24.** Let $\mu := (m_i)_{i\in I}$ be a signature. Then $\Omega_\mu$ has no infinite antichain if and only if $I$ is finite and $m_i = 1$ for every $i \in I$.

Thus, either $\Omega_\mu$ contains no infinite antichain, in which case $\mathbf{Id}(\Omega_\mu)$ is countable, or $\mathbf{Id}(\Omega_\mu)$ is uncountable. Does this dichotomy extend to hereditary classes? With this question, well-quasi-ordering enters into the study of hereditary classes of finite structures.

### 3. TYPOLOGY OF HEREDITARY CLASSES AND AGES

In this section and in Section 5, we present the results of attempts to classify hereditary classes and ages based on order and topological notions.

One could classify hereditary classes according to their proper subclasses. With this idea, the simplest classes are those which contain finitely many proper subclasses, hence these classes are finite. At the next level, there are the classes which contain infinitely many proper subclasses, but every proper subclass contains only finitely many. That is, such classes are infinite but proper subclasses are finite (we call them Jónsson classes). It is a simple exercise based on Ramsey's theorem to prove that among hereditary classes of finite graphs there are only two such classes: the class of finite cliques and the class of their complements. Pursuing this idea further, one would like to attach a kind of rank to each class, preferably an ordinal. If we do this, it turns out that a class has a rank if and only if the set of its proper subclasses ordered by set inclusion is well-founded. This latter condition amounts to the class being well-quasi-ordered. This allows us to apply to hereditary classes results of the rich literature concerning well-quasi-ordered posets by now well-known [113], notably to construct wqo hereditary classes. Above all, we are lead to classifying ages by the same process. After recalling the notion of better-quasi-order (bqo) invented by Nash-Williams [139, 138] and the Nash-Williams conjecture, we are lead to consider four types of (potentially distinct) ages: the ages which
are better-quasi-ordered, the well-quasi-ordered ages, the ages for which the collection of subages is count-
able, and those for which the collection of subages is well-founded. If the signature is finite, it is possible
that wqo ages are necessarily bqo. Otherwise, there are counterexamples.

A central question is to know whether or not an age is wqo whenever the collection of subages is well-
founded. This old question remains unanswered. It is discussed in Problems 4 and 5 and in Conjecture
1. A parallel with the study of join semilattices is mentioned. The notions of kernel and generation are
introduced. Applications to a topological study of the collection of subages of a hereditary class (Theorems
3.40 and 3.41) are given; the Vietoris topology and the Vietoris rank are mentioned. By way of conclusion,
we observe that the problems and conjecture mentioned above have a positive answer for ages of posets
coverable by two chains.

3.1. **Well-quasi-ordering.** A poset *P* is *well-quasi-ordered* (wqo for short) if every nonempty subset contains finitely many minimal elements (this number being non-zero). Equivalently, *P* is wqo if it contains no infinite descending chain and no infinite antichain. A final segment *F* of a poset *P* is *finitely generated* if for some finite subset *K* of *P*, *F* =↑*K*.

We recall a result by Higman [94]:

**Theorem 3.1.** *The following properties are equivalent for a poset *P*:*

(i) *P* is wqo;

(ii) every final segment *F* of *P* is finitely generated;

(iii) the set $\mathbf{I}(\mathbf{P})$ of initial segments of $\mathbf{P}$, ordered by set inclusion, is well-founded.

Condition (iii) in Theorem 3.1 allows to do induction on the collection of initial segments. An example
of easy induction is given by the following result.

**Theorem 3.2.** *A wqo poset is a finite union of ideals.*

**Proof.** If this is not true, take a wqo poset $P$ for which this is not true. Since $\mathbf{I}(P)$ is well founded, it contains a minimal initial segment $I$ which is not a finite union of ideals. Due to the minimality condition, this $I$ cannot be the union of two proper initial segments. But then it is up-directed. Indeed, if $x, y \in I$ have no upper bound in $I$ then $I$ is the union of two proper initial segments $I \uparrow x$ and $I \uparrow y$. Since $I$ cannot be empty (the empty set is an empty union of ideals), this is an ideal. This is a contradiction. $\square$

The previous two results remind us of the characterization of noetherian rings and the fact that in a noe-
therian ring every ideal is a finite intersection of irreducible ideals.

The wqo condition is not necessary in Theorem 3.2; the fact that there is no infinite antichain suffices (take a well-founded cofinal subset, it will be wqo). A necessary and sufficient condition for a poset to be a finite union of ideals is due to Erdös and Tarski (1943) [64]. Simple, beautiful, this is one of the first min-max results in the theory of ordered sets. We will state and prove it.

Let us say that two elements of a poset *P* are *incompatible* if they do not have a common upper bound
and let us say that a subset *A* of *P* is *inconsistent* if no pair of distinct elements of *A* are compatible.

**Theorem 3.3.** If a poset *P* contains no infinite inconsistent set, the size of inconsistent sets is bounded by a nonnegative integer *n* and the least upper bound is the minimum number of ideals needed to cover *P*.

**Proof.** Let $F$ be the set of $x \in P$ such that the final segment $\uparrow x$ is up-directed. This is a final segment. Among the inconsistent subsets of $F$, pick a maximal one with respect to set inclusion, say $A$. From the maximality of $A$, we deduce that the union of the sets $I_x := \downarrow (\uparrow x)$ for $x \in A$ will cover $I := \downarrow F$. If $I$ does not cover $P$, build a copy of the binary tree $T := 2^\omega$ in $P \setminus I$ in such a way that at every stage, the images of the sequences $s_0$ and $s_1$ (obtained by adding 0 and 1 to a sequence $s \in T$) are two incompatible elements above the image of $s$. Then, the images of the sequences $11...10$ form an inconsistent set. $\square$

The most useful trick to prove that a poset is wqo is *the minimal bad sequence technique* discovered by Nash-Williams [138], and the most important tools to construct wqo sets are due to Higman and Kruskal
([94, 112]). We present here the minimal bad sequence technique (in a simple form) and will present the Higman and Kruskal theorems in Subsection 3.3.

Let $P$ be a poset; a sequence $(q_n)_{n<\omega}$ of elements of $P$ is bad if $q_n \nleq q_m$ for $n < m$. This sequence is minimally bad if there is no bad sequence $(q'_n)_{n<\omega}$ and some $m < \omega$ such that $q'_n = q_n$ for $n < m$ and $q'_m < q_m$. Nash-Williams's lemma asserts that:

**Lemma 3.4.** If a poset $P$ is well-founded but not wqo then it contains a minimally bad sequence.

**Proof.** Let $q_0 \in P$ be minimal such that there is some bad sequence $(q'_n)_{n<\omega}$ with $q'_0 = q_0$. Supposing $q_n$ defined for $n < m$ such that there is some bad sequence $(q'_n)_{n<\omega}$ with $q'_n = q_n$ for $n < m$. Among the $m$-th terms of these sequence, select $q'_m$ be minimal and set $q_m = q'_m$. $\square$

This lemma is tricky and powerful. A fact, inspired from the theory of rings, simpler to conceive and as powerful is the following.

Let $P$ be a poset. Suppose that $P$ contains a final segment $F$ which is not finitely generated. Then it follows from Zorn's lemma that $F$ is contained in a final segment maximal, with respect to set inclusion, with the same property. If $\tilde{F}$ is such a final segment then $P \downarrow \tilde{F}$ is wqo. Indeed, if $F'$ is any final segment of $P \downarrow \tilde{F}$ then $\tilde{F} \cup F'$ is a final segment of $P$. This final segment is finitely generated iff $\tilde{F} \cup F' \neq \tilde{F}$, that is, $F'$ is nonempty or equivalently, $F'$ is nonempty and finitely generated. If $P$ is well-founded, then the set $A := \min(\tilde{F})$ is an infinite antichain of $P$ and every element of $P \downarrow \tilde{F}$, if any, is below almost every element of $A$. With that, we get:

**Lemma 3.5.** If a level-finite and up-closed poset $P$ contains an infinite antichain then it contains a wqo ideal $I$ such that $\min(P \downarrow I)$ is an infinite antichain.

This was observed in several works; see, for instance, the comment after Corollary 4.6 and Lemma 4.7 of [157].

One of the most important results about wqo is the de Jongh-Parikh Theorem (see [202] for the first part, and [50] for the second).

**Theorem 3.6.** If a poset $P$ is wqo then all the linear extensions of $P$ are well ordered and there is one having the largest possible order type.

This largest order type, denoted $o(P)$, is the ordinal length of $P$. If a poset $P$ is wqo, then since the set $I(P)$ of initial segments of $P$, ordered by set inclusion, is well-founded, then we may decompose it into levels via the height function. An equivalent formulation of de Jongh-Parikh's theorem was given in [170].

**Theorem 3.7.** If $P$ is wqo then $o(P) = h(P, I(P))$.

**Example 3.8.** If $A$ is an alphabet made of $p$ letters then the set $A^*$ of words over $A$, ordered by the subword ordering, is wqo and $o(A^*) = \omega^{\omega^{p-1}}$ [50].

The ordinal length of several other wqo posets have been computed. For example, the habilitation of D.Schmidt [185] contains the extension to wqo alphabets of the above result and several results on classes of labelled trees. The ordinal length of the class of finite trees was computed by Rathjen and Weiermann[175] (here the trees are graphs and the embeddings are topological embeddings).

### 3.2. Well quasi-ordered hereditary classes.
Since in $\Omega_\mu$ each principal initial segment is finite, hereditary subclasses $\mathcal{C}$ of $\Omega_\mu$ with no infinite antichains are wqo. In particular, if the maximum of the signature $\mu$ is 1 and the number of unary symbols is finite, $\Omega_\mu$ is wqo (Corollary 2.24). This observation leads us to some examples of hereditary classes, but in fact, very few. If the maximum of the arity is exactly 2, the situation is completely different. As we will show in Section 7 there are $2^{\aleph_0}$ hereditary subclasses of $\Omega_\mu$ which are wqo. Except for very few, given right below, the construction of examples requires work, so we prefer to present first the general properties of wqo hereditary classes.
**Examples 3.9.** The simplest example of a wqo hereditary class of finite structures is Chain, the class of finite chains. Indeed it is totally ordered by embeddability, thus has order type $\omega$. What is trivial for finite chains is not for the infinite; the extension of the wqo character to the class of countable chains was the famous conjecture of Fraïssé, solved by Laver. The fact that Chain is totally ordered by embeddability was extended by Fraïssé to chainable structures; some properties of the class of these structures are in Subsection 5.1. Beyond Chain, there are two typical examples: namely the collection of direct sums of finite chains and the collection of direct sums of paths. The fact that these classes are wqo follows immediately from a theorem of Higman given in Subsection 3.3. But such a deep result is not necessary here. Indeed, let $I_{<\omega}(\omega \times \omega)$, be the set, ordered by set inclusion, of finitely generated subsets of the direct product of $\omega$ by $\omega$. This poset is wqo. It is not too difficult to prove that the collection $\bigoplus$ Chain of direct sums of finite chains, quasi-ordered by embeddability, yields a poset isomorphic to this poset. As a poset, the collection of direct sums of paths, quasi-ordered by embeddability, yields a poset extending the previous one, thus is wqo. Note that while these two posets are not isomorphic they have the same profile, namely the partition function.

Structural properties of wqo hereditary classes start with the translation of Theorem 3.1 in terms of hereditary classes.

**Proposition 3.10.** Let $\mathcal{C}$ be a hereditary class of finite structures. Then the following properties are equivalent:

(a) $\mathcal{C}$ contains no infinite antichain;

(b) $\mathcal{C}$ contains at most countably many hereditary subclasses;

(c) the set $I(\mathcal{C})$ of hereditary subclasses of $\mathcal{C}$ ordered by set inclusion is well-founded;

(d) the powerset $\wp(\mathbb{N})$ ordered by set inclusion does not embed in the collection $I(\mathcal{C})$ of hereditary subclasses of $\mathcal{C}$ ordered by inclusion.

**Proof.** The proof is straightforward: (a) and (b) are equivalent. Indeed, if (a) holds then $\mathcal{C}$ is level-finite, hence $\mathcal{C}$ is at most countable. According to (ii) of Theorem 3.1, each final segment $F$ of $\mathcal{C}$ is finitely generated, hence the set $F(\mathcal{C})$ of these final segments is at most countable. Since $I(\mathcal{C})$ is dually isomorphic to $F(\mathcal{C})$, it is at most countable and (b) holds. Conversely, if (b) holds, then no infinite antichain can exist, otherwise the collection of final segments of $\mathcal{C}$ generated by subsets of such an antichain will be uncountable and thus $F(\mathcal{C})$ will be uncountable and $I(\mathcal{C})$ too.

That (a) is equivalent to (c) follows from the equivalence of (i) and (iii) of Theorem 3.1.

We see that (c) implies (d) because $\wp(\mathbb{N})$ ordered by set inclusion is not well-founded.

Finally, we show (d) implies (a). Indeed, if $\mathcal{C}$ contains an infinite antichain, say $\mathcal{A}$, let $(G_n)_{n \in \mathbb{N}}$ be an enumeration of $\mathcal{A}$. The map $\varphi : \wp(\mathbb{N}) \to I(\mathcal{A})$ defined by setting $\varphi(I) := \{G : G \leq G_n \text{ for some } n \in I\}$ for each subset $I$ of $\mathbb{N}$ is an embedding, demonstrating the negation of (d). $\square$

Note that every wqo hereditary subclass $\mathcal{C}$ of $\Omega_\mu$ is countable, even when $\mu$ is infinite (indeed, each level, being an antichain, is finite). Hence, wqo ideals are ages. From Theorem 3.2 (or Theorem 3.3) we obtain:

**Corollary 3.11.** Every wqo hereditary class $\mathcal{C}$ of finite structures is a finite union of wqo ages.

Since a hereditary class which is level-finite is necessarily up-closed (cf. (1) of Proposition 2.13), Lemma 3.5 yields the following result (cf. [157], Lemma 4.7 and [155], 3.9, p. 329):

**Lemma 3.12.** A level-finite hereditary class $\mathcal{C}$ is wqo if and only if every age properly included into $\mathcal{C}$ has only finitely many bounds belonging to $\mathcal{C}$.

We illustrate this result with Corollary 4.11 and Theorem 5.51.

3.2.1. *Ordinal length of well-quasi-ordered hereditary classes and height of an age.* Let $\mathcal{C}$ be a hereditary class of finite structures. If $\mathcal{C}$ is wqo, then according to de Jongh-Parikh's result, $\mathcal{C}$ has an ordinal length. Since $\mathcal{C}$ is countable this ordinal length is a countable ordinal. Since, in this case, $\mathrm{Id}(\mathcal{C})$ is well-founded, we can compute its height (defined by formula (1.1) by setting

$$h(\mathfrak{A}, \mathrm{Id}(\mathcal{C})) := \sup\{h(\mathfrak{A}', \mathrm{Id}(\mathcal{C})) + 1 : \mathfrak{A}' \in \mathrm{Id}(\mathcal{C}) \text{ and } \mathfrak{A}' \subset \mathfrak{A}\},$$
and $h(\mathrm{Id}(\mathfrak{C})) := \sup\{h(\mathfrak{A}) + 1 : \mathfrak{A} \in \mathrm{Id}(\mathfrak{C})\}$. This height, that we also denote $\mathbf{H}(\mathfrak{C})$, is defined provided that $\mathrm{Id}(\mathfrak{C})$ is well-founded. One of the main unsolved questions is to know whether or not an age $\mathfrak{A}$ is wqo whenever $\mathrm{Id}(\mathfrak{A})$ is well-founded (see Problem 5). Despite that, we have the following.

**Theorem 3.13.** Let $\mathfrak{C}$ be a level-finite hereditary class of finite structure. If $\mathrm{Id}(\mathfrak{C})$ is well-founded then $\mathbf{H}(\mathfrak{C})$ is at most countable.

This result is a consequence of general results of descriptive set-theory [137]. In our case, we use the following result (for a proof, see [162]).

**Proposition 3.14.** Let $V$ be a countable set and $\mathcal{F}$ be a family of subsets of $V$ such that $\mathcal{F}$ is closed in the space $\wp(V)$, endowed with the pointwise convergence topology, and $\mathcal{F}$ is well-founded under set inclusion. Then $h(\mathcal{F}) < \omega_1$.

**Problems 2.**

(1) Is every countable ordinal attained by the ordinal length of some wqo hereditary class of finite structures with a given finite signature?

(2) Is there a largest countable ordinal depending upon the signature?

(3) Is there a countable ordinal which bounds the ordinal length of wqo hereditary classes of graphs?

The ordinal length of the class of finite (ordered) forests is the ordinal $\epsilon_0$. The ordinal length of the class of finite series-parallel posets is the ordinal $\Gamma_0$ [163]. The ordinal length of the class of finite cographs is at most $\Gamma_0$; we do not know if the equality holds.

If we allow unbounded signature, the answer to the first problem above is negative: every ordinal below $\omega_1$, the first uncountable ordinal, can be attained. Indeed, let $\alpha$ be a countable ordinal; the poset $P$ intersection of two orders, one of order type $\omega$, the other of order type $\alpha$, is embeddable into $[\omega]^{<\omega}$. According to Corollary 1.4 of [55], $o(P) = \alpha$. Now, use a construction presented in Subsection 3.4.1. Let $V := P \cup A$, where $A$ is an infinite set disjoint from $P$. Let $\mathcal{F} := \{\downarrow x : x \in P\}$, $M_{\mathcal{F}}$ as defined in 3.4.1 and $\mathfrak{A} := \mathrm{Age}(M_{\mathcal{F}})$. According to Lemma 3.26 below, $\mathfrak{A}$ is the image of the direct product $\mathcal{F}^{<\omega} \times \omega$ by an order preserving map, hence it is wqo (in fact bqo). Since it embeds $\mathcal{F}$, that is $P$, its ordinal length is at least $\alpha$.

There is a relationship between the ordinal length of a poset $P$ and the height of ideals of $P$. For example, if $P$ is wqo and up-directed then $o(P) = h(P, \mathbf{I}(P)) \le \omega^{\mathbf{H}(P)}$ where $\mathbf{H}(P) := h(P, \mathrm{Id}(P))$ and $\mathrm{Id}(P)$ is the set of ideals of $P$ [204].

The computation for ages yields a better upper-bound.

**Theorem 3.15.** If $\mathrm{Id}(\mathrm{Age}(R))$ is wqo then $o(\mathrm{Age}(R)) = \omega^\alpha \cdot q$, where $\alpha$ is such that $\omega \cdot \alpha \le \mathbf{H}(\mathrm{Age}(R)) < \omega \cdot (\alpha + 1)$ and $q$ is the number of ages included into $\mathrm{Age}(R)$ whose height is between $\omega \cdot \alpha$ and $\omega \cdot (\alpha + 1)$.

This result mentioned in [157] (cf. Theorem 4.12) is included in [190] and a forthcoming paper [164]. With Example 3.8, it yields:

**Example 3.16.** Let $R := (\mathbb{Q}, U_1, \dots, U_p)$ be the chain of rational numbers, colored with $p$ colors $U_1, \dots, U_p$, in a dense way. Then, $\mathbf{H}(\mathrm{Age}(R)) = \omega^p$, while $o(\mathrm{Age}(R)) = \omega^{\omega^{p-1}}$.

In Subsection 3.6 and Section 5, we look at ages of height less than $\omega^2$.

**3.3. Construction of wqo hereditary classes.** A theorem of Kruskal [112] asserts that finite (ordered) trees labelled by a wqo form a wqo. A weaker version, expressed in terms of algebras quasi-ordered by divisibility, is due to Higman [94]. A simpler version, often cited as Higman's theorem, asserts that an algebra with only finitely many operations and quasi-ordered by divisibility is wqo provided that some generating set is wqo (see Cohn [42], Theorem 2.9). The complete version, with a wqo set of operations, is given in Exercise 10 of Chapter III [42]. The set of finite structured trees (ordered trees with a linear order on the successors of each node) labelled by a set can be viewed as an ordered algebra. Hence, the complete version is equivalent to Kruskal's theorem. In the sequel, we present the simpler version of Higman's theorem, because it is very easy to use.
An (abstract) *algebra* is a pair $\mathfrak{A} := (A, F)$ where $F$ is a set of finitary operations on $A$, each one being a function $f$ of $A^{a(f)}$ into $A$, where $a(f)$ is a nonnegative integer, called the *arity* of $f$. A subset $X$ of $A$ generates $\mathfrak{A}$ if $\mathfrak{A}$ is the sole subalgebra of $\mathfrak{A}$ containing $X$. Supposing that $F$ is finite, a quasi-order $\leq$ on $A$ is a *divisibility quasi-order* if:

(1) each $f \in F$ is order preserving, that is, $f(u) \leq f(v)$ for all $u \leq v$ in $A^{a(f)}$ equipped with the product quasi-order;

(2) each $f \in F$ is extensive, that is, $u_i \leq f(u)$ for every $f \in F$, $u := (u_0, \dots, u_i, \dots u_{a(f)-1}) \in A^{a(f)}$, $i < a(f)$.

Higman's theorem reads as follows:

**Theorem 3.17.** An algebra $\mathfrak{A}$ quasi-ordered by divisibility is wqo provided that some generator is wqo.

If $\mathfrak{A}$ is an ordered set, the ordered monoid $A^*$ is generated by the set of words of length 1; this set is order isomorphic to $\mathfrak{A}$. The Higman ordering on $A^*$ is a divisibility ordering, hence, from Theorem 3.17 above:

**Theorem 3.18.** If $\mathfrak{A}$ is wqo, the ordered monoid $A^*$ equipped with the Higman ordering is wqo.

The next consequence of Higman's theorem is about cographs and series-parallel posets.

**3.3.1. Cographs and series-parallel posets.** Let us recall that a (loopless undirected) graph is a cograph if it does not embed a path on four vertices. It was proved by Sumner [192] that if $G$ is a finite cograph then either $G$ or its complement $G^{comp}$ is disconnected. It follows that the set of isomorphic type of finite cographs coincides with the set $G$ consisting of the empty graph and the one-vertex graph and the direct sum $G \oplus G'$ and the complete sum $G + G'$ of any two of its members. Equipped with the operations of direct and complete sums, and ordered by embeddability, $G$ is a algebra quasi-ordered by divisibility. Since $G$ is generated by a two-element set, it is wqo.

A poset $P$ is series-parallel if it does not embed a $N$, the poset made of four elements $a, b, c, d$ such that $a < b$ and $c < b, d$ are the only comparabilities. This amounts to the fact that the comparability graph of $P$ is a cograph. Due to the recursive construction of finite cographs recalled above, the set of isomorphic type of finite series-parallel posets coincides with the set $\mathcal{N}$ consisting of the empty poset and the one-vertex poset and the direct sum $P \oplus P'$ and the ordinal sum $P + P'$ of any two of its members. Equipped with the operations of direct and complete sums, and ordered by embeddability, $\mathcal{N}$ is a algebra quasi-ordered by divisibility. Since $\mathcal{N}$ is generated by a two-element set, it is wqo.

This yields the beautiful result of Damaschke [45]:

**Theorem 3.19.** The collections of finite cographs and of finite series-parallel posets are wqo under embeddability.

This result extends to binary structures as we show below.

**3.3.2. Lexicographical sums of binary structures.** As said, a relational structure is *binary* if it consists of relations which are unary or binary. If $R := (V, (\rho_i)_{i \in I})$ is a binary structure and $\mathfrak{F} := (S_x)_{x \in V}$ is a family of binary structures $S_x := (V_x, (\rho_i^x)_{i \in I})$, indexed by the elements of $V$ such that $V$ and the $V_x$'s are nonempty, the *lexicographic sum* of $\mathfrak{F}$ over $R$, denoted by $\sum_{x \in R} S_x$, is the binary structure $T$ obtained by replacing each element $x \in V$ by the structure $S_x$. More precisely, $T = (Z, (\tau_i)_{i \in I})$ where $Z := \{(x, y) : x \in V, y \in V_x\}$ and for each $i \in I$, $(x, y)\tau_i(x', y')$ if either $x \neq x'$ and $x\rho_i x'$ or $x = x'$ and $y\rho_i^x y'$.

**Example 3.20.** If $R$ is a finite binary structure, one may use $R$ as an operation of *arity* $|R|$ acting on the class $\overline{\Omega}_{\mu}$ of binary structures with signature $\mu$, this operation $R$ associating to each family $\mathfrak{F} := (S_x)_{x \in V}$ the lexicographic sum of $\mathfrak{F}$ over $R$. Hence, if $\mathfrak{R}$ is a set of finite binary structures, the pair $(\overline{\Omega}_{\mu}, \mathfrak{R})$ can be viewed as an algebra. If $\mathfrak{S}$ is a subclass of $\overline{\Omega}_{\mu}$ then the subalgebra it generates, say $\overline{\Sigma}_{\mathfrak{R}}\mathfrak{S}$, consists of members of $\mathfrak{S}$, of lexicographical sums of members of $\mathfrak{S}$ indexed by members of $\mathfrak{R}$ and the iterates of these sums. Since each operation attached to $R \in \mathfrak{R}$ is increasing and extensive, if $\mathfrak{R}$ is finite, $(\overline{\Omega}_{\mu}, \mathfrak{R})$ is an algebra quasi-ordered by divisibility.
Hence, according to Theorem 3.17, we have:

**Lemma 3.21.** If $\mathfrak{R}$ is finite and $\mathfrak{S}$ is wqo with respect to embeddability, then $\tilde{\mathfrak{R}}\mathfrak{S}$ is wqo.

**3.3.3.** *Primality.* If $R := (V, (\rho_i)_{i \in I})$ is a binary structure, a subset $A$ of $V$ is autonomous if $\rho_i(x, y) = \rho_i(x', y)$ and $\rho_i(y, x) = \rho_i(y, x')$ for all $i \in I$, $x, x' \in A$ and $y \in V \setminus A$. A binary structure is prime or indecomposable if all its autonomous subsets are trivial, that is, are either $\emptyset$, singletons, or the whole set. With this definition, structures with at most two vertices are prime.

The notion of module goes back to Fraïssé [69] and Gallai [84], see also [77]. The notion we consider here is due to Gallai. The notion of Fraïssé is less demanding. A fundamental decomposition result of a binary structure into modules was obtained by Gallai [84] for finite binary relations (see [60] for further extensions).

We will need the following compactness result of Ille [98].

**Theorem 3.22.** A binary structure $R$ is prime if and only if every finite subset $F$ of its domain extends to a finite set $F'$ such that the restriction $R_{\upharpoonright F'}$ is prime.

The decompositions of a binary structure into lexicographic sums are in correspondence with the partitions of its domain into modules. Hence, if a finite binary structure is not prime, it decomposes into a sum of proper substructures indexed by some prime structure.

With Lemma 3.21, we obtain the first part of the following result.

**Theorem 3.23.** If a hereditary class $\mathfrak{C}$ of finite binary structures with a finite signature contains only finitely many prime members (up to isomorphy) then:

(1) $\mathfrak{C}$ is wqo;

(2) the cardinality of bounds of $\mathfrak{C}$ is bounded above.

**Proof.** For the second part, let $\mathfrak{D} := \text{Ind}(\mathfrak{C})$ be the set of prime members of $\mathfrak{C}$. Then $\mathfrak{C}$ is included into $\sum \mathfrak{D}$, the least subclass of $\Omega_\mu$ containing $\mathfrak{D}$ and stable by lexicographical sum indexed by members of $\mathfrak{D}$. Since $\mathfrak{D}$ is finite then, according to the first part of Theorem 3.23, $\sum \mathfrak{D}$ is wqo. Hence, $\mathfrak{C}$ has finitely many bounds in $\sum \mathfrak{D}$. If $k$ is the maximum of the cardinality of members of $\mathfrak{D}$ the bounds of $\sum \mathfrak{D}$ have size at most $k+2$. Indeed, each bound must be prime and according to a result of Schmerl and Trotter [184], each prime structure of size $\ell$ contains a prime structure of size $\ell-1$ or $\ell-2$. Consequently, the cardinality of bounds of $\mathfrak{C}$ is bounded, as claimed. $\square$

**Corollary 3.24.** There are only countably many hereditary classes $\mathfrak{C}$ of finite binary structures of finite signature containing only finitely many prime members (up to isomorphy).

The 4-element path is prime and every prime graph embeds a 4-element path (Sumner [192] for finite graphs and Kelly [106] for infinite graphs). Hence, prime cographs have at most two vertices, thus, up to isomorphism, there are only finitely many of them. The same fact holds for series-parallel graphs, hence Theorem 3.19 is a special case of (1) of Theorem 3.23.

When $\mathfrak{C}$ is made of bichains, Theorem 3.23 is due to Albert and Atkinson [2], the general case is in [142]. As we will see in Subsection 4, general results on wqo imply the boundedness of the size of bounds of several hereditary classes. The use of the Schmerl-Trotter [184] result in the proof of (2) of Theorem 3.23 can be avoided. An extension of Theorem 3.23 based on a strengthening of the notion of wqo will be given in Proposition 4.12.

One could be tempted to believe that a hereditary class of finite binary structures is wqo whenever the subclass of its prime members is wqo. This is definitively false. For an example, for each integer $n \ge 2$, let $\text{DF}_n$ be the double-ended fork of length $n$ as defined in Subsection 3.7. Let $\mathfrak{C} := \downarrow \{\text{DF}_n : n \ge 2\}$ be the collection of graphs which are embeddable into some $\text{DF}_n$. The $\text{DF}_n$'s ($n \ge 2$) form an infinite antichain, hence $\mathfrak{C}$ is not wqo. On the other hand, the prime members of $\mathfrak{C}$ consist of all finite paths, and an independent set with two vertices, thus form a wqo class.
**3.4. Well-quasi-order and better-quasi-order.** At the very beginning of the study of hereditary classes, one cannot avoid facing the problem raised by Nash-Williams about better-quasi-ordering (bqo), a notion strengthening the notion of wqo that he invented and for which he proved the fundamental results. Nash-Williams (p. 700, [139]) asserted that "one is inclined to conjecture that most wqo sets which arise in a reasonably 'natural' manner are likely to be bqo."

**Problem 3.** Is a hereditary class of finite structures with finite signature bqo whenever it is wqo?

It is not known if the answer is positive for hereditary classes of finite graphs (it is also unsolved for the class of finite graphs equipped with the minor quasi-order while, by Robertson-Seymour's theorem, this class is wqo). It is positive for the class of bipartite permutation graphs and the corresponding classes of bichains and posets mentioned in Theorem 3.45 (the proof is nontrivial, see [170]). It is also positive for the ages of almost multichainable relational structures studied in Section 5 (see Theorem 5.34). However, the answer is negative if the signature is infinite and the arity is unbounded. There are wqo ages that are not bqo. Examples are based on a construction given in [162]. We recall it in Subsection 3.4.1.

We give the minimal information needed to understand bqo. We recall that if $P$ is a poset, the Higman ordering defined in Subsection 1.4.3 on finite sequences can be extended to ordinal sequences. If $f : \alpha \to P$ and $g : \beta \to P$ are two ordinal sequences, set $f \leq g$ if there exists some injective order preserving map $h : \alpha \to \beta$ such that $f(\gamma) \leq g(\gamma)$ for all $\gamma < \alpha$. This gives a quasi-order. Given an ordinal $\alpha$, $P$ is $\alpha$-well-quasi-ordered ($\alpha$-wqo for short) if the set $P^\alpha$ of ordinal sequences $f : \alpha \to P$ is well-founded. Say that $P$ is better-quasi-ordered (bqo) if it is $\omega_1$-wqo for the first uncountable ordinal $\omega_1$. This is the shortest possible definition of bqo. It is not too difficult to prove that if $\alpha$ is an indecomposable ordinal then $P$ is $\alpha$-wqo if and only if the collection $P^{<\alpha}$ of $\beta$-sequences $f : \beta \to P$, with $\beta < \alpha$, is wqo (use Higman's theorem on words, see Theorem 3.18). For an example, $P$ is $\omega$-wqo if and only if it is wqo. Since $\omega_1$ is an indecomposable ordinal, a poset $P$ is bqo if and only if the set $P^{<\omega_1}$ is wqo. More is true, Nash-Williams [139] proved that if $P$ is bqo then the collection of all ordinal sequences with values in $P$ is bqo. For more, see the paper by Marcone [131].

A more intuitive definition of bqo presented by Laver [118] is that the transfinite iterates $I^{[\beta]}(P)$ of the set of initial segments of $P$, where $\beta$ runs through ordinal numbers, are all wqo.<fnref n="3" /> None of these definitions are easy to work with; the appropriate tools for the notion of bqo are based on the notion of *barrier* invented by Nash-Williams [139].

A basic example of a wqo poset $P$ such that $I(P)$ is not wqo was discovered by Rado. This is the set $\mathrm{Rad} := \{(n, m) \in [N]^2 : n < m\}$ ordered by $(n, m) \leq (n', m')$ if either $n = n'$ and $n \leq m'$ or $m < n'$.

Marcone [131] proved that:

**Theorem 3.25.** For each countable indecomposable ordinal $\alpha$ there is some poset $P_\alpha$ made of finite subsets of $\omega$ which is not $\alpha$-wqo but is $\beta$-wqo for every $\beta < \alpha$.

For an example, $\mathrm{Rad}$ is not $\omega^2$-wqo, but is $\beta$-wqo for every $\beta < \omega^2$.

From Marcone's result it follows that for each countable indecomposable ordinal $\alpha$ there is some poset $Q$ made of finite subset of $\omega$ such that all $I^{[\beta]}(Q)$ are wqo for $\beta < \alpha$ and $I^{[\alpha]}(Q)$ is not wqo.

The notion of bqo was invented to prove that some classes of countable structures are wqo (see Section 8 below), so one may ask why it is important to know whether wqo ages which are made of finite structures are in fact bqo. The reason is twofold. First, in several instances, the complexity of an infinite hereditary class $\mathcal{C}$ of finite structures can be better represented by a single infinite relational structure $R$ (this requiring that $\mathcal{C}$ is an age and $\mathcal{C} = \mathrm{Age}(R)$). This is one of the originalities of the approach of combinatorial problems by the theory of relations. Next, properties of families of ages can be reflected in properties of families of countable structures. For example, countable antichain of ages yield trivially countable antichains of countable structures (the same property holds with chains, see Theorem V-2.3 in [151] and also [162]). Now, if an age embeds the Rado poset, it will contain an infinite antichain of ages. Up to now, the known examples of

<footnote n="3">³This notation is to avoid confusion with the $\beta$ derivative of $I(P)$.</footnote>
ages embedding this poset and which are wqo are made of relational structures with an unbounded signature.
Such an example is given below.

3.4.1. *A construction of wqo ages which are not bqo.* The construction below is borrowed from [162], p.301.

Let $V$ be an infinite set and $\mathcal{F} \subseteq [V]^{<\omega} \setminus \{\emptyset\}$. Let $M_{\mathcal{F}} := (V, (K_F)_{F \in \mathcal{F}})$ be the relational structure, where $K_F$ is the $|F|$-ary relation on $V$ defined by $K_F(x_1, \dots, x_{|F|}) = +$ if and only if $\{x_1, \dots, x_{|F|}\} = F$. Let $U_{\mathcal{F}} := (V, (U_F)_{F \in \mathcal{F}})$ where $U_F(x_1, \dots, x_{|F|}) = -$ everywhere.

Let $\mathcal{F}^{<\omega}$ (resp., $\mathcal{F}^{\cup}$) be the collection of finite (resp., arbitrary) unions of members of $\mathcal{F}$. Given $A \subseteq V$, set $\mathring{A} := \bigcup\{F \in \mathcal{F} : F \subseteq A\}$.

**Lemma 3.26.** The age $\text{Age}(M_{\mathcal{F}})$ of $M_{\mathcal{F}}$ ordered by embeddability embeds the set $\mathcal{F}^{<\omega}$ ordered by set inclusion. It is the image of the direct product $\mathcal{F}^{<\omega} \times \omega$ by an order preserving map provided that for every $F \in \mathcal{F}^{<\omega}$ and every integer $n \in \omega$ there is some $H \in [V \setminus F]^n$ such that $(F \cup H) = F$.

**Proof.** The first assertion in the lemma is obvious. For the second assertion, let $(F, n) \in \mathcal{F}^{<\omega} \times \omega$. Observe that if $H, H' \in [V \setminus F]^n$ such that $F \cup H = F$ and $F \cup H' = F$, the restrictions $M_{\mathcal{F}} \upharpoonright F \cup H$ and $M_{\mathcal{F}} \upharpoonright F \cup H'$ are isomorphic. Hence we may set $f(F, n) = M_{\mathcal{F}} \upharpoonright F \cup H$ and by this way define an order preserving map from $\mathcal{F}^{<\omega} \times \omega$ in $\text{Age}(M_{\mathcal{F}})$. This map is trivially surjective since for every subset $X \in [V]^{<\omega}$, the restriction $M_{\mathcal{F}} \upharpoonright X$ is of the form $f(\mathring{X}, n)$ where $n = |X \setminus \mathring{X}|$. $\square$

**Corollary 3.27.** The age $\text{Age}(M_{\mathcal{F}})$ is wqo if and only if $\mathcal{F}$ contains no infinite antichain.

**Proof.** Since $\mathcal{F}$ ordered under set inclusion is well-founded, it is wqo provided it contains no infinite antichain. By Higman's Theorem, $\mathcal{F}^{<\omega}$ is wqo. Hence, the direct product $\mathcal{F}^{<\omega} \times \omega$ is wqo. By Lemma 3.26, $\text{Age}(M_{\mathcal{F}})$ is the image of the direct product $\mathcal{F}^{<\omega} \times \omega$. Thus, $\text{Age}(M_{\mathcal{F}})$ is wqo. Conversely, suppose that $\text{Age}(M_{\mathcal{F}})$ is wqo. Since it embeds $\mathcal{F}^{<\omega}$, this set is wqo. Hence $\mathcal{F}$ is wqo. $\square$

Due to Lemma 3.26, if $\mathcal{F}$ is wqo but not bqo, the age of $\text{Age}(M_{\mathcal{F}})$ is wqo and not bqo.

* Example of an age $\mathfrak{A}$ which is wqo and such that $\mathbf{I}(\mathfrak{A})$ is not wqo.

Let $\mathcal{F} := \{\{0, \dots, j\} \setminus \{i\} : 0 \le i < j < \omega\}$. Ordered by inclusion, $\mathcal{F}$ is isomorphic to $\text{Rad}$. Since $\text{Rad}$ is wqo, the age $\mathfrak{A} := \text{Age}(M_{\mathcal{F}})$ is wqo by Corollary 3.27. But, since $\text{Rad}$ embeds in $\mathfrak{A}$, $\mathbf{I}(\text{Rad})$ embeds in $\mathbf{I}(\mathfrak{A})$, hence this set is not wqo.

* Example of an age $\mathfrak{A}$ such that $\mathbf{I}(\mathfrak{A})$ is wqo but $\mathbf{I}(\mathbf{I}(\mathfrak{A}))$ is not.

Let $P$ be a poset embeddable into $[\omega]^{<\omega}$ such that $\mathbf{I}(P)$ is wqo but $\mathbf{I}(\mathbf{I}(P))$ is not. Set $V := P \cup A$, where $A$ is an infinite set disjoint from $P$. Let $\mathcal{F} := \{\downarrow x : x \in P\}$. Let $M_{\mathcal{F}}$ be as above and $\mathfrak{A} := \text{Age}(M_{\mathcal{F}})$. In terms of the theory of bqo, $\mathcal{F}$, that is $P$, is $\omega^2$-wqo but not $\omega^3$-wqo. From the extension of Higman's theorem to bqo's, it follows that $\mathcal{F}^{<\omega}$ is $\omega^2$-wqo and hence $\mathcal{F}^{<\omega} \times \omega$ is $\omega^2$-wqo. Since $\mathfrak{A}$ is a surjective image of $\mathcal{F}^{<\omega} \times \omega$, it is $\omega^2$-wqo, that is $\mathbf{I}(\mathfrak{A})$ is wqo. Since $P$ embeds in $\mathfrak{A}$ and $P$ is not $\omega^3$-wqo, $\mathfrak{A}$ is not, hence $\mathbf{I}(\mathbf{I}(\mathfrak{A}))$ is not wqo.

* A more complicated example follows from Theorem 3.25: For every indecomposable ordinal $\alpha$ there is an age $\mathfrak{A}$ such that all $\mathbf{I}^{[\beta]}(\mathfrak{A})$ are wqo for $\beta < \alpha$ and $\mathbf{I}^{[\alpha]}(\mathfrak{A})$ is not wqo.

However, our examples have unbounded signature (and an infinite kernel).

**3.5. From hereditary classes to ideals.** From Corollary 3.11, a part of the study of wqo hereditary classes of finite structures can be reduced to the study of wqo ages.

**Problem 4.** Are the previous equivalences in Proposition 3.10 still true if we replace $\mathfrak{C}$ by an age and the hereditary subclasses of $\mathfrak{C}$ by ages (see p. 167, [150])?

In order to be more specific about this problem, we gather in the theorem below obtained with Sobrani [164] various properties of the set of ages included in a given hereditary class.
**Theorem 3.28.** Let us consider the following properties of a countable hereditary class $\mathfrak{C}$ of finite structures:

(i) $\mathfrak{C}$ is bqo;

(ii) $\mathrm{Id}(\mathfrak{C})$ is wqo;

(iii) $\mathfrak{C}$ is wqo;

(iv) $\mathrm{Id}(\mathfrak{C})$ is a countable Priestley space;

(v) $\mathrm{Id}(\mathfrak{C})$ is topologically scattered;

(vi) $\mathrm{Id}(\mathfrak{C})$ is order-scattered;

(vii) every chain of $\mathrm{Id}(\mathfrak{C})$ is at most countable;

(viii) $\mathrm{Id}(\mathfrak{C})$ is well-founded;

(ix) $[\omega]^{<\omega}$ does not embed into $\mathfrak{C}$;

(x) $\wp(\omega)$ does not embed into $\mathrm{Id}(\mathfrak{C})$.

Then:

$$ (i) \Rightarrow (ii) \Rightarrow (iii) \Rightarrow (iv) \Rightarrow (v) \Rightarrow (vi) \Leftrightarrow (vii) \Leftrightarrow (viii) \Rightarrow (ix) \Leftrightarrow (x). $$

• There are ages $\mathfrak{C}$ of structures of unbounded signature such that

$$ (iii) \Leftrightarrow (ii) \Leftrightarrow (i). $$

• There are hereditary classes $\mathfrak{C}$ of finite structures with a finite signature such that $\mathrm{Id}(\mathfrak{C})$ is well-founded and has cardinality $2^{\aleph_0}$ proving that $(viii) \Leftrightarrow (v)$.

**Proof. Positive results.** The really nontrivial implication is $(vii) \Rightarrow (viii)$ ([151], Section II-3.1) and also ([150], Théorème V-4, p. 76). Implications $(i) \Rightarrow (ii) \Rightarrow (iii)$ are elementary facts about wqo.

$(iii) \Rightarrow (iv)$. Since $\mathfrak{C}$ is wqo, it is level-finite, we may apply Proposition 2.13. Hence, $\mathrm{Id}(\mathfrak{C})$ is a countable Priestley space.

$(iv) \Rightarrow (v)$. Since $\mathrm{Id}(\mathfrak{C})$ is countable and compact, it is topologically scattered (see Subsection 1.2).

$(v) \Rightarrow (vi)$. Suppose by way of contradiction that there is some embedding $f$ from the chain $\mathbb{Q}$ of rational numbers into $\mathrm{Id}(\mathfrak{C})$. Since $\mathrm{Id}(\mathfrak{C})$ is closed under unions of chains, for every $r \in \mathbb{R}$ the set $\tilde{f}(r) := \cup\{f(r') : r' < r\}$ belongs to $\mathrm{Id}(\mathfrak{C})$. This allows to define an embedding $\tilde{f} : \mathbb{R} \to \mathrm{Id}(\mathfrak{C})$. Since the image of this map has no isolated point, $\mathrm{Id}(\mathfrak{C})$ is not topologically scattered.

$(vi) \Leftrightarrow (vii)$. If $\mathrm{Id}(\mathfrak{C})$ is order scattered, an uncountable chain would contain a chain with order type $\omega_1$ or its dual $\omega_1^*$. But, this will lead to a sequence of $\aleph_1$ distinct elements of $\mathfrak{C}$. Since $\mathfrak{C}$ is countable, this is impossible.

$(vii) \Leftrightarrow (viii)$. That $(vii) \Rightarrow (viii)$ is treated in Section II-3, Proposition II.3.2 on page 143 of [151]. It makes use of a special property of ideals that we will consider in Subsection 3.6.1 (cf. Theorem 3.35), namely, the fact that for every ideal $P \in \mathrm{Id}(\mathfrak{C})$ and $x \in P$, the set $g(x, P)$ of $Q \in \mathrm{Id}(P)$ such that $\{x\} \cup Q$ generates $P$ is finite (that is no proper ideal of $P$ contains $\{x\} \cup Q$). To see the converse, note that $(viii) \Rightarrow (vi)$ is trivial and we have the implication $(vi) \Rightarrow (vii)$ above.

Finally, $(viii) \Rightarrow (x)$ is obvious since $\wp(\omega)$ is not well-founded. The equivalence $(ix) \Leftrightarrow (x)$ is Theorem 1.1, a general fact about posets.

**Negative results.** The examples given in Subsection 3.4.1 prove our first assertion. For the second, by no means trivial, an example of a hereditary class $\mathfrak{C}$ of finite structures with a finite signature such that $\mathrm{Id}(\mathfrak{C})$ is well-founded and has cardinality $2^{\aleph_0}$ is given in Proposition 7.4. $\square$

We note that Theorem 3.40 shows that the implication $(v) \Rightarrow (viii)$ remains true when the embeddability order is replaced by set containment.

Since level-finite hereditary classes are countable, they embed in $[\omega]^{<\omega}$ (to each $\tau$ belonging to a hereditary class $\mathfrak{C}$ associate the finite set $\downarrow \tau = \{\tau' \in \mathfrak{C} : \tau' \le \tau\}$). Hence we have the following dichotomy result:

**Lemma 3.29.** For every level-finite age $\mathfrak{C}$, either $\mathfrak{C}$ does not embed $[\omega]^{<\omega}$ or $\mathfrak{C}$ is equimorphic to $[\omega]^{<\omega}$.
3.5.1. A central question about ages. It is a tempting and old conjecture that all statements in Theorem 3.28 are equivalent when $\mathcal{C}$ is an age.

**Conjecture 1.** An age $\mathcal{C}$ does not embed $[\omega]^{<\omega}$ if and only if it contains no infinite antichain, that is, $\mathcal{C}$ is wqo.

Here are two subproblems, formulated in 1978, of this conjecture; see [150], I.4, p. 67.

**Problem 5.** Determine whether an age is wqo whenever

(1) the collection of its subages is well-founded with respect to set inclusion, or

(2) the collection of its subages is countable.

Implication (ii) ⇒ (v) of Theorem 3.28 asserts that condition (2) implies condition (1). But, the solutions to these problems elude us.

3.6. **Topological scatteredness versus well-quasi-ordering: an illustration of the notion of kernel.** In this subsection, we show that the topological scatteredness of the space of subages of a level-finite hereditary class of $\Omega_\mu$ implies the well-foundedness of that space ordered by set inclusion (Theorem 3.40). Proofs are based on the notions of kernel and generation.

3.6.1. **Kernel.** Let $R$ be a relational structure with domain $V$. For $X \subseteq V$, set $R_{-X} := R_{\upharpoonright V \setminus X}$; if $X := \{x\}$, resp., $X := \{x, y\}$ set $R_{-x} := R_{-X}$, resp., $R_{-x, -y} := R_{-X}$. If $S \in \text{Age}(R)$, the kernel of $S$ in $R$ is the set $\ker(S, R)$ of $x \in V$ such that $S$ does not embed in $R_{-x}$. The kernel of $R$, $\ker(R)$, is the set union of the kernels $\ker(S, R)$ for $S \in \text{Age}(R)$, that is,

$$ \ker(R) := \{x \in V : \text{Age}(R_{-x}) \neq \text{Age}(R)\}. $$

Let $a, b \in V(R)$. Set $a \leq_R b$ if $\text{Age}(R_{-a}) \subseteq \text{Age}(R_{-b})$. This defines a quasi-order on $V(R)$. It plays a crucial role in the study of the kernel. We mention the following fact (see [152], III.1.5). Other properties will be recalled in Subsection 5.4.

**Lemma 3.30.** Let $R$ be a relational structure with domain $V$ and $a, b \in V$.

(1) If $b \notin \ker(R)$ that is $\text{Age}(R_{-b}) = \text{Age}(R)$ then $\text{Age}(R_{-a, -b}) = \text{Age}(R_{-a})$;

(2) If $b \in \ker(R)$ then the initial segment $\{a \in V : a \leq_R b\}$ is finite.

**Lemma 3.31.** If the kernel of $R$ is infinite then:

(1) the set $\{\text{Age}(R_{-a}) : a \in \ker(R)\}$ is infinite;

(2) there are arbitrarily long finite chains of infinite subages of $\text{Age}(R)$.

**Proof.** (1) is an immediate consequence of (2) of Lemma 3.30.

(2). Define a sequence $(a_n, A_n)_{n \in \mathbb{N}}$. Pick $a_0 \in \ker(R)$ and $A_0$ finite such that $R_{\upharpoonright A_0} \notin R_{-a_0}$. Suppose the sequence is defined for all $n' < n$. Pick $a_n \in \ker(R) \setminus \bigcup_{n' < n} A_{n'}$ and pick $A_n$ finite such that $R_{\upharpoonright A_n} \notin R_{-a_n}$. Let $k \in \mathbb{N}$. We have:

$$ (3.1) \qquad \text{Age}(R_{-a_0, \dots, -a_k}) \subseteq \text{Age}(R_{-a_1, \dots, -a_k}) \subseteq \dots \subseteq \text{Age}(R_{-a_i, \dots, -a_k}) \subseteq \dots \subseteq \text{Age}(R_{-a_k}). $$

Since $R_{\upharpoonright A_i} \in \text{Age}(R_{-a_{i+1}, \dots, -a_k}) \setminus \text{Age}(R_{-a_i, \dots, -a_k})$ for $i = 0, \dots, k-1$, this sequence of ages is strictly increasing with respect to set inclusion. $\square$

The kernel is an invariant of the age of $R$ in the following sense: If $R$ and $R'$ have the same age, then there is an isomorphism $f$ from $R_{\upharpoonright \ker(R)}$ onto $R'_{\upharpoonright \ker(R')}$ such that

(a) every restriction of $f$ to every finite subset $F$ of $\ker(R)$ extends to every finite superset $\bar{F}$ of $F$ to an embedding of $R_{\upharpoonright \bar{F}}$ in $R'$;

(b) the same property holds for $f^{-1}$.
From (1) of Lemma 3.30, for each finite subset $F$ of $V$ disjoint from the kernel of $R$, the restriction $R_{\upharpoonright V \setminus F}$ has the same age as $R$.

Here are two other lemmas that can be found in [152], III.1.3 and [152], III.1.6, p. 323.

**Lemma 3.32.** An element $a \in V(R)$ belongs to $\ker(R)$ if and only if there is some finite subset $A$ of $V(R)$ containing all the images of $a$ by the local automorphisms defined on $A$.

**Lemma 3.33.** The kernel of $R$ is the least subset with respect to set inclusion among the subsets $K$ of $V(R)$ such that for every nonempty subset $H$ of $V(R) \setminus K$ and every finite subset $A$ of $K$ there are infinitely many local isomorphisms defined on $H$, extendible via the identity on $A$ and with pairwise disjoint images.

An age $\mathfrak{A}$ is *inexhaustible*, or has the *disjoint embedding property*, if two arbitrary members of $\mathfrak{A}$ can be embedded into a third member in such a way that the images of their domains are disjoint. Due to the fact above, the kernel of a relational structure $R$ is empty if and only if $\text{Age}(R)$ is inexhaustible. We say that an age $\mathfrak{A}$ which is not inexhaustible is *exhaustible*. It is *almost inexhaustible* if the kernel of some $R$ with age $\text{Age}(R) = \mathfrak{A}$ is finite.

Almost inexhaustible and inexhaustible structures are linked by means of reductions, which are defined as follows. Given a relational structure $R := (V, (\rho_i)_{i \in I})$ and $K \subseteq V$ a reduction of $R$ over $K$ is a relational structure $M := (V \setminus K, (\tau_j)_{j \in J})$ such that the local automorphisms of $M$ are precisely the restrictions of local isomorphisms of $R$ fixing $K$ pointwise (this is not to be confused with the notion of reduct).

**Lemma 3.34.** Let $R$ be a relational structure, $\ker(R)$ be its kernel, $r := |\ker(R)|$, and $M$ be a reduction of $R$ over $\ker(R)$. If $\ker(R)$ is finite then:

(1) $\ker(M)$ is empty.

(2) $\mathbf{H}(\text{Age}(R)) = \mathbf{H}(\text{Age}(M)) + p$, for some integer $p$, if and only if one of these heights exists.

(3) $\varphi_R(n) \le 2^r \varphi_M(n)$ and $\varphi_M(n) \le a\varphi_R(n + k)$ for some $a \in \mathbb{R}_+^*$, $k \in \mathbb{N}$, and all $n \in \mathbb{N}$.

We note that (1) is special case of Theorem 20 of [87], (2) is a special case of Theorem 4.6 of [162], and (3) can be proved in the same way as Theorem 21 of [87], using the fact that the profile does not decrease.

The notion of inexhaustibility was introduced by Fraïssé in the 1960's. The notion of kernel appears first in the special case of almost chainable structures studied by Fraïssé. He proved the existence of a smallest subset $K$ (smallest with respect to set inclusion) for which an almost chainable structure was $K$-chainable, see Subsection 5.1). The general notion was introduced in [149] and studied in several papers [152], [155], and Lemma IV-3.1, p. 37,[154], first for structures with finite signature. The general case was considered in [162].

**3.6.2. Generation of an age.** Let $\mathfrak{A}' \subseteq \mathfrak{A}$ be two ages and $S \in \mathfrak{A} \setminus \mathfrak{A}'$. We say that $\mathfrak{A}$ is generated by $\mathfrak{A}'$ and $S$ if there is no proper subage of $\mathfrak{A}$ containing $\mathfrak{A}' \cup \{S\}$. When these conditions are fulfilled then

$$ (3.2) \qquad \ker(R) = \ker(R') \cup \ker(S, R) $$

for every $R'$, $R$ such that $R'$ is a restriction of $R$, $\text{Age}(R') = \mathfrak{A}'$ and $\text{Age}(R) = \mathfrak{A}$ (see [162], Proposition 3.9). But, in principle, without some conditions, the fact that $\mathfrak{A}' \subseteq \mathfrak{A}$ does not imply the existence of $R$ and $R'$ such that $R'$ is a restriction of $R$, $\text{Age}(R') = \mathfrak{A}'$ and $\text{Age}(R) = \mathfrak{A}$. Such a condition is that $\mathfrak{A}$ is level-finite. So, in this subsection we suppose that the hereditary classes under consideration are level-finite. Let $\mathfrak{A}$ be an age and $S \in \mathfrak{A}$. We denote by $g(S, \mathfrak{A})$ the set of ages $\mathfrak{A}'$ which together with $S$ generate $\mathfrak{A}$.

We recall Proposition V-2.3 of [150], and Corollary 3.10 of [162].

**Theorem 3.35.** $g(S, \mathfrak{A})$ is finite, in fact $|g(S, \mathfrak{A})| \le 2^{\ker(S,R)}$ where $|\ker(S, R)|$ is the number of elements of $\ker(S, R)$ for any relational structure $R$ having age $\mathfrak{A}$.

Let $\mathfrak{A}' \subseteq \mathfrak{A}$ be two ages and $[\mathfrak{A}', \mathfrak{A}]$ be the set of ages $\mathfrak{B}$ such that $\mathfrak{A}' \subseteq \mathfrak{B} \subseteq \mathfrak{A}$.

Theorem 3.35 is the key of the following result (see Proposition V-3.2 of [150], Theorem 3.11 and Corollary 3.14 of [162]).
**Theorem 3.36.** Let $\mathfrak{A}' \subseteq \mathfrak{A}$ be two ages. Then the following properties are equivalent

(i) $\mathfrak{A}'$ and some $S \in \mathfrak{A}$ generate $\mathfrak{A}$.

(ii) The interval $[\mathfrak{A}', \mathfrak{A}]$ ordered by set inclusion has finite height.

(iii) The interval $[\mathfrak{A}', \mathfrak{A}]$ is finite.

In [162], Theorem 3.16 p. 314, it was shown that the interval $[\mathfrak{A}', \mathfrak{A}]$ contains an infinite chain (and in fact a chain of order type $\omega$) whenever it is infinite. More precisely:

**Theorem 3.37.** Two ages $\mathfrak{A}'$ and $\mathfrak{A}$ be given with $\mathfrak{A}' \subset \mathfrak{A}$ be given, if the set $[\mathfrak{A}', \mathfrak{A}]$ of ages $\mathfrak{B}$ such that $\mathfrak{A}' \subseteq \mathfrak{B} \subseteq \mathfrak{A}$ is infinite, then this set contains a chain of ages with order type $\omega + 1$.

We will use this result for the proof of Proposition 5.49 below.

We will use an other consequence (part (a) is Proposition 4.7, p. 325 of [157]).

**Corollary 3.38.** Let $\mathfrak{A}$ be an age such that $\mathrm{Id}(\mathfrak{A})$ is well-founded;

(a) If $\mathfrak{A}$ is inexhaustible, then $\mathbf{H}(\mathfrak{A})$ is a limit ordinal;

(b) If $\mathfrak{A}$ is a strictly increasing union of inexhaustible ages then $\mathbf{H}(\mathfrak{A}) \ge \omega^2$.

**Proof.** (a). Suppose that $\mathbf{H}(\mathfrak{A}) = \alpha + 1$. There is some $\mathfrak{A}' \in \mathrm{Id}(\mathfrak{A})$ such that $\mathfrak{A}' = \alpha$. Then the interval $[\mathfrak{A}', \mathfrak{A}]$ has two elements. According to Theorem 3.36, there is some $S \in \mathfrak{A}$ such that $\mathfrak{A}'$ and $S$ generate $\mathfrak{A}$. If $R'$, $R$ are such that $\mathrm{Age}(R') = \mathfrak{A}'$ and $\mathrm{Age}(R) = \mathfrak{A}$ then, from Equation 3.2, $\mathrm{ker}(R) = \mathrm{ker}(R') \cup \mathrm{ker}(S, R)$. Hence $\mathrm{ker}(S, R) \ne \emptyset$. This proves that $\mathfrak{A}$ is not inexhaustible. (b). This is an immediate consequence of (a).

□

3.6.3. *Height of an age and Cantor-Bendixson rank.* A link between the height of an age and its Cantor-Bendixson rank (when defined) is given by the following proposition. The first part is Proposition V-3.2 in [150] (with a small improvement). The second part is in [164].

**Proposition 3.39.** Let $\mathfrak{C}$ be a hereditary class of finite structures which is level-finite, $\mathrm{Id}(\mathfrak{C})$ be the set of ages included in $\mathfrak{C}$, equipped with the product topology, $\alpha$ be an ordinal and $\mathfrak{A} \in \mathrm{Id}^{(\alpha)}(\mathfrak{C})$.

(1) $\mathfrak{A}$ is above some minimal element of $\mathrm{Id}^{(\alpha)}(\mathfrak{C})$. If $\mathfrak{A}$ is minimal, then $\mathrm{Id}(\mathfrak{A})$ is well-founded and $\mathbf{H}(\mathfrak{A}) \le \omega.\alpha$, where $\mathbf{H}(\mathfrak{A}) := h(\mathfrak{A}, \mathrm{Id}(\mathfrak{C}))$ as defined by formula (1.1); furthermore, if $\mathfrak{A}$ has finitely many bounds in $\mathfrak{C}$ then it has Cantor-Bendixson rank $\alpha$.

(2) If $\mathfrak{A}$ has Cantor-Bendixson rank $\alpha$, that is $\mathfrak{A} \notin \mathrm{Id}^{(\alpha+1)}(\mathfrak{C})$, then $\mathrm{Id}(\mathfrak{A})$ is well-founded and
$$ \mathbf{H}(\mathfrak{A}) < \omega \cdot (\alpha + 1). $$

(3) If $\mathfrak{A}$ has finitely many bounds and $\mathrm{Id}(\mathfrak{A})$ is wqo then $\mathfrak{A}$ has a Cantor-Bendixson rank in $\mathrm{Id}(\mathfrak{C})$ and if $\beta$ is its rank, then

$$ (3.3) \qquad \omega.\beta \le \mathbf{H}(\mathfrak{A}) < \omega \cdot (\beta + 1). $$

**Proof.** (1). Since $\mathfrak{C}$ is level-finite, $\mathrm{Id}(\mathfrak{C})$ is compact for the product topology (Proposition 2.13). Being closed, $\mathrm{Id}^{(\alpha)}(\mathfrak{C})$ is compact too, hence closed under the intersection of every chain of ages. Zorn's lemma ensures that every element of $\mathrm{Id}^{(\alpha)}(\mathfrak{C})$ contains some element, minimal for set inclusion. If $\mathfrak{A}$ is a minimal element of $\mathrm{Id}^{(\alpha)}(\mathfrak{C})$ then no element of $\mathrm{Id}(\mathfrak{A}) \setminus \{\mathfrak{A}\}$ is in $\mathrm{Id}^{(\alpha)}(\mathfrak{C})$, thus all are in $\mathrm{Id}^{(<\alpha)}(\mathfrak{C})$. If $\mathfrak{A}$ has finitely many bounds in $\mathfrak{C}$ then there is a clopen set reduced to $\mathrm{Id}(\mathfrak{A})$, hence $\mathfrak{A}$ has Cantor-Bendixson rank $\alpha$. If, in general, we cannot ensure that $\mathfrak{A}$ has Cantor-Bendixson rank, then since every $\mathfrak{A}' \subset \mathfrak{A}$ has some rank $\alpha' < \alpha$, the truth of (2) proved below ensures that every $\mathrm{Id}(\mathfrak{A}')$ is well-founded, hence $\mathrm{Id}(\mathfrak{A})$ is well-founded, and $\mathbf{H}(\mathfrak{A}') \le \omega.\alpha' + p' < \omega.\alpha$. Hence, $\mathbf{H}(\mathfrak{A}) \le \omega.\alpha$.

The proofs of (2) and (3) are by induction on $\alpha$.

(2). If $\alpha = 0$ then, as it is easy to see, $\mathfrak{A}$ is the age of a finite structure, hence $\mathrm{Id}(\mathfrak{A})$ is finite and thus, $\mathfrak{A}$ is well-founded, $\mathbf{H}(\mathfrak{A}) < \omega$ and our assertion holds. Let $\alpha > 0$. Suppose that our assertion holds for every $\alpha' < \alpha$. Our aim is to prove that there exists some integer $n$ such that $\mathrm{Id}(\mathfrak{A}')$ is well-founded and $\mathbf{H}(\mathfrak{A}') \le \omega.\alpha + n$ for all $\mathfrak{A}' \in \mathrm{Id}(\mathfrak{A})$. Since $\mathrm{rank}(\mathfrak{A}, \mathrm{Id}(\mathfrak{C})) = \alpha$, there is a clopen set $U \subseteq \mathrm{Id}(\mathfrak{C})$ containing
A such that $\text{rank}(\mathfrak{A}', \text{Id}(\mathfrak{C})) < \alpha$ for every $\mathfrak{A}' \in U \setminus \{\mathfrak{A}\}$. Such a clopen set $U$ is of the form $[F, \mathfrak{C} \setminus H)$ for some finite subsets $F$ and $H$ of $\mathfrak{C}$. Since $\mathfrak{A} \supseteq F$ and $F$ is finite, there is some $S \in \mathfrak{A}$ which dominates $F$. Let $\mathfrak{A}' \subseteq \mathfrak{A}$. If $S \in \mathfrak{A}' \neq \mathfrak{A}$ then $\alpha' := \text{rank}(\mathfrak{A}', \text{Id}(\mathfrak{C})) < \alpha$. Via the inductive hypothesis, $\text{Id}(\mathfrak{A}')$ is well-founded and $\mathbf{H}(\mathfrak{A}') < \omega.(\alpha' + 1) \leq \omega.\alpha$. If $S \notin \mathfrak{A}'$, then $\text{Id}(\mathfrak{A}')$ must be well-founded. Otherwise, since by Theorem 3.35, $g(S, \mathfrak{A})$ is finite, $\text{Id}(\mathfrak{A}')$ contains some $\mathfrak{A}''$ such that $\text{Id}(\mathfrak{A}'')$ is not well-founded and, with $S$, does not generate $\mathfrak{A}$. So, there is an age $\mathfrak{B}$ such that $S \cup \mathfrak{A}'' \subseteq \mathfrak{B} \subset \mathfrak{A}$. Since $\text{rank}(\mathfrak{B}, \text{Id}(\mathfrak{C})) < \alpha$, the induction hypothesis ensures that $\text{Id}(\mathfrak{B})$ is well-founded. Since this is not the case, we have a contradiction. To achieve our aim, suppose by contradiction that, for each integer $n$, there is some $\mathfrak{A}_n \in \text{Id}(\mathfrak{A})$ not containing $S$ such that $\mathbf{H}(\mathfrak{A}_n) \geq \omega.\alpha + n$. Since by Theorem 3.35, $g(S, \mathfrak{A})$ is finite, there is some $n$ and some age $\mathfrak{B}$ such that $\{S\} \cup \mathfrak{A}_n \subseteq \mathfrak{B} \subset \mathfrak{A}$. Since $\text{rank}(\mathfrak{B}, \text{Id}(\mathfrak{C})) < \alpha$, induction hypothesis ensures that $\mathbf{H}(\mathfrak{B}) < \omega.\alpha$. Since $\mathfrak{A}_n \subseteq \mathfrak{B}$, $\mathbf{H}(\mathfrak{A}_n) \leq \mathbf{H}(\mathfrak{B}) < \omega.\alpha$, which is impossible.

(3). Since $\mathfrak{A}$ is wqo, $\text{Id}(\mathfrak{A})$ is topologically scattered. Hence, every member of $\text{Id}(\mathfrak{A})$ has a rank in $\text{Id}(\mathfrak{A})$. Since $\mathfrak{A}$ has finitely many bounds in $\mathfrak{C}$, it has the same rank in $\text{Id}(\mathfrak{C})$ as in $\text{Id}(\mathfrak{A})$. If $\alpha = 0$, whatever $\mathfrak{A}$ is, $\mathbf{H}(\mathfrak{A}) \geq 0$, hence the inequalities hold. Suppose $\alpha > 0$. By definition of the rank of $\mathfrak{A}$ there is a clopen set $U \subseteq \text{Id}(\mathfrak{C})$ containing $\mathfrak{A}$ such that $\alpha = \sup\{\text{rank}(\mathfrak{A}', \text{Id}(\mathfrak{C})) + 1 : \mathfrak{A}' \in U \setminus \{\mathfrak{A}\}\}$. We consider two cases. **Case 1.** $\alpha$ is a successor ordinal, that is, $\alpha = \alpha' + 1$. In this case $U$ contains an infinite sequence $(\mathfrak{A}_n)_{n<\omega}$ with $\text{rank}(\mathfrak{A}_n, \text{Id}(\mathfrak{C})) \geq \alpha'$ for each $n < \omega$. Since $\text{Id}(\mathfrak{A})$ is wqo, we may extract a sequence $(\mathfrak{A}_{\varphi(n)})_{n<\omega}$ which is increasing with respect to set inclusion. Via the induction hypothesis, $\mathbf{H}(\mathfrak{A}_{\varphi(0)}) \geq \omega.\alpha'$. Hence $\mathbf{H}(\mathfrak{A}) \geq \omega.\alpha' + 1 + \dots + 1 + \dots = \omega.\alpha' + \omega = \omega.(\alpha' + 1) = \omega.\alpha$ as required. **Case 2.** $\alpha$ is a limit ordinal. In this case $\alpha = \sup\{\alpha_n : n < \omega\}$ with each $\alpha_n < \alpha$. For each $n < \omega$, we may select $\mathfrak{A}_n \subset \mathfrak{A}$ with $\text{rank}(\mathfrak{A}_n, \text{Id}(\mathfrak{C})) \geq \alpha_n$. Via the induction hypothesis, $\mathbf{H}(\mathfrak{A}_n) \geq \omega.\alpha_n$. Since $\mathbf{H}(\mathfrak{A}) \geq \mathbf{H}(\mathfrak{A}_n)$ the inequality $\mathbf{H}(\mathfrak{A}) \geq \omega.\alpha$ follows. $\square$

The following problem is open, see V-5.2, p. 77 in [150].

**Problem 6.** Let $\mathfrak{A}' \subseteq \mathfrak{A}$ be two ages. If $\mathfrak{A}'$ has a rank in $\text{Id}(\mathfrak{A})$, does every age $\mathfrak{A}''$ included in $\mathfrak{A}'$ has a rank in $\text{Id}(\mathfrak{A})$ and, if this is the case, does the inequality $\text{rank}(\mathfrak{A}'', \text{Id}(\mathfrak{A})) \leq \text{rank}(\mathfrak{A}', \text{Id}(\mathfrak{A}))$ hold?

The first inequality in Equation 3.3 cannot hold without some condition on $\mathfrak{A}$. This is clear if instead of an age we consider a level-finite poset $P$. If $P$ is the Rado poset, then $\text{rank}(P, \text{Id}(P)) = 2$ and $h(P, \text{Id}(P)) = \omega + 1$. But if $P := [\omega]^2$ (the subset of the direct product $\omega \times \omega$ ordered componentwise), $\text{rank}(P, \text{Id}(P)) = 2$ and $h(P, \text{Id}(P)) = \omega \cdot 2$. The first example given in 3.4.1 yields a concrete example of an age falsifying the stated inequality but the kernel is infinite and the signature is unbounded.

**Problem 7.** Is $\omega.\text{rank}(\mathfrak{A}, \text{Id}(\mathfrak{A})) \leq \mathbf{H}(\mathfrak{A})$ whenever the signature of members of $\mathfrak{A}$ is finite?

If $\text{Id}(\mathfrak{C})$ is topologically scattered, then every $\mathfrak{A} \in \text{Id}(\mathfrak{C})$ has a Cantor-Bendixson rank. Hence (2) of Proposition 3.39 yields:

**Theorem 3.40.** If the set $\text{Id}(\mathfrak{C})$ of ages of a level-finite hereditary class $\mathfrak{C}$ of finite structures is topologically scattered for the product topology then it is well-founded with respect to set inclusion.

In Section 5.4, it will be shown that ages of height less than $\omega^2$ have only finitely many bounds (Theorem 5.34 and Theorem 5.42) and the collection of their subages is wqo (Theorem 5.34). With that fact and the above result we obtain the following result. (This was announced in [150] and a proof given in Corollaire p.6 in "Caractérisation combinatoire et topologique des âges les plus simples" [149] but not published.)

**Theorem 3.41.** Let $\mathfrak{C}$ be a level-finite hereditary class of finite structures and $n$ be an integer.

(1) An age $\mathfrak{A} \in \mathfrak{C}$ has a Cantor-Bendixson rank $n$ in $\text{Id}(\mathfrak{C})$ if and only if $\text{Id}(\mathfrak{A})$ is well-founded and $\omega \cdot n \leq \mathbf{H}(\mathfrak{A}) < \omega \cdot (n+1)$.

(2) If $\text{Id}^{(n)}(\mathfrak{C})$ is nonempty then the set of isolated points it contains is dense.

**Proof.** Let $\mathfrak{A} \in \mathfrak{C}$ with Cantor-Bendixson rank $n$ in $\text{Id}(\mathfrak{C})$. According to (2) of Proposition 3.39, $\text{Id}(\mathfrak{A})$ is well-founded and $\mathbf{H}(\mathfrak{A}) < \omega \cdot (n+1)$. According to Theorems 5.34 and 5.42 given in Subsection 5.4,
A is the age of an almost multichainable structure, hence it has finitely many bounds and the collection of subages is wqo. According to (3) of Proposition 3.39, $H(A) \ge \omega \cdot n$. Conversely, if $\mathrm{Id}(A)$ is well-founded and $\omega \cdot n \le H(A) < \omega \cdot (n+1)$, then due to Theorem 5.34 and 5.42, A has finitely many bounds and the collection of subages is wqo. Thus, in virtue of (3), A has rank $n$. Let us prove that (2) holds. Let $U$ be a clopen set intersecting $\mathrm{Id}^{(n)}(C)$. Take a minimal element $A$ w.r.t. set inclusion. Apply (1) of Proposition 3.39. Then, $H(A) < \omega \cdot (n+1)$. As said, A has finitely many bounds, hence by (3) of Proposition 3.39, $\mathrm{rank}(A, \mathrm{Id}(C)) = n$, that is A is isolated in $\mathrm{Id}^{(n)}(C)$. $\square$

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

**3.6.4. Vietoris topology.** Sobrani and I observed that the Vietoris topology seems to be appropriate to study ideals of a poset when the collection of ideals is well-founded and not necessarily well-quasi-ordered. We give some hints. Details are in [164], a paper to appear soon.

Let $P$ be a set and $F, H \subseteq P$ with $F \subseteq H$. Set $[F, H] := \{X \in \wp(P) : F \subseteq X \subseteq H\}$. The collection $\{[F, H] : F \in [P]^{<\omega}, H \subseteq P\}$ is the basis of a topology on $\wp(P)$, the *Vietoris topology*. Since the collection $\{[F, P \setminus H] : F, H \in [P]^{<\omega}\}$ is a basis of the product topology, the Vietoris topology is finer than the product topology.

If $P$ is wqo, there is no need to consider the Vietoris topology induced on the set $\mathrm{Id}(P)$ of ideals of $P$. Indeed:

**Lemma 3.42.** Let $P$ be a poset. Then the following properties are equivalent:

(i) $P$ is wqo.

(ii) The Vietoris topology and the product topology induced on $\mathbb{I}(P)$ coincide.

(iii) (a) The Vietoris topology and the product topology induced on $\mathrm{Id}(P)$ coincide.

(b) $\mathrm{Id}(P)$ is compact w.r.t. the product topology.

We may apply the Cantor-Bendixson reduction process to $\mathrm{Id}(P)$ equipped with the Vietoris and product topologies induced by $\wp(P)$. It is immediate to observe that an element $Q \in \mathrm{Id}(P)$ is isolated for the Vietoris topology if and only if $Q = \downarrow a$ for some $a \in P$. This generalizes as follows: to each nonempty up-directed poset $Q$ associate, whenever possible, an ordinal, $\mathrm{rank}_{\nu}(Q)$, the *Vietoris rank*, by the following rules:

* $\mathrm{rank}_{\nu}(Q) := 0$ if $Q$ has a largest element;

* assuming that all $Q'$ such that $\mathrm{rank}_{\nu}(Q') < \alpha$ are defined, we set $\mathrm{rank}_{\nu}(Q) := \alpha$ if $\mathrm{rank}_{\nu}(Q)$ is not strictly less than $\alpha$ and there is some element $x \in Q$ such that $\mathrm{rank}_{\nu}(Q') < \alpha$ for each $Q' \in \mathrm{Id}_x(Q) \setminus \{Q\}$, where $\mathrm{Id}_x(Q) := \{Q' : x \in Q' \in \mathrm{Id}(Q)\}$.

For example, if $Q$ is up-directed, $\mathrm{rank}_{\nu}(Q) = 1$ if and only if $Q$ has no largest element and there is some $x \in Q$ such that every proper ideal of $Q$ containing $x$ has a largest element.

**Lemma 3.43.** Let $P$ be a poset and $Q \in \mathrm{Id}(P)$. Then $\mathrm{rank}_{\nu}(Q)$ is the topological rank of $Q$ in $\mathrm{Id}(P)$ equipped with the Vietoris topology.

Since the Vietoris topology is finer than the product topology, $\mathrm{Id}(P)$ is scattered for the Vietoris topology whenever it is scattered for the product topology. The converse does not hold (think about the binary tree). For hereditary classes, we have:

**Theorem 3.44.** For every level-finite hereditary class $\mathcal{C}$ of finite structures, the set of ages $\mathrm{Id}(\mathcal{C})$ is scattered for the Vietoris topology if and only if it is well-founded with respect to set inclusion.

**3.7. The case of ages of posets coverable by two chains.** Recently, Imed Zaguia and I [170] realized that the four types of ages described in the introduction of this section are equal for ages consisting of finite posets coverable by two chains. We also show that the answer to Conjecture 1 is positive. The full result reads as follows.
**Theorem 3.45.** Let $\mathcal{B}$ be a bichain, $P := o(\mathcal{B})$ and $G := \text{Inc}(P)$. If $P$ is coverable by two chains and $\mathcal{C}$ is the age of one of these structures and if $\text{Id}(\mathcal{C})$ is the collection of ages included into $\mathcal{C}$ then the following propositions are equivalent.

(i) $\mathcal{C}$ is bqo;

(ii) $\mathcal{C}$ is wqo;

(iii) $\text{Id}(\mathcal{C})$ is countable;

(iv) $\text{Id}(\mathcal{C})$ is well-founded;

(v) $\wp(\mathbb{N})$ does not embed in $\text{Id}(\mathcal{C})$;

(vi) $[\omega]^{<\omega}$ does not embed in $\mathcal{C}$.

The equivalence of (ii) and (vi) is in Corollary 50 of [170]. The equivalence between (i) and (ii) is a consequence of Theorem 10 of [170]. Theorem 3.28 asserts that the implications (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (iv) $\Rightarrow$ (v) $\Rightarrow$ (vi) hold. We will give a hint of the implication $\neg(ii) \Rightarrow \neg(vi)$, which follows from properties of double-ended forks.

A double-ended fork $\text{DF}_n$ of length $n$, for $n \ge 1$, is the graph obtained from a path $P_n$ on $n$ vertices by adding two vertices adjacent to each end vertex of $P_n$, these two vertices being nonadjacent.

<figure><img src="image_3.png" /><figcaption>FIGURE 1. Double-ended forks</figcaption></figure>

**Theorem 3.46.** Let $\mathcal{C}$ be an age made of finite bipartite permutation graphs. Then $\mathcal{C}$ is not wqo if and only if it contains the age of a direct sum $\bigoplus_{i \in I} \text{DF}_i$ of double-ended forks of arbitrarily large length for some infinite subset $I$ of $\mathbb{N}$.

With this in hand, the proof of the implication $\neg(ii) \Rightarrow \neg(vi)$ goes as follows. Suppose that $\mathcal{C} = \text{Age}(G)$ and (ii) does not hold. Apply Theorem 3.46. Since $\mathcal{C}$ contains an infinite antichain, there is a infinite subset $I$ of $\mathbb{N}$ such that $\text{Age}(\bigoplus_{n \in I} \text{DF}_n) \subseteq \mathcal{C}$. For every finite subset $F$ of $I$, set $\varphi(F) := \bigoplus_{n \in F} \text{DF}_n$. This leads to an embedding of $[I]^{<\omega}$, the set of finite subsets of $I$, ordered by set inclusion, in $\text{Id}(\mathcal{C})$, hence an embedding of $[\omega]^{<\omega}$ in $\text{Id}(\mathcal{C})$, since, as posets, $[I]^{<\omega}$ and $[\omega]^{<\omega}$ are isomorphic. Hence (v) does not hold. Now, if $\text{Age}(B)$ or $\text{Age}(P)$ are not wqo, note that $\text{Age}(G)$ is not wqo. To the infinite antichain of $\text{DF}_n$ with $n \in I$ as above corresponds an antichain in $\text{Age}(B)$ and in $\text{Age}(P)$ and it yields an embedding of $[\omega]^{<\omega}$ in $\text{Age}(B)$ and in $\text{Age}(P)$. Hence $\neg(ii) \Rightarrow \neg(vi)$ holds for $\mathcal{C} = \text{Age}(B)$ and for $\text{Age}(P)$ as well.

Theorem 3.46 above is Theorem 14 of [170]. It extends previous results of Korpelainen and Lozin, Theorem 26 in [108], and of Lozin and Mayhill, Theorem 7 in [125].

**Problem 8.** Extend Theorem 3.45 to arbitrary bichains.

3.7.1. *A parallel development: ideals in join-semilattices.* We do not know how to characterize Priestley spaces made of ages of a hereditary class. Ages have much in common with ideals of a join-semilattice. In terms of orders, these ideals form an algebraic lattice. With Sobrani [164] and Chakir [39], [37] we studied the length of chains in algebraic lattices. Replacing in Theorem 3.28 the poset $\Omega_\mu$ by the lattice $\mathbf{I}_{<\omega}(Q)$ of a well-founded poset $Q$ and replacing the age $\mathcal{C}$ by the join-semilattice $P$ of $\mathbf{I}_{<\omega}(Q)$ generated by some
subposet of $\mathcal{Q}$, we proved in that case that the properties in Theorem 3.28 are equivalent (see Theorem 4.16 and Corollary 4.17 of [39]). We deduced the following result (Corollary 1.8):

**Lemma 3.47.** A join-subsemilattice of $[\omega]^{<\omega}$ contains either $[\omega]^{\omega}$ as a join-subsemilattice or is wqo.

Some examples of ages fit in this frame. For example, let $P$ be made of finite direct sums of finite chains; as a poset it is isomorphic to $\mathbf{I}_{<\omega}(\omega \times \omega)$. Then $\mathbf{Id}(P)$ is isomorphic to $\mathbf{I}(\omega \times \omega)$. Hence $\mathbf{H}(P) := h(P, \mathbf{Id}(P)) = h(\omega \times \omega, \mathbf{I}(\omega \times \omega)) = o(\omega \times \omega) = \omega^2$, while $o(\mathbf{Id}(P)) = \omega^{\omega+2} + 1$. Other examples were given in 3.4.1.

The exact relationship between the ordinal lengths of a well-quasi-ordered subset $A$ of $[\omega]^{<\omega}$ and the poset $\mathbf{I}_{<\omega}(A)$ of finitely generated initial segments of $A$ can be obtained. Write $o(A) = \omega \cdot \xi + p$ where $p$ is the cardinality of the largest finite final segment $\check{A}$ of $A$. Then $o(\mathbf{I}_{<\omega}(A)) = \omega^{\xi} \cdot q$ where $q$ is the cardinality of $\mathbf{F}(\check{A})$, the set of final segments of $\check{A}$ (see [164]).

## 4. LABELLING AND WELL-QUASI-ORDERING

In this section, we discuss the preservation of well-quasi-order by labelling. There are several notions for which the eventual equivalence is not known. When they hold they have some strong consequences, notably on the finiteness of bounds of hereditary classes, as will be illustrated in Section 5.

**4.1. Extensions of well-quasi-ordering to labelled classes.** The concatenation of two relational structures $R$ and $S$ on the same domain is the relational structure, denoted by $R \cdot S$, made of the relations of $R$ followed by the relations of $S$. Let $P$ be a poset. A labelling of a relational structure $R$ by $P$ is a map $f$ from $V(R)$, the domain of $R$, into $P$. Let $\mathcal{C}$ be a class of relational structures with a fixed signature $\mu$. Denote by $\mathcal{C} \cdot P$ the class of relational structures $R \in \mathcal{C}$ labelled by $P$, that is, the class of pairs $(R, f)$ with $f : V(R) \to P$. We quasi-order $\mathcal{C} \cdot P$ by dominance:

$$ (4.1) \quad (R, f) \le (R', f') \text{ if there is an embedding } h : R \to R' \text{ such that } f(x) \le f'(h(x)) \text{ for all } x \in V(R). $$

**Examples 4.1.** Suppose that $P = \{0,1\}$ with 0 incomparable to 1. Then $\mathcal{C} \cdot P$ with this quasi-order is isomorphic to the collection $\mathcal{C}_{[1]}$ made of concatenats $R \cdot U$ where $R \in \mathcal{C}$ and $U$ is a unary relation on $V(R)$, this collection being quasi-ordered by embeddability. More generally, let $m$ be an integer and $P$ be an antichain of size $2^m$ then $\mathcal{C} \cdot P$ with the quasi-order above is isomorphic to the collection $\mathcal{C}_{[m]}$ made of concatenats $R \cdot U_1 \cdots U_m$ where $R \in \mathcal{C}$ and $U_1, \dots, U_m$ are $m$ unary relation on $V(R)$, this collection being quasi-ordered by embeddability. Indeed, let us identify the $2^m$-element antichain $P$ with $\wp(\{1, \dots, m\})$, the power set of $\{1, \dots, m\}$, ordered by the equality relation. To $f : V \to \wp(\{1, \dots, m\})$ associate $U(f) := (U_1, \dots, U_m)$ where $U_i := \{x \in V(R) : i \in f(x)\}$. Clearly $(R, f) \le (R', f')$ if and only $R \cdot U(f) \le R' \cdot U(f')$. More interestingly, order $\wp(\{1, \dots, m\})$ with the inclusion order, in this case $R \cdot U_1 \cdots U_m \le R' \cdot U'_1 \cdots U'_m$ means that there is some embedding $h : R \to R'$ such that $x \in U_i$ implies $h(x) \in U'_i$ for every $x \in V(R)$ and $i := 1, \dots, m$.

Let $R$ be a relational structure and $m$ be a nonnegative integer. A labelling of $R$ with $m$ constants is the structure $R$ with $m$ distinguished elements $a_1, \dots, a_m$ of $V(R)$ added. An embedding of $(R, a_1, \dots, a_m)$ into $(R', a'_1, \dots, a'_m)$ is an embedding $f$ of $R$ into $R'$ such that $f(a_i) = a'_i$ for $i = 1, \dots, m$. If $\mathcal{C}$ is a class of structures, we denote by $\mathcal{C}_{[m-]}$ the class of $(R, a_1, \dots, a_m)$ where $R \in \mathcal{C}$. Such type of labelling and embedding is a special case of the one mentioned above: we label by unary relations which take value 1 on exactly one element.

With these notions of labelling we may strengthen the notion of wqo. Let $\mathcal{C}$ be a class of relational structures. If $m$ is a nonnegative integer, we say that $\mathcal{C}$ is $m$-wqo, resp., $m^-$-wqo, if $\mathcal{C}_{[m]}$, resp. $\mathcal{C}_{[m^-]}$, is wqo. We say that $\mathcal{C}$ is very well-quasi-ordered, in short vwqo, if $\mathcal{C}$ is $m$-wqo for every integer $m$. Let $P$ be a wqo, we say that $\mathcal{C}$ is $P$-wqo if $\mathcal{C} \cdot P$ is wqo. With this notion, $\mathcal{C}$ is vwqo if and only if $\mathcal{C}$ is $P$-wqo for every finite poset $P$. We say that $\mathcal{C}$ is hereditarily wqo if $\mathcal{C}$ is $P$-wqo for every wqo $P$. We have to reserve this latter notion for classes of finite structures. Indeed, if $R$ is the chain $\omega$ of the integers, the fact that $\{R\} \cdot P$
is wqo is equivalent to the fact that $I(P)$ is wqo. The example of Rado Rad is wqo but $I(\mathrm{Rad})$ is not wqo. Thus, for infinite structures the appropriate notion is rather that of hereditarily bqo.

**Examples 4.2.** Trivially, every finite union of hereditarily wqo classes is hereditarily wqo; hence every finite subclass $\mathcal{C}$ of $\Omega_\mu$ is hereditarily wqo. More interestingly, if Chain is the class of finite chains, the class Chain-A of finite chains labelled by a poset $A$ can be identified with the set $A^*$ of finite words over the alphabet $A$ equipped with the Higman ordering. The fact that Chain is hereditarily wqo is Theorem 3.18. More generally the collection of finite direct sums of finite chains is hereditarily wqo. In fact, the collection of finite series-parallel posets is hereditarily wqo (apply the full version of Higman's theorem, namely Theorem 3.17). More examples follow from the following two facts.

**Fact 1.** If $\mathcal{C}$ is hereditarily wqo then its image by a free operator is hereditarily wqo.

In particular, the ages of structures freely interpretable by a chain are hereditarily wqo. These ages are the basic blocks in a construction of ages. Their properties are given in Subsection 5.1.

**Fact 2.** If $\mathcal{C}$ is a class of finite relational structures, $\mathcal{C}$ is hereditarily wqo if and only if $\downarrow \mathcal{C}$, its downward closure, is hereditarily wqo.

For an example, the class Tree of finite ordered structured trees is hereditarily wqo since by Kruskal's Theorem, the class Tree-A of structured trees labelled by a wqo poset $A$ is wqo. Hence, $\downarrow$ Tree is hereditarily wqo.

Given a hereditary class $\mathcal{C}$, the relationship between the wqo character of $\mathcal{C}_{[m]}$ and $\mathcal{C}_{[m-1]}$ for various $m$ is almost totally unknown. We have examples demonstrating that: (1) there are ages of graphs which are wqo but not $1^-$-wqo; (2) there are ages of graphs which are $1^-$-wqo but not $2^-$-wqo.

**Examples 4.3.** Regarding (2), the age of an infinite path is $1^-$-wqo but not $2^-$-wqo. The age of an infinite path consists of direct sums of finite paths. As seen in Example 3.20, it is wqo. The collection of finite paths with one label is isomorphic to the set of pairs $(n, m) \in \omega \times \omega$ such that $n \le m$, thus is wqo. Hence, from Lemma 3.21, the set of direct sums of finite paths with at most one label is wqo. With two labels, it is not wqo. Indeed, let $\overline{P}_n$ be the $n$-vertex path $(n \ge 2)$ with two constants, one for each extremity of the path. Then the family of these labelled paths is an antichain. The example given at the end of Subsection 3.7 is an adaptation (experience shows that all antichains of graphs are built by an appropriate adaptation of this, but no theorem has emerged yet).

Regarding (1), if $\mu$ is a word on a 2-letter alphabet which is uniformly recurrent then the age of the graph $G_\mu$ defined in Subsection 7 is wqo (this age is minimal prime by Theorem 7.16 and wqo by Theorem 7.23). If $\mu$ is uniformly recurrent and non periodic, then the age of $G_\mu$ is not $1^-$-wqo. The fact that this age is not $1^-$-wqo follows essentially from the fact that the collection $\mathrm{Fac}(\mu)$ of finite factors of $\mu$ is not wqo for the prefix ordering $(\alpha \le_{\mathrm{pref}} \beta$ if $\beta = \alpha.\gamma$ for some word $\gamma$). The argument for this fact is not difficult. If $\mathrm{Fac}(\mu)$ was wqo, it will be a finite union of ideals. For each nonnegative integer $n$, the set $\mathrm{Pref}(\mu, n)$ made of finite prefixes of $\mu_{\upharpoonright[n,\infty[}$ is an infinite ideal of $\mathrm{Fac}(\mu)$ for the prefix order. Any infinite ideal (for this ordering) of $\mathrm{Fac}(\mu)$ is made of the prefixes of some infinite word, hence it does not contain an infinite proper ideal. Consequently, there are two distinct nonnegative integers $n$ and $m$ such that $\mathrm{Pref}(\mu, n) = \mathrm{Pref}(\mu, m)$. From this follows that $\mu$ is eventually periodic, a contradiction.

The notion of very-well-quasi-ordered class appeared in 1972 in our note [147] (under the French name *très belle classe*). The following problems emerged at this time; up to now they are unsolved.

**Problems 9.** Let $\mathcal{C}$ be a class of finite relational structures.

(1) Is it true that $\mathcal{C} \cdot P$ is wqo for every wqo $P$ whenever $\mathcal{C}_{[1]}$ is wqo? whenever $\mathcal{C}_{[2^-]}$ is wqo?

(2) Let $P$ be a wqo. Is it true that $\mathcal{C} \cdot P$ is wqo whenever $\mathcal{C} \cdot P'$ wqo for every finite $P' \le P$?

(3) Is it true that $\mathcal{C}$ is 1-wqo whenever it is $m^-$-wqo for every integer $m$? Note that the converse trivially holds.
For some categories of finite structures, the answer is negative. Kriz and Sgall [111] constructed for each integer $n$ a concrete category of finite objects, say $\mathfrak{C}$, such that $\mathfrak{C}$ labelled by an $n$-element chain is wqo and $\mathfrak{C}$ labelled by a $n+1$-element chain is not. More generally, they show by a clever construction that the set of countable ordinals $\gamma$ such that there is some $\mathfrak{C}$ such that $\mathfrak{C} \cdot \gamma'$ is wqo for every $\gamma' < \gamma$ but is not wqo for $\gamma' = \gamma$ is uncountable. But their objects are not relational structures.

**4.2. Well-quasi-ordering and finiteness of the kernel of a relational structure.** The fact that the age of a relational structure $R$ is wqo does not imply that $R$ has a finite kernel – an example is an infinite path with a loop at the initial element of the path. With labelling, the situation is different. We have for an example Corollary 4.5 below (Corollaire p.6 in “Caractérisation combinatoire et topologique des âges les plus simples” [149]). For the reader’s convenience, we give a proof. It uses the characterization of the kernel recorded in Lemma 3.32.

**Proposition 4.4.** Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure made of finitely many relations. If the set $\text{Age}(R)_{[1^{-}]} := \{(S, a) : S \in \text{Age}(R), a \in V(S)\}$ is a finite union of ideals, then $\text{ker}(R)$ is finite.

**Proof.** Suppose that $\text{ker}(R)$ is infinite. We build a sequence $(R_{\uparrow A_n}, a_n)$ of elements of $\text{Age}(R)_{[1^{-}]}$ such that no two members of the sequence have a common extension belonging to $\text{Age}(R)_{[1^{-}]}$. By construction, these members form an infinite antichain of $\text{Age}(R)_{[1^{-}]}$, moreover if $\text{Age}(R)_{[1^{-}]}$ is an union of a family of ideals, no pair of distinct members of this sequence can be contained in one of these ideals. Hence this family of ideals must be infinite. To define the sequence, suppose $(A_n, a_n)$ be defined for $n < m$, pick $a_m \in V \setminus \bigcup_{n<m} A_n$, select $A$ given by Lemma 3.32 and set $A_m := A \cup \bigcup_{n<m} A_n$. $\square$

According to Theorem 3.2 every wqo poset is a finite union of ideals, hence we get:

**Corollary 4.5.** If the age of $R$ is $1^{-}$-wqo then $\text{ker}(R)$ is finite.

**Proposition 4.6.** Let $R := (V, (\rho_i)_{i \in I})$ be a relational structure made of finitely many binary relations and $\mathfrak{A} := \text{Age}(R)$. If every proper subage of $\mathfrak{A}$ is hereditarily wqo then $\text{ker}(R)$ is finite.

**Proof.** If $\text{ker}(R) = \emptyset$, there is nothing to prove. Otherwise, pick $a \in \text{ker}(R)$. Define $S := R_{-a}U_1 \dots U_k$ where the $U_i$'s are unary relations on $V \setminus \{a\}$ such that the local isomorphisms of $S$ extend by the identity on $a$ to local isomorphisms of $R$. The structure $S$ is hereditarily wqo and in particular $1^{-}$-wqo, hence by Corollary 4.5 its kernel $\text{ker}(S)$ is finite. Since $\text{ker}(R) = \{a\} \cup \text{ker}(S)$, $\text{ker}(R)$ is finite. $\square$

We do not know if the conclusion holds for relational structures which are not necessarily binary. That is:

**Problem 10.** Is $\text{ker}(R)$ finite whenever $R$ is made of finitely many relations and every proper subage of $\text{Age}(R)$ is hereditarily wqo?

A special instance of this problem is when $R$ is made of finitely many relations and $\mathbf{H}(\text{Age}(R)) < \omega^2$; indeed in this case every proper subage of $\text{Age}(R)$ is hereditarily wqo (Theorem 5.34). We will see in Subsection 5.4 that in this case the answer to our problem is positive.

**4.3. Bounds of labelled wqo classes.** The notions above allow to prove that some hereditary classes are wqo and have finitely many bounds. For example, we have:

**Lemma 4.7.** If a hereditary class $\mathfrak{C}$ of (undirected loopless) graphs is 1-wqo, it has finitely many bounds.

The proof is easy. In each bound $B$ of $\mathfrak{C}$, pick a vertex $x_B$. Set $D_B := B \uparrow V(B) \setminus \{x_B\}$ and $\bar{D}_B := D_B \cdot X_B$ where $X_B := \{y \in V(B) : y \neq x_B \text{ and } \{x_B, y\} \in E(B)\}$. Clearly, if $B'$ is another bound and $f$ is an embedding of $\bar{D}_B$ into $\bar{D}_{B'}$ then the map $\bar{f}$ extending $f$ by setting $f(x_B) := x_{B'}$ is an embedding of $B$ into $B'$. Hence, if $\mathfrak{B}$ is an infinite set of bounds of $\mathfrak{C}$, the set $\{\bar{D}_B : B \in \mathfrak{B}\}$ is an infinite antichain of $\mathfrak{C}_{[1]}$, which then is not wqo.

If instead of graphs, one considers directed graphs then to get the same conclusion with a similar proof would requires that $\mathfrak{C}_{[2]}$ is wqo (and that $\mathfrak{C}_{[2k]}$ is wqo if $\mathfrak{C}$ is made of binary structures each consisting of $k$ binary relations). For directed graphs or multigraphs, one can do better:
**Lemma 4.8.** Let $\mathfrak{C}$ be a hereditary class of binary structures with a given finite arity. If the class $\mathfrak{C}_{[1,1^-]}$ of $R \cdot U \cdot a$, where $R \in \mathfrak{C}$, $U$ is unary and $a$ is a constant, is wqo then the cardinality of bounds of $\mathfrak{C}$ is bounded.

**Proof.** We suppose that the cardinality of bounds of $\mathfrak{C}$ is unbounded and we get a contradiction. Since $\mathfrak{C}$ is wqo this is a finite union of ages (Corollary 3.11). Since the cardinality of bounds of $\mathfrak{C}$ is unbounded, then the cardinality of bounds of some age $\mathfrak{A}$ included into $\mathfrak{C}$ is also unbounded. Choose $\mathfrak{A}$ minimal with respect to set inclusion. It follows that every member of $\mathfrak{A}$ embeds into some members of $\text{Forb}(\mathfrak{A})$ of arbitrarily large finite cardinality. Let $B \in \text{Forb}(\mathfrak{A})$. Let $b \in V(B)$. Let $E_b(B)$ be the set of $S \in \mathfrak{A}$ with the same base as $B$ that coincide with $B$ on $V(B) \setminus \{b\}$. We claim that $E_b(B)$ is nonempty. Indeed, $B_{\upharpoonright V(B) \setminus \{b\}}$ embeds into members of $\text{Forb}(\mathfrak{A})$ of arbitrarily large finite cardinality. For each $S \in E_b(B)$ and $x \in V(S)$ set $\varphi_B(x) := (B(b,x), B(x,b))$ and $\varphi_S(x) := (S(b,x), S(x,b))$ and set

$$ \text{Good}(S) := \{x \in V(S) : \varphi_B(x) = \varphi_S(x)\}. $$

Choose $S$ such that the cardinality of $\text{Good}(S)$ is maximum and set $S_B := S \cdot \text{Good}(S) \cdot b$. Since $\mathfrak{A}_{[1,1^-]}$ is wqo, we may extract a strictly increasing sequence

$$ S_{B_n} := S_n \cdot \text{Good}(S_n) \cdot b_n \text{ of the set of } S_B \text{ for } B \in \text{Forb}(\mathfrak{A}). $$

For each $n$, let $f_n$ be an embedding of $S_{B_n}$ into $S_{B_{n+1}}$; for $m > n$, let $g_{n,m} := f_{m-1} \circ \cdots \circ f_n$ and $x_0 \in V(S_0) \setminus \text{Good}(S_0)$ and $x_{n+1} := f_n(x_n)$. We claim that there are $n < m$ such that $\varphi_{B_n}(x_0) = \varphi_{B_m}(x_m)$. Indeed, we may suppose that $|B_n| \ge 3$, hence the restriction of $B_n$ to $\{b_n, x_n\}$ belongs to $\mathfrak{A}$ which is wqo and thus there are only finitely many such restrictions. Since $|V(B_n)| < |V(B_m)|$, we may pick $u \in V(B_m) \setminus \text{Range}(g_{n,m})$. Since $B_m \in \text{Forb}(\mathfrak{A})$, $B_m \upharpoonright (V(B_m) \setminus \{u\}) \in \mathfrak{A}$, hence $B_m \upharpoonright \text{Range}(g_{n,m}) \in \mathfrak{A}$. Let $S'_n$ be its inverse image by $g_{n,m}$. Then $S'_n \in E_{b_n}(B_n)$. Furthermore $\text{Good}(S'_n) \supset \text{Good}(S_n) \cup \{x_n\}$. This contradicts the maximality of $\text{Good}(S_n)$. $\square$

If we deal with undirected loopless graphs, the hypothesis in Lemma 4.7 is weaker than in Lemma 4.8.

**Problem 11.** Find a common root to Lemmata 4.7 and 4.8.

The proof of Lemma 4.8 can be extended to non-binary relational structures.

**Theorem 4.9.** Let $\mathfrak{C}$ be a hereditary class of relational structures with arity bounded by $m$. If the class $\mathfrak{C}_{[m-1,m-1^-]}$ of $R \cdot U_1 \cdots U_{m-1} \cdot a_1 \cdots a_{m-1}$, where $R \in \mathfrak{C}$, $U_1, \dots, U_{m-1}$ are unary and $a_1, \dots, a_{m-1}$ are $m-1$ constants, is wqo then the cardinality of bounds of $\mathfrak{C}$ is bounded.

This result (with the stronger assumption that the labelling uses $m$ constants instead of $m-1$) is in [147]; the technique used here in the proof of Lemma 4.8 allows us to reduce the number of constants by 1. As a consequence we have:

**Theorem 4.10.** Provided that the signature $\mu$ is bounded, the cardinality of bounds of every hereditary and hereditarily wqo subclass of $\Omega_\mu$ is bounded.

With Theorem 4.10 and Lemma 3.12 we obtain:

**Corollary 4.11.** A hereditary class $\mathfrak{C}$ of finite structures with a finite signature is wqo whenever every age properly included in $\mathfrak{C}$ is hereditarily wqo.

With the notion of hereditarily wqo classes, we obtain the following generalization of Lemma 3.21.

**Proposition 4.12.** Let $\mathfrak{C}$ be a class of binary structures of arity $\mu$ and $\mathfrak{R}$ be a class of finite binary structures of arity $\mu$. If $\mathfrak{C}$ is wqo and $\mathfrak{R}$ is hereditarily wqo then $\tilde{\mathfrak{S}}_{\mathfrak{R}}\mathfrak{C}$ is wqo. If in addition $\mathfrak{C}$ is hereditarily wqo then $\tilde{\mathfrak{S}}_{\mathfrak{R}}\mathfrak{C}$ is hereditarily wqo.

**Proof.** The proof is an application of the minimal bad sequence technique of Nash-Williams. We consider finite ordered trees which are ramified in the sense that every non terminal vertex is the meet of two incomparable vertices. If $T$ is a finite ordered tree and $x \in T$, we denote by $T_{\uparrow x}$ the restriction to $\uparrow x$ of the tree $T$; if $x < y$, we set $T(x, y)$ for the unique successor of $x$ below $y$. We consider a class $\mathfrak{T}$ of labelled ramified
trees defined as follows. If $x$ is a terminal vertex of $T \in \mathcal{T}$, it is labelled by some member $C_x$ of $\mathcal{C}$, if $x$ is non terminal, the set $T(x)$ of immediate successors of $x$ in $T$ is the domain of some $R_x \in \mathfrak{R}$. If $T$ and $T'$ are two such trees, we set $T \leq T'$ if there is a 1-1 meet-preserving map $f$ from $T$ to $T'$ such that the following holds:

(a) for every vertex $x$ of $T$, $f(x)$ is a terminal vertex of $T'$ and $C_x$ is embeddable into $C'_{f(x)}$ if $x$ is a terminal vertex of $T$;

(b) for every non terminal vertex $x$ the map $y \mapsto T'(x, f(y))$ from $T(x)$ to $T'(x)$ is an embedding of $R_x$ into $R'_{f(x)}$.

We set $T < T'$ if $T \leq T'_{\uparrow x}$ for some successor $x$ of the root of $T'$. To each $T \in \mathcal{T}$ we associate $F(T) \in \tilde{\bigoplus}_{\mathfrak{R}} \mathcal{C}$ by the following process defined inductively: if $T$ has just one vertex, $F(T)$ is the label of that vertex, if $T$ has more that one vertex, and $r$ is the root of $T$, then $F(T)$ is the lexicographical sum $\sum_{x \in R_r} F(T_{\uparrow x})$ where for each $x \in T(r)$, $T_{\uparrow x}$ is the restriction to $\uparrow x$ of the labelled tree $T$. One easily checks that the map $F$ is order preserving and surjective, hence the image is wqo provided that $\mathcal{T}$ is wqo. If $\mathcal{T}$ is not wqo then it contains a bad sequence, and since $\leq$ is well-founded it contains a bad sequence $T_0, \dots, T_n, \dots$ which is minimal in the sense that if $T'_0, \dots, T'_n, \dots$ is a sequence which coincides up to $T_n$ and $T'_{n+1} \leq T_n$ then this sequence is not bad. From this it follows that the set $\mathcal{T}'$ of $T'$ such that $T' < T_n$ for some $n$ is wqo. Since $\mathcal{C}$ is wqo, only finitely many $T_n$ are reduced to their root. Let $n$ such that $T_n$ has more than one vertex. Let $r_n$ be the root of $T_n$ and $R_{r_n} \in \mathfrak{R}$ on the set of successors $x$ of $r_n$. Labelling each successor $x$ by the labelled tree $T_{n\uparrow x}$ yields the labelled relational structure $\overline{R}_{r_n} := (R_{r_n}, (T_{n,\uparrow x})_{x \in T_n(r_n)})$. Since $\mathfrak{R}$ is hereditarily wqo and $\mathcal{T}'$ is wqo, the collection of these labelled structures is wqo In particular there are $n < m$ such that $\overline{R}_{r_n} \leq \overline{R}_{r_m}$. But, as this can be easily checked, this implies $T_n \leq T_m$, a contradiction. Suppose now that $\mathcal{C}$ is hereditarily wqo. Let $P$ be a wqo. In order to prove that $\tilde{\bigoplus}_{\mathfrak{R}} \mathcal{C} \cdot P$ is wqo, it suffices to replace $\mathcal{C}$ by $\mathcal{C}z \cdot P$ in the above proof. $\square$

If $R$ is a finite binary relational structure then the modules of $R$ and of $R \cdot U_1 \cdot \dots \cdot U_k$, where $U_1, \dots, U_k$ are unary relations, are the same. (Note that this does not hold with the notion of module of Fraïssé.) Hence, Theorem 3.23 admits the following refinement: *A class $\mathcal{C}$ of finite binary structures with a finite signature which contains only finitely many prime members (up to isomorphy) is very well-quasi-ordered.*

Moreover, from Proposition 4.12, we obtain the following result.

**Theorem 4.13.** *A hereditary class $\mathcal{C}$ of finite binary structures with a finite signature which contains only finitely many prime members (up to isomorphy) is hereditarily well-quasi-ordered.*

**4.4. Preserving wqo by adding a linear order.** If the wqo character of some classes of structures can be preserved by adding unary predicates, there is no chance it will be preserved by adding binary predicates. An obvious reason is that contrarily to unary relations, the classes of binary relations are not necessarily wqo. Even if the binary relations that we add happen to form a wqo class, the resulting structures do not form a wqo in general. For example, the class of bichains is not wqo under embeddability [188]. Still, I guess that it could be interesting to look at classes of structures whose wqo character is preserved by adding appropriately chosen linear orders. In that respect, We will mention the fact that the automorphism group of a countable homogeneous ordered structure is extremely amenable if and only if the structure has the Ramsey property [104].

**Problems 12.**

(1) Let $\mathcal{C}$ be a wqo hereditary class of finite structures. Is it true that for every $S \in \mathcal{C}$ there is some linear order $L_S$ on $V(S)$, the domain of $S$, such that the class of $S \cdot L_S$ is wqo?

(2) If an age $\mathfrak{A}$ is wqo, is it true that $\text{Age}(R \cdot L)$ is wqo for some $R$ such that $\text{Age}(R) = \mathfrak{A}$ and a linear order $L$ on $V(R)$?

A positive answer to the second problem yields a positive answer to the first. Indeed, if $\mathcal{C}$ is wqo then $\mathcal{C}$ is a finite union of wqo ages $\mathfrak{A}_i$. Each $\mathfrak{A}_i$ is the age of some relational structure $R_i$. If (2) has a positive answer, there is some linear order $L_i$ such that $\text{Age}(R_i \cdot L_i)$ is wqo. Then, $\mathcal{C}' := \bigcup_{i=1,n} \text{Age}(R_i \cdot L_i)$ is wqo. If for each $S \in \mathcal{C}$ one selects some $L_S$ such that $S \cdot L_S \in \mathcal{C}'$, the resulting class being included into $\mathcal{C}'$ is wqo.
Note that if (1) has a positive answer, then we may associate to every member $S \in \mathfrak{A}$ some linear order $L_S$ such that the class $\mathfrak{A}'$ of $S \cdot L_S$ is wqo. We do not know if the hereditary closure of $\mathfrak{A}'$ contains a wqo hereditary subclass whose first projection is $\mathfrak{A}$. (This would hold were $\mathfrak{A}$ a hereditarily wqo.)

Also, observe that if the second problem has a positive answer, then for every $R$ with $\text{Age}(R) = \mathfrak{A}$ there is some linear order $L$ on $V(R)$ such that $\text{Age}(R \cdot L)$ is wqo. Indeed, let $R_0$ and $L_0$ such that $\text{Age}(R_0) = \mathfrak{A}$ and $\mathfrak{A}' := \text{Age}(R_0 \cdot L_0)$ is wqo. Let $\mathcal{P}$ be the free operator transforming each concatenat $R' \cdot L'$ to $R'$. By hypothesis, $\mathfrak{A}$ is the image of $\mathfrak{A}'$ hence, via colored compactness of first order logic, for every $R$ with $\text{Age}(R) = \mathfrak{A}$ there is some $L$ such that $\text{Age}(R \cdot L) \subseteq \mathfrak{A}'$. Hence, $\text{Age}(R \cdot L)$ is wqo.

Ordered structures have peculiar properties. For instance, following similar steps as in the proof of Lemma 4.8, it can be shown that:

**Lemma 4.14.** If the age of an ordered directed multigraph $G$ is $2^-$-wqo then it has finitely many bounds. Consequently, there are only countably many hereditary classes of ordered graphs which are $2^-$-wqo.

**Problem 13.** How many hereditary classes of finite graphs are $2^-$-wqo?, $1^-$-wqo? How many hereditary classes of finite ordered graphs are $1^-$-wqo?

**4.5. Uniform prehomogeneity.** A relational structure $R$ is uniformly prehomogeneous if for every finite set $F$ of the domain $V$ of $R$ there is a finite superset $F'$ of $F$ whose cardinality is bounded by some function $\theta$ of the cardinality of $F$ such that every local isomorphism of $R$ defined on $F$ extends to an automorphism provided that it extends to $F'$.

This notion extends the notion of homogeneity. It was introduced by Pabion [145] for relational structures with finite signature. For relational structures with possibly infinite signature, a closely related concept was defined in terms of maximal existential types and a necessary and sufficient condition for existence was given in [146]. For our purposes here it suffices to say that the two notions coincide for structures with finite profile.

**Problem 14.** Let $R$ be a uniformly prehomogeneous structure. If $\text{Age}(R)$ is wqo, is it true that $(R, L)$ is uniformly prehomogeneous and $\text{Age}(R, L)$ is wqo for some linear order $L$ on $V(R)$?

It was proved independently in [146] and [181] that:

**Theorem 4.15.** A countable relational structure $R$ such that $\text{Aut}(M)$ is oligomorphic is equimorphic to a countable $R'$ which is uniformly prehomogeneous and furthermore $\text{Aut}(R')$ is oligomorphic.

From the test of existence of uniformly prehomogeneous structures given in [146] one has:

**Theorem 4.16.** If an ideal $\mathfrak{A}$ of finite relational structures is $m^-$-wqo for every nonnegative integer $m$ then there is a uniformly prehomogeneous structure $R$ with $\text{Age}(R) = \mathfrak{A}$.

**Proof.** Here is a sketch of the argument. Fix a nonnegative integer $m$. Let $\mathfrak{A}(m)$ be the collection of $(S, a_1, \dots, a_m)$ where $S \in \mathfrak{A}$ and $a_1, \dots, a_m \in S$. Quasi-ordered by embeddability, this set is wqo. Hence, it is a finite union of ideals. This is the test given in [146] in terms of existential $m$-types for the existence of a uniformly prehomogeneous structure $R$ with age $\mathfrak{A}$. $\square$

**Problem 15.** If $R$ is uniformly prehomogeneous and $\text{Age}(R)$ wqo, is it true that $\text{Age}(R)$ is $m^-$-wqo for every nonnegative integer $m$?

## 5. HEREDITARY CLASSES OF SMALL LENGTH AND AGES OF SMALL HEIGHT

This section is about hereditary classes of small length, that is, classes of height less than $\omega^2$. These classes extend classes of monomorphic, chainable, almost monomorphic and almost chainable structures. These former classes appeared first in the thesis of Fraïssé [72]. They play a crucial role in the proof that the profile is non-decreasing (Theorem 6.1). We give an other illustration with the characterization by Cameron of monomorphic permutation groups. A careful examination of the notions of almost monomorphy and almost chainability allows extension of these properties to ages of almost multichainable structures. These
ages are wqo, in fact hereditarily wqo, hence have finitely many bounds (Theorem 5.34 and Theorem 5.39), and have height less than $\omega^\omega$ (Theorem 5.42). The central result of this section is that ages of height less than $\omega^2$ are ages of almost multichainable structures (Theorem 5.35). This allows us to characterize the members of the Cantor-Bendixson derivatives of finite rank of the space of subages of a given age as we did in Subsection 3.6 and also to prove the existence of jumps in the profile as presented in Section 6.

**5.1. Height at most $\omega$. Monomorphy and chainability.** If $P$ is a finite poset, $o(P)$ and $h(P, I(P))$ are equal to the cardinality of $P$. If $P$ is an infinite poset and every initial segment is finite then $P$ is countable and $o(P) = h(P, I(P)) = \omega$. Such a poset $P$ is *Jónsson*.

**5.1.1. Jónsson posets.**

**Definition 5.1.** A poset $P$ is a *Jónsson* poset if it is infinite and every proper initial segment has a strictly smaller cardinality than $P$.

Jónsson posets were introduced by Oman and Kearnes [103]. Countable Jónsson posets were studied and described in [149, 161, 5]. We recall Proposition 3.1 in [5].

**Theorem 5.2.** Let $P$ be a countable poset. The following statements are equivalent.

(i) $P$ is Jónsson;

(ii) $P$ is wqo and $o(P) = \omega$;

(iii) $P$ is level-finite, has height $\omega$, and for each $n < \omega$, there is $m < \omega$ such that each element of height at most $n$ is below every element of height at least $m$.

Jónsson posets are in fact better-quasi-ordered (bqo) (see Subsection 3.4 for the definition). This fact, observed in [149], has been significantly extended [36].

We state and prove Lemma 4 of [143]:

**Lemma 5.3.** Every infinite well-founded poset $P$ which is level-finite contains an initial segment which is Jónsson.

**Proof.** Observe that the intersection of every descending sequence $(I_\alpha)_{\alpha \in \kappa}$ of infinite initial segments $I_\alpha$ of $P$ is infinite. Indeed, let $I := \bigcap_{\alpha \in \kappa} I_\alpha$. Fix $n < \omega$ and let $P_n$ be the $n$-level of $P$. We have $I \cap P_n = \bigcap_{\alpha \in \kappa} (I_\alpha \cap P_n)$. Since for each $\alpha \in \kappa$, $I_\alpha$ is infinite, $I_\alpha \cap P_n$ is nonempty. Since $(I_\alpha)_{\alpha \in \kappa}$ is descending, $(I_\alpha \cap P_n)_{\alpha \in \kappa}$ is descending too; since $P_n$ is finite, it is in fact stationary, hence the intersection is nonempty. With this observation, an application of Zorn's lemma yields an infinite initial segment which is minimal w.r.t. set inclusion. $\square$

**5.1.2. Jónsson hereditary classes.** Hereditary classes of relational structures which are Jónsson are particularly simple. They were characterized by Fraïssé in terms of monomorphy (see Chapter III in [72], Exercises 3, 4, 8, pp. 109-113 in [75], 9.5, p. 53, 9.6, p. 258 in [76] and [155].) The results obtained by Fraïssé and Frasnay [81] in this area form one of the most important chapters of the theory of relations.

We recall some basic facts that can be found in [155]. We focus on monomorphic classes since the properties of classes of higher complexity, such as those of almost chainable or almost multichainable structures, are extensions of monomorphic classes. Given a relational structure $R$ and a nonnegative integer $p$, $R$ is said to be *p-monomorphic* if its restrictions to finite sets of cardinality $p$ are isomorphic. The structure $R$ is *monomorphic* if it is *p*-monomorphic for every integer $p$.

There are eight types of monomorphic directed graphs, four made of reflexive directed graphs, four made of irreflexive graphs. For the reflexive ones, there are the chains, the reflexive cliques, the antichains, plus the 3-element oriented reflexive cycle. Whereas, for the irreflexive ones, there are the acyclic (oriented) graphs, the cliques, the independent sets, and the 3-element oriented irreflexive cycle. Other examples of monomorphic relational structures can be found in [110].

Fraïssé gave a characterization of infinite monomorphic relational structures by means of his notion of chainability: a relational structure $R := (V, (\rho_i)_{i \in I})$ is *chainable* if there is a linear ordering $\leq$ on $V$ such that $L := (V, \leq)$ interprets $R$ freely, that is, every local isomorphism of $L := (V, \leq)$ is a local isomorphism of $R$.
Such a linear order $\le$ is said to *chain* $R$. Chains are monomorphic, hence chainable relational structures are also monomorphic. The converse does not hold (as shown by a 3-element cycle). Fraïssé proved that it holds if the structure is infinite.

**Theorem 5.4.** *An infinite relational structure is monomorphic if and only if it is chainable.*

Fraïssé's proof, given for relational structures of finite signature, was based on Ramsey's theorem [174] and the compactness theorem of first order logic (in a weaker form, given by Fraïssé's "coherence lemma"). The extension to arbitrary signature requires an other application of the compactness theorem. Since Ramsey's theorem and the compactness theorem of first order logic are among the most important tools of the theory of relations, we give the proof idea (for a detailed proof, see Section IV, p. 295 of [155]).

With Ramsey's theorem, Fraïssé proved the following:

**Lemma 5.5.** *Every infinite relational structure with a finite signature has an infinite chainable restriction.*

**Proof.** Let $R$ be a relational structure and $V$ be its domain. We suppose $V$ infinite. Let $A$ be a countably infinite subset of $V$. Let $m$ be the maximum of the signature of $R$ and let $[A]^m$ be the set of $m$-element subsets of $A$. Put a linear order $\le$ of type $\omega$ on $A$. Define an equivalence relation on $[A]^m$: say that two $m$-element subsets $X, X' \in [A]^m$ are equivalent if the unique order isomorphism of $(X, \le_X)$ on $(X', \le_{X'})$ is a local isomorphism of $R$. Observe that the number of equivalence classes is finite. Apply Ramsey's theorem and get an infinite subset $A' \subseteq A$ such that all elements of $[A']^m$ are equivalent. We may suppose that all $m$-elements subsets of $A'$ are equivalent for all $m' \le m$ (if this is not the case, replace $A'$ by $A'$ minus its first $m-1$-elements). It follows that for $V' := A'$, the restriction $R_{\upharpoonright V'}$ is chainable. $\square$

From Lemma 5.5, Fraïssé deduced that if $R := (V, (\rho_i)_{i \in I})$ is an infinite monomorphic relational structure then all its finite restrictions are chainable. Indeed, let $I'$ be a finite subset of $I$. Then, the reduct $R^{\upharpoonright I'} := (V, (\rho_i)_{i \in I'})$ is monomorphic. From Lemma 5.5, it contains an infinite induced structure $(R^{\upharpoonright I'})'$ which is chainable. Since $R^{\upharpoonright I'}$ is monomorphic, each finite substructure of $R^{\upharpoonright I'}$ is isomorphic to some finite substructure of $(R^{\upharpoonright I'})'$ hence is chainable. If $X$ is a finite subset of $V$, the number of linear orders on $X$ being finite, there is a linear order $\le_X$ which chains all the finite reducts of $R_{\upharpoonright X}$, thus $R_{\upharpoonright X}$ is chainable as claimed. The application of the compactness theorem of first order logic is as follows. For each finite subset $X$ of $V$, let $\mathcal{U}(X)$ be the set of binary relation $\rho$ on $V$ such that $\rho_{\upharpoonright X}$ is a linear order chaining $R_{\upharpoonright X}$. Each $\mathcal{U}(X)$ is a nonempty closed subset of the space $\wp(V \times V)$ made of binary relations on $V$. Since $\mathcal{U}(X) \cap \mathcal{U}(X') \supset \mathcal{U}(X \cup X')$ for every finite $X, X' \subseteq V$, the intersection of finitely many of these closed sets is nonempty. Since $\wp(V \times V)$ is compact, the intersection of all these closed sets is nonempty. Every member of this intersection is a linear order which chains $R$. With that fact, the proof of Theorem 5.4 is complete. $\square$

In his thesis, Frasnay 1965 ([81]) obtained the following result:

**Theorem 5.6.** *For every integer $m$ there exists an integer $d$ such that every $d$-monomorphic relational structure $R$ whose maximum of the signature is at most $m$ and domain infinite or sufficiently large is chainable.*

The least integer $d$ in the statement of Theorem 5.6 above is the *monomorphy threshold*, $d_m$. An upper bound of $d_m$ is in Frasnay's thesis. In 1990, Frasnay [83], using a result of Hodges et al [96] and his theory of permuted chains, obtained the exact value: $d_1 = 1$, $d_2 = 3$, $d_m = 2m - 2$ for $m \ge 3$. For a detailed exposition see [76] Chapter 13, notably p. 378.

Frasnay deduced the following consequence (cf. 13.1.2, Corollaire, p. 519 in [81]).

**Theorem 5.7.** *The age of a chainable structure with a finite signature has finitely many bounds.*

If we are only concerned with the existence of $d_m$ and not its numerical values, we can derive it from Theorem 5.7. Indeed, with Ramsey's theorem, for every integer $p$, all the $p$-element restrictions of a $p$-monomorphic member $S$ of $\Omega_\mu$ are chainable provided that the cardinality of $S$ is large enough. Hence, if $p$ is the maximum of the cardinality of the bounds of the class $Chain_\mu$ of finite chainable structures of