On ℵ_{0}-categorical weakly o-minimal structures

B.Herwig, H.D.Macpherson, G.Martin,

A.Nurtazin, and J.K.Truss^{1}.

Abstract

ℵ_{0}-categorical o-minimal structures were completely described in [4], and are essentially built up from copies of the rationals as an ordered set by ‘cutting and copying’. Here we investigate the possible structures which an ℵ_{0}-categorical weakly o-minimal set may carry, and find that there are some rather more interesting (and not o-minimal) examples. We show that even here the possibilities are limited. We subdivide our study into the following principal cases: the structure is 1-indiscernible, in which case all possibilities are classified up to binary structure; the structure is 2-indiscernible, classified up to ternary structure; the structure is 3indiscernible, in which case we show that it is k-indiscernible for every finite k. We also make some remarks about the possible structures of higher arities which an ℵ_{0}-categorical weakly o-minimal structure may carry.

1 Introduction

For any linearly ordered set (X, <) an open interval is a subset of the form (a, b) = {x ∈ X : a < x < b} for some a, b ∈ X ∪{±∞}. Similarly we may define closed or semi-closed intervals, so that for instance a point of X is itself a (trivial) closed interval. A subset C of X is convex if x < z < y ∧ x, y ∈ C ⇒ z ∈ C. Thus a set is convex if it is an interval whose endpoints are now allowed to lie in the order-completion \overline{X} of X.

We recall that a structure M is said to be o-minimal if there is a relation < in its signature which linearly orders M (the domain of M), and such that every definable subset of M is a finite union of intervals, and it is weakly ominimal if every definable subset of M is a finite union of convex subsets. The easiest example of an o-minimal structure is the ordered set of rational numbers, and this is also ℵ_{0}-categorical. An important and non-ℵ_{0}-categorical example is afforded by the field of real numbers. It was shown in [4] that all ℵ_{0}-categorical o-minimal sets can be built up in a fairly straightforward way (by cutting, duplicating, and taking suitable disjoint unions) from (ℚ, <).

1Research supported by European Union Grant INTAS-93-3547 and EPSRC Grant GR/K60503.

If we relax the requirement of o-minimality to weak o-minimality, but still require ℵ_{0}-categoricity, then as we shall see, the class of structures is somewhat broadened, but it is still possible to give substantial structural information without too much trouble. Our discussion proceeds by way of the degree of indiscernibility possessed by the structure. By the Ryll-Nardzewski Theorem, if M is ℵ_{0}-categorical then for each k it has only a finite number of k-types of increasing k-tuples, and saying it is k-indiscernible just means that this number is 1.

Any ℵ_{0}-categorical structure is a finite union of 1-indiscernible pieces (the realizations of the 1-types), so it is natural to begin our investigations by assuming 1-indiscernibility. Here the easiest example of a weakly o-minimal structure which is not also o-minimal has domain consisting of ℚ copies of ℚ, (that is, ℚ × ℚ ordered lexicographically), with an equivalence relation ∼ with convex classes saying that elements lie in the same copy of ℚ. Because ∼ is in the language, each equivalence class is definable (with just one parameter), but its endpoints do not lie in the structure, and so o-minimality fails. It is almost as easy to see that this structure is weakly o-minimal and ℵ_{0}-categorical. The construction immediately generalizes to the lexicographic ordering on ℚ^{n} with a chain of equivalence relations. The main result of §2 is that these are essentially the only possible 1-indiscernible ℵ_{0}-categorical weakly o-minimal structures, at any rate if we restrict attention to the binary theory. One can build more general ℵ_{0}-categorical weakly o-minimal structures from these much as in [4] for the o-minimal case, and it should be possible to describe all possibilities (up to binary theory). We do not go into details here, which will be more involved than in [4], since there are ℵ_{0} possible ‘building blocks’ (the ℚ^{n} with the relations mentioned above), rather than just one. The method we adopt throughout most of the paper for looking at these structures is to view them as ultrametric spaces with a finite set of possible distances, and indeed they may be viewed as having been constructed by a Fraïssé-style method among ultrametric spaces with specified finite set of possible distances. An alternative and essentially equivalent method analyses the structure of the cuts in the order-completion of the structure defined by the 2-atoms of increasing pairs.

In §§3 and 4 we carry out a similar analysis for the next stage up, constructing examples of 2-indiscernible ℵ_{0}-categorical weakly o-minimal structures, and classifying them up to ternary theory. Once again the two methods of visualization used in the previous case can be applied. Here we also use the key notion of a C-relation from [1]. In a similar way that a general 1-indiscernible ℵ_{0}-categorical weakly o-minimal structure is constructed from a chain of equivalence relations, here a general structure is constructed from a chain of C-relations, or more exactly, ‘ordered’ C-relations. Along with any C-relation comes a notion of two points being ‘close’ with respect to a third, and so a family of ultrametrics also naturally occurs. Since, by [1], C-relations may be viewed as branches through a tree under a natural ternary relation, it is not surprising that the construction actually proceeds by way of a suitable tree, with the branches carrying the structure of a 1-indiscernible ℵ_{0}-categorical weakly o-minimal set. In principle it would be possible to carry out the classification proof for these structures by showing that one can interpret the tree used in their construction. In fact we use a different method, which involves formulating a list of axioms, which we show are true in any 2-indiscernible ℵ_{0}-categorical weakly o-minimal structure, and which characterize the structure uniquely up to isomorphism (assuming countability).

In the remaining sections we show that if an ℵ_{0}-categorical weakly o-minimal structure is 3-indiscernible, then it is k-indiscernible for all k, so that its automorphism group is isomorphic as a permutation group to Aut(ℚ, <) (§5), and that the structures we have constructed may be modified by including a wide variety of relations of higher arities (§6). In particular, there is an example which does not admit a finite language, in the sense that its automorphism group is not the automorphism group of a structure over a finite language, and we show that there are 2^{ℵ_{0}} structures like this.

2 ℵ_{0}-categorical, weakly o-minimal, 1-indiscern-ible structures

Let ℚ^{n} be the set of n-tuples x = (x_{0}, …, x_{n−1}) of rational numbers, ordered lexicographically by < where x < y if ∃i(x_{i} < y_{i} ∧ (∀j < i)(x_{j} = y_{j})), and let the equivalence relation E_{i} be given by E_{i}(x, y) ⇔ (∀j < n − i)(x_{j} = y_{j}). Then for each i the equivalence classes of E_{i} are convex subsets of ℚ^{n}. Moreover, E_{0} is the identity relation, E_{n} the universal relation, and E_{i−1} refines E_{i} for each i > 0.

Using a back-and-forth argument one sees that M = (ℚ^{n}; =, <, (E_{i})_{0≤i≤n}) is ℵ_{0}-categorical, admits elimination of quantifiers, and is also weakly o-minimal and 1-indiscernible. We define an ultrametric on ℚ^{n} by

d(x, y) = i ⇔ E_{i}(x, y) ∧ ¬E_{i−1}(x, y).

(We recall that a metric d is said to be an ultrametric if it satisfies the ‘ultrametric inequality’ d(x, z) ≤ max(d(x, y), d(y, z)) for all x, y, and z. Note that our ultrametrics are unusual in that the ‘distances’ only take values in the finite set {0, 1, …, n}.) We define R_{i} for 1 ≤ i ≤ n by R_{i}(x, y) ⇔ (x < y ∧ d(x, y) = i). Then the R_{i} are all the 2-atoms in M of pairs (x, y) with x < y. The structures (ℚ^{n}; =, <, (E_{i})_{0≤i≤n}) and (ℚ^{n}; =, <, d) and (ℚ^{n}; =, <, (R_{i})_{1≤i≤n}) are all inter-definable. (Actually < can be defined in (ℚ^{n}; =, (R_{i})_{1≤i≤n}) by x < y ⇔ (∃i)R_{i}(x, y), but we do not need to bother with this.) In a formal treatment, the binary function d into {0, …, n} would be represented by n binary relations.

We shall see that, up to binary structure, (ℚ^{n}; =, <, (R_{i})_{1≤i≤n}) is the only ℵ_{0}-categorical, weakly o-minimal, and 1-indiscernible structure having n 2atoms of increasing pairs.

Let us suppose therefore that (M; =, <, …) is ℵ_{0}-categorical, weakly ominimal, and 1-indiscernible. By ℵ_{0}-categoricity there are finitely many 2-atoms of pairs (x, y) with x < y. Let these be R_{1}, …, R_{n}, indexed so that for all x, y, y′ ∈ M and for all i, j with 1 ≤ i < j ≤ n, x < y, y′ ∧ R_{i}(x, y) ∧ R_{j}(x, y′) ⇒ y < y′. This is possible since for fixed x, the R_{i}(x, y) are the 1-atoms of the induced weakly o-minimal structure on (x, ∞)^{M}, and therefore define convex sets.

Instead of R_{i}(x, y) we write d_{→}(x, y) = i. Then the following hold:

• x < y ∧ d_{→}(x, y) = i isolates a complete 2-type,

• x < y < z ⇒ d_{→}(x, y) ≤ d_{→}(x, z).

Now re-index {R_{i} : 1 ≤ i ≤ n} as {S_{i} : 1 ≤ i ≤ n} in such a way that for all x, x′, y ∈ M and for all i, j with 1 ≤ i < j ≤ n, x, x′ < y ∧ S_{i}(x, y) ∧ S_{j}(x′, y) ⇒ x′ < x. If we write S_{i}(x, y) as d_{←}(x, y) = i, then {d_{←}(x, y) = i : 1 ≤ i ≤ n} are just the same formulae as {d_{→}(x, y) = i : 1 ≤ i ≤ n}, perhaps in a different order, and

• x < y ∧ d_{←}(x, y) = i isolates a complete 2-type,

• x < y < z ⇒ d_{←}(y, z) ≤ d_{←}(x, z).

We shall show that d_{→} = d_{←}, and is an ultrametric on M.

Lemma 2.1 For m ≤ n + 1 we have (i) d_{→}(x, y) = m ⇔ d_{←}(x, y) = m, (ii) if x < y < z and d_{→}(x, y) ≤ m then d_{→}(y, z) = m ⇒ d_{→}(x, z) = m, (iii) if x < y < z and d_{→}(x, y) < m then d_{→}(y, z) = m ⇔ d_{→}(x, z) = m.

Proof We prove the lemma by downwards induction on m. Basis: m = n + 1. All three statements are vacuously fulfilled. Induction step: Assume the result for m + 1 ≤ n + 1.

(i) It suffices to find x′ < y′ such that d_{→}(x′, y′) = m and d_{←}(x′, y′) = m since both formulae isolate a complete type. Choose x < y < z such that d_{→}(x, y) = m and d_{←}(y, z) = m. Thus d_{→}(x, z) ≥ m and d_{←}(x, z) ≥ m. We show that d_{→}(x, z) = d_{←}(x, z) = m. If one of d_{→}(x, z), d_{←}(x, z) is bigger than m then by the induction hypothesis the other is too. But if d_{→}(x, z) > m, then by (iii) (for values greater than m), d_{→}(y, z) = d_{→}(x, z) > m, and by (i) again, d_{←}(y, z) > m, which is not the case.

(ii) Let x < y < z and d_{→}(x, y) ≤ m and d_{→}(y, z) = m. By (i) we have d_{←}(y, z) = m and therefore d_{←}(x, z) ≥ m and d_{→}(x, z) ≥ m. If d_{→}(x, z) > m then by (iii) (for values greater than m), d_{→}(y, z) > m. Thus d_{→}(x, z) = m.

(iii) Let x < y < z and d_{→}(x, y) < m. We have to show that d_{→}(x, z) = m ⇒ d_{→}(y, z) = m as the other direction follows from (ii). Suppose d_{→}(x, z) = m. We choose x < w_{1} < w_{2} such that d_{→}(x, w_{1}) = m and d_{→}(w_{1}, w_{2}) = m. By (ii) d_{→}(x, w_{2}) = m. Now for all y′ if d_{→}(x, y′) < m then y′ < w_{1} and by (i) m = d_{←}(x, w_{2}) ≥ d_{←}(y′, w_{2}) ≥ d_{←}(w_{1}, w_{2}) = m. Using (i) again, d_{→}(y′, w_{2}) = m. So there is w′ (namely w_{2}) with d_{→}(x, w′) = m such that for all y′, (d_{→}(x, y′) < m ⇒ d_{→}(y′, w′) = m). As the formula d_{→}(x, w′) = m isolates a complete 2-type, this holds for every w′ such that d_{→}(x, w′) = m, in particular for z, and so we deduce from d_{→}(x, z) = m and d_{→}(x, y) < m that d_{→}(y, z) = m. □

Now we define

d(x, y) = \{ \begin{matrix}d_{→}(x, y) & if x < y \\ d_{→}(y, x) & if y < x \\ 0 & if y = x. \end{matrix}

Then d induces an ultrametric. To see this we have to check the following statements:

• For x < y < z, d(x, y) ≤ d(y, z) ⇒ d(x, z) = d(y, z),

• For x < y < z, d(z, y) ≤ d(y, x) ⇒ d(z, x) = d(y, x).

The first statement is a reformulation of (ii) of Lemma 2.1 and the second statement follows from the same lemma applied to the reversed order. We further observe that d is compatible with the ordering < in the sense that for every x and i the set {y : d(x, y) ≤ i} is convex.

The following theorem sums up what we have shown:

Theorem 2.2 If (M; =, <, …) is ℵ_{0}-categorical, weakly o-minimal, and 1-in-discernible having n 2-atoms of pairs (x, y) with x < y, then there is an ultrametric d on M taking values in {0, …, n} compatible with < such that the n 2-atoms on increasing pairs (x, y) are given by d(x, y) = i (for 1 ≤ i ≤ n). The ultrametric d is uniquely determined by these properties.

Theorem 2.3 The 0-definable equivalence relations on M are precisely E_{i} for 0 ≤ i ≤ n given by E_{i}(x, y) ⇔ d(x, y) ≤ i.

Proof Let E be a 0-definable equivalence relation, (x)_{E} the E-class containing x. If the classes of E had more than one convex component, then the formula saying that x is in the leftmost component of (x)_{E} would be true of some but not all elements of M, contrary to 1-indiscernibility.

The set {(x, y) : xEy} is a union of some of the 2-atoms and because the equivalence classes are convex there are i, j such that xEy ⇔ (y ≤ x ∧ d(y, x) ≤ i) ∨ (x ≤ y ∧ d(x, y) ≤ j). By symmetry of E we get i = j. □

Theorem 2.4 For each i < n and x ∈ M, X = {(y)_{E_{i}} : y ∈ (x)_{E_{i+1}}} is countable and densely linearly ordered without endpoints.

Proof Pick y, z ∈ (x)_{E_{i+1}} such that y < x < z and d(y, x) = i + 1 = d(x, z). We have (y)_{E_{i}} < (x)_{E_{i}} < (z)_{E_{i}} and as x was arbitrary X has no endpoints. For density let y′, z′ ∈ (x)_{E_{i+1}} with (y′)_{E_{i}} < (z′)_{E_{i}}, which just means that d(y′, z′) = i + 1. Thus there is an automorphism g sending (y, z) to (y′, z′), and then (y′)_{E_{i+1}} < (x^{g})_{E_{i+1}} < (z′)_{E_{i+1}}. □

Theorem 2.4 just says that (M; =, <, d) is universal and homogeneous (in the sense of Fraïssé) among all countable ultrametric spaces with possible distances in {0, 1, …, n} which are compatible with the ordering.

Corollary 2.5 If (M; =, <, …) is ℵ_{0}-categorical, weakly o-minimal, and 1indiscernible having n 2-atoms of pairs (x, y) with x < y, then

(M; =, <, (E_{i})_{0≤i≤n}) ≅ (ℚ^{n}; =, <, (E_{i})_{0≤i≤n}).

A variant of this corollary expresses things in terms of the 2-atoms rather than the 0-definable equivalence relations.

Corollary 2.6 If (M; =, <, …) is ℵ_{0}-categorical, weakly o-minimal, and 1indiscernible having n 2-atoms R_{i} of pairs (x, y) with x < y, indexed so that for x < y, y′ and i < j, R_{i}(x, y) ∧ R_{j}(x, y′) ⇒ y < y′, then

(M; =, <, (R_{i})_{1≤i≤n}) ≅ (ℚ^{n}; =, <, (R_{i})_{1≤i≤n}).

3 ℵ_{0}-categorical, weakly o-minimal, 2-indiscern-ible structures

In this section we carry out a similar classification of the structures in the 2indiscernible case, this time up to ternary structure. We first construct examples of ℵ_{0}-categorical, weakly o-minimal, 2-indiscernible structures, using the structures in §2 as auxiliary, and then show that up to ternary structure these are the only ones. The construction gives a tree, and the weakly o-minimal structure we seek arises as a set of branches through the tree. (By tree we understand a partially ordered set for which any two elements have a common lower bound, and any two incomparable elements have no common upper bound.) So, not surprisingly, the resulting structures carry ‘C-relations’ on them (see [1]). Here they are actually ‘ordered C-relations’, where this means that there is natural compatibility with <.

We start with ℚ^{m} ordered lexicographically and with d defined as in §2. Fix a function e : ℚ^{m} → 2 (= {0, 1}) such that e^{−1}(0), e^{−1}(1) are both dense in ℚ^{m}. We let M be the set of maps a from ℚ^{m} to 2 with {x : a(x) ≠ e(x)} finite, and T be the family of initial segments of elements of M. Thus T = {a|(−∞, x) : a ∈ M, x ∈ ℚ^{m}}.

We view M ∪ T as a structure. Here T is the ‘scaffolding’ used to build M, which may be discarded when the construction is complete. The basic relations on M ∪ T are as follows:

• a unary predicate picking out M,

• the lexicographic ordering < on M,

• ‘extension’ ⪯ on M ∪ T, given by a ⪯ b if, as functions, b extends a.

If a ⪯ b ∈ T or b ⪯ a ∈ T we write d(a, b) for d(sup dom a, sup dom b).

Now for any a < b in M there is a least x ∈ ℚ^{m} such that a(x) ≠ b(x), and for this x, a(x) < b(x). We define t(a, b) to be a|(−∞, x). This suggests a general method for interpreting T in M (though we do not actually do things this way).

The ternary structure induced on M by these relations is as follows:

• T_{i}(x, y, z) if x < y < z in M and t(x, y) ≺ t(y, z) and d(t(x, y), t(y, z)) = i,

• U_{i}(x, y, z) if x < y < z in M and t(y, z) ≺ t(x, y) and d(t(y, z), t(x, y)) = i.

Notice that if x < y < z, since T is a binary tree, we cannot have t(x, y) = t(y, z), so either t(x, y) ≺ t(y, z) or t(y, z) ≺ t(x, y), and for some i, T_{i}(x, y, z) or U_{i}(x, y, z).

The structure M_{2m} is then defined by

M_{2m} = (M; =, <, T_{1}, …, T_{m}, U_{1}, …, U_{m}).

A slight modification yields M_{2m+1}. This time we take M to consist of all maps from ℚ^{m} to ℚ such that supp a = {x : a(x) ≠ 0} is finite. We define T_{i}, U_{i} as before, and in addition let V (x, y, z) if x < y < z in M and t(x, y) = t(y, z). Then M_{2m+1} = (M; =, <, T_{1}, …, T_{m}, V, U_{1}, …, U_{m}).

Remarks 3.1 (1) By definition of ‘lexicographic’, if x < y < z then t(x, y) ≺ t(y, z) ⇒ t(x, y) = t(x, z) and t(x, y) ≻ t(y, z) ⇒ t(y, z) = t(x, z). The converse implications also hold in M_{n} for n even. If x < y < z and t(x, y) = t(y, z) in M_{n} then n must be odd, and t(x, y) = t(x, z) = t(y, z).

(2) The desired weakly o-minimal structures are the M_{n} (see Theorem 3.2 below). The analysis of a general 2-indiscernible, weakly o-minimal, ℵ_{0}- categorical structure may proceed by interpreting T in M_{n} via equivalence classes of ordered pairs and the map t above, though the method we use is to show that a certain list of axioms, which are true in M_{n}, and which characterize a countable structure uniquely up to isomorphism, hold in any 2-indiscernible, weakly o-minimal, ℵ_{0}-categorical structure.

(3) It will turn out that T_{i}, U_{i} (and V if n is odd) are the atoms of M_{n} on increasing triples. From the tree representation it is easy to see that they come in the following order, as z increases, for fixed x and y: z < x < y : T_{m}(z, x, y), …, T_{1}(z, x, y), V (z, x, y), U_{1}(z, x, y), …, U_{m}(z, x, y), x < z < y : U_{m}(x, z, y), …, U_{1}(x, z, y), V (x, z, y), T_{1}(x, z, y), …, T_{m}(x, z, y), x < y < z : T_{m}(x, y, z), …, T_{1}(x, y, z), V (x, y, z), U_{1}(x, y, z), …, U_{m}(x, y, z), (where V just applies if n is odd). Thus the order of the terms is reversed as we pass through a parameter, as in §2.

(4) The structures M_{n} can be described in terms of ultrametrics which are parametrized by elements of M_{n}: If x < y < z we write d_{x}^{r}(y, z) = i (for 1 ≤ i ≤ n) if (x, y, z) lies in the ith 3-atom in increasing order in the above enumeration (regarding x as fixed, d_{x}^{r} measures distances between points to the right of x), and similarly for d_{x}^{l} (distances between points on the left of x). So if 1 ≤ i ≤ m and x < y < z then

d_{x}^{r}(y, z) = i ⇔ T_{m+1−i}(x, y, z)
⇔ t(x, y) ≺ t(y, z) ∧ d(t(x, y), t(y, z)) = m + 1 − i
⇔ d_{z}^{l}(x, y) = n + 1 − i,
d_{x}^{r}(y, z) = n + 1 − i ⇔ U_{m+1−i}(x, y, z)
⇔ t(y, z) ≺ t(x, y) ∧ d(t(y, z), t(x, y)) = m + 1 − i
⇔ d_{z}^{l}(x, y) = i.

If n = 2m + 1 is odd then we have in addition

d_{x}^{r}(y, z) = m + 1 ⇔ V (x, y, z) ⇔ t(x, y) = t(y, z) ⇔ d_{z}^{l}(x, y) = m + 1.

To make d_{x}^{r} into an ultrametric on (x, ∞) we have to symmetrize the function d_{x}^{r} defined above and add: if y > x then d_{x}^{r}(y, y) = 0. The structure M_{n} is interdefinable with (M; =, <, d_{x}^{r}), where the functions d_{x}^{r} are represented by means of ternary relations. For the proof that d_{x}^{r} is an ultrametric, see Theorem 4.5.

(5) The construction given generalizes one which may be given using a ‘Crelation’. We say that a C-relation on a set X is a ternary relation C (written with a semicolon between the first two arguments, to emphasize the symmetry between the second and third) such that

(C0) x ≠ y → C(x; y, y),

(C1) C(x; y, z) → C(x; z, y),

(C2) C(x; y, z) → ¬C(y; x, z),

(C3) C(x; y, z) ∧ ¬C(w; y, z) → C(x; w, z). The definition given in [1] has two further axioms, but those we give are the universal axioms, and the treatment goes more smoothly with just these four.

The other (∀∃) axioms will in any case hold in the generic model. In addition, when there is a linear ordering on the structure, we say that the C-relation is order-compatible if C(x; y, z) ∧ y < w < z ⇒ C(x; y, w). This is the same as saying that when we fix x, the equivalence relation given by y ∼ z if C(x; y, z) has convex classes.

If in the present context we define C_{i} for 1 ≤ i ≤ m by

C_{i}(x; y, z) if (y, z ∈ (x, ∞) ∧ d_{x}^{r}(y, z) ≤ i) ∨ (y, z ∈ (−∞, x) ∧ d_{x}^{l}(y, z) ≤ i)

then C_{i} is indeed an order-compatible C-relation, and moreover T_{i} and U_{i} can be recovered from {C_{j}}_{j≤m} by

T_{i}(x, y, z) ⇔ x < y < z ∧ C_{m+1−i}(x; y, z) ∧ ¬C_{m−i}(x; y, z)
and U_{i}(x, y, z) ⇔ x < y < z ∧ C_{m+1−i}(z; x, y) ∧ ¬C_{m−i}(z; x, y),

and for n odd V can also be recovered by

V (x, y, z) ⇔ x < y < z ∧ ¬C_{m}(x; y, z) ∧ ¬C_{m}(z; x, y).

Thus the situation is analogous to that in §2, where the models could be specified by the 2-atoms R_{i}, the equivalence relations E_{i}, or the ultrametric d. Here the C-relations play the role of the equivalence relations; in fact, they may be regarded as indexed families of equivalence relations. If C is one of the C-relations mentioned above, we get corresponding equivalence relations ∼_{x} on {y ∈ M : x ≠ y} by letting y ∼_{x} z if C(x; y, z).

Since T_{i}, U_{i}, and (for n odd) V can be defined from the C_{i} it follows that so can the ultrametrics d_{x}^{r} and d_{x}^{l} described in (4). Spelling this out in more detail we have, for x < y < z:

for 1 ≤ i ≤ m : d_{x}^{r}(y, z) = i if C_{i}(x; y, z) ∧ ¬C_{i−1}(x; y, z),
for n + 1 − m ≤ i ≤ n : d_{x}^{r}(y, z) = i if C_{n+1−i}(z; x, y) ∧ ¬C_{n−i}(z; x, y),
fori = m + 1 : d_{x}^{r}(y, z) = m if ¬C_{m}(x; y, z) ∧ ¬C_{m}(z; x, y),

where the third clause is omitted if n = 2m is even (which corresponds to the condition x < y < z ⇒ C_{m}(x; y, z)∨C_{m}(z; x, y)), and d_{z}^{l}(x, y) = n+1−d_{x}^{r}(y, z), and C_{0}(x; y, z) just means x ≠ y and y = z.

The idea of a homogeneous ordered C-relation is implicit in [2]. For instance, M_{2} is ∂P T_{3} of that paper.

(6) The structure M_{3} is a reduct of one of the weakly o-minimal structures first considered (by Dickmann, see [3], where the notion of weak o-minimality was originally defined). Let (R; =, <, +, ·) be a countable non-archimedean realclosed field, V the valuation ring consisting of the finite elements, Γ the value group, and v : R → Γ the corresponding valuation. Define C on R by C(x; y, z) if v(y − x) < v(y − z). Then M_{3} is essentially the structure (R; =, <, C) (that is, T, V, U are interdefinable with C). Also C is definable in (R; =, +, ·, v), and the latter is weakly o-minimal by [3] (though of course it is not ℵ_{0}-categorical).

Theorem 3.2 For each n ≥ 1, M_{n} is an ℵ_{0}-categorical, weakly o-minimal, 2indiscernible structure having exactly n atoms of strictly increasing triples given by T_{i}, U_{i} (and, for odd n, V).

Proof This may be seen directly, but it will also follow from the work of the next section. There we give a list of axioms which we shall show hold in M_{n}, and in any ℵ_{0}-categorical weakly o-minimal 2-indiscernible structure with n 3-atoms of increasing triples. The back-and-forth proof establishes quantifier elimination, and the other properties follow from this. For instance, to check weak o-minimality one only needs to show that sets defined (using parameters) from <, or one of the T_{i}, U_{i}, V are convex, and this is straightforward. □

4 An axiomatization in terms of ultrametrics

In this section we give a list of axioms, prove that they hold in M_{n}, and in any ℵ_{0}-categorical, weakly o-minimal, 2-indiscernible structure with n 3-atoms of increasing triples, and that they are ℵ_{0}-categorical. This will conclude the classification (up to ternary structure) in the 2-indiscernible case. The reader may wish to begin by reading the statement and proof of Theorem 4.6 for an outline.

The axioms to describe such a structure M are formulated in a language containing < and binary functions d_{a}^{r}, d_{a}^{l} to {0, 1, …, n} for each a ∈ M (which are formally represented by means of ternary relations), and are as follows, where by ‘dual’ we understand the statement obtained by reversing all orderings on elements of M, and interchanging d^{r} and d^{l}:

Universal axioms I < is a linear ordering, II d_{x}^{r} is an ultrametric on (x, ∞), and d_{x}^{l} is an ultrametric on (−∞, x), III for x < y, {z > x : d_{x}^{r}(y, z) ≤ i} and {z < y : d_{y}^{l}(x, z) ≤ i} are convex, IV for x < y < z, d_{x}^{r}(y, z) + d_{z}^{l}(x, y) = n + 1, V for x < y < z < w and i ≤ n/2, d_{x}^{r}(y, z) ≤ i → (d_{x}^{r}(z, w) ≤i∨d_{w}^{l}(y, z) ≤ i)

and dual,

∀∃ axioms VI for i ≤ n, ∀x∀y(x < y → (∃z > y)(d_{x}^{r}(y, z) = i)) and dual, VII for i ≤ n, ∀x∀y(x < y → ∃z(x < z < y ∧ d_{x}^{r}(z, y) = i)), VIII for i ≤ n/2 and i ≤ j ≤ n + 1 − i, ∀x∀y∀z(x < y < z ∧ d_{x}^{r}(y, z) = i

→ ∃w(x < w < y ∧ d_{x}^{r}(w, y) = i ∧ d_{w}^{r}(y, z) = j)) and dual, IX for j, k_{1}, k_{2} ≤ n/2, min(k_{1}, k_{2}) = j, ∀x∀y∀z(x < y < z ∧ d_{x}^{r}(y, z) = j

→ ∃w(z < w ∧ d_{w}^{l}(y, z) = k_{1} ∧ d_{x}^{r}(z, w) = k_{2})), and dual.

Once again, the ∀∃ axioms VI-IX will be true in the (Fraïssé-) generic structure.

We first draw some consequences from the universal axioms and point out that they just axiomatize refining order-compatible C-relations.

Lemma 4.1 Let M be a structure satisfying axioms I to V. Then the following statements and their duals hold:

(i) If x < y < z, w then d_{y}^{r}(z, w) ≥ d_{x}^{r}(z, w).(For this only I-IV are required.)

(ii) Suppose that x < y < z < w and i ≤ n. If d_{x}^{r}(y, z) ≤ i then d_{x}^{r}(z, w) ≤ i or d_{w}^{l}(y, z) ≤ i.

(iii) If x < y < z < w, then min(d_{x}^{r}(z, w), d_{w}^{l}(y, z)) ≤ d_{x}^{r}(y, z).

(iv) If i ≤ n/2, i ≤ j ≤ n+1−i, x < y < z < w, d_{x}^{r}(y, w) = i and d_{y}^{r}(z, w) = j then d_{x}^{r}(y, z) = d_{x}^{r}(z, w) = i.

(v) If x < y < z < w, d_{x}^{r}(y, z) ≤ n/2 and d_{w}^{l}(x, y) ≤ n/2, then d_{w}^{l}(y, z) = min(d_{w}^{l}(x, y), d_{x}^{r}(y, z)).

Proof (i) Suppose without loss of generality that z < w. By axiom III d_{w}^{l}(y, z) ≤ d_{w}^{l}(x, z), and applying axiom IV we get d_{y}^{r}(z, w) = n+1−d_{w}^{l}(y, z) ≥ n + 1 − d_{w}^{l}(x, z) = d_{x}^{r}(z, w).

(ii) Let i > n/2, as the case i ≤ n/2 is axiom V. Suppose that d_{x}^{r}(y, z) ≤ i but d_{w}^{l}(y, z) ≥ i + 1. By (i), d_{x}^{r}(z, w) ≤ d_{y}^{r}(z, w) and by axiom IV, d_{y}^{r}(z, w) = n + 1 − d_{w}^{l}(y, z) ≤ n + 1 − (i + 1) ≤ n − n/2 = n/2 ≤ i.

(iii) This is a simple reformulation of (ii).

(iv) By axiom IV we have i ≤ d_{w}^{l}(y, z) ≤ n + 1 − i. If d_{x}^{r}(y, z) < i then by axiom V either d_{w}^{l}(y, z) < i or d_{x}^{r}(z, w) < i, and the latter implies d_{x}^{r}(y, w) < i, so both cases are impossible. As on the other hand d_{x}^{r}(y, z) ≤ d_{x}^{r}(y, w) = i we must have d_{x}^{r}(y, z) = i.

¿From d_{w}^{l}(y, z) ≤ n + 1 − i and d_{w}^{l}(x, y) = n + 1 − i it follows by axiom II that d_{w}^{l}(x, z) = n + 1 − i, which gives d_{x}^{r}(z, w) = i.

The fact that d_{x}^{r}(y, w) = i ≤ n/2 corresponds to the fact that the branches to y and w meet on ‘level i’, above where the branch to x meets each of them. That i ≤ j = d_{y}^{r}(z, w) ≤ n + 1 − i indicates that the branch to z meets those to y and w on level i or above. This is all illustrated in Fig.1(a), where we have not shown the branch to z, since it may join the branch to y either above or below where it joins the branch to w. In Figure 3 below, the lack of a line to vertex w has a similar interpretation. (The diagram is to assist the reader, but does not of course form part of the proof.)

(v) Let d_{w}^{l}(x, y) = i ≤ n/2. Then d_{x}^{r}(y, w) = n + 1 − i by axiom IV. Since d_{x}^{r}(y, z) ≤ n/2 < n + 1 − i, axiom II gives d_{x}^{r}(z, w) = n + 1 − i. Using axiom IV again, d_{w}^{l}(x, z) = i. By axiom III, d_{w}^{l}(y, z) ≤ i, thus d_{w}^{l}(y, z) ≤ d_{w}^{l}(x, y).

[figure: x; y; z; w; x; y; z; w; (a); (b)]

Figure 1: Diagrams illustrating Lemma 4.1(iv) and (v)

Let d_{x}^{r}(y, z) = j ≤ n/2. By axiom II, d_{w}^{l}(x, z) ≤ max(d_{w}^{l}(x, y), d_{w}^{l}(y, z)) = d_{w}^{l}(x, y) ≤ n/2, from which it follows that d_{x}^{r}(z, w) > n/2 ≥ j. By axiom V, we get d_{w}^{l}(y, z) ≤ j = d_{x}^{r}(y, z).

So we have d_{w}^{l}(y, z) ≤ min(d_{w}^{l}(x, y), d_{x}^{r}(y, z)). By the dual of (iii), min(d_{w}^{l}(x, y), d_{x}^{r}(y, z)) ≤ d_{w}^{l}(y, z). The configuration here is similarly illustrated in Fig.1(b). This time, since we know where the branches meet, all possible lines have been shown. □

Axiom V is crucial. It ensures that the relation (d_{x}^{r}(y, z) ≤ i ∨ d_{x}^{l}(y, z) ≤ i) defines a C-relation C_{i} for i ≤ n/2. In fact axioms I-V assert that (C_{i} : 1 ≤ i ≤ n/2) is a family of refining C-relations:

Lemma 4.2 Let (M; =, <) be a linearly ordered structure.

(i) Suppose C_{1}, …, C_{m} is a sequence of order-compatible C-relations with C_{1} ⊆ C_{2} ⊆ … ⊆ C_{m}. Let us write in addition C_{0}(x; y, z) for x ≠ y = z, and for x ∈ M let the ultrametrics d_{x}^{r} and d_{x}^{l} be given as at the end of Remark 3.1 (5) (where there are two possible cases corresponding to n odd or even, the latter distinguished by x < y < z ⇒ C_{m}(x; y, z)∨C_{m}(z; x, y)). Then axioms I-V hold in (M; =, <) expanded by the d_{x}^{r}, d_{x}^{l}.

(ii) Suppose that d_{x}^{r} and d_{x}^{l} are ultrametrics for which axioms I-V hold. For m the integer part of n/2 and 1 ≤ i ≤ m we define:

C_{i}(x; y, z) ⟺ d_{x}^{r}(y, z) ≤ i or d_{x}^{l}(y, z) ≤ i.

Then each C_{i} is an order-compatible C-relation, and C_{1} ⊆ C_{2} ⊆ … ⊆ C_{m}.

Proof The proof is fairly routine. Let us only point out (in the proof of (ii)) that axiom V only states one of three cases of the C-relation axiom (C3). The other two cases already follow from the first four axioms. For example suppose that x < w < y < z and C_{i}(x; y, z) holds, which means that d_{x}^{r}(y, z) ≤ i. We have to show d_{x}^{r}(w, z) ≤ i or d_{z}^{l}(w, y) ≤ i. But d_{x}^{r}(y, z) ≤ i ⇒ d_{z}^{l}(x, y) ≥ n + 1 − i ⇒ d_{z}^{l}(x, w) ≥ n + 1 − i or d_{z}^{l}(w, y) ≥ n + 1 − i. The former implies d_{x}^{r}(w, z) ≤ i and the latter d_{x}^{r}(y, z) ≤ d_{w}^{r}(y, z) ≤ i by Lemma 4.1(i). □

Next we want to verify the axioms in a general 2-indiscernible ℵ_{0}-categorical weakly o-minimal structure having n = 2m or 2m + 1 3-atoms R_{1}, …, R_{n} of increasing triples and we first say how d^{r} and d^{l} are given. We fix a in the structure M and look at the ordered structure M_{a} with domain (a, ∞) and the binary relation R_{i,a} = {(x, y) ∈ (a, ∞) : R_{i}(a, x, y)} for every 3-atom R_{i}. Then M_{a} is weakly o-minimal and 1-indiscernible and has n 2-atoms on increasing pairs, so by Theorem 2.2 there is an ultrametric d_{a}^{r} on M_{a} such that the 2atoms on increasing pairs M_{a} are given by d_{a}^{r}(x, y) = i for i = 1, … n. In the same way we may consider the structure with domain (−∞, a) and get an ultrametric d_{a}^{l} on it. In each case the ultrametric is uniquely determined.

Theorem 4.3 Let N be a countable, weakly o-minimal, 2-indiscernible structure with domain N, ordering <, and n atoms of strictly increasing triples. Then axioms I-IX all hold in N.

Proof II and III These follow from Theorem 2.2.

IV Fix a < b. By 2-indiscernibility we can pick x_{1} < x_{2} < … < x_{n} with a < x_{i} < b such that (a, x_{i}, b) for 1 ≤ i ≤ n realize all the 3-atoms. Then n ≥ d_{a}^{r}(x_{1}, b) > … > d_{a}^{r}(x_{n}, b) ≥ 1 and 1 ≤ d_{b}^{l}(a, x_{1}) < … < d_{b}^{l}(a, x_{n}) ≤ n and so for 1 ≤ i ≤ n we have d_{a}^{r}(x_{i}, b) = n + 1 − i and d_{b}^{l}(a, x_{i}) = i. As all the formulae of the form d_{a}^{r}(x, b) = j and d_{b}^{l}(a, x) = j isolate complete 3-types it follows that d_{b}^{l}(a, x) = i ⇔ d_{a}^{r}(x, b) = n + 1 − i which is equivalent to the equality we wanted to prove.

V To prove this axiom, we introduce some notation. For 0 ≤ i ≤ n/2 and a < b we let

E_{a}^{r,i}(b) = {x : a < x ∧ d_{a}^{r}(x, b) ≤ i},

E_{a}^{r,i}(b)^{+} = {x ∈ E_{a}^{r,i}(b) : x > b},

E_{a}^{r,i}(b)^{−} = {x ∈ E_{a}^{r,i}(b) : x < b}, and similarly

E_{b}^{l,i}(a) = {x : x < b ∧ d_{b}^{l}(x, a) ≤ i},

E_{b}^{l,i}(a)^{+} = {x ∈ E_{b}^{l,i}(a) : x > a}, and

E_{b}^{l,i}(a)^{−} = {x ∈ E_{b}^{l,i}(a) : x < a}.

Lemma 4.4 Let i ≤ n/2, a < x < b, i < d_{a}^{r}(x, b) < n + 1 − i. Then E_{a}^{r,i}(x) = E_{b}^{l,i}(x).

Proof We prove by induction on i that E_{a}^{r,i}(x)^{+} = E_{b}^{l,i}(x)^{+}. The case i = 0 is obvious.

As both sets are convex with infimum x, either E_{a}^{r,i}(x)^{+} ⊆ E_{b}^{l,i}(x)^{+} or E_{b}^{l,i}(x)^{+} ⊆ E_{a}^{r,i}(x)^{+}. Suppose for a contradiction that E_{b}^{l,i}(x)^{+} ⊂ E_{a}^{r,i}(x)^{+} (the case E_{a}^{r,i}(x)^{+} ⊂ E_{b}^{l,i}(x)^{+} being similar; note that we use ⊂ to stand for proper subset throughout the paper). Let k = d_{a}^{r}(x, b), so that i < k < n + 1 − i. As (d_{a}^{r}(x, b) = k) ∧ (a < x < b) isolates a complete type in b, we also have that b′ > x ∧ d_{a}^{r}(x, b′) = k ⇒ E_{b′}^{l,i}(x)^{+} ⊂ E_{a}^{r,i}(x)^{+}. Note that by the dual of Lemma 4.1(i), a < x < b_{1} < b_{2} implies E_{b_{1}}^{l,i}(x)^{+} ⊆ E_{b_{2}}^{l,i}(x)^{+}.

We let U_{x} = ⋂{E_{y}^{l,i}(x)^{+} : x < y ∧ d_{a}^{r}(x, y) = k}. Then

• U_{x} is definable over a, x,

• U_{x} ⊂ E_{a}^{r,i}(x)^{+},

• E_{a}^{r,i−1}(x)^{+} ⊂ U_{x}.

To prove the last statement, pick c > x with d_{a}^{r}(x, c) = k−1. For every b′ > x with d_{a}^{r}(x, b′) = k we have c < b′ and E_{c}^{l,i}(x)^{+} ⊆ E_{b′}^{l,i}(x)^{+} and thus E_{c}^{l,i}(x)^{+} ⊆ U_{x} which implies E_{c}^{l,i−1}(x)^{+} ⊂ U_{x}. Now the induction yields E_{c}^{l,i−1}(x)^{+} = E_{a}^{r,i−1}(x)^{+}.

Therefore E_{a}^{r,i−1}(x)^{+} ⊂ U_{x} ⊂ E_{a}^{r,i}(x)^{+} which is impossible since every point in E_{a}^{r,i}(x)^{+} − E_{a}^{r,i−1}(x)^{+} has the same type over a, x.

Similarly E_{a}^{r,i}(x)^{−} = E_{a}^{l,i}(x)^{−}, and the result follows. □

Now we prove V. Let x < y < z < w and d_{x}^{r}(y, z) ≤ i ≤ n/2. Suppose d_{x}^{r}(z, w) > i. If d_{x}^{r}(z, w) < n + 1 − i then, by Lemma 4.4, E_{x}^{r,i}(z) = E_{w}^{l,i}(z), which implies that d_{w}^{l}(y, z) ≤ i. If d_{x}^{r}(z, w) ≥ n+1−i then we have d_{w}^{l}(x, z) ≤ i which also implies d_{w}^{l}(y, z) ≤ i.

The dual of axiom V follows as easily from the lemma.

VI Pick x_{1} < y_{1} < z_{1} such that d_{x_{1}}^{r}(y_{1}, z_{1}) = i. By 2-indiscernibility we may suppose that x_{1} = x and y_{1} = y, and for the desired z we take z = z_{1}.

VII This is established by a similar 2-indiscernibility argument.

VIII We choose w, y, z with w < y < z and d_{w}^{r}(y, z) = j and use the dual of VI, and IV, to choose x < w with d_{x}^{r}(w, z) = i. By Lemma 4.1(iv) we have d_{x}^{r}(w, y) = i and d_{x}^{r}(y, z) = i.

We have thus found x, y, z with x < y < z and d_{x}^{r}(y, z) = i, satisfying ∃w(x < w < y ∧ d_{x}^{r}(w, y) = i ∧ d_{w}^{r}(y, z) = j)). As x < y < z ∧ d_{x}^{r}(y, z) = i isolates a complete 3-type, this applies to the x, y, z we started with.

IX We choose y < z < w with d_{w}^{l}(y, z) = k_{1} and x < y with d_{x}^{r}(y, w) = k_{2}. Hence as d_{x}^{r}(z, w) ≤ d_{x}^{r}(y, w), we have d_{x}^{r}(z, w) ≤ n/2. By the dual of Lemma 4.1(v), d_{x}^{r}(y, z) = min(d_{x}^{r}(z, w), d_{w}^{l}(y, z)). As d_{x}^{r}(y, z) ≤ d_{x}^{r}(z, w) we have d_{x}^{r}(y, w) = d_{x}^{r}(z, w) and therefore d_{x}^{r}(y, z) = min(k_{1}, k_{2}) = j.

As x < y < z ∧ d_{x}^{r}(y, z) = j isolates a complete type, axiom IX follows. □

Theorem 4.5 Axioms I-IX all hold in M_{n} as defined in §3.

Proof We shall use the facts that M is linearly ordered, and that ≺ defines a tree structure on T. This means for instance that for any x < y < z, one of t(x, y) and t(y, z) is equal to t(x, z).

II To show that d_{x}^{r} is an ultrametric it is just necessary to verify the ultrametric inequality. Let x < y < z < w. We illustrate four possible cases in Fig. 2. We

[figure: x; y; z; w; x; y; z; w; x; y; z; w; x; y; z; w; Case 1; Case 2; Case 3; Case 4]

Figure 2: Typical cases arising in the verification of II

have to show that the two greatest members of d_{x}^{r}(y, z), d_{x}^{r}(y, w), and d_{x}^{r}(z, w) are equal. We consider t(x, y), t(y, z), and t(y, w). Clearly t(y, w) ⪯ t(y, z).

Case 1: t(x, y) ⪯ t(y, w). Then d_{x}^{r}(y, z) = m + 1 − d(t(x, y), t(y, z)), d_{x}^{r}(y, w) = m + 1 − d(t(x, y), t(y, w)), and d_{x}^{r}(z, w) = m + 1 − d(t(x, z), t(z, w)). Since T is a tree, the two smallest members of t(y, z), t(y, w), and t(z, w) are equal, and hence the two greatest members of d_{x}^{r}(y, z), d_{x}^{r}(y, w), and d_{x}^{r}(z, w) are also equal, as required.

Case 2: t(y, w) ≺ t(x, y) ⪯ t(y, z). Then d_{x}^{r}(y, z) = m + 1 − d(t(x, y), t(y, z)), d_{x}^{r}(y, w) = n−m+d(t(y, w), t(x, y)), and d_{x}^{r}(z, w) = n−m+d(t(z, w), t(x, z)), of which the latter two are the largest (being at least m + 1). But t(x, y) = t(x, z) and t(y, w) = t(z, w), and so these two largest are equal.

Case 3: t(y, w) ≺ t(y, z) ≺ t(x, y). Then d_{x}^{r}(y, z) = n − m + d(t(y, z), t(x, y)), d_{x}^{r}(y, w) = n − m + d(t(y, w), t(x, y)), and d_{x}^{r}(z, w) = n − m + d(t(x, w), t(x, z)). This time t(x, z) = t(y, z) and t(x, w) = t(y, w), and the result follows from the ultrametric inequality for d.

Case 4: t(y, w) = t(y, z) ≺ t(x, y). Then d_{x}^{r}(y, z) = n − m + d(t(y, z), t(x, y)), d_{x}^{r}(y, w) = n − m + d(t(y, w), t(x, y)), and d_{x}^{r}(z, w) = m + 1 − d(t(x, z), t(z, w)). As t(y, z) = t(y, w), the result follows.

III To show {z > x : d_{x}^{r}(y, z) ≤ i} is convex, let z_{1} ≤ w ≤ z_{2} where d_{x}^{r}(y, z_{1}), d_{x}^{r}(y, z_{2}) ≤ i. Then also d_{x}^{r}(z_{1}, z_{2}) ≤ i. We first show that d_{x}^{r}(z_{1}, w) ≤ i.

If d_{x}^{r}(z_{1}, z_{2}) ≤ \frac{n+1}{2} then t(x, z_{1}) ⪯ t(z_{1}, z_{2}) ⪯ t(z_{1}, w), so d_{x}^{r}(z_{1}, w) = m + 1−d(t(x, z_{1}), t(z_{1}, w)) ≤ m+1−d(t(x, z_{1}), t(z_{1}, z_{2})) ≤ i. Otherwise d_{x}^{r}(z_{1}, z_{2}) > \frac{n+1}{2}. If t(x, z_{1}) ⪯ t(z_{1}, w) then d_{x}^{r}(z_{1}, w) ≤ m+1 ≤ i is immediate. If t(z_{1}, w) ⪯ t(x, z_{1}) then d_{x}^{r}(z_{1}, w) = n−m+d(t(z_{1}, w), t(x, z_{1})) ≤ n−m+d(t(z_{1}, z_{2}), t(x, z_{1})) (since t(z_{1}, z_{2}) ⪯ t(z_{1}, w)) ≤ i.

We deduce that d_{x}^{r}(y, w) ≤ max(d_{x}^{r}(y, z_{1}), d_{x}^{r}(z_{1}, w)) ≤ i as required.

IV is immediate from the definition.

[figure: x; y; z; w]

Figure 3: Verification of V

V Suppose d_{x}^{r}(y, z) ≤ i ≤ n/2. Then t(x, y) ≺ t(y, z) and d(t(x, y), t(y, z)) ≥ m + 1 − i. Hence t(x, z) = t(x, y). See Fig. 3. Case 1: t(y, z) ⪯ t(z, w). Then t(x, z) ≺ t(z, w) and d(t(x, z), t(z, w)) ≥ m + 1 − i, so d_{x}^{r}(z, w) ≤ i. Case 2: t(z, w) ⪯ t(x, z). Then t(z, w) ≺ t(y, z) and d(t(z, w), t(y, z)) ≥ m + 1 − i, so d_{w}^{l}(y, z) ≤ i. Case 3: t(x, z) ≺ t(z, w) ≺ t(y, z). Since d(t(x, y), t(y, z)) ≥ m + 1 − i, either d(t(x, z), t(z, w)) ≥ m + 1 − i or d(t(z, w), t(y, z)) ≥ m + 1 − i, again giving d_{x}^{r}(z, w) ≤ i or d_{w}^{l}(y, z) ≤ i.

VI First suppose i ≤ m. Pick t ∈ T with t(x, y) ≺ t ≺ y such that d(t(x, y), t) = m + 1 − i and y(q) = 0 where (−∞, q) = dom t. Choose z ∈ M so that z|(−∞, q) = t, and z(q) = 1. Then y < z and d_{x}^{r}(y, z) = i.

If i ≥ n + 1 − m we use a similar argument with t ≺ t(x, y). If n = 2m + 1 and i = m + 1 we let z|(−∞, q) = y|(−∞, q) where (−∞, q) = dom t(x, y) and z(q) = y(q) + 1.

VII The argument is similar to that in VI. If i ≤ m, choose t so that t(x, y) ≺ t ≺ y and z branching to the left of y at t; if i ≥ n + 1 − m, choose t so that

[figure: x; w; y; z; x; w; y; z; x; w; y; z; j ≤ m; n = 2m + 1, j = m + 1; j ≥ n + 1 − m]

Figure 4: Verification of VIII

Figure 5: Verification of IX

t(x, y) ≺ t ≺ x and z branching to the right of x at t; and if i = m + 1 (n odd) let t = t(x, y) and z branch to the right of x and the left of y at t.

VIII The hypotheses ensure that t(x, y) ≺ t(y, z) and d(t(x, y), t(y, z)) = m+1−i. If j ≤ m choose t so that t(x, y) ≺ t ≺ t(y, z), d(t(x, y), t) = m+1−i, d(t, t(y, z)) = m + 1 − j, and if n is even and dom t = (−∞, q), then y(q) = 1. Take w ∈ M so that w|(−∞, q) = y|(−∞, q) and w(q) = y(q)−1. If j ≥ n+1−m choose t with t(y, z) ≺ t ≺ y and if n = 2m + 1 and j = m + 1 let t = t(y, z). See Fig. 4.

IX We are given that t(x, y) ≺ t(y, z) and d(t(x, y), t(y, z)) = m + 1 − j = max(m + 1 − k_{1}, m + 1 − k_{2}). Choose t with domain (−∞, q) satisfying t(x, y) ≺ t ≺ t(y, z), d(t(x, y), t) = m + 1 − k_{1}, d(t, t(y, z)) = m + 1 − k_{2}, and y(q) = 0. Let w ∈ M be such that w|(−∞, q) = y|(−∞, q) and w(q) = y(q) + 1. See Fig. 5. □

Theorem 4.6 Any two countable models of the list of axioms are isomorphic.

We prepare for the proof of Theorem 4.6 by proving a series of lemmas that follow from the universal axioms I-V. Dual versions also hold.

Lemma 4.7 Suppose that x < y < z < w and d_{x}^{r}(y, z) > n/2. Then (i) d_{x}^{r}(z, w) = d_{y}^{r}(z, w), (ii) d_{w}^{l}(y, z) ≥ d_{w}^{l}(x, y).

Proof (i) By Lemma 4.1(i) we have d_{x}^{r}(z, w) ≤ d_{y}^{r}(z, w), so we assume for a contradiction that d_{x}^{r}(z, w) < d_{y}^{r}(z, w), and hence that d_{w}^{l}(x, z) > d_{w}^{l}(y, z). By axiom II, d_{w}^{l}(x, z) = d_{w}^{l}(x, y). We consider two cases:

Case 1: d_{w}^{l}(x, z) ≤ (n + 1)/2. Then d_{w}^{l}(y, z) ≤ n/2, so by the dual of Lemma 4.1(iii), min(d_{w}^{l}(x, y), d_{x}^{r}(y, z)) ≤ d_{w}^{l}(y, z) ≤ n/2. But d_{w}^{l}(x, y) > d_{w}^{l}(y, z) and d_{x}^{r}(y, z) > n/2, so we have a contradiction.

Case 2: d_{w}^{l}(x, z) > (n + 1)/2. Then d_{w}^{l}(x, y) > (n + 1)/2, so d_{x}^{r}(y, w) < n + 1 − (n + 1)/2 = (n + 1)/2. Thus by axiom III d_{x}^{r}(y, z) ≤ d_{x}^{r}(y, w) ≤ n/2, contradicting the hypothesis.

(ii) By (i) we have d_{w}^{l}(y, z) = d_{w}^{l}(x, z) ≥ d_{w}^{l}(x, y). □

Lemma 4.8 Let A be a finite model of axioms I-V and let a < b be adjacent elements of A. Consider two models A∪{x_{1}} and A∪{x_{2}} of axioms I-V where a < x_{1} < b and a < x_{2} < b, and d_{a}^{r}(x_{1}, b) = d_{a}^{r}(x_{2}, b) > n/2. Then for every c > b, d_{c}^{l}(x_{1}, b) = d_{c}^{l}(x_{2}, b).

Proof By Lemma 4.7(i) we have d_{a}^{r}(b, c) = d_{x_{1}}^{r}(b, c) and d_{a}^{r}(b, c) = d_{x_{2}}^{r}(b, c), so d_{x_{1}}^{r}(b, c) = d_{x_{2}}^{r}(b, c). This implies d_{c}^{l}(x_{1}, b) = d_{c}^{l}(x_{2}, b). □

Lemma 4.9 Suppose that x < y < z < w.

(i) If d_{w}^{l}(x, y) < d_{w}^{l}(y, z) then d_{z}^{l}(x, y) = d_{w}^{l}(x, y).

(ii) If d_{w}^{l}(x, y) > d_{w}^{l}(y, z) then d_{x}^{r}(y, z) = min(d_{w}^{l}(y, z), d_{x}^{r}(y, w)).

Proof (i) By Lemma 4.1(i) d_{z}^{l}(x, y) ≥ d_{w}^{l}(x, y), so we assume for a contradiction that d_{z}^{l}(x, y) > d_{w}^{l}(x, y). But then d_{x}^{r}(y, z) < d_{x}^{r}(y, w), so by axiom II d_{x}^{r}(y, w) = d_{x}^{r}(z, w), and hence d_{w}^{l}(x, y) = d_{w}^{l}(x, z). Again using axiom II, d_{w}^{l}(x, y) ≥ d_{w}^{l}(y, z), contradicting the hypothesis.

(ii) By axiom III we have d_{x}^{r}(y, z) ≤ d_{x}^{r}(y, w). The dual version of Lemma 4.1(ii) says that either d_{x}^{r}(y, z) ≤ d_{w}^{l}(y, z) or d_{w}^{l}(x, y) ≤ d_{w}^{l}(y, z). Since d_{w}^{l}(x, y) > d_{w}^{l}(y, z), we must have d_{x}^{r}(y, z) ≤ d_{w}^{l}(y, z). Thus d_{x}^{r}(y, z) ≤ min(d_{w}^{l}(y, z), d_{x}^{r}(y, w)). On the other hand, Lemma 4.1(ii) says that either d_{x}^{r}(z, w) ≤ d_{x}^{r}(y, z) or d_{w}^{l}(y, z) ≤ d_{x}^{r}(y, z). In the former case, d_{x}^{r}(y, w) = d_{x}^{r}(y, z) by axiom II, so d_{x}^{r}(y, z) ≥ min(d_{w}^{l}(y, z), d_{x}^{r}(y, w)). In the latter case, the desired conclusion is immediate. □

Lemma 4.10 Let A be a finite model of axioms I-V and let a < b be adjacent elements of A. Consider two models A∪{x_{1}} and A∪{x_{2}} of axioms I-V where a < x_{1} < b and a < x_{2} < b and d_{b}^{l}(a, x_{1}) = d_{b}^{l}(a, x_{2}) = j ≤ n/2. For every a_{1} < a, if d_{b}^{l}(a_{1}, a) ≠ j then d_{a_{1}}^{r}(a, x_{1}) = d_{a_{1}}^{r}(a, x_{2}).

Proof If d_{b}^{l}(a_{1}, a) < j then by Lemma 4.9(i) we have d_{x_{1}}^{l}(a_{1}, a) = d_{b}^{l}(a_{1}, a) = d_{x_{2}}^{l}(a_{1}, a). This implies the desired conclusion by axiom IV. On the other hand, if d_{b}^{l}(a_{1}, a) > j then by Lemma 4.9(ii) we have d_{a_{1}}^{r}(a, x_{1}) = min(d_{b}^{l}(a, x_{1}), d_{a_{1}}^{r}(a, b)) = d_{a_{1}}^{r}(a, x_{2}). □

Lemma 4.11 Let A be a finite model of axioms I-V and let h < a be elements of A. Consider two models A ∪ {x_{1}} and A ∪ {x_{2}} of axioms I-V where a < x_{1} and a < x_{2}.

(i) If d_{x_{1}}^{l}(h, a) = d_{x_{2}}^{l}(h, a) ≤ \frac{n+1}{2} and h ≤ h_{1} < a then d_{h_{1}}^{r}(a, x_{1}) = d_{h_{1}}^{r}(a, x_{2})

(ii) If d_{h}^{r}(a, x_{1}) = d_{h}^{r}(a, x_{2}) ≤ \frac{n+1}{2} and h_{1} ≤ h then d_{h_{1}}^{r}(a, x_{1}) = d_{h_{1}}^{r}(a, x_{2}).

Proof (i) We distinguish two cases:

Case 1: Suppose d_{h}^{r}(h_{1}, a) > n/2. By Lemma 4.7 d_{h_{1}}^{r}(a, x_{1}) = d_{h}^{r}(a, x_{1}) and d_{h_{1}}^{r}(a, x_{2}) = d_{h}^{r}(a, x_{2}), so the result follows by axiom IV.

Case 2: Suppose d_{h}^{r}(h_{1}, a) ≤ n/2. Since d_{x_{1}}^{l}(h, a) = d_{x_{2}}^{l}(h, a) ≤ \frac{n+1}{2}, we have d_{h}^{r}(a, x_{1}) = d_{h}^{r}(a, x_{2}) ≥ n + 1 − \frac{n+1}{2} > d_{h}^{r}(h_{1}, a). Then the dual form of Lemma 4.9(ii) can be applied (twice) to give d_{x_{1}}^{l}(h_{1}, a) = min(d_{h}^{r}(h_{1}, a), d_{x_{1}}^{l}(h, a)) = min(d_{h}^{r}(h_{1}, a), d_{x_{2}}^{l}(h, a)) = d_{x_{2}}^{l}(h_{1}, a), and we again use axiom IV.

(ii) Since d_{x_{1}}^{l}(h, a) = d_{x_{2}}^{l}(h, a) > n/2, the dual of Lemma 4.7(i) gives d_{x_{1}}^{l}(h_{1}, h) = d_{a}^{l}(h_{1}, h) = d_{x_{2}}^{l}(h_{1}, h). As d_{x_{1}}^{l}(h, a) = d_{x_{2}}^{l}(h, a) we have d_{x_{1}}^{l}(h_{1}, a) = d_{x_{2}}^{l}(h_{1}, a) by the ultrametric inequality. □

Lemma 4.12 Suppose that A ∪ {x_{1}} and A ∪ {x_{2}} are two finite models of axioms I-V. Let a < b be consecutive elements of A with a < x_{1} < b and a < x_{2} < b and d_{a}^{r}(x_{1}, b) = d_{a}^{r}(x_{2}, b). Then A ∪ {x_{1}} ≅ A ∪ {x_{2}} if and only if for every a_{1} < a and b_{1} > b, d_{a_{1}}^{r}(a, x_{1}) = d_{a_{1}}^{r}(a, x_{2}) and d_{b_{1}}^{l}(x_{1}, b) = d_{b_{1}}^{l}(x_{2}, b).

Proof The only possible isomorphism is the identity on A extended by mapping x_{1} to x_{2}. For each y ∈ A, the functions d_{y}^{r} and d_{y}^{l} are determined by their values on pairs of consecutive arguments, using axioms I-III. In a first step using d_{a}^{r}(x_{1}, b) = d_{a}^{r}(x_{2}, b) we see that d_{a}^{r} coincides on A ∪ {x_{1}} and A ∪ {x_{2}} and similarly for d_{b}^{l}. In a second step we consider d_{c}^{r} for c < a and d_{d}^{l} for d > b. The only pairs of arguments we need to check are those involving x_{1} or x_{2}. But these are all covered by the hypotheses and the first step (using axiom IV). □

Lemma 4.13 Suppose h < a < x < b and d_{b}^{l}(h, a) = d_{b}^{l}(a, x) = i ≤ n/2. Then i ≤ d_{x}^{l}(h, a) ≤ n + 1 − i.

Proof By the dual of Lemma 4.1(i), d_{x}^{l}(h, a) ≥ d_{b}^{l}(h, a) = i. Suppose for a contradiction that d_{x}^{l}(h, a) > n + 1 − i. Then d_{h}^{r}(a, x) < i, so by axiom V either d_{h}^{r}(x, b) < i or d_{b}^{l}(a, x) < i. The latter contradicts the hypothesis. The former gives d_{b}^{l}(h, x) > n + 1 − i > n/2 ≥ i, but d_{b}^{l}(h, x) = i by axiom II. □

Lemma 4.14 Suppose h_{2} < h_{1} < a < x < b and d_{b}^{l}(h_{1}, a) = d_{b}^{l}(h_{2}, a) = i ≤ n/2. Then

(i) d_{h_{2}}^{r}(h_{1}, a) ≥ i,

(ii) if k_{1} = d_{x}^{l}(h_{1}, a), k_{2} = d_{h_{2}}^{r}(a, x), k = d_{h_{2}}^{r}(h_{1}, a), and k_{1}, k_{2} ≤ n/2, then k = min(k_{1}, k_{2}).

Proof (i) Suppose for a contradiction that d_{h_{2}}^{r}(h_{1}, a) < i. By axiom V, either d_{b}^{l}(h_{1}, a) < i or d_{h_{2}}^{r}(a, b) < i. The former possibility is contrary to the hypothesis, and the latter implies d_{b}^{l}(h_{2}, a) > n + 1 − i > n/2 ≥ i, also contrary to hypothesis.

(ii) This is just the dual of Lemma 4.1(v). □

Proof of Theorem 4.6 We can now conclude the proof of the theorem using Lemmas 4.8 and 4.10-4.14. We use a back-and-forth argument, showing that if p is an isomorphism from a finite substructure A of a model M onto a substructure A′ of a model M′, then for every x ∈ M there is x′ ∈ M′ such that the extension of p carrying x to x′ is a partial isomorphism. If |A|, |A′| ≤ 1 this is immediate (since all relations except for < are ternary).

We note first that we may assume that a < x < b for some a, b ∈ A. For if not, we may make that true by first extending p as follows. For example, if x is less than every element of A, use the dual of axiom VI to choose a ∈ A and a′ ∈ A′ such that d_{a}^{r}(c, d) = 1 = d_{a′}^{r}(c′, d′), where c, c′ are the smallest and d, d′ are the largest elements of A ∪ {x}, A′. It then follows that these equalities hold for every c, d ∈ A and c′, d′ ∈ A′. Extending p by sending a to a′ gives a partial isomorphism for which a < x < b. A similar argument using axiom VI handles the case where x exceeds every element of A.

Given x ∈ M − A, let a < b be consecutive elements of A with a < x < b and let a′, b′ be their images under p.

We may suppose that d_{b}^{l}(a, x) ≤ (n + 1)/2, for otherwise we would have d_{a}^{r}(x, b) ≤ (n + 1)/2 by axiom IV and the dual of the following argument would apply.

Case 1: Suppose that n = 2m + 1 and d_{b}^{l}(a, x) = m + 1. Then also d_{a}^{r}(x, b) = m+1. By axiom VII we select x′ ∈ M′ with a′ < x′ < b′ and d_{a′}^{r}(x′, b′) = m+1. We also adjoin a new element x′′ ∉ M′ to A′ such that the extension of p mapping x to x′′ is an isomorphism from A ∪ {x} onto A′ ∪ {x′′}. We show that A′∪{x′} ≅ A′∪{x′′}. Since d_{a′}^{r}(x′, b′) = m+1 and d_{a′}^{r}(x′′, b′) = d_{a}^{r}(x, b) = m+1, Lemma 4.8 applies to give for every b′_{1} > b′ d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′). Similarly, the dual of Lemma 4.8 applies (because n+1−(m+1) = m+1) to give for every a′_{1} < a′ d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). By Lemma 4.12, this is enough to establish the claimed isomorphism.

Case 2: Suppose that d_{b}^{l}(a, x) = i ≤ n/2. We distinguish further subcases. Case 2a: Suppose that for every h ∈ A if h < a then d_{b}^{l}(h, a) ≠ i. By axiom VII we select x′ ∈ M′ such that d_{b′}^{l}(a′, x′) = i. As in Case 1, we choose x′′ such that the extension of p mapping x to x′′ is an isomorphism from A ∪ {x} onto A′ ∪ {x′′} and show that A′ ∪ {x′} ≅ A′ ∪ {x′′}. Lemma 4.8 tells us that, for every b′_{1} ≥ b′, d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′), and Lemma 4.10 that, for all a′_{1} < a′, d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). By Lemma 4.12 this suffices.

Case 2b: Suppose that there exists h < a such that d_{b}^{l}(h, a) = i, d_{x}^{l}(h, a) = m + 1, and n = 2m + 1. Write h′ for the image of h under p. By the dual of axiom VIII, taking j = m + 1, we can select x′ ∈ M′ such that a′ < x′ < b′, d_{b′}^{l}(x′, a′) = i and d_{x′}^{l}(a′, h′) = m + 1. Choose x′′ such that A ∪ {x} ≅ A′ ∪ {x′′} via the extension of p mapping x to x′′. Lemma 4.8 gives us that for every b′_{1} ≥ b′, d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′). Let a′_{1} < a′. If a′_{1} ≥ h′, then Lemma 4.11(i) applies (with a′_{1} here playing the role of h_{1} in 4.11) to give d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). If a′_{1} ≤ h′, then Lemma 4.11(ii) applies to give d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). By Lemma 4.12 this suffices.

Case 2c: Suppose again that there is h < a such that d_{b}^{l}(h, a) = i, but this time that for every such h we have either d_{x}^{l}(h, a) ≤ n/2 or d_{h}^{r}(a, x) ≤ n/2 (no longer assuming that n = 2m + 1). Now Lemma 4.13 says that i ≤ d_{x}^{l}(h, a) and i ≤ d_{h}^{r}(a, x), so the hypothesis of this case immediately gives either i ≤ d_{x}^{l}(h, a) ≤ n/2 or i ≤ d_{h}^{r}(a, x) ≤ n/2. We use this for a further case division, according to whether all h < a satisfy the first inequality, all satisfy the second inequality, or some satisfy one and some satisfy the other.

Case 2c(i): Suppose that for all h < a with d_{b}^{l}(h, a) = i we have i ≤ d_{x}^{l}(h, a) ≤ n/2. We choose h < a minimal such that d_{b}^{l}(h, a) = i and let j = d_{x}^{l}(h, a). Write h′ for the image of h under p. Then by the dual of axiom VIII we may choose x′ ∈ M′ such that a′ < x′ < b′, d_{b′}^{l}(a′, x′) = i and d_{x′}^{l}(h′, a′) = j. Choose x′′ such that A ∪ {x} ≅ A′ ∪ {x′′} via the extension of p mapping x to x′′. Lemma 4.8 implies that for all b′_{1} > b′, d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′). Now let a′_{1} < a′. If h′ ≤ a′_{1} then by Lemma 4.11(i) we get d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). If a′_{1} < h′ then by the minimality of h we have d_{b′}^{l}(a′_{1}, a′) ≠ i, so Lemma 4.10 applies to give d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). Again we finish by Lemma 4.12.

Case 2c(ii): Suppose that for all h < a with d_{b}^{l}(h, a) = i we have i ≤ d_{h}^{r}(a, x) ≤ n/2. We choose h < a maximal such that d_{b}^{l}(h, a) = i. Let k = d_{h}^{r}(a, x) and j = n + 1 − k = d_{x}^{l}(h, a). Write h′ for the image of h under p. By the dual of axiom VIII we may choose x′ ∈ M′ such that a′ < x′ < b′, d_{b′}^{l}(a′, x′) = i, and d_{x′}^{l}(h′, a′) = j. Then d_{h′}^{r}(a′, x′) = k ≤ n/2. We choose x′′ such that A ∪ {x} ≅ A′ ∪ {x′′} via the extension of p mapping x to x′′. Lemma 4.8 implies that for all b′_{1} > b′, d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′). Now let a′_{1} < a′. If a′_{1} ≤ h′, then by Lemma 4.11(ii) we get d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). If h′ < a′_{1} then by the maximality of h we have d_{b′}^{l}(a′_{1}, a′) ≠ i, so Lemma 4.10 applies to give d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). Again we finish by Lemma 4.12.

Case 2c(iii): What remains is the case where there are h_{1}, h_{2} < a such that d_{b}^{l}(h_{1}, a) = d_{b}^{l}(h_{2}, a) = i, i ≤ d_{x}^{l}(h_{1}, a) ≤ n/2 and i ≤ d_{h_{2}}^{r}(a, x) ≤ n/2. Choose h_{1} minimal and h_{2} maximal satisfying these conditions. As d_{x}^{l}(h_{2}, a) ≥ n/2 + 1 > d_{x}^{l}(h_{1}, a), we have h_{2} < h_{1}. Furthermore, h_{2} and h_{1} are adjacent, for it follows from the minimality of h_{1} and the maximality of h_{2} that any h between them would satisfy d_{b}^{l}(h, a) = i and d_{x}^{l}(h, a), d_{h}^{r}(a, x) > n/2, contrary to the assumption of Case 2c.

Write k_{1} = d_{x}^{l}(h_{1}, a), k_{2} = d_{h_{2}}^{r}(a, x) and k = d_{h_{2}}^{r}(h_{1}, a). By Lemma 4.14(ii), k = min(k_{1}, k_{2}).

Write h′_{1} and h′_{2} for the images of h_{1} and h_{2} under p. Now by axiom IX we can find x′ ∈ M′ such that a′ < x′ and d_{h′_{2}}^{r}(a′, x′) = k_{1} and d_{x′}^{l}(h′_{1}, a′) = k_{2}. Because d_{b′}^{l}(h′_{2}, a′) = i ≤ m, we have d_{h′_{2}}^{r}(a′, b′) = n + 1 − i > n/2 ≥ k_{1} = d_{h′_{2}}^{r}(a′, x′), so x′ < b′.

By Lemma 4.1(v), d_{b′}^{l}(a′, x′) ≤ d_{b′}^{l}(h′_{2}, a′) = i and by Lemma 4.7(ii), d_{b′}^{l}(a′, x′) ≥ d_{b′}^{l}(h′_{1}, a′) = i. Therefore d_{b′}^{l}(a′, x′) = i.

Choose x′′ such that A ∪ {x} ≅ A′ ∪ {x′′} via the extension of p mapping x to x′′. By Lemma 4.8, for all b′_{1} > b′, d_{b′_{1}}^{l}(x′, b′) = d_{b′_{1}}^{l}(x′′, b′). Let a′_{1} < a′. If h′_{1} ≤ a′_{1}, then by Lemma 4.11(i), d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). If a′_{1} ≤ h′_{2} then by Lemma 4.11(ii) we have d_{a′_{1}}^{r}(a′, x′) = d_{a′_{1}}^{r}(a′, x′′). By Lemma 4.12, this finishes the proof. □

Theorem 4.15 Let N be a countable, weakly o-minimal, 2-indiscernible structure with domain N, ordering <, and n atoms of strictly increasing triples. Then those atoms may be listed so that

(N; =, <, (R_{i})_{1≤i≤n}) ≅ M_{n}.

Proof This follows at once from Theorems 4.3, 4.5, and 4.6. □

5 ℵ_{0}-categorical, weakly o-minimal, 3-indiscern-ible structures

The main result of this section is that such structures are in fact k-indiscernible for all finite k, which means that they are essentially equal to (ℚ, <) (and hence are o-minimal). For this it suffices to show that they are 4-indiscernible, since we may then use induction.

Theorem 5.1 Any ℵ_{0}-categorical weakly o-minimal 3-indiscernible structure is 4-indiscernible.

Proof Let the 4-atoms {R_{i}}_{1≤i≤n} of increasing quadruples be listed, as in previous sections, in such a way that R_{i}(x, y, z, t)∧R_{j}(x, y, z, t′)∧i < j ⇒ t < t′, and assume for a contradiction that n > 1. This time we get an ultrametric if we fix two points; in fact we get three ultrametrics, on the left, right, and in the middle. These are determined by R_{i}(x, y, z, t) ⇔ d_{xy}^{r}(z, t) = i ⇔ d_{xt}^{m}(y, z) = n+ 1−i ⇔ d_{zt}^{l}(x, y) = i, and d_{xy}^{r}, d_{xt}^{m}, and d_{zt}^{l} are then ultrametrics on (y, ∞), (x, t), and (−∞, z) respectively. The formula d_{xy}^{r}(z, t) = n + 1 − d_{x,t}^{m}(y, z) = d_{zt}^{l}(x, y) holds.

Lemma 5.2 There are a < b < x < y < z < c < d such that

d_{ab}^{r}(x, y) = d_{cd}^{l}(y, z) = 1, d_{ab}^{r}(y, z) = d_{cd}^{l}(x, y) = n.

Proof There are a_{1} < b_{1} < x_{1} < y_{1} < z_{1} such that R_{1}(a_{1}, b_{1}, x_{1}, y_{1}) and R_{n}(a_{1}, b_{1}, y_{1}, z_{1}), as one sees by starting with any a_{1} < b_{1} < y_{1} and then choosing appropriate x_{1} and z_{1}. Hence d_{a_{1}b_{1}}^{r}(x_{1}, y_{1}) = 1 and d_{a_{1}b_{1}}^{r}(y_{1}, z_{1}) = n. By 3-indiscernibility for any x < y < z there are a < b < x such that d_{ab}^{r}(x, y) = 1 and d_{ab}^{r}(y, z) = n. Similarly there are d > c > z such that d_{cd}^{l}(y, z) = 1 and d_{cd}^{l}(x, y) = n. □

Lemma 5.3 If a < b < x < y < z < c < d are as in Lemma 5.2 then also for every x′ ∈ (b, c], d_{ab}^{r}(x′, d) = n.

Proof d_{ab}^{r}(y, z) = n ⇒ d_{ab}^{r}(y, d) = n ⇒ d_{ad}^{m}(b, y) = 1 and d_{cd}^{l}(x, y) = n ⇒ d_{cd}^{l}(a, y) = n ⇒ d_{ad}^{m}(y, c) = 1 and therefore d_{ad}^{m}(b, c) = 1. This implies d_{ab}^{r}(c, d) = n. As for every x′ ∈ (b, c] d_{ab}^{r}(x′, d) ≥ d_{ab}^{r}(c, d) we have d_{ab}^{r}(x′, d) = n. □

Now continuing with the main proof, we may define various equivalence relations from the ultrametrics. The two we wish to concentrate on are defined from two parameters a < b: E_{ab}^{r}(x, y) for b < x, y if d_{ab}^{r}(x, y) ≤ 1 (x and y are ab-equivalent on the right), and E_{ab}^{l}(x, y) for x, y < a if d_{ab}^{l}(x, y) ≤ 1 (x and y are ab-equivalent on the left). If a < b < c < d as in Lemma 5.2 we can therefore discuss the equivalence of points of (b, c) under either E_{ab}^{r} or E_{cd}^{l}, but there is no obvious reason why there should be any relationship between the two. The idea of our proof is to exploit the possible interaction. We write E_{ab}^{r}(x) or E_{ab}^{l}(x) for the E_{ab}^{r}-class (E_{ab}^{l}-class respectively) of x.

In what follows we shall keep a < b < d fixed, and allow c to vary in I = {x ∈ (b, d) : d_{ab}^{r}(x, d) = n} (which is a 1-type over {a, b, d}). If E_{ab}^{r}(x) ⊆ (b, c) then a right c-companion of E_{ab}^{r}(x) is an E_{cd}^{l}-class R such that

inf E_{ab}^{r}(x) < inf R < sup E_{ab}^{r}(x) < sup R.

A left c-companion of E_{ab}^{r}(x) is an E_{cd}^{l}-class L such that

inf L < inf E_{ab}^{r}(x) < sup L < sup E_{ab}^{r}(x).

Lemma 5.4 (i) Any E_{ab}^{r}-class can have at most one right c-companion.

(ii) If R is a right c-companion of E_{ab}^{r}(x) then there is y ∈ R such that E_{ab}^{r}(x) < E_{ab}^{r}(y) ⊆ R.

(iii) For every c ∈ I there are at least one and at most finitely many E_{ab}^{r}- classes having a right c-companion.

Proof (i) Two right c-companions of E_{ab}^{r}(x) must contain a non-empty final segment of E_{ab}^{r}(x), and as they are equivalence classes of E_{cd}^{l}, must be equal.

(ii) By the results of §4 we know the ternary structure of (a, ∞), which in particular implies that < induces on (a, ∞) and the E_{ab}^{r}-classes a dense linear ordering. Choose y′ ∈ R − E_{ab}^{r}(x), and y so that E_{ab}^{r}(x) < E_{ab}^{r}(y) < E_{ab}^{r}(y′), and then E_{ab}^{r}(y) ⊆ (sup E_{ab}^{r}(x), y′) ⊆ R.

(iii) Since c ∈ I, by Lemma 5.3 it has the same type over {a, b, d} as in Lemma 5.2, so x, y, z as given by that lemma exist. Then E_{ab}^{r}(y) has E_{cd}^{l}(y) as its right companion since E_{ab}^{r}(x, y) ∧ ¬E_{ab}^{r}(y, z) but ¬E_{cd}^{l}(x, y) ∧ E_{cd}^{l}(y, z). (It is at this point that we have used n > 1. We know that d_{ab}^{r}(y, z) = n and as n > 1 it follows that d_{ab}^{r}(y, z) ≠ 1.)

If infinitely many E_{ab}^{r}-classes have a right c-companion, then by weak ominimality there is an interval J ⊆ (b, c) containing infinitely many E_{ab}^{r}-classes, such that for all x ∈ J, E_{ab}^{r}(x) has a right c-companion. Choose x_{1}, x_{2} ∈ J with E_{ab}^{r}(x_{1}) < E_{ab}^{r}(x_{2}), and let R be the right c-companion of E_{ab}^{r}(x_{1}). By (ii) and density there is y ∈ R such that E_{ab}^{r}(x_{1}) < E_{ab}^{r}(y) < E_{ab}^{r}(x_{2}) and E_{ab}^{r}(y) ⊆ R. Since the only E_{cd}^{l}-class meeting E_{ab}^{r}(y) is R, E_{ab}^{r}(y) cannot have a right c-companion, contradiction. □

This lemma justifies us in writing L_{c} for the least E_{ab}^{r}-class having a right c-companion, R_{c} for that right c-companion, and T_{c} for L_{c} ∪ R_{c}.

Lemma 5.5 Suppose that c_{1} ≤ c_{2} < d and that E_{1}, E_{2} are E_{c_{1}d}^{l}, E_{c_{2}d}^{l}-classes with non-trivial intersection. Then E_{1} ⊆ E_{2}.

Proof For x < y < c_{1} we have d_{xd}^{m}(y, c_{1}) ≤ d_{xd}^{m}(y, c_{2}). This implies d_{c_{1}d}^{l}(x, y) ≥ d_{c_{2}d}^{l}(x, y). Thus E_{1} ⊆ E_{2}. □

Lemma 5.6 If c_{1}, c_{2} ∈ I and R_{c_{1}} ⊂ R_{c_{2}} or T_{c_{1}} ⊆ R_{c_{2}} then c_{1} < c_{2}.

Proof If c_{2} ≤ c_{1} then by Lemma 5.5 we would have R_{c_{2}} ⊆ R_{c_{1}}. But R_{c_{1}} is a proper subset of R_{c_{2}}. □

Lemma 5.7 For any c ∈ I there are c′, c′′ ∈ I such that T_{c′} ∩ T_{c′′} = ∅ and T_{c′} ∪ T_{c′′} ⊆ R_{c} − L_{c}.

Proof Let φ(x) be the formula (with parameters a, b, d) which asserts

(∃c′ ∈ I)(E_{ab}^{r}(x) has a left c′-companion).

Since I is a 1-type over {a, b, d}, either (∀x ∈ I)φ(x) or (∀x ∈ I)¬φ(x).

Case 1: (∀x ∈ I)φ(x): By Lemma 5.4(ii) there are w_{1}, w_{2} ∈ R_{c} such that L_{c} < E_{ab}^{r}(w_{1}) < E_{ab}^{r}(w_{2}) and E_{ab}^{r}(w_{i}) ⊆ R_{c}. Since φ(w_{1}) holds, there is c′ ∈ I and a left c′-companion F of E_{ab}^{r}(w_{1}). Arguing as in Lemma 5.4(ii) there is w_{0} ∈ F such that L_{c} < E_{ab}^{r}(w_{0}) < E_{ab}^{r}(w_{1}) and E_{ab}^{r}(w_{0}) ⊆ F. As w_{0}, w_{2} ∈ I (and L_{c} ⊆ I) there are c_{0}, c_{2} ∈ I such that E_{ab}^{r}(w_{0}) = L_{c_{0}} and E_{ab}^{r}(w_{2}) = L_{c_{2}}. Now L_{c_{0}} ⊆ F and so R_{c_{0}} ∩ F ≠ ∅. By Lemma 5.5 R_{c_{0}} ⊆ F or F ⊆ R_{c_{0}}. But the latter is impossible since it would imply L_{c_{0}} ⊆ R_{c_{0}}, and we must have R_{c_{0}} ⊆ F. A similar argument shows that as L_{c_{2}} ⊆ R_{c} we must have R_{c_{2}} ⊆ R_{c}. We may therefore let c′ = c_{0} and c′′ = c_{2}.

Case 2: (∀x ∈ I)¬φ(x): Choose w_{1} ∈ R_{c} such that L_{c} < E_{ab}^{r}(w_{1}) ⊆ R_{c} and c_{1} ∈ I such that E_{ab}^{r}(w_{1}) = L_{c_{1}}. Then R_{c_{1}} ⊂ R_{c}. By Lemma 5.6 c_{1} < c. Choose y ∈ R_{c_{1}} and x ∈ L_{c_{1}} − R_{c_{1}}. Then x < y and x ∈ R_{c} − R_{c_{1}}. As x and y lie in R_{c}, d_{cd}^{l}(x, y) = 1, and so d_{xd}^{m}(y, c) = n. As x ∉ R_{c_{1}}, d_{c_{1}d}^{l}(x, y) > 1 and so d_{xd}^{m}(y, c_{1}) < n. It follows that d_{xd}^{m}(c_{1}, c) = n and hence d_{cd}^{l}(x, c_{1}) = 1. Thus c_{1} ∈ R_{c}. Since ¬φ(c_{1}), R_{c_{1}} < E_{ab}^{r}(c_{1}), as otherwise R_{c_{1}} would be a left c_{1}-companion of E_{ab}^{r}(c_{1}). Similarly, E_{ab}^{r}(c_{1}) ⊂ R_{c} (as otherwise R_{c} would be a left c-companion of E_{ab}^{r}(c_{1}). Now choose c_{2} ∈ I such that E_{ab}^{r}(c_{1}) = L_{c_{2}}. Then R_{c_{2}} ⊆ R_{c}, so this time we can let c′ = c_{1} and c′′ = c_{2}. □

We now conclude the proof of Theorem 5.1. Let m be a positive integer greater than the greatest number of convex sets required to express an arbitrary subset of the model definable from 4 parameters as a union of convex sets. The assumptions of ℵ_{0}-categoricity and weak o-minimality ensure that such m exists.

We let c_{00} ∈ I be arbitrary, and choose c_{i0}, c_{i1} by induction for i ≥ 1. Assuming that c_{i−1 0} has been defined, we let c_{i0} < c_{i1} in I be as given by Lemma 5.7 so that T_{c_{i0}}, T_{c_{i1}} are disjoint subsets of R_{c_{i−1 0}} − L_{c_{i−1 0}}. By Lemma 5.6, c_{i1} < c_{i−1 0}, hence

c_{m0} < c_{m1} < c_{m−1 0} < c_{m−1 1} < … c_{10} < c_{11} < c_{00}.

Pick e ∈ T_{c_{m0}}. Then e ∈ T_{c_{i0}} for each i ≤ m and e ∉ T_{c_{i1}} for each positive i ≤ m. The set A = {x ∈ I : e ∈ T_{x}} is thus a subset of the model which is definable over {a, b, e, d} but which cannot be written as the union of fewer than m convex sets, since c_{i0} ∈ A and c_{i1} ∉ A, contrary to the choice of m. □

6 Higher arities

The structures we have classified have been restricted to the binary and ternary cases. It is possible that by considering higher arities we may obtain new and essentially richer structures. The purpose of this section is to give some examples illustrating that there is a wide variety of ℵ_{0}-categorical weakly o-minimal structures. We shall not do things in full generality (which in any case seems unrealistic), and so concentrate on one of the easier structures described in §3.

First we give an example of a 2-indiscernible but not 3-indiscernible ℵ_{0}- categorical weakly o-minimal structure for which 4 is the smallest number k such that every formula true in the structure is logically equivalent to a boolean combination of formulae in k or fewer variables. Its domain M consists of all maps a from ℚ to ℚ such that supp a = {q : a(q) ≠ 0} is finite, and < is the lexicographic ordering. We let l : {(a, b) ∈ M^{2} : a < b} → ℚ be given by l(a, b) = the least q ∈ ℚ such that a(q) ≠ b(q) (in which case necessarily a(q) < b(q)). If x < y and z < w in M we let R(x, y; z, w) if l(x, y) < l(z, w). From this quaternary relation, which essentially allows us to refer to the set of levels of the tree {a|(−∞, q) : a ∈ M, q ∈ ℚ} as a linearly ordered structure, we may easily define

[figure: l(x, y) < l(z, w); l(x, y) = l(z, w); l(x, y) > l(z, w)]

Figure 6: Three increasing quadruples having distinct 4-types in M

the relevant ternary relations introduced before, which are given by T (x, y, z) ⇔ l(x, y) < l(y, z), V (x, y, z) ⇔ l(x, y) = l(y, z), and U(x, y, z) ⇔ l(y, z) < l(x, y). Alternatively, in this case the ternary structure may be captured by a single C-relation given by C(x; y, z) ⇔ T (x, y, z) ∨ T (x, z, y) ∨ U(y, z, x) ∨ U(z, y, x). We take M = (M; =, <, T, V, U, R) (though (M; =, <, R) would suffice). Note that there is a significant difference here between the function l defining levels, and the function t used earlier which defined greatest common initial segments, but which did not allow us to compare levels on different branches.

Theorem 6.1 M is a 2-indiscernible ℵ_{0}-categorical weakly o-minimal structure which admits elimination of quantifiers, it has 3 atoms of increasing triples, and 4 is the least number k such that every formula true in M is equivalent to a boolean combination of formulae in k or fewer variables.

Proof Everything follows from the next theorem, except for the final assertion. By definition it is immediate (appealing to quantifier elimination) that 4 is such a number k. On the other hand, in M there are three different 4-types of increasing quadruples (x, y, z, w) as portrayed in Fig. 6 (according as l(x, y) <, =, or > l(z, w)). But if we pick any 3-subtuple, the types agree in all three cases, which shows that 4 is the smallest k which will serve. □

We now give a construction procedure based on the above model to give a wider class of examples. Let P = (ℚ; =, <, (P_{i})_{i∈I}) be ℵ_{0}-categorical, weakly o-minimal, and admit elimination of quantifiers, where P_{i} has arity r_{i}. Let M = (M; =, <, T, V, U, R) be the structure described at the beginning of §6, and expand M to a structure M[P] having additional relations (P̂_{i})_{i∈I}, where P̂_{i} has arity 2r_{i}, and where, if a_{1}, …, a_{r_{i}}, b_{1}, …, b_{r_{i}} ∈ M, and a_{j} ≠ b_{j} for each j, M[P] ⊧ P̂_{i}(a_{1}, b_{1}, …, a_{r_{i}}, b_{r_{i}}) if and only if P ⊧ P_{i}(l(a_{1}, b_{1}), …, l(a_{r_{i}}, b_{r_{i}})) (where l is symmetrized to allow for both a_{j} < b_{j} and b_{j} < a_{j}). Note that if I = ∅, that is, we do not add any extra structure, then the result will be the structure M of the previous theorem.

Theorem 6.2 M[P] is ℵ_{0}-categorical, weakly o-minimal, and admits elimination of quantifiers.

Proof The key point is to establish the natural back-and-forth property, and everything then follows quite easily. If \overline{a} = (a_{1}, a_{2}, …, a_{n}) is a strictly increasing sequence of members of M[P] let us write \overline{c}\overline{a} for the sequence (of length \frac{1}{2}n(n − 1)) with entries l(a_{i}, a_{j}) for i < j in some standard order. The main point is that if \overline{a} and \overline{b} are two such sequences, then they have the same quantifier-free type in M[P] if and only if \overline{c}\overline{a} and \overline{c}\overline{b} have the same quantifierfree type in P. This precisely corresponds to the way in which P̂_{i} was defined from P_{i}.

Now let \overline{a} = (a_{1}, …, a_{n}) and \overline{b} = (b_{1}, …, b_{n}) be strictly increasing n-tuples of elements of M having the same quantifier-free type in M[P], and let a ∈ M − \{a_{1}, …, a_{n}\}. We have to find b ∈ M such that \overline{a}a and \overline{b}b have the same quantifier-free type in M[P].

For ease we suppose that for some i, a_{i} < a < a_{i+1} and we also suppose that U(a_{i}, a, a_{i+1}) or V (a_{i}, a, a_{i+1}) holds. (If a < a_{1} or a > a_{n} or T (a_{i}, a, a_{i+1}) a similar argument to the one given may be used.) Note that in this case the only possible element in the tuple \overline{c}_{\overline{a}a} not in \overline{c}\overline{a} is l(a_{i}, a), as for every j ≠ i we have l(a_{j}, a) = l(a_{j}, a_{i}) or l(a_{j}, a) = l(a_{i}, a). Of course l(a_{i}, a) may already appear in \overline{c}\overline{a}. We define c to be l(a_{i}, a).

By the remark above, \overline{c}\overline{a} and \overline{c}\overline{b} have the same quantifier-free type in P, and by quantifier elimination in P there is d in P so that \overline{c}\overline{a}c and \overline{c}\overline{b}d have the same quantifier-free type in P. Choosing b such that b_{i} < b < b_{i+1} and l(b_{i}, b) = d, \overline{a}a and \overline{b}b then have the same quantifier-free type in M[P], as required.

Next we verify weak o-minimality. For this it suffices to show that atomic formulae involving the new predicates P̂_{i} define finite unions of convex sets. Let

S = {x : M[P] ⊧ P̂_{i}(a_{1}, b_{1}, …, a_{r_{i}−1}, b_{r_{i}−1}, a_{r_{i}}, x)}

be a set defined in this way, and let l_{j} = l(a_{j}, b_{j}) for 1 ≤ j ≤ r_{i} − 1. Then {l : P ⊧ P_{i}(l_{1}, …, l_{r_{i}−1}, l)} is a finite union of convex sets in P, C_{1} ∪ … ∪ C_{s} say. Hence

S = {x : x < a_{r_{i}} ∧ l(a_{r_{i}}, x) ∈ C_{1}} ∪ … ∪ {x : x < a_{r_{i}} ∧ l(a_{r_{i}}, x) ∈ C_{s}}∪
{x : x > a_{r_{i}} ∧ l(a_{r_{i}}, x) ∈ C_{1}} ∪ … ∪ {x : x > a_{r_{i}} ∧ l(a_{r_{i}}, x) ∈ C_{s}}

is also a finite union of convex sets. □

Next we show how the construction of Theorem 6.2 can be iterated. Let us define N_{i} inductively by N_{0} = (ℚ :=, <), N_{i+1} = M[N_{i}]. Then the theorem immediately implies that each N_{i} is ℵ_{0}-categorical, weakly o-minimal, and admits elimination of quantifiers. Our task here is to show how N_{i+1} can be viewed as an expansion of N_{i} for each i so that we may form a limit structure, and to investigate the structure of the n-types in these structures well enough to show that the limit structure is itself ℵ_{0}-categorical and weakly o-minimal, with quantifier elimination. The key is to show that although the expansions are proper, they only affect the theory in higher and higher arities.

Let us write P ⊑ Q to mean that Q is isomorphic to an expansion of P. Saying that Q is an expansion of P (or that P is a reduct of Q) means that P and Q have the same domain, and every relation of the language of P is 0-definable in Q (since we are just considering relational languages here). This is equivalent (in our ℵ_{0}-categorical setting) to saying that the automorphism group of Q is a subgroup of the automorphism group of P. It is a proper expansion if Aut(Q) is a proper subgroup of Aut(P), written P ⊏ Q.

Now since N_{1} is densely linearly ordered without endpoints, it is an expansion of N_{0} (proper in fact, as one sees by counting types of increasing triples). Clearly the construction of Theorem 6.2 has the property that if P ⊑ Q then M[P] ⊑ M[Q], and it follows that

N_{0} ⊑ N_{1} ⊑ N_{2} …

We make a suitable identification of N_{i+1} with an expansion of N_{i} when required.

Theorem 6.3 (i) For each i there are strictly increasing tuples \overline{a}, \overline{b} of length i + 3 which have equal types in N_{i} but not in N_{i+1}.

(ii) If \overline{a} and \overline{b} are tuples of length ≤ i + 2 which have the same type in N_{i} then they have the same type in N_{i+1}.

Proof (i) The relevant tuples are defined inductively. When i = 0, we may take \overline{a} and \overline{b} to be increasing triples satisfying T (\overline{a}) and U(\overline{b}). Now assume that increasing i+3-tuples \overline{a} = (a_{0}, …, a_{i+2}) and \overline{b} = (b_{0}, …, b_{i+2}) have been chosen having different types in N_{i+1} but the same type in N_{i}. Choose an arbitrary member c of N_{i+1} = M[N_{i}], which is (by definition) a function from N_{i} to ℚ. The i + 4-tuples \overline{c} and \overline{d} are now given by c_{i+3} = d_{i+3} = c and

c_{j}(q) = \{ \begin{matrix}c(q) & if q ≠ a_{j} \\ c(q) − 1 & if q = a_{j} \end{matrix}

and

d_{j}(q) = \{ \begin{matrix}c(q) & if q ≠ b_{j} \\ c(q) − 1 & if q = b_{j} \end{matrix}

Thus c_{j} and d_{j} branch off from c to the left at the points a_{j} and b_{j} respectively, as shown in Fig.7.

Observe that for 0 ≤ j < k ≤ i + 3 we have l(c_{j}, c_{k}) = a_{j} and l(d_{j}, d_{k}) = b_{j}. It now follows that the sequences \overline{c} and \overline{d} have equal types in N_{i+1} but not in N_{i+2} (using the same remarks as in the previous theorem about the relation between the types in these two structures), establishing the induction step.

(ii) We show by induction on i that if \overline{a} and \overline{b} are sequences having at most i + 2 distinct entries, and having the same type in N_{i}, then they have the same type in N_{i+1}. The basis case i = 0 is immediate by 2-indiscernibility of N_{1}.

Now assume the result for i, and let \overline{a} and \overline{b} be strictly increasing sequences of elements N_{i+2} of length i + 3 having the same type in N_{i+1}. We may form

[figure: \overline{c}; \overline{a}; \overline{d}; \overline{b}]

Figure 7: The construction in Theorem 6.3(i)

the sequences \overline{c}\overline{a} and \overline{c}\overline{b} in N_{i+1} as in the proof of Theorem 6.2, \overline{c}\overline{a} and \overline{c}\overline{b} have the same type in N_{i}. The key point here is that these can have at most i + 2 distinct entries. This may be easily proved by induction; the reason is that a finite graph-theoretical tree without vertices of valency 2 has at least one more leaf than internal node. We may now appeal to the induction hypothesis to deduce that \overline{c}\overline{a} and \overline{c}\overline{b} have the same type in N_{i+1}, and hence that \overline{a} and \overline{b} have the same type in N_{i+2} as desired. □

Let N^{∗} be the relational structure whose domain is ℚ and whose family of relations is the union of those of all the N_{i}. By Theorem 6.3(ii) the i-types of N^{∗} are the same as those of N_{i}. Since N_{i} is ℵ_{0}-categorical this number is finite, and so N^{∗} is also ℵ_{0}-categorical. In addition we deduce that N^{∗} is weakly o-minimal and admits elimination of quantifiers. By Theorem 6.3(i) N_{i+1} is a proper expansion of N_{i} for each i, and so N^{∗} is a proper expansion of each N_{i}. Putting these remarks together it follows that N^{∗} is not finitely axiomatizable, and, more strongly, does not admit a finite language, in the sense that its automorphism group is not equal to the automorphism group of any structure (with the same domain) having a finite language.

We conclude by showing that there are 2^{ℵ_{0}} essentially different structures of the kind just described, which may be constructed by suitably modifying the same method. Above we used the notation M[P] to denote a structure obtained by using the domain P of P to index the levels of a copy of M_{3}. Here we use two such constructions which we can interlock in 2^{ℵ_{0}} ways, M_{0}[P], which is the same as M[P], and M_{1}[P] = M[P^{+}] where P^{+} is obtained from P by ‘naming a point’.

More precisely, if P is a 2-indiscernible ordered relational structure admitting elimination of quantifiers, we choose a ∈ P, and let P^{+} be the structure having new unary predicates D, M, U (for ‘down’, ‘middle’, and ‘up’) standing for (−∞, a), {a}, and (a, ∞) respectively, and for each relation symbol R(x_{1}, …, x_{n}) of P, new relational symbols corresponding to each way of replacing one or more of the variables by a. (In fact D, M, and U are of this form, but we wish to single them out particularly.) Then P^{+} is also relational and admits elimination of quantifiers. Since P is 1-indiscernible the resulting structure is independent of the choice of a, and as P is 2-indiscernible, D, M, and U are the only 1-atoms of P^{+}.

We now remark on the degree of indiscernibility possessed by M_{0}[P] and M_{1}[P]. If P is 1-indiscernible then M_{0}[P] is 2-indiscernible, since the ordered pairs (a_{1}, a_{2}), (b_{1}, b_{2}) have the same type in M_{0}[P] if and only if \overline{c}_{(a_{1},a_{2})} and \overline{c}_{(b_{1},b_{2})} have the same type in P. On the other hand, if P is 2-indiscernible, then M_{1}[P] is only 1-indiscernible, and has three 2-atoms of increasing pairs, given by D̂, M̂, and Û, as again follows by considering the possible types of \overline{c}_{(a_{1},a_{2})}. So if we wish to use combinations of the processes M_{0} and M_{1} to iterate and form a limit structure, we must ensure that M_{1} is never applied twice consecutively.

For each infinite binary sequence r = (r_{i} : i ∈ ω) the derived sequence r′ is obtained by deleting the first entry (so that r′_{i} = r_{i+1}). We define N_{n}^{r} over all r which do not contain two consecutive 1s (there are 2^{ℵ_{0}} such sequences) by induction on i thus:

N_{0}^{r} = (ℚ; =, <), N_{i+1}^{r} = M_{r_{0}}[N_{i}^{r′}].

So N_{i}^{r} = M_{r_{0}}[M_{r_{1}}[… M_{r_{i−1}}[(ℚ; =, <)] …] ]. The fact that N_{i}^{r} ⊑ N_{i+1}^{r} follows easily by induction, and so we obtain a ‘limit structure’ N^{r} having the same domain (ℚ) as each N_{i}^{r}, but whose language is the union of all their languages. The fact that the expansions N_{i+1}^{r} ⊐ N_{i}^{r} are all proper follows by the argument given in Theorem 6.3(i), and so N^{r} does not admit a finite language.

We next have to verify a version of Theorem 6.3(ii) for the new situation. We show by induction on i that if there are k 0s in r before the ith entry, and \overline{a} and \overline{b} are increasing sequences of length k having the same type in N_{i}^{r} then they also have the same type in N_{i+1}^{r}. For the induction step assume that \overline{a} and \overline{b} of length k have the same type in N_{i+1}^{r} = M_{r_{0}}[N_{i}^{r′}], and that there are at least k 0s in r before the (i + 1)th entry. If r_{0} = 0 then there are at least k − 1 0s in r′ before the ith entry and the induction goes through as in the original proof. If r_{0} = 1 then there are at least k 0s in r′ before the ith entry. Also \overline{c}\overline{a} and \overline{c}\overline{b} have the same type in (N_{i}^{r′})^{+}, and so if a′ is the named point, \overline{c}\overline{a}a′ and \overline{c}\overline{b}a′ have the same type in N_{i}^{r′}. Now \overline{c}\overline{a}a′ and \overline{c}\overline{b}a′ have at most k distinct entries, so by the induction hypothesis they have the same type in N_{i+1}^{r′}, and the proof is concluded as before. Since every r we consider has infinitely many 0s, this is strong enough for us to be able to deduce that N^{r} is ℵ_{0}-categorical, admits elimination of quantifiers, and is weakly o-minimal.

Now N^{r} = M_{r_{0}}[N^{r′}], and M_{r_{0}}[N^{r′}] has 2r_{0} + 1 2-atoms on increasing pairs, so it follows that if N^{r} and N^{s} are ‘isomorphic’ (meaning that their

[figure]

Figure 8: Possible levelled ordered trees having 4 leaves

automorphism groups are isomorphic as permutation groups) then r_{0} = s_{0}. We want to show that r_{i} = s_{i} for every i, and this will establish that we really have found 2^{ℵ_{0}} ‘essentially distinct’ examples. The following statement is sufficient:

(∗) \{ \begin{matrix}if for every k, M_{r_{0}}[N^{r′}] and M_{r_{0}}[N^{s′}] have the same number of \\ types of increasing k-tuples, then the same is true of N^{r′} and N^{s′}. \end{matrix}

For this we show how to work out the number of types of increasing k + 1tuples of M_{0}[P] and M_{1}[P] in terms of the number of types of increasing ≤ k + 1-tuples of P.

We say that a (finite) levelled ordered tree is a tree (T, ⪯) together with a function l from the set R of non-leaves of T onto a linearly ordered set (L, ≤) (of ‘levels’) such that if x < y in R then l(x) < l(y) in L, and a linear ordering of the set of immediate successors of each member of R. Let t_{k,n} be the number up to isomorphism of levelled ordered trees having n levels and k leaves. (In Fig. 8 we show the levelled ordered trees with 4 leaves, illustrating that t_{4,1} = 1 and t_{4,2} = t_{4,3} = 6.) We can then see that if P has n_{i} types of increasing i-tuples for i < k then M_{0}[P] and M_{1}[P] have ∑_{i<k} n_{i}t_{k,i} and ∑_{i<k}(in_{i} + (i + 1)n_{i+1})t_{k,i} types respectively of increasing k-tuples. The proof of this uses the link between a k-tuple \overline{a} in M_{0}[P] and \overline{c}\overline{a} in P remarked on several times before, and in addition the observation that the number of types of increasing i-tuples in P^{+} is equal to

i× the number of types of increasing i-tuples in P (those i-tuples containing the named point a as an entry in one of i possible positions)

+(i+1)× the number of types of increasing (i+1)-tuples in P (corresponding to those i-tuples not containing a as an entry, with i + 1 possible positions).

We are now in a position to verify the truth of (∗). We show by induction that N^{r′} and N^{s′} have the same number of types of increasing k-tuples. Let m_{i} and n_{i} be the numbers of types of increasing k-tuples of N^{r′} and N^{s′} respectively, and assume inductively that m_{i} = n_{i} for i < k. Then by the above calculation if r_{0} = 0 the numbers of types of increasing k+1-tuples of M_{r_{0}}[N^{r′}] and M_{r_{0}}[N^{s′}] are ∑_{i≤k} m_{i}t_{k+1,i} and ∑_{i≤k} n_{i}t_{k+1,i} respectively, and these are known to be equal. Applying the induction hypothesis we deduce, since t_{k+1,k} ≠ 0, that m_{k} = n_{k}, as desired. If r_{0} = 1 we consider instead the numbers of types of increasing k-tuples, which are ∑_{i<k}(im_{i} + (i + 1)m_{i+1})t_{k,i} and ∑_{i<k}(in_{i} + (i + 1)n_{i+1})t_{k,i} respectively. Since these are known to be equal, and t_{k,k−1} ≠ 0, we again deduce that m_{k} = n_{k}.

References

[1] S.Adeleke and Peter M. Neumann, Relations related to betweenness: their structure and automorphisms, Memoirs of the American Mathematical Society 623 (1998).

[2] Peter J. Cameron, Some treelike objects, Quarterly Journal of Mathematics, (2) 38 (1987), 155-183.

[3] M.A.Dickmann, Elimination of quantifiers for ordered valuation rings, Proceedings of 3rd Easter Model Theory Conference at Gross Köris, Seminarberichte, Humboldt University (1985).

[4] A.Pillay and C.Steinhorn, Definable sets in ordered structures I, Transactions of the American Mathematical Society 295 (1986), 565-592.