Galois groups of first order theories.

E. Casanovas University of Barcelona

D. Lascar CNRS, Universite Paris VII

A. Pillay University of Illinois at Urbana-Champaign

M. Ziegler University of Freiburg

18 October 2000^{∗}

Abstract

We study the groups Gal_{L}(T) and Gal_{KP} (T), and the associated equivalence relations E_{L} and E_{KP}, attached to a first order theory T. An example is given where E_{L} ≠ E_{KP} (a non G-compact theory). It is proved that E_{KP} is the composition of E_{L} and the closure of E_{L}. Other examples are given showing this is best possible.

1 Introduction and preliminaries.

Let T be a complete first order theory, possibly many-sorted. We will be studying a certain group, Gal_{L}(T), the Lascar group of T. If T is the theory of algebraically closed fields of characteristic 0, this will be the absolute Galois group of Q (a profinite group). For “G-compact” theories, Gal_{L}(T)

∗revised 8-8-2001

1The first author was partially supported by a grant from the Spanish Ministry of Education. The third author was partially supported by NSF grants DMS-9696268 and DMS-0070179. Some of the work reported here was carried out during visits of the second author to Urbana and of the third author to Paris which were supported by a CNRS-UIUC collaboration fund.

has naturally the structure of a compact (Hausdorff) topological group. In general Gal_{L}(T) will be more of a “descriptive set-theoretic” invariant of T.

Let us begin with an informal description of the relevant groups and equivalence relations. Let M̄ be a very saturated model of T. “Small” or “bounded” means of strictly smaller cardinality than that of M̄. An equivalence relation will be called bounded (finite) if it has a bounded (finite) number of classes. Type-definable over ∅ (or ∅-type-definable) means defined by a possibly infinite set (conjunction) of L-formulas. Let S be any sort. E_{L}^{S} is the finest bounded invariant (under Aut(M̄)) equivalence relation on S. E_{KP}^{S} is the finest bounded type definable over ∅ equivalence relation on S. E_{Sh}^{S} is the intersection of all finite ∅-definable equivalence relations on S. E_{L}^{S} refines E_{KP}^{S} which in turn refines E_{Sh}^{S}. These equivalence relations have explicit syntactic descriptions which do not depend on the choice of M̄. For each of these equivalence relations E, S/E denotes the quotient space, on which clearly Aut(M̄) acts. We obtain the corresponding “Galois groups”, Gal_{L}^{S}, Gal_{KP}^{S} and Gal_{Sh}^{S}. All this can be done with some ∅-type-definable set X of possibly infinite tuples in place of the sort S. Roughly speaking, taking the projective limit of these groups as X varies, yields groups Gal_{L}(T), Gal_{KP} (T) and Gal_{Sh}^{T} which are invariants of the bi-interpretability type of T. Precise statements and definitions will be given below, but for now let us say that these Galois groups come equipped with “additional structure”: Gal_{Sh}(T) is a profinite group and Gal_{KP} (T) is a compact group (and in fact Gal_{Sh}(T) is the maximal profinite quotient of Gal_{KP} (T)). Gal_{L}(T) can be described as a “quasicompact” group (that is compact but not necessarily Hausdorff). However possibly more interesting is that Gal_{L}(T) arises naturally as the quotient of a certain “space of types” by a certain equivalence relation which is a countable union of closed sets. As such Gal_{L}(T) is a kind of “descriptive set-theoretic” invariant of T. In many cases (such as when T is stable) all these equivalence relations and Galois groups coincide.

Gal_{L}(T), the Lascar group, was introduced by the second author in [6]. He also introduced the notion of a G-compact theory and remarked that all known theories were G-compact. Essentially G-compactness of T means that Gal_{L}(T) = Gal_{KP} (T).

Additional interest was generated by the work on simple theories [5], where Lascar strong types (E_{L}-classes) took the place of strong types. Kim [4] subsequently showed that simple theories are G-compact.

The second author, in [6], defined a topology on Gal_{L}(T) in the case where T is G-compact, making Gal_{L}(T) into a compact (Hausdorff) topological group. In [2], Hrushovski gave another account of the topology, working directly with Gal_{KP} (whether T is G-compact or not). In fact in that paper the E_{KP} notation was introduced. Similar things were done in [7]. The main point was that the spaces S/E_{KP} or even X/E_{KP} are naturally equipped with compact Hausdorff topologies (the closed sets being precisely the typedefinable sets). There has been considerable attention paid to the issue of proving that E_{KP} = E_{Sh} in certain situations. For example in [1] this is proved for supersimple theories. The simple case is still open although Hrushovski [2] found a counterexample in the more general (non first order) context of Robinson theories.

The current paper is concerned with the issue of when and how E_{L} differs from E_{KP}, in particular the existence of non G-compact theories. The starting point for our work was the discovery by the fourth author of such a theory (non G-compact). This example together with two other related examples, appears in section 4. In section 2 we prove that E_{KP} is the composition of E_{L} and Ē_{L}. (Here, working on a sort S say, Ē_{L} denotes the closure of E_{L} in the Stone space of complete types in S × S.) This is done by characterizing closure in the quasicompact group Gal_{L}(T). In section 3, we look at products and co-products of structures and study the resulting Galois groups. Informed by this analysis, we present the examples in section 4. The “basic example” (a product of circles with specified structures) has E_{KP} different from E_{L}. A modification gives an example where E_{KP} is different from Ē_{L} (showing that the results in section 2 are best possible). In a third example we show that on E_{L}, closure (in the Stone space on S ×S) need not commute with restriction to a complete type p(x). We also ask some questions, which possibly need new kinds of examples to settle.

In the rest of this section we repeat some definitions, fix notation, summarise earlier relevant results, and give some additional information. As above S denotes a sort in M̄.

Definition 1.1 (i) E_{L}^{S} is the finest bounded invariant equivalence relation on S. (ii) E_{KP}^{S} is the finest bounded ∅-type-definable equivalence relation on S. (iii) E_{Sh}^{S} is the intersection of all finite ∅-definable equivalence relations on S. (iv) Let X be a ∅-type-definable set of possibly infinite tuples (for example X could be a product of infinitely many sorts). E_{L}^{X}, E_{KP}^{X}, E_{Sh}^{X} are defined as above. For example E_{KP}^{X} is the finest bounded type-definable over ∅ equivalence relation on X.

Remark 1.2 (i) E_{L}^{S} refines E_{KP}^{S} which in turn refines E_{Sh}^{S}. In stable theories they are all equal. We will not say much about E_{Sh}. (ii) Define a subset of X/E_{KP}^{X} to be closed if its preimage in X is typedefinable (maybe with parameters). Then X/E_{KP}^{X} is a compact Hausdorff topological space. Similarly for X/E_{Sh}^{X} except that this space is now profinite.

Definition 1.3 (i) Autf_{L}(M̄), the group of Lascar strong automorphisms, is the subgroup of Aut(M̄) consisting of f which fix each class of each E_{L}^{X} (X ∅-type-definable). Similarly for Autf_{KP} (M̄) and Autf_{Sh}(M̄). (iii) Gal_{L}(T), the Lascar group of T is the quotient of Aut(M̄) by the (normal) subgroup Autf_{L}(M̄). By definition it acts faithfully on {a/E_{L}^{X} : X∅- type-definable, a ∈ X}. Similarly for Gal_{KP} (T) and Gal_{Sh}(T). The latter two groups have the structure of compact Hausdorff topological groups (via the Tychonoff topology for example). These (topological) groups are invariants of (the bi-interpretability type of) T (and so do not depend on the choice of M̄).

Fact 1.4 (i) Let X ⊆ Y be ∅-type-definable (or even invariant) sets of possibly infinite tuples. Then E_{L}^{Y} |X coincides with E_{L}^{X} and it is precisely the relation (on X) of being in the same orbit under Autf_{L}(M̄). (ii) Similarly for E_{KP} and Autf_{KP} (M̄). In particular, given a sort S and a complete type p(x) of that sort, E_{KP}^{S} |p = E_{KP}^{p}.

Proof. (i) is immediate. (ii) is contained in Lemma 4.18 of [7]. But we will give another proof. Work for simplicity in a sort S. It suffices to show that the equivalence relation on S of being in the same orbit under Autf_{KP} (M̄) is type-definable over ∅ (and thus has to be E_{KP}^{S}). a and b are in the same orbit under Autf_{KP} (M̄) iff tp(a/e) = tp(b/e) whenever e is a bounded hyperimaginary. The latter is seen easily to be type-definable.

Corollary 1.5 Let S be a sort and X a ∅-type-definable subset of S. Let E be any bounded ∅-type-definable equivalence relation on X. Then there is a bounded ∅-type-definable equivalence relation E′ on S such that E is the restriction of E′ to X.

Proof By (ii) of the previous lemma, E_{KP}^{S} |X refines E. The disjunction E_{KP}^{S} ∨ E is type-definable and as required.

Remark 1.6 By Fact 1.4, we can speak unambiguously of E_{L} and E_{KP}. We will say that (possibly infinite) tuples a, b from M̄ have the same Lascar strong type if E_{L}(a, b) and the same KP -strong type if E_{KP} (a, b).

Fact 1.7 Autf_{KP} (M̄) is closed in Aut(M̄) (where Aut(M̄) is equipped with the pointwise convergence topology: the basic open sets are the stabilizers of finite tuples).

Proof. This is in 4.18 of [7].

Fact 1.8 The following are equivalent:

(i) Autf_{L}(M̄) = Autf_{KP} (M̄) (and so canonically Gal_{L}(T) = Gal_{KP} (T)). (ii) E_{L} coincides with E_{KP} (even on infinite tuples) (iii) E_{L} coincides with E_{KP} on finite tuples and Autf_{L}(M̄) is closed in Aut(M̄).

Proof. See [4] and 4.20 of [7].

Fact 1.9 (i) E_{L}(a, b) if and only if there is some n < ω and there are models M_{1}, .., M_{n} and a_{0}, .., a_{n} such that a_{0} = a, a_{n} = b and tp(a_{i}/M_{i+1}) = tp(a_{i+1}/M_{i+1}) for each i = 0, .., n − 1. (ii) Autf_{L}(M̄) is the subgroup of Aut(M̄) generated by the subgroups F ix(m) where m ranges over enumerations of small submodels of M̄.

Proof. (i) is well-known, see for example [5]. (ii) follows from (i) (and is actually Lascar’s original definition of Autf_{L}(M̄)).

Suppose that E_{L}(a, b). We define d(a, b) to be the smallest n as in Fact 1.9(i).

We now discuss thick formulas, although these will play a minor role in our proofs.

Definition 1.10 Fix a sort S. An L-formula θ(x, y), x, y of sort S, is said to be thick, if for some n, for any a_{1}, ..., a_{n} ∈ S, θ(a_{i}, a_{j}) for some i ≠ j. Similarly working inside a type-definable set of possibly infinite tuples.

Note that thickness is a symmetric notion: if θ(x, y) is thick, then so is θ(y, x). In particular (*) any thick formula is implied by a symmetric thick formula.

Fact 1.11 Suppose a ≠ b. The following are equivalent:

(i) θ(a, b) for all thick θ. (ii) a and b belong to some infinite indiscernible sequence. (iii) θ(a, b) holds for all symmetric thick formulas.

Proof. (i) implies (ii) is by compactness. (ii) implies (iii): if (a_{i} : i < ω) is infinite indiscernible and ⊧ ¬θ(a_{0}, a_{1}), then ⊧ ¬θ(a_{i}, a_{j}) for all i < j < ω, so θ is not thick. (iii) implies (i) holds by (*) above.

Let Θ be the set of thick formulas.

Fact 1.12 (i) Θ(a, b) implies that tp(a/M) = tp(b/M) for some model M. (ii) If tp(a/M) = tp(b/M) then there is c such that Θ(a, c) and Θ(c, b).

Proof. (i) is well-known. (ii) This actually lies behind Fact 1.9. The usual proof is by choosing a coheir of tp(a/M) and constructing a sequence I such that both aI and bI are (infinite) indiscernible. Alternatively one could argue directly with thick formulas: As M is a model, for each thick symmetric θ(x, y) we can find a_{1}, .., a_{n} ∈ M (suitable n) such that for all a′ there is i ≤ n such that θ(a′, a_{n}). As tp(a/M) = tp(b/M) we have θ(a, a_{i}) ∧ θ(b, a_{i}) for some i. By compactness, we find c as required.

Note that if (a, b) begins an infinite indiscernible sequence then f(a) ≠ f(b) for any ∅-definable finite-to-one function (in M̄^{eq}). So we easily get examples of a ≠ b with tp(a/M) = tp(b/M) for some model, but where a, b does not begin an infinite indiscernible sequence.

Fact 1.13 E_{L}(a, b) iff there is n < ω and there are a_{0}, a_{1}, .., a_{n} with a_{0} = a, a_{n} = b and Θ(a_{i}, a_{i+1}) for all i < n.

Proof. By 1.9 and 1.12.

Finally we mention a certain topology on Gal_{L}(T) which was given in [7]. Let μ : Aut(M̄) → Gal_{L}(T) be the canonical surjective homomorphism. Fix a small elementary substructure M_{0} of M̄, enumerated by m_{0}. In Definition 4.9 of [7], a subset C of Gal_{L}(T) was defined to be closed if whenever g_{i} ∈ μ^{−1}(C) for i ∈ I, g′ is some ultraproduct of the g_{i}, and g ∈ Aut(M̄) is such that tp(g(m_{0})/m_{0}) = tp(g′(m_{0})/m_{0}) then g ∈ μ^{−1}(C). This defines a “topology” on Gal_{L}(T), independent of the choice of M_{0}. When T is G-compact (so Gal_{L} = Gal_{KP}) this agrees with the topology on Gal_{KP} referred to earlier.

2 Gal_{L}(T)

We try to get a better understanding of the object Gal_{L}(T) and see how explicitly E_{KP} can be obtained from E_{L}. By studying closure in Gal_{L}(T) we will see that E_{KP} is obtained by first taking the closure of E_{L} (in the Stone space sense) and then closing under E_{L}.

Let us fix a small submodel M_{0} of M̄, enumerated by m_{0}. If T happens to be countable, we may assume M_{0} is too. Let S_{m_{0}}(m_{0}) be the space of extensions of tp(m_{0}/∅) to complete types over m_{0}, namely {tp(g(m_{0})/m_{0}) : g ∈ Aut(M̄)} equipped with the usual Stone space topology. Note that if M_{0} is countable, S_{m_{0}}(m_{0}) is a Polish space. Let μ : Aut(M̄) → Gal_{L}(T) be the canonical homomorphism. Let μ_{1} : Aut(M̄) → S_{m_{0}}(m_{0}) be the surjective map taking g ∈ Aut(M̄) to tp(g(m_{0})/m_{0}). We begin by making explicit some observations from [7].

Fact 2.1 μ factors through μ_{1}. That is, for g ∈ Aut(M̄), μ(g) depends only on tp(g(m_{0})/m_{0}).

Proof. If tp(g(m_{0})/m_{0}) = tp(h(m_{0})/m_{0}), let γ ∈ F ix(m_{0}) be such that γ(g(m_{0})) = h(m_{0}). Then, by Fact 1.9 (ii), both γ and h^{−1}.γ.g are in Autf_{L}(M̄). As Autf_{L}(M̄) is normal in Aut(M̄), γ.g = g.γ′ for some γ′ ∈ Autf_{L}(M̄). Thus h^{−1}.g.γ′ ∈ Autf_{L}(M̄), whereby h^{−1}.g ∈ Autf_{L}(M̄) = Ker(μ).

So we obtain a canonical surjective map ν : S_{m_{0}}(m_{0}) → Gal_{L}(T) such that ν.μ_{1} = μ.

Remark 2.2 Let p, q ∈ S_{m_{0}}(m_{0}). Then

(i) ν(p) = ν(q) if and only if for any (some) m realizing p and any (some) n realizing q, E_{L}(m, n) (equivalently m and n are in the same Autf_{L}(M̄)- orbit). (ii) The equivalence relation ν(p) = ν(q) is (by 1.13 and (i)) a countable union of closed subsets of S_{m_{0}}(m_{0}) × S_{m_{0}}(m_{0}). In particular if T (and M_{0}) are countable, this is a Borel equivalence relation. (iii) The set of Lascar strong types extending tp(m_{0}/∅) is (naturally) a principal homogeneous space for Gal_{L}(T), so can be identified with Gal_{L}(T) after fixing a point (such as the class of m_{0}). (iv) (T countable.) The set of Lascar strong types on any sort S can be considered as the quotient of a Boolean space by a Borel equivalence relation: Let m_{0} be a countable model, and let X be the space of complete types over m_{0} in sort S. Define E_{L}(p, q) if for some (any) realizations a of p and b of q, E_{L}(a, b).

Fact 2.3 (i) The topology on Gal_{L}(T) referred to in the last paragraph of section 1 is precisely the quotient topology under the map ν. That is C ⊆ Gal_{L}(T) is closed if and only if ν^{−1}(C) is closed in the space S_{m_{0}}(m_{0}). (ii) Gal_{L}(T) is a topological (not necessarily Hausdorff) group. (iii) Autf_{KP} (M̄) is precisely μ^{−1}(\overline{\{id\}}) where id is the identity element of Gal_{L}(T).

Proof. (i) Lemma 4.10 of [7] says that C is closed in Gal_{L}(T) just if {g(m_{0}) : g ∈ μ^{−1}(C)} is type-definable over m_{0}, namely if {tp(g(m_{0})/m_{0}) : g ∈ μ^{−1}(C)} (which is precisely ν^{−1}(C)) is closed in S_{m_{0}}(m_{0}). (ii) Let C ⊂ Gal_{L}(T) be closed. We have to show that

(a) X = {(g, h) ∈ Gal_{L}(T) × Gal_{L}(T) : g.h ∈ C} is closed and

(b) Y = {g ∈ Gal_{L}(T) : g^{−1} ∈ C} is closed. We will just deal with (a). Let Φ(x, m_{0}) define the closed set ν^{−1}(C). Let p, q ∈ S_{m_{0}}(m_{0}), and let m, n be any realizations of p, q respectively. We claim that (ν(p), ν(q)) ∈ X if and only if there is x such that Φ(x, m_{0}) and tp(x, n/∅) = tp(m, m_{0}/∅). The verification is left to the reader: among the points is that Autf_{L}(M̄) is a normal subgroup of Aut(M̄). (iii) Let H be the closure of the identity in Gal_{L}(T), which is, by (ii) a (normal) subgroup. Let H_{1} = μ(Autf_{KP} (M̄)). So ν^{−1}(H_{1}) is closed in S_{m_{0}}(m_{0}), being defined by E_{KP} (x, m_{0}). Thus H ⊆ H_{1}. Let Φ(x, m_{0}) define ν^{−1}(H). So Φ(x, y) → E_{KP} (x, y), and E_{L}(x, y) → Φ(x, y) (on realizations of tp(m_{0})). As H is a subgroup of Gal_{L}(T) we see that Φ(x, y) is an equivalence relation, so has to be E_{KP}. Thus H = H_{1}.

Proposition 2.4 Let C ⊆ Gal_{L}(T). Suppose that q ∈ \overline{ν^{−1}(C)} and ν(p) = ν(q). Then for any realization n of p there is n′ such that (i) (n, n′) begins an indiscernible sequence (namely Θ(n, n′) holds) and (ii) tp(n′/m_{0}) ∈ ν̄^{−1}(C).

Proof. Let m realize q. By the assumption on q there is a set I, an ultrafilter U on I and q^{i} ∈ S_{m_{0}}(m_{0}) for i ∈ I, such that ν(q^{i}) ∈ C for all i ∈ I, and q is the ultraproduct via U of the q^{i}. Let m^{i} realize q^{i} such that tp(m^{i}/m, m_{0}) is finitely satisfiable in M_{0}. As ν(p) = ν(q) there is, by Remark 2.2(i), some g ∈ Autf_{L}(M) such that g(m) = n. Let n^{i} = g(m^{i}) (i ∈ I). The ultraproduct with respect to U of {tp(m, m^{i}, n, n^{i}, m_{0}) : i ∈ I} can be realized by (m, m′, n, n′, m_{0}) for some m′, n′ in M̄. We have, by the assumptions:

(a) tp(m′/m_{0}) = q.

(b) tp(m′/m, m_{0}) is finitely satisfiable in M_{0}.

(a) and (b) imply

(c) (m, m′) begins an indiscernible sequence. As tp(n, n^{i}) = tp(m, m^{i}) for all i, we see that tp(n, n′) = tp(m, m′) and so by (c),

(d) (n, n′) begins an indiscernible sequence. By Remark 2.2, ν(tp(n^{i}/m_{0})) ∈ C for all i, whereby

(e) tp(n′/m_{0}) ∈ ν̄^{−1}(C).

(d) and (e) give the desired conclusion.

Corollary 2.5 Let C ⊆ Gal_{L}(T). Then C̄ = ν(\overline{ν^{−1}(C)}).

Proof. Clearly C̄ contains ν(\overline{ν^{−1}(C)}), so it suffices to show that the latter is closed, that is, its preimage, X say, is closed in S_{m_{0}}(m_{0}). Let Ψ(x, m_{0}) be the partial type defining \overline{ν^{−1}(C)}. By Proposition 2.4, X is the closed subset of S_{m_{0}}(m_{0}) defined by: ∃y(Θ(x, y) ∧ Ψ(y, m_{0})).

Let X be a ∅-type-definable set (of possibly infinite tuples). \overline{E_{L}^{X}} denotes the closure of E_{L}^{X} in the space of complete types p(x, y) over ∅ extending x ∈ X ∧ y ∈ X. If X is the set of realizations of a complete type p, we notationally replace X by p.

Corollary 2.6 For any complete type p(x) over ∅, and realizations a, b of p. E_{KP} (a, b) iff there is some c such that Θ(a, c) and \overline{E_{L}^{p}}(c, b). In particular, on realizations of p, E_{KP} is the composition of E_{L} with \overline{E_{L}^{p}}.

Proof. It is enough to prove this where p = tp(m_{0}). Suppose E_{KP} (a, b) where a, b are realizations of p. We may assume that b = m_{0}. By 2.3(iii), ν(tp(a/m_{0})) is in the closure of the identity in Gal_{L}(T). By Proposition 2.4, there is c such that Θ(a, c) holds and tp(c/m_{0}) is in the closure of the set of tp(c′/m_{0}) where c′ realises p and E_{L}(c′, m_{0}). So \overline{E_{L}^{p}}(c, m_{0}).

Various examples will be given in section 4 which answer some obvious “qualitative” questions: such as can E_{KP} ≠ E_{L}, can E_{KP} ≠ \overline{E_{L}}? etc. But many questions remain (regarding Gal_{L}(T) and E_{L}). Let us suppose T to be countable. What are the possible cardinalities of Gal_{L}(T), of the kernel K(T) of Gal_{L}(T) → Gal_{KP} (T) and of the set of E_{L}-classes in a given E_{KP} -class? As, by Remark 2.2, Gal_{L}(T) is the quotient of the Polish space S_{m_{0}}(m_{0}) by the Borel equivalence relation E : ν(p) = ν(q), by well-known results, CH holds for the cardinality of Gal_{L}(T). Similarly for the other questions. For example, let X be the subspace of S_{m_{0}}(m_{0}) consisting of those tp(m/m_{0}) such that E_{KP} (m, m_{0}). Then X is a Polish space and K(T) is the quotient of X by E|X. Maybe the right question to ask is what can be the “Borel cardinality” (in the sense of [3]) of this E|X. We would like to conjecture that it is very complicated (if nontrivial). A possibly related question is: Suppose Y is a KP -class and E_{L} is trivial on Y (so Y is also an E_{L}-class). Does it follow that there is a finite bound on the d(a, b) for a, b ∈ X?

3 Products and Galois groups.

The examples in section 4 will involve (elaborations of) infinite products of structures. We find it worthwhile to give some generalities about products of structures and the effect on the Galois groups Gal_{KP} and Gal_{L}.

Let (M_{i} : i ∈ I) be a family of structures in disjoint languages L_{i}. We assume for simplicity that these are 1-sorted structures. By the disjoint sum or coproduct ∐_{i} M_{i} of this family we mean the family (M_{i} : i ∈ I) considered as a many-sorted structure. That is, the sorts are labelled by the elements of I, the ith sort is M_{i} equipped with all its L_{i}-structure, and there are no additional relations or functions. By the product ∏_{i} M_{i} we mean the structure M whose universe is the set of sequences (a_{i})_{i∈I} where a_{i} ∈ M_{i} for each i, equipped with, for each i ∈ I, the equivalence relation E_{i} of having the same ith coordinate, and also equipped with all the L_{i} structure on M/E_{i} = M_{i} (all i). We emphasize that M denotes both the structure ∏_{i} M_{i} as well as its underlying set.

If the M_{i} are all saturated, then so is ∐_{i} M_{i}. If I is finite, then ∐_{i} M_{i} is bi-interpretable with ∏_{i} M_{i}. In fact it is convenient in this case (I finite) to identify both structures with the structure (M, M_{i}, f_{i})_{i} where f_{i} is the projection map from M to M/E_{i} = M_{i}.

If I is infinite ∏_{i} M_{i} is still bi-interpretable with (M, M_{i}, f_{i})_{i}. However, even if the M_{i} are all saturated, ∏_{i} M_{i} will not be saturated, unless it is finite. Let E be the intersection of the E_{i} (so type-definable). In ∏_{i} M_{i} each equivalence class of E is a singleton. Adjoining a suitably large number of elements to each E-class yields a saturated elementary extension of ∏_{i} M_{i}, which we call (∏_{i} M_{i})^{∗} or M^{∗}. If I or M is finite we set M^{∗} = M. Note that in passing to M^{∗} no new elements were added to any of the sorts M_{i}, and that ∐_{i} M_{i} is interpretable in M^{∗}.

From now on we assume that each M_{i} is saturated and we stick with notation above.

Remark 3.1 (i) Aut(∐_{i} M_{i}) is precisely the product of the Aut(M_{i}). (ii) The canonical map from Aut(M^{∗}) to Aut(∐_{i}(M_{i})) is surjective. (iii) Let X ⊂ M_{i_{1}} ×..×M_{i_{n}} be definable in the structure M^{∗} with parameters from some M_{j}’s where j ≠ i_{1}, .., i_{n}. Then X is already ∅-definable in the coproduct (or product) of M_{i_{1}},..,M_{i_{n}}.

Corollary 3.2 (i) E_{L} on (even infinite tuples from) ∐_{i} M_{i} is the same in the structure M^{∗} as in the structure ∐_{i} M_{i}. (ii) Similarly for E_{KP}. (iii) Fix i_{0} ∈ I, and let c be a finite tuple from some other M_{j}’s (j ≠ i_{0}). Then E_{L} and E_{KP} on M_{i_{0}} in the sense of the structure (∐_{i} M_{i}, c) is the same as in the sense of the structure M_{i_{0}}.

Proof. Immediate.

Lemma 3.3 Suppose I is finite.

(i) For a, b ∈ M (the universe of ∏_{i} M_{i}). E_{L}(a, b) iff E_{L}(f_{i}(a), f_{i}(b)) (in M_{i} for each i). (ii) Similarly for E_{KP}.

Proof. By induction it is enough to look at the case where |I| = 2. We give a proof for E_{KP} which also works for E_{L} (although the E_{L} case is immediate from Fact 1.13).

So now M = M^{∗} is the product of M_{1} and M_{2}. Suppose a, b ∈ M. Let f_{i}(a) = a_{i} ∈ M_{i} for i = 1, 2 and likewise f_{i}(b) = b_{i}. Suppose that E_{KP} (a_{i}, b_{i}) in M_{i} for i = 1, 2. We must show that E_{KP} (a, b) in M. By (iii) of Corollary 3.2, E_{KP} (a_{1}, b_{1}) in the sense of M. So by Fact 1.4 there is f ∈ Autf_{KP} (M) such that f(a_{1}) = b_{1}. Let a′_{2} = f(a_{2}). So E_{KP} (a_{2}, a′_{2}) in the sense of M and so also of M_{2}. Thus E_{KP} (a′_{2}, b_{2}) in the structure M_{2}. By (iii) of Corollary 3.2 again there is g ∈ Autf_{KP} (M, b_{1}) such that g(a′_{2}) = b_{2}. So g·f ∈ Autf_{KP} (M) and takes a to b, thus E_{KP} (a, b) in M.

Remark 3.4 So for I finite one sees (generalizing the above to finite tuples) that Autf_{KP} (M) is the product of the Autf_{KP} (M_{i}) and even Gal_{KP} (M) is isomorphic to the product of the Gal_{KP} (M_{i}) as topological groups.

We now consider the case where I is possibly infinite. Let us call a subset X of the underlying set M of ∏_{i} M_{i} dense if for any i_{1}, .., i_{n} ∈ I and a_{i_{j}} ∈ M_{i_{j}} for j = 1, .., n there is x ∈ X such that f_{i_{j}}(x) = a_{i_{j}} for j = 1, .., n. The following is easy.

Lemma 3.5 Any dense subset of M is the underlying set of an elementary substructure of M (and also of M^{∗}).

Lemma 3.6 Suppose that a, b ∈ M^{∗} and E(a, b). Then E_{L}(a, b), in fact a and b have the same type over some model.

Proof. We may assume I to be infinite. Choose an automorphism α of M^{∗} which maps a to b and fixes all other E-classes pointwise. The set of elements fixed by α is an elementary submodel by the last lemma.

Lemma 3.7 (I arbitrary.) (i) Let a_{i}, b_{i} ∈ M_{i} for all i. Then E_{L}((a_{i})_{i∈I}, (b_{i})_{i∈I}) in M^{∗} iff there is n < ω such that d(a_{i}, b_{i}) ≤ n for all i ∈ I. (ii) Let a, b ∈ M^{∗}. Then E_{L}(a, b) iff there is n < ω such that d(f_{i}(a), f_{i}(b)) ≤ n for all i ∈ I. (iii) For a, b ∈ M^{∗}, E_{KP} (a, b) (in M^{∗}) iff E_{KP} (f_{i}(a), f_{i}(b)) in M_{i} for all i ∈ I.

Proof. (i) By Corollary 3.2, we make work in the structure ∐_{i} M_{i}. The assertion then follows immediately from Fact 1.13. (ii) Note that E(a, (f_{i}(a))_{i∈I}) and similarly for b. So, by Lemma 3.6, (ii) is an immediate consequence of (i).

(iii) Left implies right is clear. Now suppose the right-hand side holds. Let a_{i} = f_{i}(a). By Lemma 3.3, for each finite J ⊆ I, (*) E_{KP} ((a_{i})_{i∈J}, (b_{i})_{i∈J}) in the sense of structure ∐_{i∈J} M_{i}. By Corollary 3.2 (iii) for each finite J, (*) holds in the sense of the structure ∐_{i∈I} M_{i}. By Fact 1.7, (**) E_{KP} ((a_{i})_{i∈I}, (b_{i})_{i∈I}) holds in the sense of ∐_{i∈I} M_{i}. By Corollary 3.2 (ii), (**) holds in the structure M^{∗}. As in the proof of (ii), we deduce, that E_{KP} (a, b) in M^{∗}.

Corollary 3.8 Suppose that I = ω. Suppose moreover that there are i_{1} < i_{2} < .... and a_{i_{N}} , b_{i_{N}} ∈ M_{i_{N}} for each N such that E_{L}(a_{i_{N}} , b_{i_{N}}) but d(a_{i_{N}} , b_{i_{N}}) > N in M_{i_{N}}. Then

(i) On (the underlying set of) M^{∗}, E_{L} ≠ E_{KP}. Moreover some E_{KP} class splits into continuum many E_{L} classes. (ii) In ∐_{i} M_{i}, Autf_{L} is not closed in the full automorphism group. There is an E_{KP} class of infinite tuples (a_{i})_{i} (a_{i} ∈ M_{i}) which splits into continuum many E_{L}-classes.

Proof.(i) We can find some X ⊂ 2^{ω} of size continuum such that if η ≠ ν ∈ X then for arbitrarily large N, η(N) ≠ ν(N). Define elements c_{η} ∈ M^{∗} or even in M for η ∈ X as follows: if η(N) = 0 then f_{i_{N}} (c_{η}) = a_{i_{N}}, if η(N) = 1, f_{i_{N}} (c_{η}) = b_{i_{N}} and for j different from all i_{N}, f_{j}(c_{η}) is some fixed element of M_{j}. By the above lemma, we have in M^{∗} that E_{KP} (c_{η}, c_{ν}) for all η, ν ∈ X, but for distinct η, ν, c_{η} and c_{ν} are in different E_{L}-classes. (ii) Similar.

4 Examples

By Corollary 3.8, to find an example where E_{KP} ≠ E_{L} and where Autf_{L} is not closed, we only have to find structures M_{i} for i < ω as in the hypothesis of 3.8. We proceed to do this now.

We will define structures M_{n} for n = 1, 2, .... Let n ≥ 1. M_{n} will be the structure whose universe is the circle of centre the origin, and radius 1 say (in a saturated real-closed field), equipped with a ternary relation S_{n} and a unary function g_{n}. S_{n} is the “circular order”: S_{n}(a, b, c) holds just if a, b, c are distinct and b comes before c going around the circle clockwise starting at a. g_{n} is rotation (clockwise) by 2π/n radians. Note that g_{n} is a bijection, (g_{n})^{n} is the identity, and for any a, S_{n}(a, x, y) is a dense linear ordering on M_{n} \ {a}. We will call a subset X of M_{n} dense if for all a ≠ c ∈ X there is b ∈ X with S_{n}(a, b, c). (Hopefully there will be no confusion with denseness as defined before 3.5.) Note also that any finitely generated substructure is finite. In fact the substructure generated by {a_{1}, .., a_{k}} is precisely {g_{n}^{j}(a_{i}) : i = 1, .., k, j = 0, .., n − 1}. It will be convenient later to let R_{n} denote the binary (symmetric) relation : x = y ∨ S_{n}(x, y, g_{n}(x)) ∨ S_{n}(y, x, g_{n}(y)) (so meaning that the shortest arc joining x and y has length < 2π/n).

Lemma 4.1 (i) T h(M_{n}) has a unique 1-type over ∅. (ii) Let a ∈ M_{n}, and let I_{a} = {x ∈ M_{n} : S_{n}(a, x, g_{n}(a))}. For x, y ∈ I_{a}, write x < y iff S_{n}(a, x, y). (So (I_{a}, <) is a dense linear ordering with no first or last element.) Then there is a natural 1 − 1 correspondence between partial isomorphisms between finite tuples in (I_{a}, <) and partial isomorphisms between finite substructures in (M_{n}, a): if b̄, c̄ are finite tuples in I_{a} with the same quantifier-free type in (I_{a}, <) then (b̄, g_{n}(b̄), .., (g_{n})^{n−1}(b̄)) has the same quantifier-free type as (c̄, g_{n}(c̄), .., (g_{n})^{n−1}(c̄)) in (M_{n}, a).

Proof. (i) In the elementary substructure M_{n}(R) of M_{n}, rotation by r degrees (any r) is an automorphism. So there is a unique 1-type realised in M_{n}(R), so T h(M_{n}) has a unique 1-type. (ii) Easy.

Proposition 4.2 (i) T h(M_{n}) has quantifier-elimination. (ii) X ⊆ M_{n} is an elementary substructure of M_{n} just if X is a substructure (i.e. closed under g_{n}) and X is dense.

Proof. (i) We do back-and-forth in M_{n}. Let (a_{1}, ...a_{k}), (b_{1}, .., b_{k}) have the same quantifier-free type. Given c we want d such that (a_{1}, .., a_{k}, c) and b_{1}, .., b_{k}, d) have the same quantifier-free type. By Lemma 4.1(i), we may assume that a_{1} = b_{1} = a. We may assume that the tuple of a_{i}’s enumerates a substructure. By relabelling we may assume that this substructure is generated by (a, a_{2}, .., a_{r}) where a_{i} ∈ I_{a} for i = 2, .., r. Now (a_{2}, .., a_{r}) has the same quantifier-free type as (b_{2}, .., b_{r}) in I_{a}. Replacing c by some (g_{n})^{j}(c) we may assume c ∈ I_{a}. So we find d ∈ I_{a} such that (a_{2}, .., a_{r}, c) has the same quantifier-free type as (b_{2}, .., b_{r}, d) in I_{a}. By Lemma 4.1(ii), (a_{2}, ., a_{r}, c) and (b_{2}, .., b_{r}, d) have the same quantifier-free type in (M, a) which is enough. (ii) Left implies right is clear. Right implies left: Working over a given finite tuple from X the back-and-forth argument above still works even if we also require that the first player always chooses in X. So X is an elementary substructure.

Corollary 4.3 Let a, b ∈ M_{n}. Then a and b have the same type over some elementary substructure of M_{n} if and only if R_{n}(a, b).

Proof. Suppose first that R_{n}(a, b), and we may assume that S_{n}(a, b, g_{n}(a)). Let X be the substructure of M_{n} generated by {c ∈ I_{a} : b < c}. By Proposition 4.2(ii), X is an elementary substructure of M_{n} and tp(a/X) = tp(b/X). Conversely, suppose ¬R_{n}(a, b). Let N be any elementary substructure of M_{n}. Let c ∈ N. Then for some 0 ≤ i, j < n we have S_{n}(a, (g_{n})^{i}(c), b) and S_{n}(b, (g_{n})^{j}(c), a), whereby S_{n}((g_{n})^{i}(c), b, (g_{n})^{j}(c)) but ¬S_{n}((g_{n})^{i}(c), a, (g_{n})^{j}(c)) so a and b have different types over N.

We immediately obtain:

Corollary 4.4 E_{L} (and so E_{KP}) is trivial on (the universe of) M_{n}. On the other hand there are a, b ∈ M_{n} such that d(a, b) > n/2.

Let M^{∗} be the saturated structure built from the M_{n} as in the previous section. From Corollary 4.4, Lemma 3.7, and Corollary 3.8 we obtain:

Proposition 4.5 Neither T h(M^{∗}) nor T h(∐_{n} M_{n}) are G-compact. E_{KP} is trivial on the underlying set of M^{∗} but there are continuum many E_{L}-classes on this set. In ∐_{n} M_{n}, Autf_{L} is not closed in the full automorphism group.

The “space” of Lascar strong 1-types in M^{∗} has a rather easy representation. It is the space (S_{1})^{ω} quotiented by the Borel equivalence relation F, where F ((a_{i})_{i}, (b_{i})_{i}) holds iff there is m such that for each n the length of the shortest arc between a_{n} and b_{n} is less than m/n. F appears to be substantially more complicated, in the sense of Borel cardinalities, than the Borel equivalence relation E_{1}, eventual agreement on countable sequences of reals. Again we would suppose this to be the case for any example produced using Corollary 3.8.

We now modify the above example to give an example where E_{KP} is not \overline{E_{L}}, showing that Corollary 2.6 is best possible.

We consider again the circles M_{n} mentioned at the end of section 2, but we now take M to be ∏(M_{n} : n even). Clearly the previous analysis still goes through. Recall that f_{n} is the projection map from M to M_{n}. Now define a new binary function h on M: for a ∈ M, h(a) is the unique element b ∈ M such that f_{n}(b) = (g_{n})^{n/2}(f_{n}(a)) for all n (that is, f_{n}(a) and f_{n}(b) are “antipodal” in M_{n} for all n). Note that no new structure is added to any M_{n}. Let N be the structure (M, h). Note that h is an involution, and is an automorphism of M, ∅-definable on each M_{n}. Let N^{∗} be the saturated elementary extension M^{∗} of M described in section 3, equipped with an extension of h which establishes a bijection between the E-class of a and the E-class of b (whenever h(a) = b in N). By a back and forth argument N^{∗} is a saturated elementary extension of N. As before the many-sorted saturated structure ∐_{n} M_{n} is interpretable in N^{∗}.

Lemma 4.6 The canonical map from Aut(N^{∗}) to Aut(∐_{n} M_{n}) is surjective.

Proof. Clear.

We conclude:

Lemma 4.7 E_{L} in the sense of N^{∗} on infinite tuples (a_{n})_{n} (where a_{n} ∈ M_{n}) is the same as in the sense of ∐_{n} M_{n}. Likewise for E_{KP}. In particular, E_{KP} is trivial on such infinite tuples in the structure N^{∗}.

Lemma 4.8 Let a, b ∈ N^{∗} (namely in the home sort) be such that E(a, b). Then there is an elementary substructure of N^{∗} (even of N) over which a and b have the same type.

Proof. Choose a small dense subset X of N which is closed under h and does not meet the E-class of a. Then X is an elementary submodel and tp(a/X) = tp(b/X).

As in Lemma 3.7, we conclude

Lemma 4.9 Both E_{L} and E_{KP} on the home sort in N^{∗} agree with the corresponding relations in the reduct M^{∗}. In particular E_{KP} is trivial.

Lemma 4.10 The formula h(x) ≠ y is in \overline{E_{L}} in N^{∗}.

Proof. If E_{L}(a, b) then for some n, (g_{n})^{n/2}(f_{n}(a)) ≠ f_{n}(b) in the circle M_{n}. So h(a) ≠ b.

We conclude

Proposition 4.11 In N^{∗}, \overline{E_{L}} is properly contained in E_{KP} (on the home sort)

The final example is one of a complete type p(x) in a sort S such that \overline{E_{L}^{p}} ≠ \overline{E_{L}^{S}}|p. Infinite products enter the picture again, but only “at infinity”. We will describe a many-sorted structure W. It will be convenient to put in ∐(M_{n} : n even) at the beginning (M_{n} the circles as above). So the sorts will be the M_{n} for n even together with another sort S say. S will be a disjoint union of predicates P_{n} (n even), where P_{n} is (in bijection with the underlying set of) M_{2} × M_{4} × ... × M_{n}. We also give ourselves projection functions f_{i}, i even (as part of the structure). f_{i} is defined only on those P_{n} for n ≥ i, and takes (a_{2}, a_{4}, .., a_{n}) ∈ P_{n} to a_{i} ∈ M_{i}. (Formally we could instead add the graph of f_{i} as a relation.) So far we have defined a structure W_{0} say. Let us say a few words about this structure before continuing. Let p(x) be the type in sort S which says {¬P_{n}(x) : n < ω}. p is a complete type. f_{i} is defined on all of p. Let E be the (type-definable) equivalence relation on p: f_{i}(x) = f_{i}(y) for all i. A saturated elementary extension (W_{0})^{∗} can be obtained by adding realizations of p, a suitable number in each E-class. The set of realizations of p in (W_{0})^{∗} is essentially the structure M^{∗} from section 2. On elements (or finite tuples) from the base model W_{0}, E_{L} is trivial. On realizations of p, E_{L} is as in M^{∗}. E_{KP} is trivial on W_{0}^{∗}.

We will add a function h to W_{0} to obtain W. h is a function from S to S: Suppose a ∈ P_{n}. Then h(a) is the unique b ∈ P_{n} such that for each even i ≤ n, f_{i}(b) = (g_{i})^{i/2}(f_{i}(a). Extend h to W_{0}^{∗} by making it a bijection between E-classes X and Y whenever for some (any)x ∈ X, y ∈ Y, f_{i}(y) = g_{i}^{i/2}(f_{i}(x)) for all (even) i. We obtain a structure W^{∗}. We leave it to the reader to check that W^{∗} is a saturated elementary extension of W, and that p(x) remains a complete type in T h(W^{∗}).

As in the previous examples we have:

Fact 4.12 (i) ∐_{n} M_{n} has no more induced structure in W^{∗}. (ii) For a, b realizing p(x), E(a, b) implies a and b have the same type over some model.

From this fact, we see as before that on p(x), E_{L}(a, b) holds if and only if for some n, d(f_{i}(a), f_{i}(b)) ≤ n for all i. It follows that the formula h(x) ≠ y is in \overline{E_{L}^{p}}. (Note also that E_{KP} is trivial on p(x).) On the other hand on each predicate P_{n}, E_{L} is trivial. So if a^{n}, b^{n} ∈ P_{n} with h(a^{n}) = b^{n} for each n, then any limit of tp(a^{n}, b^{n})_{n} will be in \overline{E_{L}}|p and will contain the formula h(x) = y. Thus

Proposition 4.13 In the structure W^{∗}, Ē_{L}^{p} ≠ Ē_{L}|p.

References

[1] S. Buechler, A. Pillay and F. Wagner, Supersimple theories, to appear in Journal AMS.

[2] E. Hrushovski, Simplicity and the Lascar group, preprint 1997.

[3] G. Hjorth and A. Kechris, New dichotomies for Borel equivalence relations, Bulletin of Symbolic Logic 3 (1997), 329-346.

[4] B. Kim, A note on Lascar strong types, Journal of Symbolic Logic 63 (1998), 926-936.

[5] B. Kim and A. Pillay, Simple theories, Annals of Pure and Applied Logic, 88(1997), 149-164.

[6] D. Lascar,The category of models of a complete theory, Journal of Symbolic Logic 47(1982), 249-266.

[7] D. Lascar and A. Pillay, Hyperimaginaries and automorphism groups, to appear in Journal of Symbolic Logic.