## ON BETTER-QUASI-ORDERING CLASSES OF PARTIAL ORDERS

## GREGORY MCKAY

Abstract. We provide a method of constructing better-quasi-orders by generalising a technique for constructing operator algebras that was developed by Pouzet. We then generalise the notion of σ -scattered to partial orders, and use our method to prove that the class of σ -scattered partial orders is better-quasi-ordered under embeddability. This generalises theorems of Laver, Corominas and Thomass´ e regarding σ -scattered linear orders and trees, countable forests and N -free partial orders respectively. In particular, a class of countable partial orders is better-quasi-ordered whenever the class of indecomposable subsets of its members satisfies a natural strengthening of better-quasi-order.

## Contents

| 1.               | Introduction                                        | 2   |
|------------------|-----------------------------------------------------|-----|
| 2.               | Preliminaries                                       | 3   |
| 2.1.             | Basic bqo theory                                    | 3   |
| 2.2.             | Concrete categories                                 | 5   |
| 2.3.             | Partial orders                                      | 7   |
| 3.               | Operator construction                               | 9   |
| 3.1.             | Iterating over L                                    | 10  |
| 3.2.             | Limits                                              | 13  |
| 4.               | Decomposition trees                                 | 17  |
| 4.1.             | Scattered and structured L -trees                   | 17  |
| 4.2.             | Encoding with structured L -trees                   | 20  |
| 5.               | The construction is bqo                             | 23  |
| 5.1.             | The non-limit case                                  | 23  |
| 5.2.             | The limit case                                      | 25  |
| 6.               | Constructing structured L -trees                    | 26  |
| 6.1.             | The constructed trees are σ -scattered              | 28  |
| 6.2.             | The class T L P of structured trees is well-behaved | 29  |
| 7.               | Constructing partial orders                         | 32  |
| 7.1.             | Intervals and indecomposable partial orders         | 32  |
| 7.2.             | Generalised σ -scattered partial orders             | 33  |
| 7.3.             | Pathological decomposition trees                    | 35  |
| 7.4.             | Pathological partial orders                         | 39  |
| 7.5.             | Characterising the construction                     | 40  |
| 8.               | Corollaries and conclusions                         | 42  |
|                  |                                                     | 44  |
| Acknowledgements | Acknowledgements                                    |     |
| References       | References                                          | 44  |

2010 Mathematics Subject Classification. Primary 06A07; Secondary 03E05, 06A06, 05C05.

Key words and phrases. Better-quasi-order, well-quasi-order, scattered, structured trees, interval.

This work was carried out as part of the author's Ph.D. thesis at the University of East Anglia in the UK.

## 1. Introduction

Some of the most striking theorems in better-quasi-order (bqo) theory are that certain classes of partial orders, often with colourings, are bqo under embeddability. Indeed, the notion of bqo was first used by Nash-Williams to prove that the class R of rooted trees of height at most ω has no infinite descending chains or infinite antichains under the embeddability quasi-order [9].

Another contribution from Nash-Williams comes in [10]. He proved that if Q is bqo, then the class ˜ Q of transfinite sequences of members of Q is bqo (see [11]). This theorem can be viewed as an embeddability result on a class of coloured partial orders; since it is equivalent to saying that the ordinals preserve bqo (which is to say that if Q is bqo, then the class of ordinals coloured by Q is also bqo under a natural embeddability ordering; see Definition 2.15). In fact Nash-Williams proved a technical strengthening of this statement, equivalent to saying that the ordinals are well-behaved (see Definition 2.16). This is an important generalisation of bqo that will be crucial in this paper, because it is much more useful than bqo or even preserving bqo when constructing large bqo classes.

Perhaps the most well known result of this kind comes from Laver, who proved that the class M of σ -scattered linear orders preserves bqo, a positive result for a generalisation of Fra¨ ıss´'s e conjecture [12]. A few years after his paper on σ -scattered linear orders, Laver also showed that the class T of σ -scattered trees preserves bqo [13]. Initially we notice that there should be some connection between the theorems of σ -scattered linear orders and σ -scattered trees. In each, we first take all partial orders of some particular type (linear orders, trees) that do not embed some particular order (namely Q and 2 &lt;ω ). In both cases, the class of countable unions of these objects turn out to preserve bqo.

We prove a general theorem of this type (Theorem 7.37) which states that given well-behaved classes L and P of linear orders and partial orders respectively, the class of 'generalised σ -scattered partial orders' M L P will be well-behaved (see Definition 7.10). We define our general 'scattered' partial orders to be those orders X such that:

- · Every indecomposable subset of X is contained in P . (See Definition 7.3.)
- · Every chain of intervals of X under ⊇ has order type in L . (See definitions 2.31 and 7.2.)
- · No 'pathological' order 2 &lt;ω , -2 &lt;ω or 2 &lt;ω ⊥ embeds into X . (See definitions 4.1 and 7.9).

Our class M L P is then the class of countable increasing unions or limits of such X .

Applying this theorem with classes known to be well-behaved yields generalisations of many other known results in this area. For example, Corominas showed that the class of countable C -trees 1 preserves bqo [2] (see Definition 2.33) and Thomass´ showed that the class of countable e N -free partial orders preserves bqo [1] (see Definition 2.27). We summarise known results as applications of Theorem 7.37 in the following table. 2 In each case Theorem 7.37 tells us that the given class is well-behaved. 3

| Class               | Description                          | P            | L         | Limits   |
|---------------------|--------------------------------------|--------------|-----------|----------|
| N                   | Finite numbers under injective maps  | 1, A 2       | 1         | ✗        |
| S                   | Scattered linear orders [12]         | 1, C 2       | On ∪ On ∗ | ✗        |
| M                   | σ -scattered linear orders [12]      | 1, C 2       | On ∪ On ∗ | ✓        |
| U On                | Scattered trees [13]                 | 1, C 2 , A 2 | On        | ✗        |
| T On                | σ -scattered trees [13]              | 1, C 2 , A 2 | On        | ✓        |
| T C                 | Countable L -trees [2]               | 1, C 2 , A 2 | C         | ✓        |
| C { 1 , A 2 , C 2 } | Countable N -free partial orders [1] | 1, C 2 , A 2 | C         | ✓        |

1 Here C is the class of countable linear orders.

2 Here A 2 and C 2 are the antichain and chain of size 2 respectively.

3 In the cases of U On , T On and T C the constructed M L P is actually a larger class of partial orders.

Applying this theorem with the largest known well-behaved classes L and P gives that some very large classes of partial orders are well-behaved (Theorem 8.7). For example, let P be the set of indecomposable partial orders of cardinality less than some n ∈ ω , and L = M . Then for n &gt; 2 the well-behaved class M L P contains the σ -scattered linear orders, σ -scattered M -trees, countable N -free partial orders, and generalisations of such objects.

Crucial to the ideas in this paper are those of constructing objects with so called 'structured trees'. Put simply, these are trees with some extra structure (usually a partial order) given to the set of successors of each element. Embeddings between structured trees are then required to induce embeddings of this extra structure.

Theorems on structured trees also appear throughout the literature on bqo theory (cf. [1, 2, 3, 5, 6, 8]). The rationale for their usefulness is explained by Pouzet in [5]. His method is to take a 'simple' class of objects (e.g. partial orders) and a bqo class of multivariate functions sending a list of objects to a new object (so called 'operator algebras'). Closing the class under these functions then yields a new class, which one can prove to be bqo. The crucial step is to show that this construction can be encoded as a structured tree, contained inside a class which is known to preserve bqo. Pouzet's method however was limited in that the structured trees that he used were only 'chain-finite' (i.e. those trees for which every chain is finite).

Since then, larger classes of structured trees have been shown to be preserve bqo. In particular, using a modification of the Minimal Bad Array Lemma (see [11]), Kˇ r´ ıˇ managed to prove that z if Q is well-behaved then R Q (the class of Q -structured trees of R , see Definition 4.7) is wellbehaved [3]. We give a generalisation of Pouzet's method, that incorporates these larger classes of structured trees. This allows for iterating functions over a general linear order and for taking countable limits. Using this coding, these more complex classes can be shown to be bqo (even well-behaved).

So we aim to show that some large classes of partial orders are well-behaved, the main theorem being Theorem 7.37 and its main application Theorem 8.7. The general method of the proof will be as follows. In Section 3 we define an operator algebra construction, similar to ideas explained in [5] but with our two generalisations. We also give an example of how to construct partial orders. In Section 4 we encode this construction in terms of structured trees. In Section 5 we prove that such a construction, under the correct conditions, will be bqo. In Section 6, using the structured tree theorem of Kˇ r´ ıˇ from [3] (Theorem 4.11), in conjunction with our construction z theorem, we construct a more general well-behaved class of ' σ -scattered structured L -trees'. This serves to supercharge the construction theorem. In Section 7 we prove a generalisation of Hausdorff's theorem on scattered order types, which characterises the class of partial orders that we constructed as precisely M L P . This completes the proof of our main theorem, that this class is well-behaved. Finally in Section 8 we explain how this result expands all known bqo results on embeddability of coloured partial orders.

## 2. Preliminaries

## 2.1. Basic bqo theory.

Definition 2.1. If A is an infinite subset of ω , let [ A ] ω = { X ⊆ A | | X | = ℵ } 0 and [ A ] &lt;ω = { X ⊆ A | | X &lt; | ℵ } 0 . We equate X ∈ [ A ] ω with the increasing enumeration of elements of X .

Definition 2.2. · A class Q with a binary relation /lessorequalslant Q on Q is called a quasi-order whenever /lessorequalslant Q is transitive and reflexive.

- · If Q is a quasi-order with /lessorequalslant Q antisymmetric, then we call Q a partial order .

/negationslash

/negationslash

- · For a, b ∈ Q we write a &lt; Q b iff a /lessorequalslant Q b and b /lessorequalslant Q a . We write a ⊥ Q b and call a and b incomparable iff a /lessorequalslant Q b and b /lessorequalslant Q a .

/negationslash

- · We write /lessorequalslant , &lt; and ⊥ in place of /lessorequalslant Q , &lt; Q and ⊥ Q when the context is clear.

4

- · A function f : [ ω ] ω → Q is called a Q -array (or simply an array ) if f is continuous (giving [ ω ] ω the product topology and Q the discrete topology).
- · An array f : [ ω ] ω → Q is called bad if ∀ X ∈ [ ω ] ω we have

$$f ( X ) \, \ll f ( X \, \sum \{ \min X \} ).$$

/negationslash

- · An array f : [ ω ] ω → Q is called perfect if ∀ X ∈ [ ω ] ω we have

$$f ( X ) \leqslant f ( X \, \sum \{ \min X \} ).$$

- · A quasi-order Q is called a better-quasi-order (bqo) if there is no bad Q -array.

Remark 2.3 . We note that we could replace 'continuous' in the definition of a Q -array with 'Borel measurable' and this would make no difference to the definition of bqo (see [11]). We can also consider bad arrays with domain [ A ] ω for some A ∈ [ ω ] ω .

The following is a well-known Ramsey-theoretic result due to Galvin and Prikry.

Theorem 2.4 (Galvin, Prikry [15]) . Given X ∈ [ ω ] ω and a Borel set B in [ X ] ω , there exists A ∈ [ X ] ω such that either [ A ] ω ⊆ B or [ A ] ω ∩ B = ∅ .

Proof. See [15] or [11].

$$\Box$$

Theorem 2.5 (Nash-Williams [9]) . If f is a Q -array, then there is A ∈ [ ω ] ω such that f /harpoonupright [ A ] ω is either bad or perfect.

Proof. Let B = { X ∈ [ ω ] ω | f ( X ) /lessorequalslant f ( X \ { min X } } ) . If B is Borel, then by Theorem 2.4 we will be done. Let S : [ ω ] ω → [ ω ] ω be the function S X ( ) = X \ { min X } and let g = f × ( f ◦ S ). Then g is continuous, since f and S are continuous. We also have that B = g -1 ( /lessorequalslant ), considering the relation /lessorequalslant as a subset of the discrete space Q × Q . Therefore B is open and we are done. /square

Definition 2.6. Given two sets x and y we write x /unionsq y for the disjoint union of x and y . And given a set X of sets, we define ⊔ x ∈ X x as the disjoint union of the sets in X . Definition 2.7. Let Q 0 and Q 1 be quasi-orders, we define new quasi-orders:

- · Q 0 ∪ Q 1 = ( Q 0 /unionsq Q , 1 /lessorequalslant ) where for p, q ∈ Q 0 ∪ Q 1 , we have p /lessorequalslant q iff both p and q are in the same Q i for i ∈ { 0 1 , } , and p /lessorequalslant Q i q ;
- · Q 0 × Q 1 = {〈 q , q 0 1 〉 | q 0 ∈ Q , q 0 1 ∈ Q 1 } where for 〈 p , p 0 1 〉 , 〈 q 0 , q 1 〉 ∈ Q 0 × Q 1 we have

〈 p , p 0 1 〉 /lessorequalslant 〈 q , q 0 1 〉 iff ( p 0 /lessorequalslant Q 0 q 0 ) ∧ ( p 1 /lessorequalslant Q 1 q 1 ) .

Theorem 2.8. If there is a bad Q 0 ∪ Q 1 -array f then there is A ∈ [ ω ] ω such that f /harpoonupright [ A ] ω is either a bad Q 0 -array, or a bad Q 1 -array.

$$\text{ith } B = f ^ { - 1 } ( Q _ { 0 } ). & & \Box$$

Proof. Apply Theorem 2.4 with B = f ( Q 0

Theorem 2.9 (Nash-Williams [9]) . If there is a bad Q 0 × Q 1 -array f , then there is A ∈ [ ω ] ω and either a bad Q 0 -array, or a bad Q 1 -array g with dom ( g ) = [ A ] ω and such that g X ( ) is either the first or second component of f ( X ) for all X ∈ [ A ] ω .

Proof. Define the Q 0 -array f 0 and the Q 1 -array f 1 so that for every X ∈ [ ω ] ω we have

$$f ( X ) = \langle f _ { 0 } ( X ), f _ { 1 } ( X ) \rangle.$$

Now apply Theorem 2.5 twice to restrict so that f 0 and f 1 are both either bad or perfect. Then either we are done or they are both perfect, which contradicts that f was bad. /square

2.2. Concrete categories. Usually we will be interested in quasi-ordering classes of partial orders under embeddability, however we can keep the results more general with no extra difficulty by considering the notion of a concrete category . The idea is to add a little more meat to the notion of a quasi-order, considering classes of structures quasi-ordered by existence of some kind of embedding. This allows us to generate more complicated orders by colouring the elements of these structures with a quasi-order; enforcing that embeddings must increase values of this colouring. Then we can construct complicated objects from simple objects in a ranked way by iterating this colouring process, and the notion of well-behaved allows us to reduce back down through the ranks. We shall now formalise these notions, similar to the definitions of [3] and [4].

Definition 2.10. A concrete category is a pair O = obj( 〈 O ) , hom( O 〉 ) such that:

- (1) each γ ∈ obj( O ) has an associated underlying set U γ ;
- (2) for each γ, δ ∈ obj( O ) there are sets of embeddings hom O ( γ, δ ) consisting of some functions from U γ to U δ ;
- (3) hom O ( γ, γ ) contains the identity on γ for any γ ∈ O ;
- (4) for any γ, δ, β ∈ O , if f ∈ hom O ( γ, δ ) and g ∈ hom O ( δ, β ) then f ◦ g ∈ hom O ( γ, β );
- (5) hom( O ) = { hom O ( γ, δ ) | γ, δ ∈ obj( O } ) .

Elements of obj( O ) are called objects and elements of O ( γ, δ ) are called O -morphisms or embeddings . To simplify notation we write γ ∈ O for γ ∈ obj( O ) and equate γ with U γ .

Remark 2.11 . Similar definitions to 2.10 appear in [3], [4] and [8]. The first two enjoy a more category theoretic description, and the last is in terms of structures and morphisms.

With the following definition, concrete categories will turn into quasi-ordered sets under embeddability ; (3) and (4) of Definition 2.10 guaranteeing the reflexivity and transitivity properties respectively. This allows us to consider the bqo properties of concrete categories.

Definition 2.12. For γ, δ ∈ O , we say that

/negationslash

$$\gamma \leqslant _ { \mathcal { O } } \delta \text{ iff hom} _ { \mathcal { O } } ( \gamma, \delta ) \neq \emptyset$$

i.e. γ /lessorequalslant O δ iff there is an embedding from γ to δ . If f ∈ hom O ( γ, δ ) then we call f a witnessing embedding of γ /lessorequalslant O δ .

Example 2.13. Let obj( P ) be the class of partial orders. For any two partial orders x, y , let:

- (1) U x = x ,
- (2) hom P ( x, y ) = { ϕ : x → y | ( ∀ a, b ∈ x , a ) /lessorequalslant x b ←→ ϕ a ( ) /lessorequalslant y ϕ b ( ) } ,
- (3) hom( P ) = { hom P ( γ, δ ) | γ, δ ∈ obj( P } ) ,
- (4) P = obj( 〈 P ) , hom( P 〉 ) .

The category P of partial orders with embeddings is then a pragmatic example of a concrete category, and the order /lessorequalslant P is the usual embeddability ordering on the class of partial orders. We keep this example in mind since the majority of concrete categories used in this paper are either subclasses of P or are derived from P . We note that all P -morphisms are injective.

Definition 2.14. Given a quasi-order Q and a concrete category O , we add colours to O , by defining the new concrete category O ( Q ) as follows.

- · The objects of O ( Q ) are pairs 〈 γ, c 〉 for γ ∈ O and c : γ → Q .
- · For 〈 γ, c 〉 ∈ obj( O ( Q )), we let V 〈 γ,c 〉 = V γ , we call c a Q -colouring of γ and for each v ∈ γ , we call c v ( ) the colour of v . To simplify notation we equate 〈 γ, c 〉 with γ , and write c γ = c and γ ∈ O ( Q ).
- · We define morphisms of O ( Q ) from γ to δ to be embeddings ϕ : γ → δ such that

$$\mathbf c _ { \gamma } ( x ) \leqslant _ { Q } \mathbf c _ { \delta } ( \varphi ( x ) )$$

for every x ∈ γ .

Given γ ∈ O ( Q ) and v ∈ γ , we will sometimes write c ( v ), to be read as 'the colour of v ', in place of c γ ( v ) when this is unambiguous.

We are now able to define the bqo preservation properties mentioned in Section 1, allowing us to pass from bad O ( Q )-arrays to bad Q -arrays.

Definition 2.15. Let O be a concrete category, then O preserves bqo iff

$$Q \text{ is a bqo } \longrightarrow \mathcal { O } ( Q ) \text{ is a bqo}.$$

Unfortunately, this simple definition fails to be particularly useful. Given a bad O ( Q )-array, preservation of bqo ensures the existence of a bad Q -array, but no link between these two arrays is guaranteed. The following definition remedies this situation and is extremely important for the rest of the paper.

Definition 2.16. Let O be a concrete category, then O is well-behaved iff for any quasi-order Q and any bad array f : [ ω ] ω →O ( Q , ) there is an M ∈ [ ω ] ω and a bad array

$$g \colon [ M ] ^ { \omega } \rightarrow Q$$

such that for all X ∈ [ M ] ω there is some v ∈ f ( X ) with

$$g ( X ) = \mathbf c _ { f ( X ) } ( v ).$$

We call g a witnessing bad array for f .

Warning: this notion of well-behaved is the same as from [3]; it is different from the definition of well-behaved that appears in [4] which is in fact equivalent to Louveau and Saint-Raymond's notion of reflecting bad arrays [8].

Lemma 2.17. Let P be a finite set of finite partial orders, then P is well-behaved.

Proof. Let Q be an arbitrary quasi-order and let f be a bad P ( Q )-array. Then since P is finite, we can repeatedly apply the Galvin and Prikry Theorem 2.4 to find A ∈ [ ω ] ω such that for each X,Y ∈ [ A ] ω , we have that f ( X ) and f ( Y ) have the same underlying finite partial order P . Then applying Theorem 2.5 at most | P | many times, restrict in turn so that the colours of each point of f ( X ) give either a bad array or a perfect array. They cannot all be perfect otherwise f would also be perfect on some restriction to an infinite set. Therefore one of these arrays is bad, and this is clearly a witnessing array for f . /square

Proposition 2.18. O is well-behaved -→ O preserves bqo -→ O is bqo.

Proof. If O is well-behaved then given a bad O ( Q )-array f , we have a bad Q -array. If Q were bqo this would give a contradiction and hence there is no such bad array f .

Now let 1 = { 0 } be the singleton quasi-order, clearly then 1 is bqo. Thus if O preserves bqo then O (1) is bqo. Clearly O (1) is isomorphic to O , therefore O is also bqo. /square

Remark 2.19 . Note that the converse O is bqo -→ O preserves bqo does not hold. For a counter example let Z be the partial order consisting of points 0 n and 1 n for n ∈ ω ; ordered so that for a, b ∈ Z , we have a /lessorequalslant b iff there is some n ∈ ω such that a ∈ { 0 n , 0 n +1 } and b = 1 n . Then { Z } is clearly bqo but it does not preserve bqo.

It is not known whether or not the other converse holds, i.e. is it the case that

$$\mathcal { O } \text{ preserves } b \alpha \, \longrightarrow \mathcal { O } \text{ is well-behaved?}$$

This is an interesting technical question, which was asked by Thomas in [4].

Figure 1. The partial order N .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-8a8e0926-a489-4c05-85f7-5697693f9508.jpg)

Definition 2.20. We give some notation for the set of all of possible coloured copies of some γ ∈ obj( O ). Given a concrete category O , a quasi-order Q and γ ∈ obj( O ) we define

$$Q ^ { \gamma } = \{ \langle \gamma, c \rangle \ | \ c \colon \gamma \to Q \} \subseteq \mathcal { O } ( Q ).$$

If γ , γ 0 1 ∈ O ( Q ) are such that there is some γ ∈ O with γ , γ 0 1 ∈ Q γ , then we say that γ 0 and γ 1 have the same structure .

## 2.3. Partial orders.

Definition 2.21. We define Card as the class of cardinals, On as the class of ordinals and On ∗ = { α ∗ : α ∈ On , where } α ∗ is a reversed copy of α for every α ∈ On.

Theorem 2.22 (Nash-Williams [10]) . On is

Proof. See [11, 10].

$$\text{). On is well-behaved.}$$

Definition 2.23. If P is a partial order, a chain of P is a subset with no incomparable elements. An antichain of P is a pairwise incomparable subset.

Definition 2.24. We let 1 = { 0 } be the partial order consisting of a single point. For κ ∈ Card we let A κ be the antichain of size κ . For n ∈ ω we let C n be the chain of length n .

We will now define some notation for traversing partial orders.

Definition 2.25. Let P be a partial order and x ∈ P , we define:

$$\downarrow x = \{ y \in P \ | \ y \leqslant x \}, \ \uparrow x = \{ y \in P \ | \ y \geqslant x \},$$

$$\mathbb { J } x = \{ y \in P \ | \ y < x \}, \quad \mathbb { J } x = \{ y \in P \ | \ y > x \}.$$

$$\begin{matrix} x \}, \\ x \}. \end{matrix}$$

For x, y ∈ P , if it exists, we define the meet x ∧ y to be the supremum of ↓ x ∩ ↓ y .

Definition 2.26. Let P be a partial order and P ′ ⊆ P . Then:

- · we call P ′ ↓ -closed if ( ∀ x ∈ P ′ ), ↓ x = { y ∈ P | y /lessorequalslant x } ⊆ P ′ ,
- · we call P ′ ↑ -closed if ( ∀ x ∈ P ′ ), ↑ x = { y ∈ P | y /greaterorequalslant x } ⊆ P ′ .

Definition 2.27. We define the partial order N = { 0 1 2 3 , , , } as follows. For a, b ∈ N we let a &lt; b iff a = 1 and b ∈ { 0 2 , } or a = 3 and b = 2, (see Figure 1). A partial order is called N -free if it contains no subset isomorphic to N .

Definition 2.28.

- · A linear order is a partial order L with no incomparable elements.
- · A linear order L is well-founded if it has no infinite descending sequence.
- · A linear order L is scattered if Q /lessorequalslant L .

/negationslash

- · A linear order L is σ -scattered iff L can be partitioned into countably many scattered linear orders.
- · We denote the class of all linear orders as L .
- · We denote the class of scattered linear orders as S .
- · We denote the class of σ -scattered linear orders as M .
- · We denote the class of countable linear orders as C .

Definition 2.29. Given r, r ′ ∈ L and linear sequences k = 〈 k i : i ∈ r 〉 and k ′ = 〈 k ′ j : j ∈ r ′ 〉 , we denote by /subsetsqequal the initial segment relation, and /squareimage the strict initial segment relation. That is

$$k \sqsubseteq k ^ { \prime } \text{ iff } k = k ^ { \prime } \text{ or } k = \langle k ^ { \prime } _ { i } \colon i < j \rangle \text{ or } k = \langle k ^ { \prime } _ { i } \colon i \leqslant j \rangle \text{ for some } j \in r ^ { \prime }$$

/negationslash and k /squareimage k ′ iff k /subsetsqequal k ′ and k = k . ′ We denote by k /slurabove k ′ the concatenation of k and k ′ . We also define ot( k ) = r , set k ′ \ k = 〈 k ′ i : i ∈ r ′ \ r 〉 , and call k i the i th element of k .

Definition 2.30. Let P be a partial order, and for each p ∈ P , let P p be a partial order. We define the P -sum of the P p denoted by ∑ p ∈ P P p as the set ⊔ p ∈ P P p ordered by letting a /lessorequalslant b iff · there is some p ∈ P such that a, b ∈ P p and a /lessorequalslant P p b , or

- · there are p, q ∈ P such that a ∈ P p , b ∈ P q and p &lt; P q .

Definition 2.31. If L is a class of linear orders, we define L as the least class containing L ∪ ω and closed under L -sums for all L ∈ L .

$$\text{Theorem } 2. 3 2 \ ( \text{Hausdorff } [ 1 4 ] ). \ I f \, \mathbb { L } = \text{On} \cup \text{On} ^ { * } \text{ then } \overline { \mathbb { L } } = \mathcal { S }.$$

Proof.

$$P r o o f. \, & \text{See } [ 14, 11 ].$$

Definition 2.33. A partial order T is called a tree iff ( ∀ t ∈ T ), ↓ t is a well-founded linear order. If L is a class of linear orders, we call T a L -tree iff every chain of T has order type in L and for every x, y ∈ T , we have ↓ x is a linear order and the meet x ∧ y exists.

Note that On-trees are simply trees, and L -trees are the most general 'tree-like' partial orders.

Remark 2.34 . We make explicit the definition of L -tree, in order to clarify because in the literature on bqo theory, the term 'tree' has varied quite significantly. Indeed, the historical time line of bqo results for trees in the authors' terminology is as follows: Nash-Williams proved that the class of all trees is bqo [9], Laver proved that the class of countable increasing unions of trees that do not embed 2 &lt;ω is bqo [13], then Corominas proved that the class of all countable trees is bqo [2]. This is perplexing since each successive breakthrough seems to be a subclass of the previous! However the differences become clear when we use this notation. Nash-Williams proved that a class of ω +1-trees 4 is bqo, Laver proved that a class of On-trees are bqo, and Corominas proved that a class of C -trees is bqo.

Definition 2.35. For a tree T we call α ∈ On the height of T iff α = sup x ∈ T { ot( ↓ x ) } .

Definition 2.36. Let L be a class of linear orders and T be an L -tree, then we define as follows:

- · t ∈ T is called a leaf of T if there is no t ′ ∈ T such that t ′ &gt; t .
- · T is rooted iff T has a minimal element, denoted root( T ).
- · T is chain-finite iff every chain of T is finite.

Definition 2.37. Given a rooted chain-finite tree T , and some t ∈ T we define inductively 5

$$\text{rank} ( t ) = \sup \{ \text{rank} ( s ) + 1 \, | \, t < _ { T } s \}.$$

We then define the tree rank of T as rank( T ) = rank(root( T )).

4 Here ω +1 is the set of its predecessors.

5 For the base case we have that sup( ∅ ) = 0.

## 3. Operator construction

In this section we give the definitions required to translate more complicated structured trees (i.e. not necessarily chain-finite) into an operator algebra construction similar to Pouzet's [5]. First we must give the parameters of our construction. We will always let:

- · Q be concrete category;
- · B be a subset of Q ;
- · A be a concrete category;
- · F be a quasi-ordered class of functions f with range in Q ;
- · L be a non-empty class of linear orders that is closed under taking non-empty subsets;
- · C denote the whole system 〈Q B A F L〉 , , , , .

Intuitively, Q is going to be the class of objects for which we will be constructing a bqo subclass; B will be a class of 'simple' objects that we will start the construction from; A is a class of possible arities which we will use to generalise the notion of a multivariate function; F is a class of functions which we will be applying to elements of Q in order to construct more complex elements of Q ; and L is a class of linear orders which we will allow iteration of functions from F over. We will keep these standard symbols when using this construction.

We restrict our attention to such Q F A , , and L , so that for every f ∈ F there is some a ( f ) ∈ A and b ( f ) ⊆ a ( f ) with

$$\text{dom} ( f ) = \{ a \in \mathcal { Q } ^ { \mathfrak { a } ( f ) } \ | \ ( \forall i \in \mathbf b ( f ) ), \mathbf c _ { a } ( i ) \in \mathcal { B } \}.$$

(Here Q a ( f ) is as from Definition 2.20.) We call a ( f ) the arity of f . We think of the functions of F as having arguments structured by a ( f ). For example, if a ( f ) is a finite linear order of length n then the arguments of f are linearly ordered and f has the form f ( x , ..., x 1 n ); if a ( f ) were an antichain, then the order on the x i would not matter; and if a ( f ) was the binary tree of height 2 then we think of f having form

$$f \, \left ( \begin{array} { c } x \\ y \end{array} \right ). \\ \text{tions it will be more conv}$$

We do this because for some functions it will be more convenient to think of the arguments arranged in some general partial order (particularly the sums of Definition 2.30). We include b ( f ) in the definition, since in Section 6 it will be more convenient to only allow elements of B into some arguments of our functions. All other constructions used in this paper will have b ( f ) = ∅ for every f ∈ F , in which case dom( f ) = Q a ( f ) .

Example 3.1. Let Q be a quasi-order and L be some class of linear orders. Now we let

- · Q = L ( Q ) be the class of all Q -coloured linear orders;
- · B = Q 1 , i.e. single points coloured by elements of Q ;
- · A = L ∪ ω ;
- · F be the set of L -sums for all L ∈ A , as defined in Definition 2.30, inheriting colours;
- · L = { 1 } .

We order F by letting ∑ A /lessorequalslant F ∑ B iff A /lessorequalslant B . For ∑ L ∈ F we have a ( ∑ L ) = L and b ( ∑ L ) = ∅ . Now define C Q L = 〈Q B A F L〉 , , , , . This relatively simple example will construct the class L ( Q ), which will ultimately allow us to prove that if L is well-behaved, then L is well-behaved.

Example 3.2. Let Q be a quasi-order; Q ′ be Q with an added minimal element -∞ ; let L be some class of non-empty linear orders; and let P be some class of partial orders. Now we let

- · Q be the class all of Q ′ -coloured partial orders;
- · B = Q ′ 1 ;
- · A = P ;

- · F be the set of P -sums for all P ∈ P , inheriting colours;
- · L = L .

We order F by letting ∑ A /lessorequalslant F ∑ B iff A /lessorequalslant B . Now define C Q L P , = 〈Q B A F L〉 , , , , . This example will construct our class of Q ′ -coloured partial orders, that we will characterise in Section 7.

We wish to generalise Pouzet's operator algebra construction in two ways. The first way will allow us to iterate functions over a linear order from L , and the second way will allow us to take countable limits.

3.1. Iterating over L . First we will define what is required for iteration. This will allow us to represent complicated functions in terms of simpler ones. For a basic example, suppose we would like to construct the ω -sum as from Definition 2.30. Given two linear orders L 0 and L 1 , we can define the simple function +, so that L 0 + L 1 is a copy of L 0 followed by a copy of L 1 . Now suppose we iterate this function; we can easily define L 0 + L 1 + L 2 and L 0 + L 1 + L 2 + L 3 and so on. This is easily done finitely many times (which is what Pouzet was doing when he used chain-finite trees [5]). But it is possible to iterate + over a more complex linear order. Naturally, its ω iteration would be ⋃ i ∈ ω L i ordered by a &lt; b if a ∈ L i , b ∈ L j , i &lt; j or i = j and a &lt; L i b (i.e. the ω -sum). We need not stop there though, we could define this iteration over a larger linear order, e.g. its Q iteration could be defined similarly.

Here + is really the function ∑ C 2 . We think of this function as having arguments arranged in arity C 2 . At each successive stage of the iteration we apply the next function into argument corresponding to the larger of the two points in C 2 . 6 If we repeatedly compose ∑ C 2 in this way, we get the functions ∑ C 3 , ∑ C 4 , and so on. If we allowed ourselves to compose over a linear order we could get ∑ ω or ∑ Q as in the previous paragraph. So in general we want to be able to turn linearly ordered lists of functions, each with a distinguished argument, into a new function that acts as their composition. This gives rise to the definition of a composition sequence , which will be a list of functions f i indexed by a linear order r , each with a distinguished argument s i .

/negationslash

Definition 3.3. We call η a composition sequence iff η = 〈〈 f , s i i 〉 : i ∈ r 〉 where r ∈ L , and for all i ∈ r , we have f i ∈ F and s i ∈ a ( f i ) such that if i = max( ) then r s i / ∈ b ( f ).

We call r the length of the sequence η . For i ∈ r let

/negationslash

We also define A = i r a i and B = i r b ( f i ) so that B ⊆ A . For any j ∈ r , let

$$a _ { i } ^ { \eta } = & \begin{cases} \mathbf a ( f _ { i } ) \sum \{ s _ { i } \} & \text{if} \quad i \neq \max ( r ) \\ \mathbf a ( f _ { i } ) & \text{if} \quad i = \max ( r ) \end{cases}. \\ \bigsqcup _ { i \neq r } a _ { i } ^ { \eta } \text{ and } B ^ { \eta } = \bigsqcup _ { i \neq r } \mathbf b ( f _ { i } ) \text{ so that } B ^ { \eta } \subseteq A ^ { \eta }. \text{ For a}$$

$$\mathfrak { v } \stackrel { \sim } { \lambda \cdot \nu } \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \,. } \end{cases}$$

For each composition sequence η we will define a function f η that will act as the composition of the functions f i (in order type r ). We want f j to be applied to the composition of all of the f i (for i &gt; j ) in the argument s j .

/negationslash

Remark 3.4 . We require that for i ∈ r , if i = max( ) then r s i / ∈ b ( f ), because otherwise it could be that the composition of the f j for j &gt; i is not allowed into the domain of f i in position s i .

Example 3.5. Suppose we want to define iteration of the sums of Definition 2.30 over a general linear order. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 be a composition sequence, and for each i ∈ r , suppose a ( f i ) is a partial order, f i is the a ( f i )-sum, and s i ∈ a ( f i ). We turn this composition sequence into a new function f η that acts as the composition of the f i as follows. First define the partial

6 Note that since we are dealing with multivariate functions, we are required to distinguish an argument in order to know in which position to compose further sums inside.

Figure 2. The partial order H η , for η = 〈〈 ∑ N , 3 〉 : i ∈ ω 〉 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-34be3e38-f68d-453c-98b3-8f2a1312055e.jpg)

- · i = j and u &lt; a ( f i ) v ;

order H η as the set ⊔ i ∈ r a η i ordered so that for u, v ∈ H η we let u &lt; v iff u ∈ a η i , v ∈ a η j one of the following occurs:

- · i &lt; j and u &lt; a ( f i ) s i ;
- · i &gt; j and v &gt; a ( f j ) s j .

(See Figure 2.) We can then define our composition f η to be the H η -sum. Notice that for finite r , this is equivalent to the usual finite composition of sums, each composed in the argument s i .

The next definition allows us, in a general setting, to turn composition sequences into functions that will act as the linear composition of the functions in the composition sequence.

Definition 3.6. F is called L -iterable if we distinguish a class F L consisting of composition functions f η , for every composition sequence η = 〈〈 f , s i i 〉 : i ∈ r 〉 where

$$f ^ { \eta } \colon \{ \langle q _ { u } \colon u \in A ^ { \eta } \rangle \in \mathcal { Q } ^ { A ^ { \eta } } \ | \ ( \forall u \in B ^ { \eta } ), q _ { u } \in \mathcal { B } \} \longrightarrow \mathcal { Q },$$

and F L satisfies the following properties.

- (i) For all f 0 ∈ F and s 0 ∈ a ( f 0 ), we have f 〈〈 f ,s 0 0 〉〉 = f 0 .
- (ii) Given 〈 q u : u ∈ A η 〉 ∈ dom( f η ) and some j ∈ r , set q s j = f η + j ( 〈 q u : u ∈ a , i &gt; j η i 〉 ), then

$$f ^ { \eta } ( \langle q _ { u } \colon u \in A ^ { \eta } \rangle ) = f ^ { \eta _ { j } ^ { - } } ( \langle q _ { u } \colon u \in A ^ { \eta _ { j } ^ { - } } \rangle ).$$

So we require that when we split η up into initial and final sections η -j and η + j , the composition will behave as expected (i.e. f η is f η -j applied to f η + j ). The remaining arguments of f i are then those in positions corresponding to elements of a η i (see Figure 3), so we consider f η as a multivariate function from Q , which has arguments for each element of a η i , ( i ∈ r ), and only allows values admissible into dom( f i ) (i.e. those respecting that if u ∈ b ( f i ) then q u ∈ B ).

Remark 3.7 . For a composition sequence η of length r , notice that elements of A η can be indexed by i ∈ r and u ∈ a η i , so we will sometimes write elements of dom( f η ) as 〈 q i,u : i ∈ r, u ∈ a η i 〉 .

Lemma 3.8. Let C = C Q L P , = 〈Q B A F L〉 , , , , for some quasi-order Q , some class of linear orders L and some class of partial orders P . Then F is L -iterable .

Proof. Given a composition sequence η , define f η = ∑ H η as in Example 3.5. Consider Definition 3.6, clearly f η satisfies (i). It remains to show (ii), so let 〈 q u : u ∈ A η 〉 ∈ dom( f η ) and for some

Figure 3. The arrangement of the arguments of f η .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-4cb96a42-d4cd-4fea-914b-87095a542d70.jpg)

i ∈ r , let q s i = f η + i ( 〈 q u : u ∈ a , j &gt; i η i 〉 ). We have that H η + i = ⊔ j&gt;i a η j and H η -i = { s i }/unionsq ⊔ j /lessorequalslant i a η j . So that the H η -i -sum of H η + i in position s i and single points everywhere else is precisely H η . Similarly, we see that

$$f ^ { \eta } ( \langle q _ { u } \colon u \in A ^ { \eta } \rangle ) = \sum _ { u \in H _ { \eta } } q _ { u } = \sum _ { u \in H _ { \eta _ { i } } ^ { - } } q _ { u } = f ^ { \eta _ { i } ^ { - } } ( \langle q _ { u } \colon u \in a _ { i } ^ { \eta }, j \leqslant i \rangle ).$$

So we have (ii) as required.

/square

/negationslash

Definition 3.9. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 and ν = 〈〈 f , s ′ i ′ i 〉 : i ∈ r ′ 〉 be composition sequences. We define η /lessorequalslant ν iff there is an embedding ϕ : r → r ′ such that for every i ∈ r we have f i /lessorequalslant F f ′ ϕ i ( ) and an embedding ϕ i witnessing a ( f i ) /lessorequalslant a ( f ′ ϕ i ( ) ), such that whenever i = max( ), we have r ϕ i ( s i ) = s ′ ϕ i ( ) . If η /lessorequalslant ν we define ϕ η,ν : A η → A ν so that when u ∈ a η i we have ϕ η,ν ( u ) = ϕ i ( u ).

Definition 3.10. We call f ∈ F extensive if for all q ∈ Q and x ∈ dom( f ) with i ∈ x such that c ( ) = i q , we have that q /lessorequalslant Q f ( x ).

The idea of the next definition is to express the notion that applying 'short' lists of 'small' functions to 'small' objects will give a smaller result than applying 'long' lists of 'large' functions to 'large' objects.

Definition 3.11. We call C = 〈Q B A F L〉 , , , , infinitely extensive iff:

- · F is L -iterable;
- · every f ∈ F is extensive;
- · for any two composition sequences η /lessorequalslant ν and any k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ), k ′ = 〈 q ′ u : u ∈ A ν 〉 ∈ dom( f ν ), if for all u ∈ A η we have embeddings ϕ u witnessing q u /lessorequalslant q ′ ϕ η,ν ( u ) , then we have a corresponding embedding ϕ k,k ′ η,ν witnessing f η ( k ) /lessorequalslant Q f ν ( k ′ ).

Lemma 3.12. Let L be a class of linear orders and Q be an arbitrary quasi-order, then C Q L is infinitely extensive.

Proof. Let C Q L = 〈Q B A F L〉 , , , , . Since L = { 1 } it is clear that F is L -iterable. We have that every f ∈ F is extensive, because if we take the sum of some linear orders, then each of the linear orders embeds into the sum. Now suppose as in Definition 3.11 we have composition sequences

$$\eta = \langle \langle \sum _ { A }, s \rangle \rangle \text{ and } \nu = \langle \langle \sum _ { B }, s ^ { \prime } \rangle \rangle$$

with η /lessorequalslant ν and k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ), k ′ = 〈 q ′ u : u ∈ A ν 〉 ∈ dom( f ν ) such that q u /lessorequalslant q ′ ϕ η,ν ( u ) for each u ∈ A η , with ϕ u a witnessing embedding.

So we have that f η ( k ) = ∑ u ∈ A q u and f ν ( k ) = ∑ u ∈ B q ′ u . Moreover, ϕ η,ν is an embedding from A to B . So we define ϕ k,k ′ η,ν : f η ( k ) → f ν ( k ′ ) so that for a ∈ f η ( k ), with a ∈ q u we have

$$\varphi _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \varphi _ { u } ( a ) \in q _ { \varphi _ { \eta, \nu } ( u ) } ^ { \prime } \subseteq f ^ { \nu } ( k ^ { \prime } ).$$

Then ϕ k,k ′ η,ν is clearly an embedding. Hence C Q L is infinitely extensive.

/square

Lemma 3.13. Suppose C is infinitely extensive. Let η be a composition sequence and k = 〈 q u : u ∈ A η 〉 ∈ dom ( f η ) . Then for any u ∈ A η , we have q u /lessorequalslant f η ( k ) .

Proof. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 . Pick some u ∈ A η and let i ∈ r be such that u ∈ a η i . Set η ′ = 〈〈 f , s i i 〉〉 and q s i = f η + i ( 〈 q v : v ∈ a , j &gt; i η j 〉 ). Since f i ∈ F we have f i is extensive, therefore

$$q _ { u } \leqslant f _ { i } ( \langle q _ { v } \, \colon v \in \mathfrak { a } ( f _ { i } ) \rangle ) = f ^ { \eta ^ { \prime } } ( \langle q _ { v } \, \colon v \in A ^ { \eta ^ { \prime } } \rangle ).$$

Then by a simple application of the infinite extensivity of C , we see that

$$f ^ { \eta ^ { \prime } } ( \langle q _ { v } \, \colon v \in A ^ { \eta ^ { \prime } } \rangle ) \leqslant f ^ { \eta _ { i } ^ { - } } ( \langle q _ { v } \, \colon v \in A ^ { \eta _ { i } ^ { - } } \rangle ).$$

Now by L -iterability of F , we have

$$f ^ { \eta _ { i } ^ { - } } ( \langle q _ { v } \colon v \in A ^ { \eta _ { i } ^ { - } } \rangle ) = f ^ { \eta } ( k ).$$

So that q u /lessorequalslant f η ( k ), which gives the lemma.

/square

Definition 3.14. When F is L -iterable we define ˜ C 0 ⊆ Q as the smallest class containing B and closed under applying f η for any composition sequence η .

Example 3.15. Following Definitions 2.28 and 2.30. Let Q be the class of linear orders; B = { 1 } ⊆ Q ; A = On ∪ On ∗ and F = { ∑ α | α ∈ A} be the class of ordinal sums and reversed ordinal sums; finally set L = { 1 } . Then ˜ C 0 = S the class of scattered linear orders. This is precisely Theorem 2.32, Hausdorff's theorem on scattered order types [14].

Remark 3.16 . We can construct ˜ C 0 level by level. Starting with B ; at successor stages applying f η (for every composition sequence η ) to every element of the previous level; and at limit stages taking unions. This allows the definition of an ordinal rank of an element of ˜ . C 0 So for x ∈ C ˜ , 0 we denote by rank( x ) the least α ∈ On such that x appears at level α of this construction.

Definition 3.17. We define Q α = { x ∈ C ˜ 0 | rank( x ) = α } and Q &lt;α = { x ∈ C ˜ 0 | rank( x ) &lt; α } . For each composition sequence η we also define,

$$\text{dom} ( f ^ { \eta } ) _ { < \alpha } = \{ \langle q _ { u } \, \colon u \in A ^ { \eta } \rangle \in \text{dom} ( f ^ { \eta } ) \ | \ ( \forall u \in A ^ { \eta } ), \text{rank} ( q _ { u } ) < \alpha \}.$$

3.2. Limits. Now we will define limits, which will allow us to extend the construction further. For example, when we choose our parameters so that ˜ C 0 gives us scattered linear orderings (Example 3.15), taking limits will give us the σ -scattered linear orderings of [12]. The next definition will allow us to chain together many embeddings eventually allowing us to produce embeddings between limits.

Definition 3.18. We call C extendible iff C is infinitely extensive and satisfies the following property. For any two composition sequences η /lessorequalslant ν , and any k 0 = 〈 q 0 u : u ∈ A η 〉 ∈ dom( f η ), k 1 = 〈 q 1 u : u ∈ A η 〉 ∈ dom( f η ), and k = 〈 q u : u ∈ A ν 〉 ∈ dom( f ν ); if for all u ∈ A η we have:

- · q 0 u /lessorequalslant q 1 u with µ u a witnessing embedding;
- · q 0 u /lessorequalslant q ϕ η,ν ( u ) with ϕ u a witnessing embedding;
- · q 1 u /lessorequalslant q ϕ η,ν ( u ) with ψ u a witnessing embedding;

- · ϕ u = ψ u ◦ µ u ;

then we have

$$\varphi _ { \eta, \nu } ^ { k _ { 0 }, k } = \psi _ { \eta, \nu } ^ { k _ { 1 }, k } \circ \mu _ { \eta, \eta } ^ { k _ { 0 }, k _ { 1 } }.$$

Theorem 3.19. Let C = C Q L P , = 〈Q B A F L〉 , , , , for some quasi-order Q , some class of linear orders L and some class of partial orders P . Then C is extendible.

Proof. By Lemma 3.8 we know that F is L -iterable. If we take the sum of some partial orders, then each of these partial orders embeds into the sum and therefore every f ∈ F is extensive.

Suppose now as in Definition 3.11 that we have composition sequences

$$\eta = \langle \langle f _ { i }, s _ { i } \rangle \, \colon i \in r \rangle \text{ and } \nu = \langle \langle g _ { i }, s _ { i } ^ { \prime } \rangle \, \colon i \in r ^ { \prime } \rangle$$

with η /lessorequalslant ν and k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) and k ′ = 〈 q ′ u : u ∈ A ν 〉 ∈ dom( f ν ) such that q u /lessorequalslant q ′ ϕ η,ν ( u ) for each u ∈ A η , with ϕ u a witnessing embedding.

We have that f η ( k ) = ∑ u ∈ H η q u and f ν ( k ′ ) = ∑ u ∈ H ν q ′ u . Moreover ϕ η,ν is an embedding from H η to H ν . So we define ϕ k,k ′ η,ν : f η ( k ) → f ν ( k ′ ) so that for a ∈ f η ( k ), with a ∈ q u we have

$$\varphi _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \varphi _ { u } ( a ) \in q _ { \varphi _ { \eta, \nu } ( u ) } ^ { \prime }.$$

Which is clearly an embedding, hence C is infinitely extensive.

Now suppose that ˆ = k 〈 ˆ q u : u ∈ A η 〉 is such that q u /lessorequalslant ˆ q u for all u ∈ A η , with some witnessing embedding µ u . Suppose also that ˆ q u /lessorequalslant q ′ ϕ η,ν ( ) for each u ∈ A η , with ψ u a witnessing embedding, and that ϕ u = ψ u ◦ µ u . Then for a ∈ f η ( k ), with a ∈ q u we have

$$\varphi _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \varphi _ { u } ( a ) = \psi _ { u } \circ \mu _ { u } ( a ) \in q _ { \varphi _ { \eta, \nu } ( u ) } ^ { \prime }$$

and µ k,k ′ η,ν ( a ) = µ u ( a ) ∈ ˆ , so that q u

$$\psi _ { \eta, \nu } ^ { \hat { k }, k ^ { \prime } } \circ \mu _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \psi _ { u } \circ \mu _ { u } ( a ) \in q ^ { \prime } _ { \varphi _ { \eta, \nu } ( u ) }.$$

Thus we have verified the conditions of Definition 3.18, and C is extendible.

/square

Remark 3.20 . Let x ∈ C ˜ 0 with rank( x ) = α . So for some composition sequence η , we have that x = f η ( 〈 q u : u ∈ A η 〉 ), with q u ∈ Q &lt;α for all u ∈ A η . Applying the same reasoning to each of the q u , it is then possible to view x as a composition of some more composition functions, applied to further lower ranked elements or fragments (see Figure 4).

We repeat this process, splitting fragments into more fragments. Because the ranks are wellfounded we will eventually obtain g , a composition of many f η , and an element d of dom( g ), which is a configuration of elements of B such that g d ( ) = x . Since g is just a composition of f η , it will usually be possible to compose further still.

We now make precise the notion of composing many f η .

Definition 3.21. Let I be a tree of finite sequences of elements of ⋃ L × ⋃ A under /subsetsqequal , and let D be the set of leaves of I . Suppose that I has a /subsetsqequal -minimal element, 7 and that we have F = { η /vector ( p ) : /vector p ∈ I \ D } with each η /vector ( p ) a composition sequence. We write r /vector ( p ) for the length of η /vector ( p ). Now suppose that for each /vector p ∈ I we have

$$\vec { p } \langle i, u \rangle \in \mathfrak { I } \text{ iff } i \in r ( \vec { p } ) \text{ and } u \in a _ { i } ^ { \eta ( \vec { p } ) }$$

then we call F an composition set and I a set of position sequences of F . If additionally I is a chain-finite tree under /subsetsqequal then we call F admissible .

7 For this definition we denote the minimal element of I by 〈〉 , but in general it may not be 〈〉 .

Figure 4. The arrangement of the composition of f η and f ν . Here f ν is one of the arguments of f i .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-b4af498e-efb0-4a3d-aa71-af961ee15008.jpg)

If F is admissible we define the composition of F , a new function g F : Q D →Q . To do so, we determine the value of g F ( 〈 q /vector p : /vector p ∈ D 〉 ). When /vector p ∈ I \ D we define inductively

$$k ^ { \vec { p } } = \langle k ^ { \vec { p } } _ { i, u } \colon i \in r ( \vec { p } ), u \in a _ { i } ^ { \eta ( \vec { p } ) } \rangle \in \text{dom} ( f ^ { \eta ( \vec { p } ) } ),$$

such that for each i ∈ r /vector ( p ) and each u ∈ a η /vector ( p ) i we have

$$k _ { i, u } ^ { \dagger } & = \begin{cases} \ f ^ { \eta ( \vec { p } ^ { \wedge } \langle i, u \rangle ) } ( k ^ { \vec { p } ^ { \wedge } \langle i, u \rangle } ) & \colon & \vec { p } ^ { \wedge } \langle i, u \rangle \notin \mathfrak { D } \\ q _ { \vec { p } ^ { \wedge } \langle i, u \rangle } & \colon & \vec { p } ^ { \wedge } \langle i, u \rangle \in \mathfrak { D } \end{cases}. \\ \intertext { a n i t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t b a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a c t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t { a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a s t t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a a a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t t t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a s a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a e t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t a t
 } \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolis _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nolimits _ { \nuclas _ { \nolimits _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ } { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ {.nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuch _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nuclas _ { \nu {$$

Since I was a chain-finite tree, these k /vector p are well-defined. Now when F = , we define ∅

/negationslash

$$g ^ { \tilde { 8 } } ( \langle q _ { \vec { p } } \colon \vec { p } \in \mathfrak { D } \rangle ) = f ^ { \eta ( \langle \rangle ) } ( k ^ { \langle \rangle } ),$$

and when I = D = {〈〉} so that F = , we define ∅ g F ( 〈 x 〉 ) = x for every x ∈ Q .

Definition 3.22. Let F be an admissible composition set and I be a set of position sequences of F . For /vector p ∈ I we define

$$\mathfrak { F } ( \vec { p } ) = \{ \eta ( \vec { u } ) \in \mathfrak { F } \ | \ \vec { p } \sqsubseteq \vec { u } \}$$

and I ( /vector p ) = { /vector u ∈ I | /vector p /subsetsqequal /vector u } . We notice that F ( /vector p ) is an admissible composition set and I ( /vector p ) is a set of position sequences of F ( /vector p ). We also define D ( /vector p ) to be the set of leaves of I ( /vector p ).

Definition 3.23. Let F be an admissible composition set. We call g F a decomposition function for x ∈ C ˜ , whenever there is some 0 〈 q /vector p : /vector p ∈ D 〉 ∈ dom( g F ), such that ( ∀ /vector p ∈ D ), q /vector p ∈ B and

$$x = g ^ { \widetilde { \mathfrak { S } } } ( \langle q _ { \vec { p } } \colon \vec { p } \in \mathfrak { D } \rangle ).$$

Proposition 3.24. Let x ∈ Q α then for some composition sequence η and k ∈ dom ( f η ) &lt;α , we have x = f η ( k ) .

Proof. Clear by Remark 3.16.

/square

Lemma 3.25. For any x ∈ C ˜ 0 , there is a decomposition function g for x .

Proof. Let x ∈ C ˜ , then we will define a decomposition function 0 g for x inductively on the rank of x as follows. If rank( x ) = 0 then x ∈ B so set F = ∅ and I = D = {〈〉} , so that g F ( 〈 x 〉 ) = x is a decomposition function for x .

Suppose for induction that for every q ∈ Q &lt;α there is a decomposition function for x . If rank( x ) = α &gt; 0, then x = f η ( k ) for some composition sequence η of length r , and

$$k = \langle q _ { i, u } \colon i \in r, u \in a _ { i } ^ { \eta } \rangle \in \text{dom} ( f ^ { \eta } ) _ { < \alpha }.$$

So by the induction hypothesis, for each i ∈ r and u ∈ a η i , we see that q i,u = g F i,u ( d i,u ) for some admissible composition set F i,u = { η i,u ( /vector p ) | /vector p ∈ I i,u } with I i,u a set of position sequences for F i,u and some d i,u = 〈 d i,u /vector p : /vector p ∈ D i,u 〉 , where D i,u is the set of leaves of I i,u . Let

$$\mathfrak { I } = \{ \langle i, u \rangle \cap \vec { p } \colon i \in r, u \in a _ { i } ^ { \eta }, \vec { p } \in \mathfrak { F } _ { i, u } \} \cup \{ \langle \rangle \},$$

and let D be the set of leaves of I . We set η ( 〈〉 ) = η and for i ∈ r and u ∈ a η i , we set η ( 〈 i, u 〉 /slurabove /vector p ) = η i,u ( /vector p ). Now let F = { η /vector ( p ) | /vector p ∈ I } , so that clearly F is an admissible composition set. Finally we set d 〈 i,u 〉 /slurabove /vector p = d i,u /vector p and d = 〈 d /vector p : /vector p ∈ D 〉 now we have by construction

$$g ^ { \widetilde { s } } ( d ) = f ^ { \eta } ( \langle g ^ { \widetilde { s } _ { i, u } } ( d _ { i, u } ) \, \colon i \in r, u \in a _ { i } ^ { \eta } \rangle ) = f ^ { \eta } ( k ) = x.$$

Thus g F is a decomposition function for x , which completes the induction. /square

Definition 3.26. We call a decomposition function standard if it can be constructed by the method of Lemma 3.25.

Definition 3.27. Let ( x n n ) ∈ ω be a sequence of elements of ˜ . C 0 Suppose that Q has a minimal element q 0 and for every n ∈ ω , there is a standard decomposition function g n = g F n for x n , and some k n = 〈 k /vector p n : /vector p ∈ D n 〉 ∈ dom( g F n ) with g n ( k n ) = x n . Let I n be the set of position sequences of F n and D n be the set of leaves of I n . Then we call ( x n n ) ∈ ω a limiting sequence if there are such I n , F n , D n and k n such that the following properties hold for every n ∈ ω .

- (1) I n is a ↓ -closed subset of I n +1 .
- (2) F n +1 = { η n ( /vector p ) | /vector p ∈ I n \ D n } .
- (3) η n ( /vector p ) /subsetsqequal η n +1 ( /vector p ) for every /vector p ∈ I n \ D n .
- (4) If /vector u ∈ D m for all m /greaterorequalslant n , then for all m /greaterorequalslant n we have k /vector u n = k /vector u m .
- (5) If /vector u ∈ D n and /vector v ∈ D m with n &lt; m and /vector u /squareimage /vector v , then k /vector u n = q 0 , and ∀ /vector p ∈ D n +1 such that /vector u /subsetsqequal /vector p we have in fact /vector u /squareimage /vector p .

Limiting sequences ( x n n ) ∈ ω are those sequences with an increasing construction; that is to say that x n +1 is produced by the same set of functions as x n applied to increasingly more functions. We could perhaps be slightly less restrictive in the definition, particularly in conditions (4) and (5), however these conditions simplify some of the work later on and do not reduce the set of limits we can produce. 8 This condition determines the characteristics of limits, in particular it enforces that our bqo class of σ -scattered trees will be those covered by ↓ -closed scattered trees (as opposed to any scattered trees).

Remark 3.28 . Suppose C is infinitely extensive, let ( x n n ) ∈ ω be a limiting sequence, and η = η ( 〈〉 ). So for each n ∈ ω we have x n = f η ( k n ) and x n +1 = f η ( k n +1 ), for some k n = 〈 q n u : u ∈ A η 〉 , k n +1 = 〈 q n +1 u : u ∈ A η 〉 . It can be seen by an easy induction 9 that q n u /lessorequalslant q n +1 u with ψ u a witnessing embedding, for all u ∈ A η . So to simplify notation, we let µ n = ψ k n ,k n +1 η,η .

Note that in all of the applications in this paper, we consider x n as a subset of x n +1 , in this case µ n just acts as the identity on elements of x n , and we can define the limit to be the union.

Definition 3.29. Suppose that to every limiting sequence ( x n n ) ∈ ω we associate a unique limit x ∈ Q . Let η be a composition sequence, and for each n ∈ ω let η n /subsetsqequal η be a composition sequence so that η n /subsetsqequal η n +1 , and η = ⋃ n ∈ ω η n . Also let k n = 〈 q n u : u ∈ A η 〉 ∈ dom( f η n ) be such

8 This is the case at least in the applications used within this paper.

9 Using that q 0 was minimal and repeatedly applying Lemma 3.13.

that for every u ∈ A η we have ( q n u ) n ∈ ω is a limiting sequence with limit q u . We say that C has limits if the limit of ( f η n ( k n )) n ∈ ω is precisely f η ( 〈 q u : u ∈ A η 〉 ) for all such η , η n and k n ( n ∈ ω ).

Example 3.30. Let C = C Q L P , = 〈Q B A F L〉 , , , , for some quasi-order Q , some class of linear orders L and some class of partial orders P .

Given a limiting sequence ( x n n ) ∈ ω , we have by Remark 3.28 that µ n was the embedding given by infinite extensiveness of C using the construction of each x n . Each x n +1 is x n with some elements coloured by -∞ replaced by a larger partial order. The embedding µ n then acts as the identity on everything that is not changed, and maps a point a coloured by -∞ that is replaced, into some element b of the order that replaces it. Since it makes no difference to the order, we equate a and b , and consider the underlying set of x n as a subset of the underlying set of x n +1 , possibly with some colours changing from -∞ . In this way each µ n ( n ∈ ω ) becomes the identity map from the underlying set of x n to the underlying set of x n +1 .

Now given a limiting sequence ( x n n ) ∈ ω we have that x n ⊆ x n +1 for all n ∈ ω . Hence we can define the limit x to be the union of all of the x n . This means that C has limits, because an H η -sum of limits, is the limit of the H η -sums of the elements of the limiting sequence.

Definition 3.31. Suppose that C has limits. Let ˜ C ⊆ Q be the class containing all elements of ˜ C 0 and all limits of limiting sequences in ˜ . C 0 We also define ˜ C ∞ = ˜ C \ C ˜ 0 .

Finally the following condition allows us to produce embeddings between limits.

Definition 3.32. Suppose that C has limits. Then we say that C has nice limits iff for any x, y ∈ C ˜ with x the limit of ( x n n ) ∈ ω , and for any n ∈ ω ; if there are embeddings ϕ n : x n → y such that ϕ n = ϕ n +1 ◦ µ n , then x /lessorequalslant y . 10

Theorem 3.33. Let C = C Q L P , = 〈Q B A F L〉 , , , , for some quasi-order Q , some class of linear orders L and some class of partial orders P . Then C has nice limits.

Proof. Let x, y ∈ C ˜ be such that x is the limit of ( x n n ) ∈ ω and for any n ∈ ω we have embeddings ϕ n : x n → y such that ϕ n = ϕ n +1 ◦ µ n . We want to show that x /lessorequalslant y .

By Remark 3.30 we consider each x n ⊆ x n +1 and each µ n ( n ∈ ω ) to be the identity map. So ϕ n = ϕ n +1 ◦ µ n is equivalent to a ∈ x n implies ϕ n +1 ( a ) = ϕ n ( a ). Hence it is possible to define ϕ : x → y as the union of all of the ϕ n . We claim that ϕ is an embedding.

Let a, b ∈ x = ⋃ n ∈ ω x n , and let n be least such that a, b ∈ x n and c x n ( a ) = c x ( a ) (such an n exists since either the colour of a is always -∞ or changes at some n , but then stays this colour in x ). In order to show that x /lessorequalslant y we need to verify the following properties of ϕ .

- (1) a /lessorequalslant b iff ϕ n ( a ) /lessorequalslant ϕ n ( b ) iff ϕ a ( ) /lessorequalslant ϕ b ( ) (since ϕ n is an embedding).
- (2) c x ( a ) = c x n ( a ) /lessorequalslant c y ( ϕ n ( a )) = c y ( ϕ a ( )).

So indeed ϕ is an embedding from x to y , and thus x /lessorequalslant y as required.

/square

## 4. Decomposition trees

The aim of this section is to encode the elements of ˜ in C terms of structured trees. This reduces the problem of showing that ˜ is bqo to showing that a class of structured trees is bqo. C

## 4.1. Scattered and structured L -trees.

Definition 4.1. We define the tree 2 &lt;ω , (the infinite binary tree of height ω ), as the tree of finite sequences of elements of 2 = { 0 1 , } ordered by /subsetsqequal .

Definition 4.2. Let L be a class of linear orders and T be an L -tree, then we define as follows:

10 Here µ n is as from Remark 3.28.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-656ff874-dbf3-4dc3-8917-17912eb1bdb0.jpg)

Figure 5. A ζ -tree-sum of the T γ i .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-f87da1b1-c052-49c6-9efe-7886079c8a74.jpg)

. . .

Figure 6. Scattered L -trees of increasing scattered rank, and a σ -scattered L -tree.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-87074c81-1515-47e9-b43c-e8c311bfc47b.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-ee17dd3e-7cae-4d59-a9f3-baa7724a10ba.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-3dd91a1a-a8e1-40ee-a597-ff73f2c7ba02.jpg)

- · T is scattered iff 2 &lt;ω /lessorequalslant T .

/negationslash

- · T is L -σ -scattered iff there are countably many ↓ -closed subsets of T that are each scattered L -trees, and every point of T is contained in one of these subsets.
- · We let U L be the class of scattered L -trees.
- · We let T L be the class of L -σ -scattered L -trees.
- · We let R be the class of rooted ω +1-trees.

Remark 4.3 . When the context is clear we will call elements of T L σ -scattered. Notice that elements of T L are not necessarily L -trees as they could contain chains with order type not in L . 11 We note also that different classes of linear orders can generate the same classes of σ -scattered trees, for example T ω = T ω +1 .

Definition 4.4. Given a chain ζ , and L -trees T γ i for each i ∈ ζ , and γ &lt; κ i ∈ Card, we define the ζ -tree-sum of the T γ i (see Figure 5) as the set ζ /unionsq ⊔ i ∈ ζ,γ&lt;κ i T γ i ordered by letting a /lessorequalslant b iff · a, b ∈ ζ with a /lessorequalslant ζ b ;

- · or a ∈ ζ and b ∈ T γ i for some i ∈ ζ with a &lt; ζ i and γ &lt; κ i .
- · or for some i ∈ ζ , γ &lt; κ i we have a, b ∈ T γ i with a /lessorequalslant T γ i b ;

Definition 4.5. Let L be a class of linear orders that is closed under finite sums. Let U L 0 = {∅ , 1 } , and for α ∈ On let U L α +1 be the class of ζ -tree-sums of trees of U L α for ζ ∈ L . For limit λ ∈ On we let U L λ = ⋃ γ&lt;λ U L γ , and finally set U L ∞ = ⋃ γ ∈ On U L γ . For T ∈ U L ∞ define the scattered rank of T , denoted rank U ( T ) as the least ordinal α such that T ∈ U L α . (See Figure 6.)

Theorem 4.6. Let L be a class of linear orders that is closed under non-empty subsets and finite sums. Then U L = U L ∞ .

Proof.

We leave the proof as an exercise since it is similar to Theorem 6.7. /square

Definition 4.7. Let T be a class of L -trees, and let O be a concrete category. We define the new concrete category of O -structured trees of T , denoted T O as follows. The objects of T O consist of pairs 〈 T, l 〉 such that:

- · T ∈ T .

11 Elements of T L are are still L -trees.

Figure 7. A tree structured by { C 2 , A 2 } .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-d331d731-f1c7-4d81-b738-1953a6bed079.jpg)

- · U 〈 T,l 〉 = T .
- · l = { l | v ∈ T } , where for each v ∈ T there is some γ ∈ obj( O ) such that
- v v l v : /arrowtailright v -→ γ v

and if x, y ∈ T with x &gt; y &gt; v then l v ( x ) = l v ( y ).

For O -structured trees 〈 T, l 〉 and 〈 T , l ′ ′ 〉 , we let ϕ : T → T ′ be an embedding whenever:

- (1) x /lessorequalslant y iff ϕ x ( ) /lessorequalslant ϕ y ( ),
- (2) ϕ x ( ∧ y ) = ϕ x ( ) ∧ ϕ y ( ),
- (3) for any v ∈ T , set θ : range( l v ) → range( l ′ ϕ v ( ) ) such that

$$\theta ( l _ { v } ( x ) ) = l ^ { \prime } _ { \varphi ( v ) } ( \varphi ( x ) ) ;$$

then θ is an embedding of O .

We call l v ( x ) the v -label of x . To simplify notation, we write T in place of 〈 T, l 〉 and always use l v ( x ) to denote the v -label of x , regardless of which T ∈ T Q we are considering (it will be unambiguous since v ∈ T ).

Intuitively T O is obtained by taking T ∈ T and for each vertex v ∈ T , and ordering the successors of v by some order in O as in Figure 7. Embedding for T O is then tree embedding that preserves this ordering on the successors of v for every v ∈ T . However, general L -trees may contain points with no immediate successors. To accommodate this, our labelling functions l v have domain /arrowtailright v and we enforce that if x, y ∈ T with x &gt; y &gt; v then l v ( x ) = l v ( y ).

Definition 4.8. Let T be an O -structured L -tree, with x ∈ T and p ∈ range( l x ) then we define p /arrowtailright x = { y ∈ T | ( y &gt; x ) ∧ ( l x ( y ) = p ) } .

It is clear that T Q is a concrete category and hence we also have defined the Q -coloured, O -structured L -trees of T , denoted T O ( Q ). Finally we mention a theorem of Kˇ r´ ıˇ that z is fundamental to the results of this paper.

Theorem 4.9 (Kˇ r´ ˇ, ız [3]) . If O is a well-behaved concrete category with injective morphisms, then R O is well-behaved.

$$P r o o f. \, \text{See} \, [ 3 ].$$

/square

Remark 4.10 . Louveau and Saint-Raymond proved, using a modification of Nash-Williams' original method, that if Q satisfies a slight weakening of well-behaved (that is stronger than preserving bqo) then R Q , the class of Q -structured trees of R , satisfies this same property [8]. They were unable to attain full well-behavedness and Nash-Williams' method seems to be insufficient.

Theorem 4.11. If O is a well-behaved concrete category with injective morphisms, then T ω O is well-behaved.

/negationslash

Proof. Notice that any T ∈ T ω O is a tree of height at most ω , but not necessarily rooted. Consider { t | ∀ s ∈ T, s &lt; t } , let κ be the cardinality of this set, and enumerate its elements as t i for i ∈ κ . Given a quasi-order Q , let τ : T ω O ( Q ) → On( R O ( Q )) be the function sending T to 〈 κ, c 〉 where c i ( ) = ↑ t i for each i ∈ κ . Thus we have that if τ ( S ) /lessorequalslant τ ( T ) then S /lessorequalslant T . So given a bad T ω O ( Q )-array f , we see that τ ◦ f is a bad On( R O )-array, then by Theorem 2.22 we have a witnessing bad R O ( Q )-array, and by Theorem 4.9 we have a witnessing bad Q -array for f . /square

- 4.2. Encoding with structured L -trees. We now want to take an element x ∈ C ˜ and construct from it a structured L -tree T x that contains all of the information required to describe how x is built up from elements of B , using functions from F . We assume for the rest of this section that F is L -iterable and C has limits.

Definition 4.12. Let F be an composition set with I a set of position sequences for F , and d = 〈 d /vector p : /vector p ∈ D 〉 ∈ dom( g F ). Suppose that for each /vector p ∈ I we have η /vector ( p ) = 〈〈 f /vector p i , s /vector p i 〉 : i ∈ r /vector ( p ) . 〉 We define the F ∪ B -coloured A -structured L -tree T F d whose underlying set is

$$\{ \vec { p } \langle i \rangle \ | \ \vec { p } \in \mathfrak { I } \ \mathfrak { D }, i \in r ( \vec { p } ) \} \cup \mathfrak { D } ;$$

ordering /vector p /slurabove 〈 〉 i /lessorequalslant /vector q /slurabove 〈 j 〉 or /vector p /slurabove 〈 〉 i /lessorequalslant /vector q /slurabove 〈 j, u 〉 ∈ D iff either:

- (1) /vector p = /vector q and j /greaterorequalslant i .
- (2) /vector p /squareimage /vector q and the first element of /vector q \ /vector p is 〈 j , u ′ ′ 〉 with j ′ /greaterorequalslant i .

We colour all /vector p /slurabove 〈 〉 ∈ i T F d by letting

$$\mathbf c ( \vec { p } \, \langle i \rangle ) = f _ { i } ^ { \vec { p } },$$

and for /vector p ∈ D ⊆ T F d we let

$$\mathbf c ( \vec { p } ) = d ^ { \vec { p } }.$$

For all /vector p ∈ I \ D , i ∈ r /vector ( p ) and t &gt; /vector p /slurabove 〈 〉 i we define the labels l /vector p /slurabove 〈 〉 i ( ) t ∈ a ( f /vector p i ) so that

$$l _ { \vec { p } ^ { \sim } ( i ) } ( t ) = \begin{cases} \ s _ { i } ^ { \vec { p } } & \colon & \vec { p } ^ { \sim } \langle j \rangle \subseteq t \text{ or } \vec { p } ^ { \sim } \langle j, u \rangle \subseteq t \text{ for some } j > i \text{ and } u \in a _ { j } ^ { \eta ( \vec { p } ) } &. \\ u & \colon & \vec { p } ^ { \sim } \langle i, u \rangle \subseteq t &. \\ \tilde { \sim } & \tilde { \sim } & \tilde { \sim } &. \end{cases}.$$

Definition 4.13. If g F is a standard decomposition function for x ∈ C ˜ 0 and d is such that g F ( d ) = x , then we call T F d a decomposition tree for x .

Let ( x n n ) ∈ ω be a limiting sequence and x ∈ C ˜ ∞ be the limit of this sequence. Let q 0 , F n and k /vector p n be as in Definition 3.27. We set F = ⋃ n ∈ ω F n (so F is a composition set). Let /vector p ∈ D then there must be some least m such that k /vector p m ∈ D , and we let d /vector p = k /vector p m . 12 Set d = 〈 d /vector p : /vector p ∈ D 〉 . When F and d are defined in this way we call T F d a decomposition tree for x .

Lemma 4.14. If x ∈ C ˜ then there is a decomposition tree T = T F d for x such that T ∈ T L A ( F∪B ) . Moreover if x ∈ C ˜ 0 then there is a decomposition tree T ∈ U L A ( F ∪ B ) for x with rank U ( T ) = rank ( x ) .

Proof. Suppose x ∈ C ˜ 0 then let g F be the decomposition function for x as in Lemma 3.25, and let d = 〈 q /vector p : /vector p ∈ D 〉 ∈ dom( g F ) be such that x = g F ( d ) and q /vector p ∈ B for each /vector p ∈ D . In this case we set T = T F d , so T is a decomposition tree for x . We claim that rank U ( T ) = rank( x ), and prove this by induction on the rank of x .

If rank( x ) = 0 then x ∈ B so that T is just a single point coloured by x , and hence rank U ( T ) = 0. Suppose that rank( x ) = α and for each y ∈ Q &lt;α , and each decomposition tree T ′ for y that was constructed from the decomposition function given by Lemma 3.25, that we have rank( y ) =

12 Note that by (4) of Definition 3.27, we have k /vector p m = k /vector p n for any n /greaterorequalslant m .

rank U ( T ′ ). Then let ζ = {〈 〉 | i i ∈ r ( 〈〉 } ⊆ ) T so that T is a ζ -tree-sum of decomposition trees T u i for some q i,u ∈ Q &lt;α ( i ∈ ζ, u ∈ a η ( 〈〉 ) i ). Then using the induction hypothesis, we have

$$\text{rank} _ { \mathcal { Z } } ( T ) \ & = \ \sup \{ \text{rank} _ { \mathcal { Z } } ( T _ { i } ^ { u } ) + 1 \ | \ i \in \zeta, u \in a _ { i } ^ { \eta ( \langle ) } \} \\ & = \ \sup \{ \text{rank} ( q _ { i, u } ) + 1 \ | \ i \in \zeta, u \in a _ { i } ^ { \eta ( \langle ) } \} \\ & = \ \text{rank} ( x ).$$

This completes the induction, and the lemma holds for all x ∈ C ˜ . 0

If x ∈ C ˜ ∞ then a decomposition tree T for x was of the form T = T F d for some d and F = ⋃ n ∈ ω F n , with the F n as from Definition 3.27. By what we just proved, we have that the underlying set of T is covered by ↓ -closed subsets consisting of the underling sets of T n = T F n d n ∈ U L A ( F ∪ B ) for some d n ; hence T ∈ T L A ( F ∪ B ). /square

Lemma 4.15. Let x ∈ C ˜ and T = T F d be a decomposition tree for x . For any t = /vector p /slurabove 〈 〉 ∈ i T and u ∈ range ( l t ) , there exists some x t, u ( ) ∈ C ˜ with a decomposition tree T x t,u ( ) such that

$$^ { u } \uparrow t = T _ { x ( t, u ) }.$$

/negationslash

Moreover if x ∈ C ˜ 0 and /vector p = 〈〉 or u = s 〈〉 i ; then x t, u ( ) ∈ C ˜ 0 with rank ( x t, u ( )) &lt; rank ( x ) .

/negationslash

/negationslash

Proof. Let I be a set of position sequences for F and fix t = /vector p /slurabove 〈 〉 ∈ i T and u ∈ range( l t ). We will find x t, p ( ). First, if u = s /vector p i we define:

- · I t,u = { /vector q ∈ I | /vector p /slurabove 〈 i, u 〉 /subsetsqequal /vector q } ,
- · F t,u = { η /vector ( q ) | /vector p /slurabove 〈 i, u 〉 /subsetsqequal /vector q } ⊆ F ,

and if u = s /vector p i we define:

/negationslash

- · I t,u = { /vector q ∈ I | ( ∃ j &gt; i )( ∃ v ∈ a η /vector ( p ) j ) , /vector p /slurabove 〈 j, v 〉 /subsetsqequal /vector q } ∪ { /vector p } ,
- · η ′ ( /vector p ) = η /vector ( p ) + i , and η ′ ( /vector q ) = η /vector ( q ) whenever /vector p = /vector q ∈ I ,
- · F t,u = { η ′ ( /vector q ) | /vector q ∈ I t,u } .

Now let

- · D t,u be the set of leaves of I t,u ,
- · d t,u = 〈 d /vector q : /vector q ∈ D t,u 〉 , (where d = 〈 d /vector q : /vector q ∈ D 〉 ),
- · T t,u = T F t,u d t,u .

Then in either case, by construction we have that T t,u = u /arrowtailright t .

/negationslash

If g F t,u ( d t,u ) ∈ C ˜ 0 then set x t, u ( ) = g F t,u ( d t,u ), so we have that T t,u is by definition a decomposition tree for x t, u ( ). Moreover if /vector p = 〈〉 or u = s 〈〉 i then there is some i 0 ∈ r ( 〈〉 ) and u 0 ∈ range( l 〈 i 0 〉 ) such that T t,u ⊆ u 0 /arrowtailright i 0 and hence by Lemma 4.14 we have

/negationslash

$$\text{rank} ( x ( t, u ) ) = \text{rank} _ { \mathcal { A } } ( T _ { t, u } ) \leqslant \text{rank} _ { \mathcal { A } } ( ^ { u _ { 0 } } \uparrow i _ { 0 } ) < \text{rank} _ { \mathcal { A } } ( T ) = \text{rank} ( x ).$$

It just remains to find x t, u ( ) when x ∈ C ˜ ∞ . First suppose that x is the limit of ( x n n ) ∈ ω , then consider x n ( t, u ) for every n large enough so that t ∈ T F n . Then since ( x n n ) ∈ ω was a limiting sequence; for some m ∈ ω we have that ( x n ( t, u )) n /greaterorequalslant m is a limiting sequence. We let x t, u ( ) be its limit, then by construction x t, u ( ) has a decomposition tree equal to

$$T _ { d _ { t, u } } ^ { \mathbb { U } _ { n \in \omega } \, \mathfrak { F } _ { t, u } ^ { n } } = T _ { d _ { t, u } } ^ { \mathfrak { F } _ { t, u } } = T _ { t, u } = { ^ { u } } \uparrow t.$$

Definition 4.16. For a given x ∈ C ˜ and a decomposition tree T for x , let ζ be a ↓ -closed chain of T that contains no leaf. For each i ∈ ζ , if i is not the maximum element of ζ then let j i be an arbitrary element of ζ ∩↑ i , otherwise let j i be an arbitrary element of ↑ i . We then define

$$\eta ( \zeta ) = \langle \langle \mathbf c ( i ), l _ { i } ( j _ { i } ) \rangle \, \colon i \in \zeta \rangle$$

which is a composition sequence since for each i ∈ ζ we have c ( ) is i a function of F , and since the labels below i are elements of a c ( ( )). i We note that the choice of j i made no difference to l i ( j i ), except possibly when i is maximal, in which case only s i is ambiguous - but this makes no difference to f η ζ ( ) .

To simplify notation, for each i ∈ ζ , we let f ζ i = c ( ), i s ζ i = l i ( j i ) and a ζ i = a η ζ ( ) i . We also define k ζ = 〈 x i, u ( ) : i ∈ ζ, u ∈ a η ζ ( ) i 〉 ∈ dom( f η ζ ( ) ), where x i, u ( ) is as from Lemma 4.15.

We now require the following lemma, which will allow us to swap composition sequences.

Lemma 4.17. Let F be L -iterable, x ∈ C ˜ 0 have a decomposition tree T = T F d and let ζ be a ↓ -closed chain of T , that is either maximal or has a maximum element, then

$$x = f ^ { \eta ( \zeta ) } ( k ^ { \zeta } ).$$

Moreover if C has limits, then the conclusion holds for all x ∈ C ˜ .

/negationslash

/negationslash

Proof. Let ξ = {〈 〉 | i i ∈ r ( 〈〉 } ) be the chain satisfying η ξ ( ) = η ( 〈〉 ). We assume without loss of generality that ζ /subsetsqequal ξ , since otherwise the lemma follows from a simple application of L -iterability (noticing that η ζ ( ) = η ξ ( ) -max( ) ζ ). We also assume that ξ /subsetsqequal ζ since ξ /subsetsqequal ζ is impossible unless ξ has a maximum element, 13 in which case the lemma follows similarly by L -iterability. Clearly the Lemma holds when rank( x ) = 0 so suppose for induction that rank( x ) = α and the lemma holds for all y ∈ Q &lt;α .

By Lemma 4.14 we have T ∈ T L A ( F ∪ B ) and thus ξ ∩ ζ has a maximal element m . By Proposition 3.24, we have that x = f η ξ ( ) ( k ξ ) and k ξ ∈ dom( f η ξ ( ) ) &lt;α . For each χ ∈ { ζ, ξ } and u ∈ A η χ ( ) we define w χ u = x i, u ( ) whenever i is such that u ∈ a η χ ( ) i , and

$$w _ { s _ { m } ^ { \chi } } ^ { \chi } = f ^ { \eta ( \chi ) _ { m } ^ { + } } ( \langle w _ { u } ^ { \chi } \, \colon u \in A ^ { \eta ( \chi ) _ { m } ^ { + } } \rangle ).$$

We then set w χ = 〈 w χ u : u ∈ A η χ ( ) -m i 〉 ∈ dom( f η χ ( ) ). Thus, since F is L -iterable, we have

$$f ^ { \eta ( \xi ) } ( k ^ { \xi } ) = f ^ { \eta ( \xi ) _ { m } ^ { - } } ( w ^ { \xi } ) \quad \text{and} \quad f ^ { \eta ( \zeta ) } ( k ^ { \zeta } ) = f ^ { \eta ( \zeta ) _ { m } ^ { - } } ( w ^ { \zeta } ).$$

/negationslash

Clearly η ξ ( ) -m = η ξ ( ∩ ζ ) = η ζ ( ) -m since m was the maximal element of ξ ∩ ζ . It remains to verify that w ξ = w ζ . By definition of m , for all i &lt; m and u ∈ a ξ i = a ζ i , we have w ξ u = x i, u ( ) = w ζ u . We also have w ξ u = x i, u ( ) = w ζ u for u ∈ a ξ m ∩ a ζ m . So the only possible cases in which w ξ u = w ζ u are when u ∈ { s ζ m , s ξ m } , hence it only remains to verify that they agree here too.

/negationslash

Since ξ /subsetsqequal ζ and ζ /subsetsqequal ξ we have s ξ m = s ζ m , and therefore s ξ m ∈ a ζ m . Thus

/negationslash

/negationslash

$$w _ { s _ { m } ^ { \xi } } ^ { \zeta } = x ( m, s _ { m } ^ { \xi } ).$$

We also know

$$w ^ { \xi } _ { s ^ { \xi } _ { m } } = f ^ { \eta ( \xi ) ^ { + } _ { m } } ( \langle w ^ { \xi } _ { u } \, \colon u \in A ^ { \eta ( \xi ) ^ { + } _ { m } } \rangle ) = f ^ { \eta ( \xi ) ^ { + } _ { m } } ( \langle x ( i, u ) \, \colon i \in \xi, i > m, u \in a ^ { \eta ( \xi ) ^ { - } _ { m } } _ { i } \rangle )$$

and hence by the construction of x m,s ( ξ m ) from Lemma 4.15, we see that

$$w _ { s _ { m } ^ { \xi } } ^ { \xi } = x ( m, s _ { m } ^ { \xi } ).$$

Hence indeed we have w ξ s ξ m = w ζ s ξ m .

13 This is by definition of the order on decomposition trees.

Figure 8. The method of the proof of Lemma 4.17.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-c5e72012-cb81-476f-88e5-ea40c76c3076.jpg)

/negationslash

Similarly, we have that w ξ s ζ m = x m,s ( ζ m ) and w ζ s ζ m = f η ζ ( ) + m ( 〈 w ζ u : u ∈ A η ζ ( ) + m 〉 ). It remains only to show that these are equal. Note that by Lemma 4.15, since s ζ m = s ξ m we have that rank( x m,s ( ζ m )) &lt; α . We also have that η ζ ( ) + m = η ζ ( ∩ ↑ m ) and ζ ∩ ↑ m is a ↓ -closed chain of s ζ m /arrowtailright m , which is a decomposition tree for x m,s ( ζ m ). So by the induction hypothesis we have

$$w ^ { \xi } _ { s ^ { \zeta } _ { m } } = x ( m, s ^ { \zeta } _ { m } ) = f ^ { \eta ( \zeta ) ^ { + } _ { m } } ( \langle w ^ { \zeta } _ { u } \colon u \in A ^ { \eta ( \zeta ) ^ { + } _ { m } } \rangle ) = w ^ { \zeta } _ { s ^ { \zeta } _ { m } }.$$

So we have verified that f η ξ ( ) -m ( w ξ ) = f η ζ ( ) -m ( w ζ ), and therefore x = f η ξ ( ) ( k ξ ) = f η ζ ( ) ( k ζ ).

Now suppose that C has limits and let x be the limit of ( x n n ) ∈ ω . For each n ∈ ω let T n be the corresponding decomposition tree for x n , such that the underlying set of T is the union of the underlying sets of the T n ( n ∈ ω ). Then ζ = ⋃ n ∈ ω ζ n where for each n ∈ ω ζ , n is a ↓ -closed, chain of T n which is either maximal or has a maximal element. So by what we just proved, we have that x n = f η ζ ( n ) ( k ζ n ). But we know by Definition 3.29, that the limit of the limiting sequence ( f η ζ ( n ) ( k ζ n )) n ∈ ω is precisely f η ζ ( ) ( k ζ ). Therefore since limits were unique, we have f η ζ ( ) ( k ζ ) = x as required. /square

## 5. The construction is bqo

Now we aim to prove that if x, y ∈ C ˜ have decomposition trees T x and T y respectively, then x /lessorequalslant y . This will allow us to reflect bad ˜ -arrays to bad arrays for the trees. C Then we can use a structured tree theorem such as Theorem 4.11 or Theorem 6.12 in order to show that ˜ is bqo. C

## 5.1. The non-limit case.

Theorem 5.1. Suppose C is infinitely extensive. If x ∈ C ˜ 0 and y ∈ C ˜ have decomposition trees T x and T y respectively such that T x /lessorequalslant T y , then x /lessorequalslant y .

Proof. Suppose x, y are as in the statement of the theorem. We prove x /lessorequalslant y by induction on rank( x ). So for the base case we assume rank( x ) = 0, i.e. that x ∈ B , so we have that T x is just a single point coloured by x . If T x /lessorequalslant T y , then there must be some t 0 ∈ T y such that x /lessorequalslant c ( t 0 ) and thus necessarily t 0 = /vector p /slurabove 〈 i, u 〉 is a leaf of T y . Let ξ = ↓ t 0 , thus by Lemma 4.17 we have that y = f η ξ ( ) ( 〈 y j, u ( ) : j ∈ ξ, u ∈ a ξ j 〉 ). Now since y /vector ( p /slurabove 〈 〉 i , u ) = c ( t 0 ) we have by Lemma 3.13 that

$$x \leqslant \mathbf c ( t _ { 0 } ) \leqslant f ^ { \eta ( \xi ) } ( k ^ { \xi } ) = y$$

which gives the base case.

Now suppose that rank( x ) = α and whenever rank( x ′ ) &lt; α , T x ′ /lessorequalslant T y ′ and y ′ ∈ C ˜ we have x ′ /lessorequalslant y ′ . We set η = η ( 〈〉 ) as from Proposition 3.24, so for some k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) &lt;α , we have that x = f η ( k ). We also let χ = {〈 〉 | i i ∈ r ( 〈〉 } ⊆ ) T x , η = 〈〈 f , s i i 〉 : i ∈ r 〉 and ϕ be an embedding witnessing T x /lessorequalslant T y . We notice that η = η χ ( ).

For 〈 〉 ∈ i χ we denote by ϕ i the embedding from range( l 〈 〉 i ) to range( l ϕ ( 〈 〉 i ) ) induced by the structured tree embedding ϕ . We have, since ϕ was an embedding, that for each p ∈ range( l 〈 〉 i ),

$$\varphi ( ^ { p } \uparrow \langle i \rangle ) \subseteq ^ { \varphi _ { i } ( p ) } \uparrow \varphi ( \langle i \rangle ).$$

/negationslash

By Lemma 4.15, this implies T x ( 〈 〉 i ,p ) /lessorequalslant T y ϕ ( ( 〈 〉 i ) ,ϕ i ( p )) where T x ( 〈 〉 i ,p ) and T y ϕ ( ( 〈 〉 i ) ,ϕ i ( p )) are decomposition trees for x ( 〈 〉 i , p ) and y ϕ ( ( 〈 〉 i ) , ϕ i ( p )) respectively. Moreover, whenever p = s i , or 〈 〉 i is the maximum element of χ , we have p /arrowtailright i ∩ χ = ∅ ; hence rank( x i, p ( )) &lt; α by Lemma 4.15. Therefore, by the induction hypothesis, whenever p ∈ a η i we have that

$$x ( \langle i \rangle, p ) \leqslant y ( \varphi ( \langle i \rangle ), \varphi _ { i } ( p ) )$$

Now let so that by Lemma 4.17 we have that y = f η ζ ( ) ( k ζ ). Let ϕ ′ be the embedding from ot( χ ) to ot( ζ ) induced by ϕ . It then simple to verify that ϕ ′ and the ϕ i witness the fact that η = η χ ( ) /lessorequalslant η ζ ( ). Then using (1) and since C is infinitely extensive, we have

$$\zeta = \bigcup _ { t \in \chi } \downarrow \varphi ( t ) \\ = \ f ^ { \eta ( \zeta ) ( k ^ { \zeta } ) }. \ F e t. \, \varphi$$

$$x = f ^ { \eta } ( k ) \leqslant f ^ { \eta ( \zeta ) } ( k ^ { \zeta } ) = y$$

as required.

/square

We immediately obtain the following bqo result.

Corollary 5.2. Suppose C is infinitely extensive. Also suppose that T L A is well-behaved, F is bqo and B is bqo. Then ˜ C 0 is bqo.

Proof. Suppose we had a bad array f : [ ω ] ω → C ˜ . 0 Let g : [ ω ] ω → T L A ( F ∪ B ) be defined by letting g X ( ) be a decomposition tree for f ( X ). Then by Theorem 5.1, g must be bad. Thus since T L A is well-behaved there must be a bad F ∪ B -array, which is a contradiction of Theorem 2.8 since F and B were bqo. /square

We now present a simple application of Theorem 5.1. We will show that if a class of linear orders L is well-behaved, then L is well-behaved. This will allow us to give nicer descriptions of the classes that we will construct in section 7, as well as expanding on some classical results. So for the rest of this subsection we let L be a class of linear orders and Q be a quasi-order.

Definition 5.3. We define L 0 = L ∪ ω , and for α ∈ On,

$$\L _ { \alpha + 1 } = \left \{ \sum _ { i \in L } ^ { ^ { \prime } } L _ { i } \, | \, L \in \mathbb { L } _ { 0 }, L _ { i } \in \mathbb { L } _ { \alpha } \right \} \\ \L _ { \lambda } \, \mathbb { L } _ { \sim } \, \text{final} v \, \text{set} \, \mathbb { L } _ { \sim } = | | _ { \lambda \sim } \, \mathbb { L } _ { \lambda }. \text{ For } x \in \mathbb { L } _ { \sim } \, \text{w}$$

Proposition 5.4. Let C = C Q L , then L ∞ ( Q ) = ˜ C 0 .

and for limit λ , L λ = ⋃ γ&lt;λ L γ finally set L ∞ = ⋃ α ∈ On L α . For x ∈ L ∞ we say that rank L ( x ) = α iff α is least such that x ∈ L α .

Proof. This is by construction, considering Remark 3.16.

/square

## Lemma 5.5. L = L ∞ .

Proof. Clearly L ∪ ω ⊆ L ∞ ⊆ L . So if we can show that L ∞ is closed under sums, we will have the lemma. So let y ∈ L ∞ , and y j ∈ L ∞ for each j ∈ y , and we claim that ∑ j ∈ y y j ∈ L ∞ . Let y 〈〉 = y and suppose inductively that we have defined y s ∈ L ∞ \ L 0 for some sequence s . Then we can find y ′ s ∈ L 0 and for each i ∈ y ′ s , we find y /slurabove s 〈 〉 i ∈ L ∞ with rank L ( y /slurabove s 〈 〉 i ) &lt; rank L ( y s ); such that y s = ∑ i ∈ y ′ s y /slurabove s 〈 〉 i . Thus ∑ j ∈ y s y j = ∑ i ∈ y ′ s ∑ j ∈ y s /slurabove 〈 〉 i y j . So if every y /slurabove s 〈 〉 i ∈ L 0 then

∑ i ∈ y s y i ∈ L ∞ . Since the ranks are well-founded y s ∈ L 0 for all of the longest sequences s generated by this induction. So by induction, ∑ j ∈ y y j ∈ L ∞ , which gives the lemma. /square

Theorem 5.6. If L is well-behaved, then L is well-behaved.

Proof. Let C = C Q L = 〈Q B A F L〉 , , , , . By Lemma 5.5 and Proposition 5.4 we have that L ( Q ′ ) = ˜ . C 0 Suppose we have a bad L -array f , then define g X ( ) to be a decomposition tree for f ( X ). First we note that by Definition 4.12, it is clear that the leaves of the tree g X ( ) are coloured by some element of B used to construct f ( X ). Thus the colours of the linear order f ( X ) are colours of colours of elements of g X ( ). Now using Lemma 3.12 we can apply Theorem 5.1, in order to see that g is a bad array with range in U L A ( F ∪ B ).

We know that L = ω and hence is well-behaved. We also have that A = P is well-behaved and has injective morphisms; hence by Theorem 4.11, there is a witnessing bad F ∪ B -array g ′ . Since the order on F is isomorphic to the order on L , we know that F is bqo. Hence by Theorem 2.8, we can find a witnessing bad B -array f ′ . Since the colours from each g X ( ) that were in B were points of f ( X ) we now know that f ′ is a witnessing bad array for f . Then since B = Q 1 this clearly gives a witnessing bad Q -array just passing to colours. Hence any bad L ( Q )-array admits a witnessing bad Q -array, i.e. L is well-behaved. /square

Remark 5.7 . Without much more difficulty, using we could show that the class of countable unions of elements of L is also well-behaved, by considering limiting sequences ( x n n ) ∈ ω to be such that x n ⊆ x n +1 for each n ∈ ω and defining limits as the countable union. Then it is relatively simple to verify that C is infinitely extensive and has nice limits. The result then follows similarly to Theorem 5.6 (using Theorem 5.8 in place of Theorem 5.1). We omit the proof because this is implied by Theorem 7.37.

## 5.2. The limit case.

Theorem 5.8. Let C be extendible and have nice limits. If x, y ∈ C ˜ have decomposition trees T x and T y respectively such that T x /lessorequalslant T y , then x /lessorequalslant y .

Proof. By Theorem 5.1, it only remains to check that the theorem holds when x ∈ C ˜ ∞ . So suppose that x is a limit of the limiting sequence ( x n n ) ∈ ω . For each n ∈ ω let T n = T F n d n be a decomposition tree for x n . Since T n ⊆ T x /lessorequalslant T y and each x n ∈ C ˜ 0 we have by Theorem 5.1 that x n /lessorequalslant y for every n . Let ϕ n : x n → y be the embedding granted by infinite extensivity that was used in the final line of the proof of Theorem 5.1.

By the definition of a limiting sequence, we see that for each n ∈ ω there are k, k ′ ∈ dom( g n ) such that x n = g n ( k ) and x n +1 = g n ( k ′ ). If k = 〈 q u : u ∈ D n 〉 and k ′ = 〈 q ′ u : u ∈ D n 〉 then for each u ∈ D n we have q u /lessorequalslant q ′ u since either q u = q ′ u or q u is the minimum element q 0 . Set η = η ( 〈〉 ) ∈ F , then we can inductively find, using k and k ′ , elements k n , k n +1 of dom( f η ) such that x n = f η ( k n ), x n +1 = f η ( k n +1 ). Thus we have that if k n = 〈 q n u : u ∈ A η 〉 and k n +1 = 〈 q n +1 u : u ∈ A η 〉 then q n u /lessorequalslant q n +1 u , by repeated applications of Lemma 3.13. So let ψ u be the embedding witnessing q n u /lessorequalslant q n +1 u for u ∈ A η , granted by this induction. Then since C is extendible, we see that

$$\varphi _ { n } = \varphi _ { n + 1 } \circ \psi _ { \eta, \eta } ^ { k ^ { n }, k ^ { n + 1 } } = \varphi _ { n + 1 } \circ \mu _ { n }$$

with µ n as from Remark 3.28. Therefore, since Q has nice limits we have x /lessorequalslant y . /square

Again we immediately obtain a bqo result, we also mention some further corollaries.

Corollary 5.9. Let C be extendible and have nice limits. Suppose that T L A is well-behaved, F is bqo and B is bqo. Then ˜ C is bqo.

Proof. Suppose we had a bad ˜ -array C f . Let define the bad T L A ( F ∪ B )-array g by letting g X ( ) be a decomposition tree for f ( X ). Then by Theorem 5.8, g must be bad. Thus since T L A is well-behaved there must be a bad function to F ∪ B , which is a contradiction of Theorem 2.8 since F and B were bqo. /square

Corollary 5.10 (Laver [12]) . M , the class of σ -scattered linear orders is bqo.

Proof. Set Q B F A , , , and L as in Example 3.15. For a limiting sequence ( x n n ) ∈ ω , we consider x n ⊆ x n +1 and define the limit to be the union, in this way µ n acts as the identity on elements of x n . We then have that ˜ = C M . We have A = On ∪ On ∗ and L = { 1 } hence L = ω so since A has injective morphisms and by theorems 2.22, 2.8 and 4.11 we know T L A is well-behaved. By Corollary 5.9 it just remains to show that C is extendible and has nice limits. Since L = { 1 } it is easily verified that C is extendible. Finally if we have embeddings ϕ n for n ∈ ω as in the definition of nice limits, then we let ϕ be the union of the ϕ n , this clearly satisfies the definition of nice limits. The result now follows from Corollary 5.9. /square

Corollary 5.11 (Laver [13]) . T On , the class of σ -scattered trees is bqo.

Proof. Let Q be the class of all trees, B = {∅} ⊆ Q , A = On and L = 1 . We let { } F = { c α : α ∈ On } ∪ { d κ : κ ∈ Card , ordered so that } c α &lt; c β and d α &lt; d β for α &lt; β ; where we define:

- · c α : Q α →Q such that c α ( 〈 T γ : γ &lt; α 〉 ) is the α -tree-sum of the T γ ( γ &lt; α ).
- · d κ : Q →Q κ such that d κ ( 〈 T γ : γ &lt; κ 〉 ) is the disjoint union of the T γ .

Then ˜ C 0 is U On , the class of scattered trees (as in [13]) by Theorem 4.6. Define the limit of a limiting sequence to be the union so that ˜ = C T On . Now proceed similarly to Corollary 5.10. /square

The following theorem is our main application of Theorem 5.8, which is the crucial step in showing that the large classes of partial orders in Section 7 are well-behaved.

Theorem 5.12. Let Q be a quasi-order, L be a class of linear orders, P be a bqo class of partial orders and C = C Q L P , . If T L P is well-behaved, then any bad ˜ C -array admits a witnessing bad Q -array.

Proof. Let C = 〈Q B A F L〉 , , , , . Suppose we have a bad ˜ -array C f then for each X ∈ [ ω ] ω , let g X ( ) be a decomposition tree for f ( X ). First we note that by Definition 4.12, it is clear that the leaves of the tree g X ( ) are coloured by some element of B used to construct f ( X ). Thus the colours of the partial order f ( X ) are colours of colours of leaves of g X ( ). Now by Theorem 5.8 we have that g is a bad U L A ( F ∪ B )-array.

Since we assumed that T L P is well-behaved, there is a witnessing bad F ∪ B -array g ′ . Since the order on F is isomorphic to the order on P , we know that F is bqo. Hence we can restrict g ′ as in the proof of Theorem 2.8, to find a witnessing bad B -array f ′ . Since the colours from each g X ( ) that were in B were points of f ( X ) we now know that f ′ is a witnessing bad array for f . Then since B = Q ′ 1 we can restrict again to be inside the complement of f ′-1 ( -∞ ) in order to find a witnessing bad Q 1 -array. This clearly gives a witnessing bad Q -array just passing to colours. Hence any bad ˜ -array admits a witnessing bad C Q -array. /square

## 6. Constructing structured L -trees

The aim of this section is to show that whenever L is a class of linear orders and P is a class of partial orders both of which are well-behaved, then we have T L P is also well-behaved. We can then combine this result with Theorem 5.12. The proof will consist of an application of Theorem 5.8, but now we will construct structured trees instead of partial orders.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-b374553d-586b-4c18-b065-75059e0e9445.jpg)

ε

Figure 9. The order on E ′ , for given E ∈ E .

Definition 6.1. We define E ⊆ L P ( (A )) such that whenever 2 〈 E i : i ∈ r 〉 ∈ E and i ∈ r there is a unique e ∈ E i with c ( e ) = 1.

We define from E the new concrete category E ′ of A -coloured 2 P -structured L -trees. Let E ∈ E be such that E = 〈 E i : i ∈ r 〉 , for each i ∈ r we let

- · E ′ i = E i if i is not the maximum element of r ,
- · E ′ i = E i ∪ { ε } if i is the maximum element of r .

Then we define and let E ′ = { E ′ : E ∈ E } . We order E ′ as in Figure 9 by letting ε &gt; e ∈ E ′ iff c ( e ) = 1; and for d, e ∈ E ′ we have d &lt; e iff d = ε and either

$$E ^ { \prime } = \coprod _ { i \in r } E ^ { \prime } _ { i } \\ \text{as in Figure 9 1}$$

/negationslash

- · d, e ∈ E i , c ( d ) = 1, c ( e ) = 0.
- · d ∈ E i , e ∈ E j , i &lt; j and c ( d ) = 1.

The colouring of elements of the E i induces a colouring of E ′ (with colours in A ), we also set 2 c ( ε ) = 0 when ε ∈ E ′ . For each i ∈ r and d ∈ E i with c ( d ) = 1 and d &lt; e we define the label l d ( e ) to be d if c ( e ) = 1 and e otherwise. This gives us a P -structured L -tree E ′ . We call the chain of elements of E ′ coloured by 1 the central chain of E ′ .

We define morphisms of E ′ to be maps induced by embeddings of E (we can also find a place for the possibly new maximum ε ). Thus morphisms of E ′ will also be structured tree embeddings.

We will now define the parameters of our construction. Throughout this section, we let:

- (1) Q be an arbitrary quasi-order;
- (2) Q ′ be Q with an added minimal element -∞ ;
- (3) P be an arbitrary concrete category;
- (4) L be an arbitrary class of linear orders;
- (5) Q = T L P ( Q ′ );
- (6) B = Q 1 ∪ {∅} ⊆ Q ;
- (7) A = E ′ ;
- (8) L = { 1 } .

It remains to define F , now we will define its functions.

Definition 6.2. For each E = 〈 E i : i ∈ r 〉 ∈ E we define the function S E : dom( S E ) → Q as follows. First let a ( S E ) = E ′ and b ( S E ) = { e ∈ E ′ | c ( e ) = 1 } be the central chain of E ′ . Define

the function τ : dom( S E ) →Q E ′ so that τ ( 〈 x i : i ∈ E ′ 〉 ) = 〈 x ′ i : i ∈ E ′ 〉 where x ′ i is a single point coloured by -∞ if x i = ∅ and i is on the central chain of E ′ ; and x ′ i = x i otherwise. Now we let S E = E ′ ◦ τ . We inherit labels and colours in this sum. We define S E /lessorequalslant F S F iff E /lessorequalslant E F .

∑ Throughout this section we will also let F = { S E : E ∈ E } .

Remark 6.3 . Clearly the minimal element of Q is ∅ . Therefore elements of limiting sequences are constructed by replacing ∅ arguments with larger L -trees. So limiting sequences will be sequences of coloured and structured L -trees, whose underlying sets are each ↓ -closed subsets of the next (as in Figure 6). Thus it is possible to define limits as unions of such sequences.

We now have two goals. Firstly we will show that ˜ = C T L P ( Q ′ ), and secondly we will verify the conditions of Theorem 5.8. Using this theorem we will then see that T L P is well-behaved whenever L and P are well-behaved.

6.1. The constructed trees are σ -scattered. Now we aim to show that ˜ = C T L P ( Q ′ ).

Definition 6.4. Let T ∈ T L P ( Q ′ ), ξ be a chain of T and t ∈ ξ . We define l t ( ξ ) to be ∅ whenever t is the maximal element of ξ , and if there is some t ′ ∈ ξ with t ′ &gt; t then we let l t ( ξ ) = { l t ( t ′ ) } . This is well-defined by the definition of l t .

Lemma 6.5. Suppose that T ∈ T L P ( Q ′ ) \ C ˜ 0 , and ξ is an ↓ -closed chain of T that contains no leaves. Then either ⋂ j ∈ ξ ↑ j / ∈ C ˜ 0 or there is some t ∈ ξ and p ∈ range ( l t ) \ l t ( ξ ) such that p /arrowtailright t / ∈ C ˜ 0 .

Proof. Let T and ξ ⊆ T be as described. Suppose ⋂ j ∈ ξ ↑ j ∈ C ˜ 0 and there are no such t and p . Pick a maximal chain ζ of ⋂ j ∈ ξ ↑ j , and let ξ ′ = ζ ∪ ξ . Then for each i ∈ ot( ξ ′ ) let ξ ′ i be the i th element of ξ ′ and we define E i as an A -coloured copy of range( 2 l ξ ′ i ) ∈ P , that we colour as follows. When ot( ξ ′ ) has a maximum element m , we let every colour of E m be 0. For nonmaximal i ∈ ot( ξ ′ ) we let u ∈ E i be coloured with 1 iff there is some j ∈ ot( ξ ′ ) with i &lt; j and l ξ ′ i ( ξ ′ j ) = u . We set E = 〈 E i : i ∈ ot( ξ ′ ) , then we have that 〉 E ∈ E .

/negationslash

Now for a ∈ E ′ we define K a ∈ T L P ( Q ′ ) as follows. If a is the i th point on the central chain of E ′ and c T ( ξ ′ i ) = -∞ we let K a be a single point coloured by c T ( ξ ′ i ), if c T ( ξ ′ i ) = -∞ then we let K a = , hence ∅ K a ∈ B . Otherwise a is not on the central chain of E ′ and we can let i be largest such that the i th point w of the central chain of E ′ is &lt; a (there was such a largest element, by definition of the order on E ′ ). Now let u ∈ range( l w ) be such that l w ( a ) = u . Then we set

$$K _ { a } = { ^ { u } } \uparrow \xi _ { i } ^ { \prime } \subseteq T.$$

We then have by construction that

$$S _ { E } ( \langle K _ { a } \colon a \in E ^ { \prime } \rangle ) = T.$$

But we know that each K a was in ˜ C 0 by our original assumption. Hence since ˜ C 0 was closed under applying any function in F it must be that T ∈ C ˜ 0 which is a contradiction. /square

Lemma 6.6. Suppose that T ∈ T L P ( Q ′ ) \ C ˜ 0 , then there is some u ∈ T and two disjoint ↑ -closed subtrees S , S 1 2 ⊆ /arrowtailright u such that S , S 1 2 / ∈ C ˜ 0 .

Proof. Let T ∈ T L P ( Q ′ ) \ C ˜ . 0 Pick a chain ξ 0 of T that contains no leaves and is maximal. Then by Lemma 6.5 there is some t 0 ∈ ξ 0 and p 0 ∈ range( l t 0 ) \ l t 0 ( ξ 0 ) such that p 0 /arrowtailright t 0 / ∈ C ˜ . 0 Suppose for induction that for some α ∈ On we have defined t 0 &lt; ... &lt; t α ∈ T and p , ..., p 0 α such that for any γ &lt; α we have l t γ ( t α ) = p γ and p γ /arrowtailright t α / ∈ C ˜ . 0 We now apply Lemma 6.5 to a maximal chain ξ α of p α /arrowtailright t α that contains no leaves, whence we find t α +1 ∈ p α /arrowtailright t α and p α +1 such that p α +1 /arrowtailright t α +1 / ∈ C ˜ , 0 in other words t α +1 and p α +1 satisfy the induction hypothesis.

/negationslash

Now suppose for some limit λ ∈ On we have defined such t γ and p γ for every γ &lt; λ . Let ζ λ = ⋃ γ&lt;λ ↓ t γ , then ζ λ is an ↓ -closed chain of T that contains no leaves because every element has some t γ larger than it. By Lemma 6.5 either ⋂ j ∈ ζ λ ↑ j / ∈ C ˜ 0 or there is some t ∈ ζ λ and p ∈ range( l t ) \ l t ( ζ λ ) such that p /arrowtailright t / ∈ C ˜ . 0 Suppose the latter, then let δ be least such that t &lt; t δ . Since t δ ∈ ζ λ we have that l t ( t δ ) ∈ l t ( ζ λ ) = ∅ . Now we also had that p / l ∈ t ( ζ λ ), hence the trees S 1 = p /arrowtailright t and S 2 = p δ /arrowtailright t δ are disjoint. Moreover each is clearly ↑ -closed and we also have S , S 1 2 / ∈ C ˜ 0 we now set u = t and we are done.

/negationslash

Finally suppose that ⋂ j ∈ ζ λ ↑ j / ∈ C ˜ , 0 then pick a maximal chain ξ λ of ⋂ j ∈ ξ ↑ j , so by Lemma 6.5 there is some t λ ∈ ξ λ and p λ ∈ range( l t λ ) \ l t λ ( ξ λ ) such that p λ /arrowtailright t λ / ∈ C ˜ , and we can continue 0 the induction. Now the induction must stop at some point, otherwise for all limit λ ∈ On it must be that ⋂ j ∈ ζ λ ↑ j = ∅ , and therefore T is a proper class! This contradiction ensures that we will always find u , S 1 and S 2 as required. /square

$$\text{Theorem } 6. 7. \ \tilde { \mathcal { C } } _ { 0 } = \mathcal { V } _ { \mathbb { P } } ^ { \overline { \mathbb { L } } } ( Q ^ { \prime } ).$$

/negationslash

/negationslash

Proof. First we will show that ˜ C 0 ⊆ U L P ( Q ′ ). It is clear that ˜ C 0 consists of Q ′ -coloured, P -structured L -trees, so we prove by induction on the rank of x ∈ C ˜ 0 that 2 &lt;ω /lessorequalslant x . Clearly if x ∈ B then 2 &lt;ω /lessorequalslant x , so we have the base case.

So let x ∈ Q α for some α ∈ On. Then for some E ∈ E we have that x = S E ( 〈 x i : i ∈ E ′ 〉 ) with x i ∈ Q &lt;α for each i ∈ E ′ . Hence by the induction hypothesis, x is a ζ -tree-sum of the scattered trees x i , ( i ∈ E ′ ) of lower rank for some chain ζ ⊆ x .

/negationslash

For the other direction we want to show ˜ C 0 ⊇ U L P ( Q ′ ). So suppose that T ∈ U L P ( Q ′ ) \ C ˜ , 0 we will show that 2 &lt;ω /lessorequalslant T . First we set T 〈〉 = T . Now suppose that we have already defined T s / ∈ C ˜ 0 for some s ∈ 2 &lt;ω . We apply Lemma 6.6 to T s to obtain corresponding u s , and S , S s 1 s 2 / ∈ C ˜ . 0 Now let T s /slurabove 〈 0 〉 = S s 1 and T s /slurabove 〈 1 〉 = S s 2 .

Suppose 2 &lt;ω /lessorequalslant x and let ψ be a witnessing embedding. Then either range( ψ ) is contained entirely inside the chain ζ (which is a contradiction) or there is some z ∈ 2 &lt;ω with ψ z ( ) inside x i for some i ∈ E ′ . But each x i is ↑ -closed, hence ψ ( ↑ z ) ⊆ x i . But for any point t ∈ 2 &lt;ω we have that ↑ t is a copy of 2 &lt;ω , and therefore 2 &lt;ω /lessorequalslant x i which contradicts that x i was scattered. Therefore 2 &lt;ω /lessorequalslant x , and hence we have ˜ C 0 ⊆ U L P ( Q ′ ).

We now define the embedding ϕ : 2 &lt;ω → T by letting ϕ s ( ) = u s . We claim that this is a tree embedding. For any s ∈ 2 &lt;ω we have that the ↑ -closed trees T s /slurabove 〈 0 〉 and T s /slurabove 〈 1 〉 are disjoint, hence u /slurabove s 〈 0 〉 and u /slurabove s 〈 1 〉 are incomparable elements of T . It remains to check that for i ∈ { 0 1 , } we have u s &lt; u /slurabove s 〈 〉 i , but this is clear since we had that

$$u _ { s \widehat { \mu } \langle i \rangle } \in T ^ { s \widehat { \mu } \langle i \rangle } = S _ { i } ^ { s } \subseteq \uparrow u _ { s }.$$

So indeed ϕ is an embedding and 2 &lt;ω /lessorequalslant T . Therefore T / ∈ U L P ( Q ′ ), and we conclude that ˜ C 0 ⊇ U L P ( Q ′ ). So we have shown both directions, which completes the proof. /square

## 6.2. The class T L P of structured trees is well-behaved.

Lemma 6.8. If L and P are well-behaved, then A is well-behaved and F is bqo.

Proof. Suppose L and P are well-behaved. We have that A = E ′ and E ⊆ L P ( (A )). 2 Consider the function

$$\tau \colon \mathbb { E } ^ { \prime } ( Q ) \rightarrow \mathbb { L } ( \mathbb { P } ( \mathtt A _ { 2 } \times Q ) ) \times Q ^ { \prime }$$

defined as follows. First if ˆ E ′ ∈ E ′ ( Q ), (so ˆ E ′ is an A 2 × Q -coloured copy of E ′ ∈ E ′ ), then let ˆ E be a coloured copy of E = 〈 E i : i ∈ r 〉 ∈ E such that c ˆ E i ( z ) = c ˆ E ′ ( z ) for every i ∈ r and z ∈ E i . If we added ε to E ′ then we let σ = c ( ε ), otherwise we let σ = -∞ . Then we define

τ ( ˆ ) = E ′ 〈 ˆ E,σ 〉 . Now if τ ( E ′ ) /lessorequalslant τ ( F ′ ) then there is an embedding of E that increases the colours that are in Q . Hence in this case E ′ /lessorequalslant F ′ .

So suppose there were a bad E ′ -array f , hence τ ◦ f is a bad L P ( (A 2 × Q )) × Q ′ -array and we notice that τ ◦ f ( X ) has all of its colours in Q from f ( X ), and all its colours in Q ′ either from f ( X ) or -∞ . By Theorem 2.9 we either get either a witnessing bad Q ′ -array or L P ( (A 2 × Q ))-array. In the first case applying the Galvin and Prikry Theorem 2.4, restricting to be inside the complement of f -1 ( -∞ ) would give a bad Q -array which would be witnessing for f .

So we have a witnessing bad L P ( (A 2 × Q ))-array. Since L is well-behaved, we have by Theorem 5.6 that L is well-behaved, and hence since P is also well-behaved, we have a witnessing bad A 2 × Q -array f ′ . But each of the colours in Q of f ′ ( X ) were from f ( X ), hence using Theorem 2.9 we find a witnessing bad Q -array for f . Therefore A = E ′ is well-behaved. Clearly this means that E is bqo, and hence also F is bqo. /square

We now verify the conditions of Theorem 5.8.

## Lemma 6.9. Every f ∈ F is extensive.

Proof. Let S E ∈ F and consider x = S E ( 〈 T u : u ∈ E ′ 〉 ). Either u ∈ E ′ is on the central chain of E ′ and T u is the minimal element ∅ ; or a copy of T u appears precisely in x . /square

## Theorem 6.10. C is extendible.

Proof. Since L = { 1 } it is clear that F is L -iterable. By Lemma 6.9 we know that every f ∈ F is extensive. So suppose as in Definition 3.11 that we are given composition sequences

$$\eta = \langle \langle S _ { E }, s \rangle \rangle \text{ and } \nu = \langle \langle S _ { F }, s ^ { \prime } \rangle \rangle$$

with η /lessorequalslant ν and k = 〈 q u : u ∈ A η 〉 ∈ dom( S E ), k ′ = 〈 q ′ u : u ∈ A ν 〉 ∈ dom( S F ) such that q u /lessorequalslant q ′ ϕ η,ν ( u ) for each u ∈ A η with ϕ u a witnessing embedding. So we have that f η ( k ) = S E ( k ) and f ν ( k ) = S F ( k ′ ). We also have that ϕ η,ν is an embedding from E ′ = A η to F ′ = A ν . We define ϕ k,k ′ η,ν : f η ( k ) → f ν ( k ′ ) as follows.

If u is on the central chain of E ′ , then u ∈ b ( S E ), so that q u ∈ B . We see that ϕ η,ν sends elements of the central chain of E ′ to the central chain of F ′ since it was induced from an embedding of E , thus also q ′ ϕ η,ν ( u ) ∈ B . Let a be the point of f η ( k ) that corresponds to u , i.e. either it is the single point of q u in the sum or q u = ∅ and a is a single point coloured by -∞ . In this case we let ϕ k,k ′ η,ν ( a ) be the point b ∈ f ν ( k ′ ) that corresponds to ϕ η,ν ( u ). Notice that the embedding ϕ u gives us that c ( a ) /lessorequalslant c ( b ).

Suppose u is not on the central chain of E ′ and that a ∈ q u ⊆ f η ( k ), then we let

$$\varphi _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \varphi _ { u } ( a ) \in q _ { \varphi _ { \eta, \nu } ( u ) } \subseteq f ^ { \nu } ( k ^ { \prime } ).$$

Then clearly ϕ k,k ′ η,ν is a structured tree embedding, since ϕ η,ν , and each of the ϕ u ( u ∈ A η ) are embeddings. Therefore C is infinitely extensive.

Now suppose that ˆ = k 〈 ˆ q u : u ∈ A η 〉 is such that q u /lessorequalslant ˆ q u for all u ∈ A η , with some witnessing embedding µ u . Suppose also that ˆ q u /lessorequalslant q ′ ϕ η,ν ( ) for each u ∈ A η , with ψ u a witnessing embedding, and that ϕ u = ψ u ◦ µ u . Then for a ∈ f η ( k ), with a ∈ q u , we have

$$\varphi _ { \eta, \nu } ^ { k, k ^ { \prime } } ( a ) = \varphi _ { u } ( a ) = \psi _ { u } \circ \mu _ { u } ( a ) \in q ^ { \prime } _ { \varphi _ { \eta, \nu } ( u ) }$$

and µ k,k ′ η,ν ( a ) = µ u ( a ) ∈ ˆ , so that q u

$$\psi _ { \eta, \nu } ^ { \hat { k }, k ^ { \prime } } \circ \mu _ { \eta, \eta } ^ { k, \hat { k } } ( a ) = \psi _ { u } \circ \mu _ { u } ( a ) \in q ^ { \prime } _ { \varphi _ { \eta, \nu } ( u ) }.$$

It remains to check when q u = ∅ and a is the point corresponding to u . In this case ϕ k,k ′ η,ν ( a ) is the point b ∈ f ν ( k ′ ) corresponding to ϕ η,ν ( u ). Now µ k,k ˆ η,η ( a ) is the point of f η ( ˆ ) k corresponding

to u , so that ψ ˆ k,k ′ η,ν ◦ µ k,k ˆ η,η ( a ) = b . Thus we have verified the conditions of Definition 3.18, and therefore C is extendible. /square

## Theorem 6.11. C has nice limits.

Proof. First it is easily verified that C has limits. Let x, y ∈ C ˜ be such that x is the limit of ( x n n ) ∈ ω and for any n ∈ ω we have embeddings ϕ n : x n → y such that ϕ n = ϕ n +1 ◦ µ n . We want to show that x /lessorequalslant y .

We have by Remark 3.28 that µ n was the embedding given by the infinite extensiveness of F , using the construction of each x n . By the same argument as Remark 6.3; the underlying set of x n is a ↓ -closed subset of the underlying set of x n +1 where we consider µ n : x n → x n +1 acting as the identity on x n . Now we have that ϕ n = ϕ n +1 ◦ µ n is equivalent to saying that when a ∈ x n we have ϕ n +1 ( a ) = ϕ n ( a ). Hence it is possible to define ϕ : x → y as the union of all of the ϕ n . We claim that ϕ is an embedding.

Let a, b ∈ x = ⋃ n ∈ ω x n , and let n be least such that a, b ∈ x n . Let l x a be the a -label of x , and l x n +1 a be the a -label of x n +1 . If b &gt; a we define θ : range( l x a ) → range( l ϕ a ( ) ) such that if l x a ( b ) = u then θ u ( ) = l ϕ a ( ) ( ϕ b ( )) (these are labels from x ). In order to show that x /lessorequalslant y we verify the following properties of ϕ (see Definition 4.7).

- (1) a /lessorequalslant b iff ϕ n ( a ) /lessorequalslant ϕ n ( b ) iff ϕ a ( ) /lessorequalslant ϕ b ( ) (since ϕ n is an embedding).
- (2) ϕ a ( ∧ b ) = ϕ a ( ) ∧ ϕ b ( ). Note that each x n is ↓ -closed in x . So that ϕ n ( a ∧ b ) is defined, and hence since ϕ n is an embedding, we have

$$\varphi ( a \wedge b ) = \varphi _ { n } ( a \wedge b ) = \varphi _ { n } ( a ) \wedge \varphi _ { n } ( b ) = \varphi ( a ) \wedge \varphi ( b ).$$

- (3) If a /lessorequalslant b then θ is an embedding. By property (5) of Definition 3.27, we have range( l x a ) = range( l x n +1 a ). So θ is an A -morphism since it is a map induced by the embedding ϕ n +1 .
- (4) c ( a ) /lessorequalslant c ( ϕ a ( )). By property (4) of Definition 3.27, we have

$$\mathbf c _ { x } ( a ) = \mathbf c _ { x _ { n } } ( a ) \leqslant \mathbf c _ { y } ( \varphi _ { n } ( a ) ) = \mathbf c _ { y } ( \varphi ( a ) ).$$

Hence ϕ is an embedding and x /lessorequalslant y as required.

/square

Theorem 6.12. Suppose that L and P are well-behaved, then T L P is well-behaved. 14

Proof. By Theorem 6.7 we have that ˜ = C T L P ( Q ′ ). Suppose we have a bad T L P ( Q ′ )-array f then define g X ( ) to be a decomposition tree for f ( X ). First we note that by Definition 4.12, it is clear that the leaves of the tree g X ( ) are coloured by some element of B used to construct f ( X ). Thus the colours of the tree f ( X ) are colours of colours of elements of g X ( ). Now by Theorem 5.8 we have that g is a bad array with range in T L A ( F ∪ B ).

We know that L = ω and A has injective morphisms. By Lemma 6.8 we know that A is well-behaved; hence by Theorem 4.11, there is a witnessing bad F ∪ B -array g ′ . Using Lemma 6.8 we know that F is bqo, hence we can restrict g ′ using Theorem 2.8, to find a witnessing bad array f ′ to B . Since the colours from each g X ( ) that were in B were points of f ( X ) we now know that f ′ is a witnessing bad array for f . Then since B = Q 1 ∪ {∅} we can restrict again to find a witnessing bad array to Q 1 , which clearly gives a witnessing bad array to Q just passing to colours. Hence any bad array admits a witnessing bad array, i.e. T L P is well-behaved. /square

14 This result was obtained independently by Christian Delhomme in as yet unpublished work. The author thanks him for his private communication.

## 7. Constructing partial orders

In this section we aim to show that some large classes of partial orders are well-behaved. Theorems 5.12 and 6.12 together, essentially already give us that some classes of partial orders are well-behaved. The challenge now is to characterise the partial orders that we have constructed.

Our method is similar to Thomass´ e's in [1], but expanded to make use of the two generalisations of section 3. This allows us to generalise the bqo class of partial orders not only to allow embeddings of the N partial order, but also into the transfinite. In order to prove his main result of [1], Thomass´ e used a structured tree theorem: that T C C 2 (A ) preserves bqo. 3 We will use what is essentially the same method, but with the more general trees T L P for general wellbehaved classes of partial orders P and linear orders L . So that, in particular when L = M and P = { 1 A , 2 , C 2 } we obtain a transfinite version of Thomass´'s result. e We will prove the general theorem (Theorem 7.37) in this section, and explore applications of this theorem in Section 8.

- 7.1. Intervals and indecomposable partial orders. We will now borrow some definitions from [1]. We want to define the indecomposable partial orders which will serve as building blocks for larger partial orders, in order to do so we first require the notion of an interval.

Definition 7.1. Suppose that a, b, c ∈ x ∈ Q . We say that a shares the same relationship to b and c , and write SSR( a b, c ; ) iff for all R ∈ { &lt;,&gt;, ⊥} we have aRb iff aRc.

/negationslash

Definition 7.2. Let P be a partial order and I ⊆ P , then we call I = ∅ an interval of P if ∀ x, y ∈ I and ∀ p ∈ P \ I we have SSR( p x, y ; ) .

Definition 7.3. Let P be a partial order. Then P is called indecomposable if every interval of P is either P itself, or a singleton. P is called decomposable if it is not indecomposable.

Proposition 7.4. Let η be a composition sequence of length r and b 0 , b 1 , b 2 ∈ H η , such that for each i ∈ { 0 1 2 , , } we have b i ∈ a η j i for j i ∈ r then

$$j _ { 0 } < j _ { 1 }, j _ { 2 } \longrightarrow \text{SSR} ( b _ { 0 } ; b _ { 1 }, b _ { 2 } ).$$

Proof. This is clear by the definition of H η

$$\text{ion of } H _ { \eta }. & & \Box$$

Lemma 7.5. Let 〈 I j : j ∈ r 〉 be a chain of intervals of a partial order P under ⊇ . Then ⋃ j ∈ r I j and ⋂ j ∈ r I j are intervals.

Proof. Let a ∈ P \ ⋃ j ∈ r I j and b, c ∈ ⋃ j ∈ r I j . Then b, c ∈ I i for some i ∈ r , we know that I i is an interval hence SSR( a b, c ; ) as required. The case of intersection is similar. /square

Definition 7.6. Let P be a partial order and I ⊆ P be an interval. We define the new partial order P/I to be the partial order obtained from P by removing all but one point of I . This is well-defined since I is an interval. If I is a set of disjoint intervals of P , then let P/ I be the partial order obtained from P by removing all but one point of each element of I .

Definition 7.7. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 be a composition sequence, k ∈ dom( f η ) and x ∈ Q α . We call 〈 η, k 〉 maximal for x iff for each i ∈ r we have a ( f i ) is indecomposable and there is a maximal chain 〈 I j : j ∈ r 〉 of intervals of x under ⊇ such that for some

$$\colon a ^ { \eta } \vee \varepsilon \, \text{dom} \, f ^ { \eta } \vee \varepsilon$$

we have x = f ( k ), and if η = 〈〈 f , s 〉 : i /greaterorequalslant j 〉 then we have for all j ∈ r ,

$$\cdot \, \check { \ } k = \langle q _ { i, u } \, \colon i \in r, u \in a _ { i } ^ { \eta } \rangle \in \text{dom} ( f ^ { \eta } ) _ { < \alpha }, \\ \intertext { a v e x } \, x = f ^ { \eta } ( k ), \, \text{and if } \eta _ { j } = \langle \langle f _ { i }, s _ { i } \rangle \, \colon i \geqslant j \rangle \, \text{then we have for all } j \in r, \\ I _ { j } = f ^ { \eta _ { j } } ( \langle q _ { i, u } \, \colon i \geqslant j, u \in a _ { i } ^ { \eta } \rangle ).$$

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-b5f7b5a1-1285-43b6-a2c2-7f46e487da5e.jpg)

.

Figure 10. The partial order 2 &lt;ω ⊥ .

Lemma 7.8. Let η be a composition sequence of length r , and k ∈ dom ( f η ) be such that 〈 η, k 〉 is maximal for x = f η ( k ) . Then any r ′ ⊆ r has an infimum and a supremum in r .

Proof. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 , η j = 〈〈 f , s i i 〉 : i /greaterorequalslant j 〉 , k = 〈 q i,u : i ∈ r, u ∈ a η i 〉 and I j = f η j ( 〈 q i,u : i /greaterorequalslant j, u ∈ a η i 〉 ). Consider I = i ∈ r ′ I i , this is an interval by Lemma 7.5.

- ⋂ 7.2. Generalised σ -scattered partial orders. We will now begin to characterise the partial orders that we were constructing earlier. For the rest of this section we let:

⋃ For any j ∈ r we have that I j is comparable with I under ⊆ , because if j &gt; i ′ for some i ′ ∈ r ′ then I ⊇ I i ′ ⊇ I j , and if j &lt; i ′ for all i ′ ∈ r ′ then for all such i ′ we have I j ⊇ I i ′ and this implies I j ⊇ I . Thus since η was maximal, we have that 〈 I i : i ∈ r 〉 is a maximal chain and thus I = I j 0 for some j 0 ∈ r . Clearly then j 0 is a greatest lower bound of r ′ , i.e. r ′ has an infimum in r . For the supremum, consider i ∈ r ′ I i , then the argument is similar. /square

- (1) Q be an arbitrary quasi-order;
- (2) Q ′ be Q with an added minimal element -∞ ;
- (3) P be a class of non-empty partial orders that is closed under non-empty subsets;
- (4) L be a class of linear orders that is closed under subsets;
- (5) C = C Q L P , = 〈Q B A F L〉 , , , , as in Example 3.2.

Definition 7.9. We let -2 &lt;ω be the partial order obtained by reversing the order on 2 &lt;ω . We also define the partial order 2 &lt;ω ⊥ as follows. Elements of 2 &lt;ω ⊥ are finite sequences of elements of 2, for s, t ∈ 2 &lt;ω ⊥ , we define s &lt; t iff there are some sequences u, s , t ′ ′ such that s = u /slurabove 〈 0 〉 /slurabove s ′ and t = u /slurabove 〈 1 〉 /slurabove t ′ . (See Figure 10.)

The following definition of S L P will characterise the orders of ˜ C 0 (see Theorem 7.35). We think of these as a generalisation of scattered linear orders S . We will think of M L P as a generalisation of σ -scattered orders M . Our aim is to show that ˜ C 0 = S L P and ˜ = C M L P .

Definition 7.10. We define S L P to be the class of non-empty partial orders X with the following properties.

- (i) If Y /lessorequalslant X is indecomposable, then Y ∈ P .
- (ii) Every chain of intervals of X with respect to ⊇ has order type in L .
- (iii) 2 &lt;ω , -2 &lt;ω and 2 &lt;ω ⊥ do not embed into X .

We let P L P be the class of those non-empty X satisfying (i) and (ii). We call a sequence ( x n n ) ∈ ω increasing if for each n ∈ ω , we have that x n ∈ S L P and x n +1 is an x n -sum of some partial orders from S L P (so we consider x n ⊆ x n +1 similarly to Remark 3.30). We let M L P be the class containing all of S L P and unions of increasing sequences.

Remark 7.11 . For any limiting sequence ( x n n ) ∈ ω , let y n be the underlying set of x n for each n ∈ ω . Then ( y n n ) ∈ ω is an increasing sequence. Furthermore, for any union y of an increasing

sequence, we could construct a limiting sequence ( x n n ) ∈ ω with a limit x whose underlying set is y and has any Q ′ -colouring that we desire.

In order to prove that ˜ = C M L P , we first require several lemmas. Firstly given an x ∈ C ˜ , we now want to fine tune the construction of a decomposition tree for x by making more explicit the choice of η used to construct a decomposition function. (See Lemma 3.25 and Definition 4.12.) We want to only take η that are maximal in the sense of Definition 7.7.

Lemma 7.12. Let x ∈ Q α ∩ P L P ( Q ) . Then there is a composition sequence η and k ∈ dom ( f η ) , such that 〈 η, k 〉 is maximal for x .

Proof. Let x ∈ Q α so by Proposition 3.24, there is some η and k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) &lt;α such that x = f η ( k ) = ∑ u ∈ H η q u . We will define a maximal chain 〈 I ′ i : i ∈ r ′ 〉 of intervals of x , a composition sequence η ′ and some k ′ ∈ dom( f η ′ ), so that 〈 η , k ′ ′ 〉 is maximal for x .

Let r be the length of η , then for j ∈ r define

$$I _ { j } = \{ d \in x \ | \ d \in q _ { u }, u \in a _ { i } ^ { \eta }, i \geqslant j \}.$$

By Proposition 7.4 and since x is an H η -sum, we have for all j ∈ r that I j is an interval of x ; and for i &lt; j we have I i ⊃ I j . So 〈 I j : j ∈ r 〉 is a chain of intervals under ⊇ . Consider a maximal chain 〈 I ′ i : i ∈ r ′ 〉 of intervals under ⊇ that includes all of the I j . For i ∈ r we define the set

$$D _ { i } = \sum _ { u \in a _ { i } ^ { \eta } } q _ { u } = I _ { i } \, \sum \{ I _ { i ^ { \prime } } \ | \ i ^ { \prime } < i \}$$

and for j ∈ r ′ we define the set

$$D _ { j } ^ { \prime } = I _ { j } ^ { \prime } \, \bigcup \{ I _ { j ^ { \prime } } ^ { \prime } \, | \, j ^ { \prime } < j \}. \\ \text{moreover since each of the $I_{i}$ were} \\ \text{more over $i$} \,. \,. \,. \,. \,. \,. \,. \,. \,.$$

Then D ′ j ⊆ x = ⋃ i ∈ r D i , and moreover since each of the I i were equal to some I ′ j it must be that each D i is a union of some of the D ′ j . In particular, for all j ∈ r ′ there is some i ∈ r such that D ′ j ⊆ D i . Therefore, for some b j ⊆ a η i and some q ′ u ⊆ q u for u ∈ b j , we can write

$$D ^ { \prime } _ { j } & = \sum _ { u \in b _ { j } } q ^ { \prime } _ { u }. \\ - \frac { 1 } { 2 } \sim \frac { 1 } { 2 } \sim \dots \dots \dots.$$

/negationslash

For j ∈ r ′ , if j = max( r ′ ) we put b ′ j = b j , otherwise we can set b ′ j = b j /unionsq { s ′ j } . We define the order on b ′ j by inheriting from b j , and for u ∈ b ′ j with u = s ′ j we put

- · u &lt; s ′ j iff there is some w ∈ x \ ⋃ j ′ /lessorequalslant j D ′ j ′ and v ∈ q ′ w such that v &lt; w and · u &gt; s ′ j iff there is some w ∈ x \ ⋃ j ′ /lessorequalslant j D ′ j ′ and v ∈ q ′ w such that v &gt; w . This order is well-defined since 〈 I ′ i : i ∈ r ′ 〉 was a chain of intervals.

$$D ^ { \prime } _ { j } = \sum _ { u \in a _ { j } \langle \{ s ^ { \prime } _ { j } \} } y _ { u }. \\ \omega \quad \cdot \, - \, \omega \quad \omega \quad.$$

Let Z = { Z γ : γ ∈ κ } be the set of all non-singleton unions of maximal chains of intervals of b ′ j that do not contain s ′ j ; so by Lemma 7.5 for each γ ∈ κ we have Z γ is an interval. Now let a j = b / ′ j Z , letting e γ ∈ a j be the point remaining from Z γ . So the only non-singleton intervals of a j contain s ′ j . For each u ∈ a j \ ( { e γ | γ &lt; κ } ∪ { s ′ j } ) define y u = q ′ u and for each γ ∈ κ define y e γ = ∑ u ∈ Z γ q ′ u . Thus we can write

We set f ′ j = ∑ a j and η ′ = 〈〈 f , s ′ j ′ j 〉 : j ∈ r ′ 〉 . For each i ∈ r , D i was a union of some D ′ j , so since 〈 I ′ i : i ∈ r ′ 〉 was a maximal chain of intervals, we can see that x = ⋃ j ∈ r ′ D ′ j . We chose η ′ precisely so that H η ′ consisted of copies of the a j arranged in the same order as the D ′ j were arranged; we also know that D ′ j was a sum of the y u and therefore x is an H η ′ sum of the y u .

In other words x = f η ′ ( 〈 y u : u ∈ A η ′ 〉 ). Since for each u ∈ A η we have q ′ u ⊆ q u ∈ Q &lt;α , we know that q ′ u ∈ Q &lt;α (by applying the same construction to q ′ u as to q u , taking smaller sums where necessary we see that q ′ u must have rank &lt; α ). Let η j = 〈〈 f , s ′ i ′ i 〉 : i /greaterorequalslant j 〉 then we have I ′ j = f η j ( 〈 q ′ u : u ∈ a , i η i /greaterorequalslant j 〉 ), since the I ′ j were just the corresponding portion of the H η ′ sum.

Now we set k ′ = 〈 y u : u ∈ A η ′ 〉 ∈ dom( f η ′ ) and thus in order to show that 〈 η , k ′ ′ 〉 is maximal, it remains only to show that a i is indecomposable for each i ∈ r ′ . So suppose for contradiction that there is an i ∈ r ′ with a i decomposable, so we can let Z be an interval of a i with 1 &lt; Z &lt; a | | | i | . Thus we have from before that s ′ i ∈ Z . Now set

$$J = \left ( \sum _ { u \in Z \vee \{ s _ { i } ^ { \prime } \} } y _ { u } \right ) \cup \bigcup _ { j > i } I _ { j } ^ { \prime }. \\ \text{id we are taking the sum, it is simple}.$$

Since Z is an interval of a i and we are taking the sum, it is simple to verify that J is an interval of x . Moreover, J is a strict subset of I ′ i = ( ∑ u ∈ a i \{ s ′ i } y u ) ∪ ⋃ j&gt;i I ′ j which strictly contains ⋃ j&gt;i I ′ j . But then existence of such a J contradicts that 〈 I ′ j : j ∈ r 〉 was a maximal chain of intervals. Thus no such Z exists and each a i is indecomposable. This completes the proof. /square

Remark 7.13 . When we constructed decomposition functions (Lemma 3.25), the only condition on the composition sequence η that we used at each stage is that when rank( x ) = α we have x = f η ( k ) for some k ∈ dom( f η ) &lt;α . Hence by Lemma 7.12, we can always assume without loss of generality that at every stage of the construction of a decomposition tree for x (Definition 4.12) we chose η with a corresponding maximal chain of intervals so that η was maximal. Doing so makes no difference to the results of Section 5, since the choice of η was arbitrary so long as η satisfies the condition above. For the rest of this section, we always assume that any decomposition tree was constructed by choosing such maximal composition sequences.

Lemma 7.14. If x ∈ C ∩ ˜ P L P ( Q ) has a decomposition tree T , then for every non-leaf t ∈ T , range ( l t ) is indecomposable.

Proof. Let t ∈ T x then either t is a leaf or t = /vector p /slurabove 〈 〉 i for some /vector p and i . If η /vector ( p ) = 〈〈 f /vector p i , s /vector p i 〉 : i ∈ r /vector ( p ) 〉 then range( l t ) = a ( f /vector p i ). Following Remark 7.13, we have assumed that η /vector ( p ) is maximal, and therefore a ( f /vector p i ) is indecomposable, which gives the lemma. /square

- 7.3. Pathological decomposition trees. We now continue with lemmas that mainly address which types of embeddings of 2 &lt;ω can appear within decomposition trees, and what affect such embeddings will have on the partial order. First we have a lemma that tells us that we can always find a copy of 2 &lt;ω in decomposition trees for elements of ˜ C ∞ .

Lemma 7.15. Let x ∈ P L P ( Q ) with x / ∈ C ˜ 0 , then any decomposition tree for x is not scattered.

Proof. We will prove this by induction on the scattered rank of possible decomposition trees for x . Since the only non-empty scattered tree of rank 0 is a single point, clearly x has no scattered decomposition tree of rank 0. Suppose for any y ∈ P L P ( Q ) \C ˜ 0 that y has no decomposition tree T ′ with rank U ( T ′ ) &lt; α and that x / ∈ C ˜ 0 has a scattered decomposition tree T with rank U ( T ) = α . Thus there is a chain ζ of T such that T is a ζ -tree-sum of the lower ranked trees p /arrowtailright t ( t ∈ ζ, p ∈ a ζ t ).

Then x = f η ζ ( ) ( k ζ ) by Lemma 4.17. For each t ∈ ζ and p ∈ a ζ t we have a decomposition tree T x t,p ( ) = p /arrowtailright t for x t, p ( ), with rank U ( T x t,p ( ) ) &lt; α . Thus by the induction hypothesis it must be that x t, p ( ) ∈ C ˜ . 0 But then since x = f η ζ ( ) ( k ζ ) we see that x is f η ζ ( ) applied to elements of ˜ C 0 hence it must be that x ∈ C ˜ . 0 This is a contradiction, therefore x has no scattered decomposition tree of rank α . This completes the induction and gives the lemma. /square

Figure 11. The structured trees B + , B -, C Q , and A .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-7553b453-3212-43ca-89c4-25065dfd162a.jpg)

Lemma 7.16. Let x ∈ C ˜ , and T be a decomposition tree for x . If y ⊆ x is indecomposable and | y | &gt; 1 , then there exists t ∈ T such that the underlying partial order of y embeds into range ( l t ) .

Proof. First we suppose x ∈ C ˜ . 0 If rank( x ) = 0 then x is a single point, hence | y | /lessorequalslant | x | = 1 which gives the base case. Suppose now that for some α ∈ On we have the lemma for all x 0 ∈ Q &lt;α and that some x ∈ Q α has an indecomposable subset y ⊂ x with | y | &gt; 1. Then we know that x = f η ( k ) = ∑ u ∈ H η q u for some k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) &lt;α . If any of these q u contains a subset isomorphic to a copy of y ; then since a decomposition tree for x is a ζ -tree-sum of decomposition trees for the q u (for some chain ζ ), by the induction hypothesis we are done.

So suppose for every u ∈ A η , q u does not have a subset isomorphic to y . We claim that if η = 〈〈 f , s i i 〉 : i ∈ r 〉 then for some i ∈ r , and some partial order P with y /lessorequalslant P , we have f i = ∑ P . If for some i ∈ r at least two points of y were in ∑ u ∈ a η i q u and another point of y was in ∑ u ∈ a η j q u for j &lt; i , then the interval

/negationslash

$$y \cap \bigcup _ { j ^ { \prime } > j } \sum _ { u \in a _ { i } ^ { \eta } } q _ { u } & \subset y \\ \intertext { w o c a n l o t i b o l a e t e n c h }$$

shows that y is decomposable. So we can let i be least such that y ∩ a η i = ∅ , and we know that there is at most one point v ∈ y contained inside some q u for u ∈ a η j with j &gt; i ; in this case we let ϕ v ( ) = s i . If two points of y were in some q u ⊂ x then there is another point of y not in here, so that the interval q u ∩ y ⊂ y shows that y is decomposable. Thus all w ∈ y \ { v } are inside ∑ u ∈ a η i q u , with at most one point in each q u . So we let ϕ w ( ) = u whenever w ∈ q u . Thus we have defined ϕ : y → a ( f i ) and it is simple to verify that ϕ is an embedding. Now without loss of generality we have η = η ( 〈〉 ) so that a ( f i ) = range( l 〈 〉 i ). This completes the proof for x ∈ C ˜ . 0

Suppose that x ∈ C ˜ ∞ is the limit of ( x n n ) ∈ ω . Then we claim that for some n ∈ ω there is some y ′ ⊆ x n such that the underlying orders of y ′ and y are isomorphic. Let n be least such that | y ∩ x n | &gt; 1. If y is not a subset of x n then for some m&gt;n , some points of x n were replaced by larger partial orders; equating the original point to a point of this partial order as in Remark 3.30. If at least two points of y were in a partial order that replaced a single point, then these points form a proper interval of y which contradicts that y is indecomposable. So let y ′ consist of those points of x n that are either in y or are replaced by a partial order containing a point of y in some x m ( m &gt; n ). Thus the underlying orders of y ′ and y are isomorphic. Hence for some T n a decomposition tree for x n we have t ∈ T n and the underlying partial order of y ′ = y embeds into range( l t ). Hence also t ∈ T . This completes the proof. /square

We next define the { C 2 , A 2 } -structured, { ∑ C 2 , ∑ A 2 } -coloured trees B + , B -, C , Q and A as in Figure 11. These will be pathological decomposition trees for the partial orders 2 &lt;ω , -2 &lt;ω , 2 &lt;ω ⊥ , Q and A ℵ 0 respectively (we deal with these in 7.4). It will turn out that Q and A can never be decomposition trees under the assumption granted by Remark 7.13.

Definition 7.17. B + has underlying set consisting of all finite sequences s = 〈 s i : i /lessorequalslant n 〉 of elements of { 0 1 2 3 , , , } such that:

/negationslash

- · if s = 〈〉 then s 0 ∈ { 2 3 , } ,
- · if s i ∈ { 0 1 , } and i &lt; n then s i +1 ∈ { 2 3 , } ,
- · if s i = 2 and i &lt; n then s i +1 ∈ { 0 1 , } ,
- · if s i = 3 then i = n .

Thus B + is a tree under /subsetsqequal . If n is even, then we set c ( s ) = C 2 and label so that

$$\text{ree under $\sqsubset$}. \text{ If $n$ is even, then we set $c(s)=\sum_{C_{2}}$ and label so that} \\ l _ { s } ( \widehat { s } \langle 3 \rangle ) = \min ( C _ { 2 } ) \text{ and } l _ { s } ( s \langle 2 \rangle \widehat { s } t ) = \max ( C _ { 2 } ) \\ \mu _ { s } \quad - \mu _ { s }.$$

for every possible sequence t . If n is odd, the we set c ( s ) = ∑ A 2 and range( l s ) = A . We define 2 the tree B -in the same way as B + , with the only difference that

$$l _ { s } ( \widehat { s } \langle 3 \rangle ) = \max ( C _ { 2 } ) \text{ and } l _ { s } ( \widehat { s } \langle 2 \rangle \widehat { s } t ) = \min ( C _ { 2 } )$$

for every possible sequence t . We also define the tree C in the same way as B + , but change the labels and colours as follows. If n is even, then we set c ( s ) = ∑ A 2 and label so that range( l s ) = A . If 2 n is odd then we set c ( s ) = C 2 and for every possible sequence t

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \delta _ { 2 } \dots \dots \dots \dots \dots \delta _ { 3 } \dots \dots \dots \dots \delta _ { 4 } \dots \dots \dots \delta _ { 5 } \dots \dots \dots \delta _ { 6 } \dots \dots \dots \delta _ { 7 } \dots \dots \dots \delta _ { 8 } \dots \dots \dots \delta _ { 9 } \dots \dots \dots \delta _ { 9 } \dots \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 } \dots \delta _ { 9 - 1 } \dots \delta _ { 9 - 2 } \dots \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \ dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta_ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 3 } \dots \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots \delta _ { 9 - 2 } \dots.$$

We now define Q as a copy of 2 &lt;ω , coloured and labelled so that for each t ∈ Q we have c ( ) = t ∑ C 2 and range( l t ) = C . 2 Finally we define A as a copy of 2 &lt;ω , coloured and labelled so that for each t ∈ A we have c ( ) = t ∑ A 2 and range( l t ) = A . 2

Lemma 7.18. Let x ∈ C ˜ have a decomposition tree T . Then if B + , B -/lessorequalslant T and A /lessorequalslant T , then there is a ↑ -closed subset A ⊆ T such that A /lessorequalslant A and for each t ∈ A , we have range ( l t ) = A 2 .

/negationslash

/negationslash

Proof. Suppose B + , B -/lessorequalslant T and A /lessorequalslant T , so let ϕ : A → T be a witnessing embedding. For each t = ϕ s ( ) ∈ im( ϕ ), we have that P t = range( l t ) is some partial order that embeds A . 2 Let a t = l t ( ϕ s ( /slurabove 〈 0 )) and 〉 b t = l t ( ϕ s ( /slurabove 〈 1 )). 〉 Hence a , b t t ∈ P t with a t ⊥ b t . Now for each t , either P t = { a , b t t } or there is some c t ∈ P t such that without loss of generality (swapping the names of a t and b t if necessary) one of the following cases occurs:

- (1) a , b t t ⊥ c t ,
- (2) a t &lt; c t ,
- (3) a t &gt; c t .

/negationslash

$$\text{If } s = s ^ { \prime } \cap \langle 2 \rangle \, \text{ we let } \delta _ { 0 } \text{ and } \delta _ { 1 } \text{ be elements of }$$

Suppose that there is some u 0 ∈ im( ϕ ) such that for every u ∈ im( ϕ ) ∩↑ u 0 there is t ( u ) /greaterorequalslant u and some c t ( u ) satisfying case 2, (i.e. a t ( u ) &lt; c t ( u ) ). Set τ ( 〈〉 ) = t ( u 0 ). Suppose we have defined τ ( s ) for some s ∈ B -of length n . To simplify notation, we let s ′ be s with its last element removed and π = τ ( s ). Now suppose further that whenever s = s ′ /slurabove 〈 3 , we have we have 〉 τ ( s ) ∈ im( ϕ ); and whenever s = 〈〉 , or s = s ′ /slurabove 〈 〉 i for i ∈ { 0 1 , } we have that τ ( s ) satisfies case 2.

$$\lim ( \varphi ) \cap ^ { a _ { \pi } } \updownarrow \pi \text{ and } \, \lim ( \varphi ) \cap ^ { b _ { \pi } } \updownarrow \pi$$

respectively, and set τ ( s /slurabove 〈 0 ) = 〉 t ( δ 0 ) and τ ( s /slurabove 〈 1 ) = 〉 t ( δ 1 ). These exist and are incomparable since A was a copy of 2 &lt;ω . If s = 〈〉 or s = s ′ /slurabove 〈 〉 i for i ∈ { 0 1 , } , then pick the values of τ ( s /slurabove 〈 2 ) 〉 and τ ( s /slurabove 〈 3 ) to be elements of 〉

$$\lim ( \varphi ) \cap ^ { a _ { \pi } } \uparrow \pi \text{ and } ^ { c _ { \pi } } \uparrow \pi$$

respectively. So by construction, the map τ : B -→ T is an embedding, which is a contradiction. Thus no such u 0 exists and there is u 1 ∈ im( ϕ ) such that no t &gt; u 1 satisfies case 2.

/negationslash

Now using that B + /lessorequalslant T , we can apply a similar argument to the tree ↑ u 1 (in place of T ) and case 3 (in place of case 2). So we find a u 2 ∈ im( ϕ ) such that for every t &gt; u 2 we have that t does not satisfy cases 2 or 3 for any choice of c t . Let A = ↑ u 2 , so that for each t ∈ A we have either P t = { a , b t t } or t satisfies case 1, for any choice of c t . Hence P t is an antichain, and therefore by

Lemma 7.14 we always have P t = { a , b t t } = A , since any indecomposable antichain is either 1 2 or A . It remains to check that 2 A /lessorequalslant A , but this is clear since A = ↑ u 2 , with u 2 ∈ im( ϕ ). /square

/negationslash

Lemma 7.19. Let T be a decomposition tree for x ∈ C ∩ ˜ P L P ( Q ) . If B + , B -/lessorequalslant T , then A /lessorequalslant T .

/negationslash

/negationslash

Proof. Suppose for contradiction that B + , B -/lessorequalslant T and A /lessorequalslant T . By Lemma 7.18 there is some ↑ -closed subset A ⊆ T such that for each t ∈ A we have range( l t ) = A . Consider 2 y = x t, p ( ) for arbitrary t ∈ A and p ∈ range( l t ). We claim that y is an antichain. Suppose not, then there is some chain y ′ ⊆ y of size 2. Hence by Lemma 7.16, since y ′ is an indecomposable subset of y with | y ′ | &gt; 1, there must be some t ∈ T y ⊆ A such that y ′ embeds into P t = range( l t ). But this is a contradiction since each P t was an antichain, therefore indeed we have that y is an antichain.

Let /vector q be shortest such that there is t ′ = /vector q /slurabove 〈 i 0 〉 ∈ p /arrowtailright t for some i 0 , let w ∈ a η /vector ( q ) i 0 , then set z = x t , w ( ′ ). Then z has decomposition tree w /arrowtailright t ′ which is a ↑ -closed subset of A and hence | T z | &gt; 1 and therefore | z | &gt; 1. Let η /vector ( q ) = η = 〈〈 f , s i i 〉 : i ∈ r 〉 and for j ∈ r let η j = 〈〈 f , s i i 〉 : i /greaterorequalslant j 〉 . By Remark 7.13 can assume that there is a maximal chain of intervals 〈 I j : j ∈ r 〉 of y , and some k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) &lt;α such that x = f η ( k ) and I j = f η j ( 〈 q u : u ∈ a , i η i /greaterorequalslant j 〉 ) for each j ∈ r .

$$\bigcup _ { i > i _ { 0 } } I _ { i } \subset I \subset I _ { i _ { 0 } }. \\ \text{i as an anti-chain } \text{Than}.$$

Thus we have that z = q w so that z ⊆ I i 0 = ∑ u ∈ H η i 0 q u , since w ∈ H η i 0 . For each i ∈ r we have f i = ∑ A 2 , therefore H η is an antichain of size | r | . Let I = I j \ { ρ } for some ρ ∈ z then since | z | &gt; 1 we have

But I ⊆ y is also an interval, since y is an antichain. Therefore 〈 I j : j ∈ r 〉 was not a maximal chain of intervals of y . This contradiction gives the lemma. /square

/negationslash

Lemma 7.20. Let x ∈ C ˜ have a decomposition tree T . Then if C /lessorequalslant T and Q /lessorequalslant T , then there is a ↑ -closed subset A ⊆ T such that Q /lessorequalslant A and for each t ∈ A , we have range ( l t ) = C 2 .

Proof. Similar to Lemma 7.18, replacing ⊥ with ⊥ and &lt; with ⊥

/negationslash

$$\text{ith $\perp$.}$$

/negationslash

Lemma 7.21. Let x ∈ C ∩ ˜ P L P ( Q ) have a decomposition tree T . Then if C /lessorequalslant T then Q /lessorequalslant T .

/negationslash

/negationslash

Proof. Suppose for contradiction that C /lessorequalslant T and Q /lessorequalslant T . By the reasoning of Remark 7.13 we can assume without loss of generality that each chain used to construct T was maximal. By Lemma 7.20 there is some ↑ -closed subset A ⊆ T such that for each t ∈ A we have range( l t ) = C . 2 We can now proceed as in Lemma 7.19, replacing the word chain with antichain, and vice versa. /square

Lemma 7.22. If x ∈ C ∩ ˜ P L P ( Q ) has a decomposition tree T such that B + /lessorequalslant T ( resp. B -, C ) , then 2 &lt;ω /lessorequalslant x ( resp. -2 &lt;ω , 2 &lt;ω ⊥ ) .

Proof. Let ϕ : B + → T be an embedding. Let W be the subset of B + consisting of 〈〉 , u /slurabove 〈 0 〉 and u /slurabove 〈 1 〉 for all possible sequences u . For each s ∈ W , let t s = ϕ s ( ), and u s = l t s ( ϕ s /slurabove ( 〈 3 )). 〉 Then let y s be an element of

$$x ( t _ { s }, l _ { t _ { s } } ( u _ { s } ) ) \subseteq x.$$

/negationslash

We now define an embedding ψ : 2 &lt;ω → x . Given a = 〈 a , a 0 1 , ..., a n -1 〉 ∈ 2 &lt;ω , if a = 〈〉 then let a ′ = a , and if a = 〈〉 let a ′ = 2 〈 , a 0 , 2 , a 1 , ..., 2 , a n -1 〉 . Now set ψ a ( ) = y a ′ , so if a, b ∈ 2 &lt;ω are such that a /lessorequalslant b then a /subsetsqequal b so that a ′ /subsetsqequal b ′ and thus t a ′ /lessorequalslant t b ′ and l t a ′ ( u a ′ ) /lessorequalslant l t b ′ ( u b ′ ) which means that ψ a ( ) /lessorequalslant ψ b ( ). If a ⊥ b then similarly t a ′ /lessorequalslant t b ′ and l t a ′ ( u a ′ ) ⊥ l t b ′ ( u b ′ ) so that ψ a ( ) ⊥ ψ b ( ). Thus ψ is an embedding and witnesses 2 &lt;ω /lessorequalslant x . The cases for -2 &lt;ω and 2 &lt;ω ⊥ are similar. /square

## 7.4. Pathological partial orders.

Definition 7.23. Set M = { 2 &lt;ω , -2 &lt;ω , 2 &lt;ω ⊥ } . We call elements of M pathological partial orders.

/negationslash

Lemma 7.24. Suppose we have x ∈ Q and for each i ∈ x , we have x i ∈ Q . Suppose that for y ∈ M and all z ∈ { x } ∪ { x i | i ∈ x } we have y /lessorequalslant z . Then y /lessorequalslant i ∈ x x . i

/negationslash

∑ Proof. Fix y ∈ M and suppose that y /lessorequalslant ∑ i ∈ x x i , with ϕ a witnessing embedding. For all t ∈ y , let i t be such that ϕ s ( ) ∈ x i t . Let F be a finite subset of x , i ∈ F , and s ∈ y .

/negationslash

/negationslash

We claim that there is some s ′ ∈ y with s /subsetsqequal s ′ such that for all z ∈ y with s ′ /subsetsqequal z we have i z = . So suppose for contradiction that for all i s ′ ∈ y with s /subsetsqequal s ′ there is some Z s ( ′ ) ∈ y with s ′ /subsetsqequal Z s ( ′ ) and i Z s ( ′ ) = . i We define ψ : y → x i inductively as follows. Let ψ ( 〈〉 ) = Z s ( ) and if for t ∈ y we have defined ψ t ( ) = ϕ t ( ′ ) then for m ∈ { 0 1 , } let ψ t ( /slurabove 〈 m 〉 ) = ϕ Z t ( ( ′ /slurabove 〈 m 〉 )) . It is easily verified then that ψ is an embedding, which is a contradiction and we have the claim. Applying the claim repeatedly for each i ∈ F , we then see that for all s ∈ y there is s F ∈ y with s /subsetsqequal s F such that for all i ∈ F and all z ∈ y with s F /subsetsqequal z we have i z = . i

Now let µ ( 〈〉 ) = ϕ ( 〈〉 ). Suppose inductively we have defined µ on some sequences t ∈ y so that µ t ( ) = ϕ t ( ′ ) for some t ′ , and let G be the set of these t such that µ t ( ) is already defined. Let u ∈ y be the lexicographically least element of y \ G and let v ∈ y and m ∈ { 0 1 , } be such that u = v /slurabove 〈 m 〉 ; so µ v ( ) is already defined. Now let u ′ = v ′ /slurabove 〈 m 〉 and let µ u ( ) = ϕ s ( G ). Now µ is an embedding and i µ t ( ) is distinct for distinct t . So let µ ′ : y → x be given by µ ′ ( ) = t i µ t ( ) , then µ ′ is an embedding, which is a contradiction. /square

Proposition 7.25. Let y ∈ M , and s, s , t ′ ∈ y be such that s /subsetsqequal s ′ and s and t are incomparable under /subsetsqequal . Then ¬ SSR( ; s s , t ′ ) and ¬ SSR( s ′ ; s, t ) .

Proof. Let y ∈ M and s, s , t ′ be as described. Suppose that y = 2 &lt;ω , then since 2 &lt;ω is just ordered by /subsetsqequal we have s /lessorequalslant s ′ and s ⊥ t hence ¬ SSR( ; s s , t ′ ). We also have that s ′ ⊥ t , and therefore ¬ SSR( s ′ ; s, t ). If y = -2 &lt;ω then we have s /greaterorequalslant s ′ , s ⊥ t and s ′ ⊥ t , and again we can conclude that ¬ SSR( ; s s , t ′ ) and ¬ SSR( s ′ ; s, t ). If y = 2 &lt;ω ⊥ then we have s ⊥ s ′ , and either t &gt; s and t &gt; s ′ or t &lt; s and t &lt; s ′ . Hence again we can conclude ¬ SSR( ; s s , t ′ ) and ¬ SSR( s ′ ; s, t ). /square

/negationslash

Lemma 7.26. Suppose that no element of M embeds into any element of P . Then for all y ∈ M , and for every composition sequence η we have y /lessorequalslant H η .

Proof. Let η = 〈〈 f , s i i 〉 : i ∈ r 〉 be a composition sequence, then for each i ∈ r , we have that a ( f i ) ∈ A . Since A = P we know that

/negationslash

$$( \forall i \in r ) ( \forall y \in \mathbb { M } ), y \ll \mathfrak { a } ( f _ { i } ).$$

/negationslash

/negationslash

/negationslash

Let a = ϕ ( 〈〉 ) and choose a 0 = ϕ s ( 0 ) ∈ a η i 0 and a 1 = ϕ s ( 1 ) ∈ a η i 1 as in the claim. Now choose a 00 = ϕ s ( 00 ) ∈ a η i 00 and a 11 = ϕ s ( 11 ) ∈ a η i 11 by applying the claim to a 0 and a 1 . Notice that by a similar argument to before, we can assume that every element of I = { i, i 0 , i 1 , i 00 , i 11 } is distinct, otherwise we would be able to embed y into a ( f j ) for some j ∈ I .

Suppose that for some y ∈ M , we have y /lessorequalslant H η with ϕ a witnessing embedding. We claim that for any a = ϕ s ( ) ∈ a η i , there are a 0 = ϕ s ( 0 ) ∈ a η i 0 and a 1 = ϕ s ( 1 ) ∈ a η i 1 with s /subsetsqequal s , s 0 1 , and s , s 0 1 incomparable under /subsetsqequal , with i = i 0 = i 1 = . Suppose not, then for some i s ∈ y and i ∈ r , we have ϕ s ( /slurabove t ) ⊆ a η i for every sequence t . This is a contradiction, since then y embeds into { t ′ ∈ y | s /subsetsqequal t ′ } /lessorequalslant a η i /lessorequalslant a ( f i ). This gives the claim.

We now use Proposition 7.4 in the following cases:

- · i 0 &lt; i , i 1 00 which implies SSR( a 0 ; a , a 1 00 ),
- · i 00 &lt; i , i 0 1 which implies SSR( a 00 ; a , a 0 1 ),
- · i 1 &lt; i , i 0 00 and i 1 &lt; i , i 0 11 which implies SSR( a 1 ; a , a 0 11 ),
- · i 1 &lt; i , i 0 00 and i 11 &lt; i , i 0 1 which implies SSR( a 11 ; a , a 0 1 ),

- · i 1 &lt; i , i 0 00 and i 0 &lt; i , i 1 11 which implies i 0 &lt; i 1 &lt; i 0 which is a contradiction.

Now note that any of the first four cases contradict Proposition 7.25. So we have a contradiction in every case, and our assumption that y /lessorequalslant H η must have been false. This gives the lemma. /square

/negationslash

Lemma 7.27. If x ∈ C ˜ 0 and for all y ∈ M , z ∈ P , we have y /lessorequalslant z , then for all y ′ ∈ M , y ′ /lessorequalslant x .

/negationslash

/negationslash

/negationslash

Proof. Clearly this holds when rank( x ) = 0, since then x is a single point and so does not embed any element of M . Suppose the statement holds for all x ′ ∈ Q &lt;α for some α ∈ On, and that x ∈ Q α . Then x = f η ( k ) = ∑ u ∈ H η q u for some composition sequence η and k = 〈 q u : u ∈ A η 〉 ∈ dom( f η ) &lt;α . By the induction hypothesis, for each u ∈ H η and y ∈ M we know that y /lessorequalslant q u , and by Lemma 7.26 we know that y /lessorequalslant H η . So by Lemma 7.24, we have that y /lessorequalslant x as required. /square

/negationslash

## 7.5. Characterising the construction.

## Lemma 7.28. Suppose that:

- · U is an indecomposable partial order with | U &gt; | 2 ;

/negationslash

Then I = P .

- · P = ∑ u ∈ U P u for some non-empty partial orders P u ( u ∈ U ) ; · I ⊆ P is an interval of P with I ∩ P v 0 = ∅ and I ∩ P v 1 = ∅ for some v 0 = v 1 ∈ U .

## Proof. First we claim that

/negationslash

$$J = \{ u \, | \, I \cap P _ { u } \neq \emptyset \}$$

is an interval of U . To see this, we let v ∈ U \ J , u , u 0 1 ∈ J , a ∈ P v and b 0 ∈ I ∩ P u 0 , b 1 ∈ I ∩ P u 1 . Then a / I ∈ (otherwise v ∈ J ), so we have SSR( a b , b ; 0 1 ) because I was an interval. But this implies SSR( v u , u ; 0 1 ) since P = ∑ u ∈ U P u , hence we have the claim that J is an interval of U . Since U was indecomposable, we either have | J | = 1 or J = U . If | J | = 1 then this contradicts our assumption that I ∩ P v 0 = ∅ and I ∩ P v 1 = ∅ for some v 0 = v 1 ∈ U . Hence J = U .

/negationslash

/negationslash

/negationslash

Suppose for contradiction that there is some a ∈ P \ I , then a ∈ P v for some v ∈ U . For arbitrary u , u 0 1 ∈ U = I ′ with v / ∈ { u , u 0 1 } we have b 0 ∈ I ∩ P u 0 and b 1 ∈ I ∩ P u 1 . Since a ∈ P \ I , b 0 , b 1 ∈ I and I is an interval, we then know that SSR( a b , b ; 0 1 ). So since P = ∑ u ∈ U P u and v / ∈ { u , u 0 1 } we see that SSR( v u , u ; 0 1 ). But then since u 0 and u 1 were arbitrary, it must be that U \ { v } is an interval. Hence since U was indecomposable we have | U \ { v }| = 1 which means | U | = 2 which is a contradiction. /square

## Lemma 7.29. Suppose that:

- · U = { 0 1 , } with 0 R 1 for some R ∈ { &lt;,&gt;, ⊥} , so U ∈ { A 2 , C 2 } ;

/negationslash

/negationslash

- · there are no non-empty subsets K ,K 0 1 of P 0 with K 0 ∩ K 1 = ∅ and P 0 = K 0 ∪ K 1 , such that for all a 0 ∈ K 0 and a 1 ∈ K 1 we have a Ra 0 1 .
- · P = ∑ u ∈ U P u for some non-empty partial orders P , u ( u ∈ U ) ; · I ⊆ P is an interval of P with I ∩ P 0 = ∅ and I ∩ P 1 = ∅ ;

## Then P 0 ⊆ I .

/negationslash

/negationslash

Proof. Suppose that P 0 ⊆ I so we can let K 0 = I ∩ P 0 , K 1 = P 0 \ I . So there are a ∈ I ∩ P 0 and b ∈ P 0 \ I , such that a ⊥ b if R = ⊥ and a ⊥ b if R = ⊥ , so in either case we have ¬ ( bRa ). Let c ∈ P 1 ∩ I , then bRc since P = ∑ u ∈ U P u and b ∈ P 0 . So we have shown ¬ SSR( ; b a, c ). But a, c ∈ I and b / I ∈ with I an interval, hence we have SSR( ; b a, c ), which is a contradiction. /square

/negationslash

In the next definition and following few lemmas (7.30, 7.31, 7.32, 7.33 and 7.34) we fix a composition sequence η = 〈〈 f , s i i 〉 : i ∈ r 〉 and k ∈ dom( f η ) so that 〈 η, k 〉 is maximal for P ∈ C ˜ . 0

Definition 7.30. Let k = 〈 P i,u : i ∈ r, u ∈ a η i 〉 and define:

- · P i = ∑ u ∈ a η i P i,u ;

/negationslash

/negationslash

- · P /greaterorequalslant i = ⋃ j /greaterorequalslant u P j ⊆ f η ( k ); · P &gt;i = P /greaterorequalslant i \ P i .

Lemma 7.31. Suppose that I is an interval of P and i ∈ r be such that I ∩ P i = ∅ and I ∩ P &gt;i = ∅ . If | a ( f i ) | &gt; 2 then P /greaterorequalslant i ⊆ I , and if | a ( f i ) | = 2 then P i ⊆ I .

/negationslash

/negationslash

/negationslash

If | a ( f i ) | = 2 then set R ∈ { &lt;,&gt;, ⊥} such that for a ∈ a η i we have aRs i . Then using Lemma 7.29, we either have either that P i ⊆ I or there are non-empty K ,K 0 1 ⊆ P i with K 0 ∩ K 1 = ∅ and P i = K 0 ∪ K 1 such that for all a 0 ∈ K 0 and a 1 ∈ K 1 we have a Ra 0 1 . Consider J = K 1 ∪ P &gt;i , let a ∈ P \ J and z , z 0 1 ∈ J then either a ∈ P \ P /greaterorequalslant j in which case we have SSR( a z , z ; 0 1 ) or a ∈ K 0 in which case aRz 0 and aRz 1 , so that SSR( a z , z ; 0 1 ). Thus J is an interval. But we have that P &gt;i ⊂ J ⊂ P /greaterorequalslant i , which contradicts that η was maximal. So it must be that P i ⊆ I . /square

Proof. We have that P = f η ( k ) is an H η -sum of the non-empty partial orders P i,a . By definition of H η we have that P /greaterorequalslant i is an a ( f i )-sum of the P i,u in position u ∈ a η i , and P &gt;i in position s i . We know that a ( f i ) is indecomposable since 〈 η, k 〉 was maximal. So since I ∩ P i = ∅ , we can apply Lemma 7.28 to see that either | a ( f i ) | /lessorequalslant 2 or P /greaterorequalslant i ⊆ I .

Lemma 7.32. Let I be an interval of P , then there are j 0 , j 1 ∈ r and an X ⊆ P j 1 either empty or an interval of P j 1 such that I = P /greaterorequalslant j 0 or I = ( P /greaterorequalslant j 0 \ P /greaterorequalslant j 1 ) ∪ X.

Proof. If for any i ∈ r we have | a ( f i ) | = 1 then f i = ∑ 1 which makes no difference to the sum over H η , so without loss of generality we assume this does not occur.

Let j 0 = inf { i ∈ r | I ∩ P i = ∅} , and j 1 = sup { i ∈ r | I ∩ P i = ∅} , then j 0 , j 1 ∈ r by Lemma 7.8. Suppose that for some n ∈ r with j 0 /lessorequalslant n &lt; j 1 we have | a ( f n ) | /greaterorequalslant 2. We claim that in this case I = P /greaterorequalslant i 0 . For each such n we have by Lemma 7.31 that P /greaterorequalslant n ⊆ I . Therefore for all m ∈ r with j 0 /lessorequalslant m&lt;n we have again by Lemma 7.31 that P m ⊆ I , hence I = P /greaterorequalslant j 0 by definition of j 0 .

/negationslash

/negationslash

/negationslash

/negationslash

Suppose now that the only n ∈ r such that j 0 /lessorequalslant n /lessorequalslant j 1 with | a ( f n ) | &gt; 2 is n = j 1 , or that no such n exists. Let X = I ∩ P j 1 , then X is either empty or an interval of P j 1 . If j 0 = j 1 we are done, otherwise for each j 0 /lessorequalslant m&lt;j 1 we have | a ( f n ) | = 2. We either have P j 1 = ∅ or P j 1 = ∅ in which case by definition of j 1 there must be some m ′ ∈ r with m &lt; m &lt; j ′ 1 and P m ′ = ∅ . So in either case we can apply Lemma 7.31 to see that P m ⊆ I . Using the definition of j 0 we also have that I ⊆ P /greaterorequalslant j 0 . Therefore we have shown that I = ( P /greaterorequalslant j 0 \ P /greaterorequalslant j 1 ) ∪ X as required. /square

Lemma 7.33. Suppose that ∀ i ∈ r and ∀ a ∈ a η i , every chain of intervals of P i,a under ⊇ has order type in L . Then every chain of intervals of f η ( k ) under ⊇ has order type in L .

Proof. Let 〈 J α : α ∈ σ 〉 be a chain of intervals of P under ⊇ . If for some α ∈ σ we have some j α ∈ r with P /greaterorequalslant j α = J α then for every β /lessorequalslant α , by Lemma 7.32 and since J β ⊇ J α , there must be some j β with J β = P /greaterorequalslant j β . Hence the order type of the chain 〈 J β : β /lessorequalslant α 〉 must be a subset of the order type of { i ∈ r | j /lessorequalslant j α } , and hence this order type is in L . Therefore since L is closed under finite sums, it only remains to show that the final segment

/negationslash

$$F = \{ J _ { \gamma } \, | \, ( \forall i \in r ), J _ { \gamma } \neq P _ { \geqslant i } \}$$

has order type in L under ⊇ .

′ such that

$$\dots \dots \dots \dots \dots \dots = \cdot \\ \text{Let $J_{\gamma} \in F$, then by Lemma $7.32$, there are some $j_{\gamma}, j_{\gamma}^{\prime} \in r$ and $X$ an interval of $P_{j_{\gamma}}$ such that} \\ J_{\gamma} = ( P _ { \geqslant j_{\gamma } } \, \langle P _ { \geqslant j_{\gamma } ^ { \prime } } ) \cup X _ { \gamma } \\ \cdot \cdot \cdot$$

Now if γ &lt; υ then j γ /lessorequalslant j υ , j ′ γ /greaterorequalslant j ′ υ and X γ ⊇ X υ , and if j ′ γ &gt; j ′ υ then X υ ⊆ J γ . Let F δ = { J γ ∈ F | j γ = j δ } . Then ot( F ) is an ot( { j δ | δ ∈ σ } )-sum of the ot( F δ ). But { j δ | δ ∈ σ } ⊆ r hence this subset has order type in L . So it remains only to show that each ot( F δ ) is in L . We also have that each ot( F δ ) is an ot( { j ′ τ | τ ∈ σ, j τ = j δ } )-sum of the order types of F δ,τ = { X λ | λ ∈ σ, j λ = j δ , j ′ λ = j ′ τ } . But { j ′ τ | τ ∈ σ, j τ = j δ } ⊆ r and F δ,τ is a chain of intervals of P τ under ⊇ , whence both are in L and thus ot( F δ ) ∈ L which gives the lemma. /square

Lemma 7.34. Suppose that for any indecomposable partial order y and any i ∈ r and a ∈ a η i we have that y /lessorequalslant P i,a -→ y ∈ P . Then for any indecomposable y ′ we have y ′ /lessorequalslant f η ( k ) -→ y ′ ∈ P .

Proof. Since 〈 η, k 〉 was maximal for P we know that for each i ∈ r we have a ( f i ) is indecomposable. Now any subset A of H η = ⊔ i ∈ r a η i that contains points of a η i and at least two points of ⋃ j&gt;i a η j is such that A ∩ ⋃ j&gt;i a η j is an interval with at least two points inside. So here A cannot be indecomposable. Thus any indecomposable subset I of H η is a subset of a η i /unionsq a η j for some i, j ∈ r with i &lt; j , moreover, | I ∩ a η j | /lessorequalslant 1. So I has the same order type as a subset of a ( f i ), which shows that I has order type in P .

Thus if we take a subset A ⊆ P with at least two points inside a single P i,a and at least one point not in P i,a then A ∩ P i,a is an interval which contradicts that A is indecomposable. We know that P is an H η -sum of the partial orders P i,a . So let J be an indecomposable subset J of the sum P . Then either J is entirely contained within some P i,a and hence J has order type in P ; or J contains at most one point of each of the P i,a that it intersects, and hence has the same order type as an indecomposable order of H η . Hence by the previous paragraph J has order type in P , which completes the proof. /square

We are now ready to prove the following generalisation of Hausdorff's famous theorem on scattered linear orders (Theorem 2.32).

## Theorem 7.35. S L P ( Q ′ ) = ˜ C 0 .

Proof. First we claim that ˜ C 0 ⊆ S L P ( Q ′ ). By Lemma 7.27, we have that ˜ C 0 satisfies (iii) of Definition 7.10. We will show (i) and (ii) by induction on the rank of x ∈ C ˜ . 0 If x has rank 0 then x is just a single point and so satisfies (i) and (ii) since both P and L contained 1. Now suppose that any y ∈ Q &lt;α satisfies (i) and (ii). Then if x ∈ Q α , we have that x = f η ( k ) where k ∈ dom( f η ) &lt;α . Hence by Lemma 7.34 we have that x satisfies (i), and by Lemma 7.33 we have that x satisfies (ii). So indeed we have ˜ C 0 ⊆ S L P ( Q ).

We will now show S L P ( Q ′ ) ⊆ C ˜ . 0 Suppose we have some non-empty Q ′ -coloured partial order x / ∈ C ˜ . 0 We claim that either (i), (ii) or (iii) fails for x . Suppose that (i) and (ii) hold, we will show that (iii) fails. By Lemma 7.15 we have that any decomposition tree T for x embeds 2 &lt;ω . So let T be a decomposition tree for x and B ⊆ T be a copy of 2 &lt;ω . Then we can either find a copy of A inside B , or below some point of B there is no point coloured by ∑ A 2 , and hence below this point there is a copy of Q . Thus by Lemmas 7.19 and 7.21 we have that either B + /lessorequalslant T , B -/lessorequalslant T or C /lessorequalslant T . Hence by Lemma 7.22 either 2 &lt;ω , -2 &lt;ω or 2 &lt;ω ⊥ embeds into x . Thus x fails (iii), and x / ∈ S L P ( Q ′ ), which gives the theorem. /square

## Corollary 7.36. M L P ( Q ′ ) = ˜ C .

Proof. We have that M L P ( Q ′ ) is the class containing S L P ( Q ′ ) and countable unions of increasing sequences and ˜ is the class containing C ˜ C 0 and countable unions of limiting sequences. The result then follows from Theorem 7.35, considering Remark 7.11. /square

Theorem 7.37. If L and P are well-behaved, then M L P is well-behaved.

Proof. By Corollary 7.36 we have that M L P ( Q ′ ) = ˜ . C Suppose there is a bad M L P ( Q )-array; so by theorems 6.12 and 5.12, we have a witnessing bad Q -array. Hence M L P is well-behaved. /square

## 8. Corollaries and conclusions

We now present some applications of Theorem 7.37.

Theorem 8.1 (Kˇ r´ ˇ [3]) ız . M , the class of σ -scattered linear orders is well-behaved.

Proof. Set L = On ∪ On , set ∗ P = 1 C { , 2 } . Then L = S by Theorem 2.32. L is well-behaved, by theorems 2.8 and 2.22. We also have that P is well-behaved by Lemma 2.17. Hence by Theorem 7.37 we have that M L P is well-behaved.

We claim that M L P = M . Recall the definition of S L P , 7.10. Let X ∈ S , then clearly X satisfies (i) and (iii) since if either failed then X would contain two incomparable elements. A chain of intervals of X does not embed Q , otherwise X would embed Q . Hence every chain of intervals of X under ⊇ has scattered order type. If we take the chain of intervals of X under ⊇ consisting of final segments, this chain has order type precisely the same as X . So we have that S L P = S which implies that M L P = M , and therefore M is well-behaved. /square

Definition 8.2. Let P be a set of countable indecomposable partial orders. Then C P is the class of countable partial orders such that every indecomposable subset is in P .

Theorem 8.3. If C ⊆ L then C P ⊆ M L P .

Proof. Suppose that C ⊆ L . Let X ∈ C P , we claim that X ∈ M L P . Fix an enumeration of X in order type ω , so that X = { x n : n ∈ ω } . (If | X &lt; | ℵ 0 then the argument is essentially the same.) We will write X as the countable union of some limiting sequence ( X n n ) ∈ ω that we will define.

Let X 〈〉 = X , I 0 = {〈〉} and suppose for some sequence /vector t of elements of ⋃ L × ⋃ P we have defined some X /vector t ⊆ X . When | X /vector t | &gt; 1, pick a maximal chain 〈 I /vector t i : i ∈ r /vector t 〉 of intervals of X /vector t that contains { x n } , where n is least such that x n ∈ X /vector t . Since X /vector t ⊆ X we have that r /vector t ∈ L . For each i ∈ r /vector t , let D /vector t i be the set of unions of maximal chains of intervals of I /vector t i that do not contain I /vector t i .

/negationslash

Now let f /vector t i = ∑ a i and s /vector t i be the point of a i that was also contained in ⋃ j&gt;i I /vector t j ∈ D /vector t i . We set η /vector ( ) = t 〈〈 f , s /vector t i /vector t i 〉 : i ∈ r /vector t 〉 . For i ∈ r /vector t and u ∈ a η i ⊆ a i , let X /slurabove /vector t 〈 i,u 〉 be the element of D /vector t i that contains the point u . Then if k /vector t = 〈 X /slurabove /vector t 〈 i,u 〉 : i ∈ r , u /vector t ∈ a η i 〉 we have by construction that 〈 η, k /vector t 〉 is maximal for X /vector t .

We claim that a i = I / /vector t i D /vector t i is indecomposable. If Z = a i is a non-singleton interval of a i , then let Z ′ ⊆ I /vector t i be the union of the sets of D /vector t i that contain points of Z . Then Z ′ is an interval of I /vector t i not equal to I /vector t i , and not in any of the maximal chains used to form D /vector t i ; this is a contradiction which gives the claim. Now, we see that a i is an indecomposable subset of X and thus a i ∈ P .

For m ∈ ω we let I m +1 = I m ∪ { /vector t /slurabove 〈 i, u 〉 | /vector t ∈ I m , i ∈ r , u /vector t ∈ a , η i | X /vector t | &gt; 1 } , D m be the set of leaves of I m and F m = { η /vector ( ) t | /vector t ∈ I m \ D m } . Then F m is an admissible composition set and I m is a set of position sequences for F m . Now let d m = 〈 d /vector p m : /vector p ∈ D m 〉 ∈ dom( f F m ) be such that each d /vector p m is a single point, coloured either by -∞ if | X /vector p | &gt; 1, and coloured by c X /vector p ( x ) when X /vector p = { x } . Now define X m = g F m ( d m ), so that by construction ( X m m ω ) ∈ is a limiting sequence. Moreover, for each m ∈ ω we can consider the underlying set of each X m as a subset of the underlying set of X . Note also that the underling set of X m contains the point x m , and since the relevant chain of intervals contained { x m } the colour of this point in X m will be the same as from X . Thus the limit of ( X m m ω ) ∈ is precisely X , so that X ∈ M L P as required. /square

Corollary 8.4. If P is a well-behaved set of countable indecomposable partial orders, then C P is well-behaved. 15

Proof. By Theorems 8.1, 8.3 and 7.37.

$$\Box$$

Remark 8.5 . If P is a set of finite partial orders then let ˜ be the class of countable partial orders P whose every finite restriction is in P . In [5], Pouzet asked: if P preserves bqo, then is ˜ P bqo? As we have seen, well-behaved is a more useful concept than preserving bqo, so we modify the

15 This result was obtained independently by Christian Delhomme in as yet unpublished work. The author thanks him for his private communication.

Figure 12. An antichain of ⋃ n ∈ ω I n (A ). 2

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0315v3-figure-d115117b-6ca4-4f07-a5f0-b90b906b884f.jpg)

question to if P well-behaved. Corollary 8.4 brings us closer to a result of this kind, however fails to account for possible infinite indecomposable subsets of orders in ˜ . P If we could prove that for any infinite indecomposable order X the set of finite indecomposable subsets of X is not well-behaved, then we would answer this version of Pouzet's question positively.

Definition 8.6. For n ∈ ω let I n denote the set of indecomposable partial orders whose cardinality is at most n .

Theorem 8.7. For any n ∈ ω , the class M M I n is well-behaved.

Proof. I n is a finite set of finite partial orders so by Lemma 2.17, is well-behaved. Furthermore, M is well-behaved by Theorem 8.1, so using Theorem 7.37 completes the proof. /square

Corollary 8.8. For any n ∈ ω , the class C I n is well-behaved.

Proof. By Theorems 8.3 and 8.7.

$$\Box$$

Note that ⋃ n ∈ ω I n (A ) contains an antichain as in Figure 12, and as described by Pouzet in 2 [5]. Hence ⋃ n ∈ ω I n does not preserve bqo and is certainly not well-behaved. Thus Theorem 8.7 is maximal in some sense. In order to improve this result we would like to know the answers to questions such as:

- (1) Is there consistently a well-behaved class of linear orders larger than M ? E.g. is the class of Aronszajn lines from [16] well-behaved under PFA?
- (2) Is there an infinite well-behaved class of indecomposable partial orders?
- (3) Is there an infinite indecomposable partial order P such that { P } is well-behaved?

A positive answer to any of these questions would immediately improve Theorem 8.7.

## Acknowledgements

The author thanks Mirna Dˇ zamonja, Yann Pequignot and Rapha¨ el Carroy for extremely helpful discussions and remarks.

## References

- [1] S. Thomass´ e, On better-quasi-ordering countable series-parallel orders . Trans. Amer. Math. Soc., Vol. 352, 6, (1999), pp 2491-2505.
- [2] E. Corominas, On better-quasi-ordering countable countable trees . Discrete Mathematics 53, North-Holland, (1985), pp 35-53.
- [3] I. Kˇ r ´ ˇ, ız Proving a witness lemma in better-quasiordering theory: the method of 'extensions' . Math. Proc. Camb. Phil. Soc. 106, (1989), pp 253-262.
- [4] R. Thomas, Well-quasi-ordering infinite graphs with forbidden finite planar minor . Trans. Amer. Math. Soc., Vol. 312, 1, (1989), pp 279-313.
- [5] M. Pouzet, Applications of well-quasi-ordering and better-quasi-ordering . Graphs and Orders, (I. Rival ed.), D. Reidel Publishing Company, (1985), pp 503-519.
- [6] J. B. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept . J. Comb. Th. (A) 13, (1972), pp 297-306.
- [7] F. van Engelen, A. W. Miller and J. Steel, Rigid Borel sets and better quasiorder theory . Contemp. Math. 65, (1987), pp 119-222.

- [8] A. Louveau and J. Saint-Raymond, On the quasi-ordering of borel linear orders under embeddability . J. Symbolic Logic, Vol. 55, 2 (1990), pp 449-896.
- [9] C. St. J.A. Nash-Williams, On well-quasi-ordering infinite trees . Proc. Camb. Phil. Soc. 61, (1965), pp 697-720.
- [10] , On well-quasi-ordering transfinite sequences . Proc. Camb. Phil. Soc. 64, (1968), 273-290.
- [11] S. G. Simpson, BQO theory and Fra¨ ıss´'s conjecture e . Chapter 9 of Recursive aspects of descriptive set theory, Oxford Univ. Press, New York, (1985), pp. 124-138.
- [12] R. Laver, On Fra¨ ıss´'s e order type conjecture . Ann. of Math. 93, (1971), pp 89-111.
- [13] , Better-quasi-orderings and a class of trees . Studies in Foundations and Combinatorics, Adv. in Math. Supplementary Studies 1 (1978), pp 31-48.
- [14] F. Hausdorff, Grundz¨ uge einer Theorie der geordneten Mengen . Math. Ann. 65 (1908), pp 435-505.
- [15] F. Galvin and K. Prikry, Borel sets and Ramsey's theorem . J. Symb. Logic 38 (1973), pp 193-198.
- [16] C. Martinez-Ranero, Well-quasi-ordering Aronszajn lines . Fund. Math. 213 (2011), pp 197-211.

School of Mathematics, University of East Anglia, Norwich Research Park, Norwich, NR4 7TJ,

UK

E-mail address : g.mckay@uea.ac.uk
Gregory McKay
On better-quasi-ordering classes of partial orders
We provide a method of constructing better-quasi-orders by generalising a
technique for constructing operator algebras that was developed by Pouzet. We
then generalise the notion of $\sigma$-scattered to partial orders, and use our
method to prove that the class of $\sigma$-scattered partial orders is
better-quasi-ordered under embeddability. This generalises theorems of Laver,
Corominas and Thomass\'{e} regarding $\sigma$-scattered linear orders and
trees, countable forests and N-free partial orders respectively. In particular,
a class of countable partial orders is better-quasi-ordered whenever the class
of indecomposable subsets of its members satisfies a natural strengthening of
better-quasi-order.