Closed subgroups of the infinite symmetric group

George M. Bergman and Saharon Shelah

In honor of Walter Taylor, on his not-yet-retirement

Abstract. Let S = Sym(Ω) be the group of all permutations of a countably infinite set Ω, and for subgroups G_{1}, G_{2} ⩽ S let us write G_{1} ≈ G_{2} if there exists a finite set U ⊆ S such that ⟨G_{1} ∪ U ⟩ = ⟨G_{2} ∪ U ⟩. It is shown that the subgroups closed in the function topology on S lie in precisely four equivalence classes under this relation. Which of these classes a closed subgroup G belongs to depends on which of the following statements about pointwise stabilizer subgroups G_{(Γ)} of finite subsets Γ ⊆ Ω holds:

(i) For every finite set Γ, the subgroup G_{(Γ)} has at least one infinite orbit in Ω. (ii) There exist finite sets Γ such that all orbits of G_{(Γ)} are finite, but none such that the cardinalities of these orbits have a common finite bound. (iii) There exist finite sets Γ such that the cardinalities of the orbits of G_{(Γ)} have a common finite bound, but none such that G_{(Γ)} = {1}. (iv) There exist finite sets Γ such that G_{(Γ)} = {1}.

Some related results and topics for further investigation are noted.

 This is the final preprint version of a paper which appeared at
Algebra Universalis, 55 (2006) 137-173.  The published version is
accessible to subscribers at  http://dx.doi.org/10.1007/s00012-006-1959-z .

1. Introduction.

In [5, Theorem 1.1], Macpherson and Neumann show that for Ω an infinite set, the group S = Sym(Ω) is not the union of a chain of ⩽ |Ω| proper subgroups. It follows that if G is a subgroup of S, and if S = ⟨G ∪ U⟩ for some set U ⊆ S of cardinality ⩽ |Ω|, then one may replace U by a finite subset of U in this equation. Galvin [4] has shown that in this situation one can even replace U by a singleton, though not necessarily one contained in U or even in ⟨U⟩.

Thus we have a wide gap – between subgroups G over which it is “easy” to generate S (where one additional element will do), and all others, over which it is “hard” (even |Ω| elements will not suffice). It is natural to wonder how one can tell to which sort a given subgroup belongs. There is probably no simple answer for arbitrary subgroups; but we will show, for Ω countable, that if our subgroup

2000 Mathematics Subject Classification: Primary: 20B07, secondary: 22F50. Key words and phrases: full permutation group on a countably infinite set, subgroups closed

in the function topology, equivalence relation on subgroups, cardinalities of orbits of stabilizers of finite sets.

Second author’s research supported by the United States–Israel Binational Science Foundation. A preprint version of this paper is readable at /~gbergman/papers/

Sym_Omega:2.{tex,dvi}, at http://shelah.logic.at as publication 823, and at arXiv:math.GR/
0401305 .

is closed in the function topology on S, then one element suffices if and only if G satisfies condition (i) of the above abstract. The method of proof generalizes to give the four-way classification of closed subgroups asserted there.

(The four conditions of that classification could be stated more succinctly, if not so transparently to the non-set-theorist, by writing λ for the least cardinal such that for some finite subset Γ ⊆ Ω, all orbits of G_{(Γ)} in Ω have cardinality < λ. Then the conditions are (i) λ = ℵ_{1}, (ii) λ = ℵ_{0}, (iii) 3 ⩽ λ < ℵ_{0} and (iv) λ = 2. But we shall express them below in the more mundane style of the abstract.)

The proofs of the above results will occupy §§2–8 of this note. In §§9–12 we note some related observations, questions, and possible directions for further investigation.

The authors are indebted to Peter Biryukov, Peter Neumann, and Zachary Mesyan for corrections to earlier drafts of this note.

2. Definitions, conventions, and basic observations.

As usual, “ ⩽ ” appearing before the symbol for a group means “is a subgroup of”, and ⟨ ... ⟩ denotes “the subgroup generated by”.

We take our notation on permutation groups from [5]. Thus, if Ω is a set, Sym(Ω) will denote the group of all permutations of Ω, and such permutations will be written to the right of their arguments. Given a subgroup G ⩽ Sym(Ω) and a subset Σ ⊆ Ω, the symbol G_{(Σ)} will denote the subgroup of elements of G that stabilize Σ pointwise, and G_{{Σ}} the larger subgroup {f ∈ G : Σf = Σ}. Elements of Ω will generally be denoted α, β, . . ..

The cardinality of a set U will be denoted |U|. Each cardinal is understood to be the least ordinal of its cardinality, and each ordinal to be the set of all smaller ordinals. The successor cardinal of a cardinal κ is denoted κ^{+}.

Let us now define, in greater generality than we did in the abstract, the relations we will be studying.

Definition 1. If S is a group, κ an infinite cardinal, and G_{1}, G_{2} subgroups of S, we shall write G_{1} ≼_{κ,S} G_{2} if there exists a subset U ⊆ S of cardinality < κ such that G_{1} ⩽ ⟨G_{2} ∪ U⟩. If G_{1} ≼_{κ,S} G_{2} and G_{2} ≼_{κ,S} G_{1}, we shall write G_{1} ≈_{κ,S} G_{2}, while if G_{1} ≼_{κ,S} G_{2} and G_{2} ⋠_{κ,S} G_{1}, we shall write G_{1} ≺_{κ,S} G_{2}.

We will generally omit the subscript S, and often κ as well, when their values are clear from the context.

Clearly ≼_{κ,S} is a preorder on subgroups of S, hence ≈_{κ,S} is an equivalence relation, equivalent to the assertion that there exists U ⊆ S of cardinality < κ such that ⟨G_{1} ∪ U⟩ = ⟨G_{2} ∪ U⟩. Note that conjugate subgroups of S are ≈_{κ}-equivalent for all κ. If G_{1} and G_{2} are ≈_{κ}-equivalent, we see that they are ≈_{κ}-equivalent to ⟨G_{1} ∪G_{2} ⟩. (However they need not be ≈_{κ}-equivalent to G_{1} ∩ G_{2}. For instance, if S = Sym(ℤ) and G_{1}, G_{2} are the pointwise stabilizers of the sets of positive, respectively negative integers, then they are conjugate, so G_{1} ≈_{ℵ_{0}} G_{2}, but G_{1} ∩ G_{2} = {1}, which is not ≈_{ℵ_{0}}-equivalent to G_{1} and G_{2}, since the latter groups are uncountable, hence not finitely generated.)

We note

Lemma 2. Let Ω be an infinite set, G a subgroup of S = Sym(Ω), and Γ ⊆ Ω a subset such that |Ω|^{|Γ|} ⩽ |Ω| (e.g., a finite subset). Then G_{(Γ)} ≈_{|Ω|^{+}} G.

Proof. Elements of G in distinct right cosets of G_{(Γ)} have distinct behaviors on Γ, hence if R is a set of representatives of these right cosets, |R| ⩽ |Ω|^{|Γ|} ⩽ |Ω|. Clearly, ⟨G_{(Γ)} ∪ R⟩ = G = ⟨G ∪ R⟩, so G_{(Γ)} ≈_{|Ω|^{+}} G, as claimed. □

Two results from the literature have important consequences for these relations:

Lemma 3 ([4], [5]). Let Ω be an infinite set. Then on subgroups of S = Sym(Ω),

(i) The binary relation ≼_{ℵ_{0}} coincides with ≼_{ℵ_{1}} (hence ≈_{ℵ_{0}} coincides with ≈_{ℵ_{1}}). (ii) The unary relation ≈_{ℵ_{0}} S coincides with ≈_{|Ω|^{+}} S.

Proof. (i) follows from [4, Theorem 3.3], which says that every countably generated subgroup of S is contained in a 2-generator subgroup.

We claim that (ii) is a consequence of [5, Theorem 1.1] (= [1, Theorem 5]) which, as recalled in §1, says that any chain of proper subgroups of S having S as union must have > |Ω| terms. For if G ≈_{|Ω|^{+}} S, then among subsets U ⊆ S of cardinality ⩽ |Ω| such that ⟨G ∪ U⟩ = S, we can choose one of least cardinality. Index this set U as {g_{i} : i ∈ |U|}. Then the subgroups G_{i} = ⟨G ∪ {g_{j} : j < i}⟩ (i ∈ |U|) form a chain of ⩽ |Ω| proper subgroups of S, which if |U| were infinite would have union S, contradicting the result of [5] quoted. So U is finite, so G ≈_{ℵ_{0}} S. □

We have not introduced the symbols ≼_{κ} and ≈_{κ} for κ finite because in general these relations are not transitive; rather, one has G_{1} ≼_{m} G_{2} ≼_{n} G_{3} ⟹ G_{1} ≼_{m+n−1} G_{3}. However, the proof of (i) above shows that in groups of the form Sym(Ω), ≼_{ℵ_{0}} is equivalent to ≼_{3} . Thus, in such groups, we do have transitivity of ≼_{κ} and ≈_{κ} when 3 ⩽ κ < ℵ_{0}, but have no need for these symbols. These observations are also the reason why in §§5–7 we won’t make “stronger” assertions than ≈_{ℵ_{0}}, though some of our constructions will lead to sets U of explicit finite cardinalities.

(Incidentally, [4, Theorem 5.7] shows that on Sym(Ω), the unary relation ≈_{ℵ_{0}} S is even equivalent to ≈_{2} S.)

3. Generalized metrics.

In this section we will prove a result which, for Ω countable, will imply that closed subgroups of Sym(Ω) falling under different cases of the classification described in the abstract are indeed ≈_{ℵ_{0}}-inequivalent.

To motivate our approach, let us sketch a quick proof that if Ω is any set such that |Ω| is an infinite regular cardinal (e.g., ℵ_{0}), and if G is a subgroup of S = Sym(Ω) such that every orbit of Ω under G has cardinality < |Ω|, then G ≉_{|Ω|} S. Given U ⊆ S of cardinality < |Ω|, let us define the “distance” between elements α, β ∈ Ω to be the length of the shortest group word in the elements of G ∪ U that carries α to β, or to be ∞ if there is no such word. It is not hard to see from our assumptions on the orbits of G and the cardinality of U that for each α ∈ Ω and each positive integer n, there are < |Ω| elements of Ω within distance n of α, hence this distance function on Ω has no finite bound. Now if an element of ⟨G ∪ U⟩ is expressible as a word of length n in elements of G ∪ U, it will move each element of Ω a distance ⩽ n. Thus, taking f ∈ Sym(Ω) which moves points by unbounded distances, we have f ∉ ⟨G ∪ U⟩; so ⟨G ∪ U⟩ ≠ S.

The next definition gives a name to the concept, used in the above proof, of a metric under which points may have distance ∞, and introduces some related terminology and notation.

Definition 4. In this definition, P will denote {r ∈ ℝ : r ⩾ 0} ∪ {∞}, ordered in the obvious way.

A generalized metric on a set Ω will mean a function d: Ω × Ω → P, satisfying the usual definition of a metric, except for this generalization of its value-set.

If d is a generalized metric on Ω, then for r ∈ P, α ∈ Ω, we will write B_{d}(α, r) for the open ball of radius r about α, {β ∈ Ω : d(α, β) < r}. If κ is an infinite cardinal, we will call the generalized metric space (Ω, d) κ-uncrowded if for every α ∈ Ω and r < ∞, the ball B_{d}(α, r) has cardinality < κ. We will call (Ω, d) uniformly κ-uncrowded if for every r < ∞, there exists a λ < κ such that for all α ∈ Ω, |B_{d}(α, r)| ⩽ λ. (For brevity we will, in these situations, also often refer to the metric d as being κ-uncrowded or uniformly κ-uncrowded.)

Given two generalized metrics d and d′ on Ω, we shall write d′ ⩽ d if d′(α, β) ⩽ d(α, β) for all α, β ∈ Ω.

For g ∈ Sym(Ω) and d a generalized metric on Ω, we define

||g||_{d} = sup_{α∈Ω} d(α, αg) ∈ P.

If ||g||_{d} < ∞, then the permutation g will be called bounded under d.

The case of these concepts that we will be most concerned with in subsequent sections is that in which |Ω| = κ = ℵ_{0}.

Observe that if a group G ⩽ Sym(Ω) has all orbits of cardinality < |Ω|, then giving Ω the generalized metric under which distinct points in the same orbit have distance 1 and points in different orbits have distance ∞, we get a |Ω|-uncrowded generalized metric with respect to which G acts by bounded permutations – this is the U = ∅ case of the construction sketched in the second paragraph of this section. Thus, if we can change the hypothesis of that construction from “ G has orbits of cardinality < |Ω| ” to “ G acts by bounded permutations with respect to a |Ω|-uncrowded generalized metric” (the condition we deduced held for ⟨G∪U⟩), we will have a stronger statement. This is done in the next theorem. If the cardinalities of the orbits of G have a common bound λ < |Ω|, then the above construction gives a uniformly |Ω|-uncrowded generalized metric. The theorem will generalize that case as well.

Note that if a generalized metric space (Ω, d) is |Ω|-uncrowded, the function d is necessarily unbounded, i.e., takes on values exceeding every positive real number.

Theorem 5. Suppose Ω is an infinite set, κ a regular cardinal ⩽ |Ω|, d a κuncrowded (respectively a uniformly κ-uncrowded) generalized metric on Ω, and G a subgroup of S = Sym(Ω) consisting of elements bounded with respect to d.

Then for any subset U ⊆ Sym(Ω) of cardinality < κ, there exists a generalized metric d′ ⩽ d on Ω, again κ-uncrowded (respectively, uniformly κ-uncrowded), such that every element of U, and hence every element of ⟨G∪U⟩, is bounded with respect to d′.

Thus, for subgroups G ⩽ S, the property that there exists a (uniformly) κuncrowded generalized metric on Ω with respect to which every element of G acts by bounded permutations is preserved under passing to groups H ≼_{κ} G, and in particular, under passing to groups H ≈_{κ} G.

Proof. Given Ω, κ, d as in the first sentence and U as in the second, let us define d′(α, β) for α, β ∈ Ω, to be the infimum, over all finite sequences of the form

(1) (α_{0}, α_{1}, …, α_{2n+1}) where α = α_{0}, α_{2n+1} = β, and where for i odd, α_{i+1} ∈ α_{i} (U ∪ U^{−1}),

of the sum

(2) d(α_{0}, α_{1}) + 1 + d(α_{2}, α_{3}) + 1 + … + 1 + d(α_{2n}, α_{2n+1}). This infimum is ⩽ d(α, β) because the set of sequences over which it is taken includes the sequence (α, β). We also see from (2) that whenever d′(α, β) ≠ d(α, β), we have d′(α, β) ⩾ 1, hence d′(α, β) is nonzero for α ≠ β. Symmetry and the triangle inequality are immediate from the definition, and each g ∈ U satisfies ||g||_{d′} ⩽ 1 because elements α and αg are connected by the sequence (α, α, αg, αg). Thus, d′ is a generalized metric ⩽ d, with respect to which every element of U is bounded; it remains to show that d′ is again (uniformly) κ-uncrowded.

So consider a ball of finite radius, B_{d′}(α, r). An element β lies in this ball if and only if there is a sequence (1) for which the sum (2) is < r. But (2) has n summands equal to 1, so given r < ∞, there are only finitely many values of n that need to be considered; so it suffices to show that for fixed n and α, the number of sequences (1) making (2) less than r is < κ, and in the uniform case has a bound < κ depending only on r. Now for 0 ⩽ i < 2n + 1, if we are given α_{i}, then the number of possibilities for α_{i+1} consistent with (2) being less than r is ⩽ |B_{d}(α_{i}, r)| < κ if i is even, while it is ⩽ | U ∪ U^{−1}| < κ if i is odd. By the regularity of κ, it follows that the number of possible sequences (1) of length 2n + 1 making (2) less than r and starting with a given α_{0} is < κ. Moreover, if we have a bound on |B_{d}(α_{i}, r)| independent of α_{i}, we also clearly get a bound on the above cardinal independent of α, as required.

The final assertions, concerning the relations ≼_{κ} and ≈_{κ}, clearly follow. □

Remark. What if in the above theorem we weaken the assumption that U has cardinality < κ to say that it has cardinality ⩽ κ?

If κ = ℵ_{0}, we get exactly the same conclusions, since the result of [4] cited in the proof Lemma 3(i) lets us replace any countable U by a set of cardinality 2. Can we see this stronger assertion without calling on [4]? Yes, by a slight modification of the proof of our theorem: We write the countable set U as {f_{1}, f_{2}, …}, and replace each of the “1”s in (2) by a value N such that α_{i+1} = α_{i} f_{N}^{±1}. Thus in the final step of the proof, the number of choices of α_{i+1} that can follow α_{i} for i odd will still satisfy a bound below ℵ_{0}, namely 2r.

For an uncountable regular cardinal κ, the sort of generalized metric we have introduced is not really the best tool. (Indeed, if (Ω, d) is κ-uncrowded, then for every α ∈ Ω, “most” elements of Ω must be at distance ∞ from α, and the main import of d lies in the equivalence relation of having distance < ∞; so such a metric is hardly a significant generalization of an equivalence relation.) What is more useful then is the concept of a κ ∪ {∞}-valued ultrametric, where the symbol ∞ is again taken as greater than all other values of the metric. Defining in the obvious way what it means for such an ultrametric to be (uniformly) κ-uncrowded, one can apply the same method as above when |U| = κ, with the summation (2) replaced by a supremum. Since we will not be looking at this situation, we leave the details to the interested reader.

The above theorem, in generalizing the argument sketched at the beginning of this section, discarded the explicit connection with cardinalities of orbits. The next result records that connection.

Let us understand a partition of a set Ω to mean a set A of disjoint nonempty subsets of Ω having Ω as union. If A is a partition of Ω and S = Sym(Ω), we define

(3) S_{(A)} = {f ∈ S : (∀ Σ ∈ A) Σf = Σ }. (This is an extension of the notation S_{(Σ)} recalled in the preceding section.)

Theorem 6. Let Ω be an infinite set, A a partition of Ω, S = Sym(Ω), G = S_{(A)}, and let κ be an infinite regular cardinal ⩽ |Ω|. Then

(a) If some member of A has cardinality ⩾ κ, then there is no κ-uncrowded generalized metric on Ω with respect to which all members of G are bounded.

(b) If all members of A have cardinalities < κ, but there is no common bound λ < κ for those cardinalities, then there is a κ-uncrowded generalized metric with respect to which all elements of G are bounded, but no uniformly κ-uncrowded generalized metric with this property.

(c) If all members of A have cardinalities ⩽ λ for some λ < κ, then there is a uniformly κ-uncrowded generalized metric with respect to which all elements of G are bounded.

Thus, by the last sentence of Theorem 5, for partitions A, B of Ω falling under distinct cases above, we have S_{(A)} ≉_{κ} S_{(B)}. More precisely, if A falls under a later case than B, then S_{(A)} ⋡_{κ} S_{(B)}.

Proof. To show (a), let Σ ∈ A have cardinality ⩾ κ and let d be any κ-uncrowded generalized metric on Ω. To construct an element of G which is unbounded with respect to d, let us choose elements α_{j}, β_{j} ∈ Σ for each positive integer j as follows: Assuming the elements with subscripts i < j have been chosen, take for α_{j} any element of Σ distinct from all of these. Since B_{d}(α_{j}, j) has cardinality < κ ⩽ |Σ|, the set Σ − B_{d}(α_{j}, j) − {α_{1}, …, α_{j−1}, β_{1}, …, β_{j−1}} is nonempty; let β_{j} be any element thereof. Once all α_{j} and β_{j} are chosen, let f ∈ G = S_{(A)} interchange α_{j} and β_{j} for all j, and fix all other elements of Ω. Since d(α_{j}, β_{j}) ⩾ j for each j, f is unbounded with respect to d.

The final assertion of (b) is shown similarly: If d is uniformly κ-uncrowded, then for each positive integer n we can find a cardinal λ_{n} < κ such that all balls of radius n contain ⩽ λ_{n} elements. On the other hand, the assumption on A allows us to choose for each n a set Σ_{n} ∈ A with more than λ_{n} + (2n − 2) elements. Assuming α_{1}, …, α_{n−1}, β_{1}, …, β_{n−1} have been chosen, we take for α_{n} any element of Σ_{n} − {α_{1}, …, α_{n−1}, β_{1}, …, β_{n−1}} and for β_{n} any element of Σ_{n} − B_{d}(α_{n}, n) − {α_{1}, …, α_{n−1}, β_{1}, …, β_{n−1}}, and finish the argument as before.

To get the positive assertions of (b) and (c), we define a generalized metric d_{A} on Ω by letting d_{A}(α, β) = 1 if α and β are in the same member of A, and ∞ otherwise. This is clearly κ-uncrowded, respectively uniformly κ-uncrowded, and all elements of G are bounded by 1 under d_{A}.

The conclusions of the final paragraph are straightforward. □

The three cases of the above theorem will be used to separate the first three of the four situations described in the abstract. One may ask whether the remaining case can be treated similarly. For parallelism, one might call a generalized metric “absolutely uncrowded” if all balls of finite radius are singletons, i.e., if the distance between any two distinct points is ∞, and then note that the trivial group is the unique group of permutations whose elements are bounded with respect to the absolutely uncrowded generalized metric. However, the property of acting by bounded permutations with respect to the unique absolutely uncrowded metric is certainly not preserved under adjunction of finitely many elements, i.e., is not an ≈_{ℵ_{0}}-invariant. Rather than any result of this sort, the property of countability will separate this fourth equivalence class from the others.

4. The function topology.

If Ω is an infinite set and we regard it as a discrete topological space, then the set Ω^{Ω} of all functions Ω → Ω becomes a topological space under the function topology. In this topology, a subbasis of open sets is given by the sets {f ∈ Ω^{Ω} : αf = β} (α, β ∈ Ω). The closure of a set U ⊆ Ω^{Ω} consists of all maps f such that, for every finite subset Γ ⊆ Ω, there exists an element of U agreeing with f at all members of Γ. It is immediate that composition of maps is continuous in this topology.

The group S = Sym(Ω) is not closed in Ω^{Ω} in the function topology. For instance when Ω = ω, we see that the sequence of permutations (0, 1), (0, 1, 2), …, (0, …, n), … (cycle notation) converges to the map n ↦ n + 1, which is not surjective. Nevertheless, when restricted to S, this topology makes ( )^{−1} as well as composition continuous; indeed, {f ∈ S : αf = β}^{−1} = {f ∈ S : βf = α}.

Given a subset U ⊆ S, we shall write cl(U) for the closure of U in S (not in Ω^{Ω} !) under the function topology. The fact that S is not closed in Ω^{Ω} has the consequence that if one wants to prove the existence of an element f ∈ cl(U) behaving in some desired fashion, one cannot do this simply by finding elements of U that show the desired behavior at more and more elements of Ω, and saying “take the limit”; for the limit may be an element of Ω^{Ω} which is not in S. However, there is a standard way of getting around this difficulty, “the method of going back and forth”. One constructs elements of U which not only agree on more and more elements of Ω, but whose inverses also agree on more and more elements. Taking the limit, one thus gets a map and also an inverse to that map. (What is being used is the fact that though S is not closed in Ω^{Ω}, the set {(g, g^{−1}) : g ∈ S} is closed in Ω^{Ω} × Ω^{Ω}.) Cf. [2, §§9.2, 16.4] for examples of this method, and some discussion. The next result, a formalization of this idea, will be used at several points below.

Lemma 7. Suppose that Ω = {ε_{0}, ε_{1}, … } is a countably infinite set, and that g_{0}, g_{1}, … ∈ S = Sym(Ω) and Γ_{0}, Γ_{1}, … ⊆ Ω are such that for all j > 0,

(4) {ε_{0}, …, ε_{j−1} } ∪ {ε_{0} g_{j−1}^{−1}, …, ε_{j−1} g_{j−1}^{−1}} ⊆ Γ_{j}, and

(5) g_{j} ∈ S_{(Γ_{j})} g_{j−1}.

Then the sequence (g_{j})_{j=0,1,...} converges in S.

Proof. Let i ⩾ 0.

For all j > i, the conditions ε_{i} ∈ Γ_{j} and (5) imply that ε_{i} g_{j} = ε_{i} g_{j−1}. Thus, the sequence (g_{j}) is eventually constant on ε_{i}.

Likewise, (5) and the condition ε_{i} g_{j−1}^{−1} ∈ Γ_{j} imply that ε_{i} g_{j}^{−1} = ε_{i} g_{j−1}^{−1}; hence the element of Ω carried to ε_{i} by g_{j} is the same for all j > i.

Since the first conclusion holds for all ε_{i} ∈ Ω, the sequence (g_{j})_{j=0,1,...} converges to an element of Ω^{Ω}, which is one-to-one because all the g_{j} are. Applying the second conclusion, we see that each ε_{i} is in the range of g, so g ∈ Sym(Ω). □

We note some elementary facts about closures of subgroups in the function topology.

Lemma 8. Suppose Ω is a set and G a subgroup of S = Sym(Ω). Then

(i) cl(G) is also a subgroup of S. (ii) G and cl(G) have the same orbits in Ω. (iii) If Γ is a finite subset of Ω, then cl(G)_{(Γ)} = cl(G_{(Γ)}).

Proof. Statement (i) is an immediate consequence of the continuity of the group operations.

From the characterization of the closure of a set in our topology, we see that for α, β ∈ Ω, the set cl(G) will contain elements carrying α to β if and only if G does, from which (ii) is clear.

The direction ⊇ in (iii) follows by applying (ii) to the orbits of elements of Γ. (Finiteness of Γ is not needed for this direction.) To get ⊆, assume f ∈ cl(G)_{(Γ)}. Since f ∈ cl(G), every neighborhood of f contains elements of G. But as f fixes all points of the finite set Γ, every sufficiently small neighborhood of f consists of elements which do the same, hence every such neighborhood contains points of G_{(Γ)}; so f ∈ cl(G_{(Γ)}). □

The above lemma has the consequence that once we show (for Ω countable) that the ≈_{ℵ_{0}}-class of a closed subgroup of Sym(Ω) is determined by which of conditions (i)–(iv) in our abstract hold, we can also say for an arbitrary subgroup G ⩽ Sym(Ω) that the ≈_{ℵ_{0}}-class of cl(G) is determined in the same way by which of those conditions G satisfies.

The subgroups of Sym(Ω) closed in the function topology are known to be precisely the automorphism groups of the finitary relational structures on Ω. (Indeed, one may take the n-ary relations in such a structure, for each n, to be all orbits of n-tuples of elements of Ω under the group.) But we shall not make use of this fact here.

(Incidentally, Sym(Ω) is also not open in Ω^{Ω}. It is easy to give a sequence of noninjective or non-surjective maps in which the failures of injectivity or surjectivity “drift off to infinity”, so that the limit is a bijection, e.g., the identity.)

5. Infinite orbits.

In this and the next three sections (and with minor exceptions, in subsequent sections as well), we shall restrict attention to the case of countable Ω. When an enumeration of its elements is required, we shall write

(6) Ω = {ε_{i} : i ∈ ω}. References to limits etc. in S = Sym(Ω) will always refer to the function topology; in particular, a closed subgroup of S will always mean one closed in S under that topology. The symbols ≼ and ≈ will mean ≼_{ℵ_{0},S} and ≈_{ℵ_{0},S} respectively.

We shall show in this section that if G is a closed subgroup of S such that (7) For every finite subset Γ ⊆ Ω, the subgroup G_{(Γ)} has at least one

infinite orbit in Ω, then G ≈ S. Our proof will make use of the following result of Macpherson and Neumann:

(8) [5, Lemma 2.4] (cf. [1, Lemma 3]): Suppose Ω is an infinite set and H a subgroup of Sym(Ω), and suppose there exists a subset Σ ⊆ Ω of the same cardinality as Ω, such that H_{{Σ}} (i.e., {f ∈ H : Σf = Σ}) induces, under restriction to Σ, the full permutation group of Σ. Then there exists x ∈ Sym(Ω) such that Sym(Ω) = ⟨H ∪ {x}⟩.

(This is stated in [5] and [1] for the case where Σ is a moiety, i.e., a set of cardinality |Ω| such that Ω − Σ also has cardinality |Ω|. But if the hypothesis of (8) holds for some Σ of cardinality |Ω|, it clearly also holds for a subset of Σ which is a moiety, so we may restate the result as above.)

We will also use the following fact. We suspect it is known, and would appreciate learning of any reference. (A similar technique, but not this result, occurs in [9] and [10].)

Lemma 9. Let us call a permutation g of the set ω of natural numbers local if for every i ∈ ω there exists j > i in ω such that g carries {0, …, j −1} to itself.

Then every permutation f of ω is a product gh of two local permutations.

Proof. Given f ∈ Sym(ω), let us choose integers 0 = a(0) < a(1) < a(2) < … recursively, by letting each a(i) be any value > a(i−1) such that {0, …, a(i−1)−1} f ∪ {0, …, a(i−1)−1} f^{−1} ⊆ {0, …, a(i)−1}. Let Σ_{−1} = ∅, and for i ⩾ 0 let Σ_{i} = {a(i), a(i)+1, …, a(i+1)−1}. Thus the set A = {Σ_{i} : i ⩾ 0} is a partition of ω into finite subsets, such that for each i ⩾ 0 one has Σ_{i}f ⊆ Σ_{i−1} ∪ Σ_{i} ∪ Σ_{i+1}. Note that for each i ⩾ 0, the number of elements which are moved by f from Σ_{i−1} into Σ_{i} is equal to the number that are moved from Σ_{i} into Σ_{i−1} (since these are the elements of ω that are moved “past a(i) − 1/2 ” in the upward, respectively the downward direction).

We shall now construct a permutation g such that g carries each set Σ_{2i} ∪ Σ_{2i+1} (i ⩾ 0) into itself, and g^{−1}f carries each set Σ_{2i−1} ∪ Σ_{2i} (i ⩾ 0) into itself; thus each of these permutations will be local, and they will have product f, as required. To do this let us, for each i, pair elements α that f carries from Σ_{2i} upward into Σ_{2i+1} with elements β that it carries from Σ_{2i+1} downward into Σ_{2i} (having seen that the numbers of such elements are equal), and let g exchange the members of each such pair, while fixing other elements. Clearly g preserves the sets Σ_{2i} ∪Σ_{2i+1}. It is not hard to verify that if we now look at ω as partitioned the other way, into the intervals Σ_{2i−1} ∪ Σ_{2i}, then the g we have constructed has the property that for every α ∈ ω, the element αg lies in the same interval Σ_{2i−1} ∪ Σ_{2i} as does αf. Hence g^{−1}f preserves each interval Σ_{2i−1} ∪ Σ_{2i}, completing the proof. □

We shall now prove a generalization of (8), assuming Ω countable. To motivate the statement, note that in the countable case of (8), if we enumerate the elements of Σ as α_{0}, α_{1}, …, then the hypothesis implies that we can choose elements g ∈ H in ways that allow us infinitely many choices for α_{0} g, for each such choice infinitely many choices for α_{1} g, etc.. But the hypothesis of (8) is much stronger than this, since it specifies that the set of choices for α_{0}g include all the α_{i}, that the choices for α_{1} g then include all α_{i} other than the one chosen to be α_{0} g, etc.. The next result says that we can get the same conclusion without such a strong form of the hypothesis.

Lemma 10. Let Ω be a countably infinite set and G a subgroup of Sym(Ω), and suppose there exist a sequence (α_{i})_{i∈ω} ∈ Ω^{ω} of distinct elements, and a sequence of nonempty subsets D_{i} ⊆ Ω^{i} (i ∈ ω), such that

(i) For each i ∈ ω and (β_{0}, …, β_{i}) ∈ D_{i+1}, we have (β_{0}, …, β_{i−1}) ∈ D_{i}; (ii) For each i ∈ ω and (β_{0}, …, β_{i−1}) ∈ D_{i}, there exist infinitely many elements β ∈ Ω such that (β_{0}, …, β_{i−1}, β) ∈ D_{i+1}; and (iii) If (β_{i})_{i∈ω} ∈ Ω^{ω} has the property that (β_{0}, …, β_{i−1}) ∈ D_{i} for each i ∈ ω, then there exists g ∈ G such that (β_{i}) = (α_{i} g) in Ω^{ω}.

Then G ≈ S.

Proof. Let us note first that our hypotheses imply that for (β_{0}, …, β_{i−1}) ∈ D_{i}, the entries β_{j} are all distinct. For from (i) and (ii) we see that such an i-tuple can be extended to an ω-tuple as in (iii), and by (iii) this ω-tuple is the image under a group element of the ω-tuple of distinct elements (α_{i}).

We shall now construct recursively, for i = 0, 1, …, finite sets E_{i} ⊆ D_{i}. For each i, the elements of E_{i} will be denoted e(n_{0}, …, n_{r}; π_{1}, …, π_{r}) with one such element for each choice of a sequence of natural numbers 0 = n_{0} < n_{1} < … < n_{r} = i and a sequence of permutations π_{m} ∈ Sym({n_{m−1}, …, n_{m}−1}) (1 ⩽ m ⩽ r). (Note that each e(n_{0}, …, n_{r}; π_{1}, …, π_{r}), since it belongs to D_{i}, is an i-tuple of elements of Ω, where i = n_{r}; but we shall not often write it explicitly as a string of elements. Nevertheless, we shall refer to the i elements of Ω comprising this i-tuple as its components.)

We start the recursion with E_{0} = D_{0}, which is necessarily the singleton consisting of the unique length-0 sequence. Assuming E_{0}, …, E_{i−1} given, we choose an arbitrary order in which the finitely many i-tuples in E_{i} are to be chosen. When it comes time to choose the i-tuple e(n_{0}, …, n_{r}; π_{1}, …, π_{r}) ∈ E_{i}, we define its initial substring of length n_{r−1} to be the n_{r−1}-tuple e(n_{0}, …, n_{r−1}; π_{1}, …, π_{r−1}) ∈ E_{n_{r−1}}. We then extend this to an element of D_{n_{r}} in any way such that its remaining n_{r} − n_{r−1} components are distinct from all components of all elements of E_{0} ∪ … ∪ E_{i−1}, and from all components of those elements of E_{i} that have been chosen so far. This is possible by n_{r} − n_{r−1} applications of condition (ii) above: at each step, when we extend a member of a set D_{j} to a member of the next set D_{j+1} (n_{r−1} ⩽ j < n_{r}) we have infinitely many choices available for the last component, and only finitely many elements to avoid.

Once the sets E_{i} are chosen for all i, let us define an element s ∈ Sym(Ω) to permute, in the following way, those elements of Ω that occur as components in the members of ⋃_{i} E_{i}. (On the complementary subset of Ω we let s behave in any manner, e.g., as the identity.)

(9) For each (β_{j})_{0⩽j<n_{r}} = e(n_{0}, …, n_{r}; π_{1}, …, π_{r}) ∈ E_{i}, we let s act on its last n_{r} − n_{r−1} components, β_{n_{r−1}}, β_{n_{r−1}+1}, …, β_{n_{r}−1}, by β_{j} s = β_{jπ_{r}}.

That is, we let s permute the elements β_{n_{r−1}}, …, β_{n_{r}−1} by “acting as π_{r} on their subscripts”. Note that (by the choices made in the last paragraph), for each j ∈ {n_{r−1}, …, n_{r}−1}, the occurrence of β_{j} as a component of e(n_{0}, …, n_{r}; π_{1}, …, π_{r}) is its first appearance among the components of the elements we have constructed, and that it is distinct from the elements first appearing as components of other tuples e(n′_{0}, …, n′_{r}; π′_{0}, …, π′_{r}), or in other positions of e(n_{0}, …, n_{r}; π_{1}, …, π_{r}). Thus (9) uniquely defines s on this set of elements.

Consider now any permutation of {α_{i}} of the form α_{i} ↦ α_{iπ} where π is a local permutation of ω (in the sense of Lemma 9). We claim that there exists g ∈ G such that the element s constructed above “acts as π on the subscripts” of the image sequence (α_{i} g)_{i⩾0}, i.e., such that for all i ⩾ 0,

(10) α_{i} g s = α_{iπ} g.

To show this, note that since π is local, we can find natural numbers 0 = n_{0} < n_{1} < … such that π carries each of the intervals {n_{m−1}, n_{m−1}+1, …, n_{m}−1} into itself. Let us denote the restrictions of π to these intervals by π_{m} ∈ Sym({n_{m−1}, n_{m−1}+1, …, n_{m}−1}) (m ⩾ 1), and consider the tuples (11) e(n_{0}) ∈ E_{0}, e(n_{0}, n_{1}; π_{1}) ∈ E_{n_{1}}, …,

e(n_{0}, …, n_{m}; π_{1}, …, π_{m}) ∈ E_{n_{m}}, ….

Each of these tuples extends the preceding, so there is a sequence (β_{i}) ∈ Ω^{ω} of which these tuples are all truncations. From (9) we see that the sequence (β_{i}) will satisfy β_{i} s = β_{iπ} for all i ∈ ω. Also, by our hypothesis (iii) and the condition E_{i} ⊆ D_{i}, there exists g ∈ G such that β_{i} = α_{i} g for all i. Substituting this into the relation β_{i} s = β_{iπ}, we get (10), as claimed.

Now (10) can be rewritten as saying that g s g^{−1} acts on {α_{i}} by the map α_{i} ↦ α_{iπ}. In view of Lemma 9, every permutation of {α_{i}} can be realized as the restriction to that set of a product of two such permutations, hence as g s g^{−1}h s h^{−1} for some g, h ∈ G. Thus, the group H = ⟨G ∪ {s}⟩ satisfies the hypothesis of (8) with Σ = {α_{i}}. Hence by (8) there exists x ∈ Sym(Ω) such that ⟨G ∪ {s, x}⟩ = S, completing the proof of the lemma. □

We now consider a subgroup G ⩽ Sym(Ω) satisfying (7). We shall show how to construct elements α_{i} ∈ Ω and families D_{i} ⊆ Ω^{i} satisfying conditions (i) and (ii) of the above lemma, and such that if G is closed, condition (iii) thereof also holds, allowing us to apply that lemma.

We begin with another recursion, in which we will construct for each j ⩾ 0 an element α_{j}, and a finite subset K_{j} of G, indexed

(12) K_{j} = {g(k_{0}, k_{1}, …, k_{r−1}) : k_{0}, k_{1}, …, k_{r−1}, r ∈ ω, r+k_{0}+…+k_{r−1} = j}.

To describe the recursion, assume inductively that α_{i} and K_{i} have been defined for all nonnegative i < j, and let Γ_{j} ⊆ Ω denote the finite set consisting of the images of ε_{0}, …, ε_{j−1} (cf. (6)) and of α_{0}, …, α_{j−1} under the inverses of all elements of K_{0} ∪ … ∪ K_{j−1}. Let α_{j} be any element of Ω having infinite orbit under G_{(Γ_{j})} (cf. (7)). In choosing the elements g(k_{0}, k_{1}, …, k_{r−1}) comprising K_{j}, we consider two cases.

If j = 0, we have only one element, g(), to choose, and we take this to be the identity element 1 ∈ G. A consequence of this choice is that for all larger j, we have 1 ∈ K_{0} ∪ … ∪ K_{j−1}, hence the definition of Γ_{j} above guarantees that ε_{0}, …, ε_{j−1} and α_{0}, …, α_{j−1} themselves lie in Γ_{j}.

If j > 0, we fix arbitrarily an order in which the elements of K_{j} are to be constructed. When it is time to construct g(k_{0}, k_{1}, …, k_{r−1}), let us write g′ = g(k_{0}, k_{1}, …, k_{r−2}), noting that this is a member of K_{j−k_{r−1}−1}, hence already defined. We will take for g(k_{0}, k_{1}, …, k_{r−1}) the result of left-multiplying g′ by a certain element h ∈ G_{(Γ_{r−1})}. Note that whatever value in this group we choose for h, the images of α_{0}, …, α_{r−2} under hg′ will be the same as their images under g′, since elements of G_{(Γ_{r−1})} fix α_{0}, …, α_{r−2} ∈ Γ_{r−1}. On the other hand, we may choose h so that the image of α_{r−1} under hg′ is distinct from the images of α_{r−1} under the finitely many elements of K_{0} ∪ … ∪ K_{j−1}, and also under the elements of K_{j} that have so far been constructed, since α_{r−1} has infinite orbit under G_{(Γ_{r−1})}, and there are only finitely many elements that have to be avoided. So let g(k_{0}, k_{1}, …, k_{r−1}) = hg′ be so chosen.

In this way we successively construct the elements of each set K_{j}. Note that this gives us group elements g(k_{0}, …, k_{i−1} ) for all i, k_{0}, …, k_{i−1} ∈ ω. We can thus define, for each i ∈ ω,

(13) D_{i} = {(α_{0} g, …, α_{i−1} g) : g = g(k_{0}, …, k_{i−1}) for some k_{0}, …, k_{i−1} ∈ ω}. By construction, g(k_{0}, …, k_{i}) agrees with g(k_{0}, …, k_{i−1}) on α_{0}, …, α_{i−1}, so

chopping off the last component of an element of D_{i+1} gives an element of D_{i}, establishing condition (i) of Lemma 10. Moreover, any two elements of the form g(k_{0}, …, k_{i}) ∈ D_{i+1} with indices k_{0}, …, k_{i−1} the same but different last indices k_{i} act differently on α_{i}, so the sets D_{i} satisfy condition (ii) of that lemma. Suppose, now, that (β_{i}) ∈ Ω^{ω} has the property that for every i the sequence (β_{0}, …, β_{i−1}) is in D_{i}. We see inductively that successive strings (), (β_{0}), …, (β_{0}, …, β_{i−1}), … must arise from unique elements of the forms g(), g(k_{0}), …, g(k_{0}, …, k_{i−1}), …. Moreover, by construction each of these group elements g(k_{0}, …, k_{i}) is obtained from the preceding element g(k_{0}, …, k_{i−1}) by left multiplication by an element of G_{(Γ_{i})}, where Γ_{i} contains the elements ε_{0}, …, ε_{i−1} and their inverse images under all the preceding group elements. It follows by Lemma 7 that if G is closed, the above sequence converges to an element g ∈ G whose behavior on (α_{i}) is the limit of the behaviors of these elements, i.e., which sends (α_{i}) to (β_{i}), establishing condition (iii) of Lemma 10. Hence that lemma tells us that G ≈ S.

We can now easily obtain

Theorem 11. Let Ω be a countably infinite set, and G a closed subgroup of S = Sym(Ω). Then G ≈ S (i.e., S is finitely generated over G) if and only if G satisfies (7).

Proof. We have just seen that (7) implies G ≈ S. On the other hand, if (7) does not hold, then for some finite Γ ⊆ Ω, G_{(Γ)} has only finite orbits. Letting A denote the set of these orbits, we have G_{(Γ)} ⩽ S_{(A)}. But S_{(A)} falls under case (b) or (c) of Theorem 6 (with κ = ℵ_{0}) while S falls under case (a), being determined by the improper partition of Ω. We thus get

(14) G ≈ G_{(Γ)} ⩽ S_{(A)} ≺ S, where the first relation holds by Lemma 2 and Lemma 3(i), and the final strict inequality by the last sentence of Theorem 6. Thus G ≉ S. □

Notes on the development of the above theorem: In the proof of Lemma 10, and again in the arguments following that proof, it might at first appear that our hypotheses that certain subsets of Ω were infinite (namely, in the former case, the set of “next terms” extending each member of D_{i}, and in the latter, at least one orbit of G_{(Γ)} for each finite set Γ) could have been replaced by statements that those sets could be taken to have large enough finite cardinalities, since at each step, we had to make only finitely many choices from these sets, and to avoid only finitely many elements of Ω. But closer inspection shows that we dipped into these sets for additional elements infinitely many times. In the proof of Lemma 10, this is because for fixed n_{0}, …, n_{r−1} there are infinitely many possibilities for n_{r} > n_{r−1}, and for each of these, the construction of E_{n_{r}} requires extending the elements e(n_{0}, …, n_{r−1}; π_{1}, …, π_{r−1}) ∈ D_{n_{r−1}} to elements of D_{n_{r−1}+1}. Likewise, in (12), note that r ⩽ j, and each value of r comes up for infinitely many j, so that for each r we must choose, in the long run, elements of G_{(Γ_{r−1})} having infinitely many different effects on α_{r−1}.

This spreading out of the choices we made from each infinite set, into infinitely many clumps of finitely many choices each, was necessary: If we had made infinitely many choices at one time from one of our sets, we would have had infinitely many obstructions to our choices from the next set, and could not have argued that those choices could be carried out as required.

Could the two very similar recursive constructions just referred to have been carried out simultaneously? In an earlier draft of this note they were. That arrangement was more efficient (if less transparent as to what was being proved), and could be considered preferable if one had no interest except in closed subgroups. However, the present development yields the intermediate result Lemma 10, which can be used to show the ≈-equivalence to S of many non-closed subgroups for which, so far as we can see, Theorem 11 is of no help.

For example, consider a partition A of Ω into a countably infinite family of countably infinite sets Σ_{i}, and let G be the group of permutations of Ω that, for each i, carry Σ_{i}, into itself, and move only finitely many elements of that set. If we choose an arbitrary element (α_{i}) ∈ ∏_{i} Σ_{i}, and let D_{i} = Σ_{0}×…×Σ_{i−1} for each i, then we see easily that the conditions of Lemma 10 hold, hence that G ≈ S.

(The same argument works for the subgroup of the above G consisting of those elements g for which there is a bound independent of i on the number of elements of Σ_{i} moved by g.)

6. Finite orbits of unbounded size.

In this section, we again let Ω be a countably infinite set, and will show that all closed subgroups G ⩽ S = Sym(Ω) for which

(15) There exists a finite subset Γ ⊆ Ω such that all orbits of G_{(Γ)} are finite, but no such Γ for which the cardinalities of these orbits have a common finite bound,

are mutually ≈-equivalent. The approach will parallel that of the preceding section, but there are some complications.

First, there is not one natural subgroup that represents this equivalence class, as S represented the class considered in the previous section. Instead we will begin by defining a certain natural family of closed subgroups of S which we will prove ≈-equivalent to one another. Second, we do not have a result from the literature to serve in the role of (8). So we will prove such a result. The fact that a finite symmetric group is not its own commutator subgroup will complicate the latter task. (Cf. the proof of (8) as [1, Lemma 3], which uses the fact, due to Ore [7], that every element of an infinite symmetric group is a commutator.) So we will prepare for that proof by showing that certain infinite products of finite symmetric groups within S are ≈-equivalent to the corresponding products of alternating groups.

To define our set of representatives of the ≈-equivalence class of subgroups of S we are interested in, let

(16) P = {A : A is a partition of Ω into finite subsets, and there is no common finite bound on the cardinalities of the members of A }.

For A ∈ P (and S_{(A)} defined by (3)), we see that

(17) S_{(A)} ≅ ∏_{Σ∈A} Sym(Σ).

Note that if a partition A_{1} is the image of a partition A_{2} under a permutation f of Ω, then S_{(A_{2})} is the conjugate of S_{(A_{1})} by f; in particular, S_{(A_{1})} ≈ S_{(A_{2})}. Let us now show more; namely, that

(18) S_{(A)} ≈ S_{(B)} for all A, B ∈ P.

We claim first that given A, B ∈ P, we can find two elements f, g ∈ S such that

(19) For each Σ ∈ B there exists Δ ∈ A such that Σ ⊆ Δf or Σ ⊆ Δg. Indeed, write B as the disjoint union of any two infinite subsets B_{1} and B_{2}. We may construct f by defining it on one member of A after another, making sure that each member of B_{1} ends up within the image Δf of some sufficiently large Δ ∈ A. We map those members of A or subsets of members of A that are not used in this process into the infinite set ⋃_{Σ∈B_{2}} Σ, and we also make sure to include every element of ⋃_{Σ∈B_{2}} Σ in the range of f, so that f is indeed a permutation. We similarly construct g so that every member of B_{2} is contained in the image Δg of some Δ ∈ A. Condition (19) is thus satisfied.

For such f and g, we claim that

(20) S_{(B)} ⊆ (f^{−1}S_{(A)}f)(g^{−1}S_{(A)} g). Indeed, every element of S_{(B)} can be written as the product of a member of S_{(B)} which moves only elements of ⋃_{Σ∈B_{1}} Σ and one which moves only elements of ⋃_{Σ∈B_{2}} Σ; and these can be seen to belong to f^{−1}S_{(A)}f and to g^{−1}S_{(A)} g respectively.

Thus S_{(B)} ⩽ ⟨S_{(A)} ∪ {f, g}⟩, so S_{(B)} ≼ S_{(A)}. Since this works both ways, we get (18), as desired.

We next prepare for the difficulties concerning alternating groups versus symmetric groups. Let A be a partition belonging to P which contains infinitely many singletons, and whose other members are all of cardinality at least 4, and let S_{(A)}^{even} denote the subgroup of S_{(A)} which acts by an even permutation on each member of A. We shall show that

(21) S_{(A)}^{even} ≈ S_{(A)}.

To do this, let us list the non-singleton members of A as Σ_{0}, Σ_{1}, …, and for each i choose in Σ_{i} four distinct elements, which we name α_{4i}, α_{4i+1}, α_{4i+2}, α_{4i+3}. Let B denote the partition of Ω (not belonging to P) whose only nonsingleton subsets are the two-element sets {α_{2j}, α_{2j+1}} (j ⩾ 0). Thus S_{(B)} can be identified with (ℤ/2ℤ)^{ω}, and S_{(B)} ∩ S_{(A)}^{even} can be seen to correspond to the subgroup {(a_{0}, a_{1}, …) ∈ (ℤ/2ℤ)^{ω} : (∀ i ⩾ 0) a_{2i} = a_{2i+1}}.

Let us now choose from the union of the singleton members of A infinitely many elements, which we will denote α_{i} for i < 0, and let f ∈ S be any permutation such that α_{i}f = α_{i+2} for all i ∈ ℤ. Then we see that the conjugation map g ↦ f^{−1}gf will carry S_{(B)} into itself, by a homomorphism which, identifying S_{(B)} with (ℤ/2ℤ)^{ω}, takes the form (a_{0}, a_{1}, …) ↦ (0, a_{0}, a_{1}, …). Now it is not hard to see that every member of (ℤ/2ℤ)^{ω} can be written (uniquely) as the sum of an element whose 2ith and 2i+1st coordinates are equal for each i, and an element whose 0th coordinate is 0 and whose 2i+1st and 2i+2nd coordinates are equal for all i. Hence

(22) S_{(B)} = (S_{(B)} ∩ S_{(A)}^{even}) ( f^{−1}(S_{(B)} ∩ S_{(A)}^{even})f ) ⩽ ⟨S_{(A)}^{even} ∪ {f}⟩.

We also see that S_{(A)} = S_{(B)}S_{(A)}^{even}. (For, given any h ∈ S_{(A)} which we wish to represent in this way, a factor in S_{(B)} can be chosen which gives a permutation of the desired parity on each Σ_{i} ∈ A, and a factor in S_{(A)}^{even} then turns this into the desired permutation h.) Hence S_{(A)} ⩽ ⟨S_{(A)}^{even} ∪ {f}⟩, so (21) holds.

We can now obtain our analog of (8). Suppose that

(23) H is a subgroup of S, and A an infinite family of disjoint nonempty subsets of Ω, of unbounded finite cardinalities, such that writing Δ = ⋃_{Σ∈A} Σ, every member of Sym(Δ)_{(A)} extends to an element of H_{{Δ}}.

That is, we assume we can find elements of H which give any specified family of permutations of the sets Σ comprising A – but we don’t assume that we can control what they do off those sets. We claim that by adjoining to H one element from S, we can get a group which contains a subgroup S_{(A′)}^{even} for some A′ ∈ P satisfying the conditions stated before (21) (infinitely many singletons, all other members having cardinality ⩾ 4).

To do this let us split the set A of (23) into three infinite disjoint subsets, A = A_{1} ∪ A_{2} ∪ A_{3}, in any way such that A_{1} has members of unbounded finite cardinalities and no members of cardinality < 4. If we let Δ_{1} = ⋃_{Σ∈A_{1}} Σ, Δ_{2} = ⋃_{Σ∈A_{2}} Σ, Δ_{3} = Ω − Δ_{1} − Δ_{2}, we see that these sets each have cardinality ℵ_{0} (the last because it contains ⋃_{Σ∈A_{3}} Σ). Since Δ_{1} ∪ Δ_{2} ⊆ Δ, it follows from (23) that

(24) For every f ∈ Sym(Δ_{1})_{(A_{1})} there exists an f′ ∈ H which agrees with f on Δ_{1}, and acts as the identity on Δ_{2}.

Now take any g ∈ S that interchanges Δ_{2} and Δ_{3}, and fixes Δ_{1} pointwise. Conjugating (24) by g gives

(25) For every f ∈ Sym(Δ_{1})_{(A_{1})} there exists an f′ ∈ g^{−1}H g which agrees with f on Δ_{1} and acts as the identity on Δ_{3}.

Now if one forms the commutator of a permutation which acts as the identity on Δ_{2} and preserves Δ_{3} with a permutation which acts as the identity on Δ_{3} and preserves Δ_{2}, one gets an element which acts as the identity on Δ_{2} ∪ Δ_{3}. Hence from (24) and (25) we may conclude that ⟨H ∪{g}⟩ contains elements which act as the identity on Δ_{2} ∪ Δ_{3} = Ω − Δ_{1}, while acting on each Σ ∈ A_{1} by any specified commutator in Sym(Σ). Moreover, in the symmetric group on a finite set Σ, the commutators are precisely the even permutations [7, Theorem 1]; so letting A′ be the partition of Ω consisting of the members of A_{1} and all singleton subsets of Ω − Δ_{1}, we have

(26) ⟨H ∪ {g}⟩ ⩾ S_{(A′)}^{even}.

Combining with (21), we get our analog of (8), namely

(27) If H satisfies (23), then H ≽ S_{(A′)} for some (hence by (18), for all)

A′ ∈ P. With the help of (27) we can now prove a strengthening thereof, analogous to

Lemma 10 of the preceding section:

Lemma 12. Let Ω be a countably infinite set and G a subgroup of Sym(Ω), and suppose there exist a sequence of distinct elements (α_{i})_{i∈ω} ∈ Ω^{ω}, an unbounded sequence of positive integers (N_{i})_{i∈ω}, and a sequence of sets D_{i} ⊆ Ω^{i} (i ∈ ω), such that

(i) For each i ∈ ω and each (β_{0}, …, β_{i}) ∈ D_{i+1}, we have (β_{0}, …, β_{i−1}) ∈ D_{i}; (ii) For each i ∈ ω and each (β_{0}, …, β_{i−1}) ∈ D_{i}, there exist at least N_{i} elements β ∈ Ω such that (β_{0}, …, β_{i−1}, β) ∈ D_{i+1}; and (iii) If (β_{i})_{i∈ω} ∈ Ω^{ω} has the property that (β_{0}, …, β_{i−1}) ∈ D_{i} for each i ⩾ 0, then there exists g ∈ G such that (β_{i}) = (α_{i} g) in Ω^{ω}.

Then G ≽ S_{(A)} for some, equivalently, for all A ∈ P.

Proof. This will be similar to the proof of Lemma 10, but with two simplifications and one complication. The simplifications are, first, that we will not need to handle simultaneously strings of permutations (π_{1}, …, π_{r}) for all decompositions of {0, …, i−1} as {0, …, n_{1}−1} ∪ … ∪ {n_{r−1}, …, n_{r}−1}, but only for a single decomposition, and, secondly, that we will not have infinite families of choices that have to be spread out over successive rounds of the construction, as discussed at the end of the last section. The complication is that in general not all of the N_{i} in our hypothesis will be large enough for our immediate purposes; hence each time we move to longer strings of indices, we will have to jump forward to a value i = i(j) such that N_{i(j)} is large enough.

We begin by fixing an arbitrary increasing sequence of natural numbers 0 = n_{0} < n_{1} < …, such that the successive differences n_{m} −n_{m−1} are unbounded. We shall now construct recursively integers −1 = i(−1) < i(0) < … < i(j) < …, and for each r ⩾ 0 a subset E_{r} ⊆ D_{i(n_{r}−1)+1}. The elements of each E_{r} will be denoted e(π_{1}, …, π_{r}), where π_{m} ∈ Sym({n_{m−1}, n_{m−1}+1, …, n_{m}−1}) for m = 1, …, r.

We again begin with E_{0} = D_{0} = the singleton consisting of the empty string. Now assume inductively for some r that i(0), …, i(n_{r−1}−1) and E_{0}, …, E_{r−1} have been constructed. We want to choose n_{r} −n_{r−1} values i(n_{r−1}), …, i(n_{r}−1) ∈ ω and extend each e(π_{1}, …, π_{r−1}) ∈ E_{r−1} to a family of elements e(π_{1}, …, π_{r}) ∈ D_{i(n_{r}−1)+1}, obtaining one such extension for each π_{r} ∈ Sym({n_{r−1}, …, n_{r}−1}), in such a way that

(28) The components of each (i(n_{r}−1)+1)-tuple e(π_{1}, …, π_{r}) which correspond to the n_{r} − n_{r−1} indices i(n_{r−1}), i(n_{r−1}+1), …, i(n_{r}−1) are distinct from each other, from those components of the other i(n_{r})-tuples e(π′_{1}, …, π′_{r}) ((π′_{1}, …, π′_{r}) ≠ (π_{1}, …, π_{r})) corresponding to any of the indices i(n_{r−1}), i(n_{r−1} + 1), …, i(n_{r}−1), and also from the components of the elements of E_{r−1} with indices i(0), i(1), …, i(n_{r−1}−1).

Hence let us choose values i(n_{r−1}), …, i(n_{r}−1) such that N_{i(n_{r−1})}, N_{i(n_{r−1}+1)}, …, N_{i(n_{r}−1)} are all ⩾ |E_{r−1}|((n_{r} −n_{r−1}) (n_{r} −n_{r−1})! + n_{r−1}). (The factor n_{r} − n_{r−1} represents the number of new components of each string referred to in (28); (n_{r} − n_{r−1})! is the number of values of π_{r}, and the final summand n_{r−1} is the number of components of each member of E_{r−1} that we also have to avoid.) Using these i(j), it is not hard to see from our hypothesis (ii) that we can indeed extend our strings e(π_{1}, …, π_{r−1}) ∈ D_{i(n_{r−1}−1)+1} to strings e(π_{1}, …, π_{r}) ∈ D_{i(n_{r}−1)+1} so that (28) holds.

As in the proof of Lemma 10 we now choose a single permutation s of Ω, this time such that

(29) For each e(π_{1}, …, π_{r}) = (β_{j})_{0⩽j<n_{r}} ∈ E_{r}, the element s acts on the components β_{i(n_{r−1})}, β_{i(n_{r−1}+1)}, …, β_{i(n_{r}−1)} of this tuple so that β_{i(j)} s = β_{i(jπ_{r})}.

Now let Δ be the set {α_{i(j)} : j ⩾ 0}, and let A be the partition of Δ into subsets Σ_{r} = {α_{i(j)} : n_{r−1} ⩽ j < n_{r}} (r ⩾1). Thus the general element of Sym(Δ)_{(A)} has the form α_{i(j)} ↦ α_{i(jπ)} for some π ∈ Sym(ω) that preserves each set {n_{r−1}, …, n_{r}−1}. We claim that for any such permutation π, there is a g ∈ G such that s “acts as π on the subscripts” of the translated sequence (α_{i(j)} g)_{j⩾0}, i.e., such that for all j ⩾ 0,

(30) α_{i(j)} g s = α_{i(jπ)} g.

Indeed, given π, if for each r ⩾ 1 we let π_{r} ∈ Sym({n_{r−1}, …, n_{r}−1}) denote the restriction of π to {n_{r−1}, …, n_{r}−1}, then as in the proof of Lemma 10, the strings e(), e(π_{1}), e(π_{1}, π_{2}), … fit together to give a string (β_{i}) such that (29) says that s “acts like π ” on the components of (β_{i}) indexed by the i(j) (j ∈ ω). By hypothesis (iii), we can write (β_{i}) as (α_{i} g) so this condition becomes (30).

But (30) can be read as saying that g s g^{−1} acts on Δ as the arbitrary element α_{i(j)} ↦ α_{i(jπ)} of Sym(Δ)_{(A)}; hence letting H = ⟨G ∪ {s}⟩, (23) holds, so by (27), G ≽ S_{(A′)} for some A′ ∈ P, completing the proof of the lemma. □

The next argument also parallels what we did in the preceding section (though it will be less convoluted): For any G ⩽ Sym(Ω) satisfying (15), we shall obtain families D_{i} satisfying conditions (i) and (ii) of the above lemma, and such that if G is closed, condition (iii) also holds.

Assume G ⩽ Sym(Ω) satisfies (15), and fix an unbounded sequence of positive integers (N_{i})_{i∈ω}. We shall begin by constructing for each j ⩾ 0 a certain element α_{j}, and a certain finite subset K_{j} of G, which will be indexed

(31) K_{j} = {g(k_{0}, k_{1}, …, k_{j−1}) : 0 ⩽ k_{i} < N_{i} (0 ⩽ i < j)}. Again, K_{0} will have only one member, g(), which we take to be 1 ∈ G.

Let us assume inductively for some j ⩾ 0 that elements α_{i} have been defined for all i < j and that subsets K_{i} have been defined for all i ⩽ j. Let Γ_{j} ⊆ Ω denote (essentially as before) the set of images of ε_{0}, …, ε_{j−1} and of α_{0}, …, α_{j−1} under inverses of elements of K_{0} ∪ … ∪ K_{j}. Let α_{j} be any element of Ω not fixed by G_{(Γ_{j})}, whose orbit under that group has cardinality at least |K_{j}| N_{j}; such an element exists by (15).

We now fix an arbitrary order in which we shall construct the elements g(k_{0}, k_{1}, …, k_{j}) of K_{j+1}. When it is time to construct g(k_{0}, k_{1}, …, k_{j}), we set g′ = g(k_{0}, k_{1}, …, k_{j−1}), and left-multiply this by any element h ∈ G_{(Γ_{j})} with the property that α_{j} hg′ is distinct from the images of α_{j} under those elements of K_{j} so far constructed. Our choice of α_{j} insures that its orbit under G_{(Γ_{j})} is large enough so that collisions with all such elements can be avoided, and we define g(k_{0}, k_{1}, …, k_{j}) to be the product hg′.

For each i we then define the sets D_{i} by

(32) D_{i} = {(α_{0} g, …, α_{i−1} g) : g ∈ K_{i} }.

We now see exactly as before that conditions (i) and (ii) of Lemma 12 are satisfied, and that if G is closed, we can use Lemma 7 to get condition (iii) as well, so by Lemma 12, G ≽ S_{(A)} for some A ∈ P.

On the other hand, the reverse inequality is immediate: Taking any Γ as in the first clause of (15) and letting B denote the set of orbits of G_{(Γ)}, so that B ∈ P, we get G ≈ G_{(Γ)} ⩽ S_{(B)} ≈ S_{(A)} (where the first relation holds by Lemma 2 and Lemma 3(ii)). Combining these inequalities we have G ≈ S_{(A)}.

This completes the main work of the proof of

Theorem 13. Let Ω be a countably infinite set, and P the set of partitions of Ω defined in (16). Then the subgroups S_{(A)} ⩽ S with A ∈ P (which are clearly all closed) are mutually ≈-equivalent, and a closed subgroup G ⩽ S belongs to the equivalence class of those subgroups if and only if it satisfies (15).

Moreover, the members of this ≈-equivalence class are ≺ the members of the equivalence class of Theorem 11.

Proof. We have so far proved mutual equivalence of the S_{(A)}, and the sufficiency of (15) for membership of a closed subgroup G in their common equivalence class. To see necessity, consider any closed subgroup G which does not satisfy (15). Then either G satisfies (7), or there exists a finite set Γ such that G_{(Γ)} has orbits of bounded finite cardinality.

In the former case, Theorem 11 shows that G ≈ S; but from the “only if” direction of that theorem we see that for A ∈ P we have S_{(A)} ≉ S, and hence G ≉ S_{(A)}.

In the case where some G_{(Γ)} has all orbits of bounded finite cardinality, let A be the partition of Ω consisting of those orbits. Then G ≈ G_{(Γ)} ≼ S_{(A)}, and by the last sentence of Theorem 6, S_{(A)} is not ≽ the members of the equivalence class of this section, hence G is not in that equivalence class.

In the final sentence, the inequality ≼ holds because the equivalence class of Theorem 11 contains S itself. We have just seen that the two classes in question are distinct, so we have strict inequality ≺ . □

7. Orbits of bounded size.

Moving on to still smaller subgroups, we now consider G ⩽ S satisfying

(33) There exists a finite subset Γ ⊆ Ω and a positive integer n such that the cardinalities of all the orbits of G_{(Γ)} are bounded by n, but there exists no such Γ with G_{(Γ)} = {1}.

Analogously to (16), we define

(34) Q = {A : A is a partition of Ω for which there is a common finite bound to the cardinalities of the members of A, and such that infinitely many members of A have cardinality > 1}.

Unlike the P of the preceding section, Q has, up to isomorphism, a natural distinguished member, namely a least isomorphism class with respect to refinement:

(35) We will denote by A_{0} an element of Q, unique up to isomorphism, which has infinitely many 1-element members, infinitely many 2element members, and no others.

Clearly any A ∈ Q can be refined to a partition A′_{0} isomorphic to A_{0}, hence S_{(A)} ⩾ S_{(A′_{0})} ≈ S_{(A_{0})}, so S_{(A)} ≽ S_{(A_{0})}. We claim that the reverse inequality S_{(A)} ≼ S_{(A_{0})} also holds. To show this, let us draw a graph with the elements of Ω as vertices, and with edges making each member of our given partition A a chain (in an arbitrary way), and no other edges. Now color the edges of each such chain alternately red and green, subject to the condition that infinitely many chains have a terminal red edge and infinitely many have a terminal green edge. Clearly, the partition of Ω whose non-singleton members are the pairs of points linked by red edges, all other points forming singletons, is isomorphic to A_{0}; hence the group of permutations whose general member acts by transposing an arbitrary subset of the red-linked pairs of vertices and fixing everything else can be written f^{−1}S_{(A_{0})}f for some f ∈ Sym(Ω). Similarly, the group of permutations which act by transposing some pairs of green-linked vertices and fixing everything else can be written g^{−1}S_{(A_{0})} g. Moreover, for each Σ ∈ A, any permutation of Σ can be obtained by composing finitely many permutations, each of which acts either by interchanging only red-linked pairs or by interchanging only green-linked pairs (this is easiest to see by looking at permutations that interchange one such pair at a time); and the number of such factors needed can be bounded in terms of the cardinality of Σ. Since there is a common bound to the cardinalities of the sets Σ ∈ A, we see that every member of S_{(A)} can be written as a finite product of members of f^{−1}S_{(A_{0})}f and g^{−1}S_{(A_{0})}g, so ⟨S_{(A_{0})}∪{f, g}⟩ ⩾ S_{(A)}, so S_{(A_{0})} ≽ S_{(A)}. Combining this with the observation at the start of this paragraph, we get S_{(A_{0})} ≈ S_{(A)}, so

(36) S_{(A)} ≈ S_{(B)} for all A, B ∈ Q.

We obtain next the result that will play the role that (8) played in §5 and (27) played in §6. The development will be similar to the latter case, though simpler. Suppose that (37) H is a subgroup of S, and A an infinite family of disjoint 2-element

subsets of Ω such that, writing Δ = ⋃_{Σ∈A} Σ, every member of Sym(Δ)_{(A)} extends to an element of H_{{Δ}}.

(Again we do not assume we have any control over the behavior of these elements outside of Δ, though again our goal will be to get such control in an extended subgroup.) Let us index A by ℤ, writing A = {Σ_{i} : i ∈ ℤ}, and let h be an element of S which for each i ∈ ℤ sends Σ_{i} bijectively to Σ_{i+1}, and which fixes all elements of Ω−Δ. We claim that as f runs over all elements of H_{{Δ}} that extend elements of Sym(Δ)_{(A)}, the commutators h^{−1}f^{−1}hf all fix Ω − Δ pointwise, and their restrictions to Δ give all elements of Sym(Δ)_{(A)}. The first fact holds because h fixes Ω − Δ pointwise. The second may be seen by looking at h^{−1}f^{−1}hf as (h^{−1}f^{−1}h)f, noting that both factors are members of Sym(Δ)_{(A)}, and examining their behaviors on the general 2-element set Σ_{i} ∈ A. One sees that (h^{−1}f^{−1}h)f acts by the trivial permutation on Σ_{i} if and only if f acts trivially either on both of Σ_{i−1} and Σ_{i}, or on neither, while (h^{−1}f^{−1}h)f acts by the nonidentity element of Sym(Σ_{i}) in the remaining cases. One easily deduces that by appropriate choice of f one can get an arbitrary action on the family of subsets Σ_{i}.

Thus ⟨H ∪ {h}⟩ contains a subgroup conjugate in S to S_{(A_{0})}, proving

(38) If H satisfies (37), then H ≽ S_{(A_{0})}.

The result analogous to Lemmas 10 and 12 will be quite simple to state and prove this time:

Lemma 14. Let Ω be a countably infinite set and G a subgroup of Sym(Ω), and suppose there exist two disjoint sequences of distinct elements, (α_{i}), (β_{i}) ∈ Ω^{ω}, such that for every element (γ_{i}) ∈ ∏_{i∈ω}{α_{i}, β_{i}} ⊆ Ω^{ω}, there exists g ∈ G such that (γ_{i}) = (α_{i} g).

Then G ≽ S_{(A_{0})}.

Proof. Let Δ = {α_{i} : i ∈ ω}, let A be the partition of Δ whose members are the two-element sets {α_{2j}, α_{2j+1}} (j ⩾ 0), and let s ∈ Sym(Ω) be any element which fixes all the elements α_{i} and interchanges β_{2j} and β_{2j+1} for all j ⩾ 0. We claim that every member of Sym(Δ)_{(A)} extends to an element of ⟨G ∪ {s}⟩.

Indeed, given f ∈ Sym(Δ)_{(A)}, define (γ_{i}) ∈ Ω^{ω} by letting γ_{i} = β_{i} if α_{i} is moved by f (i.e., if it is transposed with the other member of its A-equivalence class) and γ_{i} = α_{i} otherwise. By hypothesis we can find g ∈ G such that γ_{i} = α_{i} g for all i. It is now easy to see that g s g^{−1} acts by f on Δ.

Thus ⟨G ∪ {s}⟩ satisfies (37), so by (38), S_{(A_{0})} ≼ ⟨G ∪ {s}⟩ ≈ G. □

As the pattern of the two preceding sections suggests, we will now prove that any closed subgroup G satisfying (33) satisfies the hypothesis of the above lemma. We begin with a reduction: Assuming (33), let M > 1 be the largest integer such that for every finite subset Γ ⊆ Ω, the group G_{(Γ)} has orbits of cardinality at least M. Thus, there exists some finite Δ such that G_{(Δ)} has no orbits of cardinality > M. Since G_{(Δ)} inherits from G the property (33), we may replace G by G_{(Δ)} and so assume without loss of generality that (39) For every finite subset Γ ⊆ Ω, the maximum of the cardinalities of

the orbits of G_{(Γ)} is M.

A consequence is that for any such Γ, every orbit of G_{(Γ)} of cardinality M is also an orbit of G (since the orbit of G containing it cannot have larger cardinality). Thus

(40) If Γ is a finite subset of Ω, and α an element of Ω such that |α G_{(Γ)} | = M, then for every g ∈ G we have α G_{(Γ)} g = α G_{(Γ)}.

We shall now construct recursively, for each j ⩾ 0, elements α_{j}, β_{j} ∈ Ω and a subset K_{j} ⊆ G, indexed as

(41) K_{j} = {g(k_{0}, k_{1}, …, k_{j−1}) : (k_{0}, k_{1}, …, k_{j−1}) ∈ {0, 1}^{j} }.

Again we start with K_{0} = {g()} = {1}. Assuming inductively for some j ⩾ 0 that α_{i}, β_{i} have been defined for all i < j and K_{i} for all i ⩽ j, we let Γ_{j} ⊆ Ω denote the set all of images of ε_{0}, …, ε_{j−1}, α_{0}, …, α_{j−1}, β_{0}, …, β_{j−1} under inverses of elements of K_{0} ∪ … ∪ K_{j}. By assumption, G_{(Γ_{j})} has an M-element orbit. Let α_{j} and β_{j} be any two distinct elements of such an orbit. (Note that α_{j} and β_{j} are distinct from all α_{i}, β_{i} for i < j, since the latter are fixed by G_{(Γ_{j})}.) For each (k_{0}, …, k_{j−1}) ∈ {0, 1}^{j}, we let g(k_{0}, …, k_{j−1}, 0) and g(k_{0}, …, k_{j−1}, 1) be elements of G obtained by left-multiplying g(k_{0}, …, k_{j−1}) ∈ K_{j} by an element h ∈ G_{(Γ_{j})}, chosen so that α_{j} hg(k_{0}, …, k_{j−1}) is α_{j}, respectively β_{j}. This is possible by (40).

Given an infinite string (k_{i}) of 0’s and 1’s, the elements g(k_{0}, k_{1}, …, k_{j−1}) will again converge in S by Lemma 7. Assuming G closed, the limit belongs to G, and clearly gives us the hypothesis of Lemma 14, hence the conclusion that G ≽ S_{(A_{0})}.

Again we easily get the reverse inequality: Taking Γ as in the first clause of (33) and letting A denote the partition of ω into orbits of G_{(Γ)}, we have G ≈ G_{(Γ)} ⩽ S_{(A)} ≈ S_{(A_{0})} by (36).

We deduce

Theorem 15. Let Ω be a countably infinite set, and Q the set of partitions of Ω defined in (34). Then the subgroups S_{(A)} ⩽ S for A ∈ Q (which are clearly closed) are mutually ≈-equivalent, and a closed subgroup G ⩽ S belongs to the equivalence class of those subgroups if and only if it satisfies (33).

The members of this ≈-equivalence class are ≺ the members of the equivalence class of Theorem 13.

Proof. This is obtained using the above results exactly as Theorem 13 was obtained from the results of the preceding section, except that we need a different argument to show that G does not belong to the ≈-equivalence class in question if it does not satisfy the final clause of (33), i.e., if there exists a finite subset Γ ⊆ Ω such that G_{(Γ)} = {1}. In that situation, any subgroup ≈ G will be ≈ {1}, hence countable; but clearly S_{(A_{0})} is uncountable, so S_{(A_{0})} ≉ G. □

8. Countable subgroups.

The final step of our classification is now easy, and we even get a little extra information:

Theorem 16. The countable subgroups of S = Sym(Ω) form an equivalence class under ≈, and members of this class are ≺ the members of the equivalence class of Theorem 15. Moreover, for G ⩽ S, the following conditions are equivalent.

(i) G is countable and closed. (ii) There exists a finite subset Γ ⊆ Ω such that G_{(Γ)} = {1}. (iii) G is discrete.

Proof. The countable subgroups are clearly the subgroups ≈_{ℵ_{1}}{1}, and as noted in Lemma 3, for subgroups of symmetric groups Sym(Ω), ≈_{ℵ_{1}}-equivalence is the same as ≈_{ℵ_{0}}-equivalence, which is what we are calling ≈-equivalence. This gives the first assertion; the second is also immediate, since the trivial subgroup is ≼ all subgroups, and is ≉ the subgroups of Theorem 15 by the “only if” assertion of that theorem.

To prove the equivalence of (i)–(iii), we note first that (ii) and (iii) are equivalent, since a neighborhood basis of the identity in the function topology on G is given by the subgroups G_{(Γ)} for finite Γ, so the identity element (and hence by translation, every element) is isolated in G if and only if some such subgroup is trivial.

To see that these equivalent conditions imply (i), observe that (ii) implies that G ≈ G_{(Γ)} = {1}, hence that G is countable, while (iii) implies that G is closed, by general properties of topological groups. (If G is a discrete subgroup of a topological group S, take a neighborhood U of 1 in S containing no nonidentity element of G, and then a neighborhood V of 1 such that V V^{−1} ⊆ U. One finds that for any x ∈ S, xV is a neighborhood of x containing at most one element of G; so G has no limit points in S.)

Conversely, we have seen that any countable G is ≺ the members of the equivalence class of Theorem 15, hence does not belong to the equivalence class of any of Theorems 11, 13 or 15. Hence if G is also closed, those theorems exclude all possible behaviors of its subgroups G_{(Γ)} (for Γ finite) other than that there exist such a Γ with G_{(Γ)} = {1}; so (i) implies (ii). □

For convenience in subsequent discussion, let us name the four equivalence classes of subgroups of S = Sym(Ω) which we have shown to contain all closed subgroups:

(42) C_{S} = the ≈-equivalence class of S. C_{P} = the ≈-equivalence class to which S_{(A)} belongs for all A ∈ P. C_{Q} = the ≈-equivalence class to which S_{(A)} belongs for all A ∈ Q. C_{1} = the ≈-equivalence class consisting of the countable subgroups

of S.

9. Notes and questions on groups of bounded permutations.

It would be of interest to investigate the equivalence relation ≈ on classes of subgroups G ⩽ Sym(Ω) other than the class of closed subgroups. One such class is implicit in the techniques used above: If Ω is any set and d a generalized metric on Ω, let us define the subgroup

(43) FN(Ω, d) = {g ∈ Sym(Ω) : ||g||_{d} < ∞}. (We write FN, for “finite norm”, rather than B for “bounded” to avoid confusion with the symbol for an open ball.) These subgroups are not in general closed. For instance, if d does not assume the value ∞ (i.e., if it is an ordinary metric) but is unbounded (say the standard distance metric on Ω = ω ⊆ ℝ), then by the former condition, FN(Ω, d) contains all permutations of Ω that move only finitely many elements, which form a dense subgroup of S = Sym(Ω), while by the unboundedness of d, it is nevertheless a proper subgroup of S, hence it is not closed.

Here are some easy results about the relation ≼ on these subgroups. (Cf. also [11].) Below, “uncrowded” means ℵ_{0}-uncrowded.

Lemma 17. Let d be a generalized metric on a countably infinite set Ω.

(i) If d is not uncrowded, then FN(Ω, d) ∈ C_{S}. (ii) If d is uncrowded but not uniformly uncrowded, then FN(Ω, d) is ≽ the groups in C_{P}, but is ∉ C_{S}. (iii) If d is uniformly uncrowded, but for some r < ∞, infinitely many of the balls B_{d}(α, r) contain more than one element, then FN(Ω, d) is ≽ the groups in C_{Q}, but ⋡ the groups in C_{P}. (iv) If d is uncrowded and for each r < ∞ all but finitely many balls B_{d}(α, r) are singletons, then FN(Ω, d) ∈ C_{1}.

Proof. In situation (i), let B_{d}(α, r) be a ball of finite radius containing infinitely many elements. Then all g ∈ Sym(Ω)_{(Ω−B_{d}(α,r))} satisfy ||g||_{d} ⩽ 2r, hence lie in FN(Ω, d), and the conclusion follows by (8).

In cases (ii) and (iii) we can similarly find subgroups of FN(Ω, d) of the form S_{(A)} for A ∈ P, respectively A ∈ Q, while the last sentence of Theorem 5 gives the negative statements for these two cases.

For d as in (iv), each set {g ∈ Sym(Ω) : ||g||_{d} < n} (n ∈ ω) is finite, so their union, FN(Ω, d), is countable. □

Thus, if a group FN(Ω, d) belongs to one of the four ≈-equivalence classes of (42), the above lemma determines precisely which class that must be.

Note that our definition (43) can be rewritten

(44) FN(Ω, d) = ⋃_{n∈ω} {g ∈ S : ||g||_{d} < n}. We claim that if the generalized metric d is uncrowded, then for each n the set {g∈S : ||g||_{d} < n} is compact. Indeed, the condition ||g||_{d} < n determines, for each α ∈ Ω, a certain finite set of possibilities for αg; so {g∈S : ||g||_{d} < n} is the intersection of S with a certain compact subset of Ω^{Ω} . But for each α ∈ Ω, the condition ||g||_{d} < n also limits us to finitely many possibilities for αg^{−1}, from which it can be deduced that any limit in Ω^{Ω} of elements g ∈ S with ||g||_{d} < n is again surjective, hence again belongs to S. So {g∈S : ||g||_{d} < n} is closed in a compact subset of Ω^{Ω}, hence, as claimed, is compact. This makes FN(Ω, d) a countable union of compact sets, suggesting the second part of

Question 18. If d is an uncrowded generalized metric on a countably infinite set Ω, must FN(Ω, d) belong to one of the ≈-equivalence classes of (42)?

More generally, does every subgroup of Sym(Ω) that is a union of countably many compact subsets belong one of these classes? What about subgroups that are unions of countably many closed subsets? What about Borel subgroups? Analytic subgroups?

If the answer to any of these questions is negative, can one describe all the ≈-equivalence classes to which such subgroups belong?

Let us sketch a couple of cases where it is not hard to show that FN(Ω, d) does belong to one of the equivalence classes of (42).

Let d be the standard distance function on ω (inherited from ℝ). To show that FN(ω, d) ∈ C_{Q}, let A_{1} be the partition of ω consisting of the subsets {2m, 2m+1} (m ∈ ω), and A_{2} the partition consisting of the subsets {2m+1, 2m+2} and the singleton {0}. Then A_{1}, A_{2} ∈ Q, so ⟨S_{(A_{1})} ∪S_{(A_{2})}⟩ ∈ C_{Q}. This subgroup is clearly contained in FN(ω, d); we claim that equality holds.

Indeed, given f ∈ FN(ω, d) with ||f||_{d} = n, if we let Σ_{i} = {ni, ni+1, …, n(i+1) − 1} for i ⩾ 0 and Σ_{−1} = ∅, then we see that for all i ⩾ 0, Σ_{i}f ⊆ Σ_{i−1} ∪ Σ_{i} ∪ Σ_{i+1}. Letting B_{1} be the partition of ω into the subsets Σ_{2i} ∪ Σ_{2i+1} and B_{2} the partition into the subsets Σ_{2i−1} ∪ Σ_{2i} (i ⩾ 0), we see as in the second paragraph of the proof of Lemma 9 that f ∈ S_{(B_{1})}S_{(B_{2})}. On the other hand, it is easy to show that S_{(B_{1})} and S_{(B_{2})} are both contained in ⟨S_{(A_{1})} ∪ S_{(A_{2})}⟩, using the fact that any permutation of a 2n-element string of integers Σ_{2i} ∪ Σ_{2i+1} or Σ_{2i−1} ∪ Σ_{2i} can be written as a product of finitely many transpositions of consecutive terms, and that the number of transpositions needed can be bounded in terms of n (cf. end of paragraph preceding (36)). So f ∈ ⟨S_{(A_{1})} ∪ S_{(A_{2})}⟩, as claimed, so FN(ω, d) ∈ C_{Q}.

In the above example, the argument cited from the proof of Lemma 9 uses the fact that for any f ∈ FN(ω, d), the number of elements that f carries upward past a given point is equal to the number that it carries downward past that point. If we modify this example by replacing ω with ℤ, again with the standard metric, that property no longer holds, as shown by the translation function t: n ↦ n+1. It is not hard to see, however, that given f ∈ FN(ℤ, d), the difference between the number of elements that f moves upward and downward past a given point is the same for all points, and that the function associating to f the common value of this difference is a homomorphism v: FN(ℤ, d) → ℤ. If we let A_{1} denote the partition of ℤ into sets {2m, 2m+1} and A_{2} the partition into sets {2m+1, 2m+2}, we see that S_{(A_{1})} and S_{(A_{2})} lie in the kernel of v, while v(t) = 1. The argument of the preceding paragraph can be adapted to show that ⟨S_{(A_{1})} ∪ S_{(A_{2})} ⟩ = ker(v), hence that ⟨S_{(A_{1})} ∪S_{(A_{2})} ∪{t}⟩ = FN(ℤ, d); so this group also belongs to C_{Q}. (For some further properties of this example see Suchkov [9], [10], where FN(ℤ, d) and its subgroup ker(t) are called Ḡ and G respectively.)

An example that falls under case (ii) of Lemma 17 (so that if FN(Ω, d) belongs to one of our four classes, that class is C_{P}) is given by Ω = \{\sqrt{n} : n ∈ ω\} with the metric induced from ℝ. We suspect one can show that it does belong to C_{P} by adapting the method we used for FN(ω, d), putting in the roles of A_{1} and A_{2} the partitions of Ω arising from the integer-valued functions α ↦ [α/2] and α ↦ [(α+1)/2], where [−] denotes the integer-part function.

Two cases that have some similarity to that of FN(ℤ, d) but seem less trivial, and might be worth examining, are those given by the vertex-sets of the Cayley graphs of the free abelian group, respectively the free group, on two generators, with the path-length metric. An example of a different sort is the set ω with the ultrametric under which d(α, β) is the greatest n such that α and β differ in the nth digit of their base-2 expansions. From the fact that this d is an uncrowded ultrametric, it is easily deduced that FN(ω, d) is the union of a countable chain of compact subgroups. All three of these examples fall under case (iii) of Lemma 17, so that if they belong to any of the classes of (42) it is C_{Q}.

10. Further questions about ≼ and ≈.

It seems unlikely that one can in any reasonable sense describe all ≈-equivalence classes of subgroups of the symmetric group on a countably infinite set Ω. On the other hand, if one regards the set of such equivalence classes as a join-semilattice, with join operation induced by the map (G_{1}, G_{2}) ↦ ⟨G_{1} ∪ G_{2} ⟩ on subgroups, one may ask about the properties of this semilattice. The cardinal |G| + ℵ_{0} is an ≈-invariant on subgroups G of Sym(Ω), and induces a homomorphism from this join-semilattice onto the semilattice of cardinals between ℵ_{0} and 2^{ℵ_{0}} under the operation sup . Of our four classes, C_{1} maps to the bottom member of this chain, while the other three map to the top member. Although the operation of intersection on subgroups of S does not respect the relation ≈, it is not clear whether our join-semilattice may nonetheless be a lattice. The second author hopes to give in a forthcoming note further results about this semilattice, and in particular, on Question 18 above.

How much influence does the isomorphism class of a subgroup G ⩽ Sym(Ω) have on its ≈-equivalence class? It does not determine that class; for consider the abstract group G = (ℤ/pℤ)^{ω} for p a prime. If for each i ∈ ω we let Σ_{i} be a regular ℤ/pℤ-set (hence of cardinality p) on which we let G act via the projection on its ith coordinate, and we take for Ω a disjoint union of the Σ_{i}, then we get a representation of G as a compact subgroup of Sym(Ω) belonging to C_{Q}.

On the other hand, we may identify G with the direct product ∏_{i⩾0} (ℤ/pℤ)^{i}, and let Ω be a disjoint union of regular representations of the factors in this product, getting a representation of G in Sym(Ω), also compact in the function topology, but belonging to C_{P}. Finally, observe that if V is a vector space of dimension ℵ_{0} over the field of p elements, and we also regard G = (ℤ/pℤ)^{ω} as a vector space over this field, then G and V^{ω}, both having the cardinality of the continuum, are both continuum-dimensional, hence isomorphic. Performing the same construction as before on this product expression G = ∏ V, we get a representation of G as a group of permutations of a countable set Ω (with G again closed in the function topology, but no longer compact), which Lemma 10 (with α_{i} a representative of the ith orbit, and D_{i} the product of the first i orbits) shows belongs to C_{S}.

Of course, membership of a subgroup in the class C_{1} is determined by its cardinality, hence by its isomorphism class. But to any isomorphism class I of groups of continuum cardinality, we may associate the subset of {C_{S}, C_{P}, C_{Q}} consisting of those ≈-equivalence classes (if any) that contain members of I. Which subsets of {C_{S}, C_{P}, C_{Q}} arise in this way (or in various related ways; for instance, by associating to an isomorphism class I the set of closed subgroups that belonging to I), we do not know.

If we take account of the topological structure of a subgroup G ⩽ S, this can impose restrictions on its ≈-equivalence class:

Lemma 19. If Ω is an infinite set, then a subgroup G ⩽ S = Sym(Ω) is compact in the function topology if and only if it is closed and has finite orbits.

Proof. If G is closed and the members of the partition A given by the orbits of G are all finite, then G is a closed subgroup of S_{(A)} ≅ ∏_{Σ∈A} Sym(Σ). It is not hard

to see that this isomorphism is also a homeomorphism, hence as the above product of finite discrete groups is compact, so is G.

Conversely, if G is compact, it is closed in S by general topology, and for each α ∈ Ω the orbit αG, being an image of the compact group G under a continuous map to the discrete space Ω, is finite. □

So for |Ω| = ℵ_{0}, a compact subgroup of S cannot belong to C_{S}. Note also that if G is a closed subgroup of S not in C_{S}, then by Theorem 11 there exists a finite set Γ such that G_{(Γ)} has finite orbits, so by the above lemma G_{(Γ)} is compact. Thus, though G itself need not be compact, it will be a countable extension of a compact subgroup that is open-closed in it, and thus will be locally compact.

11. Some finiteness results.

This section assumes only the notation recalled in the first two paragraphs of §2, and the contents of §4 (the definition of the function topology, and Lemma 7. At one point we will call on a result of a later section, but our use of that result will subsequently be superseded by a more general argument.) We begin with a result that we will prove directly from the definitions.

Lemma 20. Suppose Ω is a set, and G a subgroup of S = Sym(Ω) which is discrete in the function topology on S, and has the property that each member of G moves only finitely many elements of Ω. Then G is finite.

Proof. The statement that G is discrete means that there is some neighborhood of 1 containing no other element of G. Since a neighborhood basis of 1 in S is given by the subsets S_{(Γ)} for finite Γ ⊆ Ω, there is a finite Γ such that G_{(Γ)} = {1}.

Take such a Γ, and assuming by way of contradiction that G is infinite, let Γ_{0} ⊆ Γ be maximal for the property that G_{(Γ_{0})} is infinite, and let γ be any element of Γ−Γ_{0}. Then G_{(Γ_{0})} inherits the properties that we wish to show lead to a contradiction; so, replacing G with this subgroup, we may assume that for some γ ∈ Ω, G_{({γ})}, unlike G, is finite, say of order n. Then the orbit γ G must be infinite, so let γ g_{0}, …, γ g_{n} be n+1 distinct elements of that orbit. By hypothesis, each of g_{0}, …, g_{n} moves only finitely many elements of Ω, so the infinite set γ G must contain an element γg not moved by any of them. Hence G_{({γg})} contains the n+1 elements g_{0}, …, g_{n}, contradicting the fact that, as a conjugate of G_{({γ})}, it must have order n. □

If we generalize the hypothesis of this lemma by letting Σ be a subset of Ω and G a discrete subgroup of Sym(Ω)_{{Σ}} each member of which moves only finitely many elements of Σ, it does not follow that G induces a finite subgroup of Sym(Σ). For example, partition an infinite set Ω into two sets Σ and Ω − Σ of the same cardinality, and let v be a homomorphism from a free group F of rank |Ω| onto the group of those permutations of Σ that move only finitely many elements. Take a regular representation of F on Ω − Σ, and consider the representation of F on Ω = (Ω − Σ) ∪ Σ given by the “graph” of v, i.e., the set of elements of Sym(Ω)_{{Σ}} that act on Ω − Σ by an element a ∈ F, and on Σ by v(a). This subgroup is discrete because for each α ∈ Ω − Σ we have G_{({α})} = {1}; but it does not induce a finite group of permutations on Σ.

On the other hand, the proof of Lemma 20 easily generalizes to show that if G is a discrete subgroup of S = Sym(Ω), and Ω is the union of a family of G-invariant subsets Σ_{i} such that every element of G moves only finitely many members of each Σ_{i}, then G is finite. (Incidentally, note that throughout this section, when we refer to families of subsets Σ_{i} or Δ_{i} of Ω, there is no disjointness assumption.) In a different direction, if Ω is countable we can formally strengthen Lemma 20 by weakening the hypothesis “discrete” to “closed”; for a subgroup of Sym(Ω) whose members each move only finitely many elements must be countable, and we saw in Theorem 16 that a countable closed subgroup of Sym(Ω) is discrete.

Now suppose that for Ω countable we combine the above two weakenings of the hypothesis of Lemma 20, and consider a closed subgroup G < Sym(Ω) such that for some expression Ω = ⋃_{I} Σ_{i} of Ω as a union of G-invariant subsets, each element of G moves only finitely many members of each Σ_{i}. We would like to conclude that G induces a finite group of permutations of each Σ_{i}; but we cannot argue as above, for now G need not be countable, making Theorem 16 inapplicable.

In an earlier version of this preprint we asked whether this conclusion nonetheless held. Greg Hjorth has shown us a proof, which, with his permission, we give below. We will use

Lemma 21. Let Ω be a countable set, G a closed subgroup of S = Sym(Ω), and (Δ_{i})_{i∈I} a family of subsets of Ω. Then either

(i) there exists a finite set Γ ⊆ Ω such that G_{(Γ)} ⩽ S_{{Δ_{i}}} for all but finitely many i ∈ I, or (ii) there exists an element g ∈ G such that g ∉ S_{{Δ_{i}}} for infinitely many i ∈ I.

Moreover, if all Δ_{i} are finite, then in (i) we can strengthen “all but finitely many” to “all”.

Proof. As in Lemma 7, let Ω = {ε_{0}, ε_{1}, … }. Assuming (i) does not hold, we shall construct g_{0}, g_{1}, … ∈ G which converge, by that lemma, to an element g with the property asserted in (ii).

Suppose inductively that for some j ⩾ 0 we have chosen 1 = g_{−1}, g_{0}, g_{1}, …, g_{j−1} ∈ G, and also distinct indices i_{0}, …, i_{j−1} ∈ I and elements α_{0}, …, α_{j−1} ∈ Ω, such that for k = 0, …, j−1, g_{k} moves α_{k} either out of or into Δ_{i_{k}}, and such that defining, for 0 ⩽ k ⩽ j,

(45) Γ_{k} = {ε_{0}, …, ε_{k−1} } ∪ {ε_{0} g_{k−1}^{−1}, …, ε_{k−1} g_{k−1}^{−1}} ∪ {α_{0}, …, α_{k−1} } ∪ {α_{0} g_{k−1}^{−1}, …, α_{k−1} g_{k−1}^{−1}} (cf. (4)),

we have

(46) g_{k} ∈ G_{(Γ_{k})} g_{k−1} for 0 ⩽ k < j (cf. (5)). Since Γ_{j} is finite, our assumption that (i) fails tells us that there are infinitely many i such that G_{(Γ_{j})} fails to preserve Δ_{i}. It follows that by multiplying g_{j−1} on the left by a member of G_{(Γ_{j})} if necessary, we can insure that for some index other than i_{0}, i_{1}, …, i_{j−1}, which we may call i_{j}, the resulting product g_{j} fails to preserve Δ_{i_{j}}, i.e., moves an element α_{i_{j}} into or out of Δ_{i_{j}}. Also, (46) shows that g_{j} retains the properties of the preceding elements g_{k} of moving α_{k} into or out of Δ_{i_{k}} (0 ⩽ k < j). Applying Lemma 7, we get a limit element g which clearly preserves none of Δ_{i_{0}}, Δ_{i_{1}}, ….

To get the final assertion, observe that if all Δ_{i} are finite and (i) holds, we may take a Γ as in (i) and then adjoin to it the elements of the finitely many sets Δ_{i} not preserved by G_{(Γ)}. □

Applying the above lemma (in particular the final sentence) in the case where the Δ_{i} are the singleton subsets of a set Σ ⊆ Ω, we get

Corollary 22. Let Ω be a countable set, G a closed subgroup of S = Sym(Ω), and Σ a subset of Ω. Then either

(i) there exists a finite set Γ ⊆ Ω such that G_{(Γ)} ⩽ S_{(Σ)}, or (ii) there exists an element g ∈ G which moves infinitely many members of Σ. □

We shall now get our desired result by an argument similar to the proof of Lemma 20, with the above corollary replacing our use of discreteness.

Theorem 23 (G. Hjorth, personal communication). Let Ω be a countable set, G a closed subgroup of S = Sym(Ω), and {Σ_{i} | i ∈ I} a family of G-invariant subsets of Ω such that each element of G moves only finitely many elements of each Σ_{i}, and ⋃_{I} Σ_{i} = Ω.

Then G acts on each Σ_{i} as a finite group of permutations; equivalently, G fixes all but a finite subset of each Σ_{i}.

Proof. The equivalence of the two forms of the conclusion follows from the hypothesis that each member of G moves only finitely many elements of each Σ_{i}. To prove the first form of that conclusion, suppose, on the contrary, that G induces an infinite group of permutations on Σ_{j} for some j ∈ I. Applying the preceding corollary to Σ_{j}, and noting that, by hypothesis, case (ii) of that corollary is excluded, we get a finite Γ ⊆ Ω such that G_{(Γ)} ⩽ S_{(Σ_{j})}.

As in the proof of Lemma 20, let Γ_{0} be a maximal subset of Γ such that G_{(Γ_{0})} induces an infinite group of permutations of Σ_{j}, and γ any element of Γ − Γ_{0}. Replacing G by G_{(Γ_{0})}, which clearly inherits the hypotheses of the theorem, we have that G_{({γ})}, unlike G, induces a finite group of permutations of Σ_{j}, say of order n. Thus for any g ∈ G, the group G_{({γg})} likewise induces a group of permutations of Σ_{j} of order n.

As before, γ must have infinite orbit γ G. Now applying to some Σ_{i} that contains γ the hypothesis that each element of G moves only finitely many elements of Σ_{i}, we see that each element of G lies in G_{({γg})} for all but finitely many distinct γg ∈ γ G. It follows that every finitely generated subgroup of G is likewise contained in G_{({γg})} for all but finitely many distinct γg. Since G induces an infinite group of permutations of Σ_{j}, we can find a finitely generated subgroup of G that induces a group of > n permutations of that set. But by the last sentence of the preceding paragraph, a group of order > n can’t be contained in any of the subgroups G_{({γg})}, let alone in all but finitely many of them. This contradiction completes the proof of the theorem. □

We remark that the analog of Lemma 20 (and hence of Theorem 23) fails for submonoids of Ω^{Ω} . For instance, let Ω = ω, and for i, j ∈ ω define f_{i}(j) = max(i, j). Then G = {f_{i} | i ∈ ω} satisfies the hypotheses of Lemma 20 with “submonoid of ω^{ω} ” in place of “subgroup of Sym(Ω),” but does not satisfy the conclusion.

12. Other preorderings, and further directions for investigation.

In the arguments of §§5-7, when we obtained a relation G ≼ H, we often did this by showing that G lay in the subgroup of S generated by finitely many conjugates of H. This suggests

Definition 24. If S is a group, κ an infinite cardinal, and G_{1}, G_{2} subgroups of S, let us write G_{1} ≼_{κ,S}^{cj} G_{2} if there exists a subset U ⊆ S of cardinality < κ such that G_{1} ⩽ ⟨ ⋃_{f∈U} f^{−1}G_{2}f ⟩.

As with ≼_{κ,S}, we may omit the subscripts κ and S from ≼_{κ,S}^{cj} when their values are clear from context, and we will write ≈_{κ,S}^{cj} or ≈^{cj} for the induced equivalence relation. For the remainder of this discussion, κ will be ℵ_{0} and S will be Sym(Ω) for a countably infinite set Ω, and these subscripts will not be shown.

In general, ≼^{cj} and ≈^{cj} are finer relations than ≼ and ≈ . Since not all the arguments in §§5-7 were based on combining conjugates of the given subgroup G (in particular, some were based on conjugating a carefully constructed element s ∈ S by elements of G), it is not obvious whether those results can be strengthened to say that the classes of subgroups that we proved ≈-equivalent are in fact ≈^{cj}-equivalent. Let us show that the answer is “almost”.

Recall (cf. [2, p.51, Theorem 6.3]) that since Ω is countably infinite, the only proper nontrivial normal subgroups of S are the group of permutations that move only finitely many points, which we shall denote S^{finite}, and the subgroup of even permutations in S^{finite}, which we shall denote S^{even}.

Lemma 25. Let Ω be a countably infinite set, and G a subgroup of S = Sym(Ω) not contained in S^{finite}. Then the unary relations ≼^{cj} G and ≼ G on the set of subgroups of S coincide. Hence if G is uncountable, the unary relations ≈^{cj} G and ≈ G on that set also coincide.

Proof. In the first assertion, the nontrivial direction is to show that H ≼ G implies H ≼^{cj} G. The former condition says that H ⩽ ⟨G ∪ U ⟩ for some finite U ⊆ S. Now since G is not contained in the largest proper normal subgroup of S, the normal closure of G is S. Hence each element of U ⊆ S is a product of finitely many conjugates of elements of G. The desired conclusion follows immediately.

To see the second assertion, note that if G is uncountable, so is any H ≈ G, hence we also have H ⊈ S^{finite}, and the preceding result can be applied to H as well as to G, giving H ≈^{cj} G. □

We can now get

Proposition 26. Let Ω be a countably infinite set, and S = Sym(Ω). Then all ≈-equivalence classes of subgroups of S other than C_{1} are also ≈^{cj}-equivalence classes. The class C_{1} decomposes into the following six ≈^{cj}-equivalence classes:

(i) The set of countable (finite or infinite) subgroups not contained in S^{finite}, (ii) The set of infinite (necessarily countable) subgroups of S^{finite} not contained

in S^{even}.

(iii) The set of infinite (again countable) subgroups of S^{even}.

(iv) The set of finite subgroups contained in S^{finite} but not in S^{even}.

(v) The set of finite nontrivial subgroups of S^{even}.

(vi) The set containing only the trivial subgroup.

Proof. The first assertion follows immediately from the preceding lemma. In the second, it is not hard to see that the sets (i)-(vi) partition C_{1}, and that a subgroup in one of these sets cannot be ≈^{cj}-equivalent to one not in that set, so it remains only to show that any two groups in the same set in our list are ≈^{cj}-equivalent.

That this is true of (i) follows from the first assertion of the preceding lemma, and the fact that all members of C_{1} are ≈-equivalent.

Skipping to (iii), if G is in that class, then Lemma 20 shows that G is nondiscrete. From a sequence of nonidentity elements of G approaching 1, we can extract an infinite subsequence consisting of elements whose supports, supp(g) = {α ∈ Ω | gα ≠ α}, are pairwise disjoint. If we take s ∈ S whose support has singleton intersection with each of those supports, we find that each of the corresponding commutators s^{−1}g^{−1}sg is a 3-cycle [2, p.51, Exercise 6(i)]. These 3-cycles lie in ⟨G∪s^{−1}Gs⟩, and no point belongs to the support of more than two of them, so we can find an infinite set of 3-cycles in that group with disjoint supports. By dropping some of these, we may assume that the complement in Ω of the union of their supports is infinite. Hence we may assume without loss of generality that Ω = ℤ and that we have gotten the 3-cycles (4n, 4n+1, 4n+2) for all n ∈ ℤ. Three more conjugations now give us all 3-cycles of the form (k, k+1, k+2) (k ∈ ℤ), and these generate S^{even}. Hence G ≈^{cj} S^{even}. So all subgroups in (iii) are ≈^{cj}-equivalent to that subgroup, hence to each other, as required.

For G in class (ii), the above result shows that finitely many conjugates of G ∩ S^{even} generate S^{even}, and since G also contains an odd permutation, the corresponding conjugates of G generate S^{finite}. So all such groups are ≈^{cj}-equivalent to S^{finite}, and so again, to each other. That the members of each of (iv), (v), and (vi) are mutually ≈^{cj}-equivalent is easily deduced from standard results about finite symmetric groups [2, §2.4]. □

We note that the ordering on these sets induced by the relation ≼^{cj} on subgroups is

(i) ≻^{cj} (ii) ≻^{cj} {(iii), (iv)} ≻^{cj} (v) ≻^{cj} (vi),

with (iii) and (iv) incomparable.

There is another family of preorders also implicit in the methods we have used. Given subgroups G, H ⩽ Sym(Ω) and a cardinal κ, let us write

(47) G ≼_{κ}^{fix} H if for some Γ ⊆ Ω with |Γ| < κ we have G_{(Γ)} ⩽ H,

and let us write G ≈_{κ}^{fix} H for the conjunction of G ≼_{κ}^{fix} H and H ≼_{κ}^{fix} G.

Lemma 2 yields an implication between these relations and those studied in this note:

(48) G ≼_{ℵ_{0}}^{fix} H ⟹ G ≼_{|Ω|^{+}} H.

The relations ≈_{κ}^{fix} and ≼_{κ}^{fix} tend to be quite fine-grained. For instance, given partitions A_{1} and A_{2} of Ω, it is not hard to see that S_{(A_{1})} ≈_{κ}^{fix} S_{(A_{2})} if and only if A_{1} and A_{2} “disagree at < κ elements”, meaning that one can be obtained from the other by “redistributing” < κ elements of Ω.

In a different direction, one might define on abstract groups (rather than subgroups of a fixed group) a preordering analogous to ≼_{κ}, by letting G_{1} ≼_{κ}^{emb} G_{2} mean that G_{1} admits an embedding in a group H which is generated over G_{2} by < κ elements.

In our study of symmetric groups in this note, we have considered only countable Ω, except when no additional work or distraction was entailed by allowing greater generality. It would be of interest to know what can be said about ≈_{κ}-equivalence classes of closed subgroups of Sym(Ω) for general Ω and κ; in particular, whether there are simple criteria for a closed subgroup G ⩽ Sym(Ω) to be ≈_{ℵ_{0}}-equivalent (equivalently, ≈_{|Ω|^{+}}-equivalent) to Sym(Ω).

A related topic which has been studied extensively (e.g., [8], [12]) is the cofinality of groups Sym(Ω), defined as the least cardinal κ such that Sym(Ω) can be written as the union of a chain of < κ proper subgroups. If S = Sym(Ω) is of cofinality ⩾ κ, then our unary relation ≈_{ℵ_{0},S} S is equivalent to ≈_{κ,S} S (cf. proof of Lemma 3(ii) above); though the converse fails under some set-theoretic assumptions.

Still another direction for study would be to consider questions of the sort studied here, but for structures other than groups. Mesyan [6] gets some results of this sort for the ring of endomorphisms of the Ω-fold direct sum of copies of a module.

References

[1] George M. Bergman, Generating infinite symmetric groups, to appear, J. London Math. Soc.. Preprint version, 9 pp.: http://math.berkeley.edu/∼ gbergman/papers/Sym Omega: 1.{tex,dvi}, arXiv:math.GR/0401304 .

[2] Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller and Peter M. Neumann, Notes on infinite permutation groups, Texts and Readings in Mathematics, 12, Hindustan Book Agency, New Delhi, and Lecture Notes in Mathematics, 1698, Springer-Verlag, 1997. MR 99e:20003.

[3] Stephen Bigelow, Supplements of bounded permutation groups, J. Symbolic Logic 63 (1998) 89–102. MR 99b:20007.

[4] Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995) 230–242. MR 96a:20005.

[5] H. D. Macpherson and Peter M. Neumann, Subgroups of infinite symmetric groups, J. London Math. Soc. (2) 42 (1990) 64–84. MR 92d:20006. (Note: It is shown in [3] that Theorem 1.2 of this paper requires additional set-theoretic hypotheses for some κ.)

[6] Zachary Mesyan, Generating subrings of endomorphism rings using small numbers of elements (title tentative), preprint, April 2005, 13 pp.. (Author’s e-mail address: zak@math.berkeley.edu .)

[7] Oystein Ore, Some remarks on commutators, Proc. Amer. Math. Soc. 2 (1951) 307–314. MR 12, 671e.

[8] Saharon Shelah and Simon Thomas, The cofinality spectrum of the infinite symmetric group, J. Symbolic Logic 62 (1997) 902–916. MR 98k:03106.

[9] N. M. Suchkov, An example of a mixed group factorable by two periodic subgroups, (Russian) Algebra i Logika 23 (1984), 573–577, 600. (English translation: Algebra and Logic 23 (1984), 385–387.) MR 87d:20058.

[10] N. M. Suchkov, Subgroups of a product of locally finite groups, (Russian) Algebra i Logika 24 (1985), 408–413, 493. (English translation: Algebra and Logic 24 (1985) 265–268.) MR 87e:20059.

[11] N. M. Suchkov, On a group of restricted permutations, (Russian) pp.84–89 in Constructions in algebra and logic, Tver. Gos. Univ., Tver, 1990. MR 94c:20010.

[12] Simon Thomas, Cofinalities of infinite permutation groups, pp.101–120 in Advances in algebra and model theory (Essen, 1994; Dresden, 1995 ) Algebra Logic Appl., v.9. MR 2000a:20005.

(G. Bergman) University of California, Berkeley, CA 94720-3840, USA

E-mail address: gbergman@math.berkeley.edu

(S. Shelah) University of Jerusalem, Einstein Institute of Mathematics, Jerusalem 91904, Israel, and Hill Center-Busch Campus, Rutgers, The State University of New Jersey, Piscataway, NJ 08854-8019, USA

E-mail address: shelah@math.huji.ac.il