Andreas Baudisch
email: baudisch@mathematik.hu-berlin.de

Amador Martin-Pizarro

Martin Ziegler
email: ziegler@uni-freiburg.de

Martin Ziegler Ample

Hierarchy 2013 Hal- 00863214v2

AMPLE HIERARCHY

Keywords: Mathematics Subject Classification, Primary: 03C45, Key words and phrases, Model Theory, CM-triviality, 1

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Morley's renowned categoricity theorem [START_REF] Morley | Categoricity in power[END_REF] described any model of an uncountably categorical theory in terms of basic foundational bricks, socalled strongly minimal sets. A long-standing conjecture aimed to understand the geometry of a strongly minimal set in terms of three archetypal examples: a trivial set, a vector space over a division ring and an irreducible curve over an algebraically closed field. The conjecture was proven wrong [START_REF] Hrushovski | A new strongly minimal set[END_REF] by obtaining in a clever fashion a non-trivial strongly minimal set which does not interpret a group. In particular, Hrushovski's new strongly minimal set does not interpret any infinite field, which follows from the fact that the obtained structure is CM-trivial. Recall that CM-triviality is a generalisation of 1-basedness and it prohibits a certain point-line-plane configuration which is present in Euclidian geometry. The simplest example of a CMtrivial theory that is not 1-based is the free pseudoplane: an infinite forest with infinite branching at every node. CM-trivial theories are rather rigid and in particular definable groups of finite Morley rank are nilpotent-byfinite [START_REF] Pillay | The geometry of forking and groups of finite Morley rank[END_REF].

Taking the pseudoplane as a guideline, a non CM-trivial ω-stable theory which does not interpret an infinite field was constructed in a pure combinatorial way [START_REF] Baudisch | A free pseudospace[END_REF]. The structure so obtained is of infinite rank, and it remains still open whether the construction could be modified to produce one of finite Morley rank. In [START_REF] Pillay | A note on CM-triviality and the geometry of forking[END_REF]4] a whole hierarchy of new geometries (called n-ample) was exhibited, infinite fields being at the top of the classfication. Evans suggested that his construction could be used to show that the hierarchy is strict, though no proof was given.

The goal of this article is to generalise the aforementioned construction to higher dimensions in order to show that the N -dimensional pseudospace is N -ample yet not (N + 1)-ample, showing therefore that the ample hierarchy is proper. After a thorough study of the pseudospace, we were able to simplify the combinatorics behind the original construction. In particular, we characterise non-forking and give explicit descriptions of canonical basis of finitary types over certain substructures. Moreover, we show that the theory of the pseudospace has weak elimination of imaginaries.

Tent obtained earlier the same result [START_REF] Tent | The free pseudospace is n-ample, but not (n + 1)-ample[END_REF] independently; however, we present a different construction and axiomatisation of the free pseudospace for higher dimensions. We are indebted to her as she pointed out that the prime model of the 2-dimensional free pseudospace could be seen as a building. We would like to express our gratitude to Yoneda for a careful reading of a first version of this work. We thank the referee for helpful remarks.

Ample concepts

Throughout this article, we assume a certain knowledge of stability theory, in particular nonforking and canonical bases. We refer the reader to [START_REF] Tent | A course in Model Theory[END_REF] for a gentle and careful explanation of these notions. All throughout this article, we work inside a sufficiently saturated model of a first-order theory T and all sets are small subsets of it.

We first state a fact, which we believe is common knowledge, that will be used repeatedly.

Fact 2.1. Given a stable theory T and sets A, B, C and D, if acl eq (B) ∩ acl eq (C) = acl eq (A) and D | A BC, then acl eq (DB) ∩ acl eq (DC) = acl eq (DA).

Proof. In order to show that acl eq (DB) ∩ acl eq (DC) ⊂ acl eq (DA), pick an element e in acl eq (DB)∩acl eq (DC). The independence D | A BC yields that Cb(De/BC) lies in acl eq (B)∩acl eq (C) = acl eq (A), so e lies in acl eq (DA).

Recall now the definition of CM-triviality and n-ampleness [START_REF] Pillay | A note on CM-triviality and the geometry of forking[END_REF]4]. Definition 2.2. Let T be a stable theory.

The theory T is 1-based if for every pair of algebraically closed (in T eq ) subsets A ⊂ B and every real tuple c, we have that Cb(c/A) is algebraic over Cb(c/B). Equivalently, for every algebraically closed set A (in T eq ) and every real tuple c, the canonical base Cb(c/A) is algebraic over c.

The theory T is CM-trivial if for every pair of algebraically closed (in T eq ) subsets A ⊂ B and every real tuple c, if acl eq (Ac) ∩ B = A, then Cb(c/A) is algebraic over Cb(c/B).

The theory T is called n-ample if there are n + 1 real tuples satisfying the following conditions (possibly working over parameters):

(1) acl eq (a 0 , . . . , a i )∩acl eq (a 0 , . . . , a i-1 , a i+1 ) = acl eq (a 0 , . . . , a i-1 ) for every 0 ≤ i < n, (2) a i+1 | a i a 0 , . . . , a i-1 for every 1 ≤ i < n, (3) a n | a 0 . By inductively choosing models M i ⊃ a i such that

M i | a i
M 0 , . . . , M i-1 , a i+1 , . . . , a n , Fact 2.1 allows us to deduce the following, which was already remarked in [START_REF] Pillay | The geometry of forking and groups of finite Morley rank[END_REF]Corollary 2.5] in the case of CM-triviality.

Remark 2.3. In the definition of n-ampleness, we can replace all tuples by models.

Corollary 2.4. A stable theory T is n-ample if and only if T eq is.

Clearly, every 1-based theory is CM-trivial. Furthermore, a theory is 1based if and only if it is not 1-ample; it is CM-trivial if and only if it is not 2-ample [START_REF] Pillay | A note on CM-triviality and the geometry of forking[END_REF]. Also, to be n-ample implies (n-1)-ampleness: by construction, if a 0 , . . . , a n witness that T is n-ample, the sequence a 0 , . . . , a n-1 witnesses that T is (n -1)-ample. In order to see this, we need only show that In order to prove that the N -dimensional free pseudospace is not (N +1)ample, we need only consider some of the consequences from the conditions listed above. Therefore, we will isolate such conditions for Section 8.

Remark 2.5. If the (possibly infinite) tuples a 0 , . . . , a n witness that T is n-ample, they satisfy the following conditions:

(a) a n | a i a i-1 for every 1 ≤ i < n. (b) acl eq (a i , a i+1 ) ∩ acl eq (a i , a n ) = acl eq (a i ) for every 0 ≤ i < n -1. (c) a n | acl eq (a i )∩acl eq (a i+1 ) a i for every 0 ≤ i < n -1.

If the tuples a 0 , . . . , a n witness that T is n-ample over some set of parameters A, by adding all elements of A to each of the tuples, then we may assume that all the conditions hold with A = ∅.

Proof. Let a 0 , . . . , a n witness that T is n-ample.

First, note that acl eq (a 1 )∩acl eq (a 2 ) ⊂ acl eq (a 0 ) by property [START_REF] Baudisch | An alternative approach to the free pseudospace[END_REF]. For i ≤ 2, the set acl eq (a i ) ∩ acl eq (a i+1 ) is contained in acl eq (a i ) ∩ acl eq (a 0 , . . . , a i-1 ) again by [START_REF] Baudisch | An alternative approach to the free pseudospace[END_REF]. Now, condition [START_REF] Baudisch | A free pseudospace[END_REF] implies that acl eq (a i ) ∩ acl eq (a 0 , . . . , a i-1 ) is a subset of acl eq (a i ) ∩ acl eq (a i-1 ). By induction, we have that acl eq (a i ) ∩ acl eq (a i+1 ) ⊂ acl eq (a 0 ).

The independence a n | a i a i-1 follows directly from property (2) and yields (a). Since a n | a i+2 a 0 , . . . , a i+1 , we have that

a n | a i ,a i+2 a i+1 .
Hence, acl eq (a i , a i+1 ) ∩ acl eq (a i , a n ) ⊂ acl eq (a i , a i+1 ) ∩ acl eq (a i , a i+2 ), and thus in acl eq (a 0 , . . . , a i ) by [START_REF] Baudisch | An alternative approach to the free pseudospace[END_REF]. Since

a i+1 | a i a 0 , . . . , a i-1 ,
we get (b). If

a n |
acl eq (a i )∩acl eq (a i+1 ) a i for some 0 ≤ i < n -1, then i > 0 by [START_REF] Blossier | On variants of CMtriviality[END_REF]. Since a n | a i a 0 , . . . , a i-1 , transitivity gives that a n | acl eq (a i )∩acl eq (a i+1 ) a 0 , . . . , a i .

Thus, we obtain the independence a n | a 0 a 0 , . . . , a i and in particular a n | a 0 a 1 . Since a n | a 1 a 0 by [START_REF] Baudisch | A free pseudospace[END_REF] and acl eq (a 0 ) ∩ acl eq (a 1 ) = ∅ by [START_REF] Baudisch | An alternative approach to the free pseudospace[END_REF], this implies that a n | a 0 , which contradicts [START_REF] Blossier | On variants of CMtriviality[END_REF].

In [START_REF] Blossier | On variants of CMtriviality[END_REF], a weakening of CM-triviality was introduced, following the spirit of [START_REF] Kowalski | Quantifier elimination for algebraic D-groups[END_REF], where some of the consequences for definable groups in 1-based theories were extended to type-definable groups in theories with the Canonical Base Property. For the purpose of this article, we extend the definition to all values of n. However, we do not know of any definability properties for groups that may follow from the general definition.

Let Σ be an ∅-invariant family of partial types. Recall that a type p over A is internal to Σ, or Σ-internal, if for every realisation a of p there is some superset B ⊃ A with a | A B, and realisations b 1 , . . . , b r of types in Σ based on B such that a is definable over B, b 1 , . . . , b r . If we replace definable by algebraic, then we say that p is almost internal to Σ or almost Σ-internal. Definition 2.6. A stable theory T is called n-tight (possibly working over parameters) with respect to the family Σ if, whenever there are n + 1 real tuples a 0 , . . . , a n satisfying the following conditions:

(1) acl eq (a 0 , . . . , a i )∩acl eq (a 0 , . . . , a i-1 , a i+1 ) = acl eq (a 0 , . . . , a i-1 ) for every 0 ≤ i < n.

(2) a i+1 | a i a 0 , . . . , a i-1 for every 1 ≤ i < n, then Cb(a n /a 0 ) is almost Σ-internal over a 1 .

Remark 2.7. As before, we may assume that all tuples are models. In particular, the theory T is n-tight if and only if T eq is. A theory T is 2-tight with respect to Σ if for every pair of sets A ⊂ B and every tuple c, if acl eq (Ac) ∩ acl eq (B) = acl eq (A), then Cb(c/A) is almost Σinternal over Cb(c/B) . In particular, this notion agrees with [START_REF] Blossier | On variants of CMtriviality[END_REF]Definition 3.1] If T is not n-ample, it is n-tight with respect to any family Σ. Furthermore, if T is (n -1)-tight, it is n-tight.

Proof. The equivalence between both definitions is a standard reformulation by setting a 0 = A, a 1 = Cb(c/B) and a 2 = c for one direction (working over acl eq (a 0 ) ∩ acl eq (a 1 )), and A = a 0 , B = a 0 ∪ Cb(a 2 /a 1 ) and c = a 2 for the other.

If T is not n-ample, it is clearly n-tight, since algebraic types are always almost Σ-internal for any Σ.

Suppose now that T is (n -1)-tight, and consider n + 1 tuples a 0 , . . . , a n witnessing (1) and [START_REF] Baudisch | A free pseudospace[END_REF]. So do a 0 , . . . , a n-1 as well. Hence, the canonical base Cb(a n-1 /a 0 ) is almost Σ-internal over a 1 .

Since a n | a n-1 a 0 , it follows by transitivity that Cb(a n /a 0 ) is algebraic over Cb(a n-1 /a 0 ) and therefore the former is also almost Σ-internal over a 1 .

In this article, we will show that the free N -dimensional pseudospace is N -ample yet not (N + 1)-ample. Furthermore, if N ≥ 2, it is N -tight with respect to the family of Lascar rank 1 types.

Fraïssé Limits

The results in this section were obtained by the third author in an unpublished note [START_REF] Ziegler | Strong Fraïssé limits[END_REF] (in a slightly more general context). We include them here for the sake of completeness.

Throughout this section, let K denote a class of structures closed under isomorphisms in a fixed language L. We assume that the empty structure 0 is in K. Furthermore, a class S of embeddings between elements of K is given, called strong embeddings, containing all isomorphisms and closed under composition. We also assume that the empty map 0 → A is in S for every A ∈ K.

We call a substructure A of B strong if the inclusion map is in S. We denote this by A ≤ B. Definition 3.1. An increasing chain of strong substructures {A i } i<ω is rich if, for all i < ω and all strong f : A i → B, there is some i ≤ j < ω and a strong g : B → A j such that g • f : A i → A j is the inclusion map.

A Fraïssé limit of (K, S) is the union of a rich sequence.

Theorem 3.2. Suppose (K, S) satisfies the following conditions:

(1) There are at most countably many isomorphism types in K.

(2) For each A and B in K, there are at most countably many strong embeddings A → B. (3) K has the amalgamation property with respect to strong embeddings.

Then rich sequences exist and all Fraïssé limits are isomorphic.

The existence of rich sequences is easy to show. The uniqueness will follow from the next lemma. For that, let us say that A is r-strong in a Fraïssé limit M , denoted by A ≤ r M , if M is the union of a rich sequence starting with A. Proof. We observe first that if A 0 ≤ A 1 ≤ . . . is a rich sequence and B ≤ A 0 , then the sequence B ≤ A 0 ≤ A 1 ≤ . . . is also rich. This implies (a). For (b), choose a rich sequence A = A 0 ≤ A 1 ≤ . . . with union M . If B ≥ A is given, there exists, by richness, some index j and B ≤ A j isomorphic to B over A.

The set B is r-strong in M , since the subsequence B ≤ A j ≤ A j+1 ≤ . . . is again rich.

The lemma implies that Fraïssé limits are isomorphic by a standard backand-forth argument: given two Fraïssé limits M and M with rich sequences

A 0 ≤ A 1 ≤ . . . and A 0 ≤ A 1 ≤ . . . , consider an isomorphism B → B , where B is strong in A i and B is strong in A i .
Then there is an extension to an isomorphism C → C such that A i ≤ C ≤ A j and A i ≤ C ≤ A j for some j > i. This results in an ascending sequence of isomorphisms whose union yields an isomorphism M → M . The convention that S is contains all isomorphisms and is closed under composition represents no obstacle, thanks to the following easy remark. Remark 3.5. Let S be a set of embeddings between elements of K with the amalgamation property. The closure of S together with all isomorphisms under composition has again the amalgamation property.

The free pseudospace

In this section, we will construct and axiomatise the N -dimensional free pseudospace, which is a generalisation of [START_REF] Baudisch | A free pseudospace[END_REF], based on the free pseudoplane. An alternative axiomatisation, in terms of flags, may be found in [START_REF] Baudisch | An alternative approach to the free pseudospace[END_REF].

Remark 4.1. Recall that the (free) pseudoplane is a bicolored graph with infinite branching and no loops. These elementary properties describe a complete ω-stable theory of Morley rank ω.

Quantifier elimination is obtained after adding the collection of binary predicates:

d n (x, y) ⇐⇒ the distance between x and y is exactly n.

In particular, since there are no loops, the set d 1 (x, a) is strongly minimal. Morley rank for this theory is additive and agrees with Lascar rank. Given the type of an element c over an algebraically closed set A, its canonical base Cb(c/A) is the unique point a in A whose distance to c is smallest possible (or empty if there is no path between c and A). It follows that the theory has weak elimination of imaginaries and is moreover CM -trivial but not 1-based.

The idea behind the construction of the free pseudospace [START_REF] Baudisch | A free pseudospace[END_REF] is to take a free pseudoplane, whose vertices of one color are called planes and vertices of the other are referred to as lines, and on each line put an infinite set of points, such that, for each plane, the lines which are incident with it, together with the points on them form again a free pseudoplane. Nevertheless, the actual construction was rather combinatorial and therefore less intuitive. Instead, our approach consists in building a model out of some basic operations and study the complete theory of such a structure, in order to show that it agrees with the free pseudospace in [START_REF] Baudisch | A free pseudospace[END_REF] for dimension N = 2. Definition 4.2. For N ≥ 1, a colored N -space A is a colored graph with colors (or levels) A 0 ,. . . ,A N such that an element in A i can only be linked to vertices in A i-1 ∪ A i+1 . We will furthermore consider two (invisible) levels A -1 and A N +1 , consisting of a single imaginary element a -1 and a N +1 respectively, which are connected to all vertices in A 0 and A N respectively. Given such a graph A and a subset s of {0, • • • , N }, we set

A s (A) = i∈s A i (A).
Given x and y in A s (A), its distance in A s (A) is denoted by d A s (x, y). Given a colored N -space A and vertices a in A l (A) and b ∈ A r (A), we say that b lies over a (or a lies beneath b) if l < r and there is a path of the form a = a l , a l+1 , . . . , a r = b. Note that a k must be in A k (A). By convention, the point a N +1 lies over all other vertices (including a -1 ) and a -1 lies beneath all other vertices.

With A, a and b as above, we denote by A a the subgraph of A consisting of all the elements of A lying over a. Similarly A b denotes the subgraph of all the elements lying beneath b. The subgraph A b a = (A a ) b consists of all the elements of A lying between a and b, if a lies beneath b.

Observe that, after a suitable renumbering of levels, the subgraph A a becomes a colored (N -l -1)-space, whereas A b becomes a colored (r -1)space and A b a a colored (r -l -2)-space.

Notation. Intervals are assumed to be non-empty If either l s = -1 or r s = N + 1, then a ls lies automatically beneath a rs .

The N -dimensional pseudospace will now be obtained by iterating countably many times all operations α s for s varying over all intervals in [0, N ]. Clearly, we have the following. A strong embedding A → B is an isomorphism of A with a strong subspace of B. Let K ∞ be the class of all finite colored N -spaces A with ∅ ≤ A. By the last remark and Remark 3.5, the class K ∞ has the amalgamation property with respect to strong embeddings . Clearly, there are only countably may isomorphism types in K ∞ and only finitely many maps between two structures of K ∞ . We can consider the subclass K 0 , where by a 0-strong embedding we only allow operations α s , for singleton s. Again, the class K 0 has the amalgamation property.

By Theorem 3.2, we define the following structures: Definition 4.6. Let M N ∞ be the Fraïssé limit of K ∞ with strong embeddings and M N 0 be the Fraïssé limit of K 0 with 0-strong embeddings, starting from a given (fixed) path a 0 -. . . -a N , where a i ∈ A i .

We will drop the superindex N in M N ∞ or M N 0 when they are clear from the context.

In particular, the structure M 2 0 so obtained agrees with the prime model constructed in [START_REF] Baudisch | A free pseudospace[END_REF], as Theorem 4.14 will show.

Remark 4.7. Let p be either 0 or ∞. Consider a in A l (M N p ) and b be in

A r (M N p ) lying over a. Then, (M N p ) a ∼ = M N -l-1 p , (M N p ) b ∼ = M r-1 p , (M N p ) b a ∼ = M r-l-2 p . Furthermore, given -1 ≤ l < r ≤ N + 1, we have that A [l,r] (M N p ) ∼ = M r-l-1 p .
Proof. Given a colored N -space M and corresponding vertices a and b, every operation in M a can be extended to an operation on M . Moreover, if an operation on M has no meaning restricted to M a , then M a does not change.

The other statements can be proved in a similar fashion.

We will now introduce a notion, simply connectedness, which traditionally implies path-connectedness topologically. Despite this abuse of notation, we will use this term since it implies that loops are not punctured (cf. Remark 4.9(2) and Corollary 6.16). Definition 4.8. A colored N -space M is simply connected if, whenever we are given l < r in [-1, N + 1], an interval t ⊂ [l, r], vertices a in A l (M ) beneath b in A r (M ) and x and y in A t (M ) lying between a and b which are t-connected by a path of length k not passing through a nor b, then there is a path in A t (M ) of length at most k connecting x and y such that every vertex in the path lies between a and b.

Note that simply connectedness is an empty condition for l = -1 and r = N + 1. Remark 4.9. Let M be a simply connected connected colored N -space. The following hold:

(1) The subgraph A [l,l+1] (M ) has no closed paths with no repetitions.

(2) In a closed path P in A [l,r] (M ), all elements in P ∩A [l,r) are connected (in A [l,r) (M )). Likewise for the dual statement.

Proof. For (1), set r = N + 1, l = l and take t = [l, l + 1] in the definition of simply connectedness. For (2), given x and y in P ∩ A [l,r) , if they are connected using an arch of P in A [l,r) (M ), there is nothing to prove. Otherwise, replace successively every occurrence of a vertex z in P ∩ A r (M ) ∩ P by a subpath in A [l,r) (M ) connecting the immediate neighbours of z in P .

As the following Lemma shows, simply connectedness is preserved under application of the operations α s 's, Lemma 4.10. Let A be a simply connected colored N -space. If B is obtained from A by applying α s on (a ls , a rs ), then B is simply connected as well.

Proof. By hypothesis, the set B equals A ∪ S B , where S B is the path a ls , b ls+1 , . . . , b rs-1 , a rs .

Let now t ⊂ [l, r] be given, as well as a in A l beneath b in A r and vertices x and y in A t lying between a and b connected by a path P in A t (B) of length k. We consider the following cases:

(a) Both a and b lie in B \ A. Take the direct path between x and y. (b) Both a and b lie in A. We consider the following mutually exclusive subcases: (i) Both x and y lie in A: We can replace all repetitions in P to transform it into a path fully contained in A of length at most k. Since A is simply connected, the result follows. (ii) Both x and y lie in S B . Again, take the direct path between x and y. (iii) Exactly one vertex, say y, lies in A. The path P must contain either a ls or a rs . Suppose that P contains a rs . Hence, we can decompose P into the direct connection (which lies between a and b) from x to a rs and a path P in A t (A) from a rs to y. As A is simply connected, we obtain a path in A t (A) between a and b connecting y and a rs whose length is bounded by the length of P . This yields a path from y to x between a and b of the appropriate length. (c) Exactly one vertex in {a, b} lies in A. Suppose that a lies in A \ B and b lies in S B \ A. In particular, the vertex a lies beneath a ls . Consider the following mutually exclusive cases: (i) Both x and y lie in S B . The direct path between them in S B yields again the result. (ii) Both x and y lie in A: If either x or y equals a ls , then one of them lies over the other and the direct connection between them yields the result. Otherwise, we may assume that both x and y lie beneath a ls . Let Q be the path consisting of the direct connection from x to a ls and from a ls to y. If the path P connecting x and y necessarily passes through a ls , then its length is at least the length of Q and the result follows. Otherwise, since A is simply connected, there is a path connecting x and y of length at most k between a and a ls , and thus, between a and b. (iii) Exactly one, say y, is in A. Then y must lie beneath x and the direct path between them yields the result.

Since the only moment a vertex from A lt ∪ A rt was added was in case (c)(ii), namely a ls (though only if the original path passed through it), a careful analysis of the previous proof yields the following, which corresponds to Axiom (Σ4) in [START_REF] Baudisch | A free pseudospace[END_REF]; though we will not require its full strength.

Corollary 4.11. A colored N -space B with ∅ ≤ B has the following property. Given t = [l t , r t ] ⊂ [l, r], as well as a in A l (B) beneath b in A r (B), vertices x and y in A t (B) lying between a and b and a path in A t (B) of length k connecting them, there is a path P in A t (B) between a and b connecting x and y of length at most k such that all vertices in P with levels A lt ∪ A rt come from the original path.

By iterating Lemma 4.10, we obtain the following: Corollary 4.12. If A is simply connected, then so is every strong extension of A.

The following observation can be easily shown. Lemma 4.13. Let B be obtained from A by applying the operation α s . Then, for every t ⊂ {0, • • • , N } and every x and y in A t (A),

d A t (x, y) = d B t (x, y).
Theorem 4.14 (Axioms). Both Fraïssé limits M ∞ and M 0 have the following elementary properties:

(1) simply connectedness.

(2) Given a finite subset A and a non-empty interval s = (l, r), for any two elements a l and a r in A with a r over a l , there are paths

a l , b l+1 , . . . , b r-1 , a r such that the s-distance of b i to A s (A) is arbitrarily large. In partic- ular, if s = {i}, there is a new vertex b i not contained in A.
Proof. (1): This follows from Corollary 4.12.

(2): After enlarging A, we may assume that A ≤ M ∞ . One single application of α s on (a l , a r ) yields that s-distance of b i to A is infinite and remains so at the end of the construction by Lemma 4.13.

If we are considering M 0 , we may assume as well that A ≤ M 0 . Furthermore, we may suppose that in order to build up M 0 from A, each of the operations α i , for i in s, was applied k many times consecutively on each of the new vertices in A i+1 and A i-1 between a l and a r . Lemma 4.13 yields now the desired result. where a i belongs to A i (M ) and they form a path.

A set D of a colored N -space M is complete if every point in D is contained in a flag in D.

Observe that, if D satisfies Axiom (2), it is complete. Definition 4.17. A subset D of a colored N -space M is nice it satisfies the following conditions:

(1) For any two (possibly imaginary) points a and b in D,

D b a = D ∩ M b a . (2
) for all intervals t ⊂ {0, . . . , N } and all x and y in A t (D), (2) for all intervals t ⊂ {0, . . . , N } and all x and y in A t (D),

d M t (x, y) < ∞ ⇒ d D t (x, y) < ∞. A set D is wunderbar in M if it
d M t (x, y) = d D t (x, y).
Clearly, wunderbar sets are nice. As an application of the operation α s on A does not yield connections between the points of A unless there was already one, the following result follows immediately from Lemma 4.13. Proof. Since D b a = D ∩ M b a for any a and b in D, the first condition of niceness holds for D ar a l . For the second condition, we may assume that a l = -1 by Remark 4.7. Let t ⊂ (-1, r] be an interval and vertices x and y in A t (D) beneath a r . We need only show that, if x and y are connected in A t (D), then they are connected in A t (D) beneath a r . Let P be a path in A t (D) connecting x and y, but not necessarily running beneath a r . We call a vertex in P avoidable if it does not lie beneath a r . Let A n be the largest level containing an avoidable vertex in P . Let m be the number of avoidable vertices in P of level n. Choose P such that the pair (n, m) is minimal for the lexicographical order.

Given an avoidable vertex b in A n ∩ P , denote by a 1 in A l 1 the first nonavoidable vertex in P between b and x. Likewise, let a 2 in A l 2 be the first non-avoidable vertex in P between b and y. Note that l 1 and l 2 are both smaller than n, by maximality of n. Furthermore, since every avoidable direct neighbour of a non-avoidable vertex lies necessarily in a larger level, by definition, it follows that both l 1 and l 2 are strictly smaller than n. Hence, the subpath P of P between a 1 and a 2 yields a connection in A t , where t = t ∩ (-1, n] not passing through a r . As M is simply connected, there is a path Q (with no repetitions) connecting a 1 and a 2 running beneath a r . Now, the paths Q and P have only a 1 and a 2 as common vertices and they induce a loop. Remark 4.9(2) yields that a 1 and a 2 are t 1 -connected, where t 1 = t ∩ (-1, n). Since D is nice, there is also a t 1 -connection R in D. Replacing P by R, we have a path whose avoidable vertices are still contained in (-1, n] and with fewer avoidable vertices of level n. Minimality of (n, m) shows that this path runs beneath a r , as desired.

Corollary 4.20. Let D be nice in a colored N -space M . If M is simply connected, then so is D. Lemma 4.21. Let A be a nice subset of a simply connected colored N -space M . Consider a non-empty interval s = (l, r) and two vertices a ls in A ls (A) and a rs in A rs (A) such that a rs lies over a ls . Let B ⊂ M be an extension of A given by new vertices b ls+1 , . . . , b rs-1 such that the sequence

a l , b l+1 , . . . , b r-1 , a r
is a path. The following are equivalent: (a) The set B is nice and obtained from A by applying α s on (a ls , a rs ). (b) For some (equivalently, all) i in s, we have that

d M s (b i , A) = ∞. (c) For some (equivalently, all) i in s, we have that d M ar a l (b i , A) = ∞.
Note that simply connectedness yields that

d M ar a l (b i , A) = d M (l,r) (b i , A ar a l ).
We say that B is obtained from A by a global application of α s if it satisfies (any of) the above conditions. In particular, the set B is nice.

Proof. (a) → (b): By the definition of α

s the distance d B s (b i , A) is infinite for every i in s. Since B is nice in M , so is d M s (b i , A) = ∞. (b) → (c): Obvious. (c) → (b)
If both a l and a r are imaginary, then there is nothing to prove. Thus, may assume that a r is real. Furthermore, suppose that there is a path P connecting some b i with some a in A s (A) in A s (M ). Take P of shortest possible length.

We need to show that

d M ar a l (b i , A) < ∞.
Note that a and a r are connected in A (l,r] (M ) and, since A is nice, there is a shortest path Q in A (l,r] (A) witnessing this. In particular, let a r-1 be the direct neighbour of a r in Q. Connecting Q and P , we have that a r-1 and b i lie beneath a r and are connected in A (l,r] by a path disjoint from a r . Simply connectedness yields a path Q 1 beneath a r in A (l,r) connecting them. If a l is imaginary, we are done. Otherwise, the vertices a r-1 and a l are connected through b i . Again by simply connectedness, there is a path Q connecting them below a r in [l, r). Let now a l+1 be the direct neighbour in Q above a l Note that a l+1 and b i lie between a l and a r . Simply connectedness of M yields that there is a path in M ar a l between b i and a l+1 . Hence

d M ar a l (b i , A) < ∞.
(b) → (a): If both a l and a r are imaginary, then there are clearly no new connections between any b i and A, and thus B is obtained by applying α [0,N ] to A. Hence, we may assume that a r is real. We first need to show that no b i is in relation to an element in A besides a r and a l . This implies that B is obtained from A by application of α s . Assume first that b r-1 is connected with some other element a r in A r (A). Since A is nice, there is a path in A {r-1,r} (A) connecting a r and a r . This, together with the extra connection to b r-1 yields a loop in A {r-1,r} , which contradicts Remark 4.9 [START_REF] Baudisch | A free pseudospace[END_REF]. Likewise for b l+1 . Finally, by assumption, no b i in A (l+1,r-1) is in relation with an element in A s (A). Now, in order to show that B is nice, consider x and y in B with finite t-distance in M . If both x and y lie in A, we are done, since A is nice. Likewise, if both x and y lie in the path a l , b l+1 , . . . , b r-1 , a r , the direct connection works as well. Therefore, assume that x lies in A and y does not. By the assumption it follows that t s. Suppose that l lies in t. Since y and a l are t-connected (in M ), so are x and a l . As A is nice, there is a connection between x and a l in A t (A). In particular, there is a connection between x and y in A t (B).

Theorem 4.22. Let M be complete and simply connected. Given a nice subset A and b in M , there is a nice subset B of M containing b such that A ≤ B in finitely many steps.

Proof. We may clearly assume that b does not lie in A.

Let r be minimal such that there exists an element a r in A r (A) lying over b (if r = N + 1, set a r = a N +1 ). Likewise, choose l maximal such that there exists an element a l in A l (A) beneath b (if l = -1, then set a l = a -1 ). We call the interval s = (l, r) the width of b over A. Define as well the distance from b to A as d s (b, A ar a l ). We prove the theorem by induction on the width and the distance from b to A: If the distance is infinite, by completeness of M , choose a path Otherwise, let P be a path of minimal length lying between a l and a r connecting b to A. Let b be the last element in P before b. By assumption, the distance from b to A is strictly smaller than the length of P . Thus, there is a nice set B ≥ A containing b . Either the width or the distance of b to B has become smaller and we can now finish by induction.

In particular, we can now prove that the notions of nice and wunderbar agree.

Corollary 4.23. A nice subset A of a complete simply connected set M is wunderbar.

Proof. Suppose we are given two points a and b in A and an s-path P in M of length n connecting them. By Theorem 4.22, we can obtain a nice set B such that A ≤ B and B contains the path P . By Lemma 4.18, the set A is wunderbar in B, so there is an s-path of length n in A connecting a and b. Thus, the set A is wunderbar.

Combining the previous results, we obtain the following. Corollary 4.24. Let M be complete and simply connected and A be a nice subset. The following hold:

(a) If M \ A is countable, then A ≤ M . (b) A is simply connected. (c) A is wunderbar. (d) If A is countable, then ∅ ≤ A.
Proof. Theorem 4.22 yields (a). Now, Corollary 4.20 yields (b). In order to prove (c), it is sufficient to consider countable nice subsets A. Replace M by a countable elementary substructure M that contains A. Then A is nice in M and A ≤ M by a. Lemma 4.18 yields that A is wunderbar in M and hence in M . Since ∅ is nice, clearly (d) follows from (a) and (b).

It follows that, for countable A, we have ∅ ≤ A if and only if A is simply connected and complete. And for simply connected complete countable B, we have that A ≤ B if and only if A is nice in B. Therefore Corollary 4.25. The model M ∞ is the Fraïssé limit of the class of finite complete simply connected colored N -spaces together with nice embeddings.

The construction is actually simpler than the general construction given in Section 3, since if a finite set B satisfies that

B b a = B ∩ M b a for all a and b in B, then B is r-strong in M ∞ if and only it is nice in M ∞ . Indeed, consider a rich sequence A 0 ≤ A 1 ≤ . . . with union M ∞ . Then B is contained some A i . But B is also nice in A i , which implies B ≤ A i , and therefore B is r-strong in M ∞ .
Having M ∞ as a model, the theory PS N is consistent. It will follow from the next proposition that it is complete. In particular, the stronger version of Axiom (1) stated in Corollary 4.11 follows formally from our axioms. Proposition 4.26. Any two ω-saturated models of PS N have the back-andforth property with respect to partial isomorphisms between finite nice substructures.

Proof. Let M and M be two ω-saturated models and consider a partial isomorphism f : A → A , where A is nice in M and A is nice in M .

Given b in M , Theorem 4.22 yields a nice finite subset B ≥ A containing it. Thus, we may assume that B is obtained from A by applying α s on (a l , a r ). Since M is an ω-saturated model of Axiom (2), there is a path a l , b l+1 , . . . , b r-1 , a r in M such that the s-distance of b i to A is infinite. By Lemma 4.21) the set B = A ∪ {b l+1 , . . . , b r-1 } is nice and f extends to an isomorphism between B and B . Theorem 4.27. Any partial isomorphism f : A → A between two finite nice subsets of two models of PS N is elementary.

Proof. Replace the models M and M by two ω-saturated extensions M 1 and M 1 Note that A and A remain nice in the corresponding extensions. Lemma 4.26 yields that f is elementary with respect to M 1 and M 1 and thus its restriction to M and M is elementary as well.

Corollary 4.28. The theory PS N is complete.

Proof. Note that set ∅ is nice in any colored N -space and apply Theorem 4.27.

Corollary 4.29. The type of a nice set A is determined by its quantifier-free type.

Corollary 4.30. The model M ∞ is ω-saturated.

Proof. Let M be any ω-saturated model of PS N . It follows from Lemma 3.3 and the equality of nice and r-strong that the family of isomorphisms between finite nice subset of M and M ∞ has the back-and-forth property. This implies that M ∞ is also ω-saturated.

Corollary 4.31. The Fraïssé limit M 0 is the prime model of PS N .

Proof. Consider any finite A ⊂ M which can be obtained from some fixed flag by a sequence of applications of α {i} for varying i ∈ [0, N ]. Since the d {i} -distances are either 0 or ∞, it follows inductively from Lemma 4.21 that all intermediate sets are nice. So the quantifier-free type of A implies that A is nice and therefore implies the type of A. Whence A is atomic. This shows that M 0 is atomic. Proof. By Corollary 4.30, we may assume that the nice set A is a subset of M ∞ . By Corollary 4.24 (a), we have that M is an increasing union of nice sets containing A. Thus, we may reduce the statement to showing that if B = A∪{b ls+1 , . . . , b rs-1 } is obtained by applying the operation α s on a ls , a rs in A, then the tuple (b ls+1 , . . . , b rs-1 ) has infinitely many A-conjugates. This is now clear, as any two sets resulting from applying the operation α s on a ls , a rs in A have the same type over A, by Lemma 4.21 and Corollary 4.29.

Words and letters

In this section, we will study the semigroup Cox(N ) generated by the operations α s , where s stands for a non-empty interval in [0, N ]. Such intervals will be then called letters. We will exhibit a normal reduced form for words in Cox(N ) and describe the possible interactions between words when multiplying them.

Two letters s and t in [0, N ] commute if their distance is at least 2. That is, either r s ≤ l t or r t ≤ l s , where s = (l s , r s ) and t = (l t , r t ). By definition, no letter commutes with itself nor with any proper subletter. Definition 5.1. We define Cox(N ) to be the monoid generated by all letters in [0, N ] modulo the following relations:

• ts = st = s if t ⊂ s, • ts = st if s and t commute.
We denote by 1 the empty word.

The inversion u → u -1 of words defines an antiautomorphism of Cox(N ). All concepts introduced from now on will be invariant under inversion.

The centraliser C(u) of a word u in Cox(N ) is the collection of all indexes in [0, N ] commuting with every letter in u. Clearly, a letter s commutes with u in Cox(N ) if and only if s ⊂ C(u).

In order to obtain a normal form for elements in Cox(N ), we say that a word s 1 • • • s n is reduced if there is no pair i = j of indices such that s i ⊂ s j and s i commutes with all s k with k between i and j. Definition 5.2. The word u can be reduced to v, denoted by u → v, if v is obtained from u by finitely many iterations of the following rules:

Commutation: Replace an occurrence of s • t by t • s, if s and t commute.

Cancellation: Replace an occurrence of s • t or t • s by s, if t ⊂ s. Two words u and v are equivalent (or u is a permutation of v), denoted by u ≈ v, if u → v by exclusively applying the commutation rule.

It is easy to see that permutations of reduced words remain reduced. In particular, a word is reduced if and only if the cancellation rule cannot be applied to any permutation.

Clearly, two word u and v represent the same element in Cox(N ) if u → v. The following proposition yields in particular that the converse is true: Two words have a common reduction if they represent the same element in Cox(N ) (cf. Corollary 5.4). Proposition 5.3. Every word u can be reduced to a unique (up to equivalence) reduced word v. We refer to v as the reduct of u.

Proof. Among all possible reductions of the word u, choose v of minimal length. Clearly, cancellation cannot be applied any further to a permutation of v, thus v is reduced. We need only show that v is unique such.

For that, we first introduce the following rule:

Generalised Cancellation: Given a word s 1 • • • s n and a pair of indices i = j such that s i ⊂ s j and s i commutes with all s k 's with k between i and j, then delete the letter s i .

If the situation described above occurs, we say that s i is absorbed by s j . Note that a generalised cancellation is obtained by successive commutations and one single cancellation. Furthermore, one single cancellation applied to some permutation of u can be obtained as some permutation of a generalised cancellation applied to u. This implies that every reduct can be obtained by a sequence of generalised cancellations followed by a permutation. Assume now that u → v 1 and u → v 2 , where both v 1 and v 2 are reduced. We will show, by induction on the length of u, that v 2 is a permutation of v 1 . If u is itself reduced, then v 1 and v 2 are permutations of u and hence the result follows. Otherwise, there are two words u 1 and u 2 obtained from u by one single generalised cancellation such that u i → v i for i = 1, 2.

We claim that there is a word u such that u i → u for i = 1, 2, either by permutation or by a single generalised cancellation. This is immediate except for the case where there are indices i, j and k (for i = k) such that u 1 is obtained from u because the letter s i is absorbed by s j and u 2 is obtained from u in in which the same letter s j is absorbed by s k . In this case, set u to be the word obtained from u by having both s i and s j absorbed by s k . Clearly, we have that u 1 → u . Also, since s i ⊂ s j , it follows that s i commutes also with all letters between s j and s k . Hence, the word u is obtained from u 2 in which s k absorbs s i . Let v be a reduct of u . Induction applied to u 1 and u 2 implies that v is a permutation of both v 1 and v 2 . Hence, the word v 1 is a permutation of v 2 .

Corollary 5.4. Every element of Cox(N ) is represented by a reduced word, which is unique up to equivalence.

Proof. Let C be the collection of equivalence classes of reduced words. From the previous result, it follows that there is a natural surjection C → Cox(N ). Represent by [u] the equivalence class of the word u.

Set [u] • [v] = [w] iff u • v → w.
Then C has a natural semigroup structure. Since C satisfies the defining relations of Cox(N ), the map C → Cox(N ) is an isomorphism.

In order to exhibit a canonical representative of the equivalence class [u], we introduce the following partial ordering on letters:

(l s , r s ) < (l t , r t ) iff r s ≤ l t . A reduced word s 1 • • • s n is in normal form if for all i < n, if s i and s i+1 commute, then s i < s i+1 .
Remark 5.5. Every reduced word is equivalent to a unique word in normal form.

Proof. We will actually prove a more general result: Let S be any set equipped with a partial order <. We say that s and t commute if either s < t or t < s. Let S * be the semigroup generated by S modulo commutation. Two words in S * are equivalent if they can be transformed into each other by successive commutations of adjacent elements. A word s 1 • • • s n is in normal form if s i > s i+1 for all i < n. We have the following.

Claim. Every word u in S * is equivalent to a unique word v in normal form.

For existence, start with u and swap successively every pair s i > s i+1 . This process must stop since the number of inversions {(i, j) | i < j and s i > s j } is decreased by 1 at every step. The resulting v is in normal form.

For uniqueness, consider two equivalent words in normal form

u = s 1 • • • s n and v = t 1 • • • t n .
Let π be some permutation transforming u into v. Suppose for a contradiction that π(1) = k = 1. Then t k = s 1 commutes with t i for i < k. By hypothesis, we have t k-1 < t k . Note that there is no i < k with t i < t k and t k < t i-1 . Hence, for all i < k, we have that t i < t k and thus t 1 < t k , that is, t 1 < s 1 . By means of the permutation π -1 , we conclude that s 1 < t 1 , which yields a contradiction. Thus π(1) = 1 and hence

s 2 • • • s n is equivalent to t 2 • • • t n . Induction on n yields the desired result.
It is an easy exercise to show that, for S and S * as before, we have

r • t 2 • • • t n ≈ r • s 2 • • • s n ⇒ t 2 • • • t n ≈ s 2 • • • s n .
Therefore, we obtain the following result.

Remark 5.6. u • v ≈ u • v implies v ≈ v . Given two reduced words u = s 1 • • • s m and v = t 1 • • • t n , their product u • v is not reduced if

and only if one of the two following cases occurs:

• There are i ≤ m and j ≤ n such that s i commutes with s i+1 The concepts initial segment, right-absorbed and left-biting are defined likewise.

Clearly, these notions depend only on the equivalence class of u and v. Thus, the following lemma follows.

Lemma 5.8. Given two reduced words u and v, the product u • v is reduced if and only if none of them bites the other one (in the corresponding directions).

If both u and v are reduced and u is absorbed by v, then u • v reduces to v. Corollary 5.14 will show that the converse also holds.

The following observations will be often used throughout this article.

Lemma 5.9 (Absorption Lemma). Let v be a (possibly non-reduced) word.

(1) If a letter s is left-absorbed by v, then there is a unique letter in v witnessing it. (2) If two non-commuting letters are absorbed by v, then they are absorbed by the same letter in v.

(3) Suppose v = v 1 • v 2 and let u be a word left-absorbed by v but not bitten from the right by v 1 , then u and v 1 commute and u is left absorbed by v 2 .

Proof.

Assume v = t 1 • • • t n . Let r ⊂ t i commute with t 1 • • • t i-1 and s ⊂ t j commute with t 1 • • • t j-1 . Assume i ≤ j.
Then, either i = j or s commutes with t i , which implies that s commutes with r. This yields both (1) and (2). For (3), we apply induction on the length m of u = s 1 • • • s m . If m = 0, then there is nothing to prove. Otherwise, the subword u = s 2 • • • s m is not bitten by v 1 by assumption. Induction gives that u commutes with v 1 and is absorbed by v 2 . The letter s 1 cannot be absorbed by v 1 , for otherwise s 1 would also commute with u and thus it would belong to the final segment of u. The word u would then be bitten by v 1 . Since s 1 is absorbed by v but not by v 1 , it must commute with v 1 and hence it is absorbed by v 2 as well.

Based on the the previous result, we introduce the following notions.

Definition 5.10.

The left stabiliser S L (v) of a word v = t 1 • • • t n is the union of the sets S j L (v) = t j ∩ C(t 1 . . . t j-1
). The right stabiliser S R (v) is defined likewise or, alternatively, as S L (v -1 ) By Lemma 5.9(2), the sets S j L (v) are either empty or intervals commuting with each other. Equivalent words have same stabilisers. In fact, if u → v then S L (u) ⊂ S L (v).

Lemma 5.11. The letter s is absorbed by v if and only if s ⊂ S L (v).

Set

|s 1 • • • s m | = s 1 ∪ • • • ∪ s m .
Then u is absorbed by v if and only if |u| ⊂ S L (v). Furthermore, the word v bites u from the right if and only if some element in the final segment of u is contained in S L (v).

Lemma 5.12. Given two words u and v, there is a unique decomposition u = u 1 • u 2 (up to commutation) such that:

• u 2 is left-absorbed by v.

• u 1 is not bitten from the right by v.

The decomposition of u depends only on the set S L (v).

Proof. We proceed by induction on the length of u. If u is not bitten by v, we set u 1 = u and u 2 = 1. Otherwise, up to permutation, we have u = u • s, where s is absorbed by v. Decompose u as u 1 • u 2 and set u 1 = u 1 and

u 2 = u 2 • s.
Uniqueness is proved in a similar fashion.

We can now describe the general form of the product of two reduced words in Cox(N ). Theorem 5.13 (Decomposition Lemma). Given two reduced words u and v, there are unique decompositions (up to permutation):

u = u 1 • u v • v 1 = v, such that: (a) u is left-absorbed by v 1 , (b) v is properly right-absorbed by u 1 , (c) u and v commute, (d) u 1 • v 1 is reduced. It follows that u • v → u 1 • v 1 .
We call such a decomposition fine.

Proof. We apply Lemma 5.12 to u and v to obtain a decomposition

u = u 1 • u ,
such that u is left-absorbed by v and u 1 is not bitten by v from the right. The same (in the other direction) with u 1 and v yields

v • v 1 = v,
where v is right-absorbed by u 1 and v 1 is not bitten from the left by u 1 .

First, we show (c), that is, the words u and v commute. If not, let s the first element of u which does not commute with v . Since s is left-absorbed by v • v 1 , it must be left-absorbed by v . As u 1 right-absorbs v , it also rightabsorbs s, which contradicts that u 1 • u is reduced. Lemma 5.9(3) gives that u is absorbed by v 1 , showing (a).

Let us now show (d): the product u 1 • v 1 is reduced. Otherwise, as v 1 is not bitten from the left by u 1 , it bites u 1 from the right, i.e. it left-absorbs a letter s from the final segment of u 1 . The Absorption Lemma 5.9, applied to u 1 = u 1 1 • s and v , which is right absorbed by u 1 , gives (possibly after permutation) a decomposition v = x • y, where |x| ⊂ s and y commutes with s. There are two cases:

(1) The word x = 1. Then s commutes with v and is absorbed by v 1 .

This contradicts that u 1 is not bitten by v 1 from the right. (2) The word x is not trivial. As it is absorbed by s and s is rightabsorbed by v 1 , we have that x is right-absorbed by v 1 . This contradicts that v • v 1 is reduced.

The only point left to prove is that v is properly right-absorbed by u 1 . Otherwise, there is a letter t in v which is absorbed but not properly absorbed by u 1 . Then t occurs in the final segment of u 1 and v = t • y up to commutation. In particular, the word u 1 is bitten from the right by v and thus by v, which contradicts our choice of u 1 .

In order to show uniqueness, assume we are given another fine decomposition:

u = u 1 • u v • v 1 = v
We need only show the following four facts:

(1) The word u is left-absorbed by v: Since u commutes with v and is left-absorbed by v 1 , then it is left-absorbed by v • v 1 as well.

(2) The word u 1 is not bitten by v from the right: Suppose not and take a letter s in the final segment of u 1 which is left-absorbed by v. Since u 1 • v 1 is reduced, the letter s must be left-absorbed by v . Let t in v containing s. However, the word t is right-absorbed by u 1 . As u 1 is reduced and s is in the final segment of u 1 , the only possibility is that s = t. But then t is not properly left-absorbed by u 1 , which is a contradiction. (3) v is right-absorbed by u 1 : By definition. (4) v 1 is not bitten from the left by u 1 : This clearly follows from the fact that u 1 • v 1 is reduced.

Corollary 5.14. Let u and v be reduced words. Then v left-absorbs u if and

only if uv = v in Cox(N ). Note that uv = v in Cox(N ) if and only if u • v → v. Proof. Clearly, if v left-absorbs u, then u • v → v.
For the converse, apply the Decomposition Lemma 5.13 to u and v to obtain:

u = u 1 • u v • v 1 = v
such that u is left-absorbed by v 1 , the word v is properly right-absorbed by u 1 , the words u and v commute and u 1 • v 1 is reduced. By assumption,we have

u • v → u 1 • v 1 ≈ v = v • v 1 .
Thus u 1 = v . Since u 1 must be properly right-absorb itself, this forces u 1 to be trivial. Hence u = u is left-absorbed by v.

As in Cox(N ) (or generally, in any semi-group), the identity uvx = uv holds if vx = v, we have the following.

Corollary 5.15. Let u and v be reduced words and w the reduct of u • v. Then S R (v) ⊂ S R (w).

Definition 5.16. The wobbling between two words is

Wob(u, v) = S R (u) ∩ S L (v).
Remark 5.17. If u • v is reduced, then every s ⊂ Wob(u, v) is properly right-absorbed by u and properly left-absorbed by v.

Proof. If s is not properly right-absorbed by u, then s belongs to the final segment of u. Since s is left-absorbed by v, the product u • v would not be reduced.

Lemma 5.18. Assume that v 1 • v 2 and u • v 2 are reduced. If v 1 is right absorbed by u, then Wob(v 1 • v 2 , h) ⊂ Wob(u • v 2 , h). Proof. The word u • v 2 is the reduct of u • (v 1 • v 2 ). Corollary 5.15 yields that S R (v 1 • v 2 ) ⊂ S R (u • v 2 ).
We will now study the idempotents of Cox(N ). Definition 5.19. A word is commuting if it consists of pairwise commuting letters.

The letters of the final segment of a word u form a commuting word, which we denote by ũ (up to equivalence).

Commuting words are automatically reduced. Since every subset of [0, N ] can uniquely be written as the union of commuting intervals, a commuting word (up to equivalence) can be considered as just a set of numbers. The following is an easy observation: Lemma 5.20. Every word u is equivalent to a word x • ũ, where ũ is the final segment of u.

Note that no letter in the final segment of x commutes with ũ.

Proposition 5.21. Let u and v reduced words such that v left-absorbs u. Then, up to permutation, there is are unique decompositions

u = u • w w • v = v, such that
(1) u is properly left-absorbed by v , (2) w commutes with u , (3) w is a commuting word.

Proof. Apply the Absorption Lemma 5.9 to v and u, which is completely left-absorbed by v. The letters of u which are not properly left-absorbed by v must commute with all other letters and form the word w.

We obtain therfore the following consequence, which implies that a word is commuting if and only if it is an idempotents in Cox(N ).

Corollary 5.22. A reduced word is commuting if and only if it absorbs itself (left, or equivalently, right).

Proof. Clearly, if u is commuting, then |u| = S L (u), so u absorbs itself. Suppose now that u left-absorbs itself. By the proposition applied to v = u we find u = w • u ≈ w • v such that u is properly left-absorbed by v and w is a commuting word. It follows that u = v properly absorbs itself, i.e. the word u = 1.

We can now state a symmetric version of the Decomposition Theorem 5.13, combined with Proposition 5.21.

Corollary 5.23 (Symmetric Decomposition Lemma). Let u and v be two reduced words. Each can be uniquely decomposed (up to commutation) as:

u = u 1 • u • w w • v • v 1 = v, such that: (a) u is properly left-absorbed by v 1 , (b) v is properly right-absorbed by u 1 , (c) u , w and v pairwise commute, (d) w is a commuting word, (e) u 1 • w • v 1 is reduced.
In particular, we have u

• v → u 1 • w • v 1 . w v v 1 u 1 u w u 1 w v 1 u v w Proof. Let u = u 1 • ū v • v1 = v
be a fine decomposition as in Theorem 5.13. Apply Proposition 5.21 to ū and v1 to obtain

ū = u • w w • v 1 = v1 ,
where u is properly left-absorbed by v 1 , w commutes with u and w is a commuting word. Uniqueness follows similarly.

In order to describe canonical paths between elements (or rather, between flags) in the Fraïssé limit M N ∞ , we require a stronger form of reduction, since applying twice the same operation α s does not necessarily yield a global application of α s , but rather a finite product of proper subletters. If v is reduced, we call v a strong reduct of u.

As an example note that u • u -1 * -→ 1. Despite the possible confusion for the reader, we will not refer to reductions defined in 5.2 as weak reductions.

Related to the notion of strong reduction, we also consider the following partial ordering on words. Definition 5.25. For words u and v, we define u ≺ v if some permutation of u is obtained from v by replacing at least one letter s of v by by a (possibly empty) product of proper subletters of s. By u v, we mean u ≺ v or u ≈ v. Well-foundedness implies in particular that if u ≺ v, then u ≈ v. Furthermore, property (2) yields that ≺ induces a partial order on Cox(N ), setting

[u] ≺ [v] if u ≺ v,
where both u and v are reduced. With this notation, the trivial word 1 becomes the smallest element.

Proof. To see that ≺ is well-founded, we introduce an ordinal-valued rank function ord. For i in [0, N ], set ord i (w) to be number of letters s in w with i + 1 elements. Define now ord(w) = ω N ord N (w) + ω N -1 ord N -1 (w) + . . . + ord 0 (w).

Then u ≺ v implies ord(u) < ord(v).

The semigroup Cox(N ), equipped with the order function as above, is an ordered semigroup in which left and right-cancellation are (almost) orderpreserving.

Lemma 5.27. Let w • v be reduced and w

• v w • v . Then v v . The condition that w • v is reduced is needed, by taking v = t s = w = v and w • v * - → 1.
Proof. By induction on the number of letters appearing in w, we need only consider the case where w = s for some interval s.

The assumption implies that s • v is equivalent to a word u s • u where u s s and u v . The word u s either equals s or is a product of proper subletters of s. If u s = s, we have v ≈ u v and are done. Otherwise, since s • v is reduced, it follows that u s = 1. This implies v ≺ s • v ≈ u v .

Corollary 5.28. Given reduced words w • v and v such that w • v is smaller than some strong reduct of w • v , then v v .

Lemma 5.29. The partial order is compatible with the semigroup operation in Cox(N ).

Proof. Given reduced words u,v and w, we have to show the following:

[u] [v] ⇒ [w][u] [w][v] and [u] [v] ⇒ [u][w] [v][w].
By symmetry, it is sufficient to show the first implication. By induction on |w|, it is enough to consider the case where w is a single letter s.

Suppose first that s is left-absorbed by v. By Corollary 5.14,

[s][v] = [v].
If s is also left-absorbed by u, we are clearly done. Otherwise, by Theorem 5.13, decompose u (up to permutation) as u = u • u 1 , where s • u 1 is the reduct of s • u. Also, write v = v • t • v 1 such that s ⊂ t and v is in C(s). Now, the word u 1 u v, so write

u 1 = ū1 • u t 1 • ū1 1 , where ū1 v, u t 1 t and u 1 1 v 1 . Since s • u 1 is reduced, so is s • ū1 • u t 1 = ū1 • s • u t 1 .
This forces u t 1 to be either trivial or different from t (and s = t as well). In both cases, we have that s • u t 1 t, which implies s • u 1 v, so we are done.

If s is not left-absorbed by v, by Theorem 5.13, we can write (up to permutation) v = v • v 1 , where v is properly absorbed by s and s

• v 1 is reduced. So [s][v] = [s • v 1 ]. If s is left-absorbed by u, then [s][u] = [u] [v • v 1 ] ≺ [s • v 1 ]. Otherwise, write u = ū • u • u 1 as above such that s • u → ū • s • u 1 . Since ū and s commute, note that ū • u 1 is irreducible, since u is. Decompose ū • u 1 = u 1 • u 11 with u 1 v and u 11 v 1 . Since s • ū • u 1 = ū • s • u 1 is reduced, the word u 1 must be trivial. Therefore s • ū • u 1 = s • u 11 s • v 1 .
In particular, since 1 v for any word v, we obtain the following result.

Corollary 5.30. Let u be reduced. Given any word v, the reduction w of u • v is -larger than u.

In contrast to Proposition 5.3, uniqueness of strong reductions does no longer hold, e.g. s•s * -→ s and s•s * -→ 1. However, we get the following result, which allows us to permute the steps of the strong reduction:

Proposition 5.31 (Commutation Lemma). If x is a strong reduct of u•v•w, then there is a strong reduct y of v such that u • y • w * - → x.
Proof. Consider first the case where u = t has length 1, the word v has length 2 and w is empty. Suppose furthermore that in the first step of the reduction t • v * -→ x, the letter t is deleted. It is easy to check that setting y as the reduct of v, the results follows, except if v = s • s, the letter t is contained in s and the strong reduction is t

• (s • s) * - → s • s * - → x,
where x is a product of letters which are properly contained in s. Then:

• If t = s, set y = s. • If t • x * - → x, set y = x.
• Otherwise, apply Theorem 5.13 to x and t and decompose

x = x • x 1 such that |x | is properly contained in t and t • x 1 is reduced. Set y = t • x 1 .
In all three cases, the strong reductions hold:

t • (s • s) * - → t • y * - → x.
In order to show the proposition for the general case, motivated by the proof of 5.3, let us introduce the following rule:

Generalised Splitting: Given a word s 1 • • • s n and a pair of indices i = j such that s i = s j and s i commutes with all s k 's with k between i and j, delete s j and replace s i by a product of letters which are properly contained in s.

Note that a strong reduction consists of finitely many generalised cancellations and generalised splittings, followed by commutation (if needed).

If v is reduced, set y = v. Otherwise, we will apply induction on the ≺-order type of v. Suppose therefore that the assertion holds for all v ≺ v and consider x a strong reduct of u

•v •w. If 2 < |v|, then (after permutation) write v = v 1 • a • v 2 ,
where a is a non-reduced word of length 2. Note that by assumption, the subword a ≺ v, so there is a strong reduct b of a such that u

• v 1 • b • v 2 • w * - → x. Since a is not reduced, we have b ≺ a and thus v 1 • b • v 2 ≺ v. Induction yields the existence of a strong reduct y of v 1 • b • v 2 such that u • y • w * - → x. Note that v = v 1 • a • v 2 * - → v 1 • b • v 2 * - → y.
Therefore, we may assume that v has length 2 and it is non-reduced. By the above discussion, the first step in the strong reduction

u • v • w * - → x.
is either a generalised cancellation or a generalised splitting. If it involves only letters from v, its strong reduction is -smaller and one step shorter to the output x, so we are done by induction on the number of steps in the strong reduction. Likewise if the letters involved are in u • w. Thus, we may assume that there are two letters t and r witnessing the reduction in the first step and, say, the letter t occurs in u and r in v.

We have two cases:

• The letter t is absorbed by v. In particular, the letter lies in the final segment ũ. Write u = u 1 • t. If it was a generalised splitting, the result v ≺ v and

u 1 • v • w * - → x. Induction gives a strong reduct x of v such that u 1 • x • w * - → x.
In particular, we are now in the case t • v there exists a strong reduction y of v such that t

• y * - → x . Note that u • v • w = u 1 • (t • v) • w * - → u 1 (t • y) • w * - → u 1 • x • w * - → x,
so we are done.

If the first step was a generalised cancellation, the word v does not change and now

u 1 • v • w * - → x in one step less. We obtain a strong reduct x of v with u 1 • x • w * - → x. Again, note that t • v * - → v * - →
x so, again by the previous discussion, there is a strong reduct y of v which does the job.

• Otherwise, the occurrence r in v is deleted. If r = t, we are in the previous case. Suppose hence r t and write u = u 1 • t • u 2 , where u 2 commutes with r. We may assume that v = r • s. Note that r and s are comparable, since v is not reduced. If r ⊆ s, then set y = s, which is a strong reduct of v. We have that u • y • w * -→ x. If s r, then s and u 2 commute as well. Note that

u 1 •(t•s)•u 2 •w = u • s • w * - → x in one step less. We have that u 1 • t • u 2 • w * - →
x and setting y = r does the job.

Despite the apparent arbitrarity of the strong reductions, they are orthogonal to the reduction without splitting, as the following result shows. Proposition 5.32. Let u and v be reduced words and consider x the reduct of u • v and x * some strong reduct of u • v, where splitting occurs. Then x * ≺ x.

Note that that this is not true for the product of three reduced words: s • s • s can be strongly reduced to s by one splitting operation.

Proof. Remark first that, if w = s 1 • • • s n is a commuting word and y * is a strong reduct of w • w, then y * = t 1 • • • t n ,
where each t i is a strong reducts of s i • s i . If splitting ever occured in the reduction, then y * ≺ w.

To prove the proposition, choose decompositions

u = u 1 • u • w and w • v • v 1 = v, as in Corollary 5.23. A general cancellation applied to u 1 • u • w • w • v • v 1
does the following: either the last letter of (a permutation of) u is deleted, the first letter of v is deleted or one letter in one of the copies of w is deleted. Hence, after finitely may generalised cancellations, the end result has the form

z = u 1 • u • w • w • v • v 1 ,
where u is a left end of u , the subword v is a right right end of v and w is a subword of w. A generalised splitting for z can only happen inside w •w . So we obtain a word

z = u 1 • u • a • v • v 1 ,
where a is obtain from w • w by the splitting operation.

If we apply the Commutation Lemma 5.31 to (u

1 • v ) • a • (u • v 1 ) ≈ z , we obtain a strong reduct b of a such that u 1 •b•v 1 * - → x * . The above observation gives that b ≺ w and thus x * u 1 • b • v 1 ≺ u 1 • w • v 1 ≈ x.
Inspired by the following picture:

- → c -1 implies c • a * - → b -1 and b • c * - → a -1 . Proof. By symmetry, it is enough to show that a•b * - → c -1 implies c•a * - → b -1 . Suppose hence that a • b * - → c -1 .
We apply induction on the ≺-type of a and b.

If

a • b is reduced, then c = b -1 • a -1 and so c • a = b -1 • a -1 • a * - → b -1
. Thus, assume a • b is not reduced. We distinguish the following cases (up to permutation):

• a = a 1 • s,
a • b = a 1 • (s • b) → a 1 • b * - → c -1 . Since a 1 ≺ a, induction gives that c • a 1 * - → b -1 , which implies that c • a = (c • a 1 ) • s * - → b -1 • s → b -1 . • b = s • b 1 , where s is properly right-absorbed by a. Again a • b = a • (s • b 1 ) → a • b 1 * - → c -1 , so by induction c • a * - → b -1 1 . Thus c • (a • s) * - → b -1 1 • s = b -1 . Since a is the only strong reduct of a • s, again Proposition 5.31 gives that c • a * - → b -1 . • a = a 1 • s and b = s • b 1 Since a 1 • (s • s) • b 1 * - → c -1 , Proposition 5.31 provides a strong reduct x of s • s such that a 1 • x • b 1 * - → c -1 b * - → c -1 .
The word x is either s or a product of proper subletters of x and hence ≺-smaller than s. Since b = s • b 1 is reduced, apply Theorem 5.13 to decompose x = x 1 • x , where x is properly left absorbed by b 1 and

x 1 • b 1 is reduced (If x = s, then x 1 = s and x = 1). Since x • b 1 * - → b 1 , the reduction (a 1 • x 1 ) • (x • b 1 ) * - → c -1 implies a 1 • x 1 • b 1 * - → c -1 . Since a 1 ≺ a and x 1 • b 1 b, induction gives that c • a 1 * - → b -1 1 • x -1 1 . In particular, c • a = c • a 1 • s * - → (b -1 1 • x -1 1 ) • s → b -1 1 • s → b -1 .
We can now easily conclude the following:

Corollary 5.34. If u and v are both reduced and u

• v * - → 1, then v ≈ u -1 .
Proof. The Triangle Lemma (Proposition 5.33

) yields 1•u * - → v -1 and v •1 * - → u -1 . That is, u -1 * - → v and v * - → u -1 . Thus u -1 v u -1 ,
and therefore v ≈ u -1 .

Recall by Corollary 5.14 that if u is the reduct of u • v, then v is rightabsorbed by u. This is no longer true for strong reductions: take for example

(s • t) • (t • s • t) = s • (t • t) • (s • t) * - → s • (s • t) * - → s • t.
However, in certain situations we are still able to conclude the same for strong reductions as for reductions with no splitting. Lemma 5.35. Let u and v be reduced. If every letter in v which is rightabsorbed by u is properly absorbed and u

• v * - → u, then u • v → u.
Proof. Apply Theorem 5.13 to obtain fine decompositions u = u 1 • u and v • v 1 = v such that u is properly left-absorbed by v 1 , the word v is rightabsorbed by u 1 , the words u and v commute and u 1 • v 1 is reduced.

By hypothesis, the word v is properly right-absorbed by u 1 . The Commutation Lemma 5.31 applied to (u

1 • v ) • (u • v 1 ) * - → u gives (u 1 • v ) • (u • v 1 ) → u 1 • v 1 * - → u. Since u 1 • v 1 is reduced, we have u 1 • v 1 = u. So v 1 = u must properly absorb itself, which is a contradiction unless v 1 = 1 and thus u • v → u.
Let us conclude by giving a criteria for when a word wobbles inside two other. This will be useful for determining all possible paths between two given flags.

-1 • v * - → v, then |w| ⊂ Wob(u, v).
Proof. By Remark 5.17, it is enough to prove that w is properly rightabsorbed by u (and likewise for v). We proceed by induction on the length of |v|.

If v = 1, then w -1 • 1 * - → 1 implies w -1 = 1, since w is reduced. Suppose now that v = s • v 1 . Set u • s = u 1 , which is again reduced. So is u 1 • v 1 = u • v. The condition w -1 • v * - → v implies v -1 • w * - → v -1 by Proposition 5.33. This implies v -1 1 • (s • w • s) * - → (v -1 1 • s) • s * - → v -1 1 .
By the Commutation Lemma (Proposition 5.31), there is a strong reduct

w 1 of s • w • s with v -1 1 • w 1 * - → v -1 1 , or equivalently, w -1 1 • v 1 * - → v 1 . The Triangle Lemma 5.33 gives that s • (w • s) * - → w 1 implies w -1 1 • s * - → s • w -1 , that is, s • w 1 * - → w • s.
In particular, we have that

u 1 • w 1 = u • (s • w 1 ) * - → u • (w • s) * - → u • s = u 1 .
By the induction hypothesis applied to u 1 , v 1 and w 1 , we have that w 1 is properly right-absorbed by u 1 = u • s. By Lemma 5.9 (3), write w 1 as w s • w u where w s is properly absorbed by s and w u is properly right-absorbed by u and commutes with s. Note that s • w u is the only strong reduct of s • w 1 . Proposition 5.31 yields that the strong reduction (s

• w 1 ) • s * - → w • s • s * - → w factors through s • w u • s * - → w. Since s • w u • s is equivalent to s • s • w u , there is strong reduct x of s • s such that x • w u * - → w.
However, the product x • w u is already reduced and so x • w u = w. The reduct x is either s or consists of proper subletters of s. Suppose that x = s. Then u • w = u • s • w u = u • s, since w u is properly right-absorbed by u and commutes with s. This contradicts with u • w * -→ u. Hence, the word x consists of proper subletters of s. By Theorem 5.13, since u • s is reduced, decompose x into x • x 1 , where x is properly right-absorbed by u and u

• x 1 is reduced. Then u • x 1 is the only strong reduct of u • w = u • x • x 1 • w u .
We conclude that u • x 1 = u and thus x 1 = 1 by Corollary 5.14. Hence, the word w = x • w u is properly right-absorbed by u.

Flags and Paths

Let M be any colored N -space. As in Definition 4.16, recall that a flag F in M is a path a 0 -. . . -a N of length N , where each a i belongs to A i (M ). We call a i the i-vertex of the flag F . Definition 6.1. Given flags F and G, we say that G is obtained from F by the weak operation α s if s consists of the indexes where the vertices of F and G differ. A weak path of flags P is a sequence of flags F 0 , . . . , F n , where each F i is obtained from F i-1 by a weak operation α s i . We call s 1 • • • s n the word of P .

More generally, we define: Definition 6.2. Let A be a subset of [0, N ]. Two flags are equivalent modulo A if they have the same vertices in all levels outside A. We write F/A for the equivalence class of F modulo A.

Note that F/A is interdefinable with the set of vertices of F with levels outside A. For i in [0, N ] and A = [0, N ] \ {i}, the equivalence class F/A i is interdefinable with the vertex f i . We can say that F/A i and F /A j , for i and j immediate succesors, are connected in case they belong to a class of a common flag G. This induces a structure bi-interpretable with P S N .

Any two flags can be connected by a weak flag path: decompose the set I of indices where the vertices of F and G differ as the disjoint union s 1 ∪ • • • s n of intervals, such that s i and s j commute for i = j. Then F and G are connected by a weak path with word s 1 • • • s n . In particular, we obtain the following. Lemma 6.3. Two flags F and G are equivalent modulo A if and only if they can be connected by a weak path whose word consists of letters contained in A. Furthermore, there is such a path whose word is commuting. In particular, any two flags are connected by a weak path, by taking

A = [0, N ].
Commuting letters in a path induces another path whose word is a permutation of the previous one. Lemma 6.4. Let s and t be commuting letters and assume that F and G are connected by a weak flag path with word s • t. Then there is a unique weak flag path from F to G with word t • s.

Proof. Given the path F -H -G with word s • t, define a new flag H by replacing the s-part of H by the s-part of F and its t-part by the t-part of G. By construction, the weak path F -H -G has word t • s. Uniqueness is clear since the s-part and the t-part of H are determined by those of F and G.

Iterating the previous result, since any permutation can be achieved by a sequence of transpositions of adjacent commuting letters, given a weak path P u be a from F to G with word u, if v is a permutation of u, we can connect F and G by a weak path P v with word v. Note that P v does not depend on the sequence of transpositions and the collection of vertices of flags occuring in P u agrees with the one of flags in P . We call the path P v a permutation of P u .

We will now link the words appearing in weak paths with their distance as in Lemma 4.13. Lemma 6.5. Let t = (l, r) and F and G be equivalent modulo t. Let a l and a r the vertices of F (and G) of level l and r, respectively. Given a subletter s ⊂ t, the following are equivalent:

a) The flags F and G have finite s-distance in M ar a l . b) The flag F and G are connected by a weak flag path whose letters are contained in t but do not contain s.

Proof. (a) → (b): Consider a path b 0 , . . . b n in A s (M ar a l ) connecting two vertices of F and G. For every i in {1, . . . , n -1}, pick a flag F i containing b i and b i+1 which agrees with F and G outside the levels in t. Set F 0 = F and F n = G. If b i+1 has level j i , then F i and F i+1 are equivalent modulo t \ {j i }. They are thus connected by a weak flag path whose letters are contained in t \ {j} and therefore none contains s. The concatenation of these flag paths gives the result.

(b) → a): Let F = F 0 -. . . -F n = G be a weak flag path whose letters are in t but do not contain s. For every i in {0, n -1}, the flags F i and F i+1 have a common vertex in A s (M ar a l ). Thus, we can connect F and G by a path whose vertices lie in A s (F 0 ) ∪ . . . ∪ A s (F n ) and hence, between a l and a r .

In order to distinguish between weak operations between flags and global applications of α s to nice sets, as in Lemma 4.21, we introduce the following definition, at the level of flags. Definition 6.6. For s = (l, r), the flag G is obtained by a global application of α s from F if G is obtained by a weak application of α s from F and its new vertices have infinite distance in M ar a l from F , where a l and a r are the vertices of of F (and G) of level l and r, respectively. Since a flag is in particular a nice set, these two definitions agree, by applying Lemma 6.5 to the case t = s: Corollary 6.7. Given an interval s and flags F and G, the following are equivalent:

a) The flag G is obtained from F by a global application of α s , as in Lemma 4.21. b) The flag G is obtained from F by the weak operation α s and there is no weak flag path connecting them whose word consists of proper subletters of s. Definition 6.8. A flag path is a weak flag path where each flag is obtained from its predecessor by a global operation. If F and G are connected with a flag path with word u, we write

F - → u G.
A flag path is reduced if its word is reduced. Lemma 6.9. If there is a weak path from F to G with word u, we have

F - → v G for some v with v u.
Proof. By Lemmma 6.3, choose a weak path

F = F 0 -. . . -F n = G whose word v = s 1 • • • s n is -
smaller to u and minimal such. We need only show that this path is a flag path. Otherwise, some operation α s i is not global and, by Corollary 6.7, we can connect F i-1 and F i with a weak path whose word consists of proper subletters of s i . The resulting word is ≺-smaller than v, contradicting its minimality.

Combining the previous result and Corollary 6.7, we obtain the following: Corollary 6.10. If F and G are equivalent modulo t, then either F -→ t G or F -→

x G, for some product x whose factors are proper subletters of t.

Proof. By Lemma 6.3, the flag G is obtained from F by a weak path P whose word x either equals t or consists of letters properly contained in t. By Lemma 6.9, we may assume that P is a flag path.

We can now compose flag paths, using the results of the previous section.

Lemma 6.11. Assume F - → s G - → t H.
(1) If s and t commute, there is a unique

G with F - → t G - → s H. (2) If s is a proper subset of t, then F - → t H. Similarly, if t is a proper subset of s, then F - → s H.
(

) If s = t, then either F - → t H or F - → 3
x H, for some product x whose factors are proper subletters of t.

In particular, a permutation of a flag path yields again a flag path, by (1).

Proof. Property (1) follows easily from Lemma 6.4, since the permutation of a reduced word remains reduced. For (2), assume s t. Then H is equivalent to F modulo t. So by Corollary 6.10, either F -→ t H or F -→

x H, where x consists of proper subletters of t. The latter implies that G -→ s•x H, which contradicts the assumption G -→ t H. The proof is similar if t is a proper subset of s.

Property (3) clearly follows from Corollary 6.10, as F and H are equivalent modulo t. Lemma 6.9 yields the following. Corollary 6.12. Let F and G be two flags.

(1) If F - → u G, then F - → v G for some strong reduct v of u.
(

) If u is ≺-minimal with F - → u G, then u is reduced. 2
Definition 6.13. Let A be a subset of M and two vertices a l and a r in A such that a l lies below a r in A. The pair (a l , a r ) is called open in A if there are vertices b and c in A ar a l whose distance in M ar a l is infinite. A pair as before which is not open is called closed. Lemma 6.14. Let s = (l, r) be an interval and M be simply connected. Take a nice subset A of M with two distinguished vertices a l and a r of levels l and r, respectively. Given a flag F in A containing a l and a r , assume that

F - → s G for some flag G in M . Set B = A ∪ G.
If the pair (a l , a r ) is closed in A, we have that:

(1) The set B is obtained from A by a global application of α s on (a l , a r ). Proof. For the first assertion, by Lemma 4.21, we need only check that

d M ar a l (d, A) = ∞,
where d is one of the new vertices of G. Pick any b in A ar a l and choose some vertex c in F between a l and a r . Since (a l , a r ) is closed in A, we have that d one of the new elements of G, then either y is either also in B \ A or in A and either equal to a r or above of it. If both x and y lie in B \ A, they form a closed pair. If y = a r , all vertices between x and y lie on B \ A, and thus the pair (x, y) is closed. If y lies above a r in A, then all vertices between x and y are are connected with a r and thus their distance is finite, so (x, y) is closed.

Hence, we conclude that both x and y lie in A. Suppose (x, y) is not (a l , a r ). Either it was already open in A or there is a vertex d in B \ A whose distance to some b in A is infinite in M y

x . In particular, the vertex x lies below a l and y lies above a r . Since (x, y) is closed in A, the distance between b and a l in M y

x is finite and thus b and d have finite distance in M y

x , which is a contradiction. Flag paths provide scaffolds which are nice sets, as the following Lemma shows. Lemma 6.15. Let M be simply connected and F 0 -→

s 1 F 1 -→ s 2 . . . -→ sn F n be a reduced flag path in M . The following hold: (1) The set A n = F 0 ∪ F 1 ∪ . . . ∪ F n is nice in M . (2) If a 0 -. . . -a N are the vertices of F n , then (a l , a r ) is open in A n if
and only if the letter (l, r) belongs to final segment of s 1 s 2 . . . s n .

Proof. We prove it by induction on n. Let s i = (l i , r i ) and w i = s 1 s 2 . . . s i .

If n = 0, there is nothing to prove, since any flag is nice and the word w 0 is trivial. Suppose hence that n > 0 and let F n = a 0 -. . .-a N . Since w n is reduced by assumption, the letter s n does not belong to the final segment of w n-1 . Therefore, the pair (a ln , a rn ) appeared already in F n-1 and, by induction, it is closed in A n-1 , which is nice. Lemma 6.14 gives that so is A n .

Furthermore, Lemma 6.14 also implies that (a l , a r ) is open in A n if and only if (a l , a r ) = (a ln , a rn ) or it belongs to A n-1 and was already open in A n-1 . In particular, the pair (a l , a r ) belongs to A n-1 if and only if either (l, r) commutes with s n or (l, r) contains s n . Since s n is not contained in the final segment of w n-1 , induction gives that (a l , a r ) is open in A n iff (l, r) = s n or (l, r) commutes with s n and belongs to the final segment of w n-1 , which means that (l, r) belongs to the final segment of w n .

If the space is simply connected, we shall prove that there are no flag loops, unless they are not reduced. Corollary 6.16. If M is simply connected, there are no non-trivial closed reduced flags paths.

Proof. Let F 0 -→ s 1 F 1 -→ s 2 . . . -→ sn
F n a non-trivial reduced flag path. By Lemmata 6.14 and 6.15, the flag F n is obtained by a global application of α sn to F 0 ∪ • • • ∪ F n-1 . In particular, the flag F n must differ from F 0 .

Since there are no loops, the reduced word of a flag path is hence unique, up to permutation. Proposition 6.17. The word of a reduced path between two flags F and G is uniquely determined up to equivalence. Proof. We use induction on the length of P . Let u = v • s be the word of P with s = (l, r). Split P in a path Q from F to G with word v and in the path from G to H with word s. Denote by B the vertices of flags occurring in Q. Consider a flag K ⊂ A. If K ⊂ B, then K occurs in a permutation of Q by induction. Thus, it occurs in a permutation of P . If K B, since u is reduced, the letter s does not belong to the final segment of v, so by Lemma 6.15 implies that the pair (a l , a r ) in K is closed. Lemma 6.14 gives that H is obtained by the operation α s to the nice set B. So K -→ w H, where the reduced word w commutes with s. By Lemma 6.3, there is a unique

G ⊂ B such that G -→ w G and G - → s K. Induction gives that G is part of a reduced path F → G -→ w G, which is a permutation of Q. Then F → G -→ w G - → s H
is a permutation of P . We permute w and s and obtain

F → G - → s K -→ w H, as desired.
Once the word of a flag path between F and G is fixed, the intermediate flags appearing in the path are unique up to wobbling. Lemma 6.19 (Wobbling Lemma). Given two paths between F and G with reduced word

s 1 • • • s i • • • s n , H 1 • • • H n-1 F G, H 1 • • • H n-1 s 1 s 1 s n s n
the flags H i and H i are equivalent modulo Wob(s

1 • • • s i , s i+1 • • • s n ), for ev- ery i in {1, . . . , n -1}. Proof. Write u = s 1 • • • s i and v = s i+1 • • • s n .
Suppose we are given flags H i and H i as in the previous picture. Hence

F - → u H i - → v G F - → u H i - → v G.
Let w be some reduced word with H i -→ w H i . By Corollary 6.12 and Proposition 6.17, the word u is a strong reduct of u • w. Likewise, the word v is a strong reduct of w -1 • v. Proposition 5.36 gives that |w| ⊂ Wob(u, v), which yields the result.

We finish this section by observing that nice sets are flag-connected. Proposition 6.20. Let M be simply connected and A some union of flags from M . The set A is nice if and only if any two flags in A can be connected by a reduced flag path which belongs to A.

Proof. Clearly, any union of flags satisfies that A b a = A ∩ M b a . Suppose it is nice. Consider two flags F and G in A and connect them in M by some weak path. Since A is nice, we can find a weak path P belonging to A which is reduced in the sense of A. In order to show that P is a flag path (in the sense of M ), we need only show that if G is obtained from F by a global application of α s in A, then it remains a global application of α s in M . Equivalently, for any b in

G \ F , if d A s (b, F ) = ∞ then d M s (b, F ) = ∞.
This is exactly the definition of niceness. Assume now that every two flags in A are connected in A by a reduced flag path. Consider two vertices b and c in A s (A) with finite s-distance in M and choose two flags F and G in A containing b and c, respectively. Lemma 6.5 (with t = [0, N ]) and Lemma 6.9 imply that we can connect F and G by a reduced path P with word u whose letters do not contain s. By assumption, there is a reduced flag path P in A connecting F and G as well. Thus, the word of P is a permutation of u by Proposition 6.17. So, again by Lemma 6.5, the points b and c are s-connected in A and hence A is nice.

Forking in the free pseudospace

In this section we provide a detailed description of nonforking over nice sets and canonical bases. In particular, we obtain weak elimination of imaginaries. The theory PS N has trivial forking and is totally trivial, as in [START_REF] Baudisch | A free pseudospace[END_REF].

We will work inside a sufficiently saturated model M . We start with an easy observation which follows immediately from Theorem 4.22.

Proposition 7.1. The theory PS N is ω-stable.

Proof. Work over a countable subset A, which we may assume to be nice. Theorem 4.22 shows that every 1-type over A lies in some nice set B, obtained from A by a finite number of applications α s . In particular, there are countably many quantifier-free types of such B's over A and thus countably many types by Corollary 4.29. The theory PS N is therefore ω-stable.

The following result will allow us to determine the type of a flag over a nice set.

F ---→ u 1 •u F * -→ w G -→ w G * --→ v •v 1 G ,
where G * is a flag in X.

Let b be a strong reduct of w • w connecting F * to G * . If b ≈ w, consider the reduced word c which connects F with G * . Since c is a strong reduct of

u 1 • u • b, we have c u 1 • u • b ≺ u, a contradiction. So b is equivalent to w. We obtain a path from F to G with word u 1 • u • w • v • v 1 . Up to permutation, its only possible strong reduct is u 1 • w • v 1 . So F connects to G by word u 1 • w • v 1 , which is the reduct of u • v.
Definition 7.3. Given a nice set X. We call a flag G in X a base-point of F over X if the conditions of Proposition 7.2 hold: The word connecting F to G is -minimal among words which connect F with flags in X.

Lemma 7.4. Let X be a nice set and F 0 -→

s 1 • • • -→ sn F n be a reduced flag path with F n ∈ X. Then F n is a basepoint of F 0 over X if and only if the flag F i-1 is obtained from F i ∪ . . . F n ∪ X by a global application of α s i for all i ≥ 1.
In particular, if F n is a basepoint of F 0 over X, then F 0 ∪ . . . F n ∪ X is nice.

Proof. The equivalence for n = 1 is clear, since F 0 is obtained by an global application of α s 1 from F 1 ∪ X = X if and only if there is no connection of F 0 to X by a product of proper subletters of s by Lemma 6.5.

Proceed now by induction over n and assume first that each F i-1 is obtained from F i ∪ . . . F n ∪ X by a global application of α s i . Lemma 4.21 implies that Y = F 1 ∪ . . . F n ∪ X is nice. Furthermore, the flag F 1 is a basepoint of F 0 over Y . We will show that property 7.2 (a) holds for F 0 and F n over X. Let G be a flag in X. Choose reduced words x, y and v with

F 0 - → x G , F 1 - → y G and F n - → v G.
Then x is the reduct of s 1 • y and, by induction, the word y is the reduct of

s 2 • • • s n • v. So x is the reduct of s 1 • • • s n • v. Therefore, the flag F n is a basepoint of F 0 over X.
For the other direction, note first that F n-1 is obtained from F n ∪X = X by a global application of α sn . So Y = F n-1 ∪ F n ∪ X is nice. If we can show that F n-1 is a basepoint of F 0 over Y , we can conclude by induction. For that, we will verify 7.2(b). Consider any flag G in Y and let x be the reduced word which connects F 0 to G. If G belongs to X, we have

s 1 • • • s n-1 ≺ s 1 • • • s n x.
Otherwise, there are a flag G in X and a word w commuting with s n such the following diagram holds:

F n-1 F n F 0 G G n-1 j=1 s j x s n s n w
The reduced word x connecting F 0 with G is a strong reduct of x • s n . Minimality of u = s 1 • • • s n yields that u x . Corollary 5.28 gives that s 1 • • • s n-1 x.

Corollary 7.5. Let G be a flag in a nice set X. Given a reduced word u, there is a flag F a path P from F to G with word u such that G is the basepoint of F over X. The set X ∪ P is nice. The type of F over G (and thus, over X) is uniquely determined.

Denote these types by p u (G) and p u (G)|X.

In order to describe the regular types and the dimensions of PS N , we will need a characterisation of nonforking over nice sets in terms of the reduction of the corresponding words connecting the paths. Proof. If F | G H, there is a nice set X containing G and H such that F | G X. But then G is a basepoint of F over X and u • v → w follows. Assume now u • v → w. Take P the reduced path from G to H with word v. The set P is nice. Enough to show F | G P by verifying 7.2(a). Given any flag G in P , by Lemma 6.18, we may assume that G occurs in P . Thus, write

v 1 • v 2 = v with G -→ v 1 G -→ v 2 H. If x is reduced with F - → x G , then u • v = (u • v 1 ) • v 2 * - → x • v 2 * - → w.
By assumption u • v → w, so Proposition 5.32 yields that no splitting occurs in the strong reductions above. This implies that u•v 1 → x, which completes the proof.

Note that the previous proof also yields x • v 2 → w, which will be used in the proof of Lemma 7.19. Furthermore, we have the following:

The Morley rank of u k is at least R div (u k ) = ω 2 . Since p u (G) is the limit of the types p u k (G), its Morley rank of p u (G) is at least ω 2 + 1. Actually, it is easy to show that MR(p u (G)) = ω 2 + 1.

The non-orthogonality classes of regular types over a nice set in PS N are given by global operations of α s for s varying among all intervals. These types have trivial forking and therefore so does PS N .

Theorem 7.15. The theory PS N is ω-stable of rank ω N . Every type over a nice set X is non-orthogonal to some type p s (G)|X, where G lies in X. Forking is trivial, that is, any three pairwise independent tuples are independent (as a set).

Proof. By Lemma 7.11, the Morley rank of a flag cannot exceed R

≺ ([0, N ]) = ω N = U(p [0,N ] (G)) = MR(p [0,N ] (G))
, by Corollary 7.13. Thus, the Lascar and Morley rank of a flag over the emptyset are both ω N . Let a be a vertex of F . Lascar inequalities implie that U(F/a)+U(a) ≤ U(F ). Since U(a) > 0, this implies that U(a) = ω N , and therefore MR(a) = ω N . Given a type p over X, we may assume it is the type of a flag F and thus determined by some reduced word u connecting F a basepoint G over X. In particular, take any s in the final segment of u. The type p is hence nonorthogonal to the type p s (G)|X, since the connecting word of F over the nice set consisting of G together with a realisation of p s (G)|X is ≺-smaller than u.

Since the type p s (G) has monomial Lascar rank, it is regular. A different way to see this is by taking a non-forking realisation F of p s (G)|X and a forking realisation F to X. Now, since F forks with X over G, Proposition 7.2(b) gives a flag G in X such that the word connecting F to G is a finite product x of proper subletters of s. Since the reduction s • x * -→ s involves no splitting, the flags F and F are independent over G by Proposition 7.7. The type p s (G) is regular, and so is p s (G)|X.

Note that the geometry on every type p s (G) is trivial: given three pairwise independent realisations F 1 , F 2 and F 3 of p s (G), note that any flag in G ∪ F 2 ∪ F 3 must be either G, F 2 or F 3 , for there are no new s-connections between them. Hence, We finish the section with a strengthening of triviality, called totally trivial [START_REF] Goode | Some trivial considerations[END_REF], that is, given any set of parameters X and tuples a, b and c such that a is both independent from b and c over X, then it is independent from {b, c} over X. For theories of finite U-rank, both notions agree [6, Proposition 5].

F 1 | G F 2 ∪
By Lemma 7.6, recall that, given a nice set X and a distinguished flag F 0 in X, the following are equivalent for any flag F ,

• F | F 0 X • F | F 0 H for every flag H in X • F 0 is a basepoint of F over X.
Whilst considering flag paths, there is a simpler version of transitivity of nonforking, due to the nature of the reduction with non splitting. Lemma 7.19. Given flags H, F , H 0 and F 0 , then

F | F 0 H 0 and F | H 0 H imply F | F 0 H. If there is a reduced path F 0 - → v H 0 -→ w H, the converse also holds: F | F 0 H implies F | F 0 H 0 and F | H 0 H.
Observe that the condition on the path being reduced is needed for the converse, as the following example shows, where t s:

F 0 H 0 H F s t s s t s
Although F | F 0 H, since no splitting occurs when reducing s • t to s, we have that F | F 0 H 0 , as t is not the reduct of s • s.

Proof. We will use throughout the proof the characterisation of independence between flags given by Proposition 7.

F 0 , F 0 - → v H 0 , H 0 -→ w H and F 0 - → x H.
The word a which connects F to H 0 is the reduct of u • v. Also, the word b connecting F to H is the reduct of u • w. Hence, the word b is the reduct of u • v • w. If x were the reduct of v • w, then b is the reduct of u • x, so we are done. Therefore, suppose that splitting occurs in v • w * -→ x. Treat first the case v = w = s. Then x is a product of proper subintervals of s. By the Decomposition Lemma 5.13, either s is right absorbed by u, or u = u 1 • u , where u is properly absorbed by s and u 1 • s is reduced. In the first case, the word x is properly absorbed by u, hence F | F 0 H. For the second case, decompose u = u 1 • u as above. Then b (the word connecting F and H) equals u 1 •s. This cannot be a strong reduct of u 1 •u •x, since the latter is ≺-smaller, contradicting Proposition 5.32.

For the general case, as in the proof of Proposition 5.32).we may assume that the splitting in v • w * -→ x happens at the first step of the reduction. Write hence v = v • s and w = s • w , where

F 0 -→ v K 1 - → s H 0 - → s K 2 -→ w H.
The word y connecting K In order to prove the total triviality of PS N , we will use the following lemma, a stronger form of which follows already from total triviality, without the assumption Thus, as a is a reduct of u•x, it follows that s commutes with x and is in the final segment of u. In particular, the word x • s is reduced, which implies that v is (up to permutation) the word x • s.

F 0 | A B, since if A - → s B - → t C,
F | F 0 A , F | F 0 C and F 0 | A B, then F | F 0 B. Proof. In order to show that F | F 0 B, since F | F 0 A,
On the other hand, the word v = x • s is a strong reduct of y • t. It is easy to see that this can only be possible if (after permutation) y has the form y • s,where y and s commute. The independence F | F 0 C implies that b is the reduct of u • y. Hence s still belongs to the final segment of b. Finally, since z is a strong reduct of b•t, the word s must belong to the final segment of z, which contradicts that F | A B.

In order to ensure the independence of a flag with respect to a whole flag path over a nice set, it is enough to check the independence with respect to the set itself and the end flag of the path. H . For the general case, we will proceed by induction on the length of P , based on the above paragraph. Thus, it suffices to consider the case where P has length 1 and let s be its letter:

H 0 - → s H.
If H is a flag in A ∪ P not completely contained in A, it differs from H only on the indices outside s. As in the proof of Lemma 6.18, we can find a reduced word w commuting with s such that H -→ w H. Furthermore, there is some flag H 0 in A with H 0 -→ w H 0 and H 0 -→ s H .

Note that H 0 is again a basepoint of H over A, so in particular F 0 | H 0 H . By induction on the length of w, we may assume that w is a letter t. Setting A = H 0 , B = H and C = H, the hypotheses of Lemma 7.20 are satisfied. We conclude that F | F 0 H , which gives the desired result.

We now have all the ingredients to prove total triviality of forking.

Proposition 7.22. The theory PS N is totally trivial, that is, given any set of parameters X and tuples a, b and c such that a is both independent from b and c over X, then it is independent from {b, c} over X. In particular, the canonical base of a tuple is the union of the canonical bases of each singleton.

Proof. We may assume that our parameter set X is nice, by choosing a small model containing it independent from a, b, c. Suppose first that the tuples a, b and c consists of singletons: By transitivity, choose flags H 1 and H 2 independently from a over X containing b and c respectively. Choose now a flag F containing a independently from H 1 and from H 2 over X. We need only to show that

F | X H 1 ∪ H 2 .
Let F 0 and H 0 be basepoints of F and H 1 respectively over X. Since F | F 0 X and F | X H 1 , we have that F | F 0 X ∪ P 1 by Lemma 7.21, where P 1 denotes the reduced flag path (connecting H 1 to H 0 ) determined by H 1 over X. The set X ∪ P 1 is again nice by Lemma 7.4. Work now over X ∪ P 1 in order to show that F | F 0 X ∪ P 1 ∪ P 2 , where P 2 is the flag path given by H 2 over X ∪ P 1 . Lemma 7.21 gives that F is independent from H 1 ∪ H 2 over X.

Transitivity of forking allows us to work with finite tuples by choosing accordingly nonforking extensions for each coordinate. The result now follows by local character.

Since PS N is superstable, [START_REF] Goode | Some trivial considerations[END_REF]Proposition 7] allows to conclude the following.

Corollary 7.23. The theory PS N is perfectly trivial, that is, given given any set of parameters X and tuples a, b and c such that a and b are both independent over X, then so are they over X ∪ {c}.

Corollary 7.24. The theory PS N has weak elimination of imaginaries.

Proof. By Proposition 7.22, in order to study the canonical base of a real tuple ā over an algebraically closed set B (in PS eq N ), we may assume that ā is an enumeration of a flag F . Furthermore, we may suppose that B is nice. By Theorem 7.17, the canonical base is interdefinable with a finite set, thus we get weak elimination of imaginaries.

Although the theory PS N is not 1-based, being N -ample by Proposition 8.1, it is 2-based, i.e. the canonical base of a type is determined by two independent realisations. Proposition 7.25. Let u be a reduced word and X a nice set. The canonical base of p u (G)|X is algebraic over two independent realisations. Proof. Let F and F be realisations of p u (G)|X, which are X-independent. Since the base-point is only determined up to S R (u)-equivalence, pick a common base-point G in X for both F and F .

As F | X F and F | G X, combining Lemmas 7.19 and 7.21, we conclude that F | G F . Therefore, the word connecting F and F is the reduction of u • u -1 . Write u = u 1 ũ, where ũ is the final segment of u. Hence,

u • u -1 → u 1 • ũ • u -1
1 , as the diagram shows:

Note that G and H are equivalent modulo |w| ⊂ S R (u). By Lemma 6.19, the flag H is determined by F and F modulo S R (u) ∩ S L (u -1 1 ) and thus, modulo S R (u). In particular, the canonical base G/S R (u) is algebraic over F, F . This last section shows that the ample hierarchy defined in 2.2 is proper, since the theory of the free N -dimensional pseudospace PS N is N -ample but not (N + 1)-ample. We will furthermore show that it is N -tight with respect to the family Σ of Lascar rank 1 types, if N ≥ 2.

The proof that PS N is N -ample is a direct translation of the proof exhibited in [START_REF] Baudisch | A free pseudospace[END_REF], which we nontheless include for the sake of the presentation. (a) acl eq (a 0 , . . . , a i )∩acl eq (a 0 , . . . , a i-1 , a i+1 ) = acl eq (a 0 , . . . , a i-1 ) for every 0 ≤ i < N . (b) a i+1 | a i a 0 , . . . , a i-1 for every 1 ≤ i < N . (c) a N | a 0 .

In particular, the theory PS N is N -ample.

Proof. In order to prove (a), fix some i < N and choose parameters b i , . . . , b N independently from a i , a i+1 such that

a 0 -• • • -a i-1 -b i -• • • -b N
is a flag. Set X = {a 0 , . . . , a i-1 , b i , . . . , b N }, which is nice.

By Fact 2.1, assume for a contradiction that there is an element e in acl eq (X, a i ) ∩ acl eq (X, a i+1 ) \ acl eq (X).

Choose now a i realising tp(a i /X, e). Since the element e lies also in acl eq (X, a i ), then a i | X a i . As the -minimal word connecting a i (or rather, the flag a 0 -• • • -a N ) to X is [i, N ], it follows from Lemma 7.6 that a i and a i (or rather, generic flags containing them) are connected through a finite product of proper intervals of [i, N ]. Compactness (and Lemma 6.5) implies that there exists a natural number n such that tp(a i /X, e) |= d [i,N ] (x, a i ) ≤ n.

Let m be such that 2m > n. Consider the reduced word

u = [i + 1, N ] • i • • • [i + 1, N ] • i 2m .
Corollary 7.5 provides us with a flag F and a path P from G = a 0 -• • • -a N to F with word u

F = F 0 ----→ [i+1,N ] F 0 - → i F 1 ----→ [i+1,N ] • • • ----→ [i+1,N ] F m-1 - → i F m = G
such that G is the basepoint of F over the nice set G. Since the F i and F i are connected by the word [i, N ] to G, they have all the same type over X. Denote

F r = a 0 -• • • -a i-1 -a r i -a r i+1 -• • • -a r N F r = a 0 -• • • -a i-1 -a r i -a r+1 i+1 -• • • -a r+1 N .
Since F 0 and F 0 have the same type over X, they have also the same type over Xa 0 i and therefore over Xe. This implies that e belongs to acl eq (Xa 1 i+1 ). Similarly, the flags F 0 and F 1 have the same type over Xa 1 i+1 and therefore over Xe, which implies that e belongs to acl eq (Xa 1 i ). Iterating, we see that a m i has the the same type over Xe as a i . This implies that d [i,N ] (a m i , a i ) ≤ n, which gives a contradiction since the shortest path between a i and a m i in A [0,N ] is Before the proof that PS N is not (N + 1)-ample, we need some auxiliary results on the nature of the reduced words arising from the hypothesis on ampleness.

a 0 i -a 1 i+1 -a 1 i -• • • -a m i+1 -a m i , of length 2m.
the minimal word connecting F to a flag G B in B (resp. G A in A) (These are the same hypotheses as in Lemma 8.2). Then, either F | A∩B AB or u is nontrivial and its final segment ũ, as a set of indices, is strictly contained in ũA , the final segment of u A .

In particular, consider the reduced word v which connects G B to G A and the associated fine decomposition

u = u 1 • u , v • v 1 = v,
u = u 1 • u v • v 1 = v.
is the fine decomposition (cf. Theorem 5.13) applied to u and v, we may thus assume that u A = u 1 • v 1 .

Let H be the flag in the path G B -→ v G A between v and v 1 . Likewise, let K be the flag in the path F -→ u A G A between u 1 and v 1 . Note that H and K are connected through u . Furthermore, Lemma 5.18 gives that Wob(v , v 1 ) is contained in W = Wob(u 1 , v 1 ). Since H and K are equivalent modulo |u | and H/Wob(v , v 1 ) lies in acl eq (AB) by Lemma 6.19, it follows that K/(W ∪ |u |) lies in acl eq (AB) ∩ acl eq (AF ) = acl eq (A) and whence in A by Remark 7.16. Lemma 7.18 gives now

|v 1 | ⊂ |u | ∪ W.
Decompose the final segment of u as ũ = w 1 • w 2 , where w 2 is the final segment of u and w 1 is a subword of the final segment of u 1 . In particular u = u • w 2 and w 1 and u commute. We show first that w 1 and v 1 commute: since u ⊂ C(w 1 ) and W ⊂ S R (u 1 ) ⊂ |w 1 | ∪ C(w 1 ), we have v 1 ⊂ |w 1 | ∪ C(w 1 ). A letter s of v 1 cannot be contained in |w 1 |, since u 1 •v 1 is reduced. So s belongs to C(w 1 ), which gives the desired result. Recall that v 1 is commuting by Lemma 8.2. Thus, the final segment of

u A = u 1 • v 1 is ũA = w 1 • v 1 ,

a n- 1 | a 0 ,

 10

Lemma 3 . 3 .

 33 A Fraïssé limit M has the following properties: (a) ∅ ≤ r M (b) for every finite A ≤ r M and every B in K such that A ≤ B, there is an r-strong subset B of M containing A and isomorphic to B over A.

Corollary 3 . 4 .

 34 Assume that M and M are Fraïssé limits. Given sets B ≤ r M and B ≤ r M , every isomorphism B → B extends to an isomorphism M → M .

Definition 4 . 3 .

 43 Given an interval s = (l s , r s ) (where -1 and N +1 are possible values) in {0, • • • , N } and a colored N -space A with two distinguished vertices a ls in A ls (A) beneath a rs in A rs (A), we say that B = A∪{b i | i ∈ s} with b i ∈ A i (B) is obtained from A by applying the operation α s on (a ls , a rs ) if (a) The sequence a ls , b ls+1 , . . . , b rs-1 , a rs is a path in B. (b) B has no new edges besides the aforementioned (and those of A).

Remark 4 . 4 .

 44 If both B 1 and B 2 are obtained from A by applying respectively α s 1 and α s 2 , then the graph-theoretic amalgam C = B 1 ⊗ A B 2 is obtained by applying α s 1 to B 2 and α 2 to B 1 . Definition 4.5. Given two colored N -spaces A and B, we say that A a strong subspace of B if A is a subgraph of B and B can be obtained from A by a (possibly infinite) sequence of operations α s for varying s. We denote this by A ≤ B.

Definition 4 . 15 .

 415 We will denote by PS N the collection of sentences expressing properties (1) and (2) in Theorem 4.14. Definition 4.16. A flag is a subgraph of a colored N -space M of the form a 0 -. . . -a N ,

( 1 )

 1 satisfies the following: For any two (possibly imaginary) points a and b in D, D b a = D ∩ M b a .

Lemma 4 .

 4 18. If A ≤ B, then A is wunderbar in B.

Lemma 4 .

 4 19. Let M be a simply connected colored N -space and D nice in M . Given an interval s = [l, r] in {-1, . . . , N + 1} and a l ∈ A l (D) beneath a r ∈ A r (D), the set D ar a l is nice in A s (M ).

  a l , b l+1 , . . . , b r-1 , a r , passing through b. By Lemma 4.21, the set A ∪ {b l+1 , . . . , b r-1 } obtained from A by applying α s is nice and contains b.

Corollary 4 .

 4 32. Nice sets are algebraically closed.

Definition 5 .

 5 24. The word u is strongly reduced to v, denoted by u * -→ v, if v is obtained from u by finitely many iterations of Cancellation, Commutation, and Splitting: Replace an occurrence of s • s by a (possibly trivial) product t 1 • • • t n of letters t i , each of which is properly contained in s.

( 1 )

 1 ≺ is transitive and well-founded. (2) u ≈ u ≺ v ≈ v implies u ≺ v . (3) If the strong reduction u * -→ v involves at least one cancellation or splitting, we have v ≺ u.

  reductions from a given one, as long as products are involved. Proposition 5.33 (Triangle Lemma). Let a, b and c be reduced words. Then a • b *

  where s is properly left-absorbed by b. Since b is the only strong reduct of s • b, the Commutation Lemma 5.31 gives that

Proposition 5 .

 5 36. Let u • v and w be reduced. If u • w * -→ u and w

( 2 )

 2 The open pairs in B are exactly the open pairs of A together with (a l , a r ).

  M ar a l (b, c) < ∞. Since F -→ s G, Lemma 6.5 shows that d M ar a l (c, d) = ∞. In particular, d M ar a l (b, d) = ∞, which gives the desired result. For the second assertion, clearly (a l , a r ) is now open in B. We need only show there are no new open pairs in B. Consider an open pair (x, y). If x is

Proof.G

  If u and v are both reduced and there are two flag paths F -→ connecting F and G, composing them we get a weak path F -F with word u • v -1 . Corollary 6.12 yields a strong reduct w of u • v -1 with F -→ w F . Corollary 6.16 implies that w = 1 and thus u ≈ v by Corollary 5.34.If u is reduced, we will sometimes refer to F -→ u G by saying that the reduced word u connects F to G. Lemma 6.18. Let M be simply connected and P be a reduced flag path in M . Denote by A the set of vertices of flags occurring in P . Every flag contained in A appears in some permutation of P .

Proposition 7 . 2 .

 72 Let X be a nice set and F a flag which is connected to a flag G in X by a reduced flag path P with word u. The following are equivalent: (a) Let v by a reduced word connecting G to another flag G in X. Then F is connected to G by the reduct of u • v. (b) u is the -smallest word connecting F to a flag in X. (c) u is -minimal among words connecting F to a flag in X. Proof. (a)→(b) follows from Corollary 5.30. (b)→(c) is trivial. (c)→(a): Let G be any flag in X. Then G is connected to G by a flag path P with word v. By Proposition 6.20, we may assume that P in X. Choose a decomposition u = u 1 • u • w and w • v • v 1 = v as in Corollary 5.23, with corresponding paths

Lemma 7 . 6 .Proposition 7 . 7 .G

 7677 Let F and G be flags, where G lies in a nice set X. The independence F | G X holds if and only if G is a basepoint of F over X.Proof. Let u be the reduced word which connects F to G. Then the type p u (G) of F over G has a canonical extension p u (G)|Y to every nice set Y which contains G. Since PS N is stable, it follows that p u (G)|X is the only non-forking extension of p u (G) to X. Given three flags with reduced paths F -→ u we have that F | G H if and only if u • v → w.

  by Lemma 7.19, we need only show F | A B. Thus, consider a reduced word z with F -→ z B and connect the above flags by reduced paths as in the diagram below. Assume for a contradiction that F | A B. Then z, which is a strong reduct of a • s, is not the reduct of a • s. This has two consequences: first, the letter s does not occur in the final segment of z. Secondly, up to permutation, the path F -→ a A ends with a flag A -→ s A, such that A is connected to B by a word consisting of proper subletters of s. Since F 0 | A B, such a flag A cannot occur in any permutation of x.

8 .

 8 Ample yet not wide ample

Proposition 8 . 1 .

 81 Consider a flag a 0 -• • • -a N . We have the following:

For

  (b), chose generic flags F containing a i+1 and G containing a 0 , . . . , a i . The canonical base Cb(a i+1 /a 0 , . . . , a i ) equals Cb(F/G). On the other hand, the flags F and G are connected by the reduced word u= [0, i][i + 1, N ]. So Cb(F/G) = G/S R (u) = G/ [0, i -1] ∪ [i + 1, N ] = a iby Theorem 7.17, which gives the desired independence.

For

  (c), choose a generic flag F which contains a N and a generic flag G which contains a 0 . Then Cb(a N /a 0 ) equals Cb(F/G). On the other hand the reduced word connectingF to G is u = [0, N -1][1, N ], So Cb(F/G) = G/S R (u) = G/[1, N ] = a 0 ,which is clearly not algebraic over a 1 . Thus, a N | a 0 .

  then ũ is nontrivial and|v | |ũ| |ũ A |. Proof. Since F | B A and v is reduced connecting G B to G A , the word u • v reduces to u A . If

  • • • s m and with t 1 • • • t j-1 and it is contained in t j . • There are j ≤ n and i ≤ m such that t j commutes with t 1 • • • t j-1 and with s i+1 • • • s m and it is contained in s i . Based on the previous observation, we introduce the following definition. Definition 5.7. Given two words u = s 1 • • • s m and v = t 1 • • • t n words, we say that: (1) s i belongs to the final segment of u if s i commutes with s i+1 • • • s m .

[START_REF] Baudisch | A free pseudospace[END_REF]

The letter s is (properly) left-absorbed by v if it commutes with with t 1 • • • t j-1 and is a (proper) subset of t j for some j ≤ n. A word is (properly) left-absorbed by v if all its letters are (properly) left absorbed by v.

(3) v bites u from the right if v left-absorbs some element in the final segment of u.

  F 3 and forking is trivial on each p s (G)|X. Since the theory is superstable, forking is trivial [6, Proposition 2]. Nice sets are algebraically closed in PS eq N . If H/A ∈ X for some set A ⊂ [0, N ], then |v| is a subset of A. Proof. By Remark 7.16 and Corollary 6.12, there is a flag G in X connected to H by a reduced word |v | ⊂ A. The flag G is a basepoint of H over X by Lemma 7.4. Proposition 7.2 (b) gives that v v and therefore |v| ⊂ |v | ⊂ A.

  0 | H 0 H by Proposition 7.7. This, together with F | F 0 H, the first part of the lemma and forking symmetry implies F | H 0 H. Assume now F | F 0 H 0 and F | H 0 H. Choose reduced paths F -→

	u

[START_REF] Hrushovski | A new strongly minimal set[END_REF]

. It actually follows from the proof of Proposition 7.7 that the above converse holds, by taking F , G, G , H instead of H, F , H 0 , F 0 in the proof. Alternatively, we may argue as follows: as H 0 occurs in a reduced path P from F 0 to H, the proof of Proposition 7.7 shows that F | F 0 P . This implies

F | F 0 H 0 . Since F 0 -→ v H 0 -→ w H, we

have that F

  1 and K 2 consists of proper subletters of s. By the first part of the proof, since F | F 0 H 0 , we have that F | F 0 K 1 and F | K 1 H 0 . Similarly, we obtain F | H 0 K 2 and F | K 2 H. By the previous discussion, we have that F | K 1 K 2 . This, together with F | F 0 K 1 , yields F | F 0 K 2 , by induction on the length of v. Now, the word connecting F 0 -→ K 2 is a strong reduction of v • y, so ≺-smaller than v. Induction on the complexity of v together with F | K 2 H gives F | F 0 H, as desired.

  where s and t commute with each other, then B is definable in A ∪ C, by Lemma 6.19.

Lemma 7.20. Let A, B, C, F , F 0 be flags and s and t two commuting letters, such that A -→ s B -→ t C. If the following independencies hold:

  Lemma 7.21. Let A be a nice set and a reduced path P connecting a flag H to a basepoint in A. Given a flag F 0 in A and a flag F , we have that F | F 0 Since A ∪ P is nice byLemma 7.4, in order to check that F | F 0 A ∪ P , we need to check that F | F 0 H for any flag H in A ∪ P by the remark above Lemma 7.19. This is clear for flags in A, so let H be in A ∪ P but not in A. We treat first the case where H is in P . Let H 0 be the base-point of H in A. We have then that F 0 | H 0 H and F | F 0 H by assumption, which implies F | H 0 H by Lemma 7.19. Since the path P is reduced, Lemma 7.19 gives F | H 0 H , which together with F | F 0 H 0 implies F | F 0

A ∪ P if and only if F | F 0 A and F | F 0 H. Proof. Left-to-right is clear. Assume now that F | F 0 A and F | F 0 H.

Acknowledgements. The second author conducted research with support of programme ANR-09-BLAN-0047 Modig as well as an Alexander von Humboldt-Stiftung Forschungsstipendium für erfahrene Wissenschaftler 3.3-FRA/1137360 STP.

where P is the reduced flag path connecting G to H.

We will now compute the Morley rank MR(p) and Lascar rank U(p) of certain types in PS N . Definition 7.9. Given reduced words u and v, we say that u is a proper left-divisor of v if u ≈ v and there is a reduced w such that uw = v in Cox(N ).

If u is a proper left-divisor of v, it follows by Corollary 5.30 that u ≺ v. In particular, Lemma 5.26 yields that being a proper left-divisor is wellfounded. Let R div be its foundation rank and likewise let R ≺ denote the foundation rank with respect to ≺. Lemma 7.10. For every flag G and every reduced word u,

Proof. Show U(p u (G)) ≤ R div (u) by induction on R div (u). Assume that α < U(p u (G)). Then there is is a nice extension X of G and a realisation F of p u (G) such that α ≤ U(F/X). Since F | G X, the type of F over X is of the form p v (H)|X for a reduced word v and some flag H in X. Proposition 7.2 (a) and Lemma 7.6 imply that v is a proper left-divisor of u. By induction, we have

For the other direction, assume α < R div (u). Then there is a proper left-

Actually, such an H exists whenever v • w * -→ u. By Proposition 7.7 we have F | H G. Let P be a path from H to G with associated word w. Seen as a collection of points, the path P is nice by Lemma 6.15. Corollary 7.8 gives that F | H P , so tp(F/P ) = p v (H)|P and thus F | G P . By induction,

Lemma 7.11. For every flag G and reduced word u, we have that

Proof. Extend p u (G) to p = p u (G)|X, where X is an ω-saturated model containg G. The type p contains a formula ϕ(x) stating that there is a weak path connecting the flag x to G with word u. If F realizes ϕ, then either F realizes p or there is a path connecting F to X with word ≺-smaller that u. For the latter, induction gives that the Morley rank of F over X is strictly smaller than R ≺ (u). Since X is ω-saturated, this implies that MR(p) ≤ R ≺ (u). Lemma 7.12.

Proof. Let ord be the function introduced in the proof of Lemma 5.26. Recall that for any reduced word w

If u satifies the above hypotheses, then ord(u

. Hence, we need only that ord(u) ≤ R div (u). By induction, it is enough to find, for every α < ord(u), a proper left-divisor u of u satisfying the hypotheses of the Lemma such that α ≤ ord(u ).

There are two cases: If

Corollary 7.13. For every flag G and every reduced word

However, Lascar and Morley rank may differ in general, as the following example shows.

In particular, the Lascar rank of p u (G) is ω 2 . To compute the Morley rank of p u (G), consider the following sequence of words

Remark 7.16. Let X be nice and F be a flag with F/A ∈ acl eq (X) for some set A ⊂ [0, N ]. Then, the class F/A lies in X eq . That is, all vertices of F with level outside A belong to X.

Proof. Let u be the reduced word connecting F to a basepoint G over X. By taking a sufficiently large initial segment of a sequence of X-independent realisations of tp(F/X), since the class F/A is algebraic, we may find another realisation F with F | G F and F/A = F /A. By Lemmata 6.3 and 6.9, there is a path connecting F and F whose reduced word v satisfies |v| ⊂ A. Proposition 7.7 and the independence

In particular, the flags F and G are equivalent modulo A.

Let us now explicitly describe canonical bases of types over nice sets. They are interdefinable with finite sets of real elements and hence PS N has weak elimination of imaginaries (cf. Corollary 7.24). Theorem 7.17. Let u be a reduced word and G a flag. Then the canonical base of p u (G) is interdefinable with G/S R (u).

Observe that G/S R (u) is interdefinable with a finite set by Definition 6.2.

Proof. We have to show that p u (G) and p u (G ) have a common nonforking extension if and only if G and G are equivalent modulo S R (u). Or, in other words, given a nice set

If v is a reduced word connecting G and G , then G/S R (u) = G /S R (u) means that |v| ⊂ S R (u), or equivalently by Lemma 5.11, that v is rightabsorbed by u. Let w be the reduced word connecting F to G . Then w is the reduct of u•v by Proposition 7.2(a). The flag G is a basepoint of F if an only if w ≈ u. By Corollary 5.14, this is equivalent to v being right-absorbed by u.

The following result will be useful in order to prove that the theory PS N is not (N + 1)-ample.

Lemma 7.18 (Basepoint Lemma). Let X be a nice set and F connected by a reduced word u to its basepoint G in X. Assume u = w • v and pick a flag

Lemma 8.2. Consider nice sets A and B and a flag F such that acl eq (AB)∩ acl eq (A, F ) = acl eq (A) and F | B A. Let u = u B (resp. u A ) be theminimal word connecting F to a flag G B in B (resp. G A in A) and let v be the reduced word connecting

is the fine decomposition as in Theorem 5.13, then v 1 is commuting.

Proof. By hypothesis, F | G B

G A , so the product u 1 • v 1 is equivalent to u A . Suppose for a contradiction that v 1 is not commuting. Hence, we may decompose

, where v 2 1 is the final segment of v 1 and s does not commute with v 2 1 . By Lemma 5.9, we can write u = u 2 • u 1 , where u 1 is left-absorbed by v 1 1 • s, the word u 2 commutes with v 1 1 • s and is left-absorbed by v 2 1 . We have the following diagram:

where the path connecting K and H is given by u 2 . So the flags H and K are equivalent modulo |u 2 |.

Lemma 5.18 gives that Wob(v

). In particular, by Lemma 6.19, the class H/W lies in acl eq (AB). So does K/(|u 2 | ∪ W ), which also lies acl eq (AF ). By assumption, K/(|u 2 | ∪ W ) lies in acl eq (A) since acl eq (AB) ∩ acl eq (AF ) = acl eq (A), and therefore in A by Remark 7.16. Since u A is -minimal connecting F to a flag in A, Lemma 7.18 implies

1 must commute with s, which contradicts the definition of v Finally, assume that ũ = 1, which forces u = 1 and thus v = 1. In particular, since

We can now state and prove the desired result.

Theorem 8.4. The theory PS N is not (N + 1)-ample and is N -tight with respect to the family of Lascar rank 1 types. Proof. By Remark 2.5, we need only show that given tuples b 0 , . . . , b N +1 with:

By Fact 2.1, it suffices to prove this for tuples b 0 , . . . b N which enumerate small models B 0 , . . . B N , although for the proof, we only require that each B i is nice. Total triviality (cf. Proposition 7.22) allows us to assume that b N +1 consists of a single flag F . Choose for every i ≤ N a basepoint F i for F over B i . Note that we obtain the following configuration: such that u i • v i reduces to u i-1 , for every i in {1, . . . , N }, due to (b). Proposition 8.3 implies that either, for some i < N ,

or the final segment ũi+1 of u i+1 is non-trivial and strictly contained in ũi for all i < N .

The second possibility for every i < N delivers a strictly increasing sequence of length N + 1 of non-empty subsets of {0, . . . , N }, which implies that ũ0 equals [0, N ] and thus u 0 = [0, N ]. Hence

and thus

B 0 .

The first possibility implies

as desired. This proves that PS N is not (N + 1)-ample.

Suppose now that N ≥ 2. In order to show that PS N is N -tight with respect to Σ, where Σ denotes the collection of all Lascar rank 1 types, assume we are given tuples b 0 , . . . , b N witnessing the following conditions:

As in Remark 2.5, it follows that:

(c) acl eq (b i+1 ) ∩ acl eq (b i ) ⊂ acl eq (b 0 ) for every 1

Note that (almost) internality is preserved under taking nonforking restrictions. Furthermore, if a tuple d is (almost) internal over C and e is algebraic over Cd, then so is e (almost) internal over C. Thus, we may as before replace every b i by a nice set B i by Fact 2.1 and assume that b N is a flag F by total triviality (cf. Proposition 7.22). In particular, we need to prove that Cb(F/B 0 ) is almost Σ-internal over B 1 .

As before, let u i be -minimal connecting F to a flag F i of F in B i for i < N . Since N ≥ 2, there is (at least) one triangle to apply Proposition 8.3 and thus, either for some 0 ≤ i < N -1 we have that

or the final segment ũi+1 of u i+1 is non-trivial and strictly contained in ũi for every i < N . The independence

implies by properties (b) and (c) that F | acl eq (B 0 )∩acl eq (B 1 ) B 0 . So Cb(F/B 0 ) is algebraic over B 1 , and hence internal over B 1 .

Otherwise, if