Interpretable groups, stably embedded sets, and Vaughtian pairs

Bernhard Herwig, Institüt für mathematische Logik,

Universität Freiburg, D-79104 Freiburg, Germany, herwig@ruf.uni-freiburg.de

Ehud Hrushovski, Department of Mathematics, The Hebrew University, Jerusalem, Israel ehud@math.huji.ac.il

Dugald Macpherson, Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, England h.d.macpherson@leeds.ac.uk

March 1, 2002

2000 Mathematics Subject Classification: 03C52

Abstract

The paper concerns sufficiently saturated structures M over a countable language with a unary predicate P. It is shown that if P (M) is stably embedded and there are no Vaughtian pairs with respect to P, then an infinite group is interpretable over M (in an infinitary sense of ‘interpretable’). Also, it is shown that if M is ω-categorical, f : D → P is a 0-definable map with finite fibres, and P (M) is stably embedded but D is not, then some infinite group is interpretable over M.

1 Introduction

We consider (sufficiently saturated) first order structures M with a unary predicate P. We suppose that the structure is controlled in a rather weak sense by P; namely, that P does not give rise to a Vaughtian Pair, and is stably embedded. The most simple examples of such a situation arise as one of the following. A) The structure is algebraic over P. B) P has the structure of a group (say a vector space) and the rest of the structure is an affine space for P. We will show that in general, either Case A holds or there is an infinite group living in M (in a sense which needs to be made precise). Under additional assumptions this group will live in P.

The proof was first visualised on a visit by Hrushovski to London in 1988. The original assumptions were stronger (relative categoricity – see Section 4) but no stability or simplicity were assumed. The main ingredients – stable embeddedness, co-analysability, and the definition of the group, were as below. Some of the other details were different from those below, or perhaps missing altogether.

Meanwhile, and independently, Shami and Wagner considered related questions in the case of simple theories. Wagner earlier realised the relevance of a theorem due to Schlichting and to Bergman and Lenstra, given below. We follow Shami-Wagner [9] here in quoting this lemma, once we obtain its hypotheses.

In the stable and simple contexts, to find a group one deals with two definable sets D and P, with D internal to P (that is, for some ℓ there is a definable surjection P^{ℓ} → D). In the general situation considered here, a third definable set C arises: the elements of C are parameters defining the function P^{ℓ} → D. To analyse the relation of C and P, one would seem to need a new definable set C′, and so on. It would be interesting to pursue this. We analyse the phenomenon in a certain minimal manifestation, and there we show just three sets are needed in order to obtain a group.

Suppose M is an ω_{1}-saturated model , over a countable language. The 0definable set P (M) is stably embedded in M if for all n > 0, every definable subset of P^{n} is definable with parameters from P. By ω_{1}-saturation of M, this is equivalent to assuming the uniform version for an arbitrary model N of the theory : namely, that for every formula ϕ(x̄, ȳ) there is a formula ψ(x̄, z̄) without parameters such that for every c̄ ∈ N there is b̄ ∈ N(P) such that N ⊧ ∀x̄ ∈ P (ϕ(x̄, c̄) ↔ ψ(x̄, b̄)).

Remark 1.1 Assume that M is an uncountable structure over a countable language with a unary predicate P, and is saturated.

(a) The following are equivalent.

(i) P is stably embedded.

(ii) The restriction map Aut(M) → Aut(P) is surjective (in general the image would just be a dense subset of Aut(P)).

(iii) For any tuple ā ∈ M, tp(ā/P (M)) is definable.

(b) If P is stably embedded, then any two tuples from M with the same type over P (M) are Aut(M/P)-conjugate.

One source for this is (5.6) of [3]; it was mentioned as an exercise in [7], but similar results were known much earlier (cf [10], [8]). In fact, the equivalence holds under assumptions weaker than saturation. It suffices to ensure M is ω_{1}-saturated and that for any countable B ⊂ M, and every B-definable subset D of M which is stably embedded over C, the structure M is strongly ω_{1}-homogeneous over B ∪ D; the homogeneity here means that if ā, b̄ are tuples from M, E ⊂ M is countable, and tp(ā/B ∪D ∪E) = tp(b̄/B ∪D ∪E), then there is σ ∈ Aut(M) fixing B ∪D ∪E pointwise with σ(ā) = b̄. It can be checked that just in ZFC, every complete theory over a countable language has a model of size 2^{ℵ_{0}} with this property.

Conventions 1.2 We assume M is a model over a countable language with a unary predicate P, and is ω_{1}-saturated and has sufficient homogeneity to ensure that the equivalences of Remark 1.1 hold. We often write P for P (M), the set of realisations of P in M. This setting is assumed to hold in Section 2 (from Corollary 2.7 onwards) and in Section 3.

A Σ^{1}(B) (respectively, Π^{1}(B)) -definable relation is a union (respectively, intersection) of countably many B-definable relations. A Σ^{1} (respectively, Π^{1}) - definable relation is a Σ^{1}(B)-definable relation, for some countable B ⊂ M. In general, ‘definable’ means ‘definable with parameters’.

A Π^{1}- interpretable group is a Π^{1}-definable set G, a Π^{1}-definable equivalence relation E on G, and a definable ternary relation R on a definable set containing G, which induces a function ∗ : (G/E)^{2} → (G/E) which is a group law. By induces, we mean that for g_{1}, g_{2}, g_{3} ∈ G, we have g_{1}/E ∗ g_{2}/E = g_{3}/E if and only if there are h_{1}, h_{2}, h_{3} ∈ G with h_{i}Eg_{i} and R(h_{1}, h_{2}, h_{3}).

When D′, D′′ are subsets of M^{eq}, we write Aut(D′/D′′) for the group of permutations of D′ which are elementary over D′′. This is a closed permutation group, and in general properly contains the group induced on D′ by its setwise stabiliser in Aut(M/D′′). If D ⊂ M and a ∈ acl(D) , we write Mult(a/D) for the number of realisations of tp(a/D). We sometimes use the notation AB for A ∪ B, and Ac for A ∪ {c}, where A, B, {c} are sets of parameters.

We shall at various times be assuming some of the following hypotheses. Note that H2+ strengthens H2, and H2* strengthens H2+.

Hypotheses H1 There is no uncountable N ≡ M with P (N) countable. H2 P is stably embedded. H2+ For any tuple a from M, tp(a/P (M)) is isolated. H2* For any tuple a from M, tp(a/P (M)) is algebraic.

The main theorem of the paper now follows. Some corollaries are given in Section 4.

Theorem 1.3 Assume Convention 1.2 for M, and also H1, H2, but not H2*. Then there exists an infinite group, Π^{1}-interpretable over M. If H1, H2+ hold but not H2*, there exists an infinite group interpretable over M.

Acknowledgement. The research of the first and third authors was partially supported by EPSRC grant GR/K60503. This research was conducted by Ehud Hrushovski as a CMI Prize Fellow, for the Clay Mathematics Institute.

2 Preliminaries

We first give a useful equivalent to the condition H1, implicit in Baldwin and Lachlan [1]. We include a proof of equivalence (Proposition 2.4 below).

Definition 2.1 Let N be a structure with a subset defined by a unary predicate P, and let Q be a definable subset of N^{m} (where n > 0). Then

(i) Q is P -co-analysable in 0 steps if Q is finite;

(ii) Q is P -co-analysable in k + 1 steps if for some ℓ there is a set R ⊂ Q × P^{ℓ}, definable with parameters in N, such that

(a) the projection R → Q is surjective, and

(b) if a ∈ P^{ℓ}, then the fibre {x ∈ Q : R(x, a)} is P -co-analysable in k steps uniformly in a; that is, the formulas witnessing co-analysability of the fibres have a uniform form, but the parameters in these formulas may be chosen freely for each fibre.

(iii) Q is P -co-analysable if for some natural number k it is co-analysable in k steps.

Remark 2.2 The condition P -co-analysability is a property of the theory; that is, if Q is N-definable then Q is P -co-analysable in k steps in N if and only if it is P -co-analysable in k steps in any elementary extension of N. The uniformity condition in (ii)(b) could be omitted if we require that the ambient structure, over a language L, is |L^{+}|-saturated.

Lemma 2.3 Suppose that for i = 1, 2, Q_{i} is P -co-analysable in k_{i} steps. Then Q_{1} ∨ Q_{2} is P -co-analysable in k := max{k_{1}, k_{2}} steps.

Proof. Suppose Q_{i} is k_{i}-step co-analysable witnessed by R_{i} ∈ Q × P^{ℓ_{i}}, for i = 1, 2. We may suppose k_{1} = k_{2}, and by adding dummy parameters, that ℓ_{1} = ℓ_{2}. Now R_{1} ∪ R_{2} witnesses the result. □

Proposition 2.4 Let T be a complete theory in a countable language L, and P, Q be unary predicates. The following are equivalent.

(i) T has no model N with P (N) countable and Q(N) uncountable.

(ii) Q is P -co-analysable.

Proof. (i) ⇒ (ii) We shall suppose that Q is not co-analysable. Choose countable N′ ⊧ T, and suppose N′ is an elementary substructure of a large sufficiently saturated C ⊧ T. By taking a countable elementary extension if necessary we may suppose that for any ℓ and any definable relation R(x, y), if each set R(N′, b) (b ∈ P^{n} for some n) is k-step co-analysable, then the R(x, b) are uniformly (as the parameter b varies) co-analysable in k steps. It suffices to show there is an elementary extension N of N′ with P (N) = P (N′) and Q(N) ≠ Q(N′). We must find a non-algebraic complete type q(x) over N′ containing the formula Q(x), such that if a ∈ C realises q then the partial type p := {P (y)} ∪ {y ≠ m : m ∈ P } is not isolated over N′a. For then, if T′ is the theory of C in L(N′a), then we may take N to be the L-reduct of any model of T′ omitting p.

We build a sequence (Q_{n}(x) : n ∈ ω) of formulas over N′ which are not P -co-analysable, such that Q_{0} := Q and N′ ⊧ ∀x(Q_{n+1} → Q_{n}). Let (ψ_{i}(x, y) : i < ω) list all formulas over N′ in the two (single) free variables x, y. Assume that Q_{0}, …, Q_{n} have been found as above, and that in addition, if a ∈ C with ⊧ Q_{n}(a), then for any i < n, if ⊧ ∃y(ψ_{i}(a, y) ∧ P (y)), then there is b ∈ P (N′) with ⊧ ψ_{i}(a, b).

Case (i). Q_{n}(x) ∧ ¬∃y(ψ_{n}(x, y) ∧ P (y)) is not P -co-analysable. In this case, put Q_{n+1}(x) := Q_{n}(x) ∧ ¬∃y(ψ_{n}(x, y) ∧ P (y)).

Case (ii). Q_{n}(x)∧¬∃y(ψ_{n}(x, y)∧P (y)) is P -co-analysable. Now, by Lemma 2.3, Q′(x) := Q_{n}(x) ∧ ∃y(ψ_{n}(x, y) ∧ P (y)) is not P -co-analysable. Let R be the relation Q′(x)∧ψ_{n}(x, y)∧P (y) on Q′×P. Since R projects onto Q′, there is some b ∈ P such that Q′(x) ∧ ψ_{n}(x, b) is not P -co-analysable. Now put Q_{n+1}(x) := Q_{n}(x) ∧ ψ_{n}(x, b).

Finally, choose q to be any complete type over N′ containing {Q_{n} : n ∈ ω}. By the condition on Q_{n+1}, if a realises q and p is as above, then ψ_{n}(a, y) does not isolate p.

(ii) ⇒ (i) Suppose this is false, and, with k as small as possible, find N ⊧ T, and k-step co-analysable Q such that Q(N) is uncountable and P (N) is countable. Clearly k > 0, so there is definable R ⊂ Q × P^{ℓ} projecting surjectively to Q, with (k − 1)-step co-analysable fibres over P^{ℓ}. By induction, each fibre R(N, a) (for a ∈ P^{ℓ}) is countable, so Q is countable. □

Remark 2.5 The above proof just uses a version of co-analysability where the parameter l in Definition 2.1 (ii) takes value 1. It follows that such a version is equivalent to that in 2.1.

We shall use a group-theoretic result of Schlichting [5], re-discovered by Bergman and Lenstra [2]. In fact, P. M. Neumann (Theorem 5 of [2]) has shown that the function f(n) below may be taken to be n^{n^{n}}.

Theorem 2.6 ([2] Theorem 4) There is a function f : ω → ω such that the following holds. Let G be a group and H be a subgroup, and suppose there is n ∈ ω such that for all g ∈ G, |H : H ∩ H^{g}| ≤ n. Then there is N ⊴ G such that |N : H ∩ N| ≤ n and |H : H ∩ N| ≤ f(n).

In the next corollary, when G is a permutation group on X and x ∈ X and A ⊂ X we write G_{x} for the stabiliser in G of x, and G_{(A)} for the pointwise stabiliser in G of A. If G has an induced action on some invariant set B (possibly a quotient), we write G^{B} for the permutation group induced on B. The argument is very close to some in [9]. For the rest of Sections 2 and 3, Convention 1.2 regarding M applies.

Corollary 2.7 Assume H2, let C be the set of realisations in M of a partial type over P (M), and put G := Aut(C/P). Suppose there is n ∈ ω such that for all a, b ∈ C, |G_{a} : G_{a} ∩ G_{b}| ≤ n.

(i) There is a G-invariant equivalence relation τ on C with finite classes, and if C̄ := C/τ then there is finite F ⊂ C̄ such that G_{(F)} fixes C̄ pointwise.

(ii) If C is a G-orbit, then any τ as in (i) is the intersection with C^{2} of a P -definable set.

Proof. (i) For each a ∈ C, we have |G_{a} : G_{a} ∩ G_{a}^{g}| ≤ n for all g ∈ G. Hence there is N ⊴ G such that |N : G_{a} ∩ N| ≤ n and |G_{a} : G_{a} ∩ N| ≤ f(n) (where f is as in Theorem 2.6). Furthermore, for any b ∈ C, |G_{a} : G_{a} ∩ G_{b}| ≤ n and |G_{b} : G_{a} ∩ G_{b}| ≤ n. It follows that |G_{b} : G_{b} ∩ N| ≤ |G_{b} : G_{b} ∩ G_{a} ∩ N| = |G_{b} : G_{b} ∩ G_{a}| × |G_{b} ∩ G_{a} : G_{b} ∩ G_{a} ∩ N| ≤ n|G_{a} : G_{a} ∩ N| ≤ nf(n) and likewise |N : G_{b} ∩ N| ≤ n^{2}.

Let τ be the G-invariant equivalence relation on C whose classes are the Norbits, and put C̄ := C/τ. Let b ∈ C. Since |N : G_{b} ∩ N| ≤ n^{2}, the τ-class of b has size at most n^{2}. Also, since |G_{b} : G_{b} ∩ N| ≤ nf(n), also |GC̄ ; b : GC̄ ; b ∩ N C̄| ≤ nf(n). Thus, as N C̄ = 1, |GC̄ ; b| ≤ nf(n). The existence of F follows.

(ii) In this case all τ-classes have the same size, ℓ, say. Now τ is is a union of finitely many (at most ℓ) complete types on C^{2} over P; namely, for fixed a ∈ C, the types {tp(ab/P) : bτa}. Thus, τ is a type and by compactness there is definable τ′ ⊃ τ such that for each c ∈ C there are at most ℓ elements c′ ∈ C with τ′(c, c′). Then τ′ ∩ C^{2} = τ ∩ C^{2}. □

The next lemma is essentially in [7] (stability is assumed there, but not used).

Lemma 2.8 Assume H2, and that C is the set of realisations in M of a complete type over P (M), with C ⊂ dcl(P c) for any c ∈ C. Then

(i) Aut(C/P) is Π^{1}-interpretable in M;

(ii) if H2+ holds, then Aut(C/P) is interpretable in M;

(iii) if H2+ holds and P carries a structure whose 0-definable relations are those induced from 0-definable relations of M, then Aut(C/P) is interpretable in P.

Proof. (i) An automorphism σ of C over P is coded by the pair (c, σ(c)). Since C ⊂ dcl(P c), Aut(C/P) acts regularly on C, so σ is uniquely determined by (c, σ(c)). Furthermore (c, c′) and (d, d′) code the same automorphism if and only if tp(cd/P) = tp(c′d′/P). For suppose tp(cd/P) = tp(c′d′/P) and σ(c) = c′. There is a formula ϕ(x, y) over P such that ϕ(c, d) and ϕ witnesses interdefinability of c and d over P. Then ϕ(c′, d′) also holds, and, as σ ∈ Aut(C/P), ϕ(c′, σ(d)) holds, and it follows that σ(d) = d′. The relation tp(e/P) = tp(e′/P) is Π^{1}. Hence there is a Π^{1}-definable equivalence relation E on C^{2}, where E(cc′, dd′) if and only if tp(cd/P) = tp(c′d′/P). Then E(cc′, dd′) if and only if (c, c′) and (d, d′) code the same automorphism. By H2, C (and hence C^{2}) are also Π^{1}-definable.

Write [cc′] for the E-class of (c, c′), and ∗ for the group operation. Then [cc′] ∗ [dd′] = [ee′] if and only if there is f ∈ C with E(dd′, c′f) and E(cf, ee′). Let R be the definable relation given by R(xx′, yy′, zz′) if and only if x′ = y, z = x, and z′ = y′. R induces the group operation.

(ii) Under H2+, C is definable over P. Also, E is Σ^{1}-definable: tp(cd/P) = tp(c′d′/P) if and only if there exists a formula ϕ(x_{1}, x_{2}, ȳ) with no parameters such that for every b̄ ∈ P and a_{1} ∈ C there exists at most one a_{2} ∈ C with ϕ(a_{1}, a_{2}, b̄) and such that ∃ȳ ∈ P (ϕ(c, d, ȳ) ∧ ϕ(c′, d′, ȳ)) holds. Taking a disjunction over all such ϕ, we see that E is Σ^{1}-definable, and hence is definable by (i).

(iii) Formally, we interpret on P the group K of permutations of C which commute with Aut(C/P). Since Aut(C/P) acts regularly on C, this is definably isomorphic to Aut(C/P) (it is the opposite group). For each (c, c′) ∈ C^{2} there is a unique g ∈ K with g(c) = c′: if d ∈ C there is unique σ ∈ Aut(C/P) with σ(c) = d, and g(d) = gσ(c) = σ(c′). Furthermore, (c, c′) and (d, d′) determine the same element of K if and only if tp(cc′/P) = tp(dd′/P), a definable equivalence relation over P (as in (ii)).

For each c ∈ C, since C ⊂ dcl(P c) there is a c-definable injection t_{c} : C → P^{eq}, with range Q = Q(c). As C is a complete type over P, the set Q is independent of the choice of c. For each h ∈ K, let c ∈ C and let σ_{h} denote the definable permutation t_{h(c)}t_{c}^{−1} of Q. Since h commutes with elements of Aut(C/P), this definition is independent of the choice of c. The induced subgroup of Sym(Q) is isomorphic to K. Furthermore, the elements σ_{h} are uniformly definable from the pairs (c, h(c)), and hence by H2 are uniformly definable in the induced structure on P. The group operation is likewise definable over P, and the resulting group lives in P^{eq}. □

3 Proof of Theorem 1.3

Convention 1.2 on M is assumed throughout this section.

Lemma 3.1 The hypotheses H1, H2, H2+ are preserved under adding finitely many parameters.

Proof. For H1 there is nothing to prove. For H2 (respectively H2+) observe that if tp(ab/P) is definable (respectively, isolated) then so is tp(a/P b). □

Lemma 3.2 Assume H1 and not H2*. Then for some finite B ⊂ M, there is a B-definable set D ⊂ M such that D ⊄ acl(P B) but D ⊂ acl(P c) for some tuple c.

Proof. Assume this is not the case. Then whenever D is B-definable and D ⊂ acl(P Bc), we have that D ⊂ acl(P B). We claim that whenever D is B-definable and co-analysable over P in k steps, then D ⊂ acl(P B). This is proved by induction on k, over all D, B. For let R ⊂ D×P^{ℓ} be a Bc-definable relation witnessing k-step co-analysability of D. Each fibre R(D, a) is (k − 1)-step co-analysable, and Bcadefinable, so by induction is a subset of acl(P Bca) = acl(P Bc) (as a ∈ P^{ℓ}). Hence D ⊂ acl(P Bc), so by our assumption, D ⊂ acl(P B), proving the claim. Finally, observe that by H1 and Proposition 2.4, x = x is P -co-analysable and 0-definable, so M ⊂ acl(P (M)), a contradiction. □

By Lemma 3.2 there is a tuple c and a positive integer m such that for any d ∈ D, Mult(d/P Bc) ≤ m, and such that | Aut(D/P B) : Aut(D/P Bc)| is infinite. Now minimise m over all choices of D′ ⊂ D, B, c, and let C := tp(c/P B). If H2+ is assumed, then C will be definable over P. By Lemma 3.1, we may suppose the elements of B are named by constants.

Lemma 3.3 For any tuple e from M there exists d ∈ D with Mult(d/P e) ≥ m.

Proof. Otherwise, fixing D, and replacing c by (c, e), we could lower the value of m. □

We have now proved the following.

Lemma 3.4 Given H1 and not H2*, the following holds. H3 There is a 0-definable set D, and some complete type C over P, such that:

(i) for any c ∈ C and d ∈ D, Mult(d/P c) ≤ m;

(ii) for any e, there is d ∈ D, Mult(d/P e) ≥ m;

(iii) Aut(D/P c) does not have finite index in Aut(D/P);

(iv) m is minimal over all definable D′ ⊂ D and C satisfying (i)-(iii); that is, there does not exist a parameter set A, some A–definable D′ ⊂ D, and some complete type C′ over P ∪ A, and some m′ < m such that (i)-(iii) holds with A incorporated as constants and with (D′, C′, m′) replacing (D, C, m).

Let I = I_{m} be the ideal (in the boolean algebra of definable subsets of D) consisting of the definable subsets D′ of D, such that for some finite tuple e from M, for all d′ ∈ D′, Mult(d′/P e) < m. By Lemma 3.4, I_{m} is a proper ideal. Let I^{∗} be the filter dual to I_{m}. Elements of I^{∗} will be called large sets. The following lemma takes a little argument, and is left as an exercise.

Lemma 3.5 Under just Convention 1.2, assume that D ⊂ acl(P c) is 0-definable and that for every d ∈ D, Mult(d/P c) ≤ m. Then there exists a c-definable function f : D → P^{eq} whose fibres have size at most m.

Let C be as in Lemma 3.4. Then by Lemma 3.5, for every c ∈ C there is a c-definable function f_{c} : D → P^{eq}, such that some large set D′ ⊂ D is a union of fibres of f_{c} of size precisely m. Let

P_{1} = {a : |f_{c}^{−1}(a)| = m}

Then since C is a complete type over P, the definition of P_{1} is independent of the choice of c. Also, f_{c}^{−1}(P_{1}) is large (but does depend on c). Let P_{2} = {a : 0 < |f_{c}^{−1}(a)| < m}. Then since C is a complete type, again P_{2} does not depend on c. However, possibly f_{c}^{−1}(P_{2}) does. In any event, the partial function f_{c} : D → P_{1} ∪P_{2} has all fibres finite, of size ≤ m. We shall assume, in addition to H3, by moving to imaginaries:

H3(v) If c ≠ c′ ∈ C then f_{c} ≠ f_{c′}.

Lemma 3.6 Assume H2 and H3(i)-(v). Then C ⊂ acl(P c_{0}) for any c_{0} ∈ C.

Proof. Fix c_{0} ∈ C. It suffices to show that any c ∈ C has only finitely many conjugates over P c_{0}; equivalently that f_{c} has only finitely many conjugates.

Let E(c, c′) := P_{2} ∪ {a ∈ P_{1} : ¬∃a′ ∈ P_{1}(f_{c}^{−1}(a) = f_{c′}^{−1}(a′))} and G(c, c′) := P_{1} \ E(c, c′). Then

f_{c}^{−1}(G(c, c′)) = f_{c′}^{−1}(G(c′, c)).

Now G(c, c′) and G(c′, c) are P -definable by stable embeddedness of P. Thus by the above equation, f_{c}^{−1}(G(c, c′)) is P c′-definable.

Let X(c) := D\f_{c}^{−1}(G(c, c_{0})). So X(c) is P c_{0}-definable. Note that each point of X = X(c) has multiplicity less than m over cc_{0}P. So by minimality of m (H3(iv)), Aut(X/cc_{0}P) has finite index in Aut(X/c_{0}P).

Since the graph of f_{c}|_{X} is contained in X×P, and is left invariant by Aut(X/cc_{0}P), it has finitely many conjugates over c_{0}P. It remains to show that f_{c}|_{D\X} also has finitely many conjugates over c_{0}P. In fact, if c′ is conjugate to c over P c_{0} then f_{c}|_{D\X} = f_{c′}|_{D\X}. For let d ∈ D \ X. Then f_{c}(d) ∈ G(c, c_{0}). So a := f_{c}(d) ∈ P_{1}, and for some a′ ∈ P_{1}, f_{c}^{−1}(a) = f_{c_{0}}^{−1}(a′). Thus f_{c′}^{−1}(a) = f_{c_{0}}^{−1}(a′). So d ∈ f_{c′}^{−1}(a); and f_{c′}(d) = a = f_{c}(d). □

Proof of Theorem 1.3. Obtain first C as in Lemma 3.4 and the remarks before it. By Lemma 3.6, C ⊂ acl(P c) for c ∈ C. Since Aut(D/P c) does not have finite index in Aut(D/P), we cannot have c ∈ acl(P).

Let C̄ be the quotient of C by an equivalence relation τ with finite classes, as in Corollary 2.7 above, so that C̄ ⊂ dcl(P F) for some finite F ⊂ C̄. Since C ⊄ acl(P), also C̄ ⊄ acl(P). So Aut(C̄/P) is infinite. Now let d̄ be an enumeration of F, and C′ := tp(d̄/P). Then C′ satisfies the assumptions of Lemma 2.8, and the result follows from that lemma. □

Remark 3.7 The proof of Theorem 1.3 shows that Aut(DC′/P) has a profinite normal subgroup, namely Aut(D/P C′), such that the quotient group is isomorphic to a Π^{1}-interpretable group. For Aut(D/P C′) is closed with all orbits finite, so profinite. The restriction homomorphism τ : Aut(DC′/P) → Aut(C′/P) is surjective (this uses homogeneity, and the fact that C′ := dcl(P c) for any c ∈ C′). Since σ has kernel Aut(D/P C′), the Π^{1}-interpretable group Aut(C′/P) is isomorphic to Aut(DC′/P)/ Aut(D/P C′).

4 Further Observations

The original motivation for this paper lay in the notion of relative categoricity [6], and we recall the setting of that paper. There are countable first order languages L^{−} ⊂ L, with a unary predicate P ∈ L \ L^{−}. We consider L-theories T such that if M ⊧ T then the reduct of P (M) to L^{−} is an infinite L^{−}-structure. We say that T is relatively ω-categorical if for any models M, M′ of T with P (M) = P (M′), both countable, there is an isomorphism M → M′ over P (M). If T is relatively ωcategorical, then it is reduced; that is, for each ℓ, and every M ⊧ T, every subset of P (M)^{ℓ} which is 0-definable in the L-structure M is 0-definable in the L^{−}-structure P (M).

It is easy to see that if T is reduced and M is algebraic over P (M) in a uniform way (that is, via finitely many formulas) then T is relatively ω-categorical. Much of the work in [6] concerned conditions under which the converse holds (for reduced theories T). An example where the converse fails is the group (Z/4Z)^{ω}, with P picking out the socle. More generally, by Theorem 6.1 of [6], if N is a countable L^{−}- structure in which there is an infinite interpretable group, then there is a language L^{∗} ⊃ L^{−} with unary P ∈ L^{∗} \ L^{−}, and a relatively ω-categorical L^{∗}-structure M such that M ⊄ acl(P (M)), and such that the reduct of P (M) to L^{−} is isomorphic to N. It was suggested in [6] that if M is relatively ω-categorical but not algebraic over P (M), then relative ω-categoricity must arise in something like this way; that is, that an infinite group is interpretable in P (M). This follows immediately from Theorem 1.3.

Corollary 4.1 If T is relatively ω-categorical over P, and for some countable M ⊧ T, M ⊄ acl(P (M)), then P (M) interprets an infinite group (in the language L^{−}).

Proof. By Section 3 of [6], H1 and H2+ hold, and by assumption, H2* fails. Now apply Theorem 1.3 (to some model satisfying Convention 1.2). □

Corollary 4.2 Assume T is ω-categorical over a language with a unary predicate P, and satisfies H1, H2, but not H2*. Then there is an infinite group interpretable in the induced structure on P.

Proof. By Theorem 1.3 (applied to a sufficiently saturated model), it suffices to check that if T is ω-categorical then H2 implies H2+. Let C be a complete type over P lying in a 0-definable set C′. For each m there is a 0-definable equivalence relation E_{m} on C′, where E_{m}xy hold if for all ā ∈ P^{m}, tp(āx) = tp(āy). By ωcategoricity, there is m_{0} ∈ ω such that ⋂_{i∈ω} E_{i} = E_{m_{0}}. Then C is an E_{m_{0}}-class. By H2, C is definable over P, as required for H2+. □

Our final result describes a situation which is realised, for example, by the ‘affine duality’ phenomemon of quasi-finite structures (Chapter 4 of [4]).

Proposition 4.3 Assume that M satisfies Convention 1.2. Suppose also that f : D → P is a 0-definable map with finite fibres, and that P is stably embedded, but D is not. Then there exists an infinite torsion group, Π^{1}- interpretable over M.

Proof. Since Aut(D/P) is a closed permutation group with all orbits finite, it is a profinite group with the natural topology.

Claim. For some tuple c, Aut(D/P c) has infinite index in Aut(D/P).

Proof of Claim. Suppose this is false, and let c be a tuple in M. Then Aut(D/P c) is a closed subgroup of finite index in Aut(D/P), so is open, and hence there is finite F ⊂ D with Aut(D/P F) ≤ Aut(D/P c). By adding to F a countable subset of P, we may also ensure that Aut(P/F) = Aut(P/F c), since P is stably embedded. It follows that Aut(P D/F c) = Aut(P D/F). (For let g ∈ Aut(P D/F); then there is h ∈ Aut(P/F c) agreeing with g on P; now h extends to h′ ∈ Aut(P D/F c) and now gh^{′−1} induces on D an element of Aut(D/P F c), so g is elementary over F c.) Thus every c-definable subset of P D is invariant under Aut(M/F), and is therefore F - definable. Hence P D is stably embedded. It follows that D also is stably embedded, as P D ⊂ dcl(D). This is a contradiction.

Now choose c as in the claim, and put C := tp(c/P). Adjusting C if necessary, we obtain m as in Lemma 3.4 with H3 (i)–(iv) holding, and we may suppose H3(v) also holds. We apply Lemma 3.6, and the proof of Theorem 1.3. There is an Aut(C/P)-invariant equivalence relation τ on C with finite classes provided by Lemma 2.7, and an orbit C′ of tuples from C̄ := C/τ, such that Aut(C′/P) is infinite and Π^{1}-interpretable.

It remains to check that Aut(C′/P) is a torsion group. Let H be the image of Aut(DCC̄C′/P) in Aut(C̄/P), and let h ∈ H. There is g ∈ Aut(DCC̄C′/P) extending h. Now for some finite m (equal say to t!, where t is the least common multiple of the sizes of the fibres of f), g^{m} fixes D pointwise. Since elements of C are canonical parameters for functions D → P^{eq}, g^{m} also fixes C pointwise, so g^{m} = 1. Since H is dense in Aut(C′/P), the latter group also has exponent m. □

References

[1] J. T. Baldwin, A. H. Lachlan, ‘On strongly minimal sets’, J. Symb. Logic 36 (1971), 79–96.

[2] G. Bergman, H. W. Lenstra, ‘Subgroups close to normal subgroups’, J. Alg. 127 (1989), 80–97.

[3] Z. Chatzidakis, E. Hrushovski, ‘Model theory of difference fields’, Trans. Amer. Math. Soc. 351 (1999), 2997-3051.

[4] G. Cherlin, E. Hrushovski, ‘Large finite structures with few 4-types’, preprint.

[5] G. Schlichting, ‘Operationen mit periodischen Stabilisatoren’, Archiv der Mathematik 34 (1980), 97–99.

[6] W. A. Hodges, I. M. Hodkinson, H. D. Macpherson, ‘Omega-categoricity, relative categoricity and coordinatisation’, Ann. Pure Appl. Logic 46 (1990), 169– 199.

[7] E. Hrushovski, Contributions to stable model theory, PhD thesis, Berkeley, 1986.

[8] A. Pillay, S. Shelah, ‘Classification theory over a predicate I’, Notre Dame J. Formal Logic 26 (1985), 361–376.

[9] Z. Shami, F. Wagner, ‘On the binding group in simple theories’, preprint.

[10] S. Shelah, ‘Remark to ‘Local definability theory’ of Reyes’, Ann. Math. Logic 2 (1970), 441–447.