ON HANF NUMBERS OF THE INFINITARY ORDER PROPERTY DRAFT

RAMI GROSSBERG AND SAHARON SHELAH

Abstract. We study several cardinal, and ordinal–valued functions that are relatives of Hanf numbers. Let κ be an infinite cardinality, and let T ⊆ L_{κ^{+},ω} be a theory of cardinality ≤ κ, and let γ be an ordinal ≥ κ^{+}. Consider

(1) μ_{T}^{∗} (γ, κ) := min\{μ^{∗} : ∀φ ∈ L_{∞,ω}, with rk(φ) < γ, \underline{if} T has the (φ, μ^{∗})- order property \underline{then} there exists a formula φ′(x; y) ∈ L_{κ^{+},ω}, such that for every χ ≥ κ, T has the (φ′, χ)-order property }.

(2) μ^{∗}(γ, κ) := sup{μ_{T}^{∗} (γ, κ) | T ∈ L_{κ^{+},ω}}.

We discuss several other related functions, sample results are: · It turns out that \underline{if} T has the (φ, μ^{∗}(γ, κ))-order propery for some φ ∈

L_{∞,ω}, with rk(φ) < γ \underline{then} for every χ > κ we have that I(χ, T) = 2^{χ} holds.

· For every κ and γ as above there exists an ordinal δ^{∗}(γ, κ) such that

μ^{∗}(γ, κ) = ℶ_{δ^{∗}(γ,κ)}, · δ^{∗}(γ, κ) ≤ (|γ|^{κ})^{+}, · for κ with uncountable cofinality, we have that δ^{∗}(γ, κ) > |γ|^{κ} and · the ordinal δ^{∗}(γ, κ) is bounded below by the Galvin–Hajnal rank of a re-

duced product. For many cardinalities we have better bounds, some of the bounds obtained

using Shelah’s pcf theory. The function μ^{∗}(γ, κ) is used to compute bounds to the values of the function \overline{μ}(λ, κ) we studied in a previous paper.

Date: June 9, 1998. The authors thank the United States - Israel Binational Science foundation for supporting this

research as well as the Mathematics department of Rutgers University where part of this research was carried out.

Partially supported by the United States-Israel Binational Science Foundation and by the National Science Fundation, NSF-DMS97-04477.

This paper replaces item # 259 from Shelah’s list of publications.

1. Introduction

Let χ be an infinite cardinality, and suppose that T ⊆ L_{χ,ω} (notice that when χ = ω we are dealing with first-order theories).

The fundamental meta-problem in the area of classification theory can be stated as:

Problem 1.1. What is the structure of Mod(T)?

A more precise (and concrete) test-question is:

Problem 1.2. What are the possible functions I(·, T) : Card → Card? (where I(λ, T) stands for the number of isomorphism types of models for T of cardinality λ).

A much more precise (and a very difficult) particular case of 1.2 is the following

Conjecture 1.3. (Shelah about 1976) Let ψ ∈ L_{ω_{1},ω} be given. If there exists a cardinality μ > ℶ_{ω_{1}} such that I(μ, ψ) = 1 then for every μ > ℶ_{ω_{1}}, I(μ, ψ) = 1 holds.

A possible approach to Problem 1.1 and its relatives, is to try to imitate Classification theory for elementary classes (see [Sh c]). Namely it would be desirable to find properties parallel to stability, superstability etc. Much work has been done in the last 25 years (see for example – [Sh 48],[Sh 87a], [Sh 87b],[Sh 88],[Sh 300], [Sh 394] [MaSh],[GrSh2], or [Sh 299] for a general survey). In this article we concentrate in dealing with the parallel (for infinitary languages) to instability. The following can be viewed as a definition of stability for first-order theories:

Fact 1.4. ([Sh 16]) Let T be a complete first-order theory. The following are equivalent:

(1) T is unstable

(2) There exist a formula φ(x; y) ∈ L(T), a model M for T, and a set {a_{n} : n < ω} ⊆ M such that ℓ(x) = ℓ(y) = ℓ(a_{n}) for every n < ω, and for all n, k < ω we have n < k ⟺ M ⊧ φ[a_{n}; a_{k}].

Condition 2 in Fact 1.4 is called the order-property. One of the important properties of unstable theories is the following:

Fact 1.5. [Sh 12] Let T be a complete first-order theory. If T is unstable then for every μ > |T | we have that I(μ, T) = 2^{μ}.

An inspection of the proof of 1.5 shows that the hypothesis that T is a complete first-order unstable theory could be replaced by the following property:

(∗)_{T} There is an expansion L′ of L(T) with built-in Skolem functions and an L′-structure M, a “formula” φ(x; y) , and there exists I := {a_{i} : i < ω} ⊆ M a sequence of L′-indiscernibles such that ℓ(x) = ℓ(y) = ℓ(a_{n}) for all n < ω, M is the Skolem Hull of I, M ↾ L(T) ⊧ T and n < m ⟺ M ⊧ φ[a_{n}; a_{m}] holds for every n, m < ω.

By “formula” we mean that φ is in any logic (over the vocabulary L′) such that φ is preserved by isomorphisms of L(T)-structures.

The condition in Fact 1.4 seems to be a natural candidate for a definition of instability for infinitary logics. Since the compactness theorem fails even for L_{ω_{1},ω} the next definition is the replacement of the (the first-order) order-property.

Definition 1.6. Let T ⊆ L_{χ,ω}, φ(x; y) ∈ L_{∞,ω}, and let μ be a cardinality.

(1) We say that M has the (φ, μ)-order property iff there exists {a_{i} : i < μ} ⊆ M such that ℓ(x) = ℓ(y) = ℓ(a_{i}) < ω, and for every i, j < μ we have i < j ⟺ M ⊧ φ[a_{i}; a_{j}].

(2) T has the (φ, μ)-order property iff there exists M ⊧ T such that M has the (φ, μ)-order property.

(3) T has the (φ, ∞)-order property iff T has the (φ, μ)-order property for every μ.

(4) Let λ and μ be cardinalities, we say that T has the (L_{λ,ω}, μ)-order property iff there exists φ ∈ L_{λ,ω} such that T has the (φ, μ)-order property.

Remark 1.7. (1) In light of the last definition, Fact 1.4 can be restated as (for first-order complete T): T is unstable iff T has the (L_{ω,ω}, ℵ_{0})-order property.

(2) It is not difficult to see (using [Mo], see 1.10 below) that the following implication is true: If T has the (L_{λ^{+},ω}, ∞)-order property then (∗)_{T} holds.

A natural question to ask in this context is: Given a theory T and a cardinality μ, does T have the (L_{λ^{+},ω}, μ)-order property? The main object of study in [GrSh1] was the function \overline{μ}(λ, κ). The following μ^{∗}(λ, κ) is a relative of \overline{μ}(λ, κ) from [GrSh1].

Definition 1.8. Let κ ≤ λ.

(1) Let ψ ∈ L_{κ^{+},ω}, μ_{ψ}^{∗}(λ, κ) := min{μ^{∗} : ∀φ ∈ L_{λ^{+},ω} if ψ has the (φ, μ^{∗})- order property, then there exists a formula φ′(x; y) ∈ L_{κ^{+},ω}, such that ψ has the (φ′, ∞)-order property }.

(2) μ^{∗}(λ, κ) := sup{μ_{ψ}^{∗}(λ, κ) | ψ(x; y) ∈ L_{κ^{+},ω}}.

Remark 1.9. The idea behind Definition 1.8 is that when ψ has the (L_{λ^{+},ω}, μ^{∗}(λ, κ))-order property then (by Remark 1.7 and (∗)_{ψ}) for every χ > κ I(χ, ψ) = 2^{χ}.

Already in [Sh 16] Shelah realized the importance of the above concept, it did not appear there explicitly. Only in [Gr] (see [GrSh1]) these functions were identified. The previous definition is a generalization of one from [GrSh1], see Definition 1.8. Shelah’s fundamental result from [Sh 16] can be restated as:

Fact 1.10. ([Sh 16]) For every κ ≤ λ, we have μ^{∗}(λ, κ) ≤ μ_{0}(λ, 1)^{1}.

Recall that μ_{0}(λ, 1) ≤ ℶ_{(2^{λ})^{+}} and for some λ’s we have equality. The function μ^{∗} is very different from μ_{0}: The following is a dramatic improvement (for κ = ℵ_{0}) of Fact 1.10:

Theorem 1.11. ([GrSh1]) For every λ ≥ ℵ_{0}, we have μ^{∗}(λ, ℵ_{0}) ≤ ℶ_{λ^{+}}.

It turns out that even for first-order theories the above question is interesting (for κ = |L| = ℵ_{0}, T is a complete first-order theory in L, we could ask what is an upper bound of μ_{T}^{∗} (λ, ℵ_{0})?). Since there are cases when T is stable (i.e. there is no first-order formula defining an ω-sequence in a model of T) but still T has a hidden instability (like in the case of stable theories without the omitting-types order property).

There is a natural class of examples of theories that do not have a first-order formula exemplifying the order-property but do have an infinitary order property. Any stable first-order theory that has the omitting types order-property has the (L_{ω_{1},ω}, ∞)-order property but not the (L_{ω,ω}, ℵ_{0})-order property (see [Sh 200]).

Already from Morley’s omitting-types theorem it follows that given T and φ as above there exists μ := μ(T, φ) such that if T has the (φ, μ)-order property then ∀λ ≥ χ, T has the (φ, λ)-order property. The bound obtained from repeating the argument in the proof of Morley’s omitting types theorem (see [Sh 16]) is: μ(T, φ) ≤ max{Hanf(T), Hanf(φ)}. Where Hanf(T) and Hanf(φ) are the Hanf numbers of T and the logic containing φ (respectively).

Let χ > ℵ_{0} (T still may be first-order). Our object is to find upper bounds on μ. It turns out that for φ ∈ L_{∞,ω} − L_{χ,ω} there is a cardinality μ^{∗} := μ^{∗}(T, φ)^{2}, such that the following implication holds: If T has the (φ, μ^{∗})-order property then there exists a formula φ′ ∈ L_{χ,ω} (it is a collapse of φ) such that T has the (φ′, λ)- order property for every λ ≥ χ.

1μ_{0}(λ, λ) is the usual Morley number to be introduced in Definition 2.2 below. It is known that μ_{0}(λ, λ) = μ_{0}(λ, 1)

2The surprise is that often μ^{∗}(T, φ) is much smaller than μ(T, φ).

In this paper we present a systematic study of several cardinal and ordinal valued functions related to the infinitary order property. This is a continuation of [GrSh1], we deal with similar problems and improve many results. This is achieved via a generalization of the original problem (dealing with new cases) while obtaining often better estimates to earlier bounds. The reader is not expected to be familiar with [GrSh1].

Notation: Everything is standard. Often x, y, and z will denote free variables or finite sequences of variables, when x is a sequence ℓ(x) denote its length. It should be clear from the context whether we deal with variables or sequences of variables. L will denote a similarity type (also known as-language or signature), Δ will stand for a set of L formulas. M and N will stand for L - structures, |M| the universe of the structure M, ∥M∥ the cardinality of the universe of M. Given a fixed structure M, subsets of its universe will be denoted by A, B, C, and D. So when we write A ⊆ M we really mean that A ⊆ |M|, while N ⊆ M stands for “N is a submodel of M”. Let M be a structure. By a ∈ M we mean a ∈ |M|, when a is a finite sequence of elements then a ∈ M stands for “all the elements of the sequence a are elements of |M|”. For cardinalities κ ≤ λ, let S_{<κ}(λ) := {X ⊆ λ : |X| < κ}. When T is a first-order theory, Γ denotes a set of T -types over the empty set (not necessarily complete types). EC(T, Γ) := {M : M ⊧ T, ∀p ∈ Γ M omits the type p}. When T is first-order, L ⊆ L(T), and Γ is a set of T -types by PC(T, Γ, L) we denote the following {M ↾ L : M ⊧ T, ∀p ∈ Γ M omits the type p}; namely EC(T, Γ) = PC(T, Γ, L(T)). λ, μ, κ, and χ will stand for infinite cardinalities; α, β, γ, δ, ζ, and ξ are ordinals. References of the form “Theorem IV 3.12” are to [Sh c]. For φ ∈ L_{∞,ω}, let Sub(φ) be the set of subformulas of φ, now let

rk(φ) := \{ \begin{matrix}0 & if φ is atomic \\ Sup\{rk(χ) + 1 : χ ∈ Sub(φ)\} & otherwise. \end{matrix}

2. Review

C.C. Chang in [Ch] have made the following fundamental observation:

Fact 2.1. Let κ be an infinite cardinality, and let L be a similarity type of cardinality no more than κ. Given ψ ∈ L_{κ^{+},ω}, there exist a similarity type L′ ⊇ L, a first-order theory T in L′, and a set of T -types Γ (all three of cardinality less or equal to κ) such that Mod(ψ) = PC(T, Γ, L).

Instead of studying Mod(ψ) directly for an infinitary theory ψ it is enough to consider a class of reducts of models of a first-order theory that omits a set of types.

W. Hanf and M. Morley [Mo], have recognized the importance of the following concept:

Definition 2.2. Let T be a first-order theory, and let Γ be a set of T -types. The Morley number^{3} of T and Γ, is the following:

(1) μ_{0}(T, Γ) := min{μ : ∃M ∈ EC(T, Γ) ∥M∥ ≥ μ ⇒ ∀χ ≥ |T | ∃N ∈ EC(T, Γ) of cardinality ≥ χ}.

(2) Let λ, κ be cardinalities.

μ_{0}(λ, κ) := sup{μ_{0}(T, Γ) : |T | ≤ λ, Γ a set of T -types of cardinality ≤ κ}^{4}.

Morley (among other things) have shown that μ_{0}(ℵ_{0}, ℵ_{0}) = ℶ_{ω_{1}}. His most general result is stated as Theorem 2.4 below. Shelah in [Sh 78] have dealt with what is an interpolant of μ_{0}(T, Γ) and μ_{0}(λ, κ):

μ_{0}(T, κ) := sup{μ_{0}(T, Γ) : Γ a set of T -types, |Γ| ≤ κ}.

It is not difficult to conclude from the proof of Morley’s categoricity theorem that when T is a countable and ℵ_{0}-stable theory then μ_{0}(T, ·) ≤ ℵ_{1}. Shelah in [Sh 78] studied the effect that stability of T has on the upper bounds on μ_{0}(T, κ). This work was continued about ten years later by Hrushovski and Shelah in [HrSh].

In this paper, since our main goal is the study of unstable theories (or theories that are not stable in a weak sense) we will ignore the effect that the stability of T may have on the function μ_{0}(T, κ).

The modern era in the study of Hanf numbers begun with the paper of Barwise and Kunen [BaKu]. They studied systematically the relationship between the function μ_{0} and the first ordinal that exemplify the undefinability of well ordering in classes of models that omit a set of types. Below we recall an ordinal-valued function δ_{0}(λ, κ) that is related to μ_{0}(λ, κ) in a nice way.

3Some authors call this the Hanf number of T and the Γ

4We hope that the reader is not bothered by this abuse of notation. We are using the same letter μ_{0} to denote entirely different (but related) functions. They can be distinguished by the type of the arguments they take.

Definition 2.3. Let λ and κ be infinite cardinalities, T varies over consistent firstorder theories such that L(T) ⊇ {P, <} when P is a unary predicate and T ⊢“< linearly orders P ”. δ_{0}(λ, κ) := min{δ : |T | ≤ λ, Γ a set of T -types, |Γ| ≤ κ if for every δ′ < δ there exists M ∈ EC(T, Γ) such that otp(P^{M}, <^{M}) ≥ δ′ then there exists N ∈ EC(T, Γ) s.t. (P^{N}, <^{N}) is not well ordered }.

The following is a restatement of Morley’s “other” important theorem:

Fact 2.4. (Theorem VII 5.5) μ_{0}(λ, κ) = ℶ_{δ_{0}(λ,κ)}.

The following ordinal and cardinal-valued functions are from §4 of [GrSh1]:

Definition 2.5. Suppose T is a first-order theory such that L(T) is containing the predicates {<, P } and

T ⊢ [< is a linear order] ∧ [ <↾ P is a linear order on the unary predicate P].

(1) δ_{1}(θ, λ, κ) := min{δ : Γ a set of T -types, |Γ| ≤ λ, |T | ≤ κ if ∀δ′ < δ ∃M ∈ EC(T, Γ) with otp(P^{M}, <^{M}) ∈ On ∩ θ^{+} and otp(M −P, <^{M}) ≥ δ′, then ∃N ∈ EC(T, Γ) s.t. otp(P^{N}, <^{N}) ∈ On∩κ^{+} and (N − P^{N}, <^{N}) is not well ordered }.

(2) μ_{1}(θ, λ, κ) := min{μ : Γ| ≤ λ, |T | ≤ κ Γ a set of T -types, if ∃M ∈ EC(T, Γ) ∥M∥ ≥ μ with otp(P^{M}, <^{M}) ∈ On ∩ θ^{+} then for every χ ≥ κ ∃N ∈ EC(T, Γ) of cardinality at least χ such that otp(P^{N}, <^{N}) ∈ On ∩ κ^{+} }.

(3) When θ = λ we will omit the first parameter-θ

In an analogous way to Fact 2.4 we can prove the following equality:

Theorem 2.6. For every κ ≤ λ ≤ θ we have μ_{1}(θ, λ, κ) = ℶ_{δ_{1}(θ,λ,κ)}.

From now on we concentrate on the case that θ = λ and work with the functions δ_{1}(λ, κ) and μ_{1}(λ, κ). The arguments for the functions with three parameters are essentially similar (they require an additional technical effort, but require no new ideas). Note that by 2.1 working with two parameter functions is sufficient for L_{λ^{+},ω}. The new point is that we are able to show that μ_{1}(λ, κ) ≥ ℶ_{δ_{1}(λ,κ)}. The proof of Theorem 2.6 is similar to that of Theorem VII 5.5, we skip its proof, since later we will prove a related theorem (Th. 3.6) whose proof is similar (but is little harder).

The next proposition provides a lower bound for δ_{1}(λ, κ), it follows immediately from the definitions (in Theorem 3.8 a better lower bound is obtained).

Proposition 2.7. For λ ≥ κ we have that δ_{1}(λ, κ) ≥ δ_{1}(κ, κ) ≥ δ_{0}(κ, κ) = δ_{0}(κ, 1).

In the following proposition the connection between the last definition and the order property is clarified.

Theorem 2.8. Let κ ≤ λ, be cardinalities. ℶ_{λ^{+}} ≤ μ^{∗}(λ, κ) ≤ μ_{1}(λ, κ).

Proof. First we show that μ^{∗}(λ, κ) ≤ μ_{1}(λ, κ). Let ψ ∈ L_{κ^{+},ω}, and φ(x; y) ∈ L_{λ^{+},ω} be given. Suppose ψ has the (φ, μ_{1}(λ, κ))-order property we need to find a formula φ′ ∈ L_{κ^{+},ω} such that ψ has the (φ′, ∞)-order property.

By Fact 2.1 there exists a first-order theory T in a similarity type L(T) that extends L, and there is a set Γ of T -types of cardinality ≤ κ such that PC(T, Γ, L) = Mod(ψ). By following the inductive definition of the formula φ we may identify φ with a function f from the set P into the set L ∪ {∧, ¬, (,), =} ∪ {x_{i} : i < κ}.

Let χ be a regular large enough such that

{L_{λ^{+},ω}, L_{κ^{+},ω}, T, Γ, L, φ, f, P, ψ, λ^{+}, μ_{1}(λ, κ), δ_{1}(λ, κ)} ∪ μ_{1}(λ, κ) ⊆ H(χ).

In addition we require that the structure ⟨H(χ), ∈⟩ reflects all the relevant properties of the above sets. Let P be the rank of the formula φ, note that it is an ordinal less than λ^{+}. Let 𝔄′ ≺ ⟨H(χ), ∈, … ⟩ of cardinality μ_{1}(λ, κ) such that μ_{1}(λ, κ)^{𝔄′} = μ_{1}(λ, κ) (so μ_{1}(λ, κ) + 1 ⊆ 𝔄′), fix a bijection G from μ_{1}(λ, κ) onto the universe of 𝔄′, and let 𝔄 := ⟨𝔄′, G⟩. By the definition of μ_{1}(λ, κ), for every χ ≥ κ there exists 𝔅_{χ} ≡ 𝔄 of cardinality χ such that 𝔅_{χ} omits the types from Γ, κ^{𝔅_{χ}} = κ, and P is an ordinal less than κ^{+} (just apply the Mostowski collapse on 𝔅_{χ}). Using P^{𝔅_{χ}}, and f^{𝔅_{χ}} we know (in 𝔅_{χ}) that φ^{𝔅_{χ}} ∈ L_{κ^{+},ω}^{𝔅_{χ}}, but since κ^{𝔅_{χ}} = κ we have that φ^{𝔅_{χ}} ∈ L_{κ^{+},ω} is a formula as required in the definition of μ^{∗}(λ, κ).

To see that μ^{∗}(λ, κ) ≥ ℶ_{λ^{+}}: It is enough to show that for every α < λ^{+} there exist a sentence ψ_{α} ∈ L_{κ^{+},ω}, and a formula φ_{α} ∈ L_{λ^{+},ω} such that ψ_{α} has the (φ_{α}, ℶ_{α})-order property and ψ_{α} does not have the (L_{κ^{+},ω}, ∞)-order property.

Before proving this we need several tools.

Notation: The sentence ψ_{α} will be defined as a the theory of a well founded tree. We deal with well-founded trees whose vertices are decreasing sequences of ordinals, the root of the tree 𝕋 is denoted by rt(𝕋), for an element x ∈ 𝕋 let Suc_{𝕋}(x) stand for the set of immediate succssesors of x, and 𝕋[x] stands for the subtree of 𝕋 consisting of the elements that are greater or equal to x.

Definition 2.9. Let 𝕋 be a well founded tree.

(1) For x ∈ 𝕋 let Dp_{𝕋}(x) = β the depth of x in 𝕋 defined by induction on β: (a) if Suc_{𝕋}(x) = then Dp_{𝕋}(x) = 0.

(b) if for every y ∈ Suc_{𝕋}(x) we have Dp_{𝕋}(y) < β, and for every γ < β there exists z ∈ Suc_{𝕋}(x) of such that Dp_{𝕋}(z) ≥ γ then Dp_{𝕋}(x) = β.

(2) The depth of 𝕋 is Dp(𝕋) := sup{ Dp_{𝕋}(x) : x ∈ 𝕋}.

Proposition 2.10. Let 𝕋 be a well-founded tree, Dp(𝕋) = Dp_{𝕋}(rt(𝕋)).

Proof. Trivial. □_{2.10}

Claim. For every α there exists a well-founded tree 𝕋_{α} of depth α such that ∥𝕋_{α}∥ ≤ |α| + ℵ_{0}.

Proof. By induction on α:

For α = 0; Simply let 𝕋_{0} := ⟨⟩.

For α = β + 1; Suppose 𝕋_{β} is a tree of depth β. Let 𝕋_{α} := {⟨⟩} ∪ {⟨⟩ˆ η : η ∈ 𝕋_{β}}. The order on 𝕋_{α} is the obvious.

For α a limit ordinal; By the induction hypothesis let {𝕋_{β} : β < α} be pairwise disjoint trees, each of depth β. Define 𝕋_{α} to be the tree {⟨⟩} ∪ {⟨⟩ˆ η : η ∈ 𝕋_{β}, β < α}. □_{2}

Definition 2.11. (1) Let 𝕋_{1}, 𝕋_{2} be well-founded trees, and let α be an ordinal. By induction on α define when 𝕋_{1} ≈_{α} 𝕋_{2}:

(a) For α = 0, always 𝕋_{1} ≈_{α} 𝕋_{2}.

(b) For α ≠ 0, if for every β < α and for every x_{1} ∈ Suc_{𝕋_{1}}(rt(𝕋_{1})) there exists x_{2} ∈ Suc_{𝕋_{2}}(rt(𝕋_{2})) such that 𝕋_{1}[x_{1}] ≈_{β} 𝕋_{2}[x_{2}], and for every x_{2} ∈ Suc_{𝕋_{2}}(rt(𝕋_{2})) there exists x_{1} ∈ Suc_{𝕋_{1}}(rt(𝕋_{1})) such that 𝕋_{2}[x_{2}] ≈_{β} 𝕋_{1}[x_{1}].

(2) A tree 𝕋 is called simple iff there are no distinct x_{1}, x_{2} ∈ Suc_{𝕋}(rt(𝕋)) such that Dp_{𝕋}(x_{1}) = Dp_{𝕋}(x_{2}) and 𝕋[x_{1}] ≈_{Dp_{𝕋}(x_{1})} 𝕋[x_{2}].

Proposition 2.12. Let 𝕋_{1}, 𝕋_{2} be trees, and let α be an ordinal. If 𝕋_{1} ≈_{α} 𝕋_{2} then one of the following conditions holds:

(1) Dp(𝕋_{1}) = Dp(𝕋_{2}), or

(2) Dp(𝕋_{1}) ≥ α and Dp(𝕋_{2}) ≥ α.

Proof. Easy, by induction on α. □_{2.12}

Claim. For every ordinal α there exists a family of simple trees {𝕋_{i} : i < ℶ_{α}}, such that for every i < ℶ_{α}

(1) ∥𝕋_{i}∥ ≤ ℶ_{α},

(2) i ≠ j ⇒ 𝕋_{i} ≉_{ω+α} 𝕋_{j},

(3) Dp(𝕋_{i}) = ω + α + 1.

Proof. By induction on α:

For α = 1; First construct ℵ_{0} simple trees {𝕋_{n} ⊆^{ω>} ω : n < ω} such that 𝕋_{0} := {⟨⟩}, 𝕋_{n+1} := {⟨n + 1⟩} ∪ 𝕋_{n} when the order is an extention of the order on 𝕋_{n}; ⟨⟩ is the root, and ⟨n + 1⟩ is a new immediate successor of the root incomparable with the elements of Suc_{𝕋_{n}}(⟨⟩). Now for every A ⊂ ω let

𝕋_{A} := {⟨ω⟩ˆ η : η ∈ 𝕋_{n}, n ∈ A} ∪ {ν ∈ 𝕋_{k} : k ∉ A}.

The order of 𝕋_{A} is defined as follows: ⟨ω⟩ is a new immediate sucessor of the root, the elements ⟨ω⟩ˆ η and ν are pairwise incomparable when η ∈ 𝕋_{n}, (n ∈ A) and ν ∈ 𝕋_{k}, (k ∉ A), and we require that ⟨ω⟩ˆ η_{1} < ⟨ω⟩ˆ η_{2} ⇔ η_{1} <_{𝕋_{n}} η_{2}. In order to see that A ≠ B ⊆ ω ⇒ 𝕋_{A} ≉_{ω+α} 𝕋_{B}: W.l.o.g. we may assume that ∃n ∈ A−B. Since 𝕋_{A}[⟨ω, n⟩] ≉_{ω} 𝕋_{B}[ν] for any ν ∈ Suc_{𝕋_{B}}(⟨ω⟩) (this is because 𝕋_{k} and 𝕋_{n} are inequivalent for k ≠ n).

For α ≠ 1; By the inductive hypothesis let {{𝕋_{i}^{β} : i < ℶ_{β}} : β < α} be disjoint trees satisfying the statement of the Theorem. Denote by S the set {⟨β, i⟩ : i < ℶ_{β}, β < α}. Fix an injective mapping from S into On − Sup(⋃_{β,i} 𝕋_{i}^{β}), denote by γ_{β,i} the image of the pair ⟨β, i⟩. For every γ < α, and for every A ⊆ S cardinality ℶ_{γ} define

𝕋_{A} := {⟨⟩} ∪ {⟨γ_{β,i}⟩ˆ η : η ∈ 𝕋_{i}^{β}, ⟨β, i⟩ ∈ A}.

The order on 𝕋_{A} is defined in the natural way: ⟨⟩ is the root, and

⟨β, i⟩ˆ η_{1} <_{𝕋_{A}} ⟨β, i⟩ˆ η_{2} iff η_{1} <_{𝕋_{i}^{β}} η_{2}.

The verification that Dp(𝕋_{A}) = ω + α + 1 is left to the reader. Suppose A ≠ B ⊆ ℶ_{α} both of cardinality ℶ_{β} for some β < α. We need to show that 𝕋_{A} ≉_{ω+α} 𝕋_{B}. W.l.o.g. there exists γ_{β,i} ∈ A − B. Since ⟨γ_{β,i}⟩ˆ η : η ∈ 𝕋_{i}^{β}} is a subtree of 𝕋_{A} and for all j < ℶ_{β} we have that j ≠ i ⇒ 𝕋_{i}^{β} ≉_{ω+β} 𝕋_{j}^{β}, from the definition of the relation ≈, and the fact that it follows that there is no ordinal ϵ such that the tree {ϵˆ η : η ∈ 𝕋_{i}^{β}} does not appear as a subtree of 𝕋_{B} it is clear that 𝕋_{A} ≉_{ω+α} 𝕋_{B}. □_{2}

Back to the proof of Theorem 2.8: Let α < λ^{+} be given. By Claim 2 there exists a family of nonequivalent simple trees {𝕋_{i} : i < ℶ_{α}}. By renaming, we may assume that the above trees do not contain sequences of ordinals which are less than ℶ_{α}. We define a new tree: M_{α} its set of elements consists of

{⟨⟩} ∪ {⟨i⟩ : i < ℶ_{α}} ∪ {⟨i, i′⟩ˆ η : η ∈ 𝕋_{i′}, i′ < i, i < ℶ_{α}}.

We can view M_{α} as a partially ordered set (by “being initial segment”). We view M_{α} as a model in a languge consisting of single function symbol: A unary function f whose interpretation is the predessor of its argument (if the argument is the root than the value is defined to be the root). Notice that the following formula (of L_{ω_{1},ω}), ⋁_{k<ω}[x = f^{k}(y)]^{5} defines the relation of “being an initial segment” on well founded trees.

Let ψ_{α} := ⋀ T h_{ω,ω}(M_{α}) ∧ (∀x) ⋁_{n<ω}[f^{n}(x) = ⟨⟩]. Namely ψ_{α} is the first-order theory of M_{α} together with the statement that say that every element is of finite distance from the root.

Let φ_{α}(x, y) be the following statement: x, y ∈ Suc(⟨⟩), and for every x′ ∈ Suc(x) there exists y′ ∈ Suc(y) such that 𝕋[x′] ≈_{ω+α+1} 𝕋[y′], and there exists y′ ∈ Suc(y) such that for every x′ ∈ Suc(x) we have that 𝕋[x′] ≉_{ω+α+1} 𝕋[y′] holds.

In order to complete the proof of Theorem 2.8, it suffices to prove the following:

Sub Claim 2.13. (1) φ_{α}(x, y) ∈ L_{λ^{+},ω}, (2) M_{α} has the (φ_{α}, ℶ_{α})-order property,

(3) There do not exist a formula φ′(x, y) ∈ L_{κ^{+},ω} such that ψ_{α} has the (φ′(x, y), ∞)-order property.

Proof. (1) Let 𝕋 be a well founded tree, and let α < λ^{+} be given, it is enough to show by induction on α that there exists a formula χ(x, y) ∈ L_{λ^{+},ω} such that for every a, b ∈ 𝕋 we have that 𝕋 ⊧ χ[a, b] iff 𝕋[a] ≈_{α} 𝕋[b]. It is easy to check that the relation ≈_{α} is definable in L_{λ^{+},ω}.

(2) Check that for every i_{1}, i_{2} < ℶ_{α} we have that i_{1} < i_{2} iff M_{α} ⊧ φ_{α}[⟨i_{1}⟩, ⟨i_{2}⟩].

(3) For the sake of contradiction suppose that there exists a formula φ′(x, y) ∈ L_{κ^{+},ω} such that ψ_{α} has the (φ′, ∞)-order property. Suppose that γ is a limit ordinal < κ^{+} such that the formula φ′ has quantifier depth < γ. Denote by μ the cardinality (ℶ_{γ+1}(|L|))^{+}. Let N ⊧ ψ_{α} be a model of cardinality μ such that there exists {a_{i} : i < μ} such that ℓ(x) = ℓ(y) = ℓ(a_{i}) = n < ω and for every i_{1}, i_{2} < μ we have i_{1} < i_{2} ⟺ N ⊧ φ′[a_{i_{1}}, a_{i_{2}}] holds. For every i < μ fix ⟨b_{l}^{i} : l < n⟩ = a_{i}. By the L_{ω_{1},ω}-part of the definition of ψ_{α} we have that N ⊧ (∀x) ⋁_{m<ω} f^{m}(x) = f^{m+1}(x). For every c ∈ N let m(c) := min{m : N ⊧ f^{m}(c) = f^{m+1}(c)}.

Since μ is regular, after renaming we may assume that for every l < n there are k_{l} < ω such that for every i < μ we have m(b_{l}^{i}) = k_{l}. By increasing n we may assume that for every i < μ we have that f(b_{l}^{i}) ∈ {b_{k}^{i} : k < n}, and for every i_{1}, i_{2} < μ and every l_{1}, l_{2} < n we have

N ⊧ f(b_{l_{1}}^{i_{1}}) = b_{l_{2}}^{i_{1}} ⟺ N ⊧ f(b_{l_{1}}^{i_{2}}) = b_{l_{2}}^{i_{2}} ⋀ N ⊧ b_{l_{1}}^{i_{1}} = b_{l_{2}}^{i_{1}} ⟺ N ⊧ b_{l_{1}}^{i_{2}} = b_{l_{2}}^{i_{2}}.

We may also assume that ⟨b_{l} : l < n⟩ has no repeatition. By the Δ-system lemma there exists s ⊆ n such that for every i_{1}, i_{2} < μ and every l_{1}, l_{2} < n we have that b_{l_{1}}^{i_{1}} = b_{l_{2}}^{i_{2}} ⟺ l_{1} = l_{2} ∈ s.

5When f^{k}(y) stands for f(⋯ f(y) ⋯) k-many times.

Let Φ_{γ} be the set of L_{∞,ω} formulas of quantifier depth < γ with finitely many free variables. Clearly |Φ_{γ}| ≤ ℶ_{γ}(|L|) and |P (Φ_{γ})| ≤ ℶ_{γ+1}(|L|) < μ = cf(μ).

Let tp_{γ}(b_{0}, …, b_{m−1}; M) := {φ(x̄) ∈ Φ_{γ} : M ⊧ φ[b_{0}, …, b_{m−1}]}. Without loss of generality we may assume that for every i, j < μ we have tp_{γ}(b_{0}^{i}, …, b_{m−1}^{i}; N) = tp_{γ}(b_{0}^{j}, …, b_{m−1}^{j}; N).

We will obtain a cotradiction to the assumption that ψ_{α} has the (φ′, ∞)- order property by proving the following:

Claim. For every i, j < μ we have

N ⊧ φ′[b_{0}^{i}, …, b_{n−1}^{i}, b_{0}^{j}, …, b_{n−1}^{j}] ⟺ N ⊧ φ′[b_{0}^{j}, …, b_{n−1}^{j}, b_{0}^{i}, …, b_{n−1}^{i}]

Proof. Let B = {b_{l}^{α} : l ∈ s}

□_{2.13}

Remark 2.14. In Definition 2.5 we have introduced a third parameter, but since it does not add anything of substance (just complicates the notation that may be already little heavy) we decided to limit our treatment to the above particular case. At the end of this section we discuss several generalizations.

Theorem 2.8 provides a better upper bound than the one in Fact 1.10:

Corollary 2.15. For every κ ≤ λ, we have μ^{∗}(λ, κ) ≤ ℶ_{δ_{1}(λ,κ)}.

Remark 2.16. Using Facts 1.10 and 2.15, one can show that δ_{1}(λ, κ) ≤ δ_{0}(λ, κ) for κ ≤ λ. In [GrSh1] we have shown that in many instances the ordinal δ_{1}(λ, κ) is much smaller than δ_{0}(λ, λ) [e.g. when κ = ℵ_{0}, we have that δ_{1}(λ, κ) = λ^{+}, while for λ = ℶ_{ω_{1}}, we have δ_{0}(λ, λ) > 2^{λ}. ]

3. Connection with the Galvin-Hajnal rank

In Theorem 2.6 we reduced the problem of finding estimates for μ_{1}(·, ·) to finding bounds for δ_{1}(·, ·). In Fact 3.2, below we state a result from [GrSh1], first we need the following:

Definition 3.1. For uncountable κ, and λ ≥ κ, denote by

κ^{∗} := \{ \begin{matrix}κ & if cfκ = ℵ_{0} \\ κ^{+} & if cfκ > ℵ_{0}. \end{matrix}

cov(λ, κ) := min{|F | : F ⊆ S_{<κ^{∗}}(λ), ∀X ∈ S_{<κ^{∗}}(λ) ∃{w_{l} : l < ω} ⊆ F, such that X ⊆ ⋃_{l<ω} w_{l}}.

Clearly cov(λ, κ) ≤ λ^{κ}. But often cov(λ, κ) < λ^{κ}. In [Sh g] Shelah has a more general function. Our cov(λ, κ) is the same as cov(λ, κ^{∗}, κ^{∗}, ℵ_{1}) from Definition II 5.2 of [Sh g].

Fact 3.2. (Theorem 4.4 of [GrSh1]) Let κ ≤ λ be infinite cardinalities. (a) if κ = ℵ_{0} then δ_{1}(λ, κ) ≤ λ^{+}.

(b) if cfκ > ℵ_{0} then δ_{1}(λ, κ) ≤ (cov(λ, κ) + 2^{κ})^{+}.

(c) if cfκ = ℵ_{0} then δ_{1}(λ, κ) ≤ (cov(λ, κ) + 2^{<κ} + ℵ_{0})^{+}.

Note that the above inocent looking results are quite powerfull! E.g. By a result of [Sh g] (from Chapter XI), if (∀μ < χ)[μ^{κ} < λ] ⋀ cf(χ) = ℵ_{0} ⋀ χ ≤ λ < χ^{δ+ω_{1}} then we have that cov(λ, κ) = λ, thus μ_{1}(λ, κ) ≤ ℶ_{λ^{+}}, while using Morley’s methods we get only μ_{1}(λ, κ) ≤ ℶ_{(2^{λ})^{+}}.

The following is a generalization of the cardinal–valued function we have introduced in Definition 1.8. Here instead of assuming that φ(x; y) is an L_{λ^{+},ω} formula we look at all φ ∈ L_{∞,ω} with quantifier depth < γ, we take into consideration only the rank of the formula φ.

Definition 3.3. Let κ be an infinite cardinality, and let γ be an ordinal greater or equal to κ^{+}, T ∈ L_{κ^{+},ω}

(a) μ_{T}^{∗} (γ, κ) := min{μ^{∗} : ∀φ ∈ L_{∞,ω}, with rk(φ) < γ, if T has the (φ, μ^{∗})-order property, then ∃φ′(x; y) ∈ L_{κ^{+},ω}, such that T has the (φ′, ∞)-order property}.

(b) μ_{2}^{∗}(γ, κ) := sup{μ_{T}^{∗} (γ, κ) | T ∈ L_{κ^{+},ω}}^{6}.

The improvement in comparison to what we have seen before is that instead of limiting attention to formulas with the order-property to be from L_{λ^{+},ω} we consider what may look as a weaker order-property, by considering formulas with the order property to be from the logic L_{∞,ω} (with rank bounded by γ).

6Note that similarly to what we did in the previous section with the function μ_{0}(·, ·) above, the functions μ^{∗}(γ, κ) and μ^{∗}(λ, κ) are different objects, we distinguish between them by using different arguments.

Definition 3.4. Let T, <, <^{P} , P be as in Definition 2.5. For an ordinal γ > κ let

(a) δ_{2}(λ, γ, κ) := min{δ : Γ is a set of T -types , |Γ| ≤ κ, |T | ≤ λ if ∀δ′ < δ ∃M ∈ EC(T, Γ) with otp P^{M}, <^{P^{M}}) < γ and otp M − P, <) ≥ δ′ , then ∃N ∈ EC(T, Γ) s.t. otp(P^{N}, <^{P^{N}}) ∈ On ∩ κ^{+} and (N − P^{N}, <^{N}) is not well ordered}.

(b) μ_{2}(λ, γ, κ) := min{μ : Γ is a set of T -types , |Γ| ≤ κ, |T | ≤ λ if ∃M ∈ EC(T, Γ) ∥M∥ ≥ μ with otp(P^{M}, <^{M}) < γ then for every χ ≥ κ ∃N ∈ EC(T, Γ) of cardinality at least χ such that otp(P^{N}, <^{N}) ∈ On ∩ κ^{+}}.

(c) When λ = κ we may omit λ. By the discussion after Theorem 2.6 this case is interesting enough.

The following is an analog of Proposition 2.8:

Proposition 3.5. Let κ and μ be cardinalities, and let γ be an ordinal ≥ κ. Then (1) ⇒ (2) ⇒ (3) where

(a) μ ≥ μ_{2}(γ, κ)

(b) for every ψ ∈ L_{κ^{+},ω}, and for every φ(x; y) ∈ L_{∞,ω} of quantifier depth < γ if ψ has the (φ, μ)-order property then there exists φ′ ∈ L_{κ^{+},ω} such that ψ has the (φ′, ∞)-order property.

(c) μ ≥ ℶ_{γ}.

Theorem 3.6. For every κ and every ordinal γ ≥ κ we have μ_{2}(γ, κ) = ℶ_{δ_{2}(γ,κ)}.

Theorem 3.6 will be proved in the next section.

The following theorem connects δ_{2} to the Galvin–Hajnal rank and provides a lower bound for δ_{2}(γ, κ):

Theorem 3.7. (A lower bound): Suppose κ is an uncountable regular cardinality. Let J be the ideal of nonstationary subsets of κ. For every ordinal γ > κ we have ∥γ∥_{J} < δ_{2}(γ, κ), when ∥γ∥_{J} is the Galvin–Hajnal rank of the constant function f : κ → γ + 1 whose value is γ.

Instead of proving the above theorem, we prove a more general result. It turns out that the ideal J of nonstationary subsets can be replaced by almost any other ideal satisfying rather weak conditions:

Theorem 3.8. (A better lower bound): Suppose J is an ℵ_{1}-complete ideal on κ such that (*) J as an ideal is generated by ≤ κ sets or at least we have (**) there exists a model 𝔅 (of an expansion of set theory) with universe κ, |L(𝔅)| ≤ κ and ψ(P) ∈ L_{κ^{+},ω}, when L = L(𝔅) ∪ {P }, P is a unary predicate; having the following property:

⨂_{J} for every A ⊆ κ, we have that A ∈ J ⟺ ⟨𝔅, A⟩ ⊧ ψ(P) or at least

⨂_{J}^{−} for every A ⊆ κ, we have that A ∈ J ⟺ forsomeA’wehavethatA⊆ A′ ∈ J, ⟨𝔅, A′⟩ ⊧ ψ(P)

then for every ordinal γ > κ we have that ∥γ∥_{J} < δ_{2}(γ, κ).

Remark 3.9. (a) One way to see that Theorem 3.7 is a special case of Theorem 3.8 is by using the same argument. Another formal argument (using the statement of 3.8) we can take 𝔅 := ⟨κ, <⟩ and ψ(P) will say that {x : P (x)} is a closed unbounded set. This satisfy ⨂_{J}^{−} but not ⨂_{J}.

(b) Note that ⨂_{J}^{−} is equivalent to: for some ψ(P, R̄) ∈ L_{κ^{+},ω}, we have that A ∈ J ⟺ (∃R̄)⟨𝔅, A⟩ ⊧ ψ(P, R̄).

Proof. Let γ^{∗} := ∥γ∥_{J}, and let ds(γ^{∗}) stand for the set {ν|ν is strictly decreasing sequence of ordinals < γ^{∗}}. There exists a family of functions {f_{η} : κ → On | η ∈ ds(γ^{∗})} with the following properties:

(a) f_{⟨⟩} is constantly γ.

(b) if ηˆ i ∈ ds(γ^{∗}) then f_{ηˆ i} <_{J} f_{η}, and for every ζ < κ we have ¬[f_{ηˆ i}(ζ) < f_{η}(ζ)] ⇒ f_{ηˆ i}(ζ) = f_{η}(ζ) = 0.

(c) if η ≠ ⟨⟩ then ∀ζ < κ[f_{η}(ζ) < γ].

(d) ηˆ i ∈ ds(γ^{∗}) ⇒ ∥f_{ηˆ i}∥_{J} ≥ i.

(e) ∥f_{⟨⟩}∥_{J} = γ^{∗}. This is possible: Define the function f_{η} by induction on ℓ(η): For ℓ(η) = 0; Let f_{⟨⟩} be the constant function as in requirement (1). For ℓ(η) > 0; If ηˆ i ∈ ds(γ^{∗}) then f_{η} is defined, and by the inductive hypothesis we have that ∥f_{ηˆ i}∥_{J} > i (as ηˆ i ∈ ds(γ^{∗}) and ∥f_{⟨⟩}∥_{J} = γ^{∗}), by the definition of the Galvin–Hajnal rank there exists f′ <_{J} f_{η} such that ∥f′∥_{J} ≥ i. Now for ζ < κ let

f_{ηˆ i}(ζ) := \{ \begin{matrix}f′(ζ) & if f′(ζ) < f_{η}(ζ) \\ 0 & otherwise. \end{matrix}

This is enough: Denote by \overline{f} the sequence ⟨f_{η} : η ∈ ds(γ^{∗})⟩. Let χ^{∗} be a sufficiently large regular cardinal such that H(χ^{∗}) conatins all relevant sets and the structure ⟨H(χ^{∗}), ∈⟩ reflects all relevant properties. Let ℭ := ⟨H(χ^{∗}), ∈, <_{χ^{∗}}^{∗}, \overline{f}, κ, D, 𝔅, ψ(·), J, Q, P, i⟩_{i≤κ} , when <_{χ^{∗}}^{∗} is a well ordering of the set H(χ^{∗}), P is the unary predicate {i : i < γ}, Q is the unary predicate interpreted by the set {j : j < γ^{∗}}, D interpreted by ds(γ^{∗}). Let T := T h(ℭ), and Γ is a set of types consisting only of the following type – {x ∈ κ ∧ x ≠ i : i < κ}. Suppose N ∈ EC(T, Γ) is such that (P^{N}, <^{P^{N}}) is well ordered, and we will show that (Q^{N}, <) is well ordered.

W.l.o.g. we may assume that A^{N} := {x ∈ N : N ⊧ rk(x) ∈ P } is a transitive set and ∈^{N}↾ A^{N} =∈↾ A^{N} (by taking the Mostowski’s collapse).

So P^{N} = γ′ for some γ′, and since N omits the type in Γ we have κ^{N} = κ, since the universe of 𝔅 is κ we have 𝔅^{N} = 𝔅. So necessarily ψ(·)^{N} = ψ(·).

By the axioms of T it follows that (*) if N ⊧ ηˆ x ∈ D then N ⊧ (∃X ⊆ {i < κ : f_{η}(i) ≤ f_{ηˆ x}(i)}) 𝔅 ⊧ ψ(X). Now since ηˆ x ∈ D^{N}, we have f_{η}^{N}, f_{ηˆ x}^{N} ∈ A^{N}. So by the functions from κ into γ′. Also ψ^{N} = ψ, by absoluness we have N ⊧ (∃X ⊆ {i < κ : f_{η}(i) ≤ f_{ηˆ x}(i)}) 𝔅 ⊧ ψ(X). So by (**) we have (*) ηˆ x ∈ D^{N} ⇒ f_{ηˆ x} <_{J} f_{η}.

Now if (Q^{N}, <) is not well ordered then we can find {x_{n} ∈ Q^{N} : N ⊧ [x_{n+1} < x_{n}]}. From T ’s axioms it follows that there are {y_{n} : n < ω} such that y_{0} = ⟨⟩, y_{n+1} = y_{n}ˆ x_{n} ∈ D for all n < ω. So we have that {f_{y_{n}} : κ → γ′ | n < ω} and for every n < ω f_{y_{n+1}} <_{J} f_{y_{n}} (in V). Since J is an ℵ_{1}-complete ideal we have a contradiction. We have shown that there exists a pair T, Γ of the aproperiate cardinalities such that

(a) N ∈ EC(T, Γ), (P^{N}, <) is well ordered ⇒ (Q^{N}, <) is well ordered.

(b) there is N ∈ EC(T, Γ) with otp(P^{N}, <) ≤ γ and (Q^{N}, <) of order

type γ^{∗} (take N = ℭ). This establishes that γ^{∗} < δ_{2}(γ, κ). □_{3.8}

4. Concluding Remarks

It is natural to ask whether the lower bound from Theorem 3.8 is equal to the one in Fact 3.2. The following seems to be a reasonable

Conjecture 4.1. For cardinalities κ of uncounable cofinality and λ such that 2^{κ} < λ we have δ_{1}(λ, κ) = (cov(λ, κ) + 2^{κ})^{+}.

Remark 4.2. (a) Notice that when κ is strong limit singular of cofinality

ℵ_{0} then the conjecture holds.

(b) Why 2^{κ} < λ – See Barwise-Kunen for independence results.

(c) The conjecture can to a large extent be traslated to a one on pcf; it is

evident that e.g. (***) below is a sufficient condition:

(***) for any set 𝔞 of ≤ κ regular cardinals which are > 2^{κ} the set pcf(𝔞) has cardinality at most κ, or at least the set pcf_{ℵ_{1}-complete} (𝔞) has cardinality at most κ.

This is because by [Sh g] II 5.4 if 2^{κ} < λ then μ = cov(λ, κ) is the first μ such that if {λ_{i} : i < κ} is a set of regular cardinalities in the interval (2^{κ}, λ) and J is an ℵ_{1}-complete ideal on κ and cf(∏_{i<κ} λ_{i}, <_{J}) is well defined then it is ≤ μ.

The problem is that the ideal may not satisfy even ⨂_{J}^{−}. However by [Sh g] VII, 2.6 the ideal J is generated by a family of ≤ |pcf{λ_{i} : i < κ}| sets and even by a family of just ≤ |pcf_{ℵ_{1}-complete}{λ_{i} : i < κ}| sets, so we have |pcf({λ_{i} : i < κ}| ≤ κ ⇒ ⨂_{J}

References

[BaKu] K. J. Barwise and K. Kunen, Hanf numbers for fragments of L_{∞,ω}, Israel J. of Mathematics, 10, 306–320, 1971

[Ch] C. C. Chang, Some remarks on the model theory of infinitary languages, The Syntax and Semantics of Infinitary Languages, Springer-Verlag Lecture Notes in Mathematics 72, edited by J. Barwise (1968) pages 36–63.

[Gr] Rami Grossberg, Classification theory for non elementary classes, Ph.D. Thesis (in Hebrew), The Hebrew University of Jerusalem 1986.

[GrSh1] Rami Grossberg and Saharon Shelah, On the number of nonisomorphic models of an infinitary theory which has the infinitary order property. I, The Journal of Symbolic Logic, 51:302–322, 1986. — MR: 87j:03037, (03C45)

[GrSh2] Rami Grossberg and Saharon Shelah, A nonstructure theorem for an infinitary theory which has the unsuperstability property, Illinois Journal of Mathematics, 30:364– 390, 1986. Volume dedicated to the memory of W.W. Boone; ed. Appel, K., Higman, G., Robinson, D. and Jockush, C. — MR: 87j:03036, (03C45)

[HrSh] Ehud Hrushovski and Saharon Shelah, Stability and omitting types, Israel Journal of Mathematics, 74:289–321, 1991. — MR: 92m:03049, (03C45)

[Ma] Menachem Magidor, Chang’s conjecture and powers of singular cardinals, The Journal of Symbolic Logic, 42: 272–276, 1977.

[MaSh] Michael Makkai and Saharon Shelah, Categoricity of theories in L_{κω}, with κ a compact cardinal, Annals of Pure and Applied Logic, 47:41–97, 1990. — MR: 92a:03054, (03C75)

[Mo] Michael Morley, Omitting classes of elements, The Theory of Models, edited by Addison, Henkin and Tarski, North-Holland Publ Co (1965) pages 265–273.

[Sh 12] Saharon Shelah. The number of non-isomorphic models of an unstable first-order

theory. Israel Journal of Mathematics, 9:473–487, 1971. — MR: 43-4652. [Sh 16] Saharon Shelah, A combinatorial problem; stability and order for models and the-

ories in infinitary languages, Pacific Journal of Mathematics, 41:247–261, 1972. — MR: 46:7018, (02H10)

[Sh 48] Saharon Shelah, Categoricity in ℵ_{1} of sentences in L_{ω_{1},ω}(Q), Israel Journal of

Mathematics, 20:127–148, 1975. — MR: 52:83, (02H10) [Sh 78] Saharon Shelah, Hanf number of omitting type for simple first-order theories, The

Journal of Symbolic Logic, 44:319–324, 1979. — MR: 80k:03031, (03C50) [Sh 87a] Saharon Shelah, Classification theory for nonelementary classes I, The number of

uncountable models of ψ ∈ L_{ω_{1},ω}. Part A, Israel Journal of Mathematics, 46:212–240, 1983. — MR: 85m:03024a, (03C45)

[Sh 87b] Saharon Shelah, Classification theory for nonelementary classes. I. The number of uncountable models of ψ ∈ L_{ω_{1},ω}. Part B, Israel Journal of Mathematics, 46:241–273, 1983. — MR: 85m:03024b, (03C45)

[Sh 88] Saharon Shelah, Classification of nonelementary classes II, Abstract elementary classes, In Classification theory (Chicago, IL, 1985), volume 1292 of Lecture Notes in Mathematics, pages 419–497. Springer, Berlin, 1987. Proceedings of the USA–Israel Conference on Classification Theory, Chicago, December 1985; ed. Baldwin, J.T. — MR: 91h:03046, (03C75)

[Sh 200] Saharon Shelah. Classification of first-order theories which have a structure theo-

rem. American Mathematical Society. Bulletin. New Series, 12:227–232, 1985. [Sh 299] Saharon Shelah, Taxonomy of universal and other classes, In Proceedings of

the International Congress of Mathematicians (Berkeley, Calif., 1986), volume 1, pages 154–162. Amer. Math. Soc., Providence, RI, 1987. ed. Gleason, A.M. — MR: 89e:03006, (03-02)

[Sh 300] Saharon Shelah, Universal classes, In Classification theory (Chicago, IL, 1985), volume 1292 of Lecture Notes in Mathematics, pages 264–418. Springer, Berlin, 1987.

Proceedings of the USA–Israel Conference on Classification Theory, Chicago, December 1985; ed. Baldwin, J.T. — MR: 91k:03088, (03C52)

[Sh 394] Saharon Shelah, Categoricity of abstract classes with amalgamation. Annals of

Pure and Applied Logic, submitted. [Sh 460] Saharon Shelah, The Generalized Continuum Hypothesis revisited, Israel Journal

of Mathematics, submitted. [Sh c] Saharon Shelah, Classification Theory and the Number of Nonisomorphic Mod-

els, Rev. Ed., North-Holland, 1990, Amsterdam. [Sh g] Saharon Shelah, Cardinal Arithmetic, volume 29 of Oxford Logic Guides. Oxford

University Press, 1994. E-mail address, Rami Grossberg: rami@cmu.edu

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA

E-mail address, Saharon Shelah: shelah@math.huji.ac.il

Institute of Mathematics, The Hebrew University, Jerusalem, Israel, & Rutgers University, Mathematics Department, New Brunswick, NJ 08903 USA