More on regular reduced products

Juliette Kennedy ^{∗} Department of Mathematics

University of Helsinki Helsinki, Finland

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

August 11, 2004

Abstract

The authors show, by means of a finitary version □_{λ,D}^{fin} of the combinatorial principle □_{λ}^{b^{∗}} of [6], the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal λ, if M_{i} and N_{i} are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ^{+} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D. If in addition 2^{λ} = λ^{+} and i < λ implies |M_{i}|+|N_{i}| ≤ λ^{+} this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [1].

The problem of when two elementarily equivalent structures have isomorphic ultrapowers was prominent in the model theory of the 1960’s. Keisler [2] proved, assuming GCH, that elementarily equivalent structures have isomorphic ultrapowers. Keisler’s proof depended on GCH both on the question of existence of good ultrafilters and on limiting the size of the ultraproducts. More exactly, Keisler considered a language of size λ, models M of size ≤ λ^{+} and a λ^{+}-good countably incomplete ultrafilter D on λ. He proved that M^{λ}/D is λ^{+}-saturated. Under the weaker assumption that D is regular he proved that M^{λ}/D is λ^{+}-universal, i.e. every N ≡ M^{λ}/D can be elementarily embedded into it.

∗Research partially supported by grant 40734 of the Academy of Finland.

†The second author would like to thank the Israel Science Foundation for partial support of this research (Grant no. 242/03). Publication 852.

Shelah [5] improved the result by eliminating GCH: two structures M and N are elementarily equivalent if and only if, for some λ and some regular ultrafilter D on λ the structures M^{λ}/D and N^{λ}/D are isomorphic. This left open the following question, asked by Chang and Keisler as Conjecture 18 in [1]:

Let M and N be structures of cardinality ≤ λ in a language of size ≤ λ and let D be a regular ultrafilter over λ. If M ≡ N, then M^{λ}/D ≅ N^{λ}/D.

The Conjecture is a natural one as most of the model theory regarding ultrapowers is centered on the regular ultrafilters. Also at the time of Keisler’s question GCH was generally considered a reasonable assumption for the question.

Also the Conjecture is formulated for models of size ≤ λ, perhaps for accidental reasons, but it seems more natural if M and N have cardinality ≤ λ^{+}.

Conjecture 19 of [1], which we also address in this paper, is:

If D is a regular ultrafilter over λ, then for all infinite M, M^{λ}/D is λ^{++}-universal.

In [4] the authors proved that the transfer principle (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ) implies for all regular filters D on λ

(1)_{D} For all M in a language of size ≤ λ, M^{λ}/D is λ^{++}-universal.

(2)_{D} If M_{i} and N_{i} are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ^{+} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D.

Assuming 2^{λ} = λ^{+}, (2)_{D} is equivalent to:

(2′)_{D} For M_{i}, N_{i} as in (2)_{D} of cardinality ≤ λ^{+}, ∏_{i} M_{i}/D ≅ ∏_{i} N_{i}/D.

We note that regularity is necessary for (1_{D}). I.e.

Lemma 1 For any filter D on an infinite cardinal λ, if for all infinite N the structure N^{λ}/D is λ^{+}-universal, then D is regular.

Proof. For k = 1, 2 let M_{k} = ⟨M_{k}, P_{i}^{k}⟩_{i<λ}, where M_{1} = λ, M_{2} = λ + 1 and the P_{i}^{k} are defined as follows. Let k = 1 and let D_{0} be a regular filter on λ. Let {A_{i}} ⊆ D_{0} witness the regularity of D_{0}. Thus for α < λ, {i < λ|α ∈ A_{i}} is finite. Set P_{i}^{1} = A_{i}. Now let k = 2. Let P_{i}^{2} = A_{i} ∪ {λ}. Now let D be any ultrafilter on λ and suppose there is an elementary embedding g mapping M_{2} into M_{1}^{λ}/D. Let g(λ) = [f] and let X_{α} = {i|f(i) ∈ P_{α}^{1}}. For each α < λ, a ∈ P_{α}^{2} implies X_{α} ∈ D. It is easy to see that {X_{α}}_{α<λ} is a regular family in D. □

We note that a similar argument can be used to show that (1)_{D} fails if the language of M has size λ^{+}.

This was a partial answer to the above Conjectures 18 and 19. In this paper we show the converse for singular strong limit λ. Under GCH this is necessary as by Chang’s Two Cardinal Theorem the transfer principle (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ) can only fail, in the presence of GCH, for singular λ. It is known that (ℵ_{1}, ℵ_{0}) ↛ (ℵ_{ω+1}, ℵ_{ω}) + GCH is consistent relative to the consistency of a supercompact cardinal. It follows that the statement (2)_{D}is independent of ZFC relative to the consistency of supercompact cardinals. On the other hand (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ) holds for all λ if V = L.

In fact we show more. The results of [4] were obtained using a finitary version, denoted here by □_{λ,D}^{fin}, of the combinatorial principle □_{λ}^{b^{∗}} from [6], which is equivalent for all λ to (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ). We showed in [4] that whenever λ is singular strong limit, □_{λ,D}^{fin} is actually equivalent to □_{λ}^{b^{∗}}, using Theorem 2.3 and Remark 2.5 of [6]. Thus □_{λ,D}^{fin} is equivalent to (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ), again for λ singular strong limit. The consistency of e.g. GCH+¬□_{λ}^{b^{∗}} follows. Precisely we showed:

Lemma 2 [4] Let D be a regular filter on λ where λ is a singular strong limit cardinal. Then □_{λ,D}^{fin} is equivalent to □_{λ}^{b^{∗}}.

The final piece needed for obtaining the transfer principle from (1)_{D}, (2)_{D} and (2′)_{D} for singular strong limit λ involves proving their equivalence with the principle □_{λ,D}^{fin}, which equivalence is proved for all λ (Theorem 4).

We note that (2)_{D} is more robust than what was originally conjectured, i.e. we have given a condition on when player II has a winning strategy in the EF game of length λ^{+} on the two structures ∏_{i} M_{i}/D and ∏_{i} N_{i}/D. Thus again if λ is singular strong limit, then the model theoretic (1)_{D} and (2)_{D} are equivalent to the set theoretic (ℵ_{1}, ℵ_{0}) → (λ^{+}, λ).

We need the following definition, from Lemma 4 of [4]:

Definition 3 Let D be a regular filter on λ. If 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) Coherence: γ ∈ u_{i}^{ζ} ⇒ u_{i}^{γ} = u_{i}^{ζ} ∩ γ,

then we say that □_{λ,D}^{fin} holds.

Our main result:

Theorem 4 Assume λ ≥ ℵ_{0} and D is a regular filter on λ. Then the following conditions are equivalent:

(i) □_{λ,D}^{fin}.

(ii) If M_{i} and N_{i}, i < λ, are elementarily equivalent models of a language of cardinality ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ^{+} on ∏_{i} M_{i}/D and ∏_{i} N_{i}/D.

(iii) If M and N are structures of a language of cardinality ≤ λ, N ≡ M^{λ}/D and |N| ≤ λ^{+}, then there is a homomorphism N → M^{λ}/D.

(iv) If Δ is a set of quantifier-free formulas and M^{λ}/D satisfies every existential Δ-sentence (i.e. a sentence of the form ∃x⃗(ϕ_{1} ∧ ... ∧ ϕ_{n}), where each ϕ_{i} is in Δ) true in N, |N| ≤ λ^{+}, then there is a Δ-homomorphism N → M^{λ}/D, i.e. a homomorphism N → M^{λ}/D which preserves Δ formulas.

Additionally, if D is an ultrafilter, then (i) − (iv) are equivalent to

(v) If M is a structure in a language of cardinality ≤ λ, then M^{λ}/D is λ^{++}-universal.

Moreover in (ii), (iii) and (iv) we can equivalently assume that the models M_{i}, N_{i}, M and N have cardinality ≤ λ^{+}.

Proof. (i) → (ii), (i) → (iii) and (i) → (iv) follow from the ”Δ-existential” version of Theorem 2 of [4] which gives a Δ-homomorphism of N into M^{λ}/D for any set Δ of first-order formulas such that every Δ-existential sentence true in N is true in M. If D is an ultrafilter, [4] gives (i) → (v) and, on the other hand, (v) → (iii) is straightforward.

(ii) → (iii): It follows from N ≡ M^{λ}/D that there are M_{0} ≡ M and a homomorphism N → M_{0} (i.e. a mapping from N to M_{0} which respects the functions and relations of N) such that M_{0} has cardinality ≤ λ^{+}. By (ii) the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ^{+} on M_{0}^{λ}/D and M^{λ}/D. Using this winning strategy we get easily a homomorphism N → M^{λ}/D, by composing the appropriate mappings.

(iii) → (iv): Let M and N be as in (iv). Let N^{∗} be an expansion of N obtained by giving a name to every Δ-definable relation. Let (M^{λ}/D)^{∗} be obtained similarly from M^{λ}/D. Let M_{0}^{∗} ≡ (M^{λ}/D)^{∗} such that there is a homomorphism N^{∗} → M_{0}^{∗}. (The existence of such M_{0}^{∗} follows from the fact that we can find M_{0}^{∗} ≡ (M^{∗})^{λ}/D and a homomorphism N^{∗} → M_{0}^{∗}. But then (M^{∗})^{λ}/D is canonically embeddable into (M^{λ}/D)^{∗}). By (iii) there is a homomorphism M_{0}^{∗} → M^{λ}/D. Thus there is a Δ-homomorphism N → M^{λ}/D.

(iv) → (i): Let λ, D be given and let τ denote a language of cardinality ≤ λ. It suffices to prove the following Claim. There exist M, N such that

a) |M| = λ, |N| = λ^{+}

b) τ_{M} = τ_{N} and |τ_{N}| ≤ λ

c) M ≡ N

d) For Δ = the quantifier free formulas of τ_{M}, N has a Δ-homomorphism into M^{λ}/D, and hence □_{λ,D}^{fin} holds.

Proof. Let τ^{∗} = {F_{α} | α < λ} ∪ {<}, for F_{α} a unary function symbol. Let K be the family of all structures M such that

K1) M is a finite τ^{∗}-structure.

K2) The universe of M is {0, 1, …, k − 1}, for some k ∈ ℕ, k ≠ 0, denoted

η(M). K3) M ⊧ ∀x(F_{α}(x) ≤ x) for all α < λ. K4) If m_{1} = F_{α_{1}}^{M}(m), m_{2} = F_{α_{2}}^{M}(m) and m_{1} < m_{2}, then there exists a β < λ

such that m_{1} = F_{β}^{M}(m_{2}). K5) If F_{α_{2}}^{M}(m_{3}) = m_{2}, F_{α_{1}}^{M}(m_{2}) = m_{1} and m_{1} < m_{2} < m_{3}, then there exists

α_{3} < λ such that F_{α_{3}}^{M}(m_{3}) = m_{1}. K6) w(M) =_{df} {α | F_{α}^{M} is not the identity} is finite. K7) For m_{1} < m_{2} < k there is exactly one α such that m_{1} = F_{α}(m_{2})). We note that K is non-empty, taking K to be, e.g., a one element structure. Let {M_{i} | i < λ} list K. We will add the M_{i} together into one structure. I.e., we define a model M^{∗} for τ = τ^{∗} ∪ {E} such that a_{K}) The universe of M^{∗} = ∪{{i} × M_{i} | i < λ} b_{K}) E^{M^{∗}} = {⟨(i_{1}, m_{1}), (i_{2}, m_{2})⟩ | m_{1} < η(M_{i_{1}}), m_{2} < η(M_{i_{2}}) and i_{1} = i_{2}} c_{K}) <^{M^{∗}}= {⟨(i, m_{1}), (i, m_{2})⟩ | m_{1} < m_{2} < η(M_{i})} d_{K}) F_{α}^{M^{∗}}(i, m) = ⟨i, F_{α}^{M_{i}}(m)⟩.

Now for ρ < λ^{+} let h_{ρ} be a partial one to one function from λ onto ρ, and let ⟨a_{ρ} | ρ < λ^{+}⟩ be a set of new constant symbols. Subclaim. There is N^{∗} such that

a) N^{∗} is a τ^{∗∗} structure of cardinality λ^{+}, where τ^{∗∗} = τ ∪ {a_{ρ} | ρ < λ^{+}\} ∪ \{\overline{m}\}_{m∈M},

b) M^{∗} ≼ N^{∗} ↾ τ.

c) a_{ρ}E^{N^{∗}}a_{0} for ρ < λ^{+},

d) a_{ρ} <^{N^{∗}} a_{ξ}, for ρ < ξ < λ^{+},

e) N^{∗} ⊧ F_{j}(ā_{ρ}) = ā_{ϵ}, if h_{ρ}(j) = ϵ, for j < λ and ϵ < ρ < λ^{+}.

Proof of Subclaim. Let T = T h(M^{∗}, \overline{m})_{m∈M^{∗}} ∪ \{a_{ρ}Ea_{0}\}_{ρ<λ^{+}} ∪ \{a_{ρ} < a_{ξ} | ρ < ξ < λ^{+}} ∪ {F_{j}(a_{ρ}) = a_{ϵ} | h_{ρ}(j) = ϵ, ϵ < ρ < λ^{+}}. We claim that T is consistent. To see this, let

T_{0} = \{φ_{i}(\overline{m}\}_{i=1,...,n}∪\{a_{ρ_{i}}Ea_{0}\}_{i=1,...k}∪\{a_{ϵ_{i}} < a_{ζ_{i}}\}_{i=1,...,l}∪\{F_{α_{i}}(a_{μ_{i}}) = a_{ν_{i}}\}_{i=1,...,m}

be a finite part of T, where a_{i_{1}}, …, a_{i_{k}} and \overline{m}_{j_{1}}, …, \overline{m}_{j_{l}} are all the parameters occurring in T_{0}. Let I_{0} = {i | for some j = j_{1} …, j_{l}, m_{j} = (i, a), i < λ, a < η(M_{i})}. We can find M_{i_{0}}, i_{0} ∈ λ ∖ I_{0}, such that if we interpret the constants a_{ρ} in M_{i_{0}} and \overline{m}_{j_{i}} by m_{j_{i}} ∈ M^{∗}, then this expansion of M^{∗} is a model of T_{0} and thus T_{0} is consistent. The subclaim is proved.

Now let N^{∗} be as in claim 1 and let N = N^{∗} ↾ τ_{M}^{∗}. We note that the pair of structures N together with the M defined above satisfying a_{K})−d_{K}), satisfy the hypothesis of Theorem 2-(iv), i.e. (M^{∗})^{λ}/D satisfies every existential Δ-sentence true in N where Δ = the quantifier-free formulas of τ_{M}^{∗}. This is because N ≡ M^{∗} and these Δ-sentences are preserved under reduced products. Therefore by (iv) there is a Δ-homomorphism g: N → (M^{∗})^{λ}/D. Let g(a_{ρ}) be denoted by f_{ρ}/D.

We are now ready to define the sets u_{i}^{ζ} referred to in (i)-(iv) of the condition □_{λ,D}^{fin}. To this end, for ϵ < ρ < λ^{+}, ρ ≥ λ, define

A_{ϵ,ρ} = {j < λ | M^{∗} ⊧ (f_{ρ}(j) > f_{ϵ}(j)) ∧ F_{i(ϵ,ρ)}(f_{ρ}(j)) = f_{ϵ}(j)}.

Note that if ϵ < ρ < λ^{+}, ρ ≥ λ, then A_{ϵ,ρ} ∈ D, since (M^{∗})^{λ}/D ⊧ (g(a_{ϵ}) < g(a_{ρ})) ∧ F_{i(ϵ,ρ)}(g(a_{ρ})) = g(a_{ϵ}). For each ρ ∈ (λ, λ^{+}) and j ≤ λ define

W_{ρ,j} = {ϵ < ρ | ϵ ≥ λ and j ∈ A_{ϵ,ρ}}.

First note that without loss of generality

(∗)_{1}: M^{∗} ⊧ f_{ρ}(j)Ef_{0}(j) for every j, ρ. We claim that

(∗)_{2}: if we choose u_{j}^{ρ} =_{df} W_{ρ,j} then ⟨u_{j}^{ρ}|ρ < λ^{+}, j < λ⟩ exemplifies □_{λ,D}^{fin}, i.e. these objects satisfy the demands (i) − (iv) of Definition 3. By (∗)_{1} we can let f_{ρ}(j) = (i_{j}, m(i_{j}, ρ)). Clearly if we prove (∗)_{2} we are done.

(i), (ii): W_{ρ,j} is a finite subset of ρ:

{ϵ < ρ | ϵ ≥ λ and j ∈ A_{ϵ,ρ}} = {ϵ < ρ | ϵ ≥ λ and M ⊧ F_{i(ϵ,ρ)}(f_{ρ}(j)) = f_{ϵ}(j)}

= {ϵ < ρ | ϵ ≥ λ and M_{i_{0}} ⊧ F_{i(ϵ,ρ)}^{M_{i_{0}}}(f_{ρ}(j)) = f_{ϵ}(j)}.

But w(M_{i_{0}}) is finite, and therefore so is W_{ρ,j}. Thus if n_{i} is taken to be w(M_{i_{o}}) then (i) and (ii) of □_{λ,D}^{fin} are satisfied.

(iv): (coherency) holds of W_{ρ,j}, i.e. if ρ_{1} < ρ_{2} < λ^{+} and j < λ is given, if ρ_{1} ∈ W_{ρ_{2},j} then W_{ρ_{1},j} = W_{ρ_{2},j} ∩ ρ_{1}. Why? Let α ∈ W_{ρ_{1},j}. Then λ ≤ α < ρ_{2} and j ∈ A_{α,ρ_{1}}. But then M^{∗} ⊧ F_{i(α,ρ_{1})}(f_{ρ_{1}}(j)) = f_{α}(j) and therefore M_{i_{0}} ⊧ F_{i(α,ρ_{1})}^{M_{i_{0}}}(f_{ρ_{1}}(j)) = f_{α}(j). ρ_{1} ∈ W_{ρ_{2},j} and therefore j ∈ A_{ρ_{1},ρ_{2}}.

This means M_{i_{0}} ⊧ F_{i(ρ_{1},ρ_{2})}^{M_{i_{0}}}(f_{ρ_{2}}(j)) = f_{ρ_{1}}(j). By the definition of M_{i_{0}}, there

is β such that M_{i_{0}} ⊧ F_{β}^{M_{i_{0}}}(f_{ρ_{2}}(j)) = f_{α}(j). But β = i(α, ρ_{2}) and j ∈ A_{α,ρ_{2}} and therefore α ∈ W_{ρ_{2},j}. For the other direction suppose α ∈ W_{ρ_{2},j} ∩ ρ_{1}. Then α ≥ λ and j ∈ A_{α,ρ_{2}}, i.e. M_{i_{0}} ⊧ F_{i(α,ρ_{2})}^{M_{i_{0}}}(f_{ρ_{2}}(j)) = f_{α}(j). ρ_{1} ∈ W_{ρ_{2},j}

means that as before j ∈ A_{ρ_{1},ρ_{2}}, i.e. M_{i_{0}} ⊧ F_{i(ρ_{1},ρ_{2})}^{M_{i_{0}}}(f_{ρ_{2}}(j)) = f_{ρ_{1}}(j). But

then since α < ρ_{1}, there is β such that M_{i_{0}} ⊧ F_{β}^{M_{i_{0}}}(f_{ρ_{1}}(j)) = f_{α}(j), i.e. as before j ∈ A_{ρ_{1},j} and α ∈ W_{ρ_{1},j}.

To see that (iii) is satisfied, let B ⊆ λ^{+} be a finite set of ordinals such that B ∩ λ = ∅, and let ρ be such that B ⊆ ρ < λ^{+}. We wish to show that {j | B ⊆ W_{ρ,j}} ∈ D. Let B = {j_{1}, …, j_{n}}. Recall that by (e) of the subclaim, N^{∗} ⊧ F_{i(j,ρ)}(a_{ρ}) = a_{j} whence

C_{k} = {i | M^{∗} ⊧ F_{i(j_{k},ρ)}(f_{ρ}(i)) = f_{j_{k}}(i)} ∈ D,

for each k = 1, …, n. Also by definition if i ∈ C_{k} then i ∈ A_{j_{k},ρ} whence j_{k} ∈ W_{ρ,i}. Thus C_{1} ∩ ⋯ ∩ C_{n} ⊆ {i | B ⊆ W_{ρ,j}} ∈ D. The claim is proved.

Now if we transfer the sets u_{j}^{ρ}, λ ≤ ρ < λ^{+} to all of λ^{+}, (iv) implies (i), proving the Claim.

The claim concerning the equivalent formulations involving models of size ≤ λ^{+} follows from the fact that in the derivation (iv) → (i) above we have |M| = λ and |N| = λ^{+}. Thus Theorem 4 is proved. □

Corollary 5 Assume λ ≥ ℵ_{0}, 2^{λ} = λ^{+} and D is a regular filter on λ. Then the following are equivalent:

(i) □_{λ,D}^{fin}.

(ii) If M_{i} and N_{i}, i < λ, are elementarily equivalent models of a language of cardinality ≤ λ, and |M_{i}|, |N_{i}| ≤ λ^{+} then ∏_{i} M_{i}/D ≅ ∏_{i} N_{i}/D.

Corollary 6 GCH + the failure of properties (i)-(iv) of Theorem 4 for λ = ℵ_{ω} is consistent relative to the consistency of supercompact cardinals.

Proof. Assume GCH and (ℵ_{1}, ℵ_{0}) ↛ (ℵ_{ω+1}, ℵ_{ω}). It is well-known (cf. [1] Proposition 4.3.5) that there is a regular ultrafilter D on ℵ_{ω}. The principle □_{ℵ_{ω}}^{b^{∗}} fails. Thus □_{ℵ_{ω},D}^{fin} fails by [4]. By Theorem 4, (i)-(v) fail for the regular ultrafilter D. □

A drawback of Corollary 6 is that it deals with filters rather than ultrafilters, which was originally the most interesting case. This case will be dealt with in a work in preparation.

References

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

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

[3] J. Kennedy and S. Shelah, On embedding models of arithmetic of cardinality ℵ_{1} into reduced powers, Fundamenta Mathematicae, Volume 176, Issue 1, 2003, 17–24.

[4] J. Kennedy and S. Shelah, On regular reduced products. Journal of Symbolic Logic, Volume 67, 2002, 1169–1177.

[5] S. Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. Math., 10, 1971, 224–233,

[6] 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.