THE TRICHOTOMY THEOREM DOES NOT HOLD FOR SHORT SEQUENCES

MENACHEM KOJMAN AND SAHARON SHELAH

Abstract. The Trichotomy Theorem deals with sequences of ordinal functions on an infinite κ modulo some ideal I. If a <_{I}- increasing sequence of ordinal functions has regular length which is larger than κ^{+}, then by the Trichotomy Theorem the sequence satisfies one of three structural conditions. It was of some interest to find out if the Trichotomy Theorem could hold also for sequences of length κ^{+}. It is shown that this is not the case.

1. Introduction

The Trichotomy Theorem specifies three alternatives for the structure of an increasing sequence of ordinal functions modulo an ideal on an infinite cardinal κ — provided the sequence has regular length λ and λ is at least κ^{++}.

The natural context of the Trichotomy Theorem is, of course, pcf theory, where a sequence of ordinal functions on κ usually has length which is larger than κ^{+κ}. However, the trichotomy theorem has already been applied in several proofs to sequences of length κ^{+n}, (n ≥ 2) (see [4], [1] and [3]).

Therefore, a natural question to ask is, whether the Trichotomy Theorem is valid also for sequences of length κ^{+}, namely, whether the condition on the minimum length of the sequence can be lowered by one cardinal.

Below we show that the assumption λ ≥ κ^{++} in the Trichotomy Theorem is tight. For every infinite κ, we construct an ideal I over κ and <_{I}-increasing sequence \overline{f} ⊆ On^{κ} so that all three alternatives in the Trichotomy theorem are violated by \overline{f}.

2. The Counter-example

Let κ be an infinite cardinal. Denote by On^{κ} the class of all functions from κ to the ordinal numbers.

The first author was partially supported by NSF grant No. DMS-9622579.

The second author was partially supported by the Israeli Foundation for Basic Science. Number 673 in list of publications.

Let I be an ideal over κ. We write f <_{I} g, for f, g ∈ On^{k}, if {i < κ : f(i) ≥ g(i)} ∈ I and we write f ≤_{I} g if {i < κ : f(i) > g(i)} ∈ I. A sequence \overline{f} = ⟨f_{α} : α < λ⟩ ⊆ On^{κ} is <_{I}-increasing if α < β < λ implies that f_{α} <_{I} f_{β} and is <_{I}-decreasing if α < β < λ implies that f_{β} <_{I} f_{α}.

A function f ∈ On^{k} is a least upper bound mod I of a sequence \overline{f} = ⟨f_{α} : α < λ⟩ ⊆ On^{κ} if f_{α} <_{I} f for all α < λ and whenever f_{α} <_{I} g for all α then f ≤_{I} g. A function f ∈ On^{κ} is an exact upper bound of \overline{f} if f_{α} ≤ f for all α < λ, and whenever g <_{I} f, there exists α < λ such that g <_{I} f_{α}. For subsets t, s of κ, write t ⊆_{I} s if s − t ∈ I.

The dual filter I^{∗} of an ideal I over κ is the set of all complements of members of I. The relations ≤_{I}, <_{I} and ⊆_{I} will also be written as ≤_{I^{∗}}, <_{I^{∗}} and ⊆_{I^{∗}}.

Let us quote the theorem under discussion:

Theorem 1. (The Trichotomy Theorem)

Suppose λ ≥ κ^{++} is regular, I is an ideal over k and \overline{f} = ⟨f_{α} : α < λ⟩ is a <_{I}-increasing sequence of ordinal functions on k. Then \overline{f} satisfies one of the following conditions:

1. \overline{f} has an exact upper bound f with cff(i) > κ for all i < κ;

2. there are sets S(i) for i < κ satisfying |S(i)| ≤ κ and an ultrafilter U over k extending the dual of I so that for all α < λ there exists h_{α} ∈ ∏_{i<κ} S(i) and β < λ such that f_{α} <_{U} h_{α} <_{U} f_{β}.

3. there is a function g : κ → On such that the sequence \overline{t} = ⟨t_{α} : α < λ⟩ does not stabilize modulo I, where t_{α} = {i < κ : f_{α}(i) > g(i)}.

Proofs of the Trichotomy Theorem are found in [5], II,1.2, in [3] or in the future version of [2].

Theorem 2. For every infinite κ there exists an ultrafilter U over κ and a <_{U}-increasing sequence \overline{f} = ⟨f_{α} : α < κ^{+}⟩ ⊆ On^{κ} such conditions 1, 2 and 3 in the Trichotomy Theorem fail for \overline{f}.

Proof. Let λ = κ^{+}.

Let us establish some notation.

We recall that every ordinal has an expansion in base λ, namely can be written as a unique finite sum ∑_{k≤l} λ^{β_{l}}α_{l} so that β_{k+1} < β_{k} and α_{k} < λ. We limit ourselves from now on to ordinalz ζ < λ^{ω}. For such ordinals, the expansion in base κ contains only finite powers of λ (that is, every β_{k} is a natural number).

We agree to write an ordinal ζ = λ^{l}α_{l} + λ^{l−1}α_{l−1} + ⋯ + α_{0} simply as a finite sequence α_{l}α_{l−1} … α_{0}. We identify an expansion with λ digits with one with n > l digits by adding zeroes on the left. If ζ = α_{l}α_{l−1} … α_{0}, we call α_{k}, for k ≤ l, the k-th digit in the expansion of ζ.

For α < λ and an integer l, define:

A_{α}^{l} = {α_{l}α_{l−1} … α_{0} : α_{k} < α for all k ≤ l}  (1)

A_{α}^{l} is the set of all ordinals below λ^{ω} whose expansion in base λ contains l + 1 or fewer digits from α.

Fact 3. For all α < λ and l < ω, 1. ⋃_{α<λ} A_{α}^{l} = λ^{l+1}

2. The ordinal ∑_{k=0}^{l} λ^{k} = \overbrace{αα … α}^{l+1} is the maximal element in A_{α+1}^{l} 3. if ζ = α_{l}α_{l−1} … α_{0} ∈ A_{ζ}^{l} is not maximal in A_{α+1}^{l}, then the imme-

diate successor of ζ in A_{α+1}^{n} is obtained from ζ as follows: let k be the first k ≤ l for which α_{k} < α. Replace α_{k} by α_{k} + 1 and replace α_{m} by 0 for all m < k

Fix a partition {X_{n} : n < ω} of κ with |X_{n}| = κ for all n. Let n(i), for i < κ, be the unique n for which i ∈ X_{n}.

By induction on α < κ^{+}, define f_{α} : κ → On so that:

1. f_{α}(i) ∈ A_{α+1}^{n(i)} − A_{α}^{n(i)}

2. For all n, l < ω and finite, strictly increasing, sequences ⟨α_{k} : k ≤ l⟩ ⊆ λ it holds that for every sequence ⟨ζ_{k} : k ≤ l⟩ which satisfies ζ_{k} ∈ A_{α_{k}+1}^{n} − A_{α_{k}}, there are κ many i ∈ X_{n} for which ⋀_{k≤l} f_{α_{k}}(i) = ζ_{k}.

The first item above says that f_{α}(i) is an ordinal below λ^{ω} whose expansion in base λ has ≤ n(i) digits, at least one of which is α. The second item says that every possible finite sequence of values ⟨ζ_{k} : k < l⟩ is realized κ many times as ⟨f_{α_{κ}}(i) : k < λ⟩ for an arbitrary increasing sequence ⟨α_{κ} : k < l⟩.

The induction required to define the sequence is straightforward. Define now, for every α < κ^{+}, a function g_{α} : κ → On as follows:

g_{α}(i) = min[(A_{α+1}^{n}(i) ∪ {λ+^{n(i)+1}}) − f_{α}(i)]  (2)

Since f_{α}(i) < λ^{n(i)+1} for i ∈ X_{n}, the definition is good. If f_{α}(i) is not maximal in A_{α+1}^{n(i)}, then g_{α}(i) is the immediate successor of f_{α}(i) in A_{α+1}^{n(i)}. Let us make a note of that:

Fact 4. There are no members of A_{α+1}^{n(i)} between f_{α}(i) and g_{α}(i)

We have defined two sequences:

\overline{f} = ⟨f_{α} : α < λ⟩
\overline{g} = ⟨g_{α} : α < λ⟩

Next we wish to find an ideal modulo which \overline{f} is <_{I}-increasing and \overline{g} is a <_{I}-decreasing sequence of upper bounds of \overline{f}.

Claim 5. For every finite increasing sequence α_{0} < α_{1} < ⋯ < α_{l} < λ there exists i < κ such that for all k < l

f_{α_{k}}(i) < f_{α_{k+1}}(i) < g_{α_{k+1}}(i) < g_{α_{k}}(i)  (3)

Proof. Suppose α_{0} < α_{1} < ⋯ < α_{l} < λ is given and choose n > l. Let

ζ_{0} = \overbrace{α_{0}α_{0} … α_{0}}^{l+1} ∈ A_{α_{0}}^{n}. Let ζ_{k+1} be obtained from ζ_{k} by replacing the first l + 1 − k digits of ζ_{κ} by α_{k+1}:

α_{0}α_{1} … α_{k}α_{k+1} … α_{l} = ζ_{l}
⋮
α_{0}α_{1} … α_{k−1}α_{k} … α_{k} = ζ_{k}
⋮
α_{0}α_{1} . . . . . . α_{1} … α_{1} = ζ_{1}
α_{0}α_{0} . . . . . . α_{0} … α_{0} = ζ_{0}

Thus ζ_{0} < ζ_{1} < … < ζ_{l} and ζ_{k} ∈ A_{α_{k}}^{l} ⊆ A_{α_{k}}^{n} is not maximal in A_{α_{k}}^{n} (because n > l). Let ξ_{k} be the immediate successor of ζ_{k} in A_{β_{k}}^{n}.

By Fact 3 above, we have

1 \overbrace{0 . . . . . . 0 . . . . . . 0}^{l+1} = ξ_{0}
(α_{0} + 1) 0 . . . . . . . . . . . . 0 = ξ_{1}
⋮
α_{0}α_{1} … (α_{k−1} + 1)0 … 0 = ξ_{k}
⋮
α_{0}α_{1} . . . . . . (α_{l−1} + 1)0 = ξ_{l}

Therefore ζ_{0} < ζ_{1} < … ζ_{l} < ξ_{l} < ξ_{l−1} < … < ξ_{0}. To complete the proof it remains to find some i ∈ X_{n} for which f_{α_{k}}(i) = ζ_{κ} for k ≤ l, and, consequently, by the definition (2) above, g_{α_{k}}(i) = ξ_{k}. The existence of such i ∈ X_{n} is guaranteed by the second condition in the definition of \overline{f}.

For α < β < λ, let

C_{α,β} = {i < κ : f_{α}(i) < f_{β}(i) < g_{β}(i) < g_{α}(i)}  (4)

Claim 6. {C_{α,β} : α < β < κ^{+}} has the finite intersection property

Proof. Suppose that α_{0}, β_{0}, α_{1}, β_{1}, …, α_{l}, β_{l} are given and α_{k} < β_{k} < λ for k ≤ l. Let ⟨γ_{m} : m < m(∗)⟩ be the increasing enumeration of ⋃_{k≤l}{α_{k}, β_{k}}. To show that ⋂_{k≤l} C_{α_{k},β_{k}} is not empty, it suffices to find some i < κ for which the sequence g_{γ_{m}}(i) is decreasing in m and f_{γ_{m}}(i) is increasing in m. The existence of such an i < κ follows from Claim 5.

Let U be any ultrafilter extending {C_{α,β} : α < β < λ}. Since for every α < β it holds that f_{α} <_{U} f_{β} <_{U} g_{β} <_{U} g_{α}, we conclude that \overline{f} is <_{U}-increasing, that \overline{g} is <_{U}-decreasing and that every g_{α} is an upper bound of \overline{f} mod U.

Claim 7. There is no exact upper bound of \overline{f} mod U.

Proof. It suffices to check that there is no h ∈ On^{κ} that satisfies f_{α} <_{U} h <_{U} g_{α} for all α < κ^{+}. Suppose, then, that h ∈ On^{k} satisfies this. Since h <_{U} g_{0}, we may assume that g(i) < λ^{n(i)+1} for all i < κ (by changing h on a set outside of U).

Let i < κ be arbitrary. Since ⋃_{α<λ} A_{α}^{n(i)} = λ^{n(i)+1}, there is some α(i) so that h(i) ∈ A_{α}^{n}(i). By regularity of λ it follows that there is some α(∗) < λ such that h(i) ∈ A_{α(∗)}^{n(i)} for all i < κ. By our assumption about h, f_{α(∗)} <_{U} h <_{U} g_{α(∗)}. Thus, there is some i < κ for which f_{β(∗)}(i) < h(i) < g_{β(∗)}(i). However, all three values belong to A_{α(∗)+1}^{n(i)},

while by Fact 4 there are no members of A_{α(∗)+1}^{n(i)} between f_{β(∗)(i)} and g_{α(∗)}(i) — a contradiction.

Claim 8. there are no sets S(i) ⊆ On for i < κ which satisfy condition 2 in the trichotomy for \overline{f} and U.

Proof. Suppose that S(i), for i < κ, and h_{α} ∈ ∏_{i<κ} S(i) satisfy 2. in the Trichotomy Theorem. Find α < λ such that S(i) ⊆ A_{α}^{n(i)} for all i. Thus f_{α} <_{U} h_{α} <_{U} g_{α} — contradiction to 4.

Claim 9. there is no g : κ → On such that g, \overline{f} and the dual of U satisfy condition 3. in the Trichotomy Theorem.

Proof. Let g : κ → On be arbitrary, and let t_{α} = {i < κ : f_{α}(i) > g(i)}. As \overline{f} is <_{U}-increasing, for every α < β < λ necessarily t_{α} ⊆_{U} t_{β}. Since U is an ultrafilter, every ⊆_{U}-increasing sequence of sets stabilizes.

References

[1] James Cummings. Collapsing successors of singulars. Proc. Amer. Math. Soc., 125(9):2703–2709, 1997.

[2] Menachem Kojman. The abc of pcf. Logic Eprints.

[3] Menachem Kojman. Exact upper bounds and their uses in set theory. Ann. Pure. App. Logic, in press.

[4] Menachem Magidor and Saharon Shelah. When does almost free imply free? (For groups, transversal etc.). Jour. Amer. Math. Soc., 7:769–830, 1994.

[5] Saharon Shelah. Cardinal Arithmetics, volume 29 of Oxford Logic Guides. Oxford Science Publications, 1994.

Department of Mathematics and Computer Science, Ben Gurion University of the Negev, Beer Sheva, Israel

Department of Mathematical Sciences, Carnegie-Mellon University, Pittsburgh, PA

  E-mail address: kojman@cs.bgu.ac.il

Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel

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