The 116 reducts of (ℚ, <, a)^{∗}

Markus Junker, Martin Ziegler

Mathematisches Institut Abteilung für mathematische Logik Universität Freiburg, Germany

July 2006, revised December 2007

Abstract This article aims to classify those reducts of expansions of (ℚ, <) by unary predicates which eliminate quantifiers, and in particular to show that, up to interdefinability, there are only finitely many for a given language. Equivalently, we wish to classify the closed subgroups of Sym(ℚ) containing the group of all automorphisms of (ℚ, <) fixing setwise certain subsets. This goal is achieved for expansions by convex predicates, yielding expansions by constants as a special case, and for the expansion by a dense, co-dense predicate. Partial results are obtained in the general setting of several dense predicates.

1 Introduction

In this article, we study expansions of (ℚ, <) by unary predicates that have quantifier elimination. Our goal is to classify the reducts and to show that, up to interdefinability, there are only finitely many such. Here, a reduct for us is a structure with domain ℚ in some relational language each of whose basic relations are ∅-definable in the original structure. We will consider two interdefinable reducts as the same structure. E.g. ℚ with the circular ordering coming from < is a reduct of (ℚ, <), and considered to be the same reduct as ℚ with the reverse circular ordering. All structures under consideration here are ℵ_{0}-categorical, and so we can identify a structure with its automorphism group, viewed as a permutation group on ℚ. A reduct then corresponds to a closed subgroup of the full symmetric group on ℚ containing the automorphism group of the original structure. Having finitely many reducts thus is implies that there are only finitely many closed subgroups of the symmetric group on ℚ containing the corresponding automorphism group. First we give a proof classifying the well-known reducts of (ℚ, <), which we believe to be simpler than the existing ones. Then we show that there are only finitely many reducts of the expanded structure by an explicit classification in the following two cases: Expansions of (ℚ, <) by convex subsets (which include the case of expansion by constants), and expansions by a dense and co-dense predicate. We have partial results for several dense predicates, and indicate how the general case of an expansion of (ℚ, <) by unary predicates that eliminates quantifiers reduces to the case of dense predicates. Our results support Simon Thomas’ conjecture (shown in [T1] to hold for the random graph and for the homogeneous universal K_{m}-free graphs, and in [T2] for random k-graphs): Conjecture If 𝔐 is a structure with quantifier elimination in a finite relational language, then 𝔐 has, up to interdefinability, only finitely many reducts.

∗Version 1.18

The condition is necessary: [AZ] describes infinitely many reducts of a doubled infinite-dimensio-nal projective space over 𝔽_{2}. That structure is totally categorical and axiomatisable in a finite relational language, but does not have quantifier elimination in a finite relational language. In [T1], there is an example due to Cherlin and Lachlan of a structure having quantifier elimination in a finite relational language and a reduct of this structure that does not have quantifier elimination in a finite relational language. This is never the case in our situation. In this context, the following questions seem to be open:

Question 1 Are the following properties invariant under bi-interpretability?

• to have quantifier elimination in a finite relational language

• to have finitely many reducts

Question 2 Do non-ℵ_{0}-categorical theories always have infinitely many reducts?

We would like to thank the referees for their helpful comments.

1.1 Notations, conventions, and some explanations

We will switch freely between the model theoretic and the group theoretic aspects. Most of the model theory used in this paper can be looked up in a standard textbook, e.g. [Ho] or [P2]. Following a suggestion of one of the referees, we have provided group theoretic translations of some model theoretic statements, so that at least the propositions and theorems should become understandable for non model theorists. All structures in this paper will be ℵ_{0}-categorical, i.e. have an oligomorphic automorphism group. Some of the definitions are only possible, and some of the group theoretic translations are only valid in this context. We always consider structures up to interdefinability (also called “definitional equivalence” in [Ho]), which allows us to identify an ℵ_{0}-categorical structure with its automorphism group. Hence we identify two reducts ℜ_{1}, ℜ_{2} of a structure 𝔐 if they have the same ∅-definable sets, or, equivalently, if Aut(ℜ_{1}) = Aut(ℜ_{2}). Different reducts may still be isomorphic as structures. This happens when the automorphism groups are isomorphic as permutation groups on M, which is the same as to say that they are conjugate in the symmetric group on M. In this case, we call ℜ_{1} and ℜ_{2} equivalent up to isomorphism. If ℜ is a reduct of 𝔐, we call |Aut(ℜ) : Aut(𝔐)| the index of ℜ in 𝔐. An equivalence relation is called finite if it has finitely many classes. If 𝔐 is ℵ_{0}-categorical, we let E_{𝔐} be the finest ∅-definable finite equivalence relation on M, i.e. the finest Aut(𝔐)- invariant equivalence relation with finitely many classes. This is the relation “having the same strong type over ∅”, or “having the same type over acl^{eq}(∅)”. We denote by 𝔐_{C} the expansion of 𝔐 by predicates for the E_{𝔐}-classes. (In our context, “∅-definable” means the same as “invariant under Aut(𝔐)”, and the elements of acl^{eq}(∅) are equivalence classes of finite Aut(𝔐)-invariant equivalence relations on some M^{n}, where Aut(𝔐) acts naturally on M^{n}. Invariance of a set or a relation is always meant as setwise invariance, unless otherwise specified. A (complete) type over a set corresponds to an orbit of the pointwise stabilizer of that set in the automorphism group.) Sym(X) denotes the symmetric group on a set X, Sym(n) or S_{n} the symmetric group on {1, …, n}, A_{n} the alternating group. For a finite permutation group, we often write its order as a superscript and the number of elements it acts on as a subscript. If x̄ = (x_{1}, …, x_{n}) ∈ X^{n} and σ ∈ S_{n}, then x̄^{σ} stands for (x_{σ(1)}, …, x_{σ(n)}). A type or a formula p(x_{1}, …, x_{n}) will be called strict if p ⊢ ⋀_{i≠j} x_{i} ≠ x_{j}. A tuple is strict if its type is strict. Partitions are usually meant to be given by subsets or predicates, not by an equivalence relation. If P is a subset of the domain of a structure and R an n-ary relation, then R_{P} denotes the restriction of R to P^{n}, and ¬P the complement of P.

1.2 The setting: expansions of (ℚ, <) with quantifier elimination

An expansion of (ℚ, <) by finitely many unary predicates is quantifier-free interdefinable with an expansion by unary predicates partitioning ℚ: Replace the predicates by the atoms of the generated boolean algebra. Then the first structure eliminates quantifiers if and only if the second does. If, for example, we add to (ℚ, <) a predicate for [0, +∞), then the point 0 becomes definable as the minimum of the new predicate, but it is not quantifier-free definable.

Lemma 1.1 Let ℚ be partitioned by unary predicates P_{1}, …, P_{n}. Then (ℚ, <, P_{1}, …, P_{n}) has quantifier elimination if and only if each P_{i} is either a singleton or infinite without maximum and minimum, and for all i, j, either P_{i} < P_{j}, or P_{j} < P_{i}, or P_{i} and P_{j} are dense in each other. Moreover, the structure is determined up to isomorphism by these data.

Proof: Suppose the structure eliminates quantifiers. A maximum or a minimum of P_{i} is definable, but not quantifier-free if P_{i} is not a singleton. If neither P_{i} < P_{j} nor P_{j} < P_{i}, then we get x_{1} < y < x_{2} with x_{1}, x_{2} ∈ P_{i} and y ∈ P_{j} (or vice versa). If follows that P_{i} is infinite, and that P_{j} is dense in P_{i} because all ordered pairs in P_{i} have the same quantifier-free type, hence the same type as (x_{1}, x_{2}). But then we also get the symmetric situation with i and j interchanged. Conversely, with the usual back and forth techniques it is easy to construct an automorphism of the structure between two tuples having the same quantifier-free type, or to construct an isomorphism between two structures with the same data. □

Note that there are ℵ_{0}-categorical expansions of (ℚ, <) by unary predicates that do not eliminate quantifiers.

The rest of the paper is organised as follows: In Section 2 we treat the case n = 0 of (ℚ, <) without predicates, and in Section 3 two other very special cases: expansions of ℚ by predicates without ordering, and reducts of the general case but with a unique strong 1-type. In Section 4, we study definable orderings in expansion of (ℚ, <) by unary predicates which eliminate quantifiers. These preparations allow us to give an explicit classification of all reducts of expansions by convex sets in Section 5. In Section 6, we consider the case of dense predicates, where a complete proof of Thomas’ conjecture is obtained for the case n = 2. Finally, Section 7 indicates how the general case follows from the dense case.

2 Reducts of the dense linear order (ℚ, <)

First we introduce the three non trivial relations definable from a dense linear order, and convenient notation for some of them.

• The unoriented linear order or betweenness relation “betw”:

betw(x, y, z) :⟺ y ∈ conv(x, z) ⟺ (x < y < z) ∨ (z < y < x)

where “conv” stands for the convex hull.

• The cyclic order “cyc”:

cyc(x, y, z) ⟺ \overrightarrow{xyz} :⟺ (x < y < z) ∨ (y < z < x) ∨ (z < x < y)

• The unoriented cyclic order or separation relation “sep”:

sep(w, x, y, z) ⟺ \overleftrightarrow{wxyz} :⟺ \overrightarrow{wxyz} ∨ \overrightarrow{zyxw}

• We extend our notation for the cyclic orders by defining

\overrightarrow{x_{1} … x_{n}} : ⟺ ⋀_{1⩽i<j<k⩽n} \overrightarrow{x_{i}x_{j}x_{k}} and \overleftrightarrow{x_{1} … x_{n}} :⟺ ⋀_{1⩽i<j<k<l⩽n} \overleftrightarrow{x_{i}x_{j}x_{k}x_{l}}

Note that there are always two interdefinable linear and two interdefinable cyclic orderings: an ordering and its reversed ordering; whereas no other betweenness or separation relation is ∅-definable from a dense linear order. In the rest of this section, we present a proof of the following theorem:

Theorem 2.1 Up to interdefinability, there are exactly five reducts of (ℚ, <), namely:

1. the dense linear order (ℚ, <) itself;

2. the betweenness relation coming from <;

3. the dense cyclic order coming from <;

4. the separation relation coming from <;

5. and the infinite set ℚ without structure.

This follows immediately from a theorem of Cameron classifying the highly homogeneous permutation groups on a countable set, see [C2] theorem 3.10. That result was first proved using group-theoretic methods in [C1]. A model theoretic approach is given in [HLS]). On of the referees pointed out that the theorem was first proved by Frasnay in [F]. We reprove Theorem 2.1 here by another method. We subsequently learned of the approach of Higman in [Hi], which is very similar to ours. We are able here to combine this approach with some basic model theory to provide an alternate proof of Cameron’s theorem.

2.1 The method

Let ℜ be a reduct of (ℚ, <). It is determined by the groups

G_{n}^{ℜ} := {σ ∈ S_{n} | (x_{1}, …, x_{n}) ≡ (x_{σ(1)}, …, x_{σ(n)}) in ℜ
for some (equivalently each) x_{1} < x_{2} < ⋯ < x_{n}},

because they determine the orbits of strict n-tuples. We call (G_{n}^{ℜ})_{n∈ℕ} the structure sequence of ℜ. When is a sequence of groups a structure sequence? We need some terminology: For i ∈ {1, …, n + 1}, let

• β_{i} : {1, …, n} → {1, …, i − 1, i + 1, …, n + 1} be the order preserving bijection,

• π_{i} : S_{n+1} → S_{n} be the map σ ↦ β_{σ(i)}^{−1} ∘ σ ∘ β_{i}.

We say that G_{n} extends to G_{n+1}, and write G_{n} ⊏ G_{n+1}, if π_{i}[G_{n+1}] = G_{n} for all i.

Lemma 2.2 A sequence (G_{n})_{n∈ℕ} with G_{n} ⩽ S_{n} is a structure sequence iff G_{n} extends to G_{n+1} for all n.

Proof: “⇒” is clear: choose a tuple x_{1} < ⋯ < x_{n+1} and consider all extracted n-tuples. “⇐”: the automorphism group of the (ℵ_{0}-categorical) structure is given by all bijections acting like an element of G_{n} on ordered n-tuples, and the condition ensures that this automorphism group acts exactly like G_{n}. □

Remark 2.3 (a) Since π_{σ(i)}(τ) ∘ π_{i}(σ) = π_{i}(τσ), we have ⋂_{i=1}^{n+1} π_{i}[G_{n+1}] ⩽ S_{n}.

It follows that G_{n+1} extends some group G_{n} ⩽ S_{n} iff all π_{i}[G_{n+1}] are equal.

(b) If G_{n} ⊏ G_{n+1}, then |G_{n+1}| ⩾ |G_{n}|.

(c) If G_{n} ⊏ G_{n+1} and |G_{n+1}| = |G_{n}|, then all maps π_{i} must be bijective.

2.2 The proof

We start to determine all possible structure sequences. We need the following subgroups of S_{n}:

• the identity group I_{n};

• the cyclic “swap group” of order 2 Z_{n}^{2} := ⟨ (1 n)(2 (n − 1)) ⋯ ([\frac{n}{2}] [\frac{n+3}{2}]) ⟩

• the cyclic “cycle group” of order n Z_{n}^{n} := ⟨(1 2 … n)⟩;

• and the dihedral “square group” D_{n}^{2n} := Z_{n}^{2} ⋉ Z_{n}^{n}.

2.2.1 The different orders

Lemma 2.4 (a) (I_{n}) is the structure sequence of the dense order, and obviously I_{n+1} is the only possible extension of I_{n} if n ⩾ 2.

(b) (Z_{n}^{2}) is the structure sequence of the betweenness relation, and it is the only possible structure sequence containing Z_{3}^{2}.

(c) (Z_{n}^{n}) is the structure sequence of the cyclic order, and it is the only possible structure sequence containing Z_{3}^{3}.

(d) (D_{n}^{2n}) is the structure sequence of the separation relation, and it is the only possible structure sequence containing D_{4}^{8}.

Proof: In each case, it is rather obvious that the sequences are the structure sequences of the given relations. For example, in case (d) it is clear that D_{n}^{2n} conserves the separation relation, hence that it is a subgroup of the n^{th} structure group. D_{n}^{2n} acts transitively, thus it is sufficient to show that the one-point stabilizers of the structure group equals those of D_{n}^{2n}, which are the “swap group around that point”. But after fixing one point, the betweenness relation, whose structure group is the swap group, is definable from the separation relation.

(a) is clear anyway. For (b), if a structure sequence (G_{n}) contains Z_{3}^{2}, it has to preserve the betweenness relation, hence G_{n} ⩽ Z_{n}^{2}. By induction, G_{n} has to have at least 2 elements, whence G_{n} = Z_{n}^{2}. Analogously for (c) and (d): if (G_{n}) contains Z_{3}^{3} or D_{4}^{8}, we get (G_{n}) ⩽ Z_{n}^{n} and (G_{n}) ⩽ D_{n}^{2n} and by induction |G_{n}| ⩾ n − 1 and |G_{n}| ⩾ 2n − 2 respectively, whence equality. □

2.2.2 The full symmetric group

Clearly, (S_{n}) is the structure sequence of the infinite set.

Lemma 2.5 π_{i} : G_{n+1} → S_{n} is not injective for some i iff G_{n+1} contains a cycle ζ of consecutive elements.

Proof: If π_{i}(σ) = π_{i}(τ) and σ ≠ τ, then σ(i) ≠ τ(i). Suppose σ(i) < τ(i). Then σ ∘ τ^{−1} = (σ(i) (σ(i) + 1) … τ(i)) is the desired cycle. Conversely, suppose ζ = (c (c + 1) … d) ∈ G_{n+1} and let σ = ζ ∘ τ for arbitrary τ. Then π_{i}(σ) = π_{i}(τ) for i = σ^{−1}(c). □

Lemma 2.6 (a) S_{2} only extends to Z_{3}^{2}, Z_{3}^{3} or S_{3}.

(b) S_{3} only extends to A_{4}, S_{4} or one of the three dihedral Sylow-2-subgroups of S_{4}.

(c) If n ⩾ 4, then S_{n} only extends to A_{n+1} or S_{n+1}.

Proof: (a) S_{3} has five subgroups with at least two elements. By Remark 2.3 (c) and Lemma 2.5, S_{2} does not extend to two of the one-point stabilizers. (b),(c) If S_{n} ⊏ G_{n+1}, then G_{n+1} has at least n! elements, hence index m ⩽ n + 1 in S_{n+1}. The action of S_{n+1} on the cosets of G_{n+1} provides a homomorphism S_{n+1} → S_{m} whose image has at least m elements. If n ⩾ 4, then A_{n+1} is simple. Hence either m = 1 and G_{n+1} = S_{n+1}, or m = 2 and G_{n+1} = A_{n+1}, or m = n + 1, and then the homomorphism above is an isomorphism and G_{n+1} the one-point stabilizer of itself, hence G_{n+1} ≅ S_{n}. If n = 3, the only further subgroups of S_{4} of index at most 4 are the three Sylow-2-subgroups of index 3. This proves (b). If G_{n+1} ≅ S_{n}, G_{n+1} is a one-point stabilizer, except for n = 5, since S_{6} has non-trivial outer automorphisms and therefore six “exotic” subgroups S_{6}^{ex1}, …, S_{6}^{ex6} isomorphic to S_{5} (given by the action of S_{5} on its six Sylow-5-subgroups). By Remark 2.3 (c) and Lemma 2.5, the one-point stabilizers are excluded. Inspection of the exotic groups shows, in some numbering, (123456) ∈ S_{6}^{ex1}; (2345) ∈ S_{6}^{ex2}; (1234), (3456) ∈ S_{6}^{ex3}; (1234), (23456) ∈ S_{6}^{ex4}; (12345), (3456) ∈ S_{6}^{ex5}; (2345) ∈ S_{6}^{ex6}. (This can also be deduced somewhat lengthily from the way the non-trivial outer automorphisms act on the conjugation classes of S_{6}). Hence S_{6}^{exi} does not extend S_{5} by Lemma 2.5. This proves the “only”-parts of the lemma. One can check without difficulties that the groups really extend to the given ones, but this is not necessary for the proof of the theorem. □

2.2.3 The remaining cases

Finally we show that the remaining cases — two dihedral groups and the alternating groups — can’t occur.

Lemma 2.7 D′_{4} = ⟨(12), (1324)⟩ does not extend S_{3}.

Proof: It is straightforward to check that π_{4}[D′_{4}] = {id_{3}, (12), (13), (123)} ≠ S_{3}. □

Lemma 2.8 D′′_{4} = ⟨(14), (1243)⟩ does not extend to any group.

Proof: The 4-ary relation R(a, b, c, d) induced by D′′_{4} is the following: “the unoriented intervals (a, d) and (b, c) lie one in the other”. Given five elements a < b < c < d < e, R allows to identify a and e up to “swap” as the two elements such that ⊧ R(a, x, y, e) for each choice x, y ∈ {b, c, d}. Then d is determined from a by R(a, x, y, d) with x, y ≠ e, analogously b from e. Thus all the elements are identifiable up to swap, the betweenness relation is definable from R and the structure sequence of (ℚ, R) must be (Z_{n}^{2}). □

Lemma 2.9 A_{n} has no extension if n ⩾ 4.

Proof: Consider all σ ∈ S_{n+1} such that π_{5}(σ) = (123). We show that some π_{i}(σ) is odd. Note that σ is determined by σ(5). 1^{st} case: σ(5) ⩾ 3. Then π_{3}(σ) has the same parity as σ and π_{1}(σ) has a different parity, whence one is odd. 2^{nd} case: σ(5) = 2. Then σ = (1452) and π_{3}(σ) = (1342) is odd. 3^{rd} case: σ(5) = 1. Then σ = (145) and π_{2}(σ) = (1234) is odd. □

This proves the theorem. The information might be put together in a final picture as follows:

I_{1} ⊏ I_{2} ⊏ I_{3} ⊏ I_{4} ⊏ I_{5} ⊏ I_{6} ⊏ … linear order
S_{2} ⊏ Z_{3}^{2} ⊏ Z_{4}^{2} ⊏ Z_{5}^{2} ⊏ Z_{6}^{2} ⊏ … betweenness
Z_{3}^{3} ⊏ Z_{4}^{4} ⊏ Z_{5}^{5} ⊏ Z_{6}^{6} ⊏ … cyclic order
S_{3} ⊏̸ D′_{4}
⊏ D_{4}^{8} ⊏ D_{5}^{10} ⊏ D_{6}^{12} ⊏ … separation
D′′_{4} ⊏̸
A_{4} ⊏̸
S_{4} ⊏ A_{5} ⊏̸
S_{5} ⊏̸ exotic S_{5}
⊏ A_{6} ⊏̸
S_{6} ⊏ … infinite set

2.3 Additional remarks

The proof of Theorem 2.1 also shows that the dense linear order, cyclic order, betweenness and separation relations eliminate quantifiers in their natural languages, since in each case, if n is the arity of the relation, the n^{th} group in the structure sequence already determines the whole sequence.

2.3.1 The lattice

The reducts of a given structure 𝔐 form a complete lattice. The infimum of a family (ℜ_{i})_{i∈I} is the structure whose basic relations are those which are ∅-definable in all structures ℜ_{i}; the supremum is the structure generated by the ∅-definable sets of all structures. Let the normalised structure 𝔐′ be the structure with domain M and 2n-ary basic relations tp^{𝔐}(x̄) = tp^{𝔐}(ȳ) for each n. Note that 𝔐′′ can be different from 𝔐′. If 𝔐 is ℵ_{0}-categorical, then 𝔐′ is a reduct of 𝔐, and if 𝔐 eliminates quantifiers in a finite relational language, then 𝔐′ has finite index in 𝔐. The group Perm(𝔐) of permorphisms of 𝔐 consists of the permutations of M inducing a bijection on the definable sets. If 𝔐 is ℵ_{0}-categorical, then Aut(𝔐′) = Perm(𝔐) = N_{Sym(M)}(Aut(𝔐)). The lattice of reducts of an ℵ_{0}-categorical structure carries the indices and the normaliser function ℜ ↦ ℜ′ as additional information. A general problem would be to classify all (finite) lattices with indices and normaliser function occurring as lattices of reducts of ℵ_{0}-categorical structures. Since Sym(ℵ_{0}) has no proper closed subgroups of finite index, the index over the smallest element (M, ∅) is always ∞. The lattice for (ℚ, <) looks as follows:

(ℚ, <)
∞ /  \ 2
(ℚ, cyc)  (ℚ, betw) = (ℚ, betw)′ = (ℚ, <)′
2 \  / ∞
(ℚ, sep)= (ℚ, sep)′ = (ℚ, cyc)′
| ∞
(ℚ, ∅)

The numbers are the indices. Aut(ℚ, betw) ≅ Aut(ℚ, <)⋊Z^{2} and Aut(ℚ, sep) ≅ Aut(ℚ, cyc)⋊ Z^{2}, where in both cases Z^{2} is generated by any of the order-reversing automorphisms of order 2. With other words, the relations < and cyc are exchanged with their complements on strict tuples. Aut(ℚ, cyc) is generated by Aut(ℚ, <) and bijections β_{c} moving irrational cuts c to the cut “at infinity”. That is, β_{c} is composed of order-preserving bijections (c, +∞) → (−∞, c) and (−∞, c) → (c, +∞), and reverses the ordering between the two parts. Aut(ℚ, <) acts transitively, Aut(ℚ, betw) and Aut(ℚ, cyc) act 2-transitively, and Aut(ℚ, sep) 3-transitively on ℚ. The random graph has exactly the same lattice as (ℚ, <), see [T1], as does the random tournament, see [B]. There is a surprising analogy between the reducts: the index 2 steps correspond to semi-direct products with an anti-isomorphism (exchanging edges and non-edges on strict pairs); the switching group corresponding to Aut(ℚ, cyc) is generated by bijections β_{Y} which are isomorphisms on a subset Y of vertices and on its complement, and anti-isomorphisms between Y and its complement. In particular, the groups act as transitively as do their counterparts.

2.3.2 Imaginaries

We consider the following two equivalence relations, definable in (ℚ, <). To simplify the terminology, we assume that they are only defined on strict tuples.

• The “equally ordered relation” E^{<}x̄ȳ: ⟺ tp(x_{1}, x_{2}) = tp(y_{1}, y_{2}),

• and the “equally circled relation”

E^{cyc}x̄ȳ: ⟺ ⋁_{σ∈A_{3}} tp((x_{1}, x_{2}, x_{3})^{σ}) = tp(y_{1}, y_{2}, y_{3})

• Both are special cases of a general “equally oriented relation” between strict m-tuples x̄ and strict n-tuples ȳ, which is σ ∈ A_{m} ⟺ τ ∈ A_{n} where σ ∈ S_{m} and τ ∈ S_{n} are such that x_{σ(1)} < ⋯ < x_{σ(m)} and y_{τ(1)} < ⋯ < y_{τ(n)}.

E^{<} is interdefinable with the betweenness relation and E^{cyc} with the separation relation, since by definition they are the normalised structures of (ℚ, <) and (ℚ, cyc). Alternatively, b ∈ conv(a, c) : ⟺ E^{<}abbc and \overleftrightarrow{abcd} : ⟺ E^{cyc}abccda, and E^{<} and E^{cyc} do not define the linear and cyclic ordering respectively, hence by the classification of the reducts (ℚ, E^{<}) = (ℚ, betw) and (ℚ, E^{cyc}) = (ℚ, sep). Both equivalence relations have exactly two classes (on strict tuples). When E^{<} is definable, then the E^{<}-classes and the E^{cyc}-classes are pairwise interdefinable as they are fixed by the same automorphisms, namely those not turning around the orientation. Thus is it sufficient to consider E^{cyc}. In (Q, <) and in (Q, cyc), the E^{cyc}-classes are definable, whereas in (ℚ, sep) and in (ℚ, betw) the two E^{cyc}-classes are conjugate. Thus the two conjugate E^{cyc}-classes correspond to the two linear (or cyclic) orderings inducing the betweenness (or separation) relation: Aut(ℚ, <) equals the stabiliser of the E^{cyc}-classes in Aut(ℚ, betw), and Aut(ℚ, cyc) in Aut(ℚ, sep).

Lemma 2.10 acl^{eq}(∅) = dcl^{eq}(∅) holds in each of (ℚ, <), (ℚ, cyc) and (ℚ, ∅), and acl^{eq}(∅) = dcl^{eq}(ℚ/E^{cyc}) in (ℚ, betw) and (ℚ, sep).

(Group theoretic translation: An equivalence class of a finite Aut-invariant equivalence relation on ℚ^{n} is itself invariant (as a set) in the first three structures, and invariant under those automorphisms fixing the E^{cyc}-classes in the other two structures.) Proof: acl(∅) = ∅ in all five structures. Thus the result holds for (ℚ, <) and (ℚ, ∅) because they weakly eliminate imaginaries (easy, or see [P1]). Elements of acl^{eq}(∅) correspond, up to interdefinability, to closed subgroups of finite index of the automorphism group (by [P1]). Suppose H is a proper closed subgroup of Aut(ℚ, cyc) of finite index. According to the classification of the reducts of (ℚ, <), H is not a supergroup of Aut(ℚ, <), thus H ∩ Aut(ℚ, <) is a subgroup of finite index of Aut(ℚ, <): contradiction. The same argument now shows that Aut(ℚ, <) and Aut(ℚ, cyc) are the only proper closed subgroups of finite index of Aut(ℚ, betw) and Aut(ℚ, sep) respectively. □

3 Two extreme cases

Let 𝔓 = (ℚ, <, P_{1}, …, P_{n}) be an expansion of (ℚ, <) by a partition of ℚ such that 𝔓 eliminates quantifiers, as described in Lemma 1.1. E_{𝔓} has been defined to be the relation “having same strong type over ∅ ”, which is the finest ∅-definable finite equivalence relation in 𝔓. Two elements x < y of same type have the same Lascar strong type, since they have the same type over the elementary submodel ℚ \ [x, y], hence E_{𝔓}xy = ⋀_{i=1}^{n}(x ∈ P_{i} ↔ y ∈ P_{i}). Let ℜ be an reduct of 𝔓. We consider two somehow opposite extreme cases: the case where there is no ordering at all, and the case where there is a unique strong 1-type.

3.1 No ordering

Recall that ℜ_{C} denotes the expansion of ℜ by predicates for the E_{ℜ}-classes. As E_{ℜ} is a coarsening of E_{𝔓}, each E_{ℜ}-class is a union of predicates P_{j}.

Theorem 3.1 The reducts ℜ of 𝔓^{−} := (ℚ, P_{1}, …, P_{n}) are, up to interdefinability, determined by E_{ℜ} and the finite structure ℚ/E_{ℜ} given by the action of Aut(ℚ/E_{ℜ}) = Aut(ℜ)/Aut(ℜ_{C}) on the E_{ℜ}-classes.

Proof: Let C_{1}, …, C_{k} be the E_{ℜ}-classes. It is easy to see that E_{ℜ} = E_{ℜ_{C}}. Thus 1-types in ℜ_{C} are strong types and hence stationary. Now we work in ℜ_{C}, which has Morley rank 1 because 𝔓^{−} does. Therefore forking is determined by the algebraic closure operator, which is trivial. Suppose x and y have the same type p, and assume ā is disjoint from x and y. Then ā is independent from x, and from y. It follows that tp(x/ā) = tp(y/ā), as they are the unique non-forking extension of p. This implies immediately Aut(ℜ_{C}) = Sym(C_{1})×⋯×Sym(C_{k}) and ℜ_{C} = (ℚ, C_{1}, …, C_{k}). It follows that ℜ is determined by Aut(ℚ/E_{ℜ}) as Aut(ℜ) consists of all permutations of ℚ respecting E_{ℜ} and having image in Aut(ℚ/E_{ℜ}). □

Clearly, all coarsenings of E_{𝔓^{−}} = E_{𝔓} occur as E_{ℜ}. If k is the total number of E_{ℜ}-classes and e the number of infinite (i.e. non-singleton) classes, all subgroups of S_{e} × S_{k−e} are possible as Aut(ℚ/E_{ℜ}). Moreover, it follows from the theorem that acl^{eq}(∅) in ℜ consists, up to definable closure, of the E_{ℜ}-classes, that is Aut(acl^{eq}(∅)) = Aut(ℚ/E_{ℜ}). This is because we may assume ℜ = ℜ_{C}, hence without loss of generality ℜ = 𝔓^{−}. There the claim holds since all types are stationary.

3.2 Only one strong type

Theorem 3.2 Let ℜ be a reduct of 𝔓 with a unique strong 1-type over ∅, i.e. without nontrivial finite Aut(ℜ)-invariant equivalence relations on R. Then ℜ is a reduct of (ℚ, <′) where <′ is a dense linear order on ℚ.

Proof: An n-ary relation S is called symmetric if ⊧ S(x̄) ⟺ ⊧ S(x̄^{σ}) for all σ ∈ S_{n} where (x_{1}, …, x_{n})^{σ} = (x_{σ(1)}, …, x_{σ(n)}). Claim Let S be an n-ary symmetric relation that is ∅-definable in 𝔓. Then S is ∅-definable in 𝔓^{−} := (ℚ, P_{1}, ..., P_{n}).

Proof: Suppose two n-tuples x̄ and ȳ have the same type in 𝔓^{−}. Then for some permutation σ ∈ S_{n}, x̄^{σ} and ȳ have the same type in 𝔓. It follows 𝔓 ⊧ S(ȳ) ⟺ 𝔓 ⊧ S(x̄^{σ}) ⟺ 𝔓 ⊧ S(x̄). ♢

Claim Let ℜ be as in the theorem. Given two strict n-tuples x̄ and ȳ, there is some x̄^{σ} having the same ℜ-type as ȳ. Proof: For fixed ȳ, we define

S(z̄) : ⟺ z̄ is strict and z̄^{σ} ≡^{ℜ} ȳ for some σ ∈ S_{n}

Since S is symmetric, it is ∅-definable in 𝔓^{−} by the first claim. On the other hand, S is ∅- definable in ℜ, hence (ℚ, S) does not define a non-trivial finite equivalence relation. It follows from Theorem 3.1 that S is ∅-definable in the trivial structure (𝔓, ∅). Since it holds for ȳ, it holds for all strict n-tuples, in particular for x̄. ♢

Now by Cameron’s theorem (Theorem 6.1 in [C1], or Theorem 3.3 below), ℜ is a reduct of a dense linear order on ℚ. □

We will see in Proposition 4.3 that <′ can be chosen to be ∅-definable in 𝔓.

3.3 A proof of the remaining part of Cameron’s theorem

In this section, we prove

Theorem 3.3 (Cameron) Let 𝔐 be a countable structure such that Aut(𝔐) acts transitively on [M]^{n} for all n. Then 𝔐 is isomorphic to a reduct of (ℚ, <).

Cameron’s original Main Theorem 6.1 in [C1] is equivalent to Theorems 2.1 and 3.3 here. The latter follows easily from the following two model theoretic lemmas.

Lemma 3.4 If 𝔐 is a structure which is indiscernible with respect to an ordering <, then there is an 𝔐′ ≡ 𝔐, which is indiscernible of same type with respect to some open dense linear ordering <′.

Note that the orderings <, <′ need not to be definable in 𝔐, 𝔐′ respectively. Proof: Choose (by the usual compactness and Ramsey arguments) an 𝔐′′ ≡ 𝔐 containing an infinite indiscernible sequence (I, <′) of same type as (M, <), where <′ is an open dense linear order. “Same type” here means that for all n, all tuples m_{1} < … < m_{k} in M and i_{1} <′ … <′ i_{k} in I and all formulas φ

𝔐 ⊧ φ(m_{1}, …, m_{k}) ⟺ 𝔐′′ ⊧ φ(i_{1}, …, i_{k}).

We show with Tarski’s test that I is an elementary substructure of 𝔐′′: Assume 𝔐′′ ⊧ ∃x φ(x, b̄′) with b̄′ ∈ I. Then for a tuple b̄ in 𝔐 of same <-order type as the <′-order type of b̄′, we have 𝔐 ⊧ ∃x φ(x, b̄), that is 𝔐 ⊧ φ(a, b̄) for some a. Choose a′ ∈ I such that (a′, b̄′) has same order type as (a, b̄), which exists because <′ is dense and open. It follows that 𝔐′′ ⊧ φ(a′, b̄′). Hence I ≼ 𝔐′′ and we let 𝔐′ = I. □

Lemma 3.5 Let 𝔐 be a countable structure. Equivalent are:

(a) For all n, the automorphism group of 𝔐 acts transitively on [M]^{n}.

(b) M is an indiscernible sequence with respect to some linear ordering <.

Proof: b) ⟹ a): Given two elements of [M]^{n}, then ordered as ascending strict n-tuples they have the same type.

a) ⟹ b): 𝔐 is ℵ_{0}-categorical, because Aut(𝔐) has finitely many orbits on M^{n} for each n. Hence one can find an infinite sequence I of pairwise distinct indiscernibles in 𝔐. Up to permutation, each finite A has the same type as any subset of I with the same cardinality as A. Hence A admits an ordering as indiscernibles. But this is enough (by compactness or by König’s lemma) to get an indiscernible ordering on M. □

Proof of Theorem 3.3: Let 𝔐 be as in the theorem. Then 𝔐 is ℵ_{0}-categorical and admits an indiscernible ordering < by Lemma 3.5, which by Lemma 3.4 and the ℵ_{0}-categoricity can be chosen to be dense and open. Indiscernibility implies Aut(M, <) ⊆ Aut(𝔐). (In fact, from the classification of the reducts one sees that the original ordering < is already dense if 𝔐 is not trivial, but it might have a maximum or a minimum in case 𝔐 is a cyclic ordering or a separation relation.) □

4 Definable generalised orderings

Terminology We call any structure isomorphic to one of the five reducts of (ℚ, <) a generalised ordering, linear and cyclic orderings are oriented, betweenness and separation relations are unoriented orderings, and an infinite set without structure is called the trivial case.

Let again 𝔓 = (ℚ, <, P_{1}, …, P_{n}) be an expansion of (ℚ, <) by a partition of ℚ and eliminating quantifiers. Our aim is to describe all ∅-definable generalised orderings in 𝔓. Let B = (B_{1}, …, B_{k}) be an ordered partition of ℚ such that each B_{i} is a union of predicates P_{j} that are pairwise dense in each other. Let <^{+} denote the ordered disjoint sum of orders, let <^{−1} be the reversed ordering of <, and <^{1} = <. Then in 𝔓 there are definable linear orderings

(ℚ, <_{B,χ}) := (B_{1}, <_{B_{1}}^{χ(1)}) <^{+} ⋯ <^{+} (B_{k}, <_{B_{k}}^{χ(k)})

on ℚ for every such B and every χ : {1, …, k} → {−1, 1}. Two such orderings <_{B,χ} and <_{B′,χ′} are equal if and only if B = B′ and χ and χ′ coincide on the infinite B_{i}; and interdefinable iff equal or reversed. An ordering <_{B,χ} is dense and open if and only if each singleton B_{i} is put between two infinite blocks B_{i−1} and B_{i+1}.

Lemma 4.1 𝔓 eliminates imaginaries, and dcl^{eq}(∅) = acl^{eq}(∅) holds.

(Cf. the explanation after Lemma 2.10; elimination of imaginaries means that the stabilizer of an element in acl^{eq}(∅) equals the pointwise stabilizer of some tuple of elements in 𝔓.) Proof: Clearly, 𝔓 has the following property: if ā ≡c̄ b̄, then there is a sequence ā = ā_{0} ≡c̄ ā_{1} ≡c̄ ā_{2} ⋯ ≡c̄ ā_{k} = b̄ such that ā_{i+1} differs from ā_{i} by just one element. This shows that Aut_{A∩B}(𝔓) = ⟨Aut_{A}(𝔓), Aut_{B}(𝔓)⟩ for finite A, B, which is Lascar’s criterion for weak elimination of imaginaries. This implies acl^{eq}(∅) = dcl^{eq}(acl(∅)). But acl(∅) = dcl(∅) in 𝔓. Finally, weak elimination implies full elimination because 𝔓 is a totally ordered structure. □

Corollary 4.2 In 𝔓, there is no non-trivial ∅-definable finite equivalence relation on the realisation set of a complete type (i.e. on an orbit of Aut(𝔓) on some P^{n}).

Proposition 4.3 Any ∅-definable generalised ordering in 𝔓 is a reduct of some <_{B,χ}.

We have defined a generalised ordering to be dense. Proposition 4.3 holds and is proved for the wider class of substructures of generalised ordering.

Proof: Let <′ be a ∅-definable linear order in 𝔓. Obviously, there are only two linear orders ∅-definable in (ℚ, <), namely < and the reversed order <^{−1}. Thus the restriction of <′ to P_{i} must either equal < or <^{−1}, and as in the proof of Lemma 1.1, quantifier elimination implies that for i ≠ j, either P_{i} <′ P_{j} or P_{j} <′ P_{i}, or P_{i} and P_{j} are dense in each other with respect to <′ (where the last case can only happen when P_{i} and P_{j} are dense in each other w.r.t. <). Density w.r.t. <′ is an equivalence relation on {P_{1}, …, P_{n}} and defines a partition B such that <′ equals some <_{B,χ}. Now let cyc′ be a ∅-definable cyclic order in 𝔓. As above, cyc′ restricted to P_{i} must be either cyc or cyc^{−1}. Assume first that some P_{i} is dense in ℚ with respect to cyc′. Then < on P_{i} allows to define a cut in cyc′, namely the cut at infinity in P_{i}, and therefore yields a ∅-definable linear order inducing cyc′. If no P_{i} is dense, then there is a cut in cyc′ determined by two predicates P_{i}, P_{j}, which again allows to define without parameters a linear ordering inducing cyc′. Assume finally that O is a ∅-definable betweenness or separation relation, and let E^{cyc} be the equivalence relation which is interdefinable with the separation relation definable from O, as in Section 2.3.2. Let C be an E^{cyc}-class. Then C is definable in 𝔓 by Lemma 4.1, so (ℚ, O, C) is a reduct of 𝔓 and defines the two linear (cyclic respectively) orderings inducing O. Hence O is a reduct of some <_{B,χ}. □

For further reference in Section 5.3, we note a special case:

Remark 4.4 If all predicates P_{i} are convex and k is the number of finite P_{i}, then there are, up to interdefinability, \binom{n−k−1}{k} · k! · (n − k)! · 2^{n−k−1} dense and open ∅-definable linear orderings, and \binom{n−k}{k} · k! · (n − k − 1)! · 2^{n−k−1} dense ∅-definable cyclic orderings.

5 Reducts of (ℚ, <) with a partition into convex sets

In this section we examine expansions of (ℚ, <) by a partition into convex sets. We will describe the reducts in Theorem 5.1 and Proposition 5.8. As usual, we assume that the expansion has quantifier elimination, i.e. that it is of the form 𝔔 := (ℚ, <, Q_{1}, …, Q_{n}) where Q_{1} < Q_{2} < ⋯ < Q_{n} and the Q_{i} are either singletons, or infinite without maximum and minimum. (Note that any expansion of (ℚ, <) by convex sets is interdefinable with such an expansion, but possibly with quantifiers). First we look at two special cases of this situation:

(1) Let (ℚ, <, R_{0}, …, R_{n}) be an expansion where R_{0} < R_{1} < ⋯ < R_{n} are all infinite convex sets without maximum and minimum. Let <_{i} := <↾_{R_{i}}. Then (ℚ, <, R_{0}, …, R_{n}) is interdefinable with the “free union of n + 1 dense linear orders” (ℚ, R_{0}, <_{0}, …, R_{n}, <_{n}). In particular

Aut(ℚ, <, R_{0}, …, R_{n}) = Aut(R_{0}, <_{0}) × ⋯ × Aut(R_{n}, <_{n})
≅ Aut(ℚ, <) × ⋯ × Aut(ℚ, <).

(2) The expansion by constants (ℚ, <, a_{1}, …, a_{n}) is interdefinable with (ℚ, <, Q_{0}, …, Q_{2n}) where Q_{2i−1} = {a_{i}} and Q_{2i} = (a_{i}, a_{i+1}) with a_{0} = −∞ and a_{n+1} = +∞. It is clear that for a choice of predicates R_{0}, …, R_{n} as above,

Aut(ℚ, <, a_{1}, …, a_{n}) = Aut(ℚ \ {a_{1}, …, a_{n}}, <, Q_{0}, Q_{2}, …, Q_{2n})
≅ Aut(ℚ, <, R_{0}, …, R_{n}).

It follows that the reducts of (ℚ, <, a_{1}, …, a_{n}) in which the constants are definable are in one-to-one correspondence with the reducts of (ℚ, <, R_{0}, …, R_{n}).

5.1 Classification of the reducts

Let ℜ be a reduct of 𝔔 with E_{ℜ}-classes C_{1}, …, C_{k}; say C_{1}, …, C_{e} are infinite and C_{e+1}, …, C_{k} finite, hence singletons. Recall that each C_{i} is a union of predicates Q_{j}. Unless otherwise specified, acl^{eq}(∅) and Aut(acl^{eq}(∅)) will always be meant in ℜ, i.e. Aut(acl^{eq}(∅)) is the group of permutations of acl^{eq}(∅) induced by Aut(ℜ). Let Aut_{C}(acl^{eq}(∅)) be the normal subgroup of Aut(acl^{eq}(∅)) fixing all classes C_{i} setwise. The aim now is to prove:

Theorem 5.1 ℜ is determined by E_{ℜ}, the action of Aut(acl^{eq}(∅)), and the generalised orderings O_{i} induced on the infinite classes C_{i} by ℜ_{C}.

These generalised orderings O_{i} will be introduced in Lemma 5.2; they are completely known by Proposition 4.3. An analysis of acl^{eq}(∅) comes in Proposition 5.6. In particular there will be only finitely many possibilities for the data above. A description of how ℜ is determined by these data follows in Proposition 5.8.

Lemma 5.2 The induced structure on an infinite C_{i} by ℜ_{C} is a generalised ordering O_{i}.

Note that O_{i} is only determined up to orientation, but otherwise unique. Proof: Since C_{i} ∈ acl^{eq}(∅), the strong types in ℜ_{C} = (ℜ, C_{1}, …, C_{k}) are the same as in ℜ, therefore E_{ℜ_{C}} = E_{ℜ}. It follows that the induced structure ℜ_{C} ↾_{C_{i}} has a unique strong 1-type. Now ℜ_{C} ↾_{C_{i}} is a reduct of 𝔔 ↾_{C_{i}}, hence a generalised ordering as it satisfies the hypotheses of Theorem 3.2. □

Unlike the situation in Section 3.1, fixing E_{ℜ}-classes can induce additional structure on the other classes: Example Let A be an infinite predicate together with a dense betweenness relation betw_{A}, and an equivalence relation E with two infinite classes without structure on the complement of A. We add additional structure such that the automorphisms are exactly the maps that respect betw_{A} and E and exchange the two E-classes iff they change the orientation of the order on A. Then fixing the E-classes induces a linear order on A. □

Let ℜ_{C}^{−} be the reduct (ℚ, C_{1}, …, C_{k}, O_{1}, …, O_{e}) of ℜ_{C}, i.e. the free union of the structures (C_{1}, O_{1}), …, (C_{e}, O_{e}) plus the singletons C_{e+1}, …, C_{k}. Furthermore, let ℜ_{C}^{+} be the expansion of ℜ_{C} by the (imaginary) elements in C_{i}/E_{C_{i}}^{cyc} for all i for which O_{i} is an unoriented ordering (where E_{C_{i}}^{cyc} is the equivalence relation interdefinable with O_{i} as defined in Section 2.3.2).

Because ℜ_{C}^{+} is an expansion of ℜ_{C} by finitely many elements of acl^{eq}(∅), we get on the one hand that ℜ_{C}^{+} has finite index over ℜ_{C}, on the other hand that E_{ℜ_{C}^{+}} = E_{ℜ}. This implies with the proof of Lemma 5.2 that the structure induced on C_{i} by ℜ_{C}^{+} is a generalised ordering O_{i}^{+} expanding O_{i}. We will see in Proposition 5.6 that ℜ_{C}^{+} already the expansion by all of acl^{eq}(∅).

Lemma 5.3 O_{i}^{+} is the oriented version of an unoriented ordering O_{i}, and equals O_{i} in the other cases.

Proof: As ℜ_{C}^{+} has finite index in ℜ_{C}, the index |Aut(ℜ_{C}) ↾_{C_{i}} : Aut(ℜ_{C}^{+}) ↾_{C_{i}} | is finite. Then the index of the completions |Aut(C_{i}, O_{i}) : Aut(C_{i}, O_{i}^{+})| is finite, too. Hence O_{i}^{+} equals O_{i} if the latter is trivial or already oriented, and is the oriented version of O_{i} in the other cases because we have added the “orientations” C_{i}/E_{C_{i}}^{cyc}. □

Lemma 5.4

Aut(ℜ_{C}^{−}) ≅ Aut(C_{1}, O_{1}) × ⋯ × Aut(C_{e}, O_{e})
Aut(ℜ_{C}^{+}) ≅ Aut(C_{1}, O_{1}^{+}) × ⋯ × Aut(C_{e}, O_{e}^{+})

The isomorphisms are the natural isomorphisms as permutation groups.

Proof: The first statement is by definition of ℜ_{C}^{−}. If 𝔐 is a structure and A ⊆ M, we let 𝔐(A) be the expansion of 𝔐 by constants for the elements of A. Claim Any relation definable on C_{i} in ℜ_{C}^{+}(ℚ \ C_{i}) is a generalised ordering. Proof: Assume that new structure on C_{i} is definable with parameters ā ∈ ℚ\C_{i}. The structure ℜ_{C}^{+}(ā) is a reduct of 𝔔(ā), which is also an expansion of (ℚ, <) by convex sets. Hence we get the result by Theorem 3.2 if we show that the induced structure on C_{i} by ℜ_{C}^{+}(ā) has a unique strong 1-type. We will work in ℜ_{C}^{+} and show that fixing pointwise ℚ \ C_{i} does not induce new strong 1-types on C_{i}. For this, refine E_{ℜ} on C_{i} by the the equivalence relation “having same strong type over the union of the other E_{ℜ}-classes”. It is ∅-definable because of the ℵ_{0}-categoricity and has finitely many classes because even in 𝔔 there are only finitely many strong types in C_{i} over ℚ \ C_{i}. Hence it equals E_{ℜ}. ♢

Claim ℜ_{C}^{+}(ℚ \ C_{i}) does not induce more structure on C_{i} than ℜ_{C}^{+}. Proof: If ā, b̄ ∈ ℚ \ C_{i} have the same type in 𝔔, there is α ∈ Aut_{C_{i}}(𝔔) mapping ā onto b̄. Hence ā and b̄ induce the same generalised ordering S on C_{i}. Since 𝔔 has only finitely many types of given length, S has finite orbit under Aut(ℜ_{C}^{+}). This implies that the stabiliser of S has finite index in Aut(ℜ_{C}^{+}). As in the proof of Lemma 5.3 we can conclude from the finiteness of |Aut(ℜ_{C}^{+})↾_{C_{i}}: Aut(ℜ_{C}^{+}(ā))↾_{C_{i}} | that |Aut(C_{i}, O_{i}^{+}) : Aut(C_{i}, S)| is also finite. Because O_{i}^{+} is already oriented, O_{i}^{+} = S. ♢

The second claim shows that every automorphism of (C_{i}, O_{i}^{+}) can be extended by the identity to an automorphism of ℜ_{C}^{+}, which proves the second statement. □

Corollary 5.5 C_{i} is stably embedded in ℜ_{C}, i.e. Aut(C_{i}, O_{i}) = Aut(ℜ_{C})↾_{C_{i}}.

Proof: If α ∈ Aut(C_{i}, O_{i}) preserves O_{i}^{+}, it can be extended by the identity to an automorphism of ℜ_{C}^{+}. In the other case, choose β ∈ Aut(ℜ_{C}) which also changes the orientation on C_{i}. Then extend β ↾_{C_{i}} ∘ α and compose with β^{−1}. □

Let O_{i}^{−} be the unoriented version of an oriented O_{i}, and equal O_{i} in the other cases. Let C^{or} ⊆ acl^{eq}(∅) consist of the classes C_{1}, …, C_{k} and the imaginary elements in C_{i}/E_{C_{i}}^{cyc} for the infinite C_{i} for which O_{i}^{−} is not trivial.

Proposition 5.6 In ℜ, acl^{eq}(∅) = dcl^{eq}(C^{or}).

(That is: An automorphism of ℜ fixing the equivalence classes in C^{or} setwise, fixes all the elements of acl^{eq}(∅).) Proof: By definition of ℜ_{C}^{+}, Aut(ℜ_{C}^{+}) is the stabiliser of the algebraic elements in C^{or}. Now an algebraic element not definable over those would correspond to a proper closed subgroup of finite index. But according to Lemma 5.4, Aut(ℜ_{C}^{+}) is a direct product of groups without proper closed subgroups of finite index, hence itself a group without proper closed subgroups of finite index. □

Remark: This proposition clarifies what is meant with “the action of Aut(acl^{eq}(∅))” in Theorem 5.1, as an automorphism of acl^{eq}(∅) is determined by its action on the finitely many imaginary elements in C^{or}. For Proposition 5.6, one could make C^{or} even smaller by throwing away the elements C_{i}/E_{C_{i}}^{cyc} for which O_{i} is oriented.

Corollary 5.7 Aut(acl^{eq}(∅)) is finite. □

Proposition 5.8 Aut(ℜ) consists of all α ∈ Sym(ℚ) such that

• α respects E_{ℜ} (which allows to define C_{α(i)} := α[C_{i}]);

• α ↾_{C_{i}}: (C_{i}, O_{i}^{−}) → (C_{α(i)}, O_{α(i)}^{−}) is an isomorphism for all i ⩽ e;

• the induced map ᾱ ∈ Sym(C^{or}) is in Aut(C^{or}).

Proof: Each of the conditions makes sense by the previous one. In particular, the induced map exists because isomorphisms (C_{i}, O_{i}^{−}) → (C_{j}, O_{j}^{−}) map the orientations C_{i}/E_{C_{i}}^{cyc} onto C_{j}/E_{C_{j}}^{cyc}. It is clear that automorphisms of ℜ have to satisfy the conditions. (For the second, note that α[O_{i}^{−}] is definable from O_{α(i)}, therefore α[O_{i}^{−}] and O_{α(i)}^{−} are equal as unoriented generalised orderings of same type). Conversely, assume that α satisfies the conditions. Then there is β ∈ Aut(ℜ) inducing the same map β̄ = ᾱ on C^{or}. Then γ := β^{−1} ∘ α still satisfies the conditions, but fixes C^{or}. Hence for infinite C_{i}, γ ↾_{C_{i}} is not only an O_{i}^{−}-isomorphism, but an O_{i}^{+}-isomorphism. Thus γ ∈ Aut(ℜ_{C}^{+}) ⩽ Aut(ℜ_{C}) by Lemma 5.4. □

This proves Theorem 5.1 and Thomas’ conjecture for 𝔔, since Aut(ℜ) is determined by finitely many data.

5.2 Complements

(1) We consider C^{or} as a two-sorted finite structure ℭ^{or}: the first sort consists of the classes C_{1}, …, C_{k} and is partitioned by four colours, one for each type of induced generalised ordering O_{i}^{−}, plus one for singleton classes; and there is a function mapping the elements of C_{i}/E_{C_{i}}^{cyc} (of second sort) onto C_{i}. Then Theorem 5.8 shows that a reduct ℜ is determined by ℭ^{or} and a sub-permutation group of Aut(ℭ^{or}). All subgroups occur.

(2) It is possible to find sections of the canonical epimorphism Aut(ℜ) → Aut(acl^{eq}(∅)). Choose

• an order-reversing involution ι_{i} on each C_{i} for which O_{i}^{−} is not trivial, and

• an isomorphism α_{ij} : (C_{i}, O_{i}^{−}) → (C_{j}, O_{j}^{−}) for all (i, j) for which C_{i} and C_{j} are conjugate under Aut(acl^{eq}(∅)),

such that α_{ii} = id, α_{jk} ∘ α_{ij} = α_{ik}, and ι_{j} ∘ α_{ij} = α_{ij} ∘ ι_{i}, and construct automorphisms from these maps as described in the proof of Proposition 5.8. Then Aut(ℜ) is a generalised semi-direct product

Aut(ℜ_{C}) ⋊_{Aut_{C}(acl^{eq}(∅))} Aut(acl^{eq}(∅))

as in the following fact.

Fact 5.9 (generalised semi-direct product) Let H, N be groups and α : H → Aut(N) a morphism, let K_{N} ⩽ N, K_{H} ⩽ H and φ : K_{N} → K_{H} an isomorphism such that

(1) φ(k)^{h} = φ(k^{α(h)}) for k ∈ K_{N} and h ∈ H, and

(2) n^{α(φ(k))} = n^{k} for k ∈ K_{N} and n ∈ N.

The generalised semi-direct product N ⋊_{K} H is the group (N ⋊H)/K where K := {(n^{−1}, φ(n)) | n ∈ K_{N}}. Inner version: If N ◁ G and H ⩽ G such that G = HN and K = H ∩ N, then G is isomorphic to the generalised semi-direct product N ⋊_{K} H where α is conjugation and φ the identity.

If N ≅ M^{n} and H ⩽ S_{n} acts on the coordinates of the product, we get a generalised wreath product M ≀_{K} H.

5.3 The case n = 2: reducts of (ℚ, <, Q_{1}, Q_{2}) and (ℚ, <, a)

Theorem 5.10 Let Q_{1} be a proper initial segment of ℚ without supremum, Q_{2} its complement. 𝔔 = (ℚ, <, Q_{1}, Q_{2}) has 53 reducts up to interdefinability, and 32 reducts up to isomorphism.

Proof: According to our analysis, we get: (A) 29 reducts ℜ where Q_{1} is definable:

(a) 25 reducts (15 up to isomorphism) with Aut(ℜ) ≅ Aut(Q_{1}, O_{1}) × Aut(Q_{2}, O_{2}) for generalised orderings O_{i}.

(b) 4 (3) reducts with Aut(ℜ) ≅ (Aut(Q_{1}, O_{1}) × Aut(Q_{2}, O_{2})) ⋊ Z^{2} for oriented generalised orderings O_{i} (where Z^{2} is generated by an order-reversing involution).

According to Section 5.2 (1), they can also be counted as 9 reducts where a trivial structure is involved, plus 2 · 2 · 5 other reducts: on each C_{i} = Q_{i} two possible types of non-oriented orderings O^{−} times the number of subgroups of Z^{2} × Z^{2}, the automorphism group of two fixed two-element sets.

(B) 11 reducts where Q_{1} is not definable, but E_{𝔔}:

(a) 7 (5) reducts with Aut(ℜ) ≅ Aut(C_{i}, O) ≀ Z^{2} for a generalised ordering O (where Z^{2} is generated by an involution ι exchanging the two E_{𝔔}-classes. In case O is oriented, there are two non-interdefinable possibilities: either ι changes or respects the orientation, i.e. ι maps O_{1} onto O_{2} or onto O_{2}^{−1}.)

(b) 2 (2) reducts with Aut(ℜ) ≅ Aut(C_{i}, O) ≀_{Z^{2}} (Z^{2} × Z^{2}) and 2 (2) with Aut(ℜ) ≅ Aut(C_{i}, O)≀_{Z^{2}} Z^{4} for an oriented ordering O (generalised wreath product as after Fact 5.9; the common Z^{2} is generated by an order-reversing involution fixing the classes; its complement in Z^{2} × Z^{2} exchanges the classes; and Z^{4} is generated by an automorphism exchanging the classes and reversing the order on one side).

Alternatively: 1 reduct with trivial induced structure, plus 2·(10−5) other reducts: two possible non-trivial O^{−} times the five of the ten subgroups of D_{4}^{8}, i.e. the automorphism group of two two-elements sets, exchanging the two sets, i.e. not counted under (A).

(C) 13 reducts where E_{𝔔} is not definable: Theorem 3.2 applies and provides 13 (5) generalised orderings with Remark 4.4. Clearly, no isomorphisms are possible between reducts listed under different items. □

Theorem 5.11 Let a ∈ ℚ be a constant. Then (ℚ, <, a) has 116 reducts up to interdefinability and 56 reducts up to isomorphism.

Proof: With the notations from the beginning of Section 5, the structure can be written as (ℚ, <, Q_{0}, Q_{1}, Q_{2}) with Q_{1} = {a}. There are four cases; the first three reduce to Theorem 5.10 (A) and (B), the fourth to Theorem 3.2 and Proposition 4.3:

• Reducts, where a is definable: they are in 1-1-correspondence with the reducts of (ℚ, <, Q_{1}, Q_{2}) of Theorem 5.10: 53 reducts (32 up to isomorphism).

• Reducts where Q_{0} is definable and a has the same type as the elements in Q_{2}. Then the induced structure on Q_{2} ∪ {a} can’t be a linear order or a betweenness relation. Theorem 5.10 (A) yields 15 (12) reducts in case (a) and 2 (2) in case (b). So we have 17 (14) reducts altogether. Analogously with Q_{0} and Q_{2} exchanged. We get again 17 reducts, but no new isomorphism classes.

• Reducts with a unique 1-type, but where the equivalence relation with classes Q_{0} and Q_{2}∪{a} is definable. The induced structure on each class is the cyclic order, the separation relation or nothing. Theorem 5.10 (B) gives us 4 (3) reducts in case (a) and 2 (2) in case (b), altogether 6 (5) reducts. Analogously with Q_{0} and Q_{2} exchanged. We get 6 reducts, but no new isomorphism classes.

• Reducts with a unique strong 1-type are by Theorem 3.2 reducts of a definable linear order. By Remark 4.4, these are 4 linear orders, 4 betweenness relations, 4 cyclic orderings, 4 separation relations, and the trivial structure: 17 reducts (5 up to isomorphism).

Summa summarum: 53 + 17 + 17 + 6 + 6 + 17 = 116 (32 + 14 + 5 + 5 = 56) □

6 Reducts of (ℚ, <) with dense predicates

In this section, we study the structure 𝔓 = (ℚ, <, P_{1}, …, P_{n}) where the P_{i} form a partition of ℚ into dense subsets (n > 1). We conjecture that the reducts are given by the following data, and hence that there are only finitely many possibilities (with Theorem 5.1 and Proposition 4.3):

• the equivalence relation E_{ℜ} with classes C_{1}, …, C_{k};

• a reduct ℜ′ of (ℚ, C_{1}, <′_{1}, …, C_{n}, <′_{n}) where <′_{i} is a linear order on C_{i} that is ∅-definable in 𝔓;

• an equivalence relation E_{ℜ}^{dep}, coarser than E_{𝔓} (as defined in Definition 6.13).

The reduct ℜ should then be generated by ℜ′ and the separation relation on each E_{ℜ}^{dep}-class, except on those formed of predicates P_{i} with trivial induced structure. Theorem 3.2 shows the conjecture in the case E_{ℜ} is trivial, and we will show in Theorem 6.14 the conjecture for the case n = 2, or more generally for E_{ℜ} = E_{𝔓}. The following is an example that is not covered by our methods:

Example 6.1 Let n = 4 and ℜ = (ℚ, <_{P_{1}∪P_{2}} <^{+} <_{P_{3}∪P_{4}}^{−1}, P_{1} ∪ P_{3}, P_{2} ∪ P_{4}). In this example, the E_{ℜ}-classes are P_{1} ∪ P_{3} and P_{2} ∪ P_{4}, the E_{ℜ}^{dep}-classes are P_{1} ∪ P_{2} and P_{3} ∪ P_{4}.

6.1 Induced structure

Let ℜ be a reduct of 𝔓.

Lemma 6.2 Let C be an E_{ℜ}-class. If the induced structure on C is trivial, then the induced structure on C over ¬C is trivial, and C does not induce any additional structure on ¬C.

Proof: Otherwise there are strict k-tuples x̄, x̄′ in C, an l-tuple ȳ in ¬C and a formula φ such that ⊧ φ(x̄, ȳ) and ⊧ ¬φ(x̄′, ȳ). Moving x̄ and x̄′ slightly without changing their type in the original structure 𝔓, we find pairwise disjoint strict k-tuples x̄_{1}, …, x̄_{m}, x̄′_{1}, …, x̄′_{m} for arbitrarily large m, such that ⊧ φ(x̄_{i}, ȳ) and ⊧ ¬φ(x̄′_{i}, ȳ). Since the induced structure on C is trivial, the formula ∃ȳ( ⋀_{i_{1}}^{m} φ(x̄_{i}, ȳ) ∧ ⋀_{i_{1}}^{m} ¬φ(x̄′_{i}, ȳ)) is realised by all strict tuples in C^{2km}. Now, chose x̄_{1} < x̄′_{1} < x̄_{2} < ⋯ < x̄′_{m}. Since x̄_{i} and x̄′_{i} are of different type over ȳ, some component of x̄_{i} and its corresponding component of x̄′_{i} are separated by a component of ȳ. This is not possible if m > l. The second part of the assertion is a consequence of the first. □

6.2 Independent predicates

Definition 6.3 In ℜ, ∅-definable subsets D_{1}, …, D_{l} of ℚ are called independent if whenever x̄_{i}, x̄′_{i} ∈ D_{i} have the same type in 𝔓, then (x̄_{1}, …, x̄_{l}) and (x̄′_{1}, …, x̄′_{l}) have the same type in ℜ.

It follows that, if ℚ is partitioned into ∅-definable independent D_{1}, …, D_{l}, then ℜ is a reduct of (ℚ, <_{D_{1}}, …, <_{D_{l}}, P_{1}, …, P_{n}). Furthermore, Lemma 6.2 shows that if the induced structure on some E_{ℜ}-class C is trivial, then C is independent from its complement ¬C.

6.2.1 Dependence gives the separation relation

Proposition 6.4 Let ℜ be a reduct of 𝔓, where P_{1} and P_{2} are strong types. Then P_{1} and P_{2} are dependent if and only if the separation relation is definable on ℚ.

Beginning of the proof: The ‘if’-direction is obvious. For the converse, we may assume n = 2 because ℜ ↾_{P_{1}∪P_{2}} is (trivially) a reduct of 𝔓 ↾_{P_{1}∪P_{2}}. Furthermore we will assume in the sequel that P_{1}, P_{2} are definable. We will see that the definition of sep is invariant under exchanging P_{1} and P_{2}. Therefore the result will also hold in the more general case. Thus we have the following situation: ℜ is a reduct of (ℚ, <, P_{1}, P_{2}), the two predicates are definable and dependent. It follows that sep_{P_{1}}, sep_{P_{2}} are definable, because the induced structure on each P_{i} is non-trivial. Also it follows from Lemma 6.8 below that there is more than one strong 1-type in P_{1} over P_{2}, and conversely. For b̄ = (b_{1}, …, b_{m}) ∈ P_{2}, we let Eb̄ be the equivalence relation defined on P_{1} “to have same strong type over b̄ ”. We may assume b_{1} < ⋯ < b_{m}, and we let b_{0} = −∞ and b_{m+1} = +∞. The Eb̄-classes are unions of intervals (b_{i}, b_{i+1}) ∩ P_{1}. We say that Eb̄ jumps at b_{i} if (b_{i−1}, b_{i}) ∩ P_{1} and (b_{i}, b_{i+1}) ∩ P_{1} are in different Eb̄-classes. Fact Eb̄ jumps at every b_{i} ∈ b̄ if b̄ is long enough. (This is intuitively clear. Corollary 6.10 will provide a proof in a more general situation.)

Lemma 6.5 Assume the betweenness relation is not definable on P_{1}, and let b̄ be long enough. Then (−∞, b_{1}) ∩ P_{1} and (b_{m}, +∞) ∩ P_{1} are in the same class.

Proof: Choose for every i = 0, …, m an x_{i} ∈ (b_{i}, b_{i+1}) ∩ P_{1}, and a y ∈ P_{1} with x_{m} < y. Then ¬Eb̄x_{i}x_{i+1}, but Eb̄x_{m}y. Assume x_{0} and y are not equivalent. As the betweenness relation is not definable on P_{1}, there is a y′ < x_{0} such that (x̄, y) and (x̄, y′) have the same type in ℜ. Thus there are b′_{1}, …, b′_{m} ∈ P_{2} such that consecutive elements in the sequence y′, x_{0}, …, x_{m} are not E_{b′_{1}...b′_{m}}-equivalent. But the m elements b′_{1}, …, b′_{m} can’t cause jumps at these m + 1 consecutive pairs in the sequence: contradiction. □

Now we are able to finish the proof of Proposition 6.4: First case: The order is definable on P_{2}. Then for a ∈ P_{1} and b_{1} ∈ P_{2}

a < b_{1} ⟺ ∃y ∈ P_{1}(a ≠ y ∧ ∀b_{2} … b_{m} ∈ P_{2} (b_{1} < b_{2} < ⋯ < b_{m} → Eb̄ay)).

Then the order is definable on P_{1} ∪ P_{2}. Also it follows that m = 1 and that E_{b}xy ⟺ b ∉ conv(x, y), and clearly the situation is symmetric in P_{1} and P_{2}: E_{a}xy for a ∈ P_{1} and x, y ∈ P_{2} also defines the negation of the betweenness relation. Hence the definition of the separation relation is invariant under exchanging P_{1} and P_{2}. Second case: The betweenness relation is definable on P_{2}. As <↾ _{P_{2}} is algebraic over ℜ, the finest definable finite equivalence relation in (ℜ, <↾_{P_{2}}, b) equals the finest definable finite equivalence relation in (ℜ, b). Hence b ∉ conv(x, y) is also definable in ℜ, and we get the global betweenness relation on P_{1} ∪ P_{2}. As the assumptions for the proposition are symmetric in P_{1} and P_{2}, we get the same result if the betweenness relation is definable on P_{1}.

Third case: The cyclic ordering is definable on P_{2} and the betweenness relation is not definable on P_{1}. Let x, y ∈ P_{1} and b_{1}, …, b_{m} ∈ P_{2} be pairwise distinct. Lemma 6.5 shows that the minimal m such that E_{b_{1}...b_{m}} is not trivial is at least 2. Moreover, if m = 2, then \overleftrightarrow{xb_{1}yb_{2}} ⟺ ¬E_{b_{1}b_{2}}xy, and if m > 2, then

\overrightarrow{b_{1}xb_{2}} ⟺ ∃y ∈ P_{1}(x ≠ y ∧ ∀b_{3} … b_{m} ∈ P_{2} (\overrightarrow{b_{1}b_{2}b_{3} … b_{m}} → Eb̄xy)).

Again, the global cyclic order on P_{1} ∪ P_{2} is definable from this. Hence we see that m = 2 and that E_{b_{1}b_{2}}xy defines the negation of the separation relation. In particular, the same holds for P_{1} and P_{2} exchanged. Fourth case: The separation relation is definable on P_{2}. As above, the finest definable finite equivalence relation in (ℜ, cyc ↾_{P_{2}}, b_{1}, b_{2}) equals the finest definable finite equivalence relation in (ℜ, b_{1}, b_{2}). Hence the separation relation between P_{1} and P_{2} is also definable in ℜ. □ of 6.4

Remark 6.6 It is easy to see directly the following:

(a) If the separation relation between P_{1} and P_{2} is definable, i.e. \overleftrightarrow{x_{1}y_{1}x_{2}y_{2}} for x_{i} ∈ P_{1} and y_{i} ∈ P_{2}, then the separation relation on P_{1} ∪ P_{2} is definable.

(b) If the separation relation on P_{1} ∪ P_{2} is definable and a generalised ordering O defined on P_{1}, then O extends definably on P_{1} ∪ P_{2}.

6.2.2 Dependence is trivial as a matroid

Throughout Section 6.2.2, we will assume that all P_{i} are definable in ℜ.

Proposition 6.7 If P_{1}, …, P_{k} are pairwise independent, then they are independent.

Beginning of the proof: We prove Proposition 6.7 by induction on k. We may therefore assume that each selection of k − 1 out of P_{1}, …, P_{k} is independent. The proof will include two lemmas and will be completed at the end of Section 6.2.2. By definition, independence of P_{i_{1}}, …, P_{i_{l}} implies that there is only one strong 1-type in P_{i_{1}} over P_{i_{2}} ∪ ⋯ ∪ P_{i_{l}}.

Lemma 6.8 If there is only one strong 1-type in P_{1} over P_{2} ∪ ⋯ ∪ P_{k}, then P_{1}, P_{2}, …, P_{k} are independent.

Proof: By assumption and Theorem 3.2, any c̄ ∈ C := P_{2}∪⋯∪P_{k} induces a generalised ordering on P_{1} (determined up to interdefinability). A longer tuple induces a compatible generalised ordering, hence there is some c̄ ∈ C with maximal induced structure on P_{1} given by a relation Oc̄. If d̄ has the same type as c̄ in the structure 𝔖 := (ℚ \ P_{1}, P_{2}, …, P_{k}, <_{P_{2}}, …, <_{P_{k}}), then, because P_{2}, …, P_{k} are independent, Oc̄ and Od̄ can only differ by orientation. The equivalence relation Ex̄ȳ: ⟺ Ox̄ = Oȳ on P_{2} ∪ ⋯ ∪ P_{k} is definable in ℜ ↾_{P_{2}∪···∪P_{k}}, hence in 𝔖 since the former is a reduct of the latter. As in Lemma 4.1 and Corollary 4.2, one sees that 𝔖 eliminates imaginaries, acl(∅) = ∅, thus there is no non-trivial finite ∅-definable equivalence relation on a complete type in 𝔖. Therefore Oc̄ = Od̄, and Oc̄ is ∅-definable in ℜ. Now, if x̄, ȳ ∈ P_{1} have the same ℜ-type, they have the same Oc̄-type, and therefore the same ℜ-type over every tuple in C. This shows independence. □

Now we assume P_{1}, P_{2}, …, P_{k} to be dependent. As a consequence of Lemma 6.2, the induced structure on each P_{i} is non-trivial. By Lemma 6.8, there is more than one strong 1-type in P_{1} over its complement. We will show that this leads to a contradiction. We consider finite subsets B of P_{2} ∪ ⋯ ∪ P_{k} such that there is more than one strong type in P_{1} over B. Due to the induction hypothesis, B intersects each P_{2}, …, P_{k}. Write E_{B} for the equivalence relation on P_{1} “to have same strong type over B”.

Lemma 6.9 If B is minimal with non-trivial E_{B}, then E_{B} jumps at each parameter from B.

Proof: Assume E_{B} does not jump at b ∈ B and let b ∈ P_{2}. Set B′ = B \{b} and B′′ = B′ ∩P_{2}. Consider the equivalence relation F (x, y) on P_{2} defined by E_{xB′} = E_{yB′}. Since P_{2}, …, P_{k} are independent, F is B′′–definable. Since E_{B} does not jump at b ∈ B, a whole neighbourhood of b in P_{2} belongs to the same F -class. We conclude from this that the F -class A of b is B′′–definable. This can easily be checked through the four cases of generalised orderings O induced on P_{2}. There are only two cases where one has to recur to the special nature of E. The first case is, when O is the betweenness relation and B′′ = {b′′} is a singleton: Assume b′′ < b, then all y ∈ P_{2} with b′′ < y are in A. With the notation B′′′ = B∩(P_{3}∪⋯∪P_{k}) this means that E_{b′′yB′′′} = E_{b′′bB′′′}. Since P_{2}, …, P_{k} are independent this implies E_{x′′yB′′′} = E_{x′′xB′′′} for all three distinct x′′, x, y ∈ P_{2} such that x′′ is not between x and y. This implies that E_{xyB′′′} = E_{x′y′B′′′} for all distinct x, y and x′, y′ in P_{2}. So we have that A = P_{2} \ {b′′}. The second case, where O is separation and |B′′| = 2, is treated similarly. Therefore, if q is the O-type of b over B′′, E_{B} is also defined by the formula

∃x ∈ P_{2} (tp^{O}(x/B′′) = q ∧ E_{xB′}) ,

contradicting the minimality of B. □

Corollary 6.10 If E_{B} is non-trivial, then it jumps at each of its parameters.

Proof: Let B_{0} ⊂ P_{2}∪⋯∪P_{k} be minimal with non–trivial E_{B_{0}}. The independence of P_{2}, …, P_{k} implies that a set B′_{0} is minimal iff |B′_{0} ∩ P_{i}| = |B_{0} ∩ P_{i}| for i = 2, …, k. So, if b is any element of B, we find a minimal subset B′_{0} of B such that b ∈ B′_{0}. E_{B} jumps at b since E_{B′_{0}} does. □

To complete the proof of Proposition 6.7, choose a non-trivial E_{B} such that B intersects P_{2} and P_{3} each in at least 3 elements. Write B ∩ P_{2} = {b_{0}, …, b_{m}} for b_{0} < ⋯ < b_{m}, B ∩ P_{3} = {c_{0}, …, c_{l}} for c_{0} < ⋯ < c_{l} and set B′ = B ∩ (P_{4} ∪ ⋯ ∪ P_{k}). Since sep_{P_{2}} is definable, we can define the interval (b_{0}, b_{m}) ∩ P_{2} over b̄, similarly (c_{0}, c_{l}) ∩ P_{3} is definable over c̄. E_{xyB} jumps at x and y for all x, y. Thus

∀a ≠ a′ ∈ P_{1} ∃x ∈ (b_{0}, b_{m}) ∩ P_{2} ∃y ∉ P_{3} \ (c_{0}, c_{l}) ¬E_{xyB}(a, a′)

iff (c_{0}, c_{l}) ⊂ (b_{0}, b_{m}). This shows that there are at least two possible types of b̄c̄ over B′, which contradicts the independence of P_{2}, …, P_{k}. □ of 6.7

6.2.3 Dependence defines an equivalence relation

Lemma 6.11 If sep is definable on P_{1} ∪ P_{2} and on P_{2} ∪ P_{3}, then also on P_{1} ∪ P_{2} ∪ P_{3}.

Proof: It is sufficient to show that sep is definable on P_{1} ∪ P_{3}. If x_{1}, x_{2} ∈ P_{1} and y_{1}, y_{2} ∈ P_{3},

\overleftrightarrow{x_{1}y_{1}x_{2}y_{2}} ⟺ ∃x_{i}^{−}x_{i}^{+} ∈ P_{2} ( \overleftrightarrow{x_{1}^{−}x_{1}x_{1}^{+}x_{2}^{−}x_{2}x_{2}^{+}} ∧ \overleftrightarrow{x_{1}^{−}x_{1}^{+}yx_{2}^{−}x_{2}^{+}y_{2}} )

□

The lemma shows that dependence is an equivalence relation on the predicates. Next we show that the equivalence classes are independent.

Proposition 6.12 Let D_{i} be the union of all P_{j} which are dependent from P_{i}. If P_{1}, …, P_{k} are independent, then D_{1}, …, D_{k} also.

Proof: Consider two long tuples x̄, ȳ with entries from D_{1} ∪ ⋯ ∪ D_{k} and same order type in each D_{i}. We construct new tuples of doubled length by replacing each element v of D_{i} in x̄, ȳ with two elements v^{−}, v^{+} ∈ P_{i} such that v ∈ (v^{−}, v^{+}) and such that the intervals (v^{−}, v^{+}) are pairwise disjoint. The new tuples have the same type by independence of the P_{i}, and an automorphism moving one onto the other moves x_{i} on some element y′_{i} ∈ (y_{i}^{−}, y_{i}^{+}) because the separation relation is definable on D_{i} (Proposition 6.4) and the tuples are long. But then there is an automorphism of 𝔓 fixing all y_{i}^{−}, y_{i}^{+} and moving y′_{i} on y_{i}. □

Definition 6.13 Let E_{ℜ}^{dep} be the equivalence relation on ℚ induced by dependence: x ∈ P_{i} and y ∈ P_{j} are equivalent if and only if P_{i} and P_{j} are dependent in ℜ.

The picture is now as follows: Let ℜ be a reduct with E_{ℜ} = E_{𝔓}, and D an E_{ℜ}^{dep}-class. Then either D consists of a single predicate with trivial induced structure, or D is a union of possibly several predicates which are dense in each other in ℜ, and the induced structure on D is one of the four non-trivial reducts of (D, <_{D}). The classes are independent, but the induced generalised orderings on different classes are possibly linked.

6.3 The proof of the conjecture in case E_{ℜ} = E_{𝔓}

Let ℜ be a reduct of 𝔓 with E_{ℜ} = E_{𝔓}, i.e. all P_{i} are strong types. Let D_{1}, …, D_{l} be the classes of E_{ℜ}^{dep}. Define ℜ′ := ℜ ∩ (ℚ, P_{1}, <_{P_{1}}, …, P_{n}, <_{P_{n}}), and ℜ^{<} := ℜ ∩ (ℚ, D_{1}, <_{D_{1}}, …, D_{l}, <_{D_{l}}). We will prove:

Theorem 6.14 ℜ is of the form ℜ′ ∪ ℜ^{<} (with ∪ in the lattice of reducts).

Proof: First we need the following remark: If P_{1}, P_{2} are in the same E_{ℜ}^{dep}-class D_{i}, then the equivalence relations E_{P_{1}}^{cyc} and E_{P_{2}}^{cyc} are interdefinable. This is clear as two triples in P_{1} are equally oriented if and only if intercalated triples of P_{2} are equally oriented. Therefore the orientations P_{1}/E_{P_{1}}^{cyc} and P_{2}/E_{P_{2}}^{cyc} are interdefinable, and interdefinable with D_{i}/E_{D_{i}}^{cyc}. We let P^{or} ⊆ acl^{eq}(∅) consist of the predicates P_{1}, …, P_{n} and the orientations D_{i}/E_{D_{i}}^{cyc} for all D_{i} with non-trivial induced structure. Recall that ℜ(A) denotes the expansion by constants for the elements of A. We have to show that each automorphism α of ℜ′ ∪ ℜ^{<} is an automorphism of ℜ (the converse is trivially true). It is not hard to see that Aut(ℜ)↾_{P_{i}→P_{j},P^{or}} is dense in Aut(ℜ′)↾_{P_{i}→P_{j},P^{or}}, i.e. an automorphism of ℜ′ coincide on finite tuples of P_{i} with automorphisms of ℜ permuting P^{or} in the same way. This is true because Aut(ℜ′) equals the completion of the group generated by Aut(ℜ) and Aut(ℚ, P_{1}, <_{P_{1}}, …, P_{n}, <_{P_{n}}). As a special case we have that ℜ and ℜ′ induce the same structure on P^{or}. So we may assume that α leaves every P_{i} and the orientations on it invariant. We will now show that α coincides on every finite part of each D_{i} with some β_{i} ∈ Aut_{P^{or}}(ℜ) that is the identity outside D_{i}. Then α = β_{1} ∘ … β_{l} ∈ Aut(ℜ), which will prove the theorem. If the induced structure on D_{i} is trivial, this follows immediately from Lemma 6.2. If the induced structure on D_{i} is non-trivial, we consider long tuples x̄ whose elements come alternately from P_{1}, …, P_{n}, at least four out of each P_{j}. Say P_{1} ⊆ D_{i}. Then there is β_{i} ∈ Aut_{P^{or}}(ℜ) coinciding with α on x̄ ∩ P_{1}. Since α respects the separation relation on D_{i} and x̄ ∩ P_{1} is long enough, we can find β′_{i} ∈ Aut(𝔓) fixing α(x̄) ∩ P_{1} and moving the remaining D_{i}-part of β_{i}(x̄) on α(x̄) ∩ D_{i}. Thus α and β′_{i} ∘ β_{i} coincide on x̄ ∩ D_{i}. It is now sufficient to show that ℜ(P^{or}, ℚ\D_{i}) does not induce more structure on D_{i} as ℜ(P^{or}) does. The proof works as for the second claim of Lemma 5.4: Independence of the D_{i} implies that there is only one strong 1-type in P_{1} over ℚ \ D_{i} (as in the remark preceding Lemma 6.8). Therefore ℚ \ D_{i} induces a generalised ordering on P_{1}. Again because of the independence, tuples in ℚ \ D_{i} of same type induce the same structure. Since there are only finitely many types, the induced structure is of finite index. But the orientations are already fixed, hence there is no new induced structure on P_{1}. Now the induced structure on P_{1} together with the separation relation on D_{i} completely determines the induced structure on D_{i} (Remark 6.6). □

In particular, this settles the conjecture for n = 2, as either E_{ℜ} = E_{𝔓} or E_{ℜ} is trivial. In fact, the proof of the theorem shows that ℜ is of the form ℜ′′ ∪ ℜ^{<} where ℜ′′ := ℜ ∩ (ℚ, P_{1}, …, P_{n}, P_{1}/E_{P_{1}}^{cyc}, …, P_{n}/E_{P_{n}}^{cyc}).

6.3.1 Ideas for the remaining cases

One possibility to prove the conjecture completely would be to develop a theory of dependence for E_{ℜ}-classes. Another possibility would be to show the following: If ℜ is a reduct where P_{1} and P_{2} live in the same strong type, then ℜ is a reduct of (ℚ, <′, P_{1} ∪P_{2}, P_{3}, …, P_{n}) for some linear order <′ on ℚ that is ∅-definable in 𝔓. Example 6.1 might help to illustrate the difficulties.

7 The general case

We sketch a proof of a lower bound for the number of reducts in the general case.

Remark Let 𝔓 = (ℚ, <, P_{1}, …, P_{n}) be an expansion of (ℚ, <) by a partition of ℚ, eliminating quantifiers, and let 𝔓′ = (ℚ, <, P′_{1}, …, P′_{n}) be an expansion by a partition of dense predicates. Then 𝔓 has at most as many reducts as 𝔓′.

Sketch of a proof: This is clear if all the P_{i} are infinite, since then 𝔓 is isomorphic to some reduct (ℚ, <_{B,χ}, P′_{1}, …, P′_{n}) of 𝔓′. The idea now is to “blow up” singletons. Let ℜ be a reduct of 𝔓. With each E_{ℜ}-class C = P_{i_{1}} ∪⋯∪P_{i_{l}} we associate C′ := P′_{i_{1}} ∪⋯∪P′_{i_{l}}, and call 𝔓′/E_{ℜ} the set of these C′. Fix order preserving bijections α_{i} : P_{i} → P′_{i} for the infinite predicates P_{i}, and choose for each C′ a ∅-definable generalised ordering O′ with the following properties: (1) O′ is trivial if C is finite; (2) O′ is of the same type as the generalised ordering O induced by ℜ on C; (3) O and O′ are compatible via the α_{i}, i.e. if β ∈ Aut_{{P_{i}}}(ℜ), then α ∘ β ↾_{P_{i}} extends to an automorphism of O′. Then we define a reduct ℜ′ of 𝔓′ by letting Aut(ℜ′) the closed subgroup generated by all permutations of ℚ that act on 𝔓′/E_{ℜ} like an automorphism of ℜ and respect the generalised orderings O′ on the C′. This defines an injection of the reducts of 𝔓 to the reducts of 𝔓′. □

References

[AZ] Gisela Ahlbrandt, Martin Ziegler, Invariant subgroups of ^{V} V, J. Algebra 151 no. 1 (1992), pp 26–38.

[B] James Bennett, The reducts of some infinite homogeneous graphs and tournaments, PhD thesis, Rutgers, New Brunswick 1996.

[C1] Peter Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 148 (1976), pp. 127–139.

[C2] Peter Cameron Oligomorphic permutation groups, LMSLN 152, Cambridge University Press, Cambridge 1990.

[F] Claude Frasnay, quelques problèmes conbinatoires concernant les ordres totaux et les relations monomorphes, Annales de l’INstitut Fourier (Grenoble) 15 (1965), pp. 415– 524.

[Hi] Graham Higman, Homogeneous relations. Quart. J. Math. 28 no. 109 (1977), pp. 31–39.

[HLS] Wilfrid Hodges, Alistair Lachlan, Saharon Shelah, Possible orderings of an indiscernible sequence, Bull. London Math. Soc. 9 (1977), pp. 212–125.

[Ho] Wilfrid Hodges A shorter model theory, Cambridge University Press, Cambridge 1997.

[P1] Bruno Poizat, Une théorie de Galois imaginaire. JSL 48 no. 4 (1983), pp. 1151–1170.

[P2] Bruno Poizat A course in model theory, Springer, New York 2000.

[T1] Simon Thomas, Reducts of the random graph JSL 56 no. 1 (1991), pp. 176–181.

[T2] Simon Thomas, Reducts of the random hypergraphs APAL 80 no. 2 (1996), pp. 165–193.