Extending partial automorphisms and the profinite topology on free groups

Bernhard Herwig  Daniel Lascar

15/03/98

Abstract A class of structures C is said to have the extension property for partial automorphisms (EPPA) if, whenever C_{1} and C_{2} are structures in C, C_{1} finite, C_{1} ⊆ C_{2}, and p_{1}, p_{2}, …, p_{n} are partial automorphisms of C_{1} extending to automorphisms of C_{2}, then there exist a finite structure C_{3} in C and automorphisms α_{1}, α_{2}, …, α_{n} of C_{3} extending the p_{i}. We will prove that some classes of structures have the EPPA and show the equivalence of these kinds of results with problems related with the profinite topology on free groups. In particular, we will give a generalisation of the theorem, due to Ribes and Zalesskiì stating that a finite product of finitely generated subgroups is closed for this topology.

1 Introduction

In this paper, we will consider and relate two kinds of results. We begin by giving the basic definitions that are needed to understand these relations.

On the one hand, there will be the theorems concerning the so called “profinite topology” on the free groups. Given a group G, the profinite topology on G is the topology for which a basis of open subsets is

{gH; g ∈ G and H is a subgroup of G of finite index}

Let us recall a classical result, due to M. Hall [4]:

Theorem 1.1 Let P be a finite set, and F (P) the free group generated by P. Then every finitely generated subgroup of F (P) is closed for the profinite topology.

This result can be rephrased as follows: let H be a finitely generated subgroup of F (P). Then

H = ⋂ {K ; K is a subgroup of finite index of F (P) and H ⊆ K} .

More recently, Ribes and Zalesskiì ([9]) proved :

Theorem 1.2 Let H_{1}, H_{2}, …, H_{n} be finitely generated subgroups of F (P). Then

H_{1}H_{2} … H_{n} = {h_{1}h_{2} … h_{n} ; h_{1} ∈ H_{1}, h_{2} ∈ H_{2}, …, h_{n} ∈ H_{n}}

is closed for the profinite topology.

11991 Mathematics Subject Classification. Primary 20E05, 05C25; Secondary 05C20, 08A35 Key words and phrases: Partial isomorphisms, profinite topology, finite structures, extension problem

On the other hand, we will consider some combinatorial results concerning the extension of partial automorphisms.

Definition 1.3 Let M, M′ be two structures in a given finite relational language L. A partial isomorphism from M into M′ is an isomorphism of a substructure of M onto a substructure of M′. We will denote by Part(M, M′) the set of partial isomorphisms from M into M′. A partial automorphism of M is a partial isomorphism from M into M.

Let C be a class of L-structures (containing both finite and infinite structures), M_{0} a finite structure in C and P a set of partial automorphisms of M_{0}. We consider the following problem (the (M_{0}, P, C)-extension problem): find a structure M_{1} ∈ C, which is an extension of the structure M_{0} and for each p ∈ P an automorphism α_{p} of M_{1} extending p. We say (M_{1}, α_{p})_{p∈P} is a solution of our problem, and we will say it is finite if M_{1} is.

We say that C has the extension property for partial automorphisms (EPPA for short) if for all finite M_{0} and P ⊆ Part(M_{0}, M_{0}), if the (M_{0}, P, C)-extension problem has a solution, then it has a finite solution.

An example of this family of results is the following theorem of Hrushovski ([8]):

Theorem 1.4 Let Γ_{0} be a finite graph. Then there exists a finite graph Γ_{1} extending Γ_{0} and such that every partial automorphism of Γ_{0} can be extended to an automorphism of Γ_{1}.

(Here, a graph means undirected loop free graph.)

Hrushovski’s theorem just states that the class of all graphs has the EPPA (note that in the case where C is the class of all graphs, every extension problem has a solution, because every finite graph is embeddable in the random graph, which is homogeneous).

Herwig has generalised this result to the class of structures of a given finite relational language ([5]) and various other classes of graphs (see [6]). This kind of result is of importance for proving the small index property for the automorphism group of the corresponding generic structures (see [7] or [6] for more about this question).

This paper is organised as follows: in the next section, we show how to use the properties of the profinite topology to prove some EPPA-results. In particular, we give a proof of Hrushovski’s theorem (Theorem 1.4) from the theorem of Ribes and Zalesskiì (Theorem 1.2). This proof is not simpler than the original one. It is only given here as an illustration.

Next, we go in the other direction. First, starting from the fact that the class of n-partitioned cycle-free graphs has the EPPA, we show the Ribes-Zalesskiì theorem. Then, using the most general extension result that we have been able to prove (Theorem 3.2), we prove a property of the profinite topology (Theorem 3.3) generalising the theorem of Ribes and Zalesskiì.

The next two sections are devoted to proving extension results. First, we give a proof of the EPPA for the class of graphs (that is the theorem of Hrushovski). This proof has the advantage of being short and of admitting natural generalisation to the class of all structures in a given finite relational language. This last result, which had already been obtained by the first author (see [5]), will be used later. We will also give a proof of the EPPA for the class of n-partitioned cycle-free graphs. This proof was not necessary, since it is just a particular case of Theorem 3.2, but we included it here because we think that some of our readers (if any) will be mainly interested in an alternative simple proof of the theorem of Ribes and Zalesskiì, and we wanted to spare them the complication of the proof of Theorem 3.2. Section 5, almost half of the paper, is devoted to this proof.

We will be dealing, throughout the paper with structures in some relational language. We assume that the reader understands these words, and also the notation M ⊧ Ra_{1}a_{2} … a_{n} (where M is a structure in a language L, R is a symbol of arity n in the language L and a_{1}, a_{2}, …, a_{n} are elements in M). If L′ is a language included in L and M an L-structure, M_{|L′} is the restriction of M to L′, that is the L′-structure obtained from M by just forgetting the interpretation of the symbols of L which are not in L′. We say M_{1} is an extension of M_{0} (or M_{0} is a substructure of M_{1}) if the underlying set of M_{0} is contained in that of M_{1} and for every symbol R in L and a_{1}, a_{2}, … a_{n} ∈ M_{0}: M_{0} ⊧ Ra_{1}a_{2} … a_{n} ⇔ M_{1} ⊧ Ra_{1}a_{2} … a_{n}.

We will use the same letter, M, for example, for a structure and its underlying set. The sign · will denote the product operation in whatever group we are manipulating (but it will be often omitted, depending on the context), and ∘ will denote the composition of maps (which may be partial).

If I is a set which is totally ordered by the relation <, we may define the lexicographical order on the set I^{<ω} of finite sequences of elements of I: given two sequences a = (i_{1}, i_{2}, …, i_{n}) and b = (j_{1}, j_{2}, …, j_{m}), then a < b if and only if one of the following cases occurs

• a is a proper initial segment of b;

• a is not an initial segment of b, and if k is the smallest integer such that i_{k} ≠ j_{k}, then i_{k} < j_{k}.

The second author wishes to thank G. Sabbagh, J.E Pin and Pascal Weil for helpful discussions.

2 From the profinite topology to the extension properties

2.1 A sophisticated proof of a theorem of Hrushovski

We will give a proof (using Theorem 1.2) of the theorem of Hrushovski (Theorem 1.4).

Let Γ_{0} be a finite graph and let P be the (finite) semi-group of partial automorphisms of Γ_{0}. Let us agree that, when we write p(a) = p′(a′) or p(a) ≠ p′(a′) (where p, p′ are elements of P and a, a′ are elements of Γ_{0}) this means that both p(a) and p′(a′) are defined and of course the equality or the inequality holds.

Choose an element a_{0} of Γ_{0} and let H_{0} be the subgroup of F (P) generated by X_{0} where

X_{0} = {p^{−1} · p′ ; p, p′ ∈ P, p(a_{0}) = p′(a_{0})} ∪ {p_{3}^{−1} · p_{1} · p_{2} ; p_{1}, p_{2}, p_{3} ∈ P,
p_{1} ∘ p_{2}(a_{0}) = p_{3}(a_{0})}

(note that X_{0} is finite). Let H be any subgroup of F (P) such that

H_{0} ⊆ H  (1)

For each a ∈ Γ_{0}, there is a partial automorphism p ∈ P such that p(a_{0}) = a, and if p′ ∈ P is such that p′(a_{0}) = a, then p · H = p′ · H; so we may define a map ϕ from Γ_{0} into F (P)/H by : for all a ∈ Γ_{0}, ϕ(a) = p · H where p is any element of P such that p(a_{0}) = a.

If moreover we demand that

H ∩ X_{1} = ∅  (2)

where :

X_{1} = {p^{−1} · p′ ; p, p′ ∈ A, p(a_{0}) ≠ p′(a_{0})}

then this map ϕ is injective.

We assume that this condition is satisfied. For each g ∈ F (P), define the permutation g̃ of F (P)/H by : for all x ∈ F (P), g̃(xH) = gxH. We remark that, for every p ∈ P and a ∈ Γ_{0}, if p(a) is defined, then ϕ(p(a)) = p̃(ϕ(a)): indeed for some q ∈ P, we have a = q(a_{0}) and p(a) = p ∘ q(a_{0}). Let p′ = p ∘ q. Thus ϕ(p(a)) = p′H. On the other hand, ϕ(a) = qH, and p̃(ϕ(a)) = pqH. But p′H = pqH, since p^{′−1}pq ∈ H, by (1).

We will consider Γ_{0} as a subset of F (P)/H by identifying each a ∈ Γ_{0} with ϕ(a). Thus, for all p ∈ P, p̃ extends p. It is also clear that the map g ⟼ g̃ is a group homomorphism from F (P) into the group of permutations of F (P)/H.

We want to endow F (P)/H with a graph structure extending Γ_{0} and in such a way that for every g ∈ F (P), g̃ is a an automorphism of this graph. We do that by adding the minimal number of edges: given α and α′ in F (P)/H, we decide that F (P)/H ⊧ Rαα′ if and only if there exist a, a′ ∈ Γ_{0} and g ∈ F (P) such that Γ_{0} ⊧ Raa′ and g̃(a) = α and g̃(a′) = α′. We denote by Γ_{1} the graph that we get this way.

So, by construction, every g ∈ F (P) induces an automorphism of Γ_{1}. What is not clear is whether Γ_{1} is an extension of Γ_{0}. We have to be careful not to add an edge between two elements of Γ_{0}. This will be true if and only the following condition is satisfied :

• For all p_{0}, p_{1}, p_{2}, p_{3} ∈ P such that Γ_{0} ⊧ R p_{0}(a_{0}) p_{1}(a_{0}) ∧ ¬R p_{2}(a_{0}) p_{3}(a_{0}), there is no g ∈ F (P) such that gp_{0}H = p_{2}H and gp_{1}H = p_{3}H.

A straightforward calculation shows that this condition is equivalent to :

For all p_{0}, p_{1}, p_{2}, p_{3} ∈ P if Γ_{0} ⊧ R p_{0}(a_{0}) p_{1}(a_{0}) ∧ ¬R p_{2}(a_{0}) p_{3}(a_{0}), then  (3)
p_{0}p_{2}^{−1}p_{3}p_{1}^{−1} ∉ p_{0}Hp_{0}^{−1} p_{1}Hp_{1}^{−1}

Let us sum up : for every subgroup H of F (P) satisfying the conditions (1), (2) and (3), we have an extension Γ_{1} of Γ_{0} whose universe is F (P)/H such that every partial automorphism of Γ_{0} extends to an automorphism of Γ_{1}. So the problem is to find such a subgroup K of finite index.

We remark that if we drop the assumption that K is of finite index, then we can solve the problem. Indeed, we know that there exists a graph Γ (possibly infinite) extending Γ_{0} and for all p ∈ P an automorphism p̃ of Γ extending p (for example the random graph). Let η be the homomorphism of F (P) into Aut(Γ) such that η(p) = p̃ for all p ∈ P, and write h̃ instead of η(h). Reversing all that we have just said, we see that, if we set

H = {h ∈ F (P) ; h̃(a_{0}) = a_{0}}

then H satisfies the conditions (1), (2) and (3). Thus H_{0} also satisfies the conditions (1), (2) and (3).

Since a finite intersection of subgroups of finite index is of finite index, it suffices to prove the following facts :

• For all α ∈ X_{1}, there exists a subgroup K of F (P) of finite index, containing H_{0}, but not containing α;

This is exactly the theorem of M. Hall (Theorem 1.1).

• For all p_{0}, p_{1}, p_{2}, p_{3} ∈ P such that Γ_{0} ⊧ R p_{0}(a_{0}) p_{1}(a_{0}) ∧ ¬R p_{2}(a_{0}) p_{3}(a_{0}), there exists a subgroup K of F (P) of finite index containing H_{0} and such that p_{0}p_{2}^{−1}p_{3}p_{1}^{−1} ∉ p_{0}Kp_{0}^{−1} · p_{1}Kp_{1}^{−1}.

Here we apply the Theorem 1.2 : since p_{0}H_{0}p_{0}^{−1}p_{1}H_{0}p_{1}^{−1} is closed for the profinite topology and does not contains p_{0}p_{2}^{−1}p_{3}p_{1}^{−1}, there exist a subgroup N of F (P) of finite index such that

p_{0}p_{2}^{−1}p_{3}p_{1}^{−1} ∉ (p_{0}H_{0}p_{0}^{−1}p_{1}H_{0}p_{1}^{−1})N.

We may moreover choose N to be normal in F (P). Then K = H_{0} · N is a subgroup of F (P) of finite index containing H_{0} and (p_{0}H_{0}p_{0}^{−1}p_{1}H_{0}p_{1}^{−1})N = p_{0}Kp_{0}^{−1} p_{1}Kp_{1}^{−1}, so p_{0}p_{2}^{−1}p_{3}p_{1}^{−1} ∉ p_{0}Kp_{0}^{−1} p_{1}Kp_{1}^{−1}.

♡

2.2 Generalisation

In fact the same argument can be used to prove many other results of the same kind. For example, let us prove that the class of triangle free graphs has the EPPA. We start from a finite triangle free graph. We construct a graph Γ_{1} extending Γ_{0} as above, using a subgroup K of F (P) of finite index, and, as above, F (P) acts on Γ_{1}. We demand in addition that Γ_{1} is triangle free. For this, it is sufficient and necessary that the following condition is satisfied :

• For all a_{1}, a′_{2}, a_{2}, a′_{3}, a_{3}, a′_{1} ∈ Γ_{0} if Γ_{0} ⊧ Ra_{1}a′_{2} ∧ Ra_{2}a′_{3} ∧ Ra_{3}a′_{1}, then, there is no h_{1}, h_{2}, h_{3} ∈ F (P) such that h̃_{3}(a_{1}) = h̃_{2}(a′_{1}), h̃_{1}(a_{2}) = h̃_{3}(a′_{2}), h̃_{2}(a_{3}) = h̃_{1}(a′_{3}).

For i = 1, 2, 3, let p_{i} and p′_{i} be elements of P such that a_{i} = p_{i}(a_{0}) and a′_{i} = p′_{i}(a_{0}). A calculation shows that the above condition is equivalent to

• For all p_{1}, p′_{2}, p_{2}, p′_{3}, p_{3}, p′_{1} ∈ P if Γ_{0} ⊧ R p_{1}(a_{0}) p′_{2}(a_{0})∧R p_{2}(a_{0}) p′_{3}(a_{0})∧R p_{3}(a_{0}) p′_{1}(a_{0}), then 1 ∉ p′_{1}Kp_{1}^{−1}p′_{2}Kp_{2}^{−1} p′_{3}Kp_{3}^{−1}.

We finish the proof as above, using the Theorem 1.2.

The case of the K_{4}-free graphs seems to be more difficult and, in fact, we have not been able to deduce it from the theorem of Ribes and Zalesskiì. But it has been proved by Herwig ([6]), and, as a matter of fact, is just a particular case of Theorem 3.2.

Let us phrase the above arguments in a systematic way: let X be finite set. We consider the set

Part(X) = {p; p is an injective map from a subset of X into X}

with its natural monoid structure. Let P be a subset of Part(X). Consider the set Σ of words on the alphabet P ∪ P^{−1} (that is the free monoid generated by P ∪ P^{−1}). To a given word w in Σ we may naturally associate a partial automorphism of Y. It is ς(w), where ς is the homomorphism from Σ into the monoid of partial automorphisms of Y defined by: for p ∈ P ∪ P^{−1}, ς(p) = p. Let (X_{i}; i = 1, 2, … n) be the partition of X into orbits relatively to P (that is two elements x and y of X lie in the same X_{i} if and only if there exists w ∈ Σ such that ς(w)(x) = y) and for each i = 1, 2, … n, choose an element x_{i} in X_{i}. Furthermore choose for every x ∈ X_{i} a word w_{x} ∈ Σ such that x = ς(w_{x})(x_{i}). Then there is a correspondence between

• the n-tuples (H_{1}, H_{2}, …, H_{n}) of subgroups of F (P) such that for all p in P and i = 1, 2, …, n:

(1) w_{y}^{−1} · p · w_{x} ∈ H_{i} if y, x ∈ X_{i} and p(x) = y,

(2) w_{y}^{−1} · w_{x} ∉ H_{i} if x, y ∈ X_{i}, x ≠ y.

on one hand, and

• the tuples (Y, (p̃; p ∈ P)), where X ⊆ Y, and, for all p ∈ P, p̃ is a permutation of Y extending p. on the other hand.

Indeed, let (H_{1}, H_{2}, …, H_{n}) be a sequence subgroups of F (P) satisfying the conditions (1) and (2). Let Y be the disjoint union of the sets F (P)/H_{i}. If x ∈ X_{i}, set ϕ(x) = w_{x}H_{i}. Hereby we consider w_{x} in a natural way as an element of F (P). Condition (2) insures that the map ϕ is injective. We will identify x with ϕ(x), so that X will be viewed as a subset of Y.

For each p ∈ P, the left multiplication defines a permutation p̃ on Y which extends by condition (1) the map p.

In the reverse direction, assume that Y is a set including X, and for each p ∈ A, p̃ a permutation of Y extending p. Let φ be the group homomorphism from F (P) into P erm(Y), the group of permutation of Y, defined by: for all p ∈ P, φ(p) = p̃. Set, for i = 1, 2, …, n,

H_{i} = {h ∈ F (P); φ(h)(x_{i}) = x_{i}}

Then, the sequence (H_{1}, H_{2}, …, H_{n}) satisfies the conditions (1) and (2).

Now assume that X is the universe of a structure, also denoted X, in some finite relational language L. Assume moreover that the maps p in P are partial automorphisms of X. We want to find the solutions to the following problem (subsequently referred to as P): find an L-structure Y extending X and, for each p ∈ P, an automorphism p̃ of Y extending p.

Suppose that (Y, (p̃; p ∈ P)) is such a solution of P. Let again φ be the homomorphism from F (P) into Aut(Y), which is defined by: φ(p) = p̃, and, for h ∈ F (P), write h̃ instead of φ(h). Now, if R is a symbol of the language L of arity k, and if y_{1}, y_{2}, …, y_{k} are elements in Y such that there exist x_{1}, x_{2}, …, x_{k} in X and h ∈ F (P) such that, for all j = 1, 2, …, k, h̃(x_{j}) = y_{j} and X ⊧ Rx_{1}x_{2} … x_{k}, then necessarily, Y ⊧ Ry_{1}y_{2} … y_{k}. This proves that the following condition is satisfied:

If R is a symbol of the language L of arity k, if z_{1}, z_{2}, …, z_{k}, t_{1}, t_{2}, …, t_{k} are elements in X and if

X ⊧ Rz_{1}z_{2} … z_{k} ∧ ¬Rt_{1}t_{2} … t_{k}

then, there is no h ∈ F (P) such that, for all i = 1, 2, …, k, h̃(z_{i}) = t_{i}.

Setting H_{i} = {h ∈ F (P) ; h̃(x_{i}) = x_{i}} as above, an easy computation shows that this condition is equivalent to

(3) If R is a symbol of the language L of arity k, if i_{1}, i_{2}, …, i_{k} are elements of {1, 2, …, n}, if x_{1}, x′_{1} ∈ X_{i_{1}}, x_{2}, x′_{2} ∈ X_{i_{2}} …, x_{k}, x′_{k} ∈ X_{i_{k}} and if X ⊧ Rx_{1}x_{2} … x_{k} ∧ ¬Rx′_{1}x′_{2} … x′_{k} then there is no h ∈ F (P) such that, for all j = 1, 2, …, k, h · w_{x_{j}} ≡ w_{x′_{j}} mod(H_{i_{j}})

This condition (3) (taking for granted that the conditions (1) and (2) are satisfied) is sufficient: it suffices to define on the disjoint union, say Y, of the sets F (P)/H_{i} considered as an extension of X, the L-structure by setting: for all R, symbol of the language L of arity k, and for all y_{1}, y_{2}, …, y_{k} in Y,

Y ⊧ Ry_{1}y_{2} … y_{k} if and only if there exist x_{1}, x_{2}, …, x_{k} in X and h ∈ F (P)

such that, for all j = 1, 2, …, k, h̃(x_{j}) = y_{j} and X ⊧ Rx_{1}x_{2} … x_{k}

We remark that if a sequence of subgroups (H_{1}, H_{2}, …, H_{n}) satisfies conditions (2) and (3) and if for all i = 1, 2, …, n, K_{i} is a subgroup of H_{i}, then the sequence (K_{1}, K_{2}, …, K_{n}) satisfies also (2) and (3). We will express this fact by saying that (2) and (3) are negative conditions.

The correspondence that we have been speaking about is certainly not one to one in general. There may be several solutions corresponding to a given sequence (H_{1}, H_{2}, …, H_{n}). The solution that we have constructed enjoys the following property of “slimness”:

Definition 2.1 Let X be a finite L-structure, P a set of partial automorphism of X. A solution (Y, (p̃; p ∈ P)) of the problem P is slim if: 1) for all y ∈ Y, there exist x ∈ X and h in F (P) such that y = h̃(x); 2) for all R, symbol of the language L of arity k, and y_{1}, y_{2}, …, y_{k} elements in Y, Y ⊧ Ry_{1}y_{2} … y_{k} if and only if there exist x_{1}, x_{2}, …, x_{k} in X and h ∈ F (P) such that X ⊧ Rx_{1}x_{2} … x_{k} and y_{i} = h̃(x_{i}) for all i = 1, 2, … k.

It is easy to get a slim solution from any solution: if (Y, (p̃; p ∈ P)) is a solution, throw away from Y the elements which are not image by an element of the group generated by {p̃; p ∈ P } of an element of X, and do the same for links. There is one further condition our solutions satisfy. Namely for x, y ∈ X, if there exists h ∈ F (P) such that h̃(x) = y then x and y are in the same orbit relative to P. If we restrict ourself to slim solutions satisfying this further condition, we do get a one to one correspondence.

We will need solutions which satisfy a stronger condition. Consider again the free monoid Σ over P ∪ P^{−1} and the homomorphism ς from Σ to Part(X). We may consider every w ∈ Σ as an element of F (P) and we write again w̃ for φ(w), where φ is the group homomorphism from F (P) into Aut(Y) defined by: for all p ∈ P, φ(p) = p̃. Of course w̃ extends ς(w).

Definition 2.2 The solution (Y, (p̃; p ∈ P)) is special if it is slim and, for all t_{1}, t_{2} in X and h ∈ F (P), if h̃(t_{1}) = t_{2}, then there exists a word w ∈ Σ such that ς(w)(t_{1}) = t_{2} and w̃ = h̃.

We show now how to get a special solution from any solution. Let (Y, (p̃; p ∈ P)) a solution. Set:

• H_{i} = {h ∈ F (P); φ(h)(x_{i}) = x_{i}};

• K the kernel of φ;

• L_{i} the subgroup of F (P) generated by

{w_{y}^{−1} · p · w_{x} ; x, y ∈ X_{i} and p(x) = y};

• K_{i} = K · L_{i} (it is also the subgroup of F (P) generated by K ∪ L_{i}).

First of all, we see that the sequence (K_{1}, K_{2}, …, K_{n}) satisfies the conditions (1) to (3). Condition (1) is insured by the fact that, for all i = 1, 2, … n, L_{i} ⊂ K_{i}. Conditions (2) and (3) are negative conditions and are satisfied by (H_{1}, H_{2}, …, H_{n}). Moreover, for all i = 1, 2, … n, K_{i} ⊂ H_{i}. So, (K_{1}, K_{2}, …, K_{n}) satisfies the conditions (2) to (3).

It remains to see that the solution corresponding to (K_{1}, K_{2}, …, K_{n}) is special. So, let t_{1}, t_{2} in X and h ∈ F (P) such that h̃(t_{1}) = t_{2}. This implies that t_{1} and t_{2} belong to the same set F (P)/K_{i}, say F (P)/K_{1}, and we have t_{1} = w_{t_{1}}x_{1} = w_{t_{1}}K_{1} and t_{2} = w_{t_{2}}x_{1} = w_{t_{2}}K_{1}. Thus, we have w_{t_{2}}^{−1}hw_{t_{1}} ∈ K_{1}, and there exist k ∈ K and ℓ ∈ L_{1} such that w_{t_{2}}^{−1}hw_{t_{1}} = kℓ. So, w_{t_{2}}^{−1}hw_{t_{1}}ℓ^{−1} ∈ K, and, since K is normal w_{t_{1}}ℓ^{−1}w_{t_{2}}^{−1}h ∈ K. Since ℓ ∈ L_{1}, it is the product of elements and inverses of the set {w_{y}^{−1}pw_{x} ; x, y ∈ X_{i} and p(x) = y}. So ℓ is equal to u for some word u ∈ Σ such that ς(u)(x_{1}) = x_{1}. Set w = w_{t_{2}}uw_{t_{1}}^{−1}. Then ς(w)(t_{1}) = t_{2} and w^{−1}h ∈ K and w̃ = h̃.

It is clear that, if we start from a finite solution Y, then the special solution constructed above is also finite (since, in this case K has finite index). So we have proved:

Proposition 2.3 If the problem P has a finite solution, then it has a finite special solution.

In fact, we have proved (and will use) more than that. We will want to solve the extension problem, not in the class C of all L-structures, but in a narrower class C_{1}. Everything will go through, provided that there we can find a condition, denote it by (*), which is such that:

• if the solution is in C_{1}, then the corresponding sequence (H_{1}, H_{2}, …, H_{n}) satisfies (*);

• if (H_{1}, H_{2}, …, H_{n}) satisfies (1) to (3) and (*), then the corresponding solution is in C_{1};

• (*) is a negative condition.

The classes of triangle free graphs and K_{4}-free graphs are typical examples of such classes.

It is easy to see that our special solution has the following further property: If the problem P has a finite solution (Y, (p̃; p ∈ P)), then there is a finite special solution (Z, (p^{∗}; p ∈ P)) and a weak homomorphism ρ : Z → Y such that for every a ∈ Z and p ∈ P ρ(p^{∗}(a)) = p̃(ρ(a)). For the definition of the notion of weak homomorphism see section 3.2; to define ρ use the equality ρ(hK_{i}) = φ(h)(x_{i}).

3 From the EPPA to the profinite topology

In this section, we will show how to use the theorem concerning the extension property for automorphisms (to be proved in the next sections) to prove theorems about the profinite topology on free groups.

3.1 A proof of the theorem of Ribes and Zalesskiì

Let L be the language containing n unary predicate symbols, U_{1}, U_{2},…, U_{n} and one binary predicate symbol, R. Let C the class of L-structures M where:

1. the universe is the disjoint union of the sets U_{i}^{M}, for i = 1, 2, …, n;

2. Rxy implies that, for some i = 1, 2, …, n − 1, U_{i}x ∧ U_{i+1}y or U_{n}x ∧ U_{1}y;

3. there are no x_{1}, x_{2}, …, x_{n} in M such that

M ⊧ Rx_{1}x_{2} ∧ Rx_{2}x_{3} ∧ … ∧ Rx_{n−1}x_{n} ∧ Rx_{n}x_{1}

The class C is called the class of cycle-free n-partitioned graphs.

Theorem 3.1 The class C has the extension property for partial automorphisms.

This theorem will be proved in the next section. We give a proof of the Ribes-Zalesskiì theorem from theorem 3.1 (using the techniques of the preceding section, one could also prove Theorem 3.1 from the theorem of Ribes and Zalesskiì).

Let H_{1}, H_{2}, …, H_{n} be finitely generated subgroups of F (P), and g an element of F (P) not belonging to H_{1} · H_{2} · . . . · H_{n}. Let M be the following structure, in the above described language: the universe of M is the disjoint union of the sets F (P)/H_{i}, for i = 1, 2, …, n; the interpretation of U_{i} is just F (P)/H_{i}; finally, for x and y in M, M ⊧ Rxy if and only if: either for some i = 1, 2, …, n − 1, x ∈ F (P)/H_{i}, y ∈ F (P)/H_{i+1}, and x ∩ y ≠ ∅ or x ∈ F (P)/H_{n}, y ∈ F (P)/H_{1}, and xg^{−1} ∩ y ≠ ∅.

The fact that g ∉ H_{1}H_{2} … H_{n}, implies that M is in C. Indeed, assume, toward a contradiction, that we can find h_{1}, h_{2}, …, h_{n} in F (P) such that, for all i = 1, 2, …, n − 1 M ⊧ R h_{i}H_{i} h_{i+1}H_{i+1} and M ⊧ R h_{n}H_{n} h_{1}H_{1}. This implies that h_{1}H_{1} ∩ h_{2}H_{2} ≠ ∅, which means that h_{1}^{−1}h_{2} ∈ H_{1}H_{2}. Similarly, we see that h_{2}^{−1}h_{3} ∈ H_{2}H_{3}, …, h_{n−1}^{−1}h_{n} ∈ H_{n−1}H_{n}. At last, M ⊧ R h_{n}H_{n} h_{1}H_{1} implies g ∈ H_{1}h_{1}^{−1}h_{n}H_{n}. We deduce that g ∈ H_{1}H_{2} … H_{n}, a contradiction.

Let X_{0} be a finite subset of F (P) which contains g, a set of generators of H_{i}, for i = 1, 2, …, n, and – assuming that these elements have been written as words of P ∪ P^{−1} – all final segments of these words. Let M_{0} be the finite substructure of M whose universe is

{xH_{i} ; x ∈ X_{0}, i = 1, 2, …, n}.

For each p ∈ P, let p̄ be the partial automorphism of M_{0} defined by: for all x ∈ M_{0}, if px ∈ M_{0}, then p̄(x) = px. If px ∉ M_{0}, then p̄(x) is not defined. These partial automorphisms can obviously be extended to automorphisms of M, so by Theorem 3.1, we know that there exist a finite extension M_{1} of M_{0} in C_{0} and automorphisms p̃ of M_{1} extending p̄. Let φ be the homomorphism from F (P) into Aut(M_{1}) such that φ(p) = p̃. We remark that, if h is one of the generators of one of the H_{i}, then φ(h)H_{i} = hH_{i} (thanks to our precaution to have included in M_{1} all the final segments of h). Similarly, φ(g)H_{i} = gH_{i}. Set, for i = 1, 2, …, n, K_{i} = {h ∈ F (P) ; φ(h)(H_{i}) = H_{i}}. Obviously, for i = 1, 2, …, n, the subgroup K_{i} has a finite index in F (P), and we have already pointed out that it contains H_{i}.

We conclude by showing that g ∉ K_{1}K_{2} … K_{n}. Assume, toward a contradiction, that g = k_{1}k_{2} … k_{n}. Set x_{1} = H_{1}, x_{2} = φ(k_{1})(H_{2}), …, x_{n} = φ(k_{1}k_{2} … k_{n−1})(H_{n}). Obviously, M_{1} ⊧ R H_{1} H_{2}, thus, since φ(k_{1}) is an automorphism of M_{1}, M_{1} ⊧ Rx_{1}x_{2}. We see in a similar way that, for i = 1, 2, …, n − 1, M_{1} ⊧ Rx_{i}x_{i+1}. Finally, from the fact that M_{1} ⊧ R gH_{n} H_{1}, we deduce that M_{1} ⊧ R φ(g)(H_{n}) H_{1}, that is M_{1} ⊧ Rx_{n}x_{1}. Thus, M_{1} is not cycle-free, a contradiction.

♡

3.2 Statement of the main combinatorial theorem

Before going further, we will need to set up some more notation. In this subsection we will consider a finite relational language L.

If M and M′ are L-structures, a weak homomorphism from M to M′ is a map h from M to M′ which is such that: if n is an integer, R an n-ary predicate symbol of L and a_{1}, a_{2}, …, a_{n} are elements of M such that M ⊧ Ra_{1}a_{2} … a_{n}, then M′ ⊧ Rh(a_{1})h(a_{2}) … h(a_{n}). If A is a substructure of both M and M′, a weak A-homomorphism is a weak homomorphism which leaves the elements of A fixed.

To denote that h is a weak homomorphism from M into M′, we write: h : M ⟶_{w} M′. To denote that it is a weak A-homomorphism, we write: h : M ⟶_{w,A} M′.

If M is a structure, a link of M is a tuple (R, a_{1}, a_{2}, …, a_{n}) where R is a n-ary predicate symbol of the language L, a_{1}, a_{2}, …, a_{n} are elements of M and M ⊧ Ra_{1}a_{2} … a_{n}. We say that an element a belongs to or is contained in a link (R, a_{1}, a_{2}, …, a_{n}) if a is one of the a_{i}.

If M is a L-structure and T a set of L-structures, we say that M is T -free if there is no structure T ∈ T and weak homomorphism h : T ⟶_{w} M .

We can now state a general combinatorial theorem, that will be proved in section 5.

Theorem 3.2 Let L be a finite relational language and T a finite set of finite L-structures. Then the class of T -free L-structures has the EPPA.

3.3 Back to the free groups

A natural question is: is there a generalisation of the theorem of Ribes-Zalesskiì that can be proved using Theorem 3.2 or even which is “equivalent” to it? The answer is yes for both questions, and that is what we are going to expose now.

If H is a subgroup of F (P) and x and y are two elements of F (P), we write x ≡ y mod H for xH = yH.

Let n ∈ ω and X be a finite set (the set of unknowns). A left-system is a finite set of equations of the form

x ≡_{i} y · g where i ∈ {1, 2, … n}, x, y ∈ X and g ∈ F (P)

or of the form

x ≡_{i} g where i ∈ {1, 2, … n}, x ∈ X and g ∈ F (P)

Let H = (H_{i}, H_{2}, …, H_{n}) be a sequence of subgroups of F (P). A solution of a left-system (E) in F (P) modulo H is a family (g_{x} ; x ∈ X) of elements of F (A) such that, for each equation x ≡_{i} y ·g in (E), g_{x} ≡ g_{y} · g mod H_{i}, and for every x ≡_{i} g in (E), g_{x} ≡ g mod H_{i}.

Theorem 3.3 Let n ∈ ω, H = (H_{1}, H_{2}, …, H_{n}) be a sequence of finitely generated subgroups of F (P) and (E) be a left-system. Assume that (E) has no solution in F (P) modulo H. Then there exist subgroups K_{1}, K_{2}, …, K_{n} of finite index in F (P) such that H_{i} ⊆ K_{i} for all i, 1 ≤ i ≤ n and such that (E) has no solution in F (P) modulo K = (K_{1}, K_{2}, …, K_{n}).

We remark that this theorem immediately implies the theorem of Ribes and Zalesskiì: the fact that an element g of F (P) does not belong to H_{1} · H_{2} · . . . · H_{n} means exactly that the left-system

\{ \begin{matrix}x_{n} & ≡_{n} & g \\ x_{n−1} & ≡_{n−1} & x_{n} \\ … \\ x_{2} & ≡_{2} & x_{3} \\ x_{2} & ≡_{1} & e \end{matrix}

has no solution in F (P) modulo (H_{1}, H_{2}, …, H_{n}).

If H is a subgroup of F (P) and x and y are elements of F (P), we will write x ∼_{H} y for HxH = HyH. We notice that the relation ∼_{H} is an equivalence relation. We first want to replace the left-system by another kind of system, easier to manage for our purpose. A double-system is a finite set of equations of the form

x^{−1} · y ∼_{i} g where i = 1, 2, … n, x, y ∈ X and g ∈ F (P)

or of the form

x ∼_{i} g where i = 1, 2, … n, x ∈ X and g ∈ F (P)

Let H = (H_{1}, H_{2}, …, H_{n}) be a sequence of subgroups of F (P). A solution of a double-system (E) in F (P) modulo H is a family (g_{x} ; x ∈ X) of elements of F (P) such that, for every x^{−1}y ∼_{i} g in (E), g_{x}^{−1} · g_{y} ∼_{H_{i}} g, and for every x ∼_{i} g in (E), g_{x} ∼_{H_{i}} g.

We will prove

Proposition 3.4 Let (F) be a double-system, H_{1}, H_{2}, …, H_{n} be finitely generated subgroups of F (P). If the double-system (F) has no solution in F (P) modulo (H_{1}, H_{2}, …, H_{n}), then there exist subgroups K_{1}, K_{2}, …, K_{n} of finite index in F (P) such that H_{i} ⊆ K_{i} for all i, 1 ≤ i ≤ n and such that (F) has no solution in F (P) modulo (K_{1}, K_{2}, …, K_{n}).

We show how to prove Theorem 3.3 from Proposition 3.4. We see that the left-system (E) can be translated into a double-system. Let (F ) be the double-system obtained by replacing each equation x ≡_{i} y · g of (E) by the two equations:

\{ \begin{matrix}z^{−1} · x ∼_{i} e \\ y^{−1} · z ∼_{0} g \end{matrix}

where z is a new unknown (of course, different z should be taken for different equations). In the same way, x ≡_{i} g should be replaced by

\{ \begin{matrix}z^{−1}x ∼_{i} e \\ z ∼_{0} g \end{matrix}

In this translation, we have to introduce a new subgroup H_{0} which will be the trivial subgroup.

It is clear that the double-system (F ) has a solution modulo (H_{0}, H_{1}, …, H_{n}) if and only if the original left-system (E) has a solution modulo (H_{1}, H_{2}, …, H_{n}); thus (F ) has no solution. By Proposition 3.4, there exist subgroups K_{0}, K_{1}, …, K_{n} of finite index such that H_{i} ⊆ K_{i} for all i, 0 ≤ i ≤ n and such that (F ) has no solution modulo (K_{0}, K_{1}, … K_{n}). Again, this implies that the system (E) has no solution modulo (K_{1}, K_{2}, … K_{n}).

Incidently, we notice that a double-system can also easily be translated into a left-system, so that Theorem 3.3 and Proposition 3.4 have exactly the same content.

It remains to prove Proposition 3.4.

Let (F ) be a double-system. Write X for its set of unknowns, and let H = (H_{1}, H_{2}, …, H_{n}) be a sequence of finitely generated subgroups such that (F ) has no solution modulo (H_{1}, H_{2}, …, H_{n}). We first remark that we can assume that there is no equation of the form x ∼_{i} g (so that there will remain only “homogeneous” equations, of the form y^{−1} · x ∼_{i} g). Indeed, add one new unknown z (only one all together), and replace each equation of the form x ∼_{i} g by z^{−1} · x ∼_{i} g. If the new system had a solution (g_{z}, g_{x}; x ∈ X), then (g_{z}^{−1} · g_{x}; x ∈ X) would be a solution of the original system.

We consider the following relational language L: it contains:

• n + 1 unary predicate symbols U_{0}, U_{1}, …, U_{n};

• n binary predicate symbols T_{i};

• for each equation E : x^{−1}y ∼_{i} g in (F ), a binary predicate symbol R_{E}.

We now define a structure M:

• its base set is the disjoint union of the sets U_{i}^{M}, the interpretations of U_{i} in M, and U_{i}^{M} is the set F (P)/H_{i} for i = 1, 2, …, n, and U_{0}^{M} = F (P).

• for i = 1, 2, …, n, and x, y ∈ M, M ⊧ T_{i}xy if and only if x ∈ U_{0}^{M}, y ∈ U_{i}^{M} and x ∈ y.

• For all α and β in M and equation E : x^{−1}y ∼_{i} g, M ⊧ R_{E}αβ if and only if α, β ∈ F (P)/H_{i} and g ∈ α^{−1} · β (in other words, if and only if there exist a ∈ α and b ∈ β such that (equivalently, for all a ∈ α and b ∈ β) H_{i}a^{−1}bH_{i} = H_{i}gH_{i}).

We first notice that for all h ∈ F (P) the left multiplication by h is an automorphism of M. Call it ĥ.

Second, we exploit the fact that (F ) has no solution modulo (H). We cannot find elements c(x, i) in M, for x ∈ X and 0 ≤ i ≤ n such that the following set of conditions is satisfied:

(*) \{ \begin{matrix}1. for all x ∈ X and i, 0 ≤ i ≤ n, M ⊧ U_{i}c(x, i); \\ 2. for all x ∈ X, and i = 1, 2, …, n, M ⊧ T_{i} c(x, 0) c(x, i); \\ 3. If E : x^{−1} · y ∼_{i} g belongs to (F ) then M ⊧ R_{E} c(x, i) c(y, i). \end{matrix}

Otherwise, (c(x, 0) ; x ∈ X) would be a solution of (F ) mod H.

Write N for the L-structure whose base-set is the set {c(x, i) ; x ∈ X, 1 ≤ i ≤ n} and where the only relations are those necessary to make the conditions (*) true. Another way to say that (F ) has no solution modulo (H) is to say that N cannot be weakly embedded in M.

Let now C_{0} be a finite subset of F (P) containing the parameters occurring in the equations of (F ) and for each i, 1 ≤ i ≤ n a set generating H_{i}. For each element of c ∈ C_{0}, write it in the form p_{0}·p_{1}·· · ··p_{m} with the p_{i} in P ∪P^{−1}, and let P_{c} be the set {p_{1}p_{2} ⋯ p_{m}, p_{2}p_{3} ⋯ p_{m}, …, p_{m−1}p_{m}, p_{m}}. Set C = ⋃_{c∈C_{0}} P_{c} and let M_{0} be the substructure of M whose base set is C∪{cH_{i} ; c ∈ C, 1 ≤ i ≤ n}. For all p ∈ P, we can define a partial automorphism p̃ on M_{0} as the restriction of p̂, the left multiplication by p, to M_{0}.

Applying Theorem 3.2, we deduce that there exists a finite L-structure M_{1}, extending M_{0}, inside which N cannot be weakly embedded and for each p ∈ P, an automorphism p̃ of M_{1} extending p. Then, there is a natural group homomorphism h ⟼ h̃ from F (P) onto Aut(M_{1}). The point is that for i = 1, 2, …, n, and c ∈ C, c̃(H_{i}) = cH_{i}. In particular, this is true for a set generating H_{i}. In other words, if we set

K_{i} = {h ∈ F (P) ; h̃(H_{i}) = H_{i}}

then K_{i} contains H_{i}. Moreover, K_{i} is a subgroup of finite index of F (P).

Set K = (K_{1}, K_{2}, …, K_{n}). We shall conclude by proving that (F ) has no solution modulo K.

Assume, for a contradiction, that (g_{x} ; x ∈ X) is a solution of (F ) modulo K. For x ∈ X and i, 1 ≤ i ≤ n, set x_{i} = g̃_{x}(H_{i}) and x_{0} = g̃_{x}(e). We prove that the x_{i} satisfy the conditions (*), and thus that N is weakly embedded in M_{1}, which is contradictory.

1. For all x ∈ X and i, 1 ≤ i ≤ n, we have M_{1} ⊧ U_{i}(g̃_{x}(H_{i})) since M_{1} ⊧ U_{i}H_{i} and g̃_{x} is an automorphism. Similarly, M_{1} ⊧ U_{0}g̃_{x}(e)

2. For i = 1, 2, … n and x ∈ X, we have M_{1} ⊧ T_{i} g̃_{x}(e) g̃_{x}(H_{i}) since M_{1} ⊧ T_{i}eH_{i} and g̃_{x} is an automorphism.

3. If E : x^{−1}y ∼_{i} g is in (F ), then there exist k, k′ in K_{i} such that (g_{x})^{−1} · g_{y} = k · g · k′, so

g̃_{x}^{−1} · g̃_{y} · H_{i} = { \atop k · g · k′} · H_{i} = k̃ · g · H_{i} = k̃ · g · H_{i}. It is clear that M_{1} ⊧ R_{E} H_{i} gH_{i}, and since k̃

is an automorphism of M_{1}, M_{1} ⊧ R_{E} k̃H_{i} k̃gH_{i}, thus M_{1} ⊧ R_{E} H_{i} g̃_{x}^{−1}g̃_{y}H_{i}. Now, g̃_{x} is an automorphism, so M_{1} ⊧ R_{E} g̃_{x}(H_{i}) g̃_{y}(H_{i}).

♡

We just proved Theorem 3.3 using Theorem 3.2 and we will prove Theorem 3.2 directly in the following section. But let us point out that the method of section 2 provides a short proof of Theorem 3.2 using Theorem 3.3. One has to translate the condition of being T -free into a finite system of equations.

We can give an alternative formulation to Theorem 3.3: fix the finite alphabet P and consider equations of the form:

x ≡ y · v mod ⟨w_{1}, w_{2}, …, w_{n}⟩

where the x and y are unknowns and the v and the w are words in the alphabet P ∪ P^{−1}. Given a group G and, for each p ∈ P, a value p̄ of p, this equation has an obvious meaning: each of the words v or w_{i} occurring in these equations is interpreted by the element of G obtained by replacing the p by the p̄, and we must find values in G for the unknowns satisfying all the equations. Then Theorem 3.3 can be rephrased as follows:

Theorem 3.5 Let S be a finite set of equations of the above form. If for all finite groups G and interpretations of the p in G, the system S has a solution, then for every group G′ and for all interpretations of the p in G′ the system S has a solution.

4 Extension Lemmata

4.1 A simple combinatorial proof of the theorem of Hrushovski

In this subsection, we will give a simple combinatorial proof of Theorem 1.4. We begin with two definitions.

Definition 4.1 Let X be a finite set and n a positive integer; then Γ(X, n) denotes the graph whose base is [X]^{n}, the set of subsets of X of cardinality exactly n, and where the binary relation R is defined by: for a, b ∈ [X]^{n}, Rab if and only if a ∩ b ≠ ∅.

Definition 4.2 A subgraph Γ_{0} of Γ(X, n) is poor if: 1) for all x ∈ X, card{a ∈ Γ_{0}; x ∈ a} ≤ 2;

2) for all a, b ∈ Γ_{0}, if a ≠ b then card(a ∩ b) ≤ 1.

If α is a permutation of X, we will denote by α^{∗} the induced automorphism of Γ(X, n).

The theorem is a immediate consequence of the two following lemmata.

Lemma 4.3 Every finite graph is poorly represented: if Γ is a finite graph, then there exist a finite set X, a positive integer n and a poor subgraph Γ_{0} of Γ(X, n) isomorphic to Γ.

Proof. Let X_{0} be the set of edges of Γ. For each point a in Γ, let f(a) = {x ∈ X_{0} ; x is adjacent to a}. If the cardinality of f(a), for a ∈ Γ, is constant equal to n bigger than one, then we are done, because f is an isomorphism from Γ to a poor subgraph of Γ(X_{0}, n). In the general case, let n = sup(sup(f(a) ; a ∈ Γ), 2) and let X be a finite set containing X_{0} and sufficiently large so that it is possible to define a map h from Γ to [X]^{n} such that for all distinct a and b in Γ : f(a) ⊆ h(a), h(a) − f(a) ⊂ X − X_{0}, (h(a) − f(a)) ∩ (h(b) − f(b)) = ∅.

♡

Lemma 4.4 Let Γ_{0} and Γ_{1} be two poor subgraphs of Γ(X, n), and f an isomorphism from Γ_{0} to Γ_{1}. Then there exist a permutation α of X such that α^{∗} extends f.

Proof. First define α(x) for x ∈ X belonging to 2 elements a and b of Γ_{0}: there is no choice, it has to be the unique element of f(a) ∩ f(b); then, for all a ∈ Γ_{0}, extend α to a by defining a bijection between

{x ∈ a ; for all b ∈ Γ_{0} − {a}, x ∉ b}

and

{x ∈ f(a) ; for all b ∈ Γ_{1} − {f(a)}, x ∉ b}

This is possible because these two sets have the same cardinality. Then extend to a permutation of X.

♡

Remark: in his paper, Hrushovski remarks that the cardinality of the resulting homogeneous graph Z is bounded by something like 2^{2^{k}}, if k is the cardinality of Γ. He asks whether it is possible to find a graph Z of cardinality bounded by 2^{ck^{2}}, for some constant c.

The above proof show that, in fact the graph Z can be found of cardinality less than k^{2k}. We will make the precise computation.

Let k be the cardinality of Γ and n the valency of Γ, that is the maximal number of edges adjacent to a given vertex. The “homogeneous” graph Z is a graph Γ(X, n); let us compute precisely the cardinality of X. Let m be the number of edges of Γ, and for every a ∈ Γ, c(a) the number of edges adjacent to a. We have

∑_{a∈Γ} c(a) = 2m

On the other hand, the set X is the disjoint union of the set of edges and, for all a ∈ Γ, of a set of cardinality n − c(a). So the cardinality of X is

m + ∑_{a∈Γ}(n − c(a)) = nk − m

and the cardinality of Z is bounded by (nk)^{n}.

So, for graphs of bounded valency, the cardinality of Z is bounded polynomially in the cardinality of Γ (but we should be careful that the graph Z has a much bigger valency).

If we do not want to take the valency into account, a first estimation gives k^{2k} for the bound of the cardinality of Z. But we can get a slightly better bound: we may assume that m the number of edges in Γ is bigger than or equal to the number of non-edges, so the cardinality of X can be bounded by 3k^{2}/4 and the cardinality of Z can be bounded by

(\frac{3k^{2}}{4} )^{k} × \frac{1}{k!}

Remarking that k! ≥ (k/e)^{k}, we see that the cardinality of Z can be bounded by (3ek/4)^{k}.

4.2 Generalisation to arbitrary relational languages

Theorem 4.5 Let r > 1. Suppose the language L consists of just one r-ary predicate R. Let A be an L-structure of cardinality c. There exists an L-structure B with A ⊆ B and card(B) ≤ 2^{r!rc^{r}} such that every partial automorphism on A extends to an automorphism of B.

Before we prove the theorem we give some helpful definitions.

Definition 4.6 Let X be a finite set. We define the L-structure M(X): its domain is (℘(X))^{r}, so its elements are r-tuples of subsets of X. For an element a ∈ M(X) we denote by a_{j} the j-th coordinate of a (1 ≤ j ≤ r). We define the r-ary relation R on M(X). For a^{1}, …, a^{r} ∈ M(X):

M(X) ⊧ R(a^{1}, …, a^{r}) if and only if ⋂_{1≤i≤r} a_{i}^{i} ≠ ∅

Note that the group Sym(X) of permutations of X acts as automorphisms on M(X).

Definition 4.7 Let k be an integer. We say that a substructure N of M(X) is k-regular, if there exists an integer p_{k} > 0 such that, for every a^{1}, …, a^{k} ∈ N and every i_{1}, …, i_{k} ∈ {1, …, r}, if i_{1}, ….i_{k} are pairwise distinct, then card(⋂_{j=1}^{k} a_{i_{j}}^{j}) = p_{k}. We say that N is regular, if

• it is k-regular for every k < r;

• for a, b ∈ N distinct and 1 ≤ i ≤ r we have a_{i} ∩ b_{i} = ∅;

• for a^{1}, …, a^{r} ∈ N, if Ra^{1} … a^{r} then card(⋂_{i=1}^{r} a_{i}^{i}) = 1.

For m an integer we denote by M(X, m) the substructure of M consisting of all r-tuples of sets of size m. Note that if N is a 1-regular substructure of M(X) then there exists an m such that N is a substructure of M(X, m). Furthermore Sym(X) also acts on M(X, m).

The theorem follows immediately from the following two Lemmata:

Lemma 4.8 Let A be an L-structure of cardinality c. There exist a set X with card(X) ≤ r!c^{r} and a regular substructure of M(X) which is isomorphic to A.

Lemma 4.9 If N is a regular substructure of M(X), then every partial automorphism of N extends to an automorphism of M(X), which is induced by the action of Sym(X) on M(X).

Proof of the first Lemma:

Let X_{0} be the set of links of A (here, the r-tuple (a^{1}, a^{2}, …, a^{r}) of A such that A ⊧ Ra^{1}a^{2} … a^{r}). We first embed A into M(X_{0}): for each a ∈ A we let α(a) = (t_{1}, …, t_{r}), where t_{i} = {q ∈ X_{0}; q_{i} = a}. We first remark that the last two conditions for regularity are satisfied. We will increase the set X_{0} step by step and change the embedding α such that α[A] becomes k-regular for every k with r − 1 ≥ k ≥ 1. Do not worry that α is not necessarily an embedding to begin with. All the isolated points get mapped to the same r-tuple. In our construction we will maintain the condition, that for a, b ∈ A distinct and 1 ≤ j ≤ r we have α(a)_{j} ∩ α(b)_{j} = ∅. So the final mapping α will be injective.

We are first aiming for (r − 1)-regularity. Consider all sets of the form ⋂_{1≤j≤r−1} α(a^{j})_{i_{j}} for a^{1}, a^{2}, …, a^{r−1} ∈ A and i_{1}, …, i_{r−1} ∈ {1, …, r} pairwise distinct. Let v be the maximal cardinality of these sets. You may think of v as the (maximal) valency of the L-structure A. We let p_{r−1} = v. Easily p_{r−1} ≤ c. For every a^{1}, …, a^{r−1} ∈ A and i_{1}, …, i_{r−1} ∈ {1, …, r} pairwise distinct, if card(⋂_{j=1}^{r−1} α(a^{j})_{i_{j}}) = p′ < p_{r−1} we choose (p_{r−1} − p′) new elements which we add to each set α(a^{j})_{i_{j}} (for 1 ≤ j ≤ (r − 1)). As every new element will belong to exactly (r − 1) sets of the form α(a)_{j} with different j each, the second two conditions for regularity will remain true. If we let X_{1} be the set X_{0} together with the new points, and if we change α as indicated we will have α[A] is (r − 1)-regular in M(X_{1}). Note that X_{1} = ⋃{⋂_{j=1}^{r−1} α(a^{j})_{i_{j}}; a^{1}, …, a^{r−1} ∈ A, i_{1}, …, i_{r−1} ∈ {1, …, r} pairwise distinct}.

Now we suppose we already have constructed a set X_{t} (1 ≤ t < (r − 1)) and an embedding α : A ↪ M(X_{t}) which is j-regular for (r − 1) ≥ j ≥ (r − t), the constant for (r − t)- regularity being p_{r−t} = t!·c^{t−1}·v. Furthermore we suppose X_{t} = ⋃{⋂_{j=1}^{r−t} α(a^{j})_{i_{j}}; a^{1}, …, a^{r−t} ∈ A,

i_{1}, …, i_{r−t} ∈ {1, …, r} pairwise distinct}. Now we consider all sets of the form ⋂_{j=1}^{r−(t+1)} α(a^{j})_{i_{j}} for a^{1}, …, a^{r−(t+1)} ∈ A and i_{1}, …, i_{r−(t+1)} ∈ {1, …, r} pairwise distinct. As we have

⋂_{j=1}^{r−(t+1)} α(a^{j})_{i_{j}} = ⋃{ ⋂_{j=1}^{r−(t+1)} α(a^{j})_{i_{j}} ∩ α(b)_{k}; b ∈ A, k ∈ {1, …, r} − {i_{1}, …, i_{r−(t+1)}}},

we have card(⋂_{j=1}^{r−(t+1)} α(a^{j})_{i_{j}}) ≤ (t + 1) · c · p_{r−t}. This means we can set p_{r−(t+1)} = (t + 1)! · c^{t} · v.

Now we add (p_{r−(t+1)} − q) many new points to a set of the form ⋂_{j=1}^{r−(t+1)} α(a^{j})_{i_{j}} of cardinality q to define the set X_{t+1}.

At the end we constructed a set X = X_{r−1} and an embedding α : A ↪ M(X) such that α[A] is regular, the constant for 1-regularity being p_{1} = (r − 1)!c^{r−2}v. Every point of X is of the form α(a)_{i} with a ∈ A and i ∈ {1, …, r}. That means card(X) ≤ r · c · p_{1} = r! · c^{r−1} · v ≤ r! · c^{r}. This proves the Lemma. Note that we could get a slightly better bound in the theorem by letting B = M(X, p_{1}): card(B) ≤ (e · r · c)^{(r!·c^{r−2}·v)} ≤ (erc)^{r!c^{r−1}}.

♡

Before we prove Lemma 4.9, we do a little preparation:

Definition 4.10 Let X, Y be sets of the same cardinality and let q be a partial function from P(X) to P(Y). We say q is induced by a bijection π : X → Y, if for every a in the domain of q q(a) = π[a].

Lemma 4.11 Let X, Y be finite sets of the same cardinality and let q be a partial function from P(X) to P(Y). Then q is induced by a bijection π : X → Y if and only if for every subset s of dom(q), the domain of q, we have: card(⋂_{a∈s} a) = card(⋂_{a∈s} q(a)).

Suppose for every s ⊆ dom(q), card(⋂_{a∈s} a) = card(⋂_{a∈s} q(a)). We can suppose dom(q) is closed under intersection, as for a, b ∈ dom(q) we can define q(a ∩ b) to be q(a) ∩ q(b) and still maintain the condition on q. We can also suppose dom(q) is closed under complements, as for every a ∈ dom(q) we can define q(a^{c}) = q(a)^{c}. Here we are using the finiteness of X and Y. Finally we can suppose that for every x ∈ X, {x} ∈ dom(q): for x ∈ X we define s_{x} = {b ∈ dom(q) | x ∈ b} and by the condition on q, we have ⋂_{b∈s_{x}} q(b) ≠ ∅. We choose y ∈ ⋂_{b∈s_{x}} q(b) and let q({x}) = {y} and check that we still have the condition on q. This means we can assume dom(q) = P(X) and in this case we can define π by letting π(x) be the unique element of q({x}). Easily we have for every a ∈ P(X) q(a) = π[a].

♡

Now we prove the Lemma 4.9: Let p be a partial automorphism of N with domain D. Define a partial map q from P(X) to P(X) with domain {a_{i}; a ∈ D, 1 ≤ i ≤ r} by defining for a ∈ D and 1 ≤ i ≤ r: q(a_{i}) = p(a)_{i}. Now let k ∈ ω and let a^{1}, … a^{k} ∈ D and j_{1}, …, j_{k} ∈ {1, …, r}. We want to check that card(a_{j_{1}}^{1} ∩ … ∩ a_{j_{k}}^{k}) = card(p(a^{1})_{j_{1}} ∩ p(a^{2})_{j_{2}} ∩ … ∩ p(a^{k})_{j_{k}}). We can suppose that (a^{1}, j_{1}), …, (a^{k}, j_{k}) are pairwise distinct. Also we can suppose that j_{1}, … j_{k} are pairwise distinct as otherwise both cardinalities are 0 by the second condition for regularity. If k < r then by k-regularity both cardinalities are equal to p_{k}. If k = r by changing the enumeration we can suppose that j_{1} = 1, …, j_{r} = r. In that case only the cardinalities 0 and 1 appear. We have card(a_{1}^{1} ∩ … ∩ a_{r}^{r}) = 1 if and only if Ra^{1}a^{2} … a^{r} if and only if R p(a^{1}) p(a^{2}) … p(a^{r}) if and only if card(p(a^{1})_{1} ∩ … ∩ p(a^{r})_{r}) = 1.

Thus q and therefore also p is induced by a permutation of X.

♡

The following lemma shows how to compute bounds for bigger languages:

Lemma 4.12 Let L = L_{1} ∪ L_{2} be a finite relational language. Suppose L_{1} ∩ L_{2} = ∅. Let A be an L-structure. Let B_{1} be an L_{1}-structure with A ⊂ B_{1} such that every partial automorphism of A_{|L_{1}} can be extended to an automorphism of B_{1} and let B_{2} be an L_{2}-structure with A ⊂ B_{2} such that every partial automorphism of A_{|L_{2}} can be extended to an automorphism of B_{2}. Suppose card(B_{1}) = n_{1} and card(B_{2}) = n_{2}.

There exists an L-structure B with card(B) = n_{1} · n_{2} and A ⊂ B, such that every partial automorphism of A extends to an automorphism of B.

Proof. The domain of B is B_{1} × B_{2}.

For R ∈ L_{1}, r-ary and (a_{1}^{1}, a_{2}^{1}), …, (a_{1}^{r}, a_{2}^{r}) ∈ B we define:

R^{B} (a_{1}^{1}, a_{2}^{1}) … (a_{1}^{r}, a_{2}^{r}) ⟺ R^{B_{1}}a_{1}^{1} … a_{1}^{r}

and for R ∈ L_{2}, r-ary and (a_{1}^{1}, a_{2}^{1}), …, (a_{1}^{r}, a_{2}^{r}) ∈ B we define:

R^{B} (a_{1}^{1}, a_{2}^{1}) … (a_{1}^{r}, a_{2}^{r}) ⟺ R^{B_{2}}a_{2}^{1} … a_{2}^{r}.

Note that for α_{1} ∈ Aut(B_{1}) and α_{2} ∈ Aut(B_{2}) we have that (α_{1}, α_{2}) ∈ Aut(B).

Let i_{1} : A_{|L_{1}} ↪ B_{1} and i_{2} : A_{|L_{2}} ↪ B_{2} be the inclusion mappings. Then (i_{1}, i_{2}) : A ↪ B is an embedding of L-structures.

Via this embedding we can suppose that A ⊂ B. Let p be a partial automorphism of A. As p is a partial automorphism of A_{|L_{1}} it can be extended to an automorphism α_{1} of B_{1} and for the analogous reason to an automorphism α_{2} of B_{2}. Now (α_{1}, α_{2}) ∈ Aut(B) extends p.

♡

Corollary 4.13 Let L be a finite relational language. Let r be the maximal arity of symbols in L. For 1 ≤ j ≤ r let l_{j} be the number of j-ary symbols in L. Let A be a finite L-structure of cardinality c. There exists a structure B such that A ⊂ B and every partial automorphism of A extends to an automorphism of B and card(B) ≤ c · 2^{p(c)} where p(c) = ∑_{j=2}^{r} l_{j}j!jc^{j}.

The proof consists of putting together Theorem 4.5 and Lemma 4.12 and observing that if R only consists of unary predicates then B = A will do.

♡

4.3 The case of the cycle-free n-partitioned graph

The language L consists of n unary predicates U_{1}, …, U_{n} and one binary predicate R. We write a → b for Rab. Denote by K the class of cycle-free, n-partitioned directed graphs.

If M is in K and a, b ∈ M then we define a →_{M}^{∗} b if there exist j ≤ k and a_{j} ∈ U_{j}^{M}, …, a_{k} ∈ U_{k}^{M} such that a = a_{j} → a_{j+1} → … → a_{k} = b.

Lemma 4.14 K has the EPPA.

Proof. Let A ∈ K be finite, and let p_{1}, …, p_{t} be partial automorphisms on A. We assume there exist M ∈ K and g_{1}, …, g_{t} ∈ Aut(M) such that g_{i} extends p_{i}. We let D_{i} be the domain of p_{i} and D′_{i} be its range.

First step.

Without loss of generality we can suppose that for a, b ∈ A, if there exists an i such that a, b ∈ D_{i} or a, b ∈ D′_{i}, then a →_{M}^{∗} b if and only if a →_{A}^{∗} b. (Just put enough points as witnesses into the structure A without extending p_{i}.) Now for every a, b ∈ D_{i}: a →_{A}^{∗} b if and only if p_{i}(a) →_{A}^{∗} p_{i}(b) (because g_{i} is an automorphism it is clear that a →_{M}^{∗} b if and only if g_{i}(a) →_{M}^{∗} g_{i}(b).) This will be the only place where we use the existence of the structure M; later we will only use the fact that now p_{i} also respects →_{A}^{∗}. Now we can forget the structure M and use →^{∗} for →_{A}^{∗}

Second step.

For U ⊆ A define cl(U) := {b ∈ A ; ∃a ∈ U : a →^{∗} b}. We say U is closed, if cl(U) = U. The first level U_{1}^{A} of our structure will play a special role in the argument, we define A_{u} := A − U_{1}^{A} (the upper part of A). We order ℕ^{n−1} lexicographically and define a dimension function dim : ℘(A_{u}) → ℕ^{n−1} by:

If U is closed then dim_{2}(U) = card(U ∩U_{2}^{A}) and for k ≥ 2 dim_{k+1}(U) = card((U −cl(U ∩U_{k}^{A}))∩ U_{k+1}^{A}) and dim(U) := (dim_{2}(U), …, dim_{n}(U)); finally if U is arbitrary: dim(U) := dim(cl(U)). Informally dim_{k}(U) counts the points in the k-th level of U, which are not already in the closure of a point of lower level of U. If U ⊆ A_{u} is arbitrary one can use the following method, to determine dim(U): call b ∈ U a root of U if there does not exist an element a ∈ U such that a ≠ b, a →^{∗} b. Then dim_{k}(U) = card({b ∈ U ∩ U_{k}^{A} ; b a root of U}).

It is not hard to check, that • U ⊆ V implies cl(U) ⊆ cl(V);

• U ⊆ V implies dim(U) ≤ dim(V);

• cl(U) ⊊ cl(V) implies dim(U) < dim(V);

• if U ⊆ D_{i} then dim(U) = dim p_{i}(U).

For the last statement use the fact that p_{i} respects the relation →^{∗} and use the above mentioned method to compute the dimension.

Lemma 4.15 There exist a set C of unary predicates (called colors), containing for every a ∈ U_{1}^{A} a color Q_{a} and an expansion (A, (Q^{A})_{Q∈C}) of the structure A (a coloring of A), such that:

• Q_{a}^{A} = cl(a);

• For Q ∈ C − {Q_{a} ; a ∈ U_{1}^{A}}, Q^{A} is included in A_{u} and is closed;

• “For a closed subset V the number of colors of V (i.e. the colors Q such that V ⊆ Q^{A}) only depends on the dimension of V ”. More formally: There exists a function f : ℕ^{n−1} → ℕ, such that for every V ⊆ A_{u}, V closed,

card{Q ∈ C ; V ⊆ Q^{A}} = f(dim(V))

Let {d_{1}, …, d_{r}} = {dim V ; V ⊆ A_{u}}, d_{1} < … < d_{r} lexicographically. For every single closed V ⊆ A_{u} we will decide how many colors Q we want to put into C with Q^{A} = V. We will do this and define the function f by downward induction on dim(V). Note that the value of f only has to be defined for d_{r}, …, d_{1}.

Let C_{r} = {Q_{a} ; a ∈ U_{1}^{A}}; we will define C_{r} ⊆ … ⊆ C_{0} = C. Suppose (by induction) that for a given i < r, C_{i+1} is already defined and for d′ > d_{i+1} = d f(d′) is already defined such that for every V ⊆ A_{u}: If dimV > d then card{Q ∈ C_{i+1} ; V ⊆ Q^{A}} = f(dim(V)).

Define f(d) = max{card{Q ∈ C_{i+1} ; V ⊆ Q^{A}}; V ⊆ A_{u}, V closed, dimV = d} and add for every closed V ⊆ A_{u} with dimV = d enough colors Q with Q^{A} = V (i.e. f(d)−card{Q ∈ C_{i+1} ; V ⊆ Q^{A}} many) to C_{i+1} to define C_{i} such that card{Q ∈ C_{i} ; V ⊆ Q^{A}} = f(d).

The strict monotonicity of the dimension ensures that this works (no different closed subsets of dimension d are contained in each other and if dimV > d the equation card{Q ∈ C_{i} ; V ⊆ Q^{A}} = f(dim V) will be maintained). C = C_{0} fulfils the requirement of the claim.

♡

Note that also for arbitrary V ⊆ A_{u}, we have

card{Q ∈ C ; V ⊆ Q^{A}} = f(dim V)

because {Q ∈ C ; V ⊆ Q^{A}} = {Q ∈ C_{i} ; cl(V) ⊆ Q^{A}} = f(dim(cl(V))) and dim(cl(V)) = dim V.

Definition 4.16 Let D ⊆ A (think of D = D_{i} ∩ A_{u}) and let V ⊆ D. V is called relatively closed in D, if V = cl(V) ∩ D or, equivalently, if

∀a ∈ V, ∀b ∈ D : (a →^{∗} b ⇒ b ∈ V).

Note that for every Q ∈ C and D ⊆ A_{u}, Q^{A} ∩ D is relatively closed in D.

Lemma 4.17 Let 1 ≤ i ≤ t and let V ⊆ D_{i} ∩A_{u} be relatively closed in D_{i} ∩A_{u}. Then V′ := p_{i}(V) is relatively closed in D′_{i} ∩ A_{u} and

card{Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = V } = card{Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = V′}.

We will prove the equality by downward induction on dimV. First note that the lattice of relatively closed subsets of D_{i} ∩ A_{u} is isomorphic via p_{i} to the corresponding lattice for D′_{i} ∩ A_{u} and this isomorphism respects dimensions.

Suppose V ⊆ D_{i} ∩ A_{u} is relatively closed and suppose that for W ⊆ D_{i} ∩ A_{u} relatively closed with V ⊊ W. We already know that:

card{Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = W } = card{Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = p_{i}(W)}.

(The same equation for W not relatively closed is trivial: then both sides are 0.)

Write S := {W ; V ⊊ W ⊆ D_{i} ∩ A_{u}} and S′ := {W ; V′ ⊊ W ⊆ D′_{i} ∩ A_{u}}. Then:

card{Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = V } =

card{Q ∈ C ; V ⊆Q^{A}} − ∑_{W ∈S} card{Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = W } =

f(dim V) − ∑_{W ∈S} card{Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = p_{i}(W)} =

f(dim V′) − ∑_{W′∈S′} card{Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = W′} =

card{Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = V′}.
♡

Now we want to get the colors into the language by introducing a new binary predicate relating the points to their colors.

Definition 4.18 We let L′ = {R, U_{1}, …, U_{n}}∪{C, D}. We define an L′-structure B with domain A ∪ C. We let R^{B} = R^{A}, U_{1}^{B} = U_{1}^{A}, …, U_{n}^{B} = U_{n}^{A} and C^{B} = C and we put D^{B}qa if and only if q ∈ C and a ∈ A and a is of color q.

Lemma 4.19 For every i there is a permutation χ_{i} of the set C of colors such that p_{i} ∪ χ_{i} is a partial automorphism of B.

Certainly every color Q ∈ C belongs to exactly one set of the form

{Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = V }

(for some V ⊂ D_{i}), so we can define a permutation χ_{i} mapping {Q ∈ C ; Q^{A} ∩ D_{i} ∩ A_{u} = V } bijectively to {Q ∈ C ; Q^{A} ∩ D′_{i} ∩ A_{u} = p_{i}(V)}. Furthermore, we can find the χ_{i} such that for a ∈ D_{i} ∩ U_{1}^{A}, Q_{a}^{χ_{i}} = Q_{p_{i}(a)} (because: if Q_{a} ∩ D_{i} ∩ A_{u} = V then Q_{p_{i}(a)} ∩ D′_{i} ∩ A_{u} = p_{i}(V) and that is because p_{i} respects →^{∗}).

Now it remains to show, that r_{i} := p_{i} ∪χ_{i} is a partial automorphism of B; so let a ∈ D_{i}, Q ∈ C. We have to show that a ∈ Q^{A} if and only if a′ ∈ Q′^{A} (where a′ is p_{i}(a) and Q′ is χ_{i}(Q)).

If a ∈ U_{1}^{A}, then a ∈ Q^{A} if and only if Q = Q_{a}, if and only if Q′ = Q_{a′}, if and only if a′ ∈ Q′^{A}.

If a ∈ A_{u}, let V := Q^{A} ∩ D_{i} ∩ A_{u} so by definition of χ_{i}, Q′^{A} ∩ D′_{i} ∩ A_{u} = p_{i}(V). So a ∈ Q^{A} if and only if a ∈ V, if and only if a′ ∈ p_{i}(V), if and only if a′ ∈ Q′^{A}.

Third step

The structure B has the following properties:

• for every element a of U_{1} there exists exactly one q ∈ C (namely q = Q_{a}) such that Dqa;

• if a ∈ U_{i} (1 ≤ i < n) and a → b and Dqa then Dqb (just because the interpretation of the color q in A is closed);

• if a ∈ U_{s}^{A} and a → b and Dqa then not Dqb.

For the last point suppose Dqb; because b ∈ U_{1}^{A}, it follows that q = Q_{b}, but a ∈ Q_{b} means that b →^{∗} a, and this would mean that there is an s-cycle in A.

Now we are using the Corollary 4.13. So we know, there exists a finite L′–structure E, B ⊆ E, and g_{1}, …, g_{n} ∈ Aut(E), g_{i} extending p_{i} for every i. By the remark after Definition 2.1 we can choose B to be slim. Note that this automatically ensures that C^{E} = C^{B} = C.

Claim: The structure E has the following properties:

• for every point a ∈ U_{1} there exists exactly one q ∈ C such that Dqa;

• if a ∈ U_{i} (1 ≤ i < n) and a → b and Dqa then Dqb;

• if a ∈ U_{s}^{A} and a → b and Dqa then not Dqb.

This follows directly from the fact that E is slim, and the corresponding property of A. Suppose e.g. that a ∈ U_{i}^{E} (1 ≤ i < n) and a → b and Dqa. Then we know that there exists h ∈ F (P) such that h̃(a), h̃(b) ∈ A and of course h̃(a) → h̃(b). So we have Dh̃(q)h̃(a), which implies Dh̃(q)h̃(b) which implies Dqb.

Now to complete the proof, we have to check that E is cycle-free. Suppose there are elements a_{1} ∈ U_{1}^{E}, …, a_{n} ∈ U_{n}^{E}, such that a_{1} → a_{2} → … → a_{n} → a_{1}. Choose q ∈ C such that Dqa_{1}, inductively follows Dqa_{n} and not Dqa_{1}, a contradiction.

5 Proof of Theorem 3.2

This section is entirely devoted to the proof of Theorem 3.2. The strategy is to reduce the problem, by successive steps, to an easy one.

5.1 Reduction to stretched structures

To begin with, we will assume that all structures we are considering are irreflexive: a structure M in a language L is irreflexive if, for every n-ary predicate R in L and a_{1}, a_{2}, …, a_{n} ∈ M, if M ⊧ Ra_{1}a_{2} … a_{n}, then the a_{i} are pairwise distinct. We can do that without loss of generality (see the last section of [6]).

The first real reduction states that it is enough to prove it for a certain kind of structures, which we will call the stretched structures and which we define now.

The language L of a stretched structure M should contain unary predicates U_{0}, U_{1}, …, U_{k}. The universe of M is the disjoint union of the sets U_{i}^{M}. Moreover, for each n-ary relation symbol R of L, and for all a_{1}, a_{2}, … a_{n} in M, if M ⊧ Ra_{1}a_{2} … a_{n}, then the set {a_{1}, a_{2}, …, a_{n}} intersects each set U_{i}, for 1 ≤ i ≤ k in at most one element (notice that U_{0} has a special status).

A small structure M is a stretched structure such that for all i, 0 ≤ i ≤ k, U_{i}^{M} has at most one element.

The first reduction is a very important one (we will consistently call each of these reductions ‘proposition’).

Proposition 5.1 Let T be a finite set of small structures. Then the class of stretched T -free structures has the EPPA.

Proof. We deduce Theorem 3.2 from Proposition 5.1: suppose we are given a language L, a finite set T of finite L-structures, A a finite T -free L-structure, p_{1}, p_{2}, …, p_{n} ∈ Part(A, A), a T -free structure M extending A and automorphisms α_{1}, α_{2}, …, α_{n} ∈ Aut(M) extending respectively p_{1}, p_{2}, …, p_{n}. Let k = max(card(T); T ∈ T ). From A we want to define a stretched structure Â. We first add to the language k new unary predicates U_{0}, U_{1}, …, U_{k−1}. We will write L^{+} for the language that we obtain this way. The universe of Â is A × {0, 1, …, k − 1}. The interpretation of U_{i} in Â (for 0 ≤ i ≤ k − 1) is A × {i}. If R is an s-ary relation symbol in the language L of A, the interpretation of R in Â is defined by:

Â ⊧ R (a_{1}, i_{1}) (a_{2}, i_{2}) … (a_{s}, i_{s}) if and only if A ⊧ Ra_{1}a_{2} … a_{s} and for all i, 1 ≤ i ≤ k − 1 there is at most one m, 1 ≤ m ≤ s, such that i_{m} = i.

It is clear that Â is a stretched structure. Moreover, the map π from Â_{|L} onto A defined by π((a, i)) = a is a weak homomorphism.

For every element T of T choose a small L^{+}-structure T^{+} which expands T (this is possible because k has been chosen sufficiently large). Let T^{+} = {T^{+}; T ∈ T }. We can see that Â is T^{+}-free: if h were a weak homomorphism from some T^{+} into Â, then π ∘ h would be a weak homomorphism from T_{|L}^{+} (which is equal to T) to A.

Now, for each partial automorphism p_{i} of A, we may define a partial map p̂_{i} of Â by: if a ∈ Dom(p) and 0 ≤ i ≤ k − 1, p̂_{i}((a, j)) = (p_{i}(a), j). It is straightforward to check that these maps are partial automorphisms. We may also define analogously a stretched L^{+}-structure M̂ from M, and automorphisms α̂_{1}, α̂_{2}, … α̂_{n} of M̂. As above, M̂ is T^{+}-free, and it is clear that M̂ extends Â and that the α̂_{i} extend the p̂_{i}.

Thus we may apply Proposition 5.1: we get a finite T^{+}-free L^{+}-structure C extending Â and automorphisms γ_{1}, γ_{2}, …, γ_{n} of C extending the p̂_{i}. Moreover, if we translate the problem into a problem in the free group, as has been done in subsection 2.2, we see that to be T^{+}-free can be forced by negative conditions, so, we may apply Proposition 2.3 and assume that C is a special extension of Â. (Another way to see this is as follows: By a remark after Proposition 2.3 we find a special solution D and ρ : D ⟶_{w} C. As C is T^{+}-free also D is T^{+}-free and therefore we can suppose C to be special.)

We restrict our attention to the L-structure B that we get in the following way: first we take the substructure of C whose universe is the set of elements of C which belong to U_{0}. Then we take the L-reduct of this structure to obtain B. Some fact are immediately clear: Since C is special, the U_{i} partition the universe of C. The γ_{i} leave the set B fixed, so they induce permutations β_{i} of B, and these permutations are in fact automorphisms of B. We may identify the U_{0} part of Â with A (identifying (a, 0) with a). Doing this, B will be viewed as an extension of A, and the β_{i} as extensions of the p_{i}.

Thus, it will suffice to prove that B is T -free.

Let T ∈ T and let {t_{1}, t_{2}, …, t_{s}} be the universe of T. Let T′ be the expansion of T to L^{+}, where all the t_{i} for 1 ≤ i ≤ s belong to U_{0}. We may construct a sequence T_{0}, T_{1}, …, T_{s} of stretched L^{+}-structures which all are expansions of T, beginning with T_{0} = T^{+} and ending with T_{s} = T′ such that the only possible difference between T_{j} and T_{j+1} is that t_{j+1}, which satisfies some U_{r} in T_{j}, satisfies U_{0} instead in T_{j+1}. We prove by induction on j that C is T_{j}-free. We already know that it is T_{0}-free, and once we will know it is T_{s}-free, we will know that B is T -free.

By way of contradiction, assume that C is T_{j}-free, and that h is a weak homomorphism from T_{j+1} into C. Let G be the group of automorphisms of C generated by {γ_{1}, γ_{2}, …, γ_{n}}. Since every element of C is the image by an element of G of an element of Â, we may assume that h(t_{j+1}) ∈ Â.

Since T_{j+1} ⊧ U_{0} t_{j+1} and h is a weak homomorphism, h(t_{j+1}) = (a, 0) for some a ∈ A. Let m be the positive integer such that T_{j} ⊧ U_{m}(t_{j+1}) and h′ the map from T_{j} into C equal to h except in t_{j+1} where h′(t_{j+1}) = (a, m). We show that h′ is a weak homomorphism from T_{j} into C, and get a contradiction.

By construction, h′ preserves the predicates U_{i}. So let R be a predicate symbol of L and assume that T_{j} ⊧ Rt_{j+1}t̄ where t̄ is a sequence of t_{i} . Thus, we also have T_{j+1} ⊧ Rt_{j+1}t̄, and since h is a weak homomorphism, C ⊧ R h(t_{j+1}) h(t̄). Because C is slim, there exist b ∈ Â, a sequence c̄ of elements of Â such that Â ⊧ Rbc̄ and such that h(t_{j+1})h(t̄) = γ(bc̄) for some γ ∈ G. In particular γ(b) = h(t_{j+1}) = (a, 0). Let b′ = π(b) (that is, b = (b′, 0)), c̄′ = π(c̄) and b_{1} = (b′, m). By construction of Â A ⊧ Rb′c̄′ and Â ⊧ Rb_{1}c̄.

We now use the real strength of the hypothesis that C is special: there exist a word w of the free group F (x_{1}, x_{2}, …, x_{n}) such that γ = w(β_{1}, β_{2}, …, β_{n}) and w(p̂_{1}, p̂_{2}, …, p̂_{n})(b) = (a, 0). Since w(p̂_{1}, p̂_{2}, …, p̂_{n})(b_{1}) = (a, m), we have γ(b_{1}) = w(β_{1}, β_{2}, …, β_{n})(b_{1}) = (a, m) = h′(t_{j+1}). From Â ⊧ Rb_{1}c̄ we deduce C ⊧ Rγ(b_{1})γ(c̄). Because T is irreflexive h′(t̄) = h(t̄) = γ(c̄). Thus C ⊧ Rh′(t_{j+1})h′(t̄).

♡

5.2 Short extensions

From now on and until the end of the proof of Theorem 3.2, we will only deal with stretched structures in a fixed language L. To fix the notations, we will suppose that U_{0}, U_{1}, …, U_{k} are the unary predicates necessary to make our structures stretched. Before going any further, we need some definitions.

Definition 5.2 Let M_{0} be a stretched structure, M_{1} and M_{2} be two extensions of M_{0}. Assume that M_{1} ∩ M_{2} = M_{0}. The free amalgam of M_{1} and M_{2} over M_{0}, denoted M_{1} ∗_{M_{0}} M_{2}, is the structure whose universe is M_{1} ∪ M_{2} and whose set of links is the union of the set of links of M_{1} and of the set of links of M_{2}.

If M_{1} ∩M_{2} ≠ M_{0}, then M_{1} ∗_{M_{0}} M_{2} is defined up to M_{0}-isomorphism, and is equal to M′_{1} ∗_{M_{0}} M′_{2} where M′_{1} and M′_{2} are extensions of M_{0} which are respectively M_{0}-isomorphic to M_{1} and M_{2} and such that M′_{1} ∩ M′_{2} = M_{0}.

Now come the main devices of the proof.

Definition 5.3 1) Let A be a structure. A short extension of A is a structure which can be written as A ∗_{A_{0}} C where A_{0} is a small substructure of A or the empty set, and C is an extension of A_{0} which is also small.

2) Let D ⊆ A. A short extension is based on D if it can be written as A ∗_{A_{0}} C as above, with the requirement A_{0} ⊆ D.

3) Let A ⊆ B be two L-structures. We say that B is a strong extension of A if, for all short extension C of A, if there exists h : C ⟶_{w,A} B, then there exists h′ : C ⟶_{w,A} A. To denote that B is

a strong extension of A, we will write A ⊆_{s} B.

4) Let A and B be two L-structures and p a partial isomorphism from A to B with domain D ⊆ A and image D′ ⊆ B. We say that p is strong in (A, B) if for every short extension D_{1} of D and k : D_{1} ⟶_{w,D} A, there exists p′ : D_{1} ⟶_{w} B such that p′ extends p, and conversely, for every

short extension D′_{1} of D′ and k′ : D′_{1} ⟶_{w,D′} B, there exists p′ : D′_{1} ⟶_{w} A such that p′ extends p^{−1}.

Remark for 1): A priori, the structures A_{0} and C are not uniquely determined. But there is a kind of canonical decomposition of a short extension B: set C_{1} = B − A and

A_{1} = {a ∈ A; a is linked with an element of C_{1}}.

From the definition, it should be clear that, if B = A ∗_{A_{0}} C, then A_{1} ⊆ A_{0}, A_{1} ∪ C_{1} ⊆ C and B = A ∗_{A_{1}} (A_{1} ∪ C_{1}). It is this decomposition which will be used implicitly when a decomposition is needed.

It should be remarked that, in the above definition 2), the fact that p is strong does not depend only on p itself, but also on the way that D and D′ sit in A and B respectively. That is why we add “in (A, B)”. If p ∈ Part(A, A), we will say “p is strong in A” instead of “p is strong in (A, A)”.

The following facts are easy to prove:

Lemma 5.4 1. If A is T -free and A ⊆_{s} B is a strong extension of A, then B is T -free.

2. If B ⊆ B_{1}, then B ⊆_{s} B_{1} if and only if for every small structure C ⊆ B_{1}, there exists

h : C ⟶_{w,B∩C} B.

3. If A ⊆_{s} B and B ⊆_{s} C, then A ⊆_{s} C.

4. If A ⊆_{s} B and A ⊆ C ⊆ B, then A ⊆_{s} C.

5. If p ∈ Part(A, A) is strong in A and A ⊆_{s} B, then p is strong in B

6. If B is a short extension of A, then A ⊆_{s} B if and only if there exists h : B ⟶_{w,A} A.

7. If B is a short extension of A and B = A ∗_{A_{0}} C (where A_{0} and C are small structures), then A ⊆_{s} B if and only if there exists h : C ⟶_{w,A_{0}} A.

8. Assume that A ⊆_{s} B, A ⊆ B′ h : B′ ⟶_{w,A} B. Then A ⊆_{s} B′.

9. If A ⊆_{s} B and A ⊆ C, then C ⊆_{s} B ∗_{A} C.

10. If A ⊆_{s} B and A ⊆_{s} C, then A ⊆_{s} B ∗_{A} C.

We now get to our second reduction step:

Proposition 5.5 Let T be a finite set of small structures, A be a finite T -free structure and p_{1}, p_{2}, …, p_{n} be partial automorphisms of A. Suppose that the p_{i} are strong in A. Then there exists a finite T -free structure B extending A and automorphisms β_{1}, β_{2}, …, β_{n} ∈ Aut(B) extending respectively p_{1}, p_{2}, …, p_{n}.

Proof. We show how to deduce proposition 5.1 from proposition 5.5. Let M and α_{i} as in the hypothesis of proposition 5.1. The point is that, even if the p_{i} are not strong in A, they are obviously strong in M.

For all i between 1 and n, let D_{i} be the domain of p_{i} and D′_{i} its image. Obviously, there is only a finite number of short extensions of D_{i}, up to D_{i}-isomorphism. Thus we may find a finite structure B_{i}, A ⊆ B_{i} ⊆ M such that: for every short extension E of D_{i} and k : E ⟶_{w,D_{i}} M, there

exists k′ : E ⟶_{w,D_{i}} B_{i}. Thus if C_{i} is any substructure of M containing B_{i} and α_{i} [B_{i}], we see that

the following is true: for every short extension E of D_{i} and k : E ⟶_{w,D_{i}} M, p_{i} can be extended to

a weak homomorphism from E to C_{i}. Repeating the operation for D′_{i} in place of D_{i}, and then for all i, 1 ≤ i ≤ n, we get a finite substructure C in which all the p_{i} are strong. Then we may apply proposition 5.5 to get the structure B.

♡

The next reduction tells us that we can work sort by sort.

Proposition 5.6 Let A be a finite structure and p_{1}, p_{2}, …, p_{n} be elements of Part(A, A), and suppose that the p_{i} are strong in A. Fix an integer j, 1 ≤ j ≤ k. There exist a finite strong extension B of A and partial automorphisms q_{1}, q_{2}, …, q_{n} ∈ Part(B, B) extending respectively p_{1}, p_{2}, …, p_{n} such that all the q_{i} are strong in B and induce a permutation on U_{j}^{B}.

Proof. We prove Proposition 5.5 using Proposition 5.6. So we start with the hypothesis of Proposition 5.5. We define a sequence of finite structures A = A_{0} ⊆_{s} A_{1} ⊆_{s} … ⊆_{s} A_{k}, and we extend successively the partial automorphisms p_{i}^{0} = p_{i}: p_{i}^{0} ⊆ p_{i}^{1} ⊆ … ⊆ p_{i}^{k}, p_{i}^{j} ∈ Part(A_{j}, A_{j}) such that p_{i}^{j} is strong in A_{j}. Furthermore for j ≥ 1, p_{i}^{j} induces a permutation on U_{j}^{A_{j}}. Clearly, Proposition 5.6 allows us to do that. Next we take C to be A ∪ U_{1}^{A_{1}} ∪ U_{2}^{A_{2}} ∪ … ∪ U_{k}^{A_{k}} ⊆ A_{k} and take r_{i} to be the restriction of p_{i}^{k} to C. It is a partial automorphism on C and for 1 ≤ j ≤ k, r_{i} induces a permutation on U_{j}^{C} = U_{j}^{A_{j}}. Since A_{k} is a strong extension of A, it is T -free, and so is C.

It remains to take care of U_{0}. By Corollary 4.13, we can find a finite L–structure B extending C, and automorphisms α_{i} of B extending the r_{i}. By proposition 2.3 we can take (B, α_{1}, α_{2}, …, α_{n}) to be a slim extension of (C, r_{1}, …, r_{n}), which is automatically stretched.

Write G for the group of automorphisms of B generated by {α_{1}, …, α_{n}}. For 1 ≤ j ≤ k, if b ∈ U_{j}^{B}, there exist c ∈ U_{j}^{C} and β ∈ G such that b = β(c). Since each β ∈ G induces a permutation on U_{j}^{C}, we see that b ∈ U_{j}^{C}, so U_{j}^{C} = U_{j}^{B}.

We have to prove that B is T –free. The fact that B is a slim extension implies: for b ∈ U_{0}^{B} there exists β ∈ G such that β(b) ∈ U_{0}^{C}. Suppose now that there exist T ∈ T and r a weak homomorphism from T to B. T is a small stretched structure. If U_{0}^{T} = ∅ then r is a weak homomorphism from T to ⋃{U_{j}^{B}; 1 ≤ j ≤ s}, and this is impossible since C is T -free. If U_{0}^{T} has one element, say t then we choose γ ∈ G such that γ ∘ r(t) ∈ U_{0}^{C} and then γ ∘ r is a weak homomorphism from T to C, which is again impossible.

♡

5.3 Types

To simplify the notation slightly, we prove proposition 5.6 for j = 1. Given a ∈ U_{1}^{A} and concentrating on a partial automorphism, say p_{1}, the first step is to find an image for a, that is an element b in some extension B of A such that, if we extend p_{1} to q_{1} by setting: q_{1}(a) = b, then q_{1} is still a strong partial automorphism of B. Intuitively, the conditions to be satisfied by this element b are: 1) (for q_{1} to be a partial automorphism) the relations between b and D′_{1} (the image of p_{1}) should be exactly the image of the relations existing between a and D_{1} (the range of p_{1}); 2) (for q_{1} to be a strong partial automorphism) for every small substructure C of A containing a, there should be in B a small substructure C′of B containing b, and a weak homomorphism sending C to C′ extending q_{1}; 3) same as 2), permuting the roles of a and b and replacing q_{1} by q_{1}^{−1}. That is where the notion of type comes in: the type of a over D is meant to collect the necessary data.

For the rest of the proof, when considering a short extension B of A, we will implicitly assume that there is a (unique) element in U_{1}^{B} not in A. We will denote this element u(B).

We can preorder the set of short extensions of A in the following way: given B and C two such extensions, we write B ≤ C if there exists a weak A-homomorphism h from B into C such that h(u(B)) = u(C). It is obviously a reflexive and transitive relation (but not antisymmetric in general, so it is just a preordering).

To define the type of an element b of B, we need to consider the short extensions C of A such that there exists h : C ⟶_{w,A} B such that h(u(C)) = b. To deal only with a finite number of them,

we will consider a finite set S of short extensions of A, such that, for all short extensions C of A, C is A-isomorphic to one and only one element of S. Moreover, we will choose an element x which does not belong to A and assume that, for all C ∈ S, u(C) = x, and that for all C, C′ ∈ S, if C ≠ C′, then C ∩ C′ = A ∪ {x}.

Definition 5.7 Let B is be strong extension of A and b ∈ U_{1}^{B}. Then:

• Γ_{B}(b) is the extension of A whose universe is A ∪ {x} and such that, for all R ∈ L, R different from the equality, and for all sequences ā_{1}, ā_{2} from A, Γ_{B}(b) ⊧ Rā_{1}xā_{2} if and only if B ⊧ Rā_{1}bā_{2};

• E_{B}(b) is the set {C ∈ S; there exists h : C ⟶_{w,A} B such that h(x) = b}.

More generally, if D ⊆ A, we define:

• Γ_{B}(b/D) is the structure whose base set is A ∪ {x} and such that, for every R ∈ L and sequence ā from A ∪ {x}, Γ_{B}(b/D) ⊧ Rā if and only if Γ_{B}(b) ⊧ Rā and either all the elements of ā belong to D ∪ {x} or all elements of ā belong to A.

• E_{B}(b/D) = {C ∈ E_{B}(b); C is based on D}.

Lemma 5.8 Let D ⊆ A ⊆_{s} B ⊆_{s} B′. Let b ∈ U_{1}^{B}. Then Γ_{B}(b) = Γ_{B′}(b), Γ_{B}(b/D) = Γ_{B′}(b/D), E_{B}(b) = E_{B′}(b), E_{B}(b/D) = E_{B′}(b/D)

Proof. It is clear that Γ_{B}(b) = Γ_{B′}(b) and that Γ_{B}(b/D) = Γ_{B′}(b/D). We prove E_{B}(b) = E_{B′}(b) (the fourth equality follows immediately). Again, it is clear that E_{B}(b) ⊆ E_{B′}(b). So, let C ∈ E_{B′}(b), and let us prove C ∈ E_{B}(b). We may decompose C: C = A ∗_{A_{0}} C_{0}, where A_{0} and C_{0} are small structures, and we know that there exists h : C_{0} ⟶_{w,A_{0}} B′ with h(x) = b. Let C_{1} = h [C_{0}] and

C_{2} = C_{1} ∩ B. Thus b ∈ C_{2} and A_{0} ⊆ C_{2}. Since B ⊆_{s} B′, there exists h_{1} : C_{1} ⟶_{w,C_{2}} B, and

h_{1} ∘ h : C_{0} ⟶_{w,A_{0}} B, and this proves that C ∈ E_{B}(b).

♡

Assume that B is a short extension of A based on D ⊆ A, let p be a strong partial automorphism of A whose domain contains D, and let D′ = p [D]. We define an extension p(B) of A as follows: say that B = A∗_{A_{0}} C_{0} according to Definition 5.3 (where A_{0} ⊆ D). Let A′_{0} = p [A_{0}]. It is clear that we can find a small structure C′_{0} containing A′_{0} and an isomorphism g from C_{0} onto C′_{0} extending p_{|A_{0}}, and moreover we may assume that A ∩ C′_{0} = A′_{0}. By definition p(B) = A ∗_{A′_{0}} C′_{0}. One should consult the remark following Definition 5.3 to be sure that this definition is legal (that is, does not depend on the particular A_{0} chosen). Moreover, we may assume that, if B ∈ S, then p(B) ∈ S.

Lemma 5.9 With the above hypothesis, and supposing moreover that B is a strong extension of A, p(B) is a strong extension of A based on D′.

Proof. It suffices to show that there is a weak A-homomorphism from p(B) into A. We use the notations of the previous paragraph: p(B) = A ∗_{A′_{0}} C′_{0} and g is the isomorphism from C_{0} to C′_{0}. It is enough to show that there is a weak A′_{0}-homomorphism from C′_{0} into A.

Because B is a strong extension of A, there exists a weak A-homomorphism from B to A, so there exits h : D ∗_{A_{0}} C_{0} ⟶_{w,D} A. Since p is strong, p can be extended to a weak homomorphism k

from D ∗_{A_{0}} C_{0} into A. Then k_{|C_{0}} ∘ g^{−1} is a weak A′_{0}-homomorphism from C′_{0} into A.

♡

Lemma 5.10 Let B and C be two short extensions of A based on D and p a strong partial automorphism of A of domain D. Then B ≤ C if and only if p(B) ≤ p(C).

Proof. Since p^{−1}(p(B)) = B and p^{−1}(p(C)) = C, it suffices to prove that, if B ≤ C, then p(B) ≤ p(C).

We need some notation: let D′ be the image of p, so that p is an isomorphism from D to D′. We may write B = A ∗_{B_{2}} B_{1}, where B_{2} ⊆ B_{1} are small structures and B_{2} ⊆ D. Similarly C = A∗_{C_{2}} C_{1}. Set B′ = p(B) and C′ = p(C). Let B′_{2} = p[B_{2}] and B′ = A∗_{B′_{2}} B′_{1} and g : B_{1} ⟶ B′_{1} be the isomorphism given by the definition of p(B). Let F = C_{1} ∪ D so that C = A ∗_{D} F. We can write C′ = A ∗_{D′} F′ and f : F ⟶ F′ is an isomorphism extending p. We have to show that there exists k_{1} : B′ ⟶_{w,A} C′; it suffices to find k : B′_{1} ⟶_{w,B′_{2}} C′ with k(u(B′)) = u(C′).

As B ≤ C there exists h_{1} : B ⟶_{w,A} C such that h(u(B)) = u(C). Let h = (h_{1})_{|B_{1}}, h : B_{1} ⟶_{w,B_{2}} C.

Let E_{1} = h^{−1}(A), E_{2} = h^{−1}(F), E_{3} = h^{−1}(D). As C = A ∗_{D} F and h is a weak homomorphism we have B_{1} = E_{1} ∗_{E_{3}} E_{2}. The structure G = D ∗_{h[E_{3}]} h[E_{1}] is a small extension of D. Because p is strong there exists r : G ⟶_{w} A, r extending p. Now we are gluing together f_{|h[E_{2}]} ∘ h_{|E_{2}} and

r_{|h[E_{1}]} ∘h_{|E_{1}} which coincides on E_{3} with p_{|h[E_{3}]} ∘h_{|E_{3}} to get g′ : B_{1} ⟶_{w} C′. Finally let k = g′ ∘g^{−1},

k : B′_{1} ⟶_{w,B′_{2}} C′.

♡

Now, suppose that D ⊆ A ⊆_{s} B, that p is a strong partial automorphism of A of domain D and image D′ and that b ∈ U_{1}^{B}. We may define p(E_{B}(b/D)) as {p(C); C ∈ E_{B}(b/D)}. We may also define p(Γ_{B}(b/D)): it is the structure whose base set is A ∪ {x} and such that, for every R ∈ L and sequence ā from A ∪ {x}, p(Γ_{B}(b/D)) ⊧ Rā if and only if one of the two following cases holds:

1. all the elements of ā belong to A and A ⊧ Rā or

2. all elements of ā belong to D′ ∪ {x}, say to simplify that ā = ā′x, where ā′ is a sequence from D′, and Γ_{B}(b/D) ⊧ Rp^{−1}(ā′)x.

The next lemma shows that, as announced, we have collected the relevant information.

Lemma 5.11 Let p be a strong partial automorphism of A with domain D and image D′. Let B be a strong extension of A, and let a and a′ be elements of U_{1}^{B}, a ∉ D and a′ ∉ D′. Define a map q with domain D ∪ {a} by: q_{|D} = p and q(a) = a′. Then q is a strong partial automorphism if and only if p(Γ_{B}(a/D)) = Γ_{B}(a′/D′) and p(E_{B}(a/D)) = E_{B}(a′/D′).

Proof. It follows immediately from the definitions that q is a partial automorphism if and only if p(Γ_{B}(a/D)) = Γ_{B}(a′/D).

Suppose first that q is strong. Let C ∈ E_{B}(a/D). Let C = A ∗_{A_{0}} C′, where C′ is a small structure including A_{0}, and A_{0} ⊆ D. By definition, p(C) = A ∗_{A′_{0}} C′′, where A′_{0} = p [A_{0}] and C′ is isomorphic to C′′, via an isomorphism p^{∗} extending p_{|A_{0}} and such that p^{∗}(x) = x.

Since C ∈ E_{B}(a/D), there exists h : C′ ⟶_{w,A_{0}} B such that h(x) = a. Since q is strong,

there exists a weak homomorphism h′ from C′ into B, extending q_{|A_{0}} and such that h′(x) = a′. Thus, if we set k = h′ ∘ p^{∗−1}, k is a weak A′_{0}-homomorphism from C′′ into B, and k(x) = a′.

This proves that p(C) ∈ E_{B}(a′/D′). So p(E_{B}(a/D)) ⊆ E_{B}(a′/D′), and, for the same reason, E_{B}(a′/D′)) ⊆ p(E_{B}(a/D)).

Conversely, suppose that p(E_{B}(a/D)) = E_{B}(a′/D′). Assume that C is a short extension of D ∪ {a}, and h : C ⟶_{w,D∪{a}} B. As usual C can be written as (D ∪ {a}) ∗_{A_{0}} C′. If a ∉ A_{0}, we

may assume that a ∉ C′. Because p is strong, there exists a weak homomorphism k from C′ into B extending p_{|A_{0}}. Then the map from (D ∪ {a}) ∗_{A_{0}} C′ into B extending both k and q is a weak homomorphism, so there exists a weak homomorphism from C to B extending q.

If a ∈ A_{0}, let A_{1} = A_{0} − {a} and A′_{1} = p[A_{1}]. Obviously, h is also a weak D-homomorphism from C to B. Intuitively, this implies that A∗_{A_{1}} C′ belongs to E_{B}(a/D). More precisely, there exist C_{1} = A ∗_{A_{1}} C′_{1} ∈ E_{B}(a/D) and an A_{1}-isomorphism k from C′ onto C′_{1} satisfying k(a) = x. Let p(C_{1}) = A ∗_{A′_{1}} C′_{2} and let p^{∗} denote the isomorphism from C′_{1} onto C′_{2} extending p_{|A_{1}} satisfying and p^{∗}(x) = x. Since p(C_{1}) ∈ p(E_{B}(a/D)) = E_{B}(a′/D′), there exists a weak homomorphism k′ : C′_{2} ⟶_{w,A′_{1}} B such that k′(x) = a′. Then p_{1} = k′ ∘ p^{∗} ∘ k : C′ ⟶_{w} B extends p_{|A_{1}} and satisfies

p_{1}(a) = a′. Thus, the map from C into B which extends both p_{1} and q is a weak homomorphism and it is exactly what we had to find.

♡

Definition 5.12 Let A ⊆ B be two structures. We say that B is irreducible over A if, whenever B is isomorphic to B_{1} ∗_{A} B_{2}, one of the structures B_{1} or B_{2} is equal to B.

So, B irreducible over A exactly means that B − A is not the disjoint union of two non empty subsets B_{1} and B_{2} such that there is no link containing an element of B_{1} and an element of B_{2}.

Definition 5.13 Let A be a finite structure. A tiny extension of A is a short and strong extension B of A which is irreducible over A.

Lemma 5.14 Suppose B is a tiny extension of A based on D and that p is a strong partial automorphism of A of domain D and image D′. Then p(B) is a tiny extension of A based on D′.

Proof. To prove that p(B) is irreducible use the remark after Definition 5.12.

♡

Definition 5.15 Let D ⊆ A ⊆_{s} B and b ∈ U_{1}^{B}. Then the type of b in B over D is the pair (Γ_{B}(b/D), E_{B}^{irr}(b/D)) where E_{B}^{irr}(b/D) is the set of maximal elements (for the ordering >) of the set

{C; C ∈ E_{B}(b/D) and C is irreducible}.

We will denote t_{B}(b/D) this type. From Lemma 5.8, it follows that if B′ is a strong extension of B, then t_{B}(b/D) = t_{B′}(b/D).

Lemma 5.16 D ⊆ A ⊆_{s} B and b ∈ U_{1}^{B}, and let C be a short extension of A. Then C ∈ E_{B}(b/D) if and only if there exists C′ ∈ E_{B}^{irr}(b/D) such that C ≤ C′.

Proof. One direction is clear: if C′ ∈ E_{B}^{irr}(b/D) and C ≤ C′, then C ∈ E_{B}(b/D). Conversely, let C ∈ E_{B}(b/D). We can write C as C_{1} ∗_{A} C_{2} where C_{1} is a tiny extension of A and C_{2} is a short extension of A such that C_{2} − A contains no point in U_{1}. Clearly C_{1} ∈ E_{B}(b/D), so there exists C′ ∈ E_{B}^{irr}(b/D) such that C_{1} ≤ C′. As A ⊆_{s} B there exists h : C_{2} ⟶_{w,A} A and thus C ≤ C_{1}.

♡

Definition 5.17 A type is an object of the form t_{B}(b/A), where A ⊆_{s} B and b ∈ B. A type based on D (where D is a subset of A) is an object of the form t_{B}(b/D).

These definitions are justified by the following lemma:

Lemma 5.18 Let D ⊆ A ⊆_{s} B and b ∈ U_{1}^{B}; then t_{B}(b/D) is a type.

Proof. Let B^{∗} be an isomorphic copy of B: its universe is B^{∗} = {a^{∗} ; a ∈ B}, B ∩ B^{∗} = ∅ and the map α from B onto B^{∗} defined by α(a) = a^{∗} is an isomorphism. Let B_{1} = A ∪ B^{∗} and let h be the map from B_{1} on B defined by: for all a ∈ A, h(a) = a and for all a ∈ B : h(a^{∗}) = a. We endow B_{1} with an L-structure by setting: for R an n-ary predicate symbol and a_{1}, a_{2},…, a_{n} elements in B_{1}, B_{1} ⊧ Ra_{1}a_{2} … a_{n} if and only if B ⊧ R h(a_{1}) h(a_{2}) … h(a_{n}) and either all the a_{i} belong to A or all the a_{i} belong to B^{∗} ∪ D. With this definition, we see that B_{1} is an extension of both A and B^{∗}, and that h is a weak A-homomorphism from B_{1} to B, so by Lemma 5.4 B_{1} is a strong extension of A.

We want to check that t_{B_{1}}(b^{∗}/A) = t_{B}(b/D). It is quite clear that Γ_{B_{1}}(b^{∗}/A) = Γ_{B}(b/D).

Let t_{B_{1}}(b^{∗}/A) = (Γ, E), and C ∈ E (so C is a maximal irreducible element of E_{B_{1}}(b^{∗}/A)). In order to show that C is based on D, we need the two following general lemmata:

Lemma 5.19 Let C be a tiny extension of A, and assume that h : C ⟶_{w,A} C. Then h is the identity

or h[C] = A.

Proof. Write C = A ∗_{A_{0}} C′ where C′ is a small structure, and split the set C − A in two sets: C_{1} = {a ∈ C − A ; h(a) = a} and C_{2} = {a ∈ C − A ; h(a) ∈ A}. We have to prove that one of the sets C_{1} or C_{2} is empty.

If not, since C is irreducible, there is a link containing an element a ∈ C_{1} and an element b ∈ C_{2}. Thus, there is also a link containing a and c = h(b). We see that b and c are distinct elements, both linked to a, so both belong to C′, and belong to the same level U_{i}: this contradicts the fact that C′ is small.

♡

As a corollary, we see that the preordering < when restricted to the set of tiny extensions in S is an ordering.

Lemma 5.20 Let A ⊆_{s} B, b ∈ B −A and t_{B}(b/A) = (Γ, E). Let C ∈ E. So C is a short extension of A and there exists k : C ⟶_{w,A} B such that k(x) = b. Then, for every c ∈ C − A, k(c) ∉ A.

Proof. : Write C = A ∗_{A_{0}} C′ where C′ is a small structure. Assume for a contradiction that there exists k : C′ ⟶_{w,A_{0}} B with k(x) = b and c ∈ C′ − A with k(c) ∈ A. Choose k such

that the set X = {c ∈ C′ − A ; k(c) ∈ A} is maximal. Let C′_{1} = k[C′] and A′_{1} = C′_{1} ∩ A. Intuitively this implies that C_{1} = A ∗_{A′_{1}} C′_{1} belongs to E_{B}(b/A). More precisely there exists a small structure C′_{2} containing A′_{1} and x, and an A′_{1}-isomorphism k′ from C′_{1} to C′_{2} satisfying k′(b) = x such that A ∗_{A′_{1}} C′_{2} ∈ E_{B}(b/A). Let C_{2} = A ∗_{A′_{1}} C′_{2}. Let us first check that C′_{1} is irreducible over A′_{1}: suppose not, say C′_{1} = C_{3} ∗_{A′_{1}} C_{4} with A′_{1} ⊊ C_{3} and A′_{1} ⊊ C_{4}. Let us say b ∈ C_{3}. As A ⊆_{s} B there exists h : C_{4} ⟶_{w,A′_{1}} A. Let h′ : C′_{1} ⟶_{w,A′_{1}} B be the homomorphism

which coincides with h on C_{4} and is the identity on C_{3}. Then h′ ∘ k contradicts the choice of k as {c ∈ C − A ; k(c) ∈ A} ⊊ {c ∈ C − A ; h′ ∘ k(c) ∈ A}. Thus C′_{1} is irreducible over A′_{1}, i.e. C_{1} is irreducible over A. Thus C_{2} is irreducible over A and in E_{B}(b/A). Let ℓ : C ⟶_{w,A} C_{1} and ℓ′ : C_{1} ⟶_{w,A} C_{2} be the extension of k and k′ respectively by the identity on A. As ℓ′ ∘ ℓ : C ⟶_{w,A} C_{2}

and ℓ′ ∘ ℓ(x) = x, we have C ≤ C_{2}. Now, since C is maximal among the irreducible elements of E_{B}(b/A), we see that there exists k_{1} : C_{2} ⟶_{w,A} C with k_{1}(x) = x, so, by the previous lemma, ℓ′ ∘ ℓ

is injective, a contradiction.

♡

Now, we go back to C ∈ E. We know that there exists k : C ⟶_{w,A} B_{1}, with k(x) = b^{∗}. From the

preceding lemma, we see that the elements of C − A are mapped by k to elements of B^{∗}, so there is no link containing an element of C − A and an element of A − D. This implies that C is based on D (see the remark following Definition 5.3).

To conclude, we see that

E_{B}(b/D) ⊆ E_{B_{1}}(b^{∗}/A) ⊆ E_{B}(b/A)

The first inclusion comes from the fact that if C ∈ E_{B}(b/D) and k : C ⟶_{w,A} B with k(x) = b, then

the map k′ from C to B defined by: k′(y) = y for y ∈ A and k′(y) = (k(y))^{∗} for y ∈ C −A is a weak A-homomorphism and k′(x) = b^{∗}. The second inclusion is true because there exists h : B_{1} ⟶_{w,A} B

with h(b^{∗}) = b. Now it is easy to check that t_{B}(b/D) = t_{B_{1}}(b^{∗}/D).

♡

Let t = t_{B}(b/D) = (Γ, E) be a type based on D ⊆ A, and let p be a strong partial automorphism of A whose domain contains D. Then we define p(t) to be the pair (p(Γ), p(E)), where p(E) is the set {p(B) ; B ∈ E}. It is easy to prove that if b ∈ D, then p(t_{B}(b/D)) = t_{B}(p(b)/D′). It is also important to notice:

Lemma 5.21 With these notations, p(t) is a type.

Proof. Let D′ = p[D]. First we may assume that b ∉ D (if not, p(t) = t_{B}(p(b)/D′)). Let B^{∗} be, as above, an isomorphic disjoint copy of B. Let B_{1} = B ∪ B^{∗} and h be the map from B^{∗} ∪ D′ to B such that: for a ∈ B, h(a^{∗}) = a and for a ∈ D′, h(a) = p^{−1}(a). Now, we define another structure on B_{1}: if R is a n-ary predicate symbol and a_{1}, a_{2}, …, a_{n} are elements of B_{1}, B_{1} ⊧ Ra_{1}a_{2} … a_{n} if and only if either all the a_{i} belong to B and B ⊧ Ra_{1}a_{2} … a_{n}; or all the a_{i} belong to B^{∗} ∪ D′ and B ⊧ R h(a_{1}) h(a_{2}) … h(a_{n}). Our aim is to prove t_{B_{1}}(b^{∗}/D′) = p(t).

To prove A ⊆_{s} B_{1}, by Lemma 5.4, it suffices to prove that B ⊆_{s} B_{1}, and, again by Lemma 5.4, that, if C is a small structure of B_{1}, then there exists k : C ⟶_{w,B∩C} B. Let A_{0} = C ∩ D′,

A_{1} = C ∩ B, A_{2} = C ∩ (B^{∗} ∪ D′). By definition of B_{1}, there is no link containing an element of A_{1} −A_{0} and an element of A_{2} −A_{0}. Thus C = A_{1} ∗_{A_{0}} A_{2} and it suffices to find k_{1} : A_{2} ⟶_{w,A_{0}} B. It is

clear, from the definition of B_{1} again, that h is a weak homomorphism. Let A_{3} = h[A_{2}] and k_{2} be the restriction of h to A_{2}. Because p is strong, we know that there exists a weak homomorphism k_{3} from A_{3} to B extending p on A_{3} ∩ D. Set k_{1} = k_{3} ∘ k_{2}. Then k_{1} : A_{2} ⟶_{w,A_{0}} B as required.

As a matter of fact, a similar argument proves that E_{B_{1}}(b^{∗}/D′) ⊆ p(E_{B}(b/D)). Conversely, let C be a short extension of A based on D and k : C ⟶_{w,A} B such that k(x) = b. Set C′ = p(C). Since

C′ is based on D′, there is no link of C′ containing an element of C′ − A and an element of A − D′. We let g be the bijection from C − A to C′ − A witnessing p(C) = C′. Thus the map k_{1} defined by: k_{1}(y) = y if y ∈ A and k_{1}(y) = (k(g^{−1}(y)))^{∗} if y ∈ C′ − A is a weak A-homomorphism from C′ to B_{1} and k_{1}(x) = b^{∗}. Consequently, p(E_{B}(b/D)) ⊆ E_{B_{1}}(b^{∗}/D′). Lemma 5.10 and Lemma 5.14 now imply p(t_{B}(b/D)) = t_{B_{1}}(b^{∗}/D′).

♡

As in Lemma 5.11, we see that t_{B}(b/D) carries enough information:

Lemma 5.22 Let p be a strong partial automorphism of A with domain D and image D′. Let B be a strong extension of A and let a and a′ be elements of U_{1}^{B}, a ∉ D and a′ ∉ D′. Define a map q with domain D ∪ {a} by: q_{|D} = p and q(a) = a′. Then q is a strong isomorphism if and only if t_{B}(a′/D′) = p(t_{B}(a/D)).

Proof. One direction is clear: if q is strong, then, by Lemma 5.11, E_{B}(a′/D′) = p(E_{B}(a/D)), and t_{B}(a′/D′) = t_{B}(a/D). Conversely, we have to prove that E_{B}(a′/D′) = p(E_{B}(a/D)), assuming that E_{B}^{irr}(a′/D′) = p(E_{B}^{irr}(a/D)). But this is a direct consequence of Lemma 5.16.

♡

We are now ready to state the next reduction.

Proposition 5.23 Let A be a finite structure and let p_{1}, p_{2}, …, p_{n} ∈ Part(A, A), and suppose that the p_{i} are strong in A. Write D_{i} for the domain of p_{i} and D′_{i} for its image. There exists a finite strong extension B of A such that, for every i, 1 ≤ i ≤ n, and for every type t based on D_{i}, the sets {b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = t} and {b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = p_{i}(t)} have the same cardinality.

Proof. Fix i, 1 ≤ i ≤ n. We first remark that for every type t based on D_{i}, the sets {b ∈ U_{1}^{B} −D_{i}; t_{B}(b/D_{i}) = t} and {b ∈ U_{1}^{B} −D′_{i}; t_{B}(b/D′_{i}) = p_{i}(t)} have the same cardinality. Thus, it is possible to extend p_{i} to an injective map g_{i} from D_{i} ∪ U_{1}^{B} onto D′_{i} ∪ U_{1}^{B} such that, for all b ∈ U_{1}^{B}, t_{B}(g_{i}(b)/D′_{i}) = p_{i}(t_{B}(b/D_{i})). By Lemma 5.22, for every b ∈ U_{1}^{B} we have that (h_{i})_{|D_{i}∪{b}} is a strong partial automorphism of B. But this easily implies that h_{i} is a strong partial automorphism of B as every small structure contains at most one point in U_{1}.

♡

5.4 The weight of a type

Now, we must face the following problem. We want to find a strong extension B of A satisfying the conclusion of Proposition 5.23. Suppose, for example, that the cardinality of the set {b ∈ U_{1}^{A} ; t_{A}(b/D_{i}) = t}, where t is a type based on D_{i}, is smaller than the cardinality of {b ∈ U_{1}^{A} ; t_{A}(b/D′_{i}) = p_{i}(t)}. It is fairly easy to increase the cardinality of the set {b ∈ U_{1}^{A} ; t_{A}(b/D_{i}) = t} by one, and eventually to get a strong extension where the cardinality of these two sets are the same. But, we cannot perform such an operation simultaneously for all types and for all partial automorphisms, because when taking care of another partial automorphism p_{j}, we may destroy what we have done for p_{i}. It is to control this phenomenon that we need the notion of weight.

Let C be a tiny extension A. We define:

• n(C) the number of links of C which are not links of A.

• If a ∈ C−A, we define the height of a inductively: h(a) = 0 if and only if a ∈ U_{1}^{C}; h(a) = n+1 if there is a link containing a and an element b ∈ C − A such that h(b) = n (and the height of a has not been already defined).

Because C is irreducible over A, we know that every element of C − A has a height. Now we define

• the height of C, h(C) = max(h(a); a ∈ C − A)

• h_{0} = max(h(C); C is a tiny extension of A).

• For i, 0 ≤ i ≤ h_{0}, w_{i}(C) is the number of elements a ∈ A such that there exist b ∈ C − A with h(b) ≤ i and a link containing a and b.

• The weight of C is the sequence w(C) = ((w_{0}(C), w_{1}(C), …, w_{h_{0}}(C), card(C − A), n(C)) ordered lexicographically.

Lemma 5.24 1) Assume that C ≤ B. Then w(C) ≤ w(B) and if w(C) = w(B), then C and B are isomorphic.

2) If B is based on D ⊆ A and p is a partial automorphism of A of domain D, then w(B) = w(p(B)).

Proof. 1.) Let k : C ⟶_{w,A} B such that k(u(C)) = u(B). If a ∈ A is linked to u(C) (in C), it is

linked (in B) to u(B). Thus w_{0}(C) ≤ w_{0}(B). Moreover, suppose that c ∈ C − A has height 1 and k(c) ∈ A. Then w_{0}(C) < w_{0}(B). Indeed, there is a link between u(C) and c (because c has height 1), thus there is a link between u(B) and k(c). But since c and k(c) belong to the same U_{i}, there is no link between u(C) and k(c). Thus there is at least one element of A which is linked to u(B) (in B), but not to u(C).

Thus, if w_{0}(C) = w_{0}(B) and c ∈ C − A has height 1, k(c) ∈ B − A, and of course, has height 1. We can continue and prove in the same way that w_{1}(B) ≤ w_{1}(C) and if w_{1}(B) = w_{1}(C) and c ∈ C − A has height 2, then k(c) ∈ B − A and h(k(c)) ≤ 2. After h_{0} steps, we get that either

(w_{0}(C), w_{1}(C), …, w_{h_{0}}(C)) < (w_{0}(B), w_{1}(B), …, w_{h_{0}}(B))

or

(w_{0}(C), w_{1}(C), …, w_{h_{0}}(C)) = (w_{0}(B), w_{1}(B), …, w_{h_{0}}(B))

and that k is injective. The first part follows easily.

2) is clear from the definitions.

♡

Definition 5.25 Suppose t = (Γ, E) and t′ = (Γ′, E′) are two types. Then:

t ≤ t′ if the identity map from Γ to Γ′ is a weak homomorphism and, for every C ∈ E, there exists C′ ∈ E′ such that C ≤ C′.

We will need the following easy facts.

Lemma 5.26 Let D ⊆ A ⊆_{s} B, t and t′ be types based on D.

1) t ≤ t′ and t′ ≤ t implies t = t′.

2) For b ∈ B we have: t_{B}(b/A) ≥ t if and only if t_{B}(b/D) ≥ t.

The next definition will give an order homomorphism from the partial order of all types over A into a total order.

Definition 5.27 Let t = (Γ, E) be a type. The weight of t is the sequence w(t) = (n_{0}, n_{1}, …, n_{m}) where: n_{0} is the number of links of the structure Γ, and (n_{1}, n_{2}, …, n_{m}) is the weakly decreasing sequence (that is such that n_{1} ≥ n_{2} ≥ … ≥ n_{m}) of the form (w(C_{1}), w(C_{2}), …, w(C_{m})), where E = {C_{1}, C_{2}, …, C_{m}}. These sequences are ordered lexicographically by ≤.

Lemma 5.28 Let t and t′ be two types.

1) Assume that t ≤ t′. Then w(t) ≤ w(t′) and if w(t) = w(t′), then t = t′.

2) If t is based on D ⊆ A and p is a partial automorphism with domain D, then w(t) = w(p(t)).

Proof. Again, 2) follows immediately from the definitions. Set t = (Γ, E), t′ = (Γ′, E′). The identity map from Γ to Γ′ is a bijective weak A-isomorphism, and, if it not an isomorphism, there are strictly more links in Γ than in Γ′, and w(t) < w(t′).

So, suppose that Γ = Γ′. Let E = {C_{1}, C_{2}, …, C_{m}}, E′ = {C′_{1}, C′_{2}, …, C′_{m′}}, and suppose that (w(C_{1}), w(C_{2}), …, w(C_{m})) and (w(C′_{1}), w(C′_{2}), …, w(C′_{m′})) are both weakly decreasing. We know that, for all i, 1 ≤ i ≤ m, there exist an integer, say k(i) such that 1 ≤ k(i) ≤ m′ and C_{i} ≤ C′_{k(i)}. So, w(C_{1}) ≤ w(C′_{k(1)}) ≤ w(C′_{1}) and either w(t) < w(t′) or w(C_{1}) = w(C′_{1}) and C_{1} is equal to C′_{k(1)}. By reordering {C′_{1}, …, C′_{m′}} we can suppose k(1) = 1. In this case, k(2) ≠ 1 (because, otherwise, C_{2} ≤ C′_{1} = C_{1}, and two elements of E cannot be comparable) and k(2) ≥ 2. Again w(C_{2}) ≤ w(C′_{k(2)}) ≤ w(C′_{2}), and either w(t) < w(t′) or C_{2} = C′_{k(2)}. Going on, we reach the results that, either w(t) < w(t′) or k is injective. If k is surjective, this means that t = t′, and if not, this implies that w(t) < w(t′).

♡

We can now state our last reduction.

Proposition 5.29 Let A be a finite structure. Then there exists a strong extension B of A such that, for every type t and t′, if w(t) = w(t′), then the set {b ∈ U_{1}^{B}; t_{B}(b/A) ≥ t} and {b ∈ U_{1}^{B}; t_{B}(b/A) ≥ t′} have the same number of elements.

Proof. Let B be as in the conclusion of Proposition 5.29. By Lemma 5.26

{b ∈ U_{1}^{B}; t_{B}(b/D) = t} = {b ∈ U_{1}^{B}; t_{B}(b/A) ≥ t} −
⋃_{t′>t, t′ is based on D} {b ∈ U_{1}^{B}; t_{B}(b/D) = t′}

We argue by downward induction: assume that we have proved that the sets {b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = t} and {b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = p_{i}(t)} have the same cardinality for every type t based on D_{i} of weight strictly bigger than a given value ℓ, and let u be a type based on D_{i} of weight ℓ. We have

{b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = u} = {b ∈ U_{1}^{B}; t_{B}(b/A) ≥ u} −
⋃_{u′>u, u′ is based on D_{i}} {b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = u′}

and, analogously,

{b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = p_{i}(u)} = {b ∈ U_{1}^{B}; t_{B}(b/A) ≥ p_{i}(u)} −
⋃_{u′>p_{i}(u), u′ is based on D′_{i}} {b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = u′}

by our previous remark. The map p_{i} induces a one to one correspondence between the set {u′ > u, u′ is based on D_{i}} and the set {u′ > p_{i}(u), u′ is based on D′_{i}}. Moreover, by induction hypothesis, for each type u′ > u, u′ based on D_{i},

card({b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = u′}) = card {b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = p_{i}(u′)})

From these facts,we deduce that

card({b ∈ U_{1}^{B}; t_{B}(b/D_{i}) = u}) = card({b ∈ U_{1}^{B}; t_{B}(b/D′_{i}) = p_{i}(u)}).
♡

We have now finished the reductions, and it remains to prove Proposition 5.29. Let n_{0} = max(w(t); t is a type) (here, by abuse of language, we identify that the weight of a type with an integer). We construct by downward induction a chain of strong extensions (B_{n}, 0 ≤ n ≤ n_{0} + 1) such that, for every types t and t′, if w(t) = w(t′) ≥ n, then the set {b ∈ U_{1}^{B_{n}}; t_{B_{n}}(b/A) ≥ t} and {b ∈ U_{1}^{B_{n}}; t_{B_{n}}(b/A) ≥ t′} have the same number of elements. We start with B_{n_{0}+1} = A, and we end with B_{0}, the structure that we need.

We show how to get B_{n} from B_{n+1}. For every type t, let s(t) = card({b ∈ B_{n+1}; t_{B_{n+1}}(b/A) ≥ t}) and r = max(s(t); t is a type of weight n). Assume that for a given type t of weight n, s(t) < r. We are going to construct a strong extension B′ of B_{n+1} such that U_{1}^{B′} = U_{1}^{B_{n+1}} ∪ {a}, where t_{B′}(a/A) = t. Thus for no t′ with w(t′) ≥ w(t) and t′ ≠ t we have t_{B}(b/A) ≥ t′. Repeating this process r − s(t) times, and then doing this for all types of weight n, we will get the structure B_{n} with the desired properties.

By the proof of Lemma 5.18, we know that there exists a strong extension A_{1} of A and an element a ∈ A_{1} − A such that t_{A_{1}}(a/A) = t. Let A_{2} be the substructure of A_{1} whose universe is

A_{1} − {b; b ∈ U_{1}^{A_{1}} − U_{1}^{A} and b ≠ a}

By Lemma 5.4, A_{2} is a strong extension of A, and it is immediate to check that t_{A_{2}}(a/A) = t. Now let B′ = B_{n+1} ∗_{A} A_{2}. By Lemma 5.4 B_{n+1} ⊂_{s} B′ and A_{2} ⊆_{s} B′ and therefore also t_{B′}(a/A) = t. Thus B′ has the desired properties.

♡

6 Final comments.

We wish to conclude this article by some comments and one open question.

Just before the difficult writing of this paper was over, we became aware (thanks to J.E. Pin and P. Weil) of the work of Almeida [1] and of Almeida and Delgado [2]. It seems that starting from a theorem of Ash ([3]) they have proved a theorem which can be seen to be equivalent to our Theorem 3.3. See [2] for more details.

The result in this paper improves the results in [6]. Let us recall some notation from [6]. Suppose R is a set of link structures and F is a finite set of structures. We denote by K_{RF} the class of all F-free structures of link type R. If K_{RF} has the amalgamation property (AP) (where we allow the common part to be empty), then there exists a countable homogeneous universal structure in K_{RF}, which we call M_{RF} and which is uniquely determined up to isomorphism. In [6] the property EPPA was called (WEP). The property (EP) is the following property for a class C: For all finite M_{0} and P ⊆ Part(M_{0}, M_{0}) the (M_{0}, P, C)-extension problem has a finite solution.

Theorem 6.1 Let L be a finite relational language. Let R be a set of link structures and F be a finite set of L-structures.

a) K_{RF} has EPPA.

b) If K_{RF} has (AP) then K_{RF} has (EP) and M_{RF} satisfies the small index property.

See [6] or [7] for the definition of the small index property.

Proof. a) follows from Theorem 3.2. Use the remark after Definition 2.1 to get a slim solution and observe that a slim solution of the (M_{0}, P, C)-extension problem has the same link type as the structure M_{0} you started with.

b) If K_{RF} has (AP) then M_{RF} provides an infinite solution for every (M_{0}, P, K_{RF})-extension problem, where M_{0} is finite: Embed M_{0} into M_{RF}, which you can do by the universality of M_{RF} and by the homogeneity you can extend every partial isomorphism from P to an automorphism of M_{RF}. So in this case EPPA implies (EP). Now use the method of [7] to prove the small index property: Like in the proof of Lemma 14 in [6] deduce that K_{RF} actually satisfies the free amalgamation property. This implies that also the classes K_{RF}^{+n} (for n ∈ ω) satisfy (AP). Now Theorem 11 in [6] states that M_{RF} has the small index property. ♡

The case of the class of tournaments raises an interesting problem. Recall the definition of a tournament: it is a directed irreflexive graph Γ such that, for every two distinct points a and b in Γ, either there is an arrow from a to b, or there is an arrow from b to a, but not both. There is a countable tournament Γ_{0} which is universal (every finite tournament can be embedded in it) homogeneous (every isomorphism between two finite tournaments included in Γ_{0} can be extended to an automorphism of Γ_{0}), which in fact is determined up to isomorphism by these properties and which we shall call the generic tournament. The following question is open:

(1) Has the generic tournament the small index property?

But this question would be settled affirmatively if we could prove:

(2) The class of all tournaments has the EPPA.

This last question turns out to be equivalent to a rather natural question about free groups. Let F (P) be the free group generated by the finite set P. Consider the topology on F (P) for which a basis of open sets is

{f · H; f ∈ F (P), H is a normal subgroup of F (P) of finite odd index} .

We shall call this topology the odd-adic topology. Then, (2) is equivalent to the following assertion

(3) let H be a finitely generated subgroup of F (P). Then the 2 following properties are equivalent:

(i) H is closed for the odd-adic topology.

(ii) For all a ∈ F (P), if a^{2} ∈ H, then a ∈ H.

We sketch the proof that (2) and (3) are equivalent. We first remark that, in any case, (3 i) implies (3 ii). Assume, toward a contradiction, that H is a subgroup of F (P) which is closed for the odd-adic topology, that a ∉ H and a^{2} ∈ H. Because H is closed for the odd-adic topology, there exists a homomorphism φ from F (P) onto a finite group G of odd order, such that, if we set H′ = φ [H] and a′ = φ(a), then a^{′2} ∈ H′ but a′ ∉ H′. Now, if we consider G_{1} = {g ∈ G; gH′ = H′ and ga′H′ = a′H′} and G_{2} = {g ∈ G; {gH′, ga′H′} = {H′, a′H′}}, then we see that G_{1} is a subgroup of order 2 of G_{2}, and this is impossible since G_{1} has odd order, as subgroup of a group of odd order.

Now assume (2). We show that (3 ii) implies (3 i). So, let H be a finitely generated subgroup of F (P) satisfying (3 ii) and α an element of F (P) not in H.

We will first define a tournament T, whose base set is F (P)/H in such a way that, for all f ∈ F (P), the left multiplication by f is an automorphism of T. To do that, consider, for each pair (aH, bH) in F (P)/H with aH ≠ bH, the orbit of (aH, bH) under the action of F (P), that is X_{a,b} = {(faH, fbH); f ∈ F (P)}. Such an orbit cannot contain both a pair (cH, dH) and (dH, cH).

Otherwise, for some f ∈ F (P), fcH = dH and fdH = cH, so f^{2}dH = dH, and (d^{−1}fd)^{2}H = H. By condition (3 ii), this implies that (d^{−1}fd) ∈ H, so cH = dH, which is impossible.

Consider now the set {{aH, bH}; aH ≠ bH} and partition it into orbits for the action of F (P). Each orbit O is equal to the set {{faH, fbH}; f ∈ F (P)}, where a and b are two elements of F (P) and aH ≠ bH. The subset X(O) = {(cH, dH); {cH, dH} ∈ O} of (F (P)/H)^{2} is the disjoint union of exactly two orbits of (F (P)/H)^{2} under the action of F (P). Choose one of them, say Y (O), and define the tournament structure on F (P)/H by deciding that there is an arrow from aH to bH, if and only if (aH, bH) ∈ Y (O) for some orbit O.

We are now ready to use our machinery. Let X_{0} be a finite subset of F(P) containing α, the generators of H and closed under initial segments, as in section 2. Let T_{0} consist of the cosets modulo this subset, considered as a subtournament of T. To each element p ∈ P corresponds a partial automorphism p̂ of T_{0}. By (2), there exists a tournament T_{1} containing T_{0} and automorphisms p̃ of T_{1} extending p̂. This allows us to define an action of F (P) on T_{1} that is a homomorphism f ⟼ f̃ from F (P) into Aut(T_{1}), the automorphism group of T_{1}. Because we have put enough elements in T_{0}, the stabiliser H′ of H for this action includes H, does not contain α and, of course, is of finite index. We want to show that H′ is open.

The kernel of this action, that is K = {f ∈ F (P); f̃ = 1}, is a normal subgroup of F (P) of finite index contained in H′, and we will be done if we prove that its index is odd. But F (P)/K is isomorphic to a subgroup of Aut(T_{1}), and Aut(T_{1}) has odd order, because it cannot contain an involution.

Let us now prove that (3) implies (2). We start from a finite tournament T and a set P of partial automorphisms of T. We consider T as a directed graph, and we choose an element x_{0} in T. We may assume that for all x ∈ T, there exists p ∈ P such that x = p(x_{0}). So, there is a correspondence between the subgroups H of F (P) containing the set

X_{0} = {p^{−1} · q; p(x_{0}) = q(x_{0})} ∪ {r^{−1} · p · q; r(x_{0}) = p ∘ q(x_{0})}

and disjoint from the set

X_{1} = {p^{−1} · q; p(x_{0}) ≠ q(x_{0})}

and the tuple (U, p̃; p ∈ A) where T ⊂ U and for all p ∈ A, p̃ is a permutation of U extending p. Let H_{0} be the subgroup of F (P) generated by X_{0}. In fact we have H_{0} = {p_{1}p_{2} … p_{n}; p_{1} ∘ p_{2} ∘ … ∘ p_{n}(x_{0}) = x_{0}}. We show that H_{0} is closed for the odd-adic topology, by showing, by (3), that if g^{2} ∈ H_{0} then g ∈ H_{0}.

Say that g = p_{1} · p_{2} · . . . · p_{n}, where n is an integer and the p_{i} are elements of P ∪ P^{−1} and this representation is reduced. It is easy to construct a finite tournament T_{1} extending T and, for each p ∈ P a partial automorphism p′ of T_{1} with the following properties: 1) p′ extends p; 2) p′_{1} ∘p′_{2} ∘…∘p′_{n}(x_{0}) is defined, and if p_{1} ∘p_{2} ∘…∘p_{n}(x_{0}) is not defined, then p′_{1} ∘p′_{2} ∘…∘p′_{n}(x_{0}) ≠ x_{0}. We may now embed T_{1} into the generic tournament T_{0} and extend the maps p′ (for p ∈ P) into automorphisms p̃ of T_{0}. As usual, this will provide us with a homomorphism f ⟼ f̃ from F (P) into Aut(T_{0}). We see that g̃(x_{0}) = p′_{1} ∘ p′_{2} ∘ … ∘ p′_{n}(x_{0}), and thanks to our hypothesis on T_{1}, if g ∉ H_{0}, then g̃(x_{0}) ≠ x_{0}. Since g^{2} ∈ H_{0}, we see that g̃^{2}(x_{0}) = g^{2}(x_{0}) = x_{0}, and since g̃ cannot switch 2 different points, g̃(x_{0}) = x_{0}, and g ∈ H_{0}.

Now, we apply our technique: we find a finite set Γ_{1} extending T and a homomorphism f ⟼ f̃ from F (P) into Sym(Γ_{1}) such that, for all p ∈ A, p̃ extends p. From the fact that H_{0} is closed for the odd-adic topology, we may demand that the kernel of this homomorphism is of odd index. Thus, the subgroup G of Sym(Γ_{1}) generated by {p̃; p ∈ P } is of odd order. We can suppose that G acts transitively on Γ_{1} and as usual we define for α, β ∈ Γ_{1}: there is an arrow from α to β if there exists a, b ∈ Γ and g ∈ F (P) such that there is an arrow from a to b and g̃(a) = α and g̃(b) = β. As G is odd this defines the structure of a directed graph on Γ_{1} and Γ is a substructure of Γ_{1}.

It just remains to add arrows in Γ_{1} to turn it into a tournament, in such a way that the p̃ for p ∈ P remain automorphisms. We do that exactly as above, when we have defined a tournament structure on the set F (P)/H.

References

[1] Jorge Almeida : Hyperdecidable pseudovarieties and the calculation of semidirect products, submitted.

[2] Jorge Almeida & Manuel Delgado : Sur les système d’équations avec contraintes dans un groupe libre, preprint.

[3] Chris J. Ash : Inevitable graphs: a proof of type II conjecture and some related decision procedures, Int. J. Algebra and Computation 1 (1991), pp. 127-146.

[4] Marshall Hall : A topology for free groups and related groups, Ann. of Maths 52 (1950), pp. 127-139.

[5] Bernhard Herwig : Extending partial isomorphisms on finite structures, Combinatorica 15, (1995), pp. 365-371.

[6] Bernhard Herwig : Extending partial isomorphisms for the small index property of many ωcategorical structures, preprint.

[7] Wilfrid Hodges, Ian Hodkinson, Daniel Lascar & Saharon Shelah : The small index property for ω-categorical ω-stable structures and for the random graph, Journal of the London Math. Society (2), 48 (1993), 204-218.

[8] Ehud Hrushovski : Extending partial isomorphisms of graphs, Combinatorica 12, (1992), pp. 204-218.

[9] Luis Ribes & Pavel.A. Zalesskiì, On the profinite topology on a free group. Bull. London Math. Soc. 25 (1993), pp. 37.43.

Addresses

Bernhard Herwig Institut für mathematische Logik Universität Freiburg D-79104 Freiburg Germany herwig@sun2.ruf.uni-freiburg.de

Daniel Lascar Université Paris 7, CNRS URA 753, UFR de mathématiques 2 Place Jussieu, Case 7012 75251, Paris CEDEX 05 France lascar@logique.jussieu.fr