The existence of large ω_{1}-homogeneous but not ω-homogeneous permutation groups is

consistent with ZFC + GCH

S. Shelah ^{∗}

Institute of Mathematics Hebrew University, Jerusalem

L. Soukup ^{†}

Mathematical Institute of the Hungarian Academy of Sciences

March 27, 1996

Abstract

Denote by Perm(λ) the group of all permutations of a cardinal λ. A subgroup G of Perm(λ) is called κ-homogeneous iff for all X, Y ∈ [λ]^{κ} there is a g ∈ G with g′′X = Y. We show that if either (i) ♢^{+} holds and we add ω_{1} Cohen reals to the ground model, or (ii) we add 2^{ω_{1}} Cohen reals to the ground model, then in the generic extension for each λ ≥ ω_{2} there is an ω_{1}-homogeneous subgroup of Perm(λ) which is not ω-homogeneous.

∗The first author was supported by the United States Israel Binational Science Foundation, Publication number 389

†The second author was supported by the Hungarian National Foundation for Scientific Research grant no. l805

1 Introduction

Denote by Perm(λ) the group of all permutations of a cardinal λ. The subgroups of Perm(λ) are called permutation groups on λ. We say that a permutation group G on λ is κ-homogeneous iff for all X, Y ∈ [λ]^{κ} with |λ \ X| = |λ \ Y | = λ there is a g ∈ G with g′′X = Y. Given cardinals λ, κ and μ write H(λ, κ, μ) to mean that every κ-homogeneous permutation group on λ is μ-homogeneous, as well. P. M. Neumann has raised the problem if λ > κ > μ implies H(λ, κ, μ). He proved [3] that H(λ, κ, μ) holds for λ > κ ≥ ω and μ < ω. P. Nyikos [4] and independently S. Shelah and S. Thomas [5] showed that ¬H(2^{ω}, ω_{1}, ω) is consistent with Martin’s Axiom. Recently A. Hajnal [1] proved that ^{ω_{1}} implies ¬H(ω_{2}, ω_{1}, ω). The aim of this paper is to construct models of ZFC in which ¬H(λ, ω_{1}, ω) for each λ ≥ ω_{2}.

We will use the standard notation of set theory, see [2]. For sets A and B let us denote by Fin(A, B) the poset whose underlying set consists of all functions mapping a finite subset of A into B and whose ordering is the inclusion.

The ♢^{+} principle asserts that there is a sequence ⟨S_{α} : α < ω_{1}⟩ of countable sets such that for each X ⊂ ω_{1} we have a closed unbounded C ⊂ ω_{1} with X ∩ ν ∈ S_{ν} and C ∩ ν ∈ S_{ν} for each ν ∈ C.

Theorem 1.1 Assume that either (i) ♢^{+} holds and P = Fin(ω_{1}, 2) , or (ii) P = Fin(2^{ω_{1}}, 2). Then

V^{P} ⊧ “¬H(λ, ω_{1}, ω) for each λ ≥ ω_{1}.”

The proof of this theorem is based on the following observation. To formulate it we need some definitions. Let G be a permutation group on λ. Given X, Y ⊂ λ we say that X is (G, Y)-large iff for each n ∈ ω and g_{0}, …, g_{n−1} ∈ G we have |X \ ⋃_{i<n} g′′_{i}Y | = |X|. G is called κ-inhomogeneous iff there are

X, Y ∈ [λ]^{κ} such that X is (G, Y)-large.

Observation 1.2 Assume that V_{0} ⊂ V_{1} are ZFC models and λ ≥ ω_{2} is a cardinal in V_{1}. If

(a) V_{0} ⊧“|X| = ω_{1}” iff V_{1} ⊧“|X| = ω_{1}” for each X ∈ V_{0}.

(b) ∀X ∈ [λ]^{ω_{1}} ∩ V_{1} ∃Y ∈ [λ]^{ω_{1}} ∩ V_{0} X ⊂ Y, (c) V_{1} ⊧ “There is an ω_{1}-homogeneous, but ω-inhomogeneous

permutation group G on ω_{1} containing Perm^{V_{0}}(ω_{1}) .”

then V_{1} ⊧¬H(λ, ω_{1}, ω).

Proof of the observation: We will work in V_{1}. For each g ∈ G define g^{∗} ∈ Perm(λ) by taking g^{∗}⌈ω_{1} = g and g^{∗}(α) = α for α ∈ λ \ ω_{1}. Let G^{∗} be the subgroup of Perm(λ) generated by the set {g^{∗} : g ∈ G} ∪ Perm^{V_{0}}(λ). We claim that G^{∗} witnesses ¬H(λ, ω_{1}, ω). First we show that G^{∗} is not ωhomogeneous. Pick X, Y ∈ [ω_{1}]^{ω} such that X is (G, Y)-large. We show that X is (G^{∗}, Y)-large. Assume on the contrary that X ⊂ ⋃_{i<n} g′′_{i}Y, where

g_{i} ∈ G^{∗}. Then there must be an i < n such that X ∩ g′′_{i}Y is (G, Y)-large. So we can assume that n = 1, i.e, X ⊂ g′′Y for some g ∈ G^{∗}. Write g = h_{0} ∘ (g_{0})^{∗} ∘ h_{1} ∘ … ∘ (g_{m−1})^{∗} ∘ h_{m}, where h_{i} ∈ Perm^{V_{0}}(λ) and g_{i} ∈ G. We can assume that X and Y were chosen such that m is minimal. Define the function d : Y → m by the equation

d(y) = max{j : (h_{j} ∘ (g_{j})^{∗} ∘ … ∘ h_{m})(y) ∈ ω_{1}}.

Take Y_{j} = d^{−1}{j} for j ≤ m. For y ∈ Y_{j} we have (h_{j} ∘ (g_{j})^{∗} ∘ … ∘ h_{m})(y) = (h_{j} ∘ h_{j+1} ∘ … ∘ h_{m})(y). Since Perm^{V_{0}}(ω_{1}) ⊂ G, for each j ≤ m there is an f_{j} ∈ G such that f_{j}(y) = (h_{j} ∘ h_{j+1} ∘ … ∘ h_{m})(y) for each y ∈ Y_{j}. Putting W_{j} = f′′_{j}Y_{j} and Z_{j} = g′′_{j−1}W_{j} = (g_{j−1}^{∗})′′W_{j} this means that

X ⊂ ⋃_{j≤m}(h_{0} ∘ (g_{0})^{∗} … ∘ h_{j−1})′′Z_{j}.

But Z_{j} ⊂ (g_{j−1} ∘ f_{j})′′Y, g_{j−1} ∘ f_{j} ∈ G, so there is an j ≤ m such that taking

X^{∗} = X ∩ (h_{0} ∘ (g_{0})^{∗} … ∘ h_{j−1})′′Z_{j}

we have that X^{∗} is (G, Z_{j})-large. But X^{∗} ⊂ (h_{0} ∘ (g_{0})^{∗} … ∘ h_{j−1})′′Z_{j} and j−1 < m, which contradicts the minimality of m. So G^{∗} is ω-inhomogeneous.

If X, Y ∈ [λ]^{ω_{1}} first pick X_{0}, Y_{0} ∈ [λ]^{ω_{1}} ∩ V_{0} with X ⊂ X_{0} and Y ⊂ Y_{0} such that |X_{0} \X| = |Y_{0} \Y | = ω_{1}. Fix f, h ∈ Perm^{V_{0}}(λ) with f′′X_{0} = ω_{1} and h′′Y_{0} = ω_{1}. Since G is ω_{1}-homogeneous, we have a g ∈ G with g′′(f′′X) = h′′Y. Then (h^{−1} ∘ g ∘ f)′′X = Y and h^{−1} ∘ g ∘ f ∈ G^{∗}.

By this observation the following theorem yields theorem 1.1.

Theorem 1.3 If either (i) ♢^{+} holds and P = Fin(ω_{1}, 2), or (ii) P = Fin(2^{ω_{1}}, 2) then V^{P} ⊧ “there is an ω_{1}-homogeneous, but ω-inhomogeneous permutation group G on ω_{1} with G ⊃ Perm^{V} (ω_{1})”.

2 Proof of theorem 1.3

Since the proof of theorem 1.3 is quite long and technical, first we sketch the main ideas.

In both cases we will define an iterated forcing system with finite support

⟨P_{ν} : −1 ≤ ν ≤ κ, Q_{ν} : −1 ≤ ν < κ⟩

and an increasing sequence of permutation groups ⟨G_{ν} : ν < κ⟩, G_{ν} ≺ Perm^{V^{Pν}} (ω_{1}), simultaneously, where κ = ω_{1} in case (i) and κ = 2^{ω_{1}} in case (ii).

Take G_{0} = Perm^{V} (ω_{1}) and P_{0} = Q_{−1} = Fin(ω, 2). Denote by r the Cohen real given by the V -generic filter over P_{0}. By standard density arguments it is easy to see that ω is (G_{0}, r)-large. We try to carry out the inductive construction of the sequence ⟨G_{ν} : ν < κ⟩ in such a way that

(a) For each ν < κ we pick X_{ν}, Y_{ν} ∈ ([ω_{1}]^{ω_{1}})^{V^{Pν}}, then we construct a permutation g_{ν} ∈ V^{P_{ν}+1} with g′′_{ν}X_{ν} = Y_{ν} and take G_{ν+1} as the subgroup of Perm^{V^{P_{ν+1}}}(ω_{1}) generated by G_{ν} ∪ {g_{ν}},

(b) ω is (G_{ν}, r)-large,

and we hope that the sequence ⟨G_{ν} : ν < κ⟩ gives us a required permutation group. In case (ii) we use a bookkeeping function to ensure that every pair X, Y ∈ ([ω_{1}]^{ω_{1}})^{V^{P_{2^{ω_{1}}}}} with |ω_{1} \ X| = |ω_{1} \ Y | = ω_{1} will be chosen as X_{ν}, Y_{ν} in some step. Then G = ⋃_{ν<2^{ω_{1}}} G_{ν} will be ω_{1}-homogeneous. So the question is whether we can preserve (b) during the induction. In case (i) we can pick only ω_{1}-many pairs ⟨X, Y ⟩, so we can’t expect that G′ = ⋃_{ν<ω_{1}} G_{ν} is ω_{1}- homogeneous. But in this case we will use ♢^{+} principle to pick the sets X_{ν}, Y_{ν} for ν < ω_{1} in such a way that if we consider the elements of G′ as the family of countable approximations of our required group, and we take

G = {g ∈ Perm^{V^{Pω_{1}}} (ω_{1}) : ∀ν < ω_{1} ∃g′ ∈ G′ g⌈ν = g′⌈ν},

then G will be ω_{1}-homogeneous. Obviously, ω is (G, r)-large provided ω is (G′, r)-large.

So the question is whether one can preserve (b). Unfortunately we can’t prove a preservation theorem for (G, r)-largeness of ω, but we will introduce the notion of goodness of a pair (G, r) which can be preserved during a suitable iteration and it will clear from the definition that the goodness of (G, r) implies that ω is (G, r)-large.

After this introduction let us see the details.

For g ∈ Perm(ω_{1}) and r ⊂ ω_{1} we will write, by an abuse of notation, g(r) for g′′r. Given sets X and Y let us denote by Bij_{p}(X, Y) the set of all bijections between subsets of X and Y.

If a_{0}, a_{1}, b_{0} and b_{1} are subsets of ω_{1} with a_{0} ∩ a_{1} = b_{0} ∩ b_{1} = ∅ take

Q_{a_{0},a_{1},b_{0},b_{1}} = {g_{0} ∪ g_{1} : g_{i} ∈ Bij_{p}(a_{i}, b_{i}) and |g_{i}| < ω for i ∈ 2}

and Q_{a_{0},a_{1},b_{0},b_{1}} = ⟨Q_{a_{0},a_{1},b_{0},b_{1}}, ⊇⟩.

Definition 2.1 Let F ⊂ Bij_{p}(ω_{1}, ω_{1}) and r ⊂ ω be given.

1. A sequence X = ⟨x_{ν} : ν < μ⟩ ⊂ [ω_{1}]^{<ω} is called (F, r)-large iff for each n ∈ ω and h_{0}, …, h_{n−1} ∈ F there exists a ν < μ such that

x_{ν} ∩ ⋃{h_{i}(r) : i < n} = ∅.

2. We say that the pair (F, r) is good iff every uncountable sequence ⟨y_{ν} : ν < ω_{1}⟩ of pairwise disjoint, finite subsets of ω_{1} has a countable initial segment ⟨y_{ν} : ν < μ⟩ which is (F, r)-large.

Case (i): ♢^{+} holds and P = Fin(ω_{1}, 2).

We will define an iterated forcing system

⟨P_{ν} : −1 ≤ ν ≤ ω_{1}, Q_{ν} : −1 ≤ ν < ω_{1}⟩

with finite support, such that P_{0} = Q_{−1} = Fin(ω, 2) and for each ν < ω_{1} either Q_{ν} = Fin(ω, 2) or V^{P_{ν}} ⊧ “Q_{ν} = Q_{A_{0}^{ν},A_{1}^{ν},B_{0}^{ν},B_{1}^{ν}} for some infinite, countable subsets A_{0}^{ν}, A_{1}^{ν}, B_{0}^{ν}, B_{1}^{ν} of ω_{1}”. Since V^{P_{ν}} ⊧“the completions of Q_{ν} and Fin(ω, 2) are isomorphic”, we have V^{P} = V^{P_{ω_{1}}} , and so we may construct our desired permutation group in V^{P_{ω_{1}}}. For ν ≤ ω_{1} let G_{ν} be the P_{ν}-generic filter. Take g = ∪G_{0} : ω → 2 and r = g^{−1}{1}.

Fix a large enough regular cardinal κ and let ⟨N_{ν} : ν < ω_{1}⟩ be a sequence of countable, elementary submodels of H_{κ} = ⟨H_{κ}, ∈, ≺⟩, where H_{κ} consists of the sets whose transitive closure has cardinality < κ and ≺ is a well-ordering of H_{κ}, with the property that ⟨N_{μ} : μ < ν⟩ ∈ N_{ν} for each ν < ω_{1}. Fix a ♢^{+}-sequence S = ⟨S_{α} : α < ω_{1}⟩ ∈ N_{0}.

If ν ≤ μ < ω_{1} and G is a P_{ν}-generic filter, then take

N_{μ}[G] = {K_{G}(x) : x ∈ N_{μ}}.

A P_{ω_{1}}-name χ̃ of the characteristic function of a subset of ω_{1} is called a canonical ν-name iff ν ≤ ω_{1} and there exist maximal antichains D_{χ} ; ξ ⊂ P_{ω_{1}} and functions h_{χ} ; ξ : D_{χ} ; ξ → 2 for ξ ∈ ν such that

χ̃ = {⟨p, ˆ⟨ξ, i⟩⟩ : i = h_{χ} ; ξ(p), p ∈ D_{χ} ; ξ, ξ ∈ ν}.

χ̃ is called nice ν-name iff χ̃ is a canonical ν-name and ⋃_{ξ<ν} D_{χ} ; ξ ⊂ P_{ων}. We

will usually identify sets and their characteristic functions. To simplify our notation we will write p^{∥}—“ρ ∈ χ̃” for p^{∥}—“χ̃(ρ) = 1”.

If Ã is a nice ν-name and G is a P_{ων}-generic filter, then write

Ã[]gcal] = {ξ ∈ ν : ∃p ∈ G p^{∥}—ξ ∈ Ã}.

Given a P_{ω_{1}}-name Ã and ν < ω_{1} take

Ã⌈^{∗}ν = {⟨p, x⟩ ∈ Ã : p ∈ P_{ων}}.

A triple ⟨Ã, B̃, C⟩ is called ν-remarkable iff C ⊂ ν is a club, Ã⌈^{∗}μ and

B̃⌈^{∗}μ are nice μ-names and ⟨Ã⌈^{∗}μ, B̃⌈^{∗}μ, C ∩ μ⟩ ∈ N_{μ} for each μ ∈ C ∪ {ν}. Take

Rem(N_{ν}) = {⟨Ã, B̃, C⟩ : ⟨Ã, B̃, C⟩ is ν-remarkable} .

First we construct the family F′ of “countable approximations” of elements of our required permutation group.

By induction on ν we will define the posets Q_{ων+i} for i < ω, functions

f_{⟨_{A},_{B},C⟩} for ⟨Ã, B̃, C⟩ ∈ Rem(N_{ν}) and families F_{ν} ⊂ Bij_{p}(ω_{1}, ω_{1}) in V^{P_{ω_{1}}}

such that

(a) F_{0} = Bij_{p}(ω_{1}, ω_{1}) ∩ V,

(b) ⟨F_{μ} : μ < ν⟩ ∈ N_{ν}[G_{ων}],

(c) F_{ν} = ⋃_{μ<ν} F_{μ} ∪ {f_{⟨_{A},_{B},C⟩} : ⟨Ã, B̃, C⟩ ∈ Rem(N_{ν})},

(d) domf_{⟨_{A},_{B},C⟩} = ranf_{⟨_{A},_{B},C⟩} = γ_{⟨_{A},_{B},C⟩} for some γ_{⟨_{A},_{B},C⟩} ∈ C ∪ {ν},

(e) if ⟨Ã, B̃, C⟩ ∈ Rem(N_{ν}), μ ∈ C, then

f_{⟨_{A}⌈^{∗}μ,_{B}⌈^{∗}μ,C∩μ⟩} = f_{⟨_{A},_{B},C⟩}⌈γ_{⟨_{A}⌈^{∗}μ,_{B}⌈^{∗}μ,C∩μ⟩}.

Assume that ⟨F_{μ} : μ < ν⟩ is constructed. From now on we will work in V [G_{ων}]. Put F_{<ν} = ⋃_{μ<ν} F_{μ}. For a triple ⟨Ã, B̃, C⟩ ∈ Rem(N_{ν}) take

f_{⟨_{A},_{B},C⟩}^{∗} = ⋃_{μ∈C} f_{⟨_{A}⌈^{∗}μ,_{B}⌈^{∗}μ,C∩μ⟩}

and γ_{⟨_{A},_{B},C⟩}^{∗} = sup_{μ∈C} γ_{⟨_{A}⌈^{∗}μ,_{B}⌈^{∗}μ,C∩μ⟩}. Clearly f_{⟨_{A},_{B},C⟩}^{∗} ∈ N_{ν}[G_{ων}].

Let F_{ν}^{∗} = {f_{⟨_{A},_{B},C⟩}^{∗} : ⟨Ã, B̃, C⟩ ∈ Rem(N_{ν})}. N_{ν}[G_{ων}] ∈ N_{ν+1}[G_{ων}] im-

plies that F_{ν}^{∗} ∈ N_{ν+1}[G_{ων}] and F_{ν}^{∗} is countable in N_{ν+1}[G_{ων}]. So we can fix an enumeration F_{ν}^{∗} = {f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗} : j < ω} in N_{ν+1}[G_{ων}]. To simplify our notation we will write f_{ν,j}^{∗} = f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗}.

We define the posets Q_{ων+j} and the functions f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} ⊃ f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗} by

induction on j. Assume that we have done it for i < j. Take

F_{ν}^{j} = F_{<ν} ∪ F_{ν}^{∗} ∪ {f_{⟨_{A_{i}^{ν}},_{B_{i}^{ν}},C_{i}^{ν}⟩} : i < j}.

Put I_{ν,j} = [γ_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗}, ν). Take ξ = ων +j. Let A_{0}^{ξ} = I_{ν,j} ∩Ã_{j}^{ν}[G_{ων}], A_{1}^{ξ} =

I_{ν,j} \ Ã_{j}^{ν}[G_{ων}], B_{0}^{ξ} = I_{ν,j} ∩ B̃_{j}^{ν}[G_{ων}], B_{1}^{ξ} = I_{ν,j} \ B̃_{j}^{ν}[G_{ων}] and Q^{ξ} = Q_{A_{0}^{ξ},A_{1}^{ξ},B_{0}^{ξ},B_{1}^{ξ}}.

If the sets A_{0}^{ξ}, A_{1}^{ξ}, B_{0}^{ξ} and B_{1}^{ξ} are all (F_{ν}^{j}, r)-large, then put Q_{ξ} = Q^{ξ}. Let G^{ξ} be the Q_{ξ}-generic filter over V^{P_{ξ}}. Take f′_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} = ∪G^{ξ} and let

f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} = f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗} ∪ f′_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} and so γ_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} = ν.

Otherwise, if at least one of the sets A_{0}^{ξ}, A_{1}^{ξ}, B_{0}^{ξ} and B_{1}^{ξ} is not (F_{ν}^{j}, r)-large,

put Q_{ων+j} = Fin(ω, 2), f′_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} = ∅ and f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} = f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}^{∗}.

The inductive construction is done.

Take F = ⋃_{ν∈ω_{1}} F_{ν}. Let F′ be the closure of F under composition and inverse image.

Lemma 2.2 (F′, r) is a good pair.

Since its proof is quite long we postpone it for a while.

Having the family F′ of countable approximations we are ready to construct G.

A pair ⟨Ã, B̃⟩ is called nice iff both Ã and B̃ are nice ω_{1}-names of uncountable, co-uncountable subset of ω_{1}. Using the ♢^{+} principle, for each nice pair ⟨Ã, B̃⟩ choose a club set C = C_{_{A},_{B}} ⊂ ω_{1} such that Ã⌈^{∗}ν and B̃⌈^{∗}ν are

nice ν-names and ⟨Ã⌈^{∗}ν, B̃⌈^{∗}ν, C ∩ ν⟩ ∈ N_{ν} for all ν ∈ C, and put

f_{_{A},_{B}} = ⋃_{ν∈C} f_{⟨_{A}⌈^{∗}ν,_{B}⌈^{∗}ν,C∩ν⟩}.

Let G be the subgroup of Perm(ω_{1}) generated by the set

{f_{_{A},_{B}} : ⟨Ã, B̃⟩ is a nice pair with domf_{_{A},_{B}} = ω_{1}} .

We claim that G satisfies the requirements of the theorem.

Since cofinal many countable initial segments of the elements of G are in F′, lemma 2.2 implies that (G, r) is a good pair. Applying this fact for ω_{1} as an uncountable sequence of pairwise disjoint finite subsets of ω_{1} we obtain that there is a countable ordinal α which is (G, r)-large. This means that G is ω-inhomogeneous.

Next we show that G is ω_{1}-homogeneous. Pick a nice pair (Ã, B̃). Let

C = C_{_{A},_{B}} and consider the function f = f_{_{A},_{B}} = ⋃_{ν∈C} f_{⟨_{A}⌈^{∗}ν,_{B}⌈^{∗}ν,C∩ν⟩}. If

dom(f) = ω_{1} then f ∈ G and f′′A = B, so we are done. Assume that dom(f) = μ < ω_{1}. Then μ ∈ C. But the pair (F′, r) is good, so there is a ν > μ, ν ∈ C, such that the sets (ν \ μ) ∩ A, (ν \ μ) \ A, (ν \ μ) ∩ B and (ν \ μ) \ B are all (F′, r)-large. So we get dom(f′_{⟨_{A}⌈^{∗}ν,_{B}⌈^{∗}ν,C∩ν⟩}) = ν \ μ. Thus

dom(f) ⊃ ν. Contradiction, G is ω_{1}-homogeneous.

Finally we present the postponed proof of lemma 2.2: Proof of lemma 2.2: To start with we introduce some notion.

A condition p ∈ P_{ω_{1}} is called determined iff for each ξ < ω_{1} if p(ξ) ≠ 1_{Q_{ξ}}, then p⌈ξ^{∥}— “Q_{ξ} = Fin(ω, 2)” or p⌈ξ^{∥}— “Q_{ξ} = Q^{ξ}” and there is a function F_{p,ξ} in the ground model such that p(ξ) = F̂_{p,ξ}. Put

Det(P_{ω_{1}}) = {p ∈ P_{ω_{1}} : p is determined}.

The proof of the following sublemma is straightforward:

Sublemma 2.2.1 Det(P_{ω_{1}}) is dense in P_{ω_{1}}.

Consider a condition p ∈ Det(P_{ω_{1}}). For each ⟨Ã_{j}^{ν}, B̃_{j}^{ν}, C_{j}^{ν}⟩ ∈ Rem(N_{ν}) take

\begin{aligned}f_{ν,j}^{[p]} & = ⋃ \{p(ωμ + i) : & p⌈(ωμ + i)^{∥}—“Q_{ωμ+i} = Q^{ωμ+i} ”, μ ∈ C_{j}^{ν} ∪ \{ν\} and \\ & & ⟨Ã_{i}^{μ}, B̃_{i}^{μ}, C_{i}^{μ}⟩ = ⟨Ã_{j}^{ν}⌈^{∗}μ, B̃_{j}^{ν}⌈^{∗}μ, C_{j}^{ν} ∩ μ⟩\} . \end{aligned}

The finite function f_{ν,j}^{[p]} gathers all the information contained in p about

f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩}.

An F-term t is a sequence ⟨h_{0}, h_{1}, …, h_{n−1}⟩ where h_{i} = f_{i} or h_{i} = f_{i}^{−1} for some f_{i} ∈ F. We also use t to denote the function h_{0} ∘ ⋯ ∘ h_{n−1}. We say that t′ is a subterm of t if t′ = ⟨h_{i_{0}}, …, h_{i_{l}}⟩, where 0 ≤ i_{0} < … < i_{l} ≤ n − 1.

Given an F-term t = ⟨h_{0}, h_{1}, …, h_{n−1}⟩ and a condition p ∈ Det(P_{ω_{1}}) take t^{[p]} = h′_{0} ∘ ⋯ ∘ h′_{n−1} where

h′_{i} = \{ \begin{matrix}h_{i} & if h_{i} ∈ F_{0} (= Bij_{p}(ω_{1}, ω_{1}) ∩ V), \\ f_{ν,j}^{[p]} & if h_{i} = f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩} for some ⟨Ã_{j}^{ν}, B̃_{j}^{ν}, C_{j}^{ν}⟩ ∈ Rem(N_{ν}), \\ (f_{ν,j}^{[p]})^{−1} & if h_{i} = (f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩})^{−1} for some ⟨Ã_{j}^{ν}, B̃_{j}^{ν}, C_{j}^{ν}⟩ ∈ Rem(N_{ν}). \end{matrix}

If T is a set of F-terms let T^{[p]} = {t^{[p]} : t ∈ T }.

Given p ∈ Det(P_{ω_{1}}) , ξ ∈ ω_{1} and a function F ∈ Bij_{p}(ω_{1}, ω_{1}), if p⌈ξ^{∥}—“p(ξ)∪ F ∈ Q_{ξ}” then write p ∧_{ξ} F for the condition q ∈ Det(P_{ω_{1}}) defined by the formula

q(ζ) = \{ \begin{matrix}p(ζ) ∪ F & if ζ = ξ, \\ p(ζ) & otherwise. \end{matrix}

If p⌈ξ ∈ G_{ξ}, then let t^{[p]}[G_{ξ}] = ⋃{t^{[p∧q]} : q ∈ G_{ξ}} and T^{[p]}[G_{ξ}] = {t^{[p]}[G_{ξ}] : t ∈ T }.

If a ⊂ ω_{1} then, by an abuse of notation, we will write t(a) for t′′a and

T (a) for ⋃_{t∈T} t(a).

Assume now on the contrary that p′^{∥}— “Z = {z̃_{α} : α < ω_{1}} is a sequence of pairwise disjoint finite subsets of

ω_{1}, {Ũ_{β} : β < ω_{1}} is a sequence of finite sets of F-terms such that

z̃_{α} ∩ Ũ_{β}(r) ≠ ∅ for each α < β < ω_{1}”.

For each α < ω_{1} choose a condition p_{α} ∈ Det(P_{ω_{1}}), a set y_{α} ∈ [ω_{1}]^{<ω} and a finite set of F-terms T_{α} such that p_{α}^{∥}—“z̃_{α} = ŷ_{α} and Ũ_{α} = T̂_{α}”. We can assume that every T_{α} is closed under subterms.

Sublemma 2.2.2 There are α < β < ω_{1} and a condition p ∈ Det(P_{ω_{1}}) such that p ≤ p_{α}, p_{β} and p^{∥}—“T_{β}^{[p]}(r) ∩ y_{α} = ∅′′.

Proof: Without loss of generality we can assume that {supp(p_{α}) : α < ω_{1}} forms a Δ-system with kernel d, −1 ∈ d and p_{α}⌈d = q for each α < ω_{1}. Then q(−1) ∈ Fin(ω, 2). Take D = dom(q(−1)).

Consider a t ∈ T_{ω}. If α_{0} < α_{1} < ω then u = (t^{[p_{α_{0}}∪p_{α_{1}}∪p_{ω}]})^{−1} is a 1–1 function, and so u(y_{α_{0}}) ∩ u(y_{α_{1}}) = ∅. Thus

|{α < ω : (t^{[p_{α}∪p_{ω}]})^{−1}(y_{α}) ∩ D ≠ ∅}| ≤ |D|.

But T_{ω} is finite, so there is an α < ω such that T_{ω}^{[p_{α}∪p_{ω}]}(D) ∩ y_{α} = ∅. Take E = (T_{ω}^{[p_{α}∪p_{ω}]})^{−1}y_{α}. Then D ∩E = ∅. Put p = p_{α} ∧p_{ω} ∧q′, where q′ is defined by the equations supp(q′) = {−1} and g′(−1) = {⟨m, 0⟩ : m ∈ E}. Then p is determined and p^{∥}—“T_{ω}^{[p]}(r) ∩ y_{α} = ∅”, because (T_{ω}^{[p]})^{−1}(y_{α}) ⊂ E and p^{∥}— “r ∩ E = ∅”.

Take T = (T_{β})^{−1} =^{def} {t^{−1} : t ∈ T_{β}} and y = y_{α}. Then

p^{∥}—“T^{[p]}(y) ∩ r = ∅but T (y) ∩ r ≠ ∅”.

We will find p^{∗} ≤ p such that p^{∗}^{∥}— “T^{[p^{∗}]}(y) ∩ r = ∅ and p^{∗} “fully decides” T (y), i.e., p^{∗}^{∥}— “T (y) = T^{[p^{∗}]}(y)” contradicting to p^{∥}— “T (y) ∩ r ≠ ∅”.

Definition 2.3 Let p^{∗} ∈ Det(P_{ω_{1}}), s be an F-term, S be a set of F-terms, ρ ∈ ω_{1}, z ⊂ ω_{1}, ξ ∈ ω_{1}, s = ⟨h_{0}, h_{1}, …, h_{n−1}⟩.

1. We say that p^{∗} fully decides s(ρ) iff there is a sequence ⟨ρ_{0}, …, ρ_{m}⟩ such that ρ_{0} = ρ and p^{∗}^{∥}—“h_{i}(ρ̂_{i}) = ρ̂_{i+1}” for i < m and either m = n or m < n and p^{∗}^{∥}—“ρ̂_{m} ∉ dom(h_{m})”.

2. p^{∗} fully decides S(z) iff it fully decides s(ρ) whenever s ∈ S and ρ ∈ z.

3. Take dcd(p^{∗}, S, z) = {⟨s, ρ⟩ ∈ S × z : p^{∗} fully decides s(ρ)}.

4. If p^{∗}⌈ξ ∈ G_{ξ} then put dcd(p^{∗}, S, z)[G_{ξ}] = ⋃{dcd(p^{∗} ∧ q, S, z) : q ∈ G_{ξ}}.

If q ∈ Det(P_{ω_{1}}), y ∈ [ω_{1}]^{<ω} and S is a set of F-terms we will define the set of undecided evaluations as follows: let Und(q, S, y) be the set of triples ⟨x, ⟨ν, j⟩ , e⟩ for which there exist s ∈ S, s = ⟨h_{0}, …, h_{l}⟩, and η ∈ y satisfying (a)–(d) below:

(a) x ∈ ω_{1}, e ∈ {−1, +1} and h_{l} = (f_{⟨_{A_{j}^{ν}},_{B_{j}^{ν}},C_{j}^{ν}⟩})^{e},

(b) taking u = ⟨h_{0}, …, h_{l−1}⟩ we have u^{[q]}(η) = x,

(c) x ∉ domf_{⟨ν,j⟩}^{[q]} if e = 1,

(d) x ∉ ranf_{⟨ν,j⟩}^{[q]} if e = −1.

For ⟨μ, i⟩ ∈ ω_{1} × ω define Und^{+}(q, T, y, μ, i), the set of undecided evaluations which will be decided in step μ, as follows: it contains a triple ⟨x, ⟨ν, j⟩, e⟩ ∈ Und(q, T, y) iff (A)–(C) below are satisfied:

(A) ⟨Ã_{i}^{μ}, B̃_{i}^{μ}, C_{i}^{μ}⟩ = ⟨Ã_{j}^{ν}⌈^{∗}μ, B̃_{j}^{ν}⌈^{∗}μ, C_{j}^{ν} ∩ μ⟩,

(B) q^{∥}—“x ∈ domf′_{⟨_{A_{i}^{μ}},_{B_{i}^{μ}},C_{i}^{μ}⟩}” provided e = 1,

(C) q^{∥}—“x ∈ ranf′_{⟨_{A_{i}^{μ}},_{B_{i}^{μ}},C_{i}^{μ}⟩}” provided e = −1.

Let Und^{−}(q, T, y, μ, i), the family of undecided evaluations which remain undecided in step μ, be the set of triples ⟨x, ⟨ν, j⟩, e⟩ ∈ Und(q, T, y, μ, i) with

⟨Ã_{i}^{μ}, B̃_{i}^{μ}, C_{i}^{μ}⟩ ≠ ⟨Ã_{j}^{ν}⌈^{∗}μ, B̃_{j}^{ν}⌈^{∗}μ, C_{j}^{ν} ∩ μ⟩ or with q^{∥}—“f′_{⟨_{A_{i}^{μ}},_{B_{i}^{μ}},C_{i}^{μ}⟩} = ∅”.

If q⌈ξ ∈ G_{ξ}, ξ ≤ ωμ + i, then take

Und(q, T, y)[G_{ξ}] = ⋃{Und(q ∧ q′, T, y) : q′ ∈ G_{ξ}},
Und^{+}(q, T, y, μ, i)[G_{ξ}] = ⋃{Und^{+}(q ∧ q′, T, y, μ, i) : q′ ∈ G_{ξ}}

and

Und^{−}(q, T, y, μ, i)[G_{ξ}] = ⋃{Und^{−}(q ∧ q′, T, y, μ, i) : q′ ∈ G_{ξ}}.

Sublemma 2.3.1 There is a condition p^{∗} ≤ p which fully decides T (y) and p^{∗}^{∥}—“T^{[p^{∗}]}(y) ∩ r = ∅”.

Proof: We will define a finite, decreasing sequence of determined conditions, p_{0}, p_{1}, …, p_{l^{∗}} = p^{∗} satisfying (I) and (II) below for each l ≤ l^{∗}:

(I) p_{l}^{∥}—“T^{[p_{l}]}(y) ∩ r = ∅”, (II) |dcd(p_{l−1}, T, y)| < |dcd(p_{l}, T, y)|.

Put p_{0} = p. Assume that p_{l} is constructed.

Choose the minimal ⟨μ, i⟩ in the lexicographical order of ω_{1} × ω with the property (∗) below:

(∗) There is a p′ ∈ P_{ωμ+i}, p′ ≤ p_{l}⌈(ωμ + i), such that taking p′_{l} = p′ ∧ p_{l} we have Und^{+}(p′_{l}, T, y, μ, i) ≠ ∅.

To simplify our notation take ξ = ωμ + i. Let G_{l} be a P_{ξ}-generic filter with p′ ∈ G_{l}. By the minimality of ⟨μ, i⟩ we have T^{[p_{l}]}[G_{l}](y) = T^{[p_{l}]}(y) and so

(†)  V [G_{l}] ⊧“T^{[p_{l}]}[G_{l}](y) ∩ r = ∅”.

Clearly

Und(p′_{l}, T, y)[G_{l}] = Und^{+}(p′_{l}, T, y, μ, i)[G_{l}] ∪ Und^{−}(p′_{l}, T, y, μ, i)[G_{l}].

The condition p_{l+1} will be constructed by a finite induction. Working in V [G_{l}] we will define a natural number o_{l} and determined conditions p_{l,0}, p_{l,1}, …, p_{l,o_{l}} such that for all k ≤ o_{l} (i)–(vi) below are satisfied:

(i) p_{l,k}⌈ξ ∈ G_{l},

(ii) p_{l,k} ≤ p_{l,k−1}

(iii) p_{l,k}⌈[ξ + 1, ω_{1}) = p_{l}⌈[ξ + 1, ω_{1}),

(iv) V [G_{l}] ⊧“T^{[p_{l,k}]}[G_{l}](y) ∩ r = ∅”,

(v) |dcd(p_{l,k−1}, T, y)[G_{l}]| < |dcd(p_{l,k}, T, y)[G_{l}]|,

(vi) Und^{+}(p_{l,o_{l}}, T, y, μ, i)[G_{l}] = ∅.

Let p_{l,0} = p_{l}. Then (iv) holds by (†). Assume that p_{l,k} is chosen. If Und^{+}(p_{l,k}, T, y, μ, i)[G_{l}] = ∅ then put o_{l} = k. Let us remark that (v) and |dcd(p_{l,k+1}, T, y)[G_{l}]| ≤ |T × y| imply that o_{l} ≤ |T × y|. Suppose now that (vi) fails for k and pick a witness ⟨x_{k}, ⟨ν_{k}, j_{k}⟩ , e_{k}⟩ ∈ Und^{+}(p_{l,k}, T, y, μ, i)[G_{l}]. Let T_{k} = T^{[p_{l,k}]}[G_{l}], choose a

z_{k} ∈ \{ \begin{matrix}Ã_{i}^{μ}[G_{l}] \ (T_{k}^{−1}(r ∪ y) ∪ T^{k}(r ∪ y)) & if e_{k} = 1 \\ B̃_{i}^{μ}[G_{l}] \ (T_{k}^{−1}(r ∪ y) ∪ T^{k}(r ∪ y)) & if e_{k} = −1 \end{matrix}

and take

F_{k} = \{ \begin{matrix}\{⟨x_{k}, z_{k}⟩\} & if e_{k} = 1 \\ \{⟨z_{k}, x_{k}⟩\} & if e_{k} = −1. \end{matrix}

Let us remark that z_{k} is chosen from a non-empty set, because both Ã_{i}^{μ}[G_{l}] and B̃_{i}^{μ}[G_{l}] are (F_{μ}^{i}, r)-large.

Choose p_{l,k}^{∗} ∈ G_{l} such that

p_{l,k}^{∗}^{∥}—“p_{l,k} ∧_{ξ} F_{k} ∈ P_{ω_{1}} and ⟨x_{k}, ⟨ν_{k}, j_{k}⟩ , e_{k}⟩ ∈ Und^{+}(p_{l,k}, T, y, μ, i)[G_{l}]”

and put p_{l,k+1} = (p_{l,k}^{∗}∧p_{l,k})∧_{ξ}F_{k}. We should check only (iv). Working in V [G_{l}] assume on the contrary that there were α ∈ y and t ∈ T, t = ⟨h_{0}, …, h_{m−1}⟩, such that t^{[p_{l,k+1}]}[G_{l}](α) ∈ r. We can assume that t is of minimal length. Write α_{0} = α and α_{s+1} = h_{s}(α_{s}) for s < m. Since (iv) holds for k, it follows that t^{[p_{l,k}]}[G_{l}](α) ∉ r. Suppose first that e_{k} = 1. Then there must be an s < m

such that α_{s} = x_{k} and h_{s} = f_{⟨_{A_{l}^{η}},_{B_{l}^{η}},C_{l}^{η}⟩} , or α_{s} = z_{k} and h_{s} = (f_{⟨_{A_{l}^{η}},_{B_{l}^{η}},C_{l}^{η}⟩})^{−1},

where ⟨Ã_{l}^{η}⌈^{∗}μ, B̃_{l}^{η}⌈^{∗}μ, C_{l}^{η} ∩ μ⟩ = ⟨Ã_{i}^{μ}, B̃_{i}^{μ}, C_{i}^{μ}⟩. Pick the minimal s. Then α_{s} ∈ T^{[p_{l,k}]}[G_{l}](y), because T is closed under subterms. But z_{k} ∉ T^{[p_{l,k}]}[G_{l}](y), so α_{s} = x_{k} and α_{s+1} = z_{k}. But t is of minimal length and T is closed under subterms, so we have that there are no s′ > s with α_{s′} = x_{k} and

h_{s′} = f_{⟨_{A_{l}^{η}},_{B_{l}^{η}},C_{l}^{η}⟩} , or with α_{s′} = z_{k} and h_{s′} = (f_{⟨_{A_{l}^{η}},_{B_{l}^{η}},C_{l}^{η}⟩})^{−1}. But it means

that z_{k} = α_{s+1} ∈ (T^{[p_{l,k}]}[G_{l}])^{−1}(r), which contradicts to the choice of z_{k}. If e_{k} = −1, then a similar argument works. Condition (v) obviously holds by the construction.

So we have p_{l,o_{l}}. Choose a condition p_{l}^{∗} ∈ G_{l} such that p_{l}^{∗} ≤ p_{l,o_{l}}⌈ξ, p_{l}^{∗}^{∥}—“t^{[p_{l,o_{l}}]}[G_{l}](y) ∩ r = ∅” and taking p_{l+1} = p_{l}^{∗} ∧ p_{l,o_{l}} we have

p_{l}^{∗}^{∥}—“t^{[p_{l,o_{l}}]}[G_{l}](y) = t^{[p_{l+1}]}(y)”.

Since t^{[p_{l,o_{l}}]}[G_{l}](y) = t^{[p_{l+1}]}[G_{l}](y), it follows that p_{l+1} satisfies (I). (II) is clear from the construction.

If there is no more ⟨μ, i⟩ with property (∗), then we finish the construction of the decreasing sequence p_{0}, p_{1}, …, p_{l^{∗}}. This must happen after at most |T × y| steps, because (II) holds and |dcd(p_{l}, T, y)| ≤ |T × y|. Let p^{∗} = p_{l^{∗}}. Since there are no more ⟨μ, i⟩ satisfying (∗), it follows that p^{∗} fully decides T (y) and p^{∗}^{∥}—“T^{[p^{∗}]}(y) ∩ r = ∅”, and so p^{∗} satisfies the requirements of the sublemma.

We continue the proof of lemma 2.2. Let G_{ω_{1}} be any P_{ω_{1}}-generic filter with p^{∗} ∈ G. Then in V [G_{ω_{1}}] we have T^{[p^{∗}]}(y) = T (y), because p^{∗} fully decides T (y), and so T (y)∩r = ∅. But p ∈ G_{ω_{1}}, and p^{∥}—“T (y)∩r ≠ ∅. Contradiction, the lemma is proved. Case (ii): P = Fin(2^{ω_{1}}, 2).

Since the proof in this case is simpler then in case (i) and it doesn’t demand new ideas, we only sketch it and the details are left to the readers.

Consider the iterated forcing system ⟨P_{ν} : ν ≤ 2^{ω_{1}}, Q_{ν} : ν < 2^{ω_{1}}⟩ with finite support , where Q_{0} = Fin(ω, 2) and Q_{ν} = Fin(ω_{1}, ω) for 1 ≤ ν < 2^{ω_{1}}. Since P is isomorphic to a dense subset of P_{2^{ω_{1}}}, we must show that V^{P_{2^{ω_{1}}}} contains a suitable permutation group.

Let r be the Cohen real in V^{Q_{0}} given by the Q_{0}-generic filter. We will define, by induction on μ, permutation groups G_{μ} on ω_{1} for 1 ≤ μ ≤ 2^{ω_{1}} such that

(a) G_{ν} ⊂ G_{μ} for ν < μ,

(b) V^{P_{μ}} ⊧“the pair (G_{μ}, r) is good”.

Case 1: μ = 1.

Take G_{0} = Perm^{V} (ω_{1}). Standard density arguments give that G_{0} satisfies (b). Case 2: μ is limit.

Take G_{μ} = ⋃_{ν<μ} G_{ν}. A suitable modification of proof of lemma 2.2 gives

that G_{μ} satisfies (b). Case 3:μ = ν + 1

We will work in V^{P_{ν}}. Pick sets X_{ν}, Y_{ν} ⊂ ω_{1} with |X_{ν}| = |ω_{1} \ X_{ν}| = |Y_{ν}| = |ω_{1} \ Y_{ν}| = ω_{1}. Since (G_{ν}, r) is a good pair, we can fix partitions {X_{ν,α}^{0} : α < ω_{1}}, {Y_{ν,α}^{0} : α < ω_{1}}, {X_{ν,α}^{1} : α < ω_{1}} and {Y_{ν,α}^{1} : α < ω_{1}} of X_{ν}, Y_{ν}, ω_{1} \ X_{ν} and ω_{1} \ Y_{ν}, respectively, such that each X_{ν,α}^{i} and Y_{ν,α}^{i} are countable and (G_{ν}, r)-large. Let

R_{ν} = {f ∈ Bij_{p}(ω_{1}, ω_{1}) : |f| < ω, f′′X_{ν,α}^{i} ⊂ Y_{ν,α}^{i} for each α < ω_{1} and i ∈ 2 }.

Take R_{ν} = ⟨R_{ν}, ⊇⟩. Then R_{ν} is isomorphic to Q_{ν}, so the Q_{ν}-generic filter over V^{P_{ν}} gives us an R_{ν}-generic filter G_{ν} over V^{P_{ν}}. Take g_{ν} = ∪G_{ν} and let G_{μ} be the subgroup of Perm^{V^{Pμ}}(ω_{1}) generated by G_{ν} ∪ {g_{ν}}.

The proof of that (b) remains true is a suitable modification of the proof of lemma 2.2 and it is left to the readers.

So G = G_{2^{ω_{1}}} is ω-inhomogeneous, because the pair (G, r) is good. Using a bookkeeping function we can ensure that {(X_{ν}, Y_{ν}) : ν < 2^{ω_{1}}} enumerates all the pairs (X, Y) of uncountable, co-uncountable subsets of ω_{1} in V^{P_{2^{ω_{1}}}} . Since g′′_{ν}X_{ν} = Y_{ν}, it follows that G is ω_{1}- homogeneous.

References

[1] A. Hajnal, A remark on the homogeneity of infinite permutation groups, preprint

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

[3] P. M. Neumann, Homogeneity of infinite permutation groups, Bull. London Math. Soc. 20 (1988), 305-312

[4] P. Nyikos, Transitivities of permutation groups, preprint

[5] S. Shelah, S. Thomson, Homogeneity of infinite permutation groups, preprint