Lobachevskii Journal of Mathematics Vol. 12, 2003, 73 – 81 \begin{matrix}c \\ ◯ \end{matrix}Yi Zhang

Yi Zhang

CONSTRUCTING A MAXIMAL COFINITARY GROUP

(submitted by M. M. Arslanov)

Abstract. Assuming continuum hypothesis (CH), we construct a maximal cofinitary group step by step. We also outline a way of constructing maximal cofinitary group by assuming the negation of CH and Martin’s Axiom (MA).

1. Introduction.

A permutation g ∈ Sym(ℕ) is cofinitary iff g has only finitely many fixed points. A group G ≤ Sym(ℕ) is cofinitary iff, for all g ∈ G∖{id}, g is a cofinitary permutation. Different properties of maximal cofinitary groups has been studied (see, e.g., [A], [T1], [T2], [Z1], [Z2] etc.). In [C], P. Cameron pointed out that Zorn’s Lemma (or, Axiom of Choice) implies the existence of maximal cofinitary group. However, questions can still be asked from various directions. For example,

(1) instead of saying that Zorn’s Lemma implies existence of a maximal cofinitary group, is there any concrete example of maximal cofinitary group?

(2) can we construct a maximal cofinitary group without using Axiom of Choice (or Zorn’s Lemma), or say, does there exist a Borel maximal cofinitary group? etc.

In this notes, we give a concrete example of maximal cofinitary group under CH. In fact, we will construct a maximal cofinitary groups under CH step by step. We will also outline a way of constructing maximal cofinitary groups by assuming ¬CH and MA. The set theory notation which we use in this paper are standard, people can find them in a book like [K].

The research was partially supported by Academy of Finland, grant number 40734.

2. Constructing a maximal cofinitaty group under CH.

Let G ≤ Sym(ℕ) be a countable cofinitary group. Let f ∈ Sym(ℕ)∖G such that ⟨G, f⟩ is cofinitary. Let W_{G} = {w_{i}(x) | i ∈ ℕ} enumerate all words

g_{1}x^{n_{1}}g_{2}...g_{t}x^{n_{t}}g_{t+1}

which actually involve x such that g_{l} ∈ G∖{id} except that possibly g_{1} = id or g_{t+1} = id and n_{i} ∈ ℤ∖{0}. By induction, we construct a permutation g ∈ Sym(ℕ)∖G such that ⟨G, g⟩ is cofinitary.

At the i–th stage, we do the following. Assume that g_{i−1}^{∗} is a 1–1 finite partial function we defined up to i − 1 stage.

If g_{i−1}^{∗}(i) is defined, then let g_{i}^{∗}(i) = g_{i−1}^{∗}(i).

Assume g_{i−1}^{∗}(i) is undefined. Then we do the following.

We want to define g_{i}^{∗}(i) which satisfies the following condition (α). (α). For every conjugate subword w′_{j} of w_{j}, j < i, without cancellation, the following holds. Suppose that w′_{j}(g_{i−1}^{∗})(l) is undefined, and w′_{j}(g_{i}^{∗})(l) = l. Then w′_{j} = uzu^{−1} without cancellation and ⟨l, n⟩ ∈ u^{−1}(g_{i−1}^{∗}) for some n with z(g_{i−1}^{∗})(n) = n.

Lemma 2.1 Assume that w(x) ∈ W_{G} is a fixed word and g_{i−1}^{∗}(i) is not defined. Then for all but finitely many m ∈ ℕ we can define g_{i}^{∗}(i) = m and the condition (α) holds. Proof We argue by induction on the length of the word w. Let m ∈ ℕ ∖ rang(g_{i−1}^{∗}) and consider

ḡ_{i} = g_{i−1}^{∗} ∪ {⟨i, m⟩}.

Suppose that there exists a conjugate subword

w_{0} = g_{1}x^{n_{1}}g_{2}...g_{t}x^{n_{t}}g_{t+1}

of w and an integer l_{m} such that

w_{0}(g_{i}^{∗})(l_{m}) is undefined, and w_{0}(ḡ_{i})(l_{m}) = l_{m},

and condition (α) fails.

Consider the computation of the second formula in more detail. There exists some 1 ≤ j ≤ t such that

r = g_{j+1}(g_{i−1}^{∗})^{n_{j}+1}g_{j+2}...(g_{i−1}^{∗})^{n_{t}}g_{t+1}(l_{m})

is defined, and either

• n_{j} > 0 and there exists 0 ≤ k ≤ n_{j} − 1 such that

(g_{i−1}^{∗})^{k}(r) ∉ dom(g_{i−1}^{∗}); or

• n_{j} < 0 and there exists n_{j} + 1 ≤ k ≤ 0 such that

(g_{i−1}^{∗})^{k}(r) ∉ rang(g_{i−1}^{∗}).

At the next step of the computation, we must use the new data ⟨i, m⟩ of ḡ_{i}.

Case (1). We must have that (g_{i−1}^{∗})^{k}(r) = i and so (ḡ)_{i}^{k+1}(r) = m.

We now consider various subcases. Case 1.1. Suppose that k + 1 < n_{j}. Then we have to choose that

m ∈ dom(g_{i−1}^{∗}) ∪ {i}.

Hence there are only finitely many choice for m ∈ ℕ. Case 1.2. Suppose that k + 1 = n_{j}. Now we have to consider the rest of the computation.

g_{1}(ḡ_{i})^{n_{1}}...g_{j}(m) = l_{m}.

First suppose that j > 1. If n_{j−1} > 0, then we can continue the computation iff

g_{j}(m) ∈ dom(ḡ_{i}) = dom(g_{i−1}^{∗}) ∪ {n},

and hence there are only finitely many values for m. If n_{j−1} < 0, then we must have that

g_{j}(m) ∈ rang(ḡ_{i}) = rang(g_{i−1}^{∗}) ∪ {m}.

Since g_{j} ∈ G which is a cofinitary group, there are only finitely many values of m.

Now suppose that j = 1. Then it has to be that g_{1}(m) = l_{m}. There is an apparent difficulty since we do not know how many possibilities there are for l_{m}. But since we know that

g_{1}(ḡ_{i})^{n_{1}}g_{2}...(ḡ_{i})^{n_{t}}g_{t+1}(l_{m}) = l_{m}, and

g_{1}(g_{i−1}^{∗})^{n_{1}}g_{2}...(g_{i−1}^{∗})^{n_{t}}g_{t+1}(l_{m}) is undefined,

then this implies that either (1_{a}). g_{t+1}(l_{m}) ∈ rang(g_{i−1}^{∗}) ∪ dom(g_{i−1}^{∗}), or (1_{b}). g_{t+1}(l_{m}) = i, and w_{0}(x) = g_{1}xg_{2}.

For (1_{a}), it is clear that there are only finitely many possibilites for l_{m}, and hence only finitely many possibilities for m = g_{1}^{−1}(l_{m}).

For (1_{b}), since g_{1}(m) = l_{m} and g_{2}(l_{m}) = i, then

m = g_{1}^{−1}(g_{2}^{−1}(i)).

Again there are only finitely many values for m. Case (2). We must have that g_{i−1}^{∗}(r) = m and so

(ḡ_{i})^{k−1}(r) = i.

Case 2.1. Suppose that j < t. Then

(g_{i−1}^{∗})^{k}g_{j+1}(g_{i−1}^{∗})^{n_{i}+1}...g_{t+1}(l_{m}) = m.

Since rang((g_{i−1}^{∗})^{k}g_{j+1}...g_{t+1}) is finite, there are only finitely many values for m. Case 2.2. Suppose that j = t. If k ≠ 0, then

(g_{i_{1}}^{∗})^{k}g_{t+1}(l_{m}) = m.

Since rang((g_{i−1}^{∗})^{k}g_{t+1}) is finite, there are only finitely many values for m.

Now assume that k = 0. Then m = g_{t+1}(l_{m}). Once again, there is an apparent difficulty, since we do not know how many possibilities there are for l_{m}. We have the following two subcases to consider:

(2_{a}). n_{1} < 0 in w_{0} = g_{1}x^{n_{1}}...g_{t}x^{n_{t}}g_{t+1}. (2_{b}). n_{1} > 0 in w_{0} = g_{1}x^{n_{1}}...g_{t}x^{n_{t}}g_{t+1}.

For (2_{a}), since n_{1} < 0, then

l_{m} ∈ g_{1}(dom(ḡ_{i})) = g_{1}(dom(g_{i−1}^{∗}) ∪ {i}),

i.e., g_{t+1}^{−1}(m) ∈ g_{1}(dom(g_{i−1}^{∗}) ∪ {i}). Hence,

m ∈ g_{t+1}g_{1}(dom(g_{i−1}^{∗}) ∪ {i}).

Thus there are finitely many values for m.

Now we consider the subcase (2_{b}). Since

w_{0} = g_{1}x^{n_{1}}...g_{t}x^{n_{t}}g_{t+1} = g_{1}x(x^{n_{1}−1}g_{2}...g_{t}x^{n_{t}+1})x^{−1}g_{t+1},

we may write that w_{0} = g_{1}xzx^{−1}g_{t+1}. If z(g_{i−1}^{∗})(i) = i and g_{1} = g_{t+1}^{−1}, then we are done. Assume otherwise. Then either z(g_{i−1}^{∗})(i) ≠ i or g_{1} ≠ g_{t+1}^{−1}.

If z(g_{i−1}^{∗})(i) ≠ i, then there are two subcases: (I). z(g_{i−1}^{∗})(i) = k, for some k ∈ ℕ, or (II). z(g_{i−1}^{∗})(i) is undefined.

For (I) we may assume that z(g_{i−1}^{∗})(i) ∈ dom(g_{i−1}^{∗}) because otherwise the computation stops. Therefore, we know that

g_{i−1}^{∗}(z(g_{i−1}^{∗})(i)) ≠ m, and g_{i−1}^{∗}(z(g_{i−1}^{∗})(i)) ∈ rang(g_{i−1}^{∗}).

This implies that

l_{m} ∈ ℕ∖g_{1}(rang(g_{i−1}^{∗}));

i.e.,

g^{t+1}(m) ∈ ℕ∖g_{1}(rang(g_{i−1}^{∗})).

Hence there are finitely many possibilities for m.

For (II), there are two different possibilities: (II_{a}). z(ḡ_{i})(i) = k for some i ≠ k ∈ ℕ, (II_{b}). z(ḡ_{i})(i) = i.

For (II_{a}), there are finitely many possibilities for m, by a similar argument to the subcase (I).

Now suppose that (II_{b}) holds. By induction hypothesis, if m is a sufficiently large integer, then there exists an expression z = uz_{0}u^{−1} and an integer c ∈ ℕ such that (i). z_{0}(g_{i−1}^{∗})(c) = c, and (ii). u^{−1}(ḡ_{i})(i) = c.

If there are infinitely many such m, we must have that g_{1} = g_{t+1}, since G is a cofinitary group. But now (α) holds for all those m such that (i) and (ii) are true.

Finally suppose that z(g_{i−1}^{∗})(i) ≠ i and g_{1} ≠ g_{t+1}^{−1}. Since G is a cofinitary group, there are only finitely many possibilities for m.

We have completed the proof of the lemma. □ By this lemma, we know that we can define g_{i}^{∗}(i) which satisfies condition

(α).

A similar argument shows that we can also define k = (g_{i}^{∗})^{−1}(i) which satisfies condition (α).

Let

ġ_{i} = g_{i−1}^{∗} ∪ {⟨i, g_{i}^{∗}(i)⟩, ⟨k, (g_{i}^{∗})^{−1}(i)⟩}.

Next we want to find a pair ⟨n, f(n)⟩ ∈ f with n > i such that

g_{i}^{∗} = ġ_{i} ∪ {⟨n, f(n)⟩}

satisfies condition (α). The following lemma guarantees that we can find such pair.

Lemma 2.2 Let G be a cofinitary group and let f ∈ Sym(ℕ)∖G be such that ⟨G, f⟩ is also a cofinitary group. Assume that w(x) ∈ W_{G}. Then for all but finitely many ⟨n, f(n)⟩, ġ_{i} ∪ {⟨n, f(n)⟩} satisfies condition (α). Proof Since ⟨G, f⟩ is a cofinitary group and f ∈ Sym(ℕ)∖G, we know that f is a cofinitary permutation, i.e., f has finitely many fixed point.

Let

w_{0} = g_{1}x^{n_{1}}g_{2}x^{n_{2}}...g_{t}x^{n_{t}}g_{t+1}

be a conjugate subword of w, where n_{i} ∈ ℤ∖ {0} and g_{i} ≠ id except possibly g_{i} = id or g_{t+1} = id. Also let

g′ = ġ_{i} ∪ {⟨n, f(n)⟩},
w_{0}(g′)(l_{n}) = l_{n}, and
w_{0}(ġ_{i})(l_{n}) is undefined.

Consider the point where ⟨n, f(n)⟩ is first used. So we have that

w_{0} = ax^{e}b, and b(ġ_{i})(l_{n}) ∈ {n, f(n)},

where a, b ∈ W_{G} ∪ G.

If b involves x, then either

n ∈ rang(b(ġ_{i})), or
f(n) ∈ rang(b(ġ_{i})), i.e., n ∈ f^{−1}(rang(b(ġ_{i})),

and so there are only finitely many possibilities for n. Thus without loss of generality, we may assume that b = g_{t+1} in the following. Case 1. Suppose that n_{t} > 0.

First suppose that n_{t} > 1. Then

f(g_{t+1}(l_{n})) = f(n).

Hence if f(n) ∉ dom(ġ_{i}) ∪ {n}, then the computation will stop. Since dom(ġ_{i}) is finite and f is a cofinitary permutation, there are only finitely possibilities for n.

Now assume that n_{t} = 1. To make the computation continue, it has to be that

g_{t}(f(n)) ∈ dom(ġ_{i}) ∪ rang(ġ_{i}) ∪ {n, f(n)}.

Since g_{t} ≠ id and f ∩ g_{t} is finite, there are only finitely many n’s such that

g_{t}(f(n)) = f(n), or g_{t}(f(n)) = n.

Hence there are only finitely many n’s to make the computation continue.

So, without loss of generality, we may consider that

w_{0} = g_{1}xg_{2}.

Assume that there are infinitely many l_{n} such that

g_{1}{⟨n, f(n)⟩}g_{2}(l_{n}) = l_{n}.

This implies that

g_{1}fg_{2} = id.

Hence f = g_{1}^{−1}g_{2}^{−1} ∈ G which is a contradiction. Case 2. Suppose that n_{t} < 0.

First suppose that n_{t} < −1. We know that if

n ∉ rang(ġ_{i}) ∪ {f(n)}.

then the computation stops. There are only finitely many choice for n.

So without loss of generality, we may suppose that n_{t} = −1. Then only

g_{t}(n) ∈ dom(ġ_{i}) ∪ rang(ġ_{i}) ∪ {n, f(n)}

can make the computation continue. Since there are only finitely many n ∈ ℕ such that

g_{t}(n) = n, or, g_{t}(n) = f(n).

there are only finitely many possibilities for n.

We consider the last case

w_{0} = g_{1}x^{−1}g_{2}.

If there are infinitely many l_{n} such that

w_{0}(l_{n}) = g_{1}{⟨n, f(n)⟩}g_{2}(l_{n}) = l_{n},

then g_{1}f^{−1}g_{2} = id. Hence f^{−1} = g_{1}^{−1}g_{2}^{−1}, i.e., f = g_{2}g_{1} ∈ G. This is a contradiction as well.

We have proved the lemma. □ Let

g_{i}^{∗} = ġ_{i} ∪ {⟨n, f(n)⟩}.

We finished the i–th stage construction.

Now let g = ⋃_{i∈ℕ} g_{i}^{∗}.

We have proved the following.

Theorem 2.3 Let G be a countable cofinitary group and let f ∈ Sym(ℕ)∖G be such that ⟨G, f⟩ is also a cofinitary group. Then we can recursively construct a permutation g ∈ Sym(ℕ)∖G such that ⟨G, g⟩ is cofinitary and g ∩f is infinite.

Proof We prove that ⟨G, g⟩ is cofinitary by induction on the length of the word w_{i} ∈ W_{G}(i ∈ ω) that | fix(w(g)) |< ω.

First suppose that we cannot express w_{i} = uzu^{−1} without cancellation. Then w(g)(l) = l implies that w_{i}(g_{i}^{∗})(l) = l. It follows that

|fix(w(g))| < ω.

Next suppose that we can express w = uzu^{−1} without cancellation. By induction hypothesis |fix(z(g))| < ω, since

|fix(w(g))| = |fix(z(g))|

by condition (α). We know that |fix(w(g))| < ω.

It can be easily seen from Lemma 2.2 that g ∩ f is infinite.

□

By CH, let {f_{α} | ω ≥ α < ω_{1}} enumerate all permutations in Sym(ℕ). We construct a maximal cofinitary group G as follows.

Let g = (01)(234)(5678).... Let G_{n} = ⟨g⟩ for any n ∈ ℕ.

At the α–th stage, ω ≤ α < ω_{1}, we consider the countable cofinitary group G′_{α} = ⋃_{β<α} G_{β} and f_{α}.

Assume that f_{α} ∉ G′_{α} and ⟨G′_{α}, f_{α}⟩ is cofinitary. Then, by Theorem 2.3, we can construct a g_{α} such that G_{α} = ⟨G′_{α}, g_{α}⟩ is cofinitary, and g_{α} ∩f_{α} is infinite.

Let G = ∪_{α<ω_{1}}G_{α}. Then G is a maximal cofinitary group.

Thus we finished our construction of a maximal cofinitary group under CH.

Remark. By results in section 7 of [M], and Lemma 2.1, Lemma 2.2, you may think that we can prove that there is a Π_{1}^{1} maximal cofinitary group under V=L. Unfortunately, it is not the case. Our construction only gives a set of generators of a maximal cofinitary group. Thus the following problem is open and probably hard to solve: Open Problem 2.4 Does there exist a Borel (or, analytic, co-analytic, closed) maximal cofinitary group? Or, does there exist a Borel (or, analytic, co-analytic, closed) set of permutations which generate a maximal cofinitary group?

For more explaination, see [GZ].

3. When CH fails.

In this section, we sketch a construction of a maximal cofinitary group by MA and ¬ CH. The idea involved here is similar to the one in section 3. Thus, we will just sketch the construction and point out the p. o. set and some key results we are going to use here. Definition 3.1 Let G ≤ Sym(ℕ) be a cofinitary group. Then the partially ordered set 𝔾_{G} consists of all conditions of the form ⟨s, F ⟩ such that

• s is a 1-1 finite partial function from ℕ to ℕ,

• F is a finite subset of W_{G}; where W_{G} consists of the words g_{1}x^{n_{1}}...g_{t}x^{n_{t}}g_{t+1} which actually involves x such that g_{l} ∈ G∖{id} except that possibly g_{1} = id or g_{t+1} = id, and n_{i} ∈ ℤ∖{0}. If w(x) ∈ W_{G} and s is a 1–1 finite partial function from ℕ to ℕ, then W (s) denotes the partial function obtained by substituting s for x in w(x). We define ⟨s_{2}, F_{2}⟩ ≤ ⟨s_{1}, F_{1}⟩ iff

(a). s_{1} ⊆ s_{2} and F_{1} ⊆ F_{2};

(b). For every conjugate subword w_{0} of w ∈ F, the following holds. Suppose that w_{0}(s_{1})(l) is undefined and w_{0}(s_{2})(l) = l. Then w_{0} = uzu^{−1} without cancellation and ⟨l, n⟩ ∈ u^{−1}(s_{2}) for some n with z(s_{1})(n) = n.

It is esily seen that the poset 𝔾_{G} is c.c.c. More explainations about this poset can be found in [Z1] and [Z2]. For example, the following theorem can proved by some rather complicated density arguments which appeared in [Z1].

Lemma 2.2 (MA (κ)). Let G ≤ Sym(ℕ) be any cofinitary permuation group, where |G| ≤ κ and ω ≤ κ < 2^{ω}. Then there exists a g ∈ Sym(ℕ)∖G such that ⟨G, g⟩ = G ∗ ⟨g⟩ is a cofinitary permutation group. Here G ∗ ⟨g⟩ denotes the free product of G and ⟨g⟩. Moreover, if f ∈ Sym(ℕ)∖G and ⟨G, f⟩ is a cofinitary group, then |g ∩ f| = ω, i.e., {n ∈ ℕ | g(n) = f(n)} is infinite. Proof See the proofs of Theorem 2.6 and Lemmas 3.2, and 3.3 in [Z1]. □

Now, let {f_{α} | ω ≥ α < 2^{ω}} enumerate all permutations in Sym(ℕ). We construct a maximal cofinitary group G as follows.

Let g = (01)(234)(5678).... Let G_{n} = ⟨g⟩ for any n ∈ ℕ.

At the α–th stage, ω ≤ α < 2^{ω}, we consider the cofinitary group G′_{α} = ⋃_{β<α} G_{β} and f_{α}.

Assume that f_{α} ∉ G′_{α} and ⟨G′_{α}, f_{α}⟩ is cofinitary. Then, by Lemma 2.2, we can construct a g_{α} by MA such that G_{α} = ⟨G′_{α}, g_{α}⟩ is cofinitary, and g_{α} ∩ f_{α} is infinite.

Let G = ∪_{α<2^{ω}}G_{α}. We know that G is a maximal cofinitary group of size continuum. We thus finished our construction.

Acknowledgments. Part of the research had been done when I was visiting Kazan State University, Russia. I would like to thank Professor Marat Arslanov and his wife Mrs Farida Arslanova and the librarian Miss Galfiya for all kinds of helps and hospitalities which they provided during the period of my visit.

References

[A] S. A. Adeleke Embeddings of infinite permutation groups in sharp, highly transitive, and homogeneous groups, Proceedings of Edinburgh Mathematical Society, 31 (1981), 169–178.

[C] P. Cameron Cofinitary permutation groups, Bulletin of the London Mathematical Society, 28 (1996), 113–140.

[GZ] S. Gao and Y. Zhang Definable sets of generators in maximal cofinitary groups (preprint).

[K] K. Kunen Set Theory. An introduction of independence proofs, 1980, North-Holland.

[M] A. Miller Infinite combinatorics and definability, Annals of Pure and Applied Logic, 41 (1989), 179–203.

[T1] J. K. Truss Embeddings of infinite permutation groups, Proceedings of Groups–St Andrews, 1985, London Math. Soc. Lecture Note Ser. 121 (ed. E. F. Robertson and C. M. Cambell) 1986, 335-351, Cambridge University Press.

CONSTRUCTING A MAXIMAL COFINITARY GROUP 81

[T2] J. K. Truss Joint embeddings of infinite permutation groups, Advances in Algebra and Model Theory (ed. M. Droste and R.Göbel), Algebra, Logic and Applications, vol 9, 1997, 121–134, Gordon and Breach Science Publ.

[Z1] Y. Zhang Maximal cofinitary groups, Archive for Mathematical Logic, 39, No.1 (2000), 41–52.

[Z2] Y. Zhang Permutation groups and covering properties, Journal of London Mathematical Society 63 No. 2(2001), 1–15.

Department of Mathematics, Sun Yet-San University, Guangzhou, P. R. China Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing, P. R. China Current address: The University of Michigan, Department of Mathematics, East Hall, 525 East University Avenue, Ann Arbor, MI 48109-1109, USA E-mail address: yizhang@umich.edu

Received February 6, 2003