On regular reduced products^{∗}

Juliette Kennedy ^{†} Department of Mathematics

University of Helsinki Helsinki, Finland

Saharon Shelah ^{‡} Institute of Mathematics Hebrew University Jerusalem, Israel

March 20, 2002

Abstract

Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. Assume M is a model of a first order theory T of cardinality at most λ^{+} in a language L(T) of cardinality ≤ λ. Let N be a model with the same language. Let Δ be a set of first order formulas in L(T) and let D be a regular filter on λ. Then M is Δ-embeddable into the reduced power N^{λ}/D, provided that every Δexistential formula true in M is true also in N. We obtain the following corollary: for M as above and D a regular ultrafilter over λ, M^{λ}/D is λ^{++}-universal. Our second result is as follows: For i < μ let M_{i} and N_{i} be elementarily equivalent models of a language which has cardinality ≤ λ. Suppose D is a regular filter on λ and ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ holds. We show that then the second player has a winning strategy in the Ehrenfeucht-Fraisse game of length λ^{+} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D. This yields the following corollary: Assume GCH and λ regular (or just ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ and 2^{λ} = λ^{+}). For L, M_{i} and N_{i} be as above, if D is a regular filter on λ, then ∏_{i} M_{i}/D ≅ ∏_{i} N_{i}/D.

∗This paper was written while the authors were guests of the Mittag-Leffler Institute, Djursholm, Sweden. The authors are grateful to the Institute for its support.

†Research partially supported by grant 1011049 of the Academy of Finland.

‡Research partially supported by the Binational Science Foundation. Publication number 769.

1 Introduction

Suppose M is a first order structure and F is the Frechet filter on ω. Then the reduced power M^{ω}/F is ℵ_{1}-saturated and hence ℵ_{2}-universal ([6]). This was generalized by Shelah in [10] to any filter F on ω for which B^{ω}/F is ℵ_{1}-saturated, where B is the two element Boolean algebra, and in [8] to all regular filters on ω. In the first part of this paper we use the combinatorial principle □_{λ}^{b^{∗}} of Shelah [11] to generalize the result from ω to arbitrary λ, assuming ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. This gives a partial solution to Conjecture 19 in [3]: if D is a regular ultrafilter over λ, then for all infinite M, the ultrapower M^{λ}/D is λ^{++}-universal.

The second part of this paper addresses Problem 18 in [3], which asks if it is true that if D is a regular ultrafilter over λ, then for all elementarily equivalent models M and N of cardinality ≤ λ in a language of cardinality ≤ λ, the ultrapowers M^{λ}/D and N^{λ}/D are isomorphic. Keisler [7] proved this for good D assuming 2^{λ} = λ^{+}. Benda [1] weakened “good” to “contains a good filter”. We prove the claim in full generality, assuming 2^{λ} = λ^{+} and ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩.

Regarding our assumption ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩, by Chang’s Two-Cardinal Theorem ([2]) ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ is a consequence of λ = λ^{<λ}. So our Theorem 2 settles Conjecture 19 of [3], and Theorem 13 settles Conjecture 18 of [3], under GCH for λ regular. For singular strong limit cardinals ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ follows from □_{λ} (Jensen [5]). In the so-called Mitchell’s model ([9]) ⟨ℵ_{0}, ℵ_{1}⟩ ↛ ⟨ℵ_{1}, ℵ_{2}⟩, so our assumption is independent of ZFC.

2 Universality

Definition 1 Suppose Δ is a set of first order formulas of the language L. The set of Δ-existential formulas is the set of formulas of the form

∃x_{1}...∃x_{n}(ϕ_{1} ∧ ... ∧ ϕ_{n}),

where each ϕ_{i} is in Δ. The set of weakly Δ-existential formulas is the set of formulas of the above form, where each ϕ_{i} is in Δ or is the negation of a formula in Δ. If M and N are L-structures and h : M → N, we say that h is a Δ-homomorphism if h preserves the truth of Δ-formulas. If h preserves also the truth of negations of Δ-formulas, it is called a Δ-embedding.

Theorem 2 Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. Let M be a model of a first order theory T of cardinality at most λ^{+}, in a language L of cardinality ≤ λ and let N be a model with the same language. Let Δ be a set of first order formulas in L and let D be a regular filter on λ. We assume that every weakly Δ-existential sentence true in M is true also in N. Then there is a Δ-embedding of M into the reduced power N^{λ}/D.

By letting Δ be the set of all first order sentences, we get from Theorem 2:

Corollary 3 Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. If M is a model with language ≤ λ, and D is a regular ultrafilter on λ, then M^{λ}/D is λ^{++}-universal, i.e. if M′ is of cardinality ≤ λ^{+}, and M′ ≡ M, then M′ is elementarily embeddable into the ultrapower M^{λ}/D.

We can replace “weakly Δ-existential” by “Δ-existential” in the Theorem, if we only want a Δ-homomorphism.

The idea behind the proof of Theorem 2 is roughly as follows: suppose M = {a_{ζ} : ζ < λ^{+}}. We associate to each ζ < λ^{+} finite sets u_{i}^{ζ} ⊆ ζ, i < λ, and represent the formula set Δ as a union of finite sets Δ_{i}. The proof involves a simultaneous recursion over λ^{+} and λ. At stage i, for each ζ < λ^{+} we consider the Δ_{i}-type of those elements a_{τ} of the model whose indices lie in the set u_{i}^{ζ}, ζ < λ^{+}. This will yield a witness f_{τ}(i) in N at stage i, τ. Naturally, the sets u_{i}^{ζ} have to have some coherence properties in order for this to work. Our embedding is then given by a_{τ} ↦ ⟨f_{τ}(i) : i < λ⟩/D.

We need first an important lemma, reminiscent of Proposition 5.1 in [11]:

Lemma 4 Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. Let D be a regular filter on λ. There exist sets u_{i}^{ζ} and integers n_{i} for each ζ < λ^{+} and i < λ such that for each i, ζ

(i) |u_{i}^{ζ}| < n_{i}

(ii) u_{i}^{ζ} ⊆ ζ

(iii) Let B be a finite set of ordinals and let ζ be such that B ⊆ ζ < λ^{+}. Then {i : B ⊆ u_{i}^{ζ}} ∈ D

(iv) Coherency: γ ∈ u_{i}^{ζ} ⇒ u_{i}^{γ} = u_{i}^{ζ} ∩ γ

Assuming the lemma, and letting M = {a_{ζ} : ζ < λ^{+}} we now define, for each ζ, a function f_{ζ} : λ ↦ N.

Let Δ = {ϕ_{α} : α < λ} and let {A_{α} : α < λ} be a family witnessing the regularity of D. Thus for each i < λ, the set w_{i} = {α : i ∈ A_{α}} is finite. Let Δ_{i} = {ϕ_{α} : α ∈ w_{i}}, and let u_{i}^{ζ}, n_{i} be as in the lemma.

We define a sequence of formulas essential to the proof: suppose ζ < λ^{+} and i < λ. Let m_{i}^{ζ} = |u_{i}^{ζ}| and let

u_{i}^{ζ} = {ξ_{ζ,i,1}, ..., ξ_{ζ,i,m_{i}^{ζ}}}

be the increasing enumeration of u_{i}^{ζ}. (We adopt henceforth the convention that any enumeration of u_{i}^{ζ} that is given is the increasing enumeration.) Let θ̄_{i}^{ζ} be the Δ_{i}-type of the tuple ⟨a_{ξ_{ζ,i,1}}, ..., a_{ξ_{ζ,i,m{ζ \atop i}}} ⟩ in M. (So every

ϕ(x_{1}, ..., x_{m_{i}^{ζ}}) ∈ Δ_{i} or its negation occurs as an element of θ̄_{i}^{ζ}, according to whether ϕ(a_{ξ_{ζ,i,1}}, ..., a_{ξ_{ζ,i,m{ζ \atop i}}}) or ¬ϕ(a_{ξ_{ζ,i,1}}, ..., a_{ξ_{ζ,i,m{ζ \atop i}}}) holds in M.) We define

the formula θ_{i}^{ζ} for each i by downward induction on m_{i}^{ζ} as follows: Case 1: m_{i}^{ζ} + 1 = n_{i}. Let θ_{i}^{ζ} = ⋀ θ̄_{i}^{ζ}. Case 2: m_{i}^{ζ} + 1 < n_{i}. Let θ_{i}^{ζ} be the conjunction of θ̄_{i}^{ζ} and all formulas of the form ∃x_{m_{i}^{ϵ}}θ_{i}^{ϵ}(x_{1}, ..., x_{m_{i}^{ζ}}, x_{m_{i}^{ϵ}}), where ϵ satisfies u_{i}^{ϵ} = u_{i}^{ζ} ∪ {ζ} and hence

m_{i}^{ϵ} = m_{i}^{ζ} + 1. If no such ϵ exists, θ_{i}^{ζ} is just the conjunction of θ̄_{i}^{ζ}.

An easy induction, based on the fact that there is a uniform bound n_{i} on the sizes of the sets u_{i}^{ζ}, shows that for a fixed i < λ, the cardinality of the set {θ_{i}^{ζ} : ζ < λ^{+}} is finite.

Let i < λ be fixed. We define f_{ϵ}(i) for ϵ ∈ u_{i}^{ζ} by induction on ζ < λ^{+} in such a way that the following condition remains valid:

(IH) If ζ^{∗} < ζ and u_{i}^{ζ^{∗}} = {r_{ϵ_{1}}, ..., r_{ϵ_{k}}}, then N ⊧ θ_{i}^{ζ^{∗}}(f_{ϵ_{1}}(i), ..., f_{ϵ_{k}}(i)).

Actually, f_{ϵ}(i) gets defined once and for all at the first stage ζ such that ϵ ∈ u_{i}^{ζ}. To define f_{ϵ}(i) for ϵ ∈ u_{i}^{ζ}, we consider different cases: Case 1: n_{i} = m_{i}^{ζ} + 1. Case 1.1: n_{i} = 1. Then there is nothing to prove, since u_{i}^{ζ} is empty. Case 1.2: n_{i} > 1. Let u_{i}^{ζ} = {ξ_{1}, …, ξ_{m_{i}^{ζ}}}. Since m_{i}^{ζ} + 1 = n_{i}, the formula

θ_{i}^{ζ} is the Δ_{i}-type of the elements \{a_{ξ_{1}}, …, a_{ξ_{m{ζ \atop i}}} \}. By assumption γ = ξ_{m_{i}^{ζ}} is

the maximum element of u_{i}^{ζ}. We note that for ϵ ∈ u_{i}^{ζ} ∩ γ, f_{ϵ}(i) is already defined. By coherency, u_{i}^{γ} = u_{i}^{ζ} ∩ γ = {ξ_{1}, …, ξ_{m_{i}^{ζ}−1}}. Since γ < ζ, we know by the induction hypothesis that

N ⊧ θ_{i}^{γ}(f_{ξ_{1}}(i), …, f_{ξ_{m{ζ \atop i} −1}}(i)).

As u_{i}^{ζ} = u_{i}^{γ} ∪ {γ} and m_{i}^{γ} < n_{i} − 1, the formula θ_{i}^{γ} contains the formula ∃x_{m_{i}^{ζ}}θ_{i}^{ζ}(x_{1}, …, x_{m_{i}^{ζ}}) as a conjunct. Thus

N ⊧ ∃x_{m_{i}^{ζ}}θ_{i}^{ζ}(f_{ξ_{1}}(i), …, f_{ξ_{m{ζ \atop i} −1}}(i), x_{m_{i}^{ζ}}).

Now let b ∈ N witness this formula and set f_{γ}(i) = b. Case 2: m_{i}^{ζ}+1 < n_{i}. Let u_{i}^{ζ} = \{ξ_{1}, …, ξ_{m_{i}^{ζ}}\}. We have that M ⊧ θ_{i}^{ζ}(a_{ξ_{1}}, …, a_{ξ_{m{ζ \atop i}}}),

and therefore M ⊧ ∃x_{m_{i}^{ζ}}θ_{i}^{ζ}(a_{ξ_{1}}, …, a_{ξ_{m{ζ \atop i} −1}}, x_{m_{i}^{ζ}}). Let γ = max(u_{i}^{ζ})=ξ_{m_{i}^{ζ}}. By

coherency u_{i}^{γ} = u_{i}^{ζ} ∩ γ and therefore since γ < ζ again by the induction hypothesis we have that

N ⊧ θ_{i}^{γ}(f_{ξ_{1}}(i), …, f_{ξ_{m{ζ \atop i} −1}}(i)).

But then as in case 1.2 we can infer that

N ⊧ ∃x_{m_{i}^{ζ}}θ_{i}^{ζ}(f_{ξ_{1}}(i), …, f_{ξ_{m{ζ \atop i} −1}}(i), x_{m_{i}^{ζ}}).

As in case 1 choose an element b ∈ N to witness this formula and set f_{γ}(i) = b.

It remains to be shown that the mapping a_{ζ} ↦ ⟨f_{ζ}(i) : i < λ⟩/D satisfies the requirements of the theorem, i.e. we must show, for all ϕ such that ϕ ∈ Δ or ¬ϕ ∈ Δ:

M ⊧ ϕ(a_{ξ_{1}}, …, a_{ξ_{k}}) ⇒ {i : N ⊧ ϕ(f_{ξ_{1}}(i), …, f_{ξ_{k}}(i))} ∈ D.

So let such a ϕ be given, and suppose M ⊧ ϕ(a_{ξ_{1}}, …, a_{ξ_{k}}). Let I_{ϕ} = {i : N ⊧ ϕ(f_{ξ_{1}}(i), …, f_{ξ_{k}}(i))}. We wish to show that I_{ϕ} ∈ D. Let α < λ so that ϕ is ϕ_{α} or its negation. It suffices to show that A_{α} ⊆ I_{ϕ}. Let ζ < λ^{+} be such that {ξ_{1}, ..., ξ_{n}} ⊆ ζ. By Lemma 4 condition (iii), {i : {ξ_{1}, ..., ξ_{n}} ⊆ u_{i}^{ζ}} ∈ D. So it suffices to show

A_{α} ∩ {i : {ξ_{1}, ..., ξ_{n}} ⊆ u_{i}^{ζ}} ⊆ I_{ϕ}.

Let i ∈ A_{α} such that {ξ_{1}, ..., ξ_{n}} ⊆ u_{i}^{ζ}. By the definition of θ_{i}^{ζ} we know that N ⊧ θ_{i}^{ζ}(f_{ξ_{1}}(i), …, f_{ξ_{k}}(i)). But the Δ_{i}-type of the tuple ⟨a_{ξ_{1}}, …, a_{ξ_{k}}⟩ occurs as a conjunct of θ_{i}^{ζ}, and therefore N ⊧ ϕ(f_{ξ_{1}}(i), …, f_{ξ_{k}}(i)) □

3 Proof of Lemma 4

We now prove Lemma 4. We first prove a weaker version in which the filter is not given in advance:

Lemma 5 Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. Then there exist sets ⟨u_{i}^{ζ} : ζ < λ^{+}, i < cof(λ)⟩, integers n_{i} and a regular filter D on λ, generated by λ sets, such that (i)-(iv) of Lemma 4 hold.

Proof. By [11, Proposition 5.1, p. 149] the assumption ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ is equivalent to:

□_{λ}^{b^{∗}} : There is a λ^{+}-like linear order L, sets ⟨C_{a}^{ζ} : a ∈ L, ζ < cf(λ)⟩, equivalence relations ⟨E^{ζ} : ζ < cf(λ)⟩, and functions ⟨f_{a,b}^{ζ} : ζ < λ, a ∈ L, b ∈ L⟩ such that

(i) ⋃_{ζ} C_{a}^{ζ} = {b : b <_{L} a} (an increasing union in ζ).

(ii) If b ∈ C_{a}^{ζ}, then C_{b}^{ζ} = {c ∈ C_{a}^{ζ} : c <_{L} b}.

(iii) E^{ζ} is an equivalence relation on L with ≤ λ equivalence classes.

(iv) If ζ < ξ < cf(λ), then E^{ξ} refines E^{ζ}.

(v) If aE^{ζ}b, then f_{a,b}^{ζ} is an order-preserving one to one mapping from C_{a}^{ζ} onto C_{b}^{ζ} such that for d ∈ C_{a}^{ζ}, dE^{ζ}f_{a,b}^{ζ}(d).

(vi) If ζ < ξ < cf(λ) and aE^{ξ}b, then f_{a,b}^{ζ} ⊆ f_{a,b}^{ξ}.

(vii) If f_{a,b}^{ζ}(a_{1}) = b_{1}, then f_{a_{1},b_{1}}^{ζ} ⊆ f_{a,b}^{ζ}.

(viii) If a ∈ C_{b}^{ζ} then ¬E^{ζ}(a, b).

This is not enough to prove Lemma 5, so we have to work a little more. Let

Ξ_{ζ} = {a/E^{ζ} : a ∈ L}.

We assume, for simplicity, that ζ ≠ ξ implies Ξ_{ζ} ∩ Ξ_{ξ} = ∅. Define for t_{1}, t_{2} ∈ Ξ_{ζ}:

t_{1} <_{ζ} t_{2} ⟺ (∃a_{1} ∈ t_{1})(∃a_{2} ∈ t_{2})(a_{1} ∈ C_{a_{2}}^{ζ}).

Proposition 6 ⟨Ξ_{ζ}, <_{ζ}⟩ is a tree order with cf(λ) as the set of levels.

Proof. We need to show (a) t_{1} <_{ζ} t_{2} <_{ζ} t_{3} implies t_{1} <_{ζ} t_{3}, and (b) t_{1} <_{ζ} t_{3} and t_{2} <_{ζ} t_{3} implies t_{1} <_{ζ} t_{2} or t_{2} <_{ζ} t_{1} or t_{1} = t_{2}. For the first, t_{1} <_{ζ} t_{2} implies there exists a_{1} ∈ t_{1} and a_{2} ∈ t_{2} such that a_{1} ∈ C_{a_{2}}^{ζ}. Similarly t_{2} <_{ζ} t_{3} implies there exists b_{2} ∈ t_{2} and b_{3} ∈ t_{3} such that b_{2} ∈ C_{b_{3}}^{ζ}. Now a_{2}E^{ζ}b_{2} and hence we have the order preserving map f_{a_{2},b_{2}}^{ζ} from C_{a_{2}}^{ζ} onto C_{b_{2}}^{ζ}. Recalling a_{1} ∈ C_{a_{2}}^{ζ}, let f_{a_{2},b_{2}}^{ζ}(a_{1}) = b_{1}. Then by (vi), a_{1}E^{ζ}b_{1} and hence b_{1} ∈ t_{1}. But then b_{1} ∈ C_{b_{2}}^{ζ} implies b_{1} ∈ C_{b_{3}}^{ζ}, by coherence and the fact that b_{2} ∈ C_{b_{3}}^{ζ}. But then it follows that t_{1} <_{ζ} t_{3}.

Now assume t_{1} <_{ζ} t_{3} and t_{2} <_{ζ} t_{3}. Let a_{1} ∈ t_{1} and a_{3} ∈ t_{3} be such that a_{1} ∈ C_{a_{3}}^{ζ}, and similarly let b_{2} and b_{3} be such that b_{2} ∈ C_{b_{3}}^{ζ}. a_{3}E^{ζ}b_{3} implies we have the order preserving map f_{a_{3},b_{3}}^{ζ} from C_{a_{3}}^{ζ} to C_{b_{3}}^{ζ}. Letting f_{a_{3},b_{3}}^{ζ}(a_{1}) = b_{1}, we see that b_{1} ∈ C_{b_{3}}^{ζ}. If b_{1} <_{L} b_{2}, then we have C_{b_{2}}^{ζ} = C_{b_{3}}^{ζ} ∩ {c : c < b_{2}} which implies b_{1} ∈ C_{b_{2}}^{ζ}, since, as f_{a_{3},b_{3}}^{ζ} is order preserving, b_{1} <_{L} b_{2}. Thus t_{1} <_{ζ} t_{2}. The case b_{2} <_{L} b_{1} is proved similarly, and b_{1} = b_{2} is trivial. □

For a <_{L} b let

ξ(a, b) = min{ζ : a ∈ C_{b}^{ζ}}.

Denoting ξ(a, b) by ξ, let

tp(a, b) = ⟨a/E^{ξ}, b/E^{ξ}⟩.

If a_{1} <_{L} ... <_{L} a_{n}, let

tp(⟨a_{1}, ..., a_{n}⟩) = {⟨l, m, tp(a_{l}, a_{m})⟩|1 ≤ l < m ≤ n}

and

Γ = {tp(a⃗) : a⃗ ∈ ^{<ω}L}.

For t = tp(a⃗), a⃗ ∈ ^{n}L we use n_{t} to denote the length of a⃗.

Proposition 7 If a_{0} <_{L} ... <_{L} a_{n}, then

max{ξ(a_{l}, a_{m}) : 0 ≤ l < m ≤ n} = max{ξ(a_{l}, a_{n}) : 0 ≤ l < n}.

Proof. Clearly the right hand side is ≤ the left hand side. To show the left hand side is ≤ the right hand side, let l < m < n be arbitrary. If ξ(a_{l}, a_{n}) ≤ ξ(a_{m}, a_{n}), then ξ(a_{l}, a_{m}) ≤ ξ(a_{m}, a_{n}). On the other hand, if ξ(a_{l}, a_{n}) > ξ(a_{m}, a_{n}), then ξ(a_{l}, a_{m}) ≤ ξ(a_{l}, a_{n}). In either case ξ(a_{l}, a_{m}) ≤ max{ξ(a_{k}, a_{n}) : 0 ≤ k < n}. □

Let us denote max{ξ(a_{l}, a_{n}) : 0 ≤ l < n} by ξ(a⃗). We define on Γ a two-place relation ≤_{Γ} as follows:

t_{1} <_{Γ} t_{2}

if there exists a tuple ⟨a_{0}, … a_{n_{t_{2}}−1}⟩ realizing t_{2} such that some subsequence of the tuple realizes t_{1}.

Clearly, ⟨Γ, ≤_{Γ}⟩ is a directed partial order.

Proposition 8 For t ∈ Γ, t = tp(b_{0}, … b_{n−1}) and a ∈ L, there exists at most one k < n such that b_{k}E^{ξ(b_{0},...,b_{n−1})}a.

Proof. Let ζ = ξ(b_{0}, …, b_{n−1}) and let b_{k_{1}} ≠ b_{k_{2}} be such that b_{k_{1}}E^{ζ}a and b_{k_{2}}E^{ζ}a, k_{1}, k_{2} ≤ n − 1. Without loss of generality, assume b_{k_{1}} < b_{k_{2}}. Since E^{ζ} is an equivalence relation, b_{k_{2}}E^{ζ}b_{k_{1}} and thus we have an order preserving map f_{b_{k_{2}},b_{k_{1}}}^{ζ} from C_{b_{k_{2}}}^{ζ} to C_{b_{k_{1}}}^{ζ}. Also b_{k_{1}} ∈ C_{b_{k_{2}}}^{ζ}, by the definition of ζ and by coherence, and therefore f_{b_{k_{2}},b_{k_{1}}}^{ζ}(b_{k_{1}})E^{ζ}b_{k_{1}}. But this contradicts (viii), since f_{b_{k_{2}},b_{k_{1}}}^{ζ}(b_{k_{1}}) ∈ C_{b_{k_{1}}}^{ζ}. □

Definition 9 For t ∈ Γ, t = tp(b_{0}, … b_{n−1}) and a ∈ L suppose there exists k < n such that b_{k}E^{ξ(b_{0},...,b_{n−1})}a. Then let u_{t}^{a} = {f_{a,b_{k}}^{ζ(b_{0},...,b_{n−1})}(b_{l}) : l < k} Otherwise, let u_{t}^{a} = ∅.

Finally, let D be the filter on Γ generated by the λ sets

Γ_{≥t^{∗}} = {t ∈ Γ : t^{∗} <_{L} t}.

We can now see that the sets u_{t}^{a}, the numbers n_{t} and the filter D satisfy conditions (i)-(iv) of Lemma 4 with L instead of λ^{+}: Conditions (i) and (ii) are trivial in this case. Condition (iii) is verified as follows: Suppose B is finite. Let a ∈ L be such that (∀x ∈ B)(x <_{L} a). Let a⃗ enumerate B ∪ {a} in increasing order and let t^{∗} = tp(a⃗). Clearly

t ∈ Γ_{≥t^{∗}} ⇒ B ⊆ u_{t}^{a}.

Condition (iv) follows directly from Definition 9 and Proposition 8.

To get the Lemma on λ^{+} we observe that since L is λ^{+}-like, we can assume that ⟨λ^{+}, <⟩ is a submodel of ⟨L, <_{L}⟩. Then we define v_{t}^{α} = u_{t}^{α} ∩{β : β < α}.

Conditions (i)-(iv) of Lemma 5 are still satisfied. Also having D a filter on Γ instead of on λ is immaterial as |Γ| = λ. □

Now back to the proof of Lemma 4. Suppose u_{i}^{ζ}, n_{i} and D are as in Lemma 5, and suppose D′ is an arbitrary regular filter on λ. Let {A_{α} : α < λ} be a family of sets witnessing the regularity of D′, and let {Z_{α} : α < λ} be the family generating D. We define a function h : λ → λ as follows. Suppose i < λ. Then let

h(i) ∈ ⋂{Z_{α}|i ∈ A_{α}}.

Now define v_{α}^{ζ} = u_{h(α)}^{ζ}. Define also n_{α} = n_{h(α)}. Now the sets v_{α}^{ζ} and the numbers n_{α} satisfy the conditions of Lemma 4. □

4 Is □_{λ}^{b^{∗}} needed for Lemma 5?

In this section we show that the conclusion of Lemma 5 (and hence of Lemma 4) implies □_{λ}^{b^{∗}} for singular strong limit λ. By [11, Theorem 2.3 and Remark 2.5], □_{λ}^{b^{∗}} is equivalent, for singular strong limit λ, to the following principle:

S_{λ} : There are sets ⟨C_{a}^{i} : a < λ^{+}, i < cf(λ)⟩ such that

(i) If i < j, then C_{a}^{i} ⊆ C_{a}^{j}.

(ii) ⋃_{i} C_{a}^{i} = a.

(iii) If b ∈ C_{a}^{i}, then C_{b}^{i} = C_{a}^{i} ∩ b.

(iv) sup{otp(C_{a}^{i}) : a < λ^{+}} < λ.

Thus it suffices to prove:

Proposition 10 Suppose the sets u_{i}^{ζ} and the filter D are as given by Lemma 5 and λ is a limit cardinal. Then S_{λ} holds.

Proof. Suppose A = {A_{α} : α < λ} is a family of sets generating D. W.l.o.g., A is closed under finite intersections. Let λ be the union of the increasing sequence ⟨λ_{α} : α < cf(λ)⟩, where λ_{0} ≥ ω. Let the sequence ⟨Γ_{α} : α < cf(λ)⟩ satisfy:

(a) |Γ_{α}| ≤ λ_{α} (b) Γ_{α} is continuously increasing in α with λ as union

(c) If β_{1}, ..., β_{n} ∈ Γ_{α}, then there is γ ∈ Γ_{α} such that

A_{γ} = A_{β_{1}} ∩ ... ∩ A_{β_{n}}.

The sequence ⟨Γ_{α} : α < cf(λ)⟩ enables us to define a sequence that will witness S_{λ}. For α < cf(λ) and ζ < λ^{+}, let

V_{ζ}^{α} = {ξ < ζ : (∃γ ∈ Γ_{α})(A_{γ} ⊆ {i : ξ ∈ u_{i}^{ζ}})}.

Lemma 11 (1) ⟨V_{ζ}^{α} : α < λ⟩ is a continuously increasing sequence of subsets of ζ, |V_{ζ}^{α}| ≤ λ_{α}, and ⋃{V_{ζ}^{α} : α < cf(λ)} = ζ.

(2) If ξ ∈ V_{ζ}^{α}, then V_{ξ}^{α} = V_{ζ}^{α} ∩ ξ.

Proof. (1) is a direct consequence of the definitions. (2) follows from the respective property of the sets u_{i}^{ζ}. □

Lemma 12 sup{otp(V_{ζ}^{α}) : ζ < λ^{+}} ≤ λ_{α}^{+}.

Proof. By the previous Lemma, |V_{ζ}^{α}| ≤ λ_{α}. Therefore otp(V_{ζ}^{α}) < λ_{α}^{+} and the claim follows. □

The proof of the proposition is complete: (i)-(iii) follows from Lemma 11, (iv) follows from Lemma 12 and the assumption that λ is a limit cardinal. □

More equivalent conditions for the case λ singular strong limit, D a regular ultrafilter on λ, are under preparation.

5 Ehrenfeucht-Fraïssé-games

Let M and N be two first order structures of the same language L. All vocabularies are assumed to be relational. The Ehrenfeucht-Fraïssé-game of length γ of M and N denoted by EFG_{γ} is defined as follows: There are two players called I and II. First I plays x_{0} and then II plays y_{0}. After this I plays x_{1}, and II plays y_{1}, and so on. If ⟨(x_{β}, y_{β}) : β < α⟩ has been played and α < γ, then I plays x_{α} after which II plays y_{α}. Eventually a sequence ⟨(x_{β}, y_{β}) : β < γ⟩ has been played. The rules of the game say that both players have to play elements of M ∪ N. Moreover, if I plays his x_{β} in M (N), then II has to play his y_{β} in N (M). Thus the sequence ⟨(x_{β}, y_{β}) : β < γ⟩ determines a relation π ⊆ M × N. Player II wins this round of the game if π is a partial isomorphism. Otherwise I wins. The notion of winning strategy is defined in the usual manner. We say that a player wins EFG_{γ} if he has a winning strategy in EFG_{γ}.

Note that if II has a winning strategy in EFG_{γ} on M and N, where M and N are of size ≤ |γ|, then M ≅ N.

Assume L is of cardinality ≤ λ and for each i < λ let M_{i} and N_{i} be elementarily equivalent L-structures. Shelah proved in [12] that if D is a regular filter on λ, then Player II has a winning strategy in the game EFG_{γ} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D for each γ < λ^{+}. We show that under a stronger assumption, II has a winning strategy even in the game EFG_{λ^{+}}. This makes a big difference because, assuming the models M_{i} and N_{i} are of size ≤ λ^{+}, 2^{λ} = λ^{+}, and the models ∏_{i} M_{i}/D and ∏_{i} N_{i}/D are of size ≤ λ^{+}. Then by the remark above, if II has a winning strategy in EFG_{λ^{+}}, the reduced powers are actually isomorphic. Hyttinen [4] proved this under the assumption that the filter is, in his terminology, semigood.

Theorem 13 Assume ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩. Let L be a language of cardinality ≤ λ and for each i < λ let M_{i} and N_{i} be two elementarily equivalent Lstructures. If D is a regular filter on λ, then Player II has a winning strategy in the game EFG_{λ^{+}} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D.

Proof. We use Lemma 4. If i < λ, then, since M_{i} and N_{i} are elementarily equivalent, Player II has a winning strategy σ_{i} in the game EFG_{n_{i}} on M_{i} and N_{i}. We will use the set u_{i}^{ζ} to put these short winning strategies together into one long winning strategy.

A “good” position is a sequence ⟨(f_{ζ}, g_{ζ}) : ζ < ξ⟩, where ξ < λ^{+}, and for all ζ < ξ we have f_{ζ} ∈ ∏_{i} M_{i}, g_{ζ} ∈ ∏_{i} N_{i}, and if i < λ, then ⟨(f_{ϵ}(i), g_{ϵ}(i)) : ϵ ∈ u_{i}^{ζ} ∪ {ζ}⟩ is a play according to σ_{i}.

Note that in a good position the equivalence classes of the functions f_{ζ} and g_{ζ} determine a partial isomorphism of the reduced products. To see this, suppose ⟨(f_{ζ}, g_{ζ}) : ζ < ξ⟩ is a good position, ϕ(x_{1}, …, x_{k}) is atomic and I_{ϕ} = {i : M_{i} ⊧ ϕ(f_{α_{1}}(i), …, f_{α_{k}}(i))} ∈ D. We wish to show that I′_{ϕ} = {i : N_{i} ⊧ ϕ(g_{α_{1}}(i), …, g_{α_{k}}(i))} ∈ D. By Lemma 4, if γ < λ^{+} is such that B = {α_{1}, …, α_{k}} ⊆ γ, then J_{γ} = {i : B ⊆ u_{i}^{γ}} ∈ D. Thus J_{γ} ∩ I_{ϕ} ∈ D, and for each i ∈ J_{γ}, ⟨(f_{ϵ}(i), g_{ϵ}(i)) : ϵ ∈ u_{i}^{γ}⟩ is part of the play according to σ_{i}. Thus for each such i, i ∈ I_{ϕ} ↔ i ∈ I′_{ϕ} i.e. J_{γ} ∩ I_{ϕ} = J_{γ} ∩ I′_{ϕ}, whence I′_{ϕ} ∈ D.

The strategy of player II is to keep the position of the game “good”, and thereby win the game. Suppose ξ rounds have been played and II has been able to keep the position “good”. Then player I plays f_{ξ}. We show that player II can play g_{ξ} so that ⟨(f_{ζ}, g_{ζ}) : ζ ≤ ξ⟩ remains “good”. Let i < λ. Let us look at ⟨(f_{ϵ}(i), g_{ϵ}(i)) : ϵ ∈ u_{i}^{ξ}⟩. We know that this is a play according to the strategy σ_{i} and |u_{i}^{ξ}| < n_{i}. Thus we can play one more move in EF_{n_{i}} on M_{i} and N_{i} with player I playing f_{ξ}(i). Let g_{ξ}(i) be the answering move of II in this game according to σ_{i}. The values g_{ξ}(i), i < λ, constitute the function g_{ξ}. We have shown that II can maintain a “good” position. □

Corollary 14 Assume GCH and λ regular (or just ⟨ℵ_{0}, ℵ_{1}⟩ → ⟨λ, λ^{+}⟩ and 2^{λ} = λ^{+}). Let L be a language of cardinality ≤ λ and for each i < λ let M_{i} and N_{i} be two elementarily equivalent L-structures. If D is a regular filter on λ, then ∏_{i} M_{i}/D ≅ ∏_{i} N_{i}/D.

References

[1] M. Benda, On reduced products and filters. Ann.Math.Logic 4 (1972), 1-29.

[2] C. C. Chang, , A note on the two cardinal problem, Proc. Amer. Math. Soc., 16, 1965, 1148–1155,

[3] C.C. Chang and J.Keisler, Model Theory, North-Holland.

[4] T. Hyttinen, On κ-complete reduced products, Arch. Math. Logic, Archive for Mathematical Logic, 31, 1992, 3, 193–199

[5] R. Jensen, The fine structure of the constructible hierarchy, With a section by Jack Silver, Ann. Math. Logic, 4, 1972, 229–308

[6] B. Jónsson and P. Olin, Almost direct products and saturation, Compositio Math., 20, 1968, 125–132

[7] J. Keisler, Ultraproducts and saturated models. Nederl.Akad.Wetensch. Proc. Ser. A 67 (=Indag. Math. 26) (1964), 178-186.

[8] J. Kennedy and S. Shelah, On embedding models of arithmetic of cardinality ℵ_{1} into reduced powers, to appear.

[9] W. Mitchell, Aronszajn trees and the independence of the transfer property, Ann. Math. Logic, 5, 1972/73, 21–46

[10] S. Shelah, For what filters is every reduced product saturated?, Israel J. Math., 12, 1972, 23–31

[11] S. Shelah, “Gap 1” two-cardinal principles and the omitting types theorem for L(Q). Israel Journal of Mathematics vol 65 no. 2, 1989, 133–152.

[12] S. Shelah, Classification theory and the number of non-isomorphic models, Second, North-Holland Publishing Co., Amsterdam, 1990, xxxiv+705