# «Abstract We demonstrate the uncountable coﬁnality of the automorphism groups of various linear and partial orders. We also relate this to the ...»

Uncountable coﬁnalities of automorphism groups

of linear and partial orders

M. Droste, Universit¨t Leipzig and

a

J. K. Truss, University of Leeds1.

Abstract

We demonstrate the uncountable coﬁnality of the automorphism groups

of various linear and partial orders. We also relate this to the ‘Bergman’

property, and discuss cases where this may fail even though the coﬁnality

is uncountable.

1 Introduction

**In [5, 6], three related properties which an inﬁnite group G may have are discussed. These are the so-called Bergman property (after [2]), uncountable coﬁnality and strong uncountable coﬁnality. These say the following:**

Bergman property: for any generating set E for G which contains the identity and is closed under inverses, there is n ∈ N such that G = E n.

Uncountable coﬁnality: G cannot be expressed as i∈ω Gi where G0 ⊂ G1 ⊂ G2 ⊂... and each Gi is a proper subgroup.

Strong uncountable coﬁnality: G cannot be expressed as i∈ω Ui where U0 ⊂ U1 ⊂ U2 ⊂... and each Ui is closed under inverses, and ∀i∃j(Ui Ui ⊆ Uj ).

In fact these are related, and it is shown in [6] that G has strong uncountable coﬁnality if and only if it has both the Bergman property, and uncountable coﬁnality.

Special cases of groups which are known to have uncountable coﬁnality are the symmetric group on an inﬁnite set [16], the automorphism group A(Q) of the rational numbers [12], and an inﬁnite direct power of a ﬁnite perfect group [15]. The Bergman property has also been veriﬁed in a number of cases, starting with the inﬁnite symmetric group [2] and A(Q) [6], and going on to many more general classes in [5, 9]. The equivalence mentioned above at once assures us that these also all have strong uncountable coﬁnality.

In this paper we look at three further cases where we can ﬁnd out when uncountable coﬁnality and its variants do or do not hold. The ﬁrst is that 1 2000 Mathematics subject classiﬁcation 06A07, 06F15, 20B22, 20E15;

keywords: coﬁnality, partial order, cycle-free This work was supported by a grant from the EPSRC.

of the automorphism groups of linear orders (chains). Since we usually make some transitivity assumption on a structure whose automorphism group we are considering (to guarantee that it is suﬃciently rich), the minimum here is 1transitivity. We focus particularly on the linear orders in Morel’s classiﬁcation of the countable 1-transitive linear orders [17], but prove a more general result based on the ideas in [6]. Notice that most of the ones in Morel’s list are discrete, but this does not prevent us proving strong uncountable coﬁnality for those embedding Q. This contrasts with the results of [3], where it is shown that the small index property fails for all of these structures except Zα and Q.Zα for α ≤ 1. We also make remarks about those of the form Zα which in all cases fail to have the Bergman property, and for limit α, even fail uncountable coﬁnality (meaning that in this case the automorphism group is the union of a countable chain of proper subgroups).

Next we look at ‘trees’ (or ‘semilinear orders’) and their automorphism groups, as studied for instance in [1, 7, 8]. We demonstrate in section 3 that the automorphism group of any weakly 2-transitive tree with countable coinitiality has strong uncountable coﬁnality. This uses an adaptation of the methods of [6], and some of the technical material from [7], which we recall below.

Finally we consider cycle-free partial orders (CF P Os). Viewing these as generalizations of trees, Warren classiﬁed a class of suﬃciently transitive CF P Os in [21], and this was extended to a classiﬁcation of all the countable k-CStransitive CF P Os for k ≥ 2 in [4, 19, 13]. One point here is that these structures were shown in [10] to fall into three distinct classes, those whose automorphism groups are not simple, and those whose automorphism groups are simple, with or without a bound on the number of conjugates required (where this means that there is some ﬁxed number m such that for any non-identity elements g and h of G, h may be written as the product of at most m conjugates of g or g −1 ).

This last case at once provides us with natural examples where the coﬁnality is uncountable, but Bergman’s property fails. Here however, even those structures whose automorphism groups are simple, but where a bounded number of conjugates suﬃces, have uncountable coﬁnality but not strong uncountable conality, and this is for a slightly diﬀerent (if related) reason, namely that there is a notion of ‘distance’ in any CF P O, and the distance between two vertices can be arbitrarily large. In fact this observation enables us to conclude that a much larger class of CF P Os, even including many 1-transitive ones, fail to have the Bergman property.

We conclude this introduction by recalling some of the notation and deﬁnitions we shall require.

For any partially ordered set P = (P, ) we write A(P ) for the automorphism group of P. This is the notation adopted in [11] for instance, when P is linearly ordered, and also for trees in [7, 8]. The only other types of partially ordered set that we consider here are CF P Os, and for consistency we retain the notation for them as well.

A structure is said to be 1-transitive if its automorphism group acts singly transitively on points. Morel [17] classiﬁed all the countable 1-transitive linear orders, and they are Zα and Q.Zα for countable ordinals α. Here Zα is the restricted lexicographic power of α copies of Z (which may be taken to be the set of functions from α to Z of ﬁnite support ordered lexicographically), and Q.Zα is the lexicographic product of Q with that, Q ‘copies’ of Zα. A chain is said to be doubly homogeneous if its automorphism group acts transitively on its 2-element subsets. There is only one non-trivial countable doubly homogeneous chain, namely Q, but there are many more uncountable ones.

A tree, or semilinear order, is a partially ordered set (T, ) in which any

**two elements have a common lower bound, and for any element x, {y ∈ T :**

y ≤ x} is a chain. A tree is said to be weakly 2-transitive if its automorphism group acts transitively on its set of 2-element chains. The countable weakly 2-transitive trees were classiﬁed in [7], and properties of their automorphism ℵ0 groups described. In particular, they have 22 normal subgroups. In [8] more information was given about these, even not assuming countability.

The precise deﬁnition of cycle-free partial order (CF P O) is given in [21]. The main points are these. Any partially ordered set M has a so-called Dedekind– MacNeille completion written M D, which may be characterized by saying that in M D, any non-empty bounded above subset has a least upper bound, and it is the minimal such containing M. We then say that M is a cycle-free partial order if between any two of its points there is a unique path in M D (in a natural analogue of the notion for graphs). This entails that any CF P O is necessarily connected. Note that this gives rise to a notion of ‘distance’, since we may say that points x and y of M are at distance n if there is a sequence x = x0, x1,..., xn = y such that for each i n, xi and xi+1 are comparable, and the set Ii of points of M D lying between xi and xi+1 is a chain for each i, such that if Ii ∩ Ij = ∅ and i j, then j = i + 1 and the intersection is equal to {xi+1 }. In practice we more often work with M + rather than M D, which is the union of M and all the ramiﬁcation points, which are the elements of M D which may be expressed as either the least upper bound or greatest lower bound of two members of M (these are called ‘downward’ and ‘upward ramiﬁcation points’ respectively). This has the advantage that if M is countable, so is M +.

For trees the appropriate notions of transitivity are k-transitivity, weak ktransitivity, or k-homogeneity for k ≤ 2. For cycle-free partial orders, the fact that there is a notion of distance as described above means that in non-trivial cases, k-transitivity can never hold for k ≥ 2 since there will be incomparable points at diﬀerent distances. So in this context the appropriate notions are kCS-transitivity (or homogeneity) for k ≤ 3 where this means that for any two isomorphic connected k-element substructures, there is an isomorphism taking the ﬁrst to the second. A classiﬁcation of all the countable 2− or 3-CS-transitive CF P Os is given in the papers [21, 4, 19, 13].

We write Ω for the Dedekind-completion of a chain Ω and Ω for its ‘total completion’, that is, also including endpoints. It is clear that the automorphism group of Ω acts naturally on Ω (and Ω), and the same applies to the Dedekind– MacNeille completion of a partially ordered set.

2 Uncountable coﬁnality for some linear orders The main result in this section arose as an attempt to determine whether or not the automorphism groups of the linear orders in Morel’s classiﬁcation of all the countable 1-transitive linear orders have uncountable coﬁnality. In fact we found that we were able to prove a considerably stronger result corresponding to the structures in Morel’s list of the form Q.Zα, by adapting the methods of [6] (which in turn were derived from [12]). The situation for the other structures in her list, Zα for α ≥ 2, is as yet not completely resolved—see below. We say that a chain Ω has countable coterminality if there are points an ∈ Ω for n ∈ Z such that an an+1 and (∀a ∈ Ω)(∃m, n(am ≤ a ≤ an )). Note that it makes no diﬀerence whether these points are required to lie in Ω or its Dedekindcompletion (though the deﬁnition as it stands would refer just to Ω). A chain is scattered if it does not embed Q.

Before stating and proving the main result of this section, we prove two lemmas which are needed in the proof.

** Lemma 2.1.**

Let (Y, ) and (Z, ) be linear orders such that Y is doubly homogeneous with countable coterminality and Z is scattered. Then any two positive elements h1 and h2 of A(Y.Z) with coterminal orbits are conjugate (where by hi ‘positive’ we mean that hi (x) x for all x).

Proof: It is clear that as hi has a coterminal orbit, it follows that every orbit is coterminal, so we may pick orbits {hi (y, z) : i ∈ Z} and {hi (y, z) : i ∈ Z}. Now [(y, z), h1 (y, z)) ∼ [(y, z), h2 (y, z)), since [(y, z), h1 (y, z)) = {y} × = [z, ∞) ∪ (y, y1 ) × Z ∪ {y1 } × (−∞, z1 ) where h1 (y, z) = (y1, z1 ), and similarly for [(y, z), h2 (y, z)), and (y, y1 ) × Z ∼ (y, y2 ) × Z since (y, y1 ) ∼ (y, y2 ), and = = {y1 } × (−∞, z1 ) ∼ {y2 } × (−∞, z2 ) by the isomorphism h2 h−1. (Note that it = 1 follows from the facts that Z is scattered and Y is doubly homogeneous that h2 h−1 maps {y1 } × (−∞, z1 ) onto {y2 } × (−∞, z2 ).) Let θ be an isomorphism from [(y, z), h1 (y, z)) to [(y, z), h2 (y, z)), and extend to the whole of Y.Z by letting θ(hi (t)) = hi θ(t) for each t ∈ [(y, z), h1 (y, z)) and i ∈ Z. Then we deduce that θh1 = h2 θ and so h1 and h2 are conjugate.

** Lemma 2.2.**

For Y and Z as in the previous lemma, any element h of A(Y.Z) may be written in the form h1 h−1 where h1 and h2 are positive with coterminal orbits.

Proof: Choose z ∈ Z and yi ∈ Y for i ∈ Z such that yi yi+1 and yi → ±∞ as i → ±∞. Let ti = (yi, z). Then ti ti+1 and ti → ±∞ as i → ±∞. By passing to a coterminal subset, we may assume that for each i, ti−1 h(ti ) ti+1. Let h1 ∈ A(Y.Z) satisfy h1 (ti ) = ti+2 for each i. Then h−1 h1 (ti ) = h−1 (ti+2 ) ti+1, from which it follows that h1 and h2 = h−1 h1 are both positive with a coterminal orbit. Hence h = h1 h−1 is expressed in the desired form.

** Theorem 2.3.**

Let Z be a scattered linear order, and Ω = X.Z be the lexicographic product of X copies of Z for some inﬁnite doubly homogeneous chain X. We assume further that X may be expressed as the disjoint union of open intervals having countable coterminality. Then A(Ω) has strong uncountable coﬁnality.

Proof: Note that G = A(Ω) preserves the copies of Z (as Z is scattered), and so is equal to the wreath product of A(X) and A(Z). The same proof would work without the assumption of Z scattered, but then we would have to work with the subgroup of A(Ω) preserving the copies setwise, which could be a proper subgroup, rather than A(Ω) itself. We may allow G to act on X if we wish, since any automorphism will carry each copy of Z to a copy of Z (using again the fact that it is scattered).

Suppose for a contradiction that G may be written as i∈ω Ui where U0 ⊂ U1 ⊂ U2 ⊂..., Ui−1 = Ui, and ∀i∃j(Ui Ui ⊆ Uj ). We shall follow the proof from [6], indicating modiﬁcations where necessary.

A key point is to characterize the ﬁxed point sets in the order-completion Ω of Ω of members of G. In [6] these were called clans. Since Ω has a more complicated structure than in [6], we just use the word for a special kind of ﬁxed point set. Recall that Ω is the total completion of Ω (with endpoints).

Now Ω consists of X copies of Z, and we note that its Dedekind completion is equal to X.Z ∪ (X − X), where this is ordered by (x, z) x ⇔ x x for x ∈ X, x ∈ X − X, z ∈ Z. This is because the Dedekind cuts of X.Z are of two possible kinds, those that ‘intersect’ or ‘abut’ some copy of Z, in which case they are determined by a member of Z, and those which do not, in which case they are determined by a member of X − X. We then deﬁne a clan to be a closed subset of Ω which is a subset of X − X and such that all intervals I making up its complement are unbounded with countable coterminality.