CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS

JOEL DAVID HAMKINS AND SIMON THOMAS

Abstract. If G is a centreless group, then τ(G) denotes the height of the automorphism tower of G. We prove that it is consistent that for every cardinal λ and every ordinal α < λ, there exists a centreless group G such that

(a) τ(G) = α; and

(b) if β is any ordinal such that 1 ≤ β < λ, then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that τ(G) = β in the corresponding generic extension V^{ℙ}.

1. Introduction

If G is a centreless group, then there is a natural embedding e_{G} of G into its automorphism group Aut(G), obtained by sending each g ∈ G to the corresponding inner automorphism i_{g} ∈ Aut(G). In this paper, we shall always work with the left action of Aut(G) on G. Thus i_{g}(x) = gxg^{−1} for all x ∈ G. If π ∈ Aut(G) and g ∈ G, then πi_{g}π^{−1} = i_{π(g)}. Hence the group of inner automorphisms Inn(G) is a normal subgroup of Aut(G). Also C_{Aut(G)}(Inn(G)) = 1. In particular, Aut(G) is a centreless group. This enables us to define the automorphism tower of G inductively as follows.

Definition 1.1. (a) G_{0} = G.

(b) Suppose that G_{α} has been defined. Then G_{α+1} is chosen to be a group such that

(i) G_{α} ⩽ G_{α+1}; and (ii) there exists an isomorphism φ such that the following diagram commutes.

G_{α+1} ⟶^{φ} Aut(G_{α})
inc↑  ^{inc}↑
G_{α} ⟶^{e_{Gα}} Inn(G_{α})

The research of the first author was partially supported by a grant from the City University of New York PSC-CUNY Research Foundation.

The research of the second author was partially supported by NSF Grants.

2 JOEL DAVID HAMKINS AND SIMON THOMAS

(Here inc denotes the inclusion map. This corresponds to identifying G_{α} with Inn(G_{α}). There is actually a unique such isomorphism φ. This allows us to speak of the automorphism tower of G.)

(c) If λ is a limit ordinal, then G_{λ} = ⋃_{α<λ}G_{α}.

The automorphism tower is said to terminate if there exists an ordinal α such that G_{β} = G_{α} for all β > α. This occurs if and only if there exists an ordinal α such that G_{α} is a complete group. (A centreless group G is said to be complete if Aut(G) = Inn(G).) A classical result of Wielandt [11] says that if G is finite, then the automorphism tower terminates after finitely many steps. In [9], it was shown that the automorphism tower of an arbitrary centreless group eventually terminates; and that for each ordinal α, there exists a group whose automorphism tower terminates in exactly α steps.

Definition 1.2. If G is a centreless group, then the height τ(G) of the automorphism tower of G is the least ordinal α such that G_{β} = G_{α} for all β > α.

Let V denote the ground model, and let G ∈ V be a centreless group. If M is a generic extension of V, then τ^{M}(G) denotes the value of τ(G), when τ(G) is computed within M. In [10], it was shown that there exists a centreless group G ∈ V and a c.c.c. notion of forcing ℙ such that τ(G) = 0 and τ^{V^{ℙ}}(G) ≥ 1. This is not a very surprising result. It was to be expected that there should be a complete group G which possessed an outer automorphism in some generic extension V^{ℙ}. More surprisingly, it was also shown in [10] that there exists a centreless group G such that

(a) τ(G) = 2; and

(b) if ℙ is any notion of forcing which adjoins a new real, then τ^{V^{ℙ}}(G) = 1. Thus the height of the automorphism tower of a centreless group G may either increase or decrease in a generic extension. In fact, if M is a generic extension, then it is difficult to think of any constraints on τ(G) and τ^{M}(G); apart from the obvious one that if τ(G) ≥ 1, then τ^{M}(G) ≥ 1. (If G possesses an outer automorphism π ∈ Aut(G) ∖ Inn(G) in V, then π remains an outer automorphism in M.) These considerations led the second author to make the following conjecture in [10].

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 3

Conjecture 1.3. Let α, β be ordinals such that if α ≥ 1, then β ≥ 1. Then there exist a centreless group G and a notion of forcing ℙ such that τ(G) = α and τ^{V^{ℙ}}(G) = β.

In this paper, we will prove the consistency of a substantial strengthening of Conjecture 1.3.

Theorem 1.4. It is consistent that for every infinite cardinal λ and every ordinal α < λ, there exists a centreless group G with the following properties.

(a) τ(G) = α.

(b) If β is any ordinal such that 1 ≤ β < λ, then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that τ^{V^{ℙ}}(G) = β.

It should be pointed out that this is not the strongest conceivable consistency result on the nonabsoluteness of the heights of automorphism towers. By [10], if G is an infinite centreless group, then the automorphism tower of G terminates in strictly less than (2^{|G|})^{+} steps. However, (2^{|G|})^{+} can be an arbitrarily large cardinal in generic extensions of the ground model V. Thus the following problem remains open.

Question 1.5. Does there exist a complete group G such that for every ordinal α, there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that τ^{V^{ℙ}}(G) = α?

In Section 2, we will present an essentially algebraic argument which shows that Theorem 1.4 is a consequence of the following result.

Theorem 1.6. It is consistent that for every regular cardinal κ ≥ ω, there exists a set {Γ_{α} | α < κ^{+}} of pairwise nonisomorphic connected rigid graphs with the following property. If E is any equivalence relation on κ^{+}, then there exists a notion of forcing ℙ such that

(a) ℙ preserves cofinalities and cardinalities;

(b) ℙ does not adjoin any new κ-sequences of ordinals;

(c) each graph Γ_{α} remains rigid in V^{ℙ};

(d) Γ_{α} ≃ Γ_{β} in V^{ℙ} iff α E β.

4 JOEL DAVID HAMKINS AND SIMON THOMAS

Here a structure M is said to be rigid if Aut(M) = {id_{M}}. Thus clauses (1.6)(c) and (1.6)(d) imply that if α E β, then there exists a unique isomorphism π : Γ_{α} → Γ_{β} in V^{ℙ}. Theorem 1.6 will be proved in Section 3.

Our set-theoretic notation mainly follows that of Jech [6]. Thus if ℙ is a notion of forcing and p,q ∈ ℙ, then q ≤ p means that q is a strengthening of p. We say that ℙ is κ-closed if for every λ ≤ κ, every descending sequence of elements of ℙ

p_{0} ≥ p_{1} ≥ ⋯ ≥ p_{ξ} ≥ …, ξ < λ,

has a lower bound in ℙ. If V is the ground model, then we will denote the generic extension by V^{ℙ} if we do not wish to specify a particular generic filter H ⊆ ℙ. If we want to emphasize that the term t is to be interpreted in the generic extension M, then we write t^{M}. For example, if Γ ∈ V is a graph, then Aut^{M}(Γ) denotes the automorphism group of Γ, when the automorphism group is computed in M. The class of all ordinals will be denoted by On.

Our group-theoretic notation is standard. For example, the (restricted) wreath product of A by C is denoted by AwrC. A permutation group is a pair (G, Ω), where G is a subgroup of Sym(Ω). A pair (f, φ) is a permutation group isomorphism from (G, Ω) onto (H, Δ) if the following conditions are satisfied.

(i) f : G → H is a group isomorphism. (ii) φ : Ω → Δ is a bijection. (iii) For all g ∈ G and x ∈ Ω, f(g)(φ(x)) = φ(g(x)).

2. Normaliser towers

In this section, we will show that Theorem 1.4 is a consequence of Theorem 1.6. So throughout this section, we will assume that the following hypothesis holds in the ground model V.

Hypothesis 2.1. For every regular cardinal κ ≥ ω, there exists a set of pairwise nonisomorphic connected rigid graphs {Γ_{α} | α < κ^{+}} with the following property. If E is any equivalence relation on κ^{+}, then there exists a notion of forcing ℙ such that

(a) ℙ preserves cofinalities and cardinalities;

(b) ℙ does not adjoin any new κ-sequences of ordinals; (c) each graph Γ_{α} remains rigid in V^{ℙ};

(d) Γ_{α} ≃ Γ_{β} in V^{ℙ} iff α E β.

Our argument will use the normaliser tower technique, which was introduced in [9].

Definition 2.2. If G is a subgroup of the group H, then the normaliser tower of G in H is defined inductively as follows.

(a) N_{0}(G) = G.

(b) If α = β + 1, then N_{α}(G) = N_{H} (N_{β}(G)).

(c) If α is a limit ordinal, then N_{α}(G) = ⋃_{β<α}N_{β}(G).

The definition of the normaliser tower is motivated by the following observation.

Proposition 2.3. Let G be a centreless group, and let (G_{α} | α ≤ τ(G)) be the automorphism tower of G. Then for each α ≤ τ(G), G_{α} = N_{α}(G), where N_{α}(G) is the α^{th} group in the normaliser tower of G in G_{τ(G)}.

Proof. Let γ = τ(G). We will show that N_{G_{γ}} (G_{α}) = G_{α+1} for all α < γ. Since the inclusion G_{α} ⩽ G_{α+1} is isomorphic to the inclusion Inn(G_{α}) ⩽ Aut(G_{α}), it follows that G_{α+1} ⩽ N_{G_{γ}} (G_{α}). Conversely, suppose that g ∈ N_{G_{γ}} (G_{α}). Then g induces an automorphism of G_{α} via conjugation. Hence there exists h ∈ G_{α+1} such that hxh^{−1} = gxg^{−1} for all x ∈ G_{α}. Thus h^{−1}g ∈ C_{G_{γ}} (G_{α}). By Lemma 8.1.1 of Hulse [4], C_{G_{γ}} (G_{α}) = 1. Hence g = h ∈ G_{α+1}. Consequently, N_{G_{γ}} (G_{α}) = G_{α+1}.

The following lemma, which was essentially proved in [9], will enable us to convert normaliser towers into corresponding automorphism towers. (The proof makes use of the assumption that P SL(2, K) is simple. This is true if and only if |K| > 3.)

Lemma 2.4. Let K be a field such that |K| > 3 and let H be a subgroup of Aut(K). Let

G = P GL(2, K) ⋊ H ⩽ P Γ L(2, K) = P GL(2, K) ⋊ Aut(K).

Then G is a centreless group; and for each α, G_{α} = P GL(2, K) ⋊ N_{α}(H), where N_{α}(H) is the α^{th} group in the normaliser tower of H in Aut(K).

□

We will also make use of the following result.

Lemma 2.5 (Fried and Kollár [2]). Let Γ = ⟨X, E⟩ be any graph. Then there exists a field K_{Γ} which satisfies the following conditions.

(a) X ⊆ K_{Γ}.

(b) If ℙ is a (possibly trivial) notion of forcing and M = V^{ℙ}, then (i) π[X] = X for all π ∈ Aut^{M}(K_{Γ}); and (ii) the restriction mapping, π ↦ π ↾ X, is an isomorphism from Aut^{M}(K_{Γ})

onto Aut^{M}(Γ).

Proof. This follows from the observation that the construction of Fried and Kollár in [2] is upwards absolute.

Most of our effort in this section will go into proving the following result.

Theorem 2.6. Suppose that Hypothesis 2.1 holds. Then for every infinite cardinal λ and every ordinal α < λ, there exist a graph Γ and a subgroup H ⩽ Aut(Γ) with the following properties.

(a) The normaliser tower of H in Aut(Γ) terminates in exactly α steps.

(b) If β is any ordinal such that 1 ≤ β < λ, then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that the normaliser tower of H in Aut^{V^{ℙ}}(Γ) terminates in exactly β steps.

Corollary 2.7. Suppose that Hypothesis 2.1 holds. Then for every infinite cardinal λ and every ordinal α < λ, there exists a centreless group G with the following properties.

(a) τ(G) = α.

(b) If β is any ordinal such that 1 ≤ β < λ, then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that τ^{V^{ℙ}}(G) = β.

Proof. Let Γ and H ≤ Aut(Γ) be the graph and subgroup which are given by Theorem 2.6. Let K_{Γ} be the corresponding field which is given by Lemma 2.5. By Lemma 2.4, the centreless group G = P GL(2, K_{Γ}) ⋊ H satisfies our requirements.

Now we will begin the proof of Theorem 2.6.

Definition 2.8. (a) Suppose that Γ_{i} = (X_{i}, E_{i}) is a graph for each i ∈ I. Then the direct sum of the graphs {Γ_{i} | i ∈ I} is defined to be the graph

⨁_{i∈I} Γ_{i} = (⨆_{i∈I} X_{i}, ⨆_{i∈I} E_{i}) .

Here ⨆_{i∈I} X_{i} and ⨆_{i∈I} E_{i} denote the disjoint unions of the sets of vertices and edges respectively.

(b) Suppose further that H_{i} ⩽ Aut(Γ_{i}) for each i ∈ I. Then the direct product of the permutation groups {(H_{i}, Γ_{i}) | i ∈ I} is defined to be the permutation group

∏_{i∈I} (H_{i}, Γ_{i}) = (∏_{i∈I} H_{i}, ⨁_{i∈I} Γ_{i}) ,

where ∏_{i∈I} H_{i} acts on ⨁_{i∈I} Γ_{i} in the obvious manner. If I = {1, 2}, then we write ∏_{i∈I} (H_{i}, Γ_{i}) = (H_{1}, Γ_{1}) × (H_{2}, Γ_{2}) = (H_{1} × H_{2}, Γ_{1} ⊕ Γ_{2}).

Definition 2.9. Let Γ be a rigid connected graph. For each α, we define permutation groups (H_{α}(Γ), G_{α}(Γ)) and (F_{α}(Γ), G_{α}(Γ)) inductively as follows.

(a) (H_{0}(Γ), G_{0}(Γ)) = (F_{0}(Γ), G_{0}(Γ)) = (Aut(Γ), Γ) = (1, Γ).

(b) If α > 0, then we define

(H_{α}(Γ), G_{α}(Γ)) = (F_{0}(Γ), G_{0}(Γ)) × ∏_{β<α} (F_{β}(Γ), G_{β}(Γ)) ,

and we define F_{α}(Γ) to be the terminal group of the normaliser tower of H_{α}(Γ) in Aut(G_{α}(Γ)).

The next lemma shows that the normaliser tower of H_{α}(Γ) in Aut(G_{α}(Γ)) terminates in exactly α steps. As the proof of Lemma 2.10 is rather involved, we will first explain the basic idea for the case when α is a successor ordinal. Let α = β +1. Then

(H_{β+1}(Γ), G_{β+1}(Γ)) = (H_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) .

We will see that for each γ ≤ β, the γ^{th} group in the normaliser tower of H_{β+1}(Γ) in Aut(G_{β+1}(Γ)) is

(N_{γ}(H_{β}(Γ)), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) ,

8 JOEL DAVID HAMKINS AND SIMON THOMAS

where N_{γ}(H_{β}(Γ)) is the γ^{th} group in the normaliser tower of H_{β}(Γ) in Aut(G_{β}(Γ)). In particular, the β^{th} group in the normaliser tower of H_{β+1}(Γ) in Aut(G_{β+1}(Γ)) is

(F_{β}(Γ)), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) .

It is now easily seen that the (β + 1)^{st} group in the normaliser tower of H_{β+1}(Γ) in Aut(G_{β+1}(Γ)) is

([F_{β} × F_{β}] ⋊ ⟨π⟩, G_{β}(Γ) ⊕ G_{β}(Γ)),

where π is an element of order 2 which interchanges the two disjoint copies of G_{β}(Γ); and it turns out that this group is self-normalising in Aut(G_{β+1}(Γ)).

In the proof of Lemma 2.10, we will need to study the blocks of imprimitivity of F_{α}(Γ) in its action on the set of connected components of G_{α}(Γ). Recall that if (G, Ω) is a transitive permutation group, then the nonempty subset Z of Ω is a block of imprimitivity if for each g ∈ G, either g[Z] = Z or g[Z] ∩ Z = ∅. In this case, we obtain a G-invariant equivalence relation E on Ω corresponding to the partition {g[Z] | g ∈ G}.

Lemma 2.10. If Γ is a rigid connected graph, then normaliser tower of H_{α}(Γ) in Aut(G_{α}(Γ)) terminates in exactly α steps.

Proof. During the course of this proof, we will need a more explicit definition of the graph G_{α}(Γ). So for each ordinal α, we define the graphs G_{α}(Γ) and G_{α}^{1}(Γ) inductively as follows.

(a) G_{0}(Γ) = Γ.

(b) Suppose that α = β + 1 and that G_{β}(Γ) has been defined. Let G_{β}^{1}(Γ) be a graph such that G_{β}^{1}(Γ) ∩ G_{β}(Γ) = ∅ and G_{β}^{1}(Γ) ≃ G_{β}(Γ). Then we define G_{β+1}(Γ) = G_{β}(Γ) ⊔ G_{β}^{1}(Γ).

(c) If α is a limit ordinal, then we define G_{α}(Γ) = ⋃_{β<α}G_{β}(Γ). In particular, for each ordinal β, we have that

(H_{β+1}(Γ), G_{β+1}(Γ)) = (H_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ), G_{β}^{1}(Γ)) .

For each ordinal α, let Δ_{α} and Δ_{α}^{1} be the sets of connected components of the graphs G_{α}(Γ) and G_{α}^{1}(Γ) respectively. Then for all β < α, we have that

Δ_{α} = Δ_{β} ⊔ ⨆_{β≤γ<α} Δ_{γ}^{1}.

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 9

Since Γ is a rigid connected graph, Aut(G_{α}(Γ)) can be identified naturally with Sym(Δ_{α}). This allows us to regard H_{α}(Γ) and F_{α}(Γ) as subgroups of Sym(Δ_{α}). We will need to consider direct products of permutation groups of the form (F_{α}(Γ), Δ_{α}) or (F_{α}(Γ), Δ_{α}^{1}). We will regard each set Δ_{α} and Δ_{α}^{1} as a null graph, and continue to use the notation introduced in Definition 2.8. Thus

(H_{α}(Γ), Δ_{α}) = (F_{0}(Γ), Δ_{0}) × ∏_{β<α} (F_{β}(Γ), Δ_{β}^{1}) .

We will prove the following statements by a simultaneous induction on α ≥ 0. (1_{α}) F_{α}(Γ) acts transitively on Δ_{α}. (2_{α}) Let Δ_{0} = {v_{0}}. Then {Δ_{β} | β ≤ α} is the set of blocks Z of imprimitivity of

(F_{α}(Γ), Δ_{α}) such that v_{0} ∈ Z. (3_{α}) For each β ≤ α, let E_{β} be the F_{α}(Γ)-invariant equivalence relation corre-

sponding to the partition {g [Δ_{β}] | g ∈ F_{α}(Γ)}. Then for each β ≤ γ < α, the set Δ_{γ}^{1} is a union of E_{β}-equivalence classes. (Strictly speaking, we should write E_{β}^{α} to indicate that this is the F_{α}(Γ)-invariant equivalence relation on Δ_{α} corresponding to the block of imprimitivity Δ_{β}. However, this slight abuse of notation should not cause any confusion.)

(4_{α}) If β < α, then

(N_{β}(H_{α}(Γ)), Δ_{α}) = (F_{β}(Γ), Δ_{β}) × ∏_{β≤γ<α} (F_{γ}(Γ), Δ_{γ}^{1}) .

(5_{α}) Furthermore, if β < α, then N_{β}(H_{α}(Γ)) is the stabiliser of the partition

{Δ_{β}} ∪ {Δ_{γ}^{1} | β ≤ γ < α} in F_{α}(Γ). (6_{α}) N_{α}(H_{α}(Γ)) is self-normalising in Sym(Δ_{α}); and so N_{α}(H_{α}(Γ)) = F_{α}(Γ).

Let β ≤ α and let v be any point of Δ_{β}. Let B_{β}(v) be the set of blocks Z of imprimitivity of (F_{β}(Γ), Δ_{β}) such that v ∈ Z. Then conditions (1_{β}) and (2_{β}) imply that B_{β}(v), ordered by inclusion, is a well-ordering of order-type β + 1. Hence conditions (1_{β}) and (2_{β}) for all β ≤ α yield the following statement. (7_{α}) If β < γ ≤ α, then (F_{β}(Γ), Δ_{β}) and (F_{γ}(Γ), Δ_{γ}) are nonisomorphic permuta-

tion groups. Note that |Δ_{n}| = 2^{n} for all n ∈ ω. It is easily checked that the result holds for α =

0, 1, 2. Furthermore, F_{0}(Γ) = 1, F_{1}(Γ) = Sym(2) and F_{2}(Γ) = Sym(2)wr Sym(2). In the successor stage of the argument, we will appeal to a result of Neumann [8]

10 JOEL DAVID HAMKINS AND SIMON THOMAS

on the automorphism groups of wreath products AwrC. The hypotheses of this result require that A should not be a “special dihedral” group. For our purposes, it is enough to know that if Sym(2)wr Sym(2) ⩽ A, then A is not a “special dihedral” group.

Now suppose that α ≥ 2 and that the result holds for all β ≤ α. Remember that if (G, Ω) is a permutation group and π ∈ Sym(Ω) normalises G, then π permutes the orbits of G. Furthermore, if X and Y are G-orbits and π[X] = Y, then G must induce isomorphic permutation groups via its actions on X and Y. Using this observation, together with the inductive hypotheses for β ≤ α, we see that

(N_{β}(H_{α+1}(Γ)), Δ_{α+1}) = (F_{β}(Γ), Δ_{β}) × ∏_{β≤γ<α+1} (F_{γ}(Γ), Δ_{γ}^{1})

for all β ≤ α. In particular, we have that

(N_{α}(H_{α+1}(Γ)), Δ_{α+1}) = (F_{α}(Γ), Δ_{α}) × (F_{α}(Γ), Δ_{α}^{1}) .

It follows easily that

(N_{α+1}(H_{α+1}(Γ)), Δ_{α+1}) = (F_{α}(Γ)wr Sym(2), Δ_{α} ⊔ Δ_{α}^{1}) .

Notice that we have already established conditions (1_{α+1}) and (4_{α+1}). Next suppose that g ∈ Sym(Δ_{α+1}) normalises N_{α+1}(H_{α+1}(Γ)) = F_{α}(Γ)wr Sym(2). By Theorem 9.12 of Neumann [8], the base group F_{α}(Γ) × F_{α}(Γ) is a characteristic subgroup of the wreath product F_{α}(Γ)wr Sym(2). Hence g must also normalise N_{α}(H_{α+1}(Γ)) = F_{α}(Γ) × F_{α}(Γ); and so g ∈ N_{α+1}(H_{α+1}(Γ)). Thus condition (6_{α+1}) also holds. It is now easily checked that conditions (2_{α+1}), (3_{α+1}) and (5_{α+1}) hold. Thus the result holds for α + 1.

Now suppose that λ is a limit ordinal, and that the result holds for all α < λ. Once again, it is easy to see that conditions (4_{λ}) and (1_{λ}) hold. It is also easily checked that the following statements hold. (2_{λ})′ For each β ≤ λ, the set Δ_{β} is a block of imprimitivity of (N_{λ}(H_{λ}(Γ)), Δ_{λ}). (3_{λ})′ For each β ≤ λ, let E_{β} be the N_{λ}(H_{λ}(Γ))-invariant equivalence relation corre-

sponding to the partition {g [Δ_{β}] | g ∈ N_{λ}(H_{λ}(Γ))}. Then for each β ≤ γ < λ, the set Δ_{γ}^{1} is a union of E_{β}-equivalence classes.

(5_{λ})′ For each β < λ, the subgroup N_{β}(H_{λ}(Γ)) is the stabiliser of the partition {Δ_{β}} ∪ {Δ_{γ}^{1} | β ≤ γ < λ} in N_{λ}(H_{λ}(Γ)).

Thus it is enough to prove the following two claims.

Claim 2.11. If Z is a block of imprimitivity of (N_{λ}(H_{λ}(Γ)), Δ_{λ}) such that v_{0} ∈ Z, then Z = Δ_{β} for some β ≤ λ.

Claim 2.12. N_{λ}(H_{λ}(Γ)) is self-normalising in Sym(Δ_{λ}); and so N_{λ}(H_{λ}(Γ)) = F_{λ}(Γ).

Proof of Claim 2.11. If there exists γ < λ such that Z ⊆ Δ_{γ}, then it follows from the inductive hypotheses that Z = Δ_{β} for some β ≤ γ. Hence we can suppose that the set I = {γ < λ | Z ∩ Δ_{γ}^{1} ≠ ∅} is cofinal in λ. Fix some γ ∈ I. By condition (4_{λ}),

(N_{γ}(H_{λ}(Γ)), Δ_{λ}) = (F_{γ}(Γ), Δ_{γ}) × ∏_{γ≤ξ<λ} (F_{ξ}(Γ), Δ_{ξ}^{1}) .

Hence for each x ∈ Δ_{γ}, there exists an element g ∈ N_{γ}(H_{λ}(Γ)) ⩽ N_{λ}(H_{λ}(Γ)) such that

(i) g(v_{0}) = x; and (ii) g(y) = y for all y ∈ Δ_{γ}^{1}. By condition (ii), g[Z] ∩ Z ≠ ∅ and hence x ∈ g[Z] = Z. Thus Δ_{γ} ⊆ Z for each γ ∈ I, and so Z = Δ_{λ}.

Proof of Claim 2.12. Note that for each π ∈ N_{λ}(H_{λ}(Γ)), there exists β < λ such that π ∈ N_{β}(H_{λ}(Γ)); and so π [Δ_{γ}^{1}] = Δ_{γ}^{1} for all β ≤ γ < λ. Suppose that g ∈ Sym(Δ_{λ}) normalises N_{λ}(H_{λ}(Γ)). Then g must permute the set {E_{β} | β ≤ λ} of N_{λ}(H_{λ}(Γ))-invariant equivalence relations on Δ_{λ}. Since the set {E_{β} | β ≤ λ} is well-ordered under inclusion, it follows that E_{β} is also g-invariant for each β ≤ λ.

Next we will show that there exists an ordinal β < λ such that g [Δ_{γ}^{1}] = Δ_{γ}^{1} for all β ≤ γ < λ. For each γ < λ, let C_{γ}^{1} = g [Δ_{γ}^{1}]. Suppose that there exists a cofinal subset I ⊆ λ such that C_{γ}^{1} ≠ Δ_{γ}^{1} for all γ ∈ I. Fix some γ ∈ I. Since Δ_{γ}^{1} is an E_{γ}-equivalence class, it follows that C_{γ}^{1} = g [Δ_{γ}^{1}] is also an E_{γ}-equivalence class. Using condition (3_{λ})′, it follows that either

(i) C_{γ}^{1} = Δ_{γ}, or (ii) there exists f(γ) > γ such that C_{γ}^{1} ⊊ Δ_{f(γ)}^{1}.

12 JOEL DAVID HAMKINS AND SIMON THOMAS

Clearly we can assume that condition (ii) holds for all γ ∈ I. Furthermore, by passing to a suitable subset of I if necessary, we can assume that the resulting function f : I → λ is injective. Remember that

(H_{λ}(Γ), Δ_{λ}) = (F_{0}(Γ), Δ_{0}) × ∏_{0≤ξ<λ} (F_{ξ}(Γ), Δ_{ξ}^{1}) .

Since each F_{ξ}(Γ) acts transitively on Δ_{ξ}^{1}, there exists an element ψ ∈ H_{λ}(Γ) ⩽ N_{λ}(H_{λ}(Γ)) such that ψ [C_{γ}^{1}] ≠ C_{γ}^{1} for all γ ∈ I. Let π = g^{−1}ψg ∈ N_{λ}(H_{λ}(Γ)). Then π [Δ_{γ}^{1}] ≠ Δ_{γ}^{1} for all γ ∈ I, which is a contradiction.

Thus there exists β < λ such that g ∈ Sym(Δ_{β}) × ∏_{β≤γ<λ} Sym(Δ_{γ}^{1}). Since N_{β}(H_{λ}(Γ)) is the stabiliser of the partition {Δ_{β}}∪{Δ_{γ}^{1} | β ≤ γ < λ} in N_{λ}(H_{λ}(Γ)), it follows that g normalises N_{β}(H_{λ}(Γ)). Thus g ∈ N_{β+1}(H_{λ}(Γ)) ⩽ N_{λ}(H_{λ}(Γ)).

This completes the proof of Lemma 2.10.

Definition 2.13. Let Γ be a connected rigid graph. If 1 ≤ β < α, then we define

(D_{β}^{α}(Γ), G_{β}^{α}(Γ)) = (H_{α}(Γ), G_{α}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) .

Lemma 2.14. If Γ is a connected rigid graph, then the normaliser tower of D_{β}^{α}(Γ) in Aut(G_{β}^{α}(Γ)) terminates in exactly β steps.

Proof. Let (B, Γ′) = (F_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ), G_{β}(Γ)), and let F_{β}(Γ) wr Sym(3) = B ⋊ Sym(3) be the associated wreath product. By rearranging the order of its factors, we can identify (D_{β}^{α}(Γ), G_{β}^{α}(Γ)) with

(H_{β}(Γ), G_{β}(Γ)) × (B, Γ′) × ∏_{β<γ<α} (F_{γ}(Γ), G_{γ}(Γ)) .

Arguing as in the proof of Lemma 2.10, we find that the β^{th} element of the normaliser tower of D_{β}^{α}(Γ) in Aut(G_{β}^{α}(Γ)) is

(F_{β}(Γ), G_{β}(Γ)) × (F_{β}(Γ) wr Sym(3), Γ′) × ∏_{β<γ<α} (F_{γ}(Γ), G_{γ}(Γ)) ;

and also that this group is self-normalising in Aut(G_{β}^{α}(Γ)).

Now let λ be any infinite cardinal and let α be any ordinal such that α < λ. Choose a regular cardinal κ such that λ ≤ κ. Let {Γ_{γ} | γ < κ^{+}} be the set of

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 13

pairwise nonisomorphic connected rigid graphs given by Hypothesis 2.1. If α ≥ 1, then we define

(B_{α}, Γ^{α}) = ∏_{1≤β<α}((F_{β}(Γ_{β}), G_{β}(Γ_{β})) × (F_{β}(Γ_{β}), G_{β}(Γ_{β})))

and

(H, Γ) = (B_{α}, Γ^{α}) × (H_{α}(Γ_{α}), G_{α}(Γ_{α})) × ∏_{α≤γ<λ} (F_{γ}(Γ_{γ+1}), G_{γ}(Γ_{γ+1})) .

If α = 0, then we define

(H, Γ) = (F_{0}(Γ_{0}), G_{0}(Γ_{0})) × ∏_{0≤γ<λ} (F_{γ}(Γ_{γ+1}), G_{γ}(Γ_{γ+1})) .

We will show that Γ and H ⩽ Aut(Γ) satisfy the requirements of Theorem 2.6.

Lemma 2.15. The normaliser tower of H in Aut(Γ) terminates in exactly α steps.

Proof. For example, suppose that α ≥ 1. Then

Aut(Γ) = Aut(Γ^{α}) × Aut(G_{α}(Γ_{α})) × ∏_{α≤γ<λ} Aut(G_{γ}(Γ_{γ+1})).

Using Lemma 2.10, we see that

(a) the normaliser tower of B_{α} in Aut(Γ^{α}) terminates in exactly 1 step;

(b) the normaliser tower of H_{α}(Γ_{α}) in Aut(G_{α}(Γ_{α})) terminates in exactly α steps; and

(c) the normaliser tower of ∏_{α≤γ<λ} F_{γ}(Γ_{γ+1}) in ∏_{α≤γ<λ} Aut(G_{γ}(Γ_{γ+1})) terminates in exactly 0 steps.

It follows that the normaliser tower of H in Aut(Γ) terminates in exactly α steps.

Lemma 2.16. If β is any ordinal such that 1 ≤ β < λ, then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that the normaliser tower of H in Aut^{V^{ℙ}}(Γ) terminates in exactly β steps.

Proof. Clearly we can suppose that β ≠ α. There are two cases to consider. First suppose that 1 ≤ β < α. Let E be the equivalence relation on κ^{+} such that

γ E δ iff {γ, δ} = {α, β} or γ = δ;

14 JOEL DAVID HAMKINS AND SIMON THOMAS

and let ℙ be the corresponding notion of forcing, given by Hypothesis 2.1. Using the facts that

(a) each graph Γ_{δ} remains rigid in V^{ℙ}, and

(b) ℙ does not adjoin any new κ-sequences of ordinals, we see that (H_{γ}(Γ_{δ}), G_{γ}(Γ_{δ}))^{V^{ℙ}} = (H_{γ}(Γ_{δ}), G_{γ}(Γ_{δ})) and (F_{γ}(Γ_{δ}), G_{γ}(Γ_{δ}))^{V^{ℙ}} = (F_{γ}(Γ_{δ}), G_{γ}(Γ_{δ})) for all γ, δ < κ^{+}. Let

(B′, Γ′) = ∏_{\begin{matrix}1≤γ<α \\ γ≠β \end{matrix}} ((F_{γ}(Γ_{γ}), G_{γ}(Γ_{γ})) × (F_{γ}(Γ_{γ}), G_{γ}(Γ_{γ}))) .

Then in V^{ℙ}, (H, Γ) is isomorphic to

(B′, Γ′) × (D_{β}^{α}(Γ_{α}), G_{β}^{α}(Γ_{α})) × ∏_{α≤γ<λ} (F_{γ}(Γ_{γ+1}), G_{γ}(Γ_{γ+1})) .

Hence the normaliser tower of H in Aut^{V^{ℙ}}(Γ) terminates in exactly β steps.

Now suppose that α < β < λ. We will only deal with the case when α ≥ 1. (The case when α = 0 is almost identical.) Now let E be the equivalence relation on κ^{+} such that γ E δ iff either

(i) α ≤ γ, δ < β + 1; or (ii) γ = δ ; and let ℙ be the corresponding notion of forcing, given by Hypothesis 2.1. Then in V^{ℙ}, (H, Γ) is isomorphic to

(B_{α}, Γ^{α}) × (H_{β}(Γ_{α}), G_{β}(Γ_{α})) × ∏_{β≤γ<λ} (F_{γ}(Γ_{γ+1}), G_{γ}(Γ_{γ+1})) .

Hence the normaliser tower of H in Aut^{V^{ℙ}}(Γ) terminates in exactly β steps.

3. Rigid trees

In this section, we will prove Theorem 1.6. Rather than working directly with graphs, we will find it more convenient to prove the following analogous theorem for trees. To obtain Theorem 1.6, we can then use one of the standard coding procedures to uniformly convert each tree T_{α} into a corresponding graph Γ(T_{α}). (For example, we can use the coding of Theorem 5.5.1 [3].)

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 15

Theorem 3.1. It is consistent that for every regular cardinal κ ≥ ω, there exists a set {T_{α} | α < κ^{+}} of pairwise nonisomorphic rigid trees of height κ^{+} with the following property. If E is any equivalence relation on κ^{+}, then there exists a notion of forcing ℙ such that

(a) ℙ preserves cofinalities and cardinalities;

(b) ℙ does not adjoin any new κ-sequences of ordinals;

(c) each tree T_{α} remains rigid in V^{ℙ};

(d) T_{α} ≃ T_{β} in V^{ℙ} iff α E β.

Our proof of Theorem 3.1 relies heavily on the ideas of Jech [5]. First we need to introduce some notions from the theory of trees.

Definition 3.2. (a) A tree is a partially ordered set ⟨T, <⟩ such that for every

x ∈ T, the set pred_{T} (x) = {y ∈ T | y < x} is well-ordered by <.

(b) If x ∈ T, then the height of x in T, denoted ht_{T} (x), is the order-type of pred_{T} (x) under <.

(c) If α is an ordinal, then the α^{th} level of T is the set

Lev_{α}(T) = {x ∈ T | ht_{T} (x) = α}

and T ↾ α = ⋃_{β<α} Lev_{β}(T).

(d) A branch of T is a maximal linearly ordered subset of T. The length of a branch B is the order-type of B. An α-branch is a branch of length α.

Definition 3.3. Let δ be an ordinal and let λ be a cardinal. A tree T is said to be a (δ, λ)-tree iff

(i) for all α < δ, 0 < |Lev_{α}(T)| < λ; and (ii) Lev_{δ}(T) = ∅. A (δ, λ)-tree T is normal if each of the following conditions is satisfied.

(a) If δ > 0, then |Lev_{0}(T)| = 1.

(b) If α + 1 < δ and x ∈ Lev_{α}(T), then there exist exactly two elements y_{1}, y_{2} ∈ Lev_{α+1}(T) such that x < y_{1} and x < y_{2}.

(c) If α < β < δ and x ∈ Lev_{α}(T), then there exists y ∈ Lev_{β}(T) such that x < y.

16 JOEL DAVID HAMKINS AND SIMON THOMAS

(d) Suppose that α is a limit ordinal and x, y ∈ Lev_{α}(T). If pred_{T} (x) = pred_{T} (y), then x = y.

Let T be a (δ, λ)-tree. Then the tree T^{+} is an end-extension of T, written T ⋖ T^{+}, if T^{+} ↾ δ = T. The tree T^{+} is a proper end-extension if T ⋖ T^{+} and T ≠ T^{+}.

Definition 3.4. Let κ ≥ ω be a regular cardinal such that κ^{<κ} = κ, and let α < κ^{+}. A normal (α, κ^{+})-tree T is <κ-closed if for each β < α such that cf(β) < κ and each increasing sequence of elements of T

x_{0} < x_{1} < ⋯ < x_{ξ} < …, ξ < β,

such that x_{ξ} ∈ Lev_{ξ}(T) for each ξ < β, there exists an element y ∈ Lev_{β}(T) such that pred_{T} (y) = {x_{ξ} | ξ < β}.

Lemma 3.5. Let κ ≥ ω be a regular cardinal such that κ^{<κ} = κ.

(a) For each α < κ^{+}, there exists a <κ-closed normal (α, κ^{+})-tree.

(b) If α < β < κ^{+} and S is a <κ-closed normal (α, κ^{+})-tree, then there exists a <κ-closed normal (β, κ^{+})-tree T such that S ⋖ T.

Proof. Left to the reader.

Lemma 3.6. Let κ ≥ ω be a regular cardinal such that κ^{<κ} = κ, and let α < κ^{+}. If S and T are <κ-closed normal (α, κ^{+})-trees, then S ≃ T. Furthermore, if δ+1 ≤ α, then for each isomorphism φ : S ↾ (δ+1) → T ↾ (δ+1), there exists an isomorphism π : S → T such that φ ⊆ π.

Proof. If α ≤ κ, then S and T are both complete binary trees of height α, and so S ≃ T. Hence we can suppose that κ < α < κ^{+}. Thus |S| = |T | = κ. We will define an isomorphism π = ⋃_{ξ<κ}π_{ξ} : S → T via a back-and -forth argument.

Suppose that we have defined π_{ξ} for some ξ < κ. Assume inductively that there exists a set {B_{i} | i ∈ I} of α-branches of S such that

(i) |I| < κ; and

(ii) dom π_{ξ} = ⋃_{i∈I}B_{i}.

Let s be any element of S ∖ dom π_{ξ}. Choose an α-branch B of S such that s ∈ B. Let B = {b_{τ} | τ < α}, where b_{τ} ∈ B ∩ Lev_{τ} (S). Let β be the least ordinal such that b_{β} ∉ dom π_{ξ}. First suppose that β = γ + 1 is a successor ordinal. Then there

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 17

exists an i ∈ I such that b_{γ} ∈ B_{i}. Let C_{i} = π_{ξ} [B_{i}]. Then there exists a unique element c ∈ Lev_{β}(T) ∖ C_{i} such that π_{ξ}(b_{γ}) < c. Let C be an α-branch of T such that c ∈ C; and let ψ : B → C be the unique order-preserving bijection. Then π_{ξ+1} = π_{ξ} ∪ ψ is a partial isomorphism such that s ∈ dom π_{ξ+1}. Now suppose that β is a limit ordinal. Since {b_{τ} | τ < β} is covered by the set {B_{i} | i ∈ I} of branches, it follows that cf(β) < κ. Hence there exists an element c ∈ Lev_{β}(T) such that pred_{T} (c) = {π_{ξ}(b_{τ}) | τ < β}. Let C be an α-branch of T such that c ∈ C; and let ψ : B → C be the unique order-preserving bijection. Once again, π_{ξ+1} = π_{ξ} ∪ ψ is a partial isomorphism such that s ∈ dom π_{ξ+1}. By a similar argument, if t is any element of T ∖ran(π_{ξ+1}), then we can find a partial isomorphism π_{ξ+2} ⊃ π_{ξ+1} such that t ∈ ran π_{ξ+2}. Hence we can ensure that π = ⋃_{ξ<κ}π_{ξ} is an isomorphism from S onto T.

Finally suppose that δ + 1 ≤ α and that φ : S ↾ (δ + 1) → T ↾ (δ + 1) is an isomorphism. For each s ∈ S and t ∈ T, define S[s] = {x ∈ S | s ≤ x} and T [t] = {y ∈ T | t ≤ y}. Let γ be the ordinal such that α = δ + γ. Then for each s ∈ Lev_{δ}(S), both S[s] and T [φ(s)] are <κ-closed normal (γ, κ^{+})-trees; and so S[s] ≃ T [φ(s)]. Hence φ can be extended to an isomorphism π : S → T.

Next we will discuss the notion of forcing ℚ_{κ} which adjoins the set {T_{α} | α < κ^{+}} of distinct pairwise nonisomorphic rigid trees of height κ^{+}.

Definition 3.7. Let κ ≥ ω be a regular cardinal such that κ^{<κ} = κ. Then ℚ_{κ} is the notion of forcing consisting of all conditions p = ⟨t_{α}^{p} | α < κ^{+}⟩, where

(a) each t_{α}^{p} is a <κ-closed normal (β_{α}, κ^{+})-tree for some β_{α} < κ^{+}; and

(b) there exists an ordinal γ < κ^{+} such that t_{α}^{p} = ∅ for all γ ≤ α < κ^{+}. We define q ≤ p iff t_{α}^{p} ⋖ t_{α}^{q} for all α < κ^{+}.

Until further notice, we will work with the ground model M. Suppose that κ ≥ ω is a regular cardinal such that κ^{<κ} = κ and 2^{κ} = κ^{+}. Then it is easily checked that ℚ_{κ} is κ-closed and that |ℚ_{κ}| = κ^{+}. Hence ℚ_{κ} preserves cofinalities and cardinalities. Let G be an M-generic filter on ℚ_{κ}. For each α < κ^{+}, let T_{α} = ⋃{t_{α}^{p} | p ∈ G}.

Lemma 3.8. In M[G], {T_{α} | α < κ^{+}} is a set of distinct pairwise nonisomorphic rigid trees of height κ^{+}.

18 JOEL DAVID HAMKINS AND SIMON THOMAS

Proof. For each α < κ^{+}, let T̃_{α} be the canonical ℚ_{κ}-name for T_{α}. First suppose that for some α < κ^{+}, there exists a nonidentity automorphism f of T_{α} in M[G]. Let f̃ be a ℚ_{κ}-name for f. Then there exists a condition p ∈ ℚ_{κ} and an element a ∈ t_{α}^{p} such that

p ⊩ f̃: T̃_{α} → T̃_{α} is an isomorphism such that f̃(a) ≠ a.

Since ℚ_{κ} is κ-closed, we can inductively define a descending sequence of conditions ⟨p_{ξ} | ξ < κ⟩ such that

(1) p_{0} = p;

(2) t_{α}^{p_{ξ+1}} is a proper end-extension of t_{α}^{p_{ξ}}; and

(3) p_{ξ+1} decides f̃ ↾ t_{α}^{p_{ξ}}. Let q be the greatest lower bound of the sequence ⟨p_{ξ} | ξ < κ⟩. Then t_{α}^{q} = ⋃_{ξ<κ}t_{α}^{p_{ξ}}, and so q decides f̃ ↾ t_{α}^{q}. (In the rest of this paper, we will refer to the above argument as the bootstrap argument.) Note that t_{α}^{q} is a <κ-closed normal (γ, κ^{+})- tree for some ordinal γ such that cf(γ) = κ. Let B be a γ-branch of t_{α}^{q} such that a ∈ B, and let C be the γ-branch of t_{α}^{q} such that q ⊩ f̃[B] = C. Then B ≠ C. Since cf(γ) = κ, there exists a <κ-closed normal (γ + 1, κ^{+})-tree t_{α}^{+} such that

(i) t_{α}^{+} is a proper end-extension of t_{α}^{q}; (ii) there exists x ∈ t_{α}^{+} such that pred_{t_{α}^{+}}(x) = B; and (iii) there does not exist y ∈ t_{α}^{+} such that pred_{t_{α}^{+}}(y) = C. Let r ≤ q be a condition such that t_{α}^{+} ⋖ t_{α}^{r}. Then

r ⊩ f̃ ↾ t_{α}^{q} cannot be extended to an automorphism of t_{α}^{+}.

This is a contradiction.

Now suppose that for some α < β < κ^{+}, there exists an isomorphism g : T_{α} → T_{β} in M[G]. Let g̃ be a ℚ_{κ}-name for g. Then there exists a condition p ∈ ℚ_{κ} such that

p ⊩ g̃: T̃_{α} → T̃_{β} is an isomorphism.

By the bootstrap argument, there exists a condition q ≤ p such that

(a) t_{α}^{q} and t_{β}^{q} are <κ-closed normal (γ, κ^{+})-trees for some γ such that cf(γ) = κ;

(b) q decides g̃ ↾ t_{α}^{q}.

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 19

But then there exist <κ-closed normal (γ + 1, κ^{+})-trees t_{α}^{+} and t_{β}^{+} such that

(1) t_{α}^{+} and t_{β}^{+} are proper end-extensions of t_{α}^{q}, t_{β}^{q} respectively; and

(2) g̃ ↾ t_{α}^{q} cannot be extended to an isomorphism from t_{α}^{+} onto t_{β}^{+}. Once again, this yields a contradiction.

(A similar argument shows that each T_{α} is a κ^{+}-Suslin tree; cf. the proof of Theorem 48 [6].)

Next suppose that E is any equivalence relation on κ^{+}. Let A ⊆ κ^{+} be the set of E-equivalence class representatives obtained by selecting the least element of each class.

Definition 3.9. ℙ_{E} is the notion of forcing in M[G] consisting of all conditions p = ⟨f_{αβ} | α < β < κ^{+}⟩ such that for some γ < κ^{+},

(a) if α ∈ A, β < γ and α E β, then there exists δ < κ^{+} such that f_{αβ} is an isomorphism from T_{α} ↾ (δ + 1) onto T_{β} ↾ (δ + 1);

(b) otherwise, f_{αβ} = ∅. The ordering on ℙ_{E} is the obvious one.

Remark 3.10. Some readers may be wondering why we have introduced the set A of E-equivalence class representatives. Consider the slightly simpler notion of forcing ℙ′_{E} consisting of all conditions p = ⟨f_{αβ} | α < β < κ^{+}⟩ such that for some γ < κ^{+},

(a) if α < β < γ and α E β, then there exists δ < κ^{+} such that f_{αβ} is an isomorphism from T_{α} ↾ (δ + 1) onto T_{β} ↾ (δ + 1);

(b) otherwise, f_{αβ} = ∅. Using Lemma 3.6, it is easily seen that ℙ′_{E} adjoins a generic isomorphism g_{αβ} : T_{α} → T_{β} for each α < β < κ^{+} such that α E β. Fix such a pair α < β, and suppose that there exists an ordinal γ such that β < γ < κ^{+} and β E γ. Then g_{αγ} and g_{βγ} ∘ g_{αβ} will be distinct isomorphisms from T_{α} onto T_{γ}; and so T_{α} will no longer be rigid. The set A was introduced to deal with precisely this problem. For example, suppose that α ∈ A. Then the notion of forcing ℙ_{E} will only directly adjoin isomorphisms g_{αβ} : T_{α} → T_{β} and g_{αγ} : T_{α} → T_{γ}. Of course, we can then obtain an isomorphism from T_{β} onto T_{γ} by forming the composition g_{αγ} ∘ g_{αβ}^{−1}.

Let H be an M[G]-generic filter on ℙ_{E}. The following result is an immediate consequence of the discussion in Remark 3.10.

Lemma 3.11. If α < β < κ^{+} and α E β, then there exists an isomorphism g_{αβ} : T_{α} → T_{β} in M[G][H].

□

Lemma 3.12. ℙ_{E} preserves cofinalities and cardinalities, and does not adjoin any new κ-sequences of ordinals. The following statements hold in M[G][H].

(a) T_{α} is rigid for each α < κ^{+}.

(b) If α < β < κ^{+}, then T_{α} ≃ T_{β} iff α E β.

Proof. Let Ẽ, Ã and ℙ̃_{E} be ℚ_{κ}-names for E, A and ℙ_{E} respectively. Let ℝ be the subset of ℚ_{κ} ∗ ℙ̃_{E} consisting of those conditions

⟨p, q̃⟩ = ⟨⟨t_{α}^{p} | α < κ^{+}⟩, ⟨f_{αβ} | α < β < κ^{+}⟩⟩

such that for some γ, δ < κ^{+},

(1) p decides Ẽ ↾ (γ × γ), and hence p also decides Ã ∩ γ;

(2) if α < γ, then t_{α}^{p} is a <κ-closed normal (δ + 1, κ^{+})-tree; and

(3) (i) if α < β < γ and p ⊩ α ∈ Ã and α Ẽ β, then f_{αβ} is an isomorphism from

t_{α}^{p} onto t_{β}^{p}; (ii) otherwise, f_{αβ} = ∅.

(Here we are identifying each isomorphism f_{αβ} with its canonical ℚ_{κ}-name f̌_{αβ}.)

Claim 3.13. ℝ is a dense subset of ℚ_{κ} ∗ ℙ̃_{E}.

Proof of Claim 3.13. Let ⟨p, q̃⟩ = ⟨p, ⟨f̃_{αβ} | α < β < κ^{+}⟩⟩ be any element of ℚ_{κ}∗ℙ̃_{E}. Then there exists p′ ≤ p and γ < κ^{+} such that p′ forces

(a) f̃_{αβ} = ∅ for all β ≥ γ; and

(b) if α ∈ Ã, β < γ and α Ẽ β, then there exists τ < γ such that dom f̃_{αβ} is a <κ-closed normal (τ + 1, κ^{+})-tree.

Since ℚ_{κ} is κ-closed, there exists r ≤ p′ such that

(c) r decides Ẽ ↾ (γ × γ), and hence r also decides Ã ∩ γ;

(d) there exists δ ≥ γ such that t_{α}^{r} is a <κ-closed normal (δ + 1, κ^{+})-tree for each α < γ; and

(e) if α < β < γ and r ⊩ α ∈ Ã and α Ẽ β, then there exists τ < γ and an isomorphism f_{αβ} : t_{α}^{r} ↾ (τ + 1) → t_{β}^{r} ↾ (τ + 1) such that r ⊩ f̃_{αβ} = f_{αβ}.

CHANGING THE HEIGHTS OF AUTOMORPHISM TOWERS 21

By Lemma 3.6, if α < β < γ and r ⊩ α ∈ Ã and α Ẽ β, then there exists an isomorphism g_{αβ} : t_{α}^{r} → t_{β}^{r} such that f_{αβ} ⊂ g_{αβ}. Let g_{αβ} = ∅ for all other pairs α < β < κ^{+}. Then ⟨r, ⟨g_{αβ} | α < β < κ^{+}⟩⟩ ∈ ℝ is a strengthening of ⟨p, q̃⟩.

Thus the forcing notions ℚ_{κ}∗ℙ̃_{E} and ℝ are equivalent. It is easily checked that ℝ is κ-closed and that |ℝ| = κ^{+}. Hence ℝ preserves cofinalities and cardinalities, and does not adjoin any new κ-sequences of ordinals. It follows that no new κ-sequences of ordinals are adjoined if we force with ℙ_{E} over M[G].

Now suppose that for some μ < κ^{+}, there exists a nonidentity automorphism φ of T_{μ} in M[G][H]. Let φ̃ be an ℝ-name for φ. Then there exists a condition ⟨p, q̃⟩ ∈ ℝ and an element a ∈ t_{μ}^{p} such that

⟨p, q̃⟩ ⊩ φ̃: T̃_{μ} → T̃_{μ} is an automorphism such that φ̃(a) ≠ a.

Since ℝ is κ-closed, we can inductively define a descending sequence of conditions ⟨p_{ξ}, q̃_{ξ} | ξ < κ⟩ such that

(i) ⟨p_{0}, q̃_{0}⟩ = ⟨p, q̃⟩; (ii) t_{μ}^{p_{ξ+1}} is a proper end-extension of t_{μ}^{p_{ξ}}; and (iii) ⟨p_{ξ+1}, q̃_{ξ+1}⟩ decides φ̃ ↾ t_{μ}^{p_{ξ}}. Let t_{μ} = ⋃_{ξ<κ}t_{μ}^{p_{ξ}}; and let ψ : t_{μ} → t_{μ} be the nonidentity automorphism such that for each ξ < κ, ⟨p_{ξ+1}, q̃_{ξ+1}⟩ ⊩ φ̃ ↾ t_{μ}^{p_{ξ}} ⊂ ψ. Note that t_{μ} is a <κ-closed normal (η, κ^{+})-tree for some η such that cf(η) = κ. Arguing as in the proof of Lemma 3.8, we see that there exists a <κ-closed normal (η + 1, κ^{+})-tree t_{μ}^{+} ⊃ t_{μ} such that ψ cannot be extended to an automorphism of t_{μ}^{+}. But then the following claim yields a contradiction.

Claim 3.14. There exists a condition ⟨p_{κ}, q̃_{κ}⟩ ∈ ℝ such that

(1) ⟨p_{ξ}, q̃_{ξ}⟩ ≤ ⟨p_{κ}, q̃_{κ}⟩ for all ξ < κ; and

(2) t_{μ}^{+} ⋖ t_{μ}^{p_{κ}}.

Proof of Claim 3.14. For each α < κ^{+}, let t_{α} = ⋃_{ξ<κ}t_{α}^{p_{ξ}}. In order to construct a suitable condition ⟨p_{κ}, q̃_{κ}⟩ ∈ ℝ, we must be able to simultaneously solve the following extension problems. For various pairs of ordinals α < β < κ^{+}, we are given an isomorphism f_{αβ} : t_{α} → t_{β}; and we must find suitable extensions t_{α}^{p_{κ}} and t_{β}^{p_{κ}} of t_{α}, t_{β} such that f_{αβ} extends to an isomorphism of t_{α}^{p_{κ}} onto t_{β}^{p_{κ}}. Of

22 JOEL DAVID HAMKINS AND SIMON THOMAS

course, the most difficult cases are when either α = μ or β = μ; for then we have the additional requirement that t_{μ}^{+} ⋖ t_{μ}^{p_{κ}}. However, for each such pair of ordinals α < β < κ^{+}, there exists ξ < κ such that p_{ξ} ⊩ α ∈ Ã. Consequently f_{αβ} is the only isomorphism which needs to be considered when extending t_{β} to t_{β}^{p_{κ}}; and so there are no conflicts.

A similar argument shows that if α < β < κ^{+} and α, β are not E-equivalent, then T_{α} and T_{β} remain nonisomorphic in M[G][H].

Finally we will use a reverse Easton iteration to complete the proof of Theorem 3.1. (Clear accounts of reverse Easton forcing can be found in Baumgartner [1] and Menas [7].) Let V_{0} be a transitive model of ZF C + GCH. We define a sequence of posets ⟨ℙ_{α} | α ∈ On⟩ inductively as follows. Case 1. If α = 0, then ℙ_{0} is the trivial poset such that |ℙ_{0}| = 1. Case 2. If α is a limit ordinal which is not inaccessible, then ℙ_{α} is the inverse limit of ⟨ℙ_{β} | β < α⟩. Case 3. If α is inaccessible, then ℙ_{α} is the direct limit of ⟨ℙ_{β} | β < α⟩. Case 4. Finally suppose that α = γ + 1. If γ = κ ≥ ω is a regular cardinal, then ℙ_{α} = ℙ_{κ} ∗ ℚ̃_{κ}, where ℚ̃_{κ} ∈ V_{0}^{ℙ_{κ}} is the notion of forcing introduced in Definition 3.7. Otherwise, ℙ_{α} = ℙ_{γ} ∗ ℙ_{0}.

Let ℙ_{∞} be the direct limit of ⟨ℙ_{α} | α ∈ On⟩. For each α ∈ On, let ℙ_{α∞} be the canonically chosen class in V_{0}^{ℙ_{α}} such that ℙ_{∞} ≃ ℙ_{α} ∗ℙ_{α∞}. Let the class G ⊆ ℙ_{∞} be V_{0}-generic; and for each α ∈ On, let G_{α} = G ∩ ℙ_{α}. Let V = V_{0}[G] = ⋃_{α∈On}V_{0}[G_{α}]. Then a routine argument yields the following result.

Lemma 3.15. (a) ℙ_{∞} preserves cofinalities and cardinalities.

(b) V is a model of ZF C + GCH.

□

Let κ ≥ ω be any regular cardinal; and let {T_{α} | α < κ^{+}} ∈ V_{0}[G_{κ+1}] be the set of trees which is adjoined by ℚ_{κ} at the κ^{th} stage of the iteration. Since ℙ_{κ+1∞} is κ^{+}-closed, it follows that {T_{α} | α < κ^{+}} remains a set of pairwise nonisomorphic rigid trees in V. Now let E ∈ V be any equivalence relation on κ^{+}, and let ℙ_{E} be the corresponding notion of forcing, which was introduced in Definition 3.9. Again using the fact that ℙ_{κ+1∞} is κ^{+}-closed, we see that E, ℙ_{E} ∈ V_{0}[G_{κ+1}]. We have already shown that ℙ_{E} has the appropriate properties in V_{0}[G_{κ+1}]. Thus it only remains to prove that these properties are preserved in V.

Lemma 3.16. In V, ℙ_{E} preserves cofinalities and cardinalities, and does not adjoin any new κ-sequences of ordinals. The following statements hold in V^{ℙ_{E}}.

(a) T_{α} is rigid for each α < κ^{+}.

(b) If α < β < κ^{+}, then T_{α} ≃ T_{β} iff α E β.

Proof. Since |ℙ_{E}| = κ^{+}, ℙ_{E} preserves cofinalities and cardinalities greater than κ^{+}. The remaining parts of the lemma correspond to combinatorial properties of ℙ_{E} which are preserved under κ^{+}-closed forcing. For example, suppose that p ∈ ℙ_{E} satisfies

p ⊩ f̃: T_{α} → T_{α} is an automorphism.

We can assume that f̃ is a nice ℙ_{E}-name; ie. that f̃ = ⋃{{⟨s, t⟩}×A_{s,t} | s, t ∈ T_{α}}, where each A_{s,t} is an antichain of ℙ_{E}. Then f̃ ∈ V_{0}[G_{κ+1}], and so there exists q ≤ p such that

q ⊩ f̃(t) = t for all t ∈ T_{α}.

Hence T_{α} is rigid in V^{ℙ_{E}}.

This completes the proof of Theorem 3.1.

References

[1] J. E. Baumgartner, Iterated forcing, in Surveys in Set Theory (A. R. D. Mathias, ed.), Cambridge University Press, 1983, pp. 1–59.

[2] E. Fried and J. Kollár, Automorphism groups of fields, in Universal Algebra (E. T. Schmidt et al., eds.), Coloq. Math. Soc. Janos Boyali, vol 24, 1981, pp. 293–304.

[3] W. Hodges, Model theory, Encyclopedia of Mathematics and its Applications 42, Cambridge University Press, 1993.

[4] J. A. Hulse, Automorphism towers of polycyclic groups, J. Algebra 16 (1970), 347–398.

[5] T. Jech, Automorphisms of ω_{1}-trees, Trans. Amer. Math. Soc. 173 (1972), 57–70.

[6] T. Jech, Set Theory, Academic Press, New York, 1978.

[7] T. K. Menas, Consistency results concerning supercompactness, Trans. Amer. Math. Soc. 223 (1976), 61–91.

[8] P. M. Neumann, On the structure of standard wreath products of groups, Math. Z. 84 (1964), 343–373.

[9] S. Thomas, The automorphism tower problem, Proc. Amer. Math. Soc. 95 (1985), 166–168.

[10] S. Thomas, The automorphism tower problem II , to appear in Israel J. Math.

[11] H. Wielandt, Eine Verallgemeinerung der invarianten Untergruppen, Math. Z. 45 (1939), 209–244.

Mathematics Department, College of Staten Island, City University of New York, Staten Island, New York 10314

Mathematics Department, Rutgers University, New Brunswick, New Jersey 08903