Handbook of Set Theory

Foreman, Kanamori, and Magidor (eds.) May 9, 2005

2

Contents

I Cardinal Arithmetic 5 by U. Abraham and M. Magidor 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Elementary definitions . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 Existence of exact upper bounds . . . . . . . . . . . . . . 13 2.2 Application: Silver’s Theorem . . . . . . . . . . . . . . . 26 2.3 Application: a covering theorem . . . . . . . . . . . . . 28

3 Basic properties of the pcf function . . . . . . . . . . . . . . . . 30

3.1 The ideal J_{<λ} . . . . . . . . . . . . . . . . . . . . . . . . 32 4 Generators for J_{<λ} . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5 The cofinality of [μ]^{κ} . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1 Elementary substructures . . . . . . . . . . . . . . . . . . 45 5.2 Minimally obedient sequences . . . . . . . . . . . . . . . 49

6 Elevations and transitive generators . . . . . . . . . . . . . . . . 60 7 Size limitation on pcf of intervals . . . . . . . . . . . . . . . . . . 66 8 Revised GCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.1 T_{D}(f) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.2 Proof of the revised GCH . . . . . . . . . . . . . . . . . . 77 8.3 Applications of the revised GCH . . . . . . . . . . . . . . 79 4 CONTENTS

I. Cardinal Arithmetic

U. Abraham and M. Magidor

1. Introduction

Cardinal arithmetic is the study of rules and properties of arithmetic operations mainly on infinite cardinal numbers. Since sums and products are trivial in the sense that

m + n = m · n = max{m, n}

holds for infinite cardinals, cardinal arithmetic refers mainly to exponentiation m^{n}. If M is a set of cardinality m and [M]^{n} is the collection of all subsets of M of cardinality n, then m^{n} is equal to the cardinality of [M]^{n}. Thus exponentiation is intimately connected with the power-set operation and hence lies at the heart of set theory. Classical and basic properties of cardinal arithmetic can be found, for example, in Levy and Jech textbooks (the latter contains more advanced material). The aim of this introduction is to mention some elementary results and to put our chapter in its context— not to give a historical introduction to the subject of cardinal arithmetic, for which the reader is referred to these textbooks, to [8], and to [9] for a more general perspective.

A theorem of J. König says that if ⟨κ_{i} | i ∈ I⟩ and ⟨λ_{i} | i ∈ I⟩ are sequences of cardinals such that κ_{i} < λ_{i} holds for every i ∈ I, then

Σ_{i∈I}κ_{i} < Π_{i∈I}λ_{i}.

A theorem of Bukovský and of Hechler says that if μ is a singular cardinal and the values 2^{γ} for cardinals γ < μ stabilize, then 2^{μ} = 2^{γ_{0}}, where γ_{0} < μ is such that 2^{γ_{0}} = 2^{γ} for all γ_{0} ≤ γ < μ.

Building on earlier results (of Hausdorff, Tarski, Bernstein and others) Bukovský (1965) and Jech show how cardinal exponentiation can be computed from the gimel function (which takes κ to κ^{cf(κ)}). Applications of Solovay and Easton of the forcing method of Cohen (1963) show that for regular cardinals κ there is no restriction on 2^{κ} except that which follows from König theorem, namely that cf(2^{κ}) > κ (see [7] Chapter 3 for details). Thus the question about the possible values of κ^{cf(κ)} is most interesting from our point of view when κ is a singular cardinal. It was evident that it is much harder to apply the forcing method to singular cardinals. Involving large cardinals, work of Prikry and of Silver showed that it is possible for a strong limit singular cardinal μ to satisfy 2^{μ} > μ^{+} in some generic extension. Using large cardinals Magidor proved the consistency of ℵ_{ω} being the first cardinal κ for which 2^{κ} > κ^{+} holds. For a long time it was believed that large cardinal and more complex applications of the forcing method should yield greater flexibility for values of the power-set of singular cardinals. A first indication that there are possible limitations was the theorem of Silver (1974): If κ is a singular cardinal with uncountable cofinality and if 2^{δ} = δ^{+} for all cardinals δ < κ, then 2^{κ} = κ^{+}. This result paved the way for further investigations by Galvin and Hajnal (1975). A representative result of their work is the following: If ℵ_{δ} is a strong limit singular cardinal with uncountable cofinality, then

2^{ℵ_{δ}} < ℵ_{(|δ|^{cf(δ)})^{+}}.

For example, if ℵ_{ω_{1}} is a strong limit cardinal, then

2^{ℵ_{ω_{1}}} < ℵ_{(2^{ℵ_{1}} )^{+}}.

The method of proof of these results relied in an essential way on the assumption that cf(δ) > ℵ_{0}. Shelah (1978) was able to prove similar results for singular cardinals with countable cofinality. For example, if ℵ_{ω} is a strong limit cardinal, then

2^{ℵ_{ω}} < ℵ_{(2^{ℵ_{0}} )^{+}}.  (I.1)

In a series of papers, culminating in his book [12], Shelah developed a powerful theory with many applications–the pcf theory—which changed our view on cardinal arithmetic. A remarkable result of this theory is the following. If ℵ_{ω} is a strong limit cardinal then

2^{ℵ_{ω}} < ℵ_{ω_{4}}.  (I.2)

If 2^{ℵ_{0}} ≤ ℵ_{2}, then (I.1) is a better bound than (I.2), but in general, since (2^{ℵ_{0}})^{+} can be arbitrarily high, ω_{4} seems to be a firmer bound.

The major definition in the pcf theory is the set pcf(A) of possible cofinalities defined for every set A of regular cardinals as the collection of all cofinalities of ultraproducts ΠA/D with ultrafilters D over A. This basic and rather simple definition appears in many places and is the basis of a very fruitful investigation. It is a basic definition also in the sense that while the power-set can be easily changed by forcing, it is very hard to change pcf(A).

Our aim in this chapter is to give a self-contained development of the pcf theory and to present some of its important applications to cardinal arithmetic. Unless stated otherwise, all theorems and results in this chapter are due to Shelah.

The fullest development of the pcf theory is in Shelah’s book [12], and the interested reader can access newer articles (and the survey paper “Analytical Guide”) in the archive maintained at Rutgers University (www.math.rutgers.edu).

In addition to this material, we have profited from expository papers (Burke–Magidor, Jech, and unpublished notes by Hajnal), and in particular a recently published book [6] which is very detailed, complete and carefully written.

The authors wish to thank Maxim R. Burke, Matt Foreman, Stefan Geschke, Klaas Pieter Hart, Donald Monk, and Martin Weese for valuable corrections and improvements of earlier versions.

2. Elementary definitions

An ideal over a set A is a collection I ⊆ P(A) such that (1) I is closed under subsets, that is, X ∈ I and Y ⊆ X implies Y ∈ I, and (2) I is closed under finite unions, that is, X_{1}, X_{2} ∈ I imply X_{1} ∪ X_{2} ∈ I (and thus the union of any finite sequence of members of I is in I). If A ∉ I, then I is said to be proper. We do not require that ideals be proper (see the definition of J_{<λ} in section 3.1).

The dual notion, that of a filter, is also used in this chapter. A collection F ⊆ P(A) is a filter over A if (1) F is closed under supersets, that is, X ∈ F and X ⊆ Y ⊆ A imply Y ∈ F, and (2) F is closed under finite intersections. However, usually a filter is proper, that is ∅ ∉ F.

If I is an ideal over A, then I^{∗} = {X ⊆ A | A \ X ∈ I} is its dual filter. Sets belonging to an ideal are intuitively “small” or “null”, whereas those of a filter are “big” or “of measure one”. If I is an ideal over A, then subsets of A not in I are called “positive”, and the collection of positive sets is denoted I^{+}.

I^{+} = {X ⊆ A | X ∉ I}.

We shall deal in this section with functions from a fixed, infinite set A into the ordinals. The class of these ordinal functions is denoted Ord^{A}. If f, g ∈ Ord^{A}, then f ≤ g means that f(a) ≤ g(a) for all a ∈ A, and similarly f < g means that f(a) < g(a) for all a ∈ A (this is called the everywhere dominance ordering).

If F ⊂ Ord^{A} is a set, then the supremum function h = sup F is defined on A by

h(a) = sup{f(a) | f ∈ F }.

If f, g ∈ Ord^{A}, then we define

<(f, g) = {a ∈ A | f(a) < g(a)},

and similarly

≤(f, g) = {a ∈ A | f(a) ≤ g(a)}.

and

=(f, g) = {a ∈ A | f(a) = g(a)}.

If I is an ideal over A, then we define a relation ≤_{I} over Ord^{A} by

f ≤_{I} g iff {a ∈ A | g(a) < f(a)} ∈ I.

In general, for any relation R on the ordinals, we define R_{I} over Ord^{A} by

f R_{I} g iff {a ∈ A | ¬(f(a) R g(a))} ∈ I.

That is, the set of exceptions to the relation is null. In this way <_{I} and =_{I} are defined over Ord^{A}. We remark that ≤_{I} is weaker than “<_{I} or =_{I}”. Check that ≤_{I} is a quasi-ordering, namely a transitive and reflexive relation, and that <_{I} is irreflexive (if I is a proper ideal) and transitive.

The notations X ⊆_{I} Y and X =_{I} Y are also used for subsets X, Y ⊆ A, in the obvious meaning. For example, X ⊆_{I} Y iff X \ Y ∈ I.

For a filter F over A, the dual definitions f <_{F} g, f ≤_{F} g etc. will be used as well. For example, f <_{F} g means that {a ∈ A | f(a) < g(a)} ∈ F. If F is the dual of an ideal I, then <_{F} and <_{I} are the same relation of course.

Products of sets

Suppose that A is an index set and S = ⟨S_{a} | a ∈ A⟩ is a sequence of non-empty sets of ordinals. Then the product, denoted ΠS or Π_{a∈A} S_{a}, is defined as

ΠS = {f | f ∈ Ord^{A} and ∀a ∈ A f(a) ∈ S_{a}}.

In particular, if h : A → Ord is any ordinal function defined on A, then Πh (or Π_{a∈A} h(a)) denotes the set of all ordinal functions f defined on A such that f(a) ∈ h(a) for all a ∈ A.

If A is a set of cardinals, then ΠA (or Π_{a∈A} a) denotes the set of all ordinal function f defined on A such that f(a) ∈ a for all a ∈ A. That is, ΠA is Πh where h(a) = a is the identity function on A.

For an ideal I over A, the relations <_{I}, ≤_{I}, and =_{I} are defined on Πh, and the reduced product Πh/I consisting of all =_{I} equivalence classes is obtained. If g ∈ Ord^{A}, then we may write (somewhat informally) g ∈ Πh/I rather than [g] ∈ Πh/I, that is Πh/I is considered as a class of functions rather than equivalence classes.

A sequence of functions f = ⟨f_{ξ} | ξ < λ⟩ in ΠA is said to be <_{I}-increasing if ξ_{1} < ξ_{2} implies that f_{ξ_{1}} <_{I} f_{ξ_{2}}. For typographical reason we also say that f is I-increasing, or “increasing modulo I” instead of <_{I}-increasing. A sequence is a function, and if f_{ξ} denotes a value of that function then the sequence itself is denoted f, not f̄ or F.

Partial orderings

We say that (P, ≤_{P}) is a quasi-ordering iff ≤_{P} is a reflexive and transitive relation on P. A strict partial ordering is a transitive and irreflexive relation <_{P} on P. In this chapter we consider both the quasi-ordering ≤_{I} and the strict partial ordering <_{I}, defined on ordinal valued functions. A typical example is P = Πh with the orderings <_{I} and ≤_{I} where h ∈ Ord^{A} is such that h(a) > 0 is a limit ordinal for every a ∈ A. Thus every function in P is <_{I} bounded by another function there (for every f ∈ Πh, f <_{I} f + 1, where f + 1 is the function taking a to f(a) + 1). So our setting is a structure (P, <_{P} , ≤_{P}) where <_{P} is irreflexive and transitive, and ≤_{P} is a quasi-ordering. The following properties of (P, <_{P} , ≤_{P}) are obvious for our typical example:

P1 a <_{P} b or a = b implies a ≤_{P} b, but this implication is not necessarily reversible.

P2 If a <_{P} b ≤_{P} c or a ≤_{P} b <_{P} c, then a <_{P} c.

P3 There is no <_{P} maximal member: for every p ∈ P there exists some p′ ∈ P with p <_{P} p′.

Then we have the following definitions made whenever P is a set or a class, <_{P} is a strict partial ordering, and ≤_{P} a quasi-ordering on P.

A collection B ⊆ P is said to be cofinal in P iff for all x ∈ P there is some y ∈ B with x ≤_{P} y. B is <_{P} -cofinal if ∀x ∈ P ∃y ∈ B(x <_{P} y). If B is cofinal, and p ∈ P then we can first find p′ ∈ P such that p <_{P} p′ (by property P3 above) and then find y ∈ B such that p′ ≤_{P} y. Then p <_{P} y. Thus we can replace ≤_{P} with <_{P} in the definition of “cofinal”. The cofinality, cf(P, ≤_{P}), of the partial ordering set is the smallest cardinality of a cofinal subset. (Again cf(P, <_{P}) is similarly defined and these two cardinals are equal if properties P1–P3 above hold). This cardinal needs not be regular, if the ordering is not total (linear). We say that (P, <_{P}) has “true” cofinality if it has a totally ordered subset B ⊆ P that is cofinal. In this case the cofinality of B itself, and hence of P, is a regular cardinal. Observe that if (P, <) has a linear cofinal subset whose order-type is a regular cardinal λ, then λ is the cofinality of P (because no cofinal subset of P is of smaller cardinality, even if non-linear subsets are considered). When (P, <_{P}) has true cofinality, we write

tcf (P, <_{P}) = λ

to express both the fact that a totally ordered cofinal set exists, and that λ is the minimal cardinality of such a cofinal set.

In cases (when P3 above is not assumed) that (P, ≤_{P}) has a greatest element, then the cofinality of P is defined to be 1 and its true cofinality is also 1, but since we assume that there are no <_{P} maximal elements the cofinality and true cofinality (when it exists) are always infinite cardinals.

The following observation was made by Pouzet. For any infinite cardinal λ, tcf (P, <_{P}) = λ if and only if the following conditions hold:

1. (P, <_{P}) has a cofinal set of size λ.

2. (P, <_{P}) is λ-directed: any set X ⊆ P of size < λ has an upper bound in (P, <_{P}).

It follows that if tcf(P, <_{P}) = λ and G ⊆ P is any cofinal subset, then tcf G = λ as well.

A sequence ⟨p_{ξ} | ξ < λ⟩ of members of P is defined to be persistently cofinal iff

∀h ∈ P ∃ξ_{0} < λ ∀ξ (ξ_{0} ≤ ξ < λ ⟹ h <_{P} p_{ξ}).  (I.3)

Clearly every <_{P} increasing and cofinal sequence is persistently cofinal. If ⟨p_{ξ} | ξ < λ⟩ is persistently cofinal and p_{ξ} ≤_{P} p′_{ξ} for every ξ < λ, then ⟨p′_{ξ} | ξ < λ⟩ is persistently cofinal as well.

If (P, ≤_{P}) is a quasi-ordering and X ⊆ P, then an upper bound of X is some a ∈ P such that x ≤_{P} a for all x ∈ X. If a is an upper bound of X and a ≤_{P} a′ for every upper bound a′ ∈ P of X, then we say that a is a least upper bound of X. We say that an upper bound a of X is a minimal upper bound if there is no upper bound a′ of X such that a′ ≤_{P} a ∧ ¬(a ≤_{P} a′).

Suppose that (P, <_{P} , ≤_{P}) is as above and X ⊆ P is such that for every x ∈ X there is x′ ∈ X with x <_{P} x′ (for example X is an increasing sequence in <_{P}). Then a ∈ P is an exact upper bound of X iff

1. a is a least upper bound of X, and

2. X is cofinal in {p ∈ P | p <_{P} a}. Namely p <_{P} a implies ∃x ∈ X(p ≤_{P} x).

Exercises are natural places to stop and think, but it is not an absolute requirement to solve them on first encounter. In fact, they often become easy with later material.

2.1 Exercise. Let λ > |A| be a regular cardinal, and f = ⟨f_{ξ} | ξ < λ⟩ an increasing sequence of functions in Ord^{A} in the < ordering (of everywhere dominance). Then f has an exact upper bound h and cf(h(a)) = λ for every a ∈ A. In fact sup f is the required upper bound.

We repeat the definitions given above, for (Ord^{A}, <_{I}, ≤_{I}) where I is a proper ideal over A. So, if F ⊂ Ord^{A} then

h ∈ Ord^{A} is an upper bound of F iff f ≤_{I} h for every f ∈ F.

A function h is a least upper bound of F if it is an upper bound and h ≤_{I} h′ for every upper bound h′ ∈ Ord^{A} of F. Here, the notions of least upper bound and minimal upper bound coincide.

If h ∈ Ord^{A} and h(a) = 0 for some a ∈ A, then Πh = ∅. So, to avoid triviality h(a) > 0 is assumed for all a ∈ A, whenever the expression Πh is used. Hence if I is an ideal over A then every g ∈ Ord^{A} such that g <_{I} h is =_{I} equivalent to some function in Πh. In fact, we shall usually consider reduced products Πh/I for functions h such that h(a) > 0 is always a limit ordinal, and hence every function in Πh is <-bounded (everywhere dominated) by some function in Πh.

Suppose that F is a (non-empty) set of functions in Ord^{A} such that for every f ∈ F there exists some f′ ∈ F with f <_{I} f′. Then h ∈ Ord^{A} is an exact upper bound of F if h is a least upper bound of F and for every g <_{I} h there is some f ∈ F with g <_{I} f (namely F is cofinal in the lower <_{I} cone determined by h). Actually it is not necessary to require that h is a least upper bound of F since this follows from the assumptions that h is an upper bound of F and F is cofinal in Πh/I. Thus if F ⊆ Πh/I then h is an exact upper bound of F iff F is cofinal in Πh/I.

If h is an exact upper bound of F and A_{0} ∈ I^{+} then h ↾ A_{0} is an exact upper bound of ⟨f ↾ A_{0} | f ∈ F ⟩ with respect to the proper ideal I ∩ P(A_{0}).

If h is an exact upper bound of F with respect to some ideal I over A and J ⊇ I is a larger ideal over A, then h is an exact upper bound of F modulo J as well.

The definition of “true cofinality” of a reduced product is so important for the pcf theory that we restate it for this case.

2.2 Definition. We say that tcf(Πh/I) = λ iff λ is a regular cardinal and there exists a <_{I}-increasing sequence f = ⟨f_{ξ} | ξ < λ⟩ in Πh that is cofinal in Πh/I.

Projections

We shall often encounter the following situation.

1. A is a non-empty set of indices, and S = ⟨S_{a} | a ∈ A⟩ is a sequence of sets of ordinals. The sup of S function is defined on A by taking a ∈ A to sup S_{a}.

2. An ordinal function f ∈ Ord^{A} is given that is bounded by the sup of S, namely f(a) < sup S_{a} for every a ∈ A.

Then we define the projection of f onto ΠS, denoted proj(f, S), as the function f^{+} ∈ ΠS defined by

f^{+}(a) = min(S_{a} \ f(a)).

So f^{+}(a) = f(a) in case f(a) ∈ S_{a}, and otherwise f^{+}(a) is the least ordinal in S_{a} above f(a). (There is such an ordinal by our assumption.) It is clear that f^{+} is the least function in ΠS that bounds f, and that f_{1} ≤ f_{2} implies f_{1}^{+} ≤ f_{2}^{+}.

We shall apply projections in the presence of an ideal I over A. If f ∈ Ord^{A} is any function, not necessarily bounded by sup of S, we define f^{+} = proj(f, S) as follows. For a ∈ A such that f(a) < sup S_{a}, we define f^{+}(a) = min(S_{a} \ f(a)) as before, and for a ∈ A such that f(a) ≥ sup S_{a} we define f^{+}(a) = 0. Clearly, f_{1} =_{I} f_{2} implies that f_{1}^{+} =_{I} f_{2}^{+}. It follows, in case f <_{I} sup S, that f^{+} is the ≤_{I}-least function in Π_{a∈A} S_{a} that ≤_{I}-bounds f, up to =_{I} equivalence.

Given an ideal I over a set A, and an ordinal function h ∈ Ord^{A}, we are interested in the existence and value of the true cofinality of Πh/I. Our first step is to reduce this question to ultraproducts of regular cardinals, and we can proceed as follows. Choose for every a ∈ A a cofinal set S(a) ⊆ h(a) of order-type cf(h(a)). By our assumption that h(a) > 0 is always a limit, non-zero ordinal, the order type of S(a) is a regular infinite cardinal. Then the collections Πh and Π_{a∈A} S(a) are cofinally equivalent. That is for every f ∈ Πh there is g ∈ ΠS with f ≤ g (namely it projection), and vice versa.

Next, Π_{a∈A} S(a) is isomorphic to Π_{a∈A} |S(a)| = Π_{a∈A}cf(h(a)). This is also the case when an ideal I over A is introduced and the relation ≤_{I} is considered. Then Πh/I has the same cofinality and true cofinality as Π_{a∈A} cf(h(a))/I. Hence it suffices to consider reduced products Π_{a∈A} k(a)/I of functions k such that k(a) are infinite regular cardinals. As the following lemma shows, in some cases we may even take k to be one-to-one.

2.3 Lemma. Suppose that c : A → Regular Cardinals is a function and B = {c(a) | a ∈ A} is its range. If I is any ideal over A, and J is its Rudin-Keisler projection on B defined by

X ∈ J iff X ⊆ B and c^{−1}X ∈ I,

where c^{−1}X = {a ∈ A | c(a) ∈ X}. Then there is an order-preserving isomorphism h : ΠB/J → Π_{a∈A} c(a)/I defined by h([e]_{J}) = [e ∘ c]_{I}, for every e ∈ ΠB. If |A| < min B, then

tcf(ΠB/J) = tcf(Π_{a∈A} c(a)/I)  (I.4)

in the sense that existence of the true cofinality for one of ΠB/J and Πc/I implies existence for the other poset as well, and these cofinalities are equal.

Proof. For every e ∈ ΠB define ē ∈ Πc by ē(a) = e(c(a)). That is, ē = e ∘ c. Then e_{1} =_{J} e_{2} iff ē_{1} =_{I} ē_{2}, and e_{1} <_{J} e_{2} iff ē_{1} <_{I} ē_{2}. Thus h([e]_{J}) = ē/I induces an isomorphism from ΠB/J into Πc/I. Hence tcf (ΠB/J) is the same as the true cofinality of

G = {h([e]_{J}) | e ∈ ΠB}

in <_{I}. If |A| < min B, then G will be shown to be cofinal in Πc/I and this implies (I.4). (In general, if G is any cofinal subset of a partial ordering (P, <_{P}), then G and P have the same true cofinality.)

Now G is cofinal in Πc/I, because any g ∈ Πc is bounded by f̄ where f ∈ ΠB is defined by

f(b) = sup{g(a) | a ∈ A and c(a) = b}.

The fact that |A| < b is used here to deduce that this supremum is below the regular cardinal b ∈ B, and hence that f ∈ ΠB. Since f̄/I ∈ G, G is cofinal in Πc. ⊣

To see how this lemma is applied, suppose that λ is a regular cardinal and f = ⟨f_{ξ} | ξ < λ⟩ is a <_{I} increasing sequence of functions f_{ξ} ∈ Ord^{A}. Then (as we have said) h ∈ Ord^{A} is an exact upper bound of f iff f is cofinal in Πh/I. In this case it follows that tcf(Πh/I) = λ and hence that the true cofinality of Π_{a∈A} cf(h(a)) is λ. Let B = {cf(h(a)) | a ∈ A} be the set of cofinalities of the range of h. The preceding lemma shows that λ is the true cofinality of a reduced product of B, if |A| < cf(h(a)) for every a ∈ A.

2.1. Existence of exact upper bounds

An important piece of the pcf theory is the determination of conditions that ensure the existence of exact upper bounds. Recall that an exact upper bound of a <_{I}-increasing sequence ⟨f_{ξ} | ξ < λ⟩ of functions in Ord^{A} is a function g ∈ Ord^{A} that bounds every f_{ξ} in the ≤_{I} relation and satisfies the additional requirement that if d <_{I} g then d <_{I} f_{ξ} for some ξ < λ. The following and Definition 2.8 are central in our presentation of the pcf theory.

2.4 Definition. [Strongly increasing] Suppose that I is an ideal over A and f = ⟨f_{ξ} | ξ ∈ L⟩ is a <_{I}-increasing sequence of functions f_{ξ} ∈ Ord^{A}, where L is a set of ordinals. Then f is said to be strongly increasing if there are null sets Z_{ξ} ∈ I, for ξ ∈ L, such that whenever ξ_{1} < ξ_{2} are in L

a ∈ A \ (Z_{ξ_{1}} ∪ Z_{ξ_{2}}) ⟹ f_{ξ_{1}}(a) < f_{ξ_{2}}(a).

2.5 Exercise. An even stronger property would be to require that there are null sets Z_{ξ} ∈ I for ξ ∈ L such that whenever ξ_{1} < ξ_{2}

a ∈ A \ Z_{ξ_{2}} → f_{ξ_{1}}(a) < f_{ξ_{2}}(a).

Prove that a sequence f = ⟨f_{ξ} | ξ ∈ L⟩ satisfies this stronger property iff for every ξ ∈ L

sup{f_{α} + 1 | α ∈ L ∩ ξ} ≤_{I} f_{ξ}.  (I.5)

(Recall that f + 1 is the function that takes x to f(x) + 1.)

2.6 Exercise. Let I be an ideal over A, λ > |A| be a regular cardinal, and f = ⟨f_{ξ} | ξ < λ⟩ be a <_{I} increasing sequence of functions in Ord^{A}. Then the following conditions are equivalent:

1. f contains a strongly increasing subsequence of length λ.

2. f has an exact upper bound h such that cf(h(a)) = λ for (I-almost) all a ∈ A.

3. f is cofinally equivalent to some < (i.e. everywhere) increasing sequence of length λ.

Hint. If f (or a subsequence) is strongly increasing, let Z_{ξ} ∈ I be the null sets associated with f_{ξ} and define

h(a) = sup{f_{ξ}(a) | a ∉ Z_{ξ}}.

Prove that h is an exact upper bound as required to prove that 1 implies 2.

Since |A| < λ, it is obvious that 2 implies 3. (For every a ∈ A choose a cofinal subset of h(a) of order-type λ, and let d_{ξ} be the “flat” function which assigns to d_{ξ}(a) the ξth point in the h(a) cofinal subset.)

To prove that 3 implies 1, use the following lemma.

2.7 Lemma. (The sandwich argument) Suppose that d = ⟨d_{ξ} | ξ ∈ λ⟩ is strongly increasing and f_{ξ} ∈ Ord^{A} is such that

d_{ξ} <_{I} f_{ξ} ≤_{I} d_{ξ+1} for every ξ ∈ λ.

Then ⟨f_{ξ} | ξ ∈ λ⟩ is also strongly increasing.

Proof. Let Z_{ξ} ∈ I be the null sets that testify that the sequence d is strongly increasing. For every f_{ξ}, sandwiched between d_{ξ} and d_{ξ+1}, there exists W_{ξ} ∈ I such that

d_{ξ}(a) < f_{ξ}(a) ≤ d_{ξ+1}(a) for all a ∈ A \ W_{ξ}.

Define Z^{ξ} = W_{ξ} ∪ Z_{ξ} ∪ Z_{ξ+1}. Then Z^{ξ} ∈ I, and if ξ_{1} < ξ_{2} then for every a ∈ A \ (Z^{ξ_{1}} ∪ Z^{ξ_{2}})

f_{ξ_{1}}(a) ≤ d_{ξ_{1}+1}(a) ≤ d_{ξ_{2}}(a) < f_{ξ_{2}}(a).
⊣

2.8 Definition. Suppose that I is an ideal over a set A, λ is a regular cardinal, and f = ⟨f_{ξ} | ξ ∈ λ⟩ is a <_{I}-increasing sequence of functions f_{ξ} ∈ Ord^{A}. For any regular cardinal κ such that κ ≤ λ the following crucial property of κ (and f etc.) is denoted (∗)_{κ}:

(∗)_{κ} Whenever X ⊆ λ is unbounded, then for some X_{0} ⊆ X of order type κ, ⟨f_{ξ} | ξ ∈ X_{0}⟩ is strongly increasing.

Thus (∗)_{κ} is some kind of a partition relation, saying that any unbounded subsequence ⟨f_{ξ} | ξ ∈ X⟩ contains a strongly increasing subsequence of length κ. Clearly (∗)_{κ} implies (∗)_{κ′} for all regular κ′ < κ.

2.9 Exercise. 1. Assume κ < λ. Prove that (∗)_{κ} holds iff the set of ordinals δ ∈ λ with cf(δ) = κ and such that ⟨f_{ξ} | ξ ∈ X_{0}⟩ is strongly increasing for some unbounded set X_{0} ⊆ δ is stationary in λ.

2. Use the Erdos-Rado theorem (2^{κ})^{+} → (κ^{+})_{κ}^{2} to prove that if λ ≥ (2^{|A|})^{+} and f is a <_{I} increasing sequence of functions as above, of length λ, then (∗)_{|A|^{+}} holds.

Hint for 2. For i < j, if there exists some a ∈ A such that f_{i}(a) > f_{j}(a), then define c(i, j) = a for such an a. Otherwise define c(i, j) = −1. The homogeneous set must be of color -1, and (∗)_{|A|^{+}} can be derived by taking a subsequence.

We shall give (in Lemma 2.19) conditions that ensure property (∗)_{κ} (without any assumptions on 2^{κ}), but meanwhile the following lemma and theorem explain the main use of (∗)_{κ}.

2.10 Definition (Bounding projection). Suppose that I is an ideal over A, λ is a regular cardinal, and f = ⟨f_{ξ} | ξ < λ⟩ is a <_{I}-increasing sequence of functions in Ord^{A}. Let κ ≤ λ be any regular cardinal. We say that f has the bounding projection property for κ if whenever S = ⟨S(a) | a ∈ A⟩ with S(a) ⊂ Ord and |S(a)| < κ is such that the sequence f is <_{I}-bounded by the function sup of S, then there exists ξ < λ such that f_{ξ}^{+} = proj(f_{ξ}, ⟨S_{a} | a ∈ A⟩) is an upper bound of f in the <_{I} relation. (Recall that Sup of S(a) = sup S(a) for all a ∈ A.)

2.11 Exercise. 1. If f = ⟨f_{ξ} | ξ < λ⟩ has the bounding projection property for κ and f′ = ⟨f′_{ξ} | ξ < λ⟩ is such that f′_{ξ} =_{I} f_{ξ} for every ξ, then f′ too has the bounding projection property for κ.

2. A seemingly weaker property is obtained by requiring that the sup of S map <-bounds (i.e. everywhere) each f_{ξ}. Prove that these two definitions are equivalent.

2.12 Lemma (The bounding projection lemma). Suppose that I is an ideal over A, λ > |A| is a regular cardinal, and f = ⟨f_{ξ} | ξ < λ⟩ is a <_{I}-increasing sequence satisfying (∗)_{κ} for a regular cardinal κ such that |A| < κ ≤ λ. Then f satisfies the bounding projection property for κ.

Later on, we shall see that (∗)_{κ} is, in fact, equivalent to the bounding projection property for κ (see Theorem 2.15 for an exact formulation).

Proof. Suppose that the lemma is false and S is a counter-example, and we shall obtain a contradiction. By changing each f_{ξ} on an I set, we do not spoil the (∗)_{κ} property, and we may assume that f_{ξ}(a) < sup S_{a} for all a ∈ A (here S_{a} = S(a)). Then define

f_{ξ}^{+} = proj(f_{ξ}, ⟨S_{a} | a ∈ A⟩).

Since f_{ξ}^{+} is not a <_{I}-upper bound, there exists ξ′ < λ such that ≤(f_{ξ}^{+}, f_{ξ′}) ∈ I^{+}. That is f_{ξ}^{+}(a) ≤ f_{ξ′}(a) for an I-positive set of a ∈ A. Hence < (f_{ξ}^{+}, f_{ξ′′}) ∈ I^{+} for every ξ′′ above ξ′. This enables the definition of an unbounded set X ⊆ λ such that

if ξ, ξ′ ∈ X and ξ < ξ′ then <(f_{ξ}^{+}, f_{ξ′}) ∈ I^{+}.

Since (∗)_{κ} holds, there exists a set X_{0} ⊆ X of order-type κ such that ⟨f_{ξ} | ξ ∈ X_{0}⟩ is strongly increasing. Let Z_{ξ} ∈ I for ξ ∈ X_{0} be as in the definition of strong increase (2.4).

For every ξ ∈ X_{0} let ξ′ = min X_{0} \ (ξ + 1) be the successor of ξ in X_{0}, and pick

a_{ξ} ∈ <(f_{ξ}^{+}, f_{ξ′}) \ (Z_{ξ} ∪ Z_{ξ′}).

As κ > |A|, we may find a single a ∈ A such that a = a_{ξ} for a subset X_{1} of X_{0} of cardinality κ. Now for ξ_{1} < ξ_{2} in X_{1}

f_{ξ_{1}}^{+}(a) < f_{ξ′_{1}}(a) ≤ f_{ξ_{2}}(a) ≤ f_{ξ_{2}}^{+}(a).

(The first inequality is a consequence of a_{ξ_{1}} ∈ <(f_{ξ_{1}}^{+}, f_{ξ′_{1}}), the second follows from ξ′_{1} ≤ ξ_{2} and the fact that

a = a_{ξ_{1}} = a_{ξ_{2}} ∈ A \ (Z_{ξ′_{1}} ∪ Z_{ξ_{2}}),

and the third inequality is obvious from the definition of f_{ξ_{2}}^{+}.)

But now f_{ξ}^{+}(a) ∈ S_{a} turns out to be strictly increasing with ξ ∈ X_{1}, which is absurd since |S_{a}| < κ. ⊣ 2.13 Theorem (Exact upper bounds). Suppose that I is an ideal over A, λ > |A|^{+} is a regular cardinal, and f = ⟨f_{ξ} | ξ ∈ λ⟩ is a <_{I}-increasing sequence of functions in Ord^{A} that satisfies the bounding projection property for |A|^{+}. Then f has an exact upper bound.

Proof. Assume the |A|^{+} bounding projection property for a sequence f that is <_{I}-increasing of length a regular cardinal λ > |A|^{+}. We shall prove first that there exists a minimal upper bound to f, and then prove that this bound is necessarily an exact upper bound. Seeking a contradiction, suppose that f has no minimal upper bound. So for every h ∈ Ord^{A}, if h is an upper bound to the sequence f then it is not a minimal upper bound, and there is another upper bound h′ ∈ Ord^{A} to f such that h′ ≤ h and {a ∈ A | h′(a) < h(a)} ∈ I^{+}.

We shall define by induction on α < |A|^{+} a sequence S^{α} = ⟨S^{α}(a) | a ∈ A⟩ of sets of ordinals satisfying |S^{α}(a)| ≤ |A|, and such that:

1. The sequence of functions f is bounded by the map a ↦ sup S^{α}(a). So, the projections can always be defined.

2. The sets S^{α}(a) are increasing with α: if α < β then S^{α}(a) ⊆ S^{β}(a) for every a ∈ A. For a limit ordinal δ, S^{δ}(a) = ⋃_{α<δ} S^{α}(a).

To define S^{0}, we pick a function h_{0} that bounds f and define S^{0}(a) = {h_{0}(a)}.

Suppose that S^{α} = ⟨S^{α}(a) | a ∈ A⟩ has been defined. Since the bounding projection property for |A|^{+} holds and the cardinality of S^{α}(a) is ≤ |A|, there exists some ξ = ξ(α) < λ such that h_{α} = proj(f_{ξ}, S^{α}) is an upper bound of f. It follows for every ξ′ satisfying ξ ≤ ξ′ < λ that h_{α} =_{I} proj(f_{ξ′}, S^{α}).

Since h_{α} is not a minimal upper bound, there exists an upper bound u to the sequence f such that u ≤ h_{α} and

<(u, h_{α}) ∈ I^{+}.

Define S^{α+1}(a) = S^{α}(a) ∪ {u(a)}. Then proj(f_{ξ}, S^{α+1}) =_{I} u for all ξ(α) ≤ ξ < λ.

Now let ξ < λ be a fixed ordinal greater than every ξ(α) for α < |A|^{+} (recall that λ is a regular cardinal above |A|^{+}). Consider the functions H_{α} = proj(f_{ξ}, S^{α}) for α < |A|^{+}. Since f_{ξ} is above f_{ξ(α)}, H_{α} =_{I} h_{α}. Thus <(H_{α+1}, H_{α}) ∈ I^{+}. Since α_{1} < α_{2} < |A|^{+} implies that S^{α_{1}}(a) ⊆ S^{α_{2}}(a) for all a ∈ A, the sequence of projections ⟨H_{α} | α < |A|^{+}⟩ thus obtained satisfies the following property:

If α_{1} < α_{2} < |A|^{+}, then H_{α_{2}} ≤ H_{α_{1}} and <(H_{α_{2}}, H_{α_{1}}) ∈ I^{+}.

Yet this is impossible and leads immediately to a contradiction. For every α < |A|^{+} pick some a ∈ A such that H_{α+1}(a) < H_{α}(a). Then the same fixed a ∈ A is picked for an unbounded set of indices α ∈ |A|^{+}. Yet as the functions H_{α} are ≤-decreasing, this yields an infinite strictly descending sequence of ordinals! ⊣

Now that the existence of a minimal upper-bound is established, the following lemma concludes the theorem.

2.14 Lemma. Suppose that I is an ideal over A, λ is a regular cardinal, and f = ⟨f_{ξ} | ξ ∈ λ⟩ is a <_{I}-increasing sequence of functions in Ord^{A} that satisfies the bounding projection property for κ = 3. Let h be a minimal upper bound of f. Then h is an exact upper bound.

Proof. Assume that f satisfies the bounding projection property for 3, and h is a minimal upper bound of f. Suppose that g ∈ Ord^{A} is such that g <_{I} h. We must find f_{ξ} in the sequence f with g <_{I} f_{ξ}. For simplicity, and without loss of generality, we can assume that g(a) < h(a) for all a ∈ A.

Define S_{a} = {g(a), h(a)} for every a ∈ A. The bounding projection property implies the existence of ξ < λ for which f_{ξ}^{+} = proj(f_{ξ}, ⟨S_{a} | a ∈ A⟩) is an upper bound of the sequence f. We shall prove that g <_{I} f_{ξ} as required. Observe that

f_{ξ}^{+} =_{I} h  (I.6)

or else f_{ξ}^{+}(a) = g(a) < h(a) for a positive set of a’s in A. But then f_{ξ}^{+} is an upper-bound of f that is smaller than the minimal upper bound h on a positive set of indices, and this is impossible. Hence (I.6). Yet, for every a such that f_{ξ}^{+}(a) = h(a), g(a) < f_{ξ}(a) follows from the fact that g(a) ∈ S_{a}. Thus g <_{I} f_{ξ}. This proves the lemma. ⊣

The bounding projection lemma 2.12 and the exact upper bounds theorem 2.13 show together that a <_{I}-increasing sequence of length a regular cardinal λ > |A|^{+} and which satisfies (∗)_{|A|^{+}} has necessarily an exact upper bound h. As we shall see in the following theorem it can be deduced that

∀a ∈ A cf(h(a)) ≥ |A|^{+}.

2.15 Theorem. Suppose that I is an ideal over A, λ > |A|^{+} is a regular cardinal, and f = ⟨f_{ξ} | ξ ∈ λ⟩ is a <_{I}-increasing sequence of functions in Ord^{A}. Then for every regular cardinal κ such that |A|^{+} ≤ κ ≤ λ the following are equivalent.

1. (∗)_{κ} holds for f.

2. f satisfies the bounding projection property for κ.

3. The sequence f has an exact upper bound g for which

{a ∈ A | cf(g(a)) < κ} ∈ I.

Proof. Let κ be a regular cardinal such that |A|^{+} ≤ κ ≤ λ. Implication 1 ⟹ 2 was proved in Lemma 2.12, and so the proof starts with 2 ⟹ 3 .

Since f satisfies the bounding projection property for some cardinal that is ≥ |A|^{+}, it satisfies the bounding projection property for |A|^{+}. Theorem 2.13 above implies that f has an exact upper bound g. This exact upper bound is determined up to =_{I}, and we may assume that g(a) is never 0 or a successor ordinal (recall that the sequence f is <_{I}-increasing).

Suppose that P = {a ∈ A | cf(g(a)) < κ} ∈ I^{+} is positive, in contradiction to 3. Choose, for every a ∈ P, S(a) ⊆ g(a) cofinal in g(a) and such that order-type(S(a)) < κ. For a ∈ A \ P define S(a) = {g(a)}. Then the bounding projection property for κ gives some ξ < λ such that the projection

f_{ξ}^{+} = proj(f_{ξ}, ⟨S(a) | a ∈ A⟩)

is an upper bound of f in Π_{a∈A} S(a). But this is impossible since f_{ξ}^{+} ↾ P < g ↾ P (everywhere on P) is in contradiction to our assumption that g is the ≤_{I}-minimal upper bound of f.

We continue with proving that 3 ⟹ 1 . Suppose that g is an exact upper bound for f such that cf(g(a)) ≥ κ for all a ∈ A (change g on a null set if necessary). Choose S(a) ⊆ g(a) cofinal in g(a), closed, and with order type cf(g(a)). So order-type(S(a)) ≥ κ. We prove that (∗)_{κ} holds. Assuming that X ⊆ λ is unbounded, we shall find X_{0} ⊆ X of order-type κ over which f is strongly increasing. For this we intend to define by induction on α < κ a function h_{α} ∈ Π_{a∈A} S(a) = ΠS and an index ξ(α) ∈ X such that

1. h_{α} <_{I} f_{ξ(α)} <_{I} h_{α+1}.

2. The sequence ⟨h_{α} | α < κ⟩ is < increasing (increasing everywhere). And hence it is certainly strongly increasing.

Then the sandwich argument (Lemma 2.7) will show that {f_{ξ(α)} | α < κ} is strongly increasing.

The functions h_{α} are defined as follows.

1. h_{0} ∈ Π_{a∈A} S(a) is any function.

2. If δ < κ is a limit ordinal, then define

h_{δ} = sup{h_{α} | α < δ}.

That is

h_{δ}(a) = ⋃{h_{α}(a) | α < δ}

for every a ∈ A. Since each S(a) has regular order type ≥ κ, and as δ < κ, clearly h_{δ} ∈ Π_{a∈A} S(a).

3. If h_{α} ∈ Π_{a∈A} S(a) is defined then it is bounded by g (since S(a) ⊆ g(a)) and hence (as g is an exact upper bound) h_{α} <_{I} f_{ξ} for some ξ ∈ X, which we denote ξ(α). Now let f_{ξ(α)}^{+} = proj(f_{ξ(α)}, S) be the projection function, and define h_{α+1} ∈ ΠS so that h_{α+1} > sup{h_{α}, f_{ξ(α)}^{+}}.

Thus h_{α+1} > h_{α} and since f_{ξ(α)} ≤_{I} f_{ξ(α)}^{+} we have

h_{α} <_{I} f_{ξ(α)} <_{I} h_{α+1}, for every α.  (I.7)

Hence

X_{0} = {ξ(α) | α ∈ κ} ⊆ X

is an increasing enumeration, and it is an evidence for (∗)_{κ} (by the sandwich argument and since ⟨h_{α} | α < κ⟩ is strongly increasing). ⊣

We shall give in Lemma 2.19 below a useful condition on f from which (∗)_{κ} follows. But first we need a combinatorial theorem.

2.16 Definition. If S ⊆ λ is a stationary set, then a club guessing sequence is a sequence ⟨C_{δ} | δ ∈ S⟩, where each C_{δ} ⊆ δ is closed unbounded in δ, such that for every closed unbounded D ⊆ λ there exists some δ ∈ S with C_{δ} ⊆ D.

We shall use the notation S_{κ}^{λ} = {δ ∈ λ | cf(δ) = κ}. Clearly for regular infinite cardinals κ < λ, S_{κ}^{λ} is stationary in λ.

2.17 Theorem (Club Guessing). For every regular cardinal κ, if λ is a cardinal such that cf(λ) ≥ κ^{++}, then any stationary set S ⊆ S_{κ}^{λ} has a clubguessing sequence ⟨C_{δ} | δ ∈ S⟩ (such that C_{δ} ⊆ δ is closed unbounded of order type κ).

Proof. We shall prove this for uncountable κ’s, though the theorem holds for κ = ℵ_{0} as well.

Let S ⊆ S_{κ}^{λ} be any stationary set. Fix a sequence C = ⟨C_{δ} | δ ∈ S⟩ such that C_{δ} ⊆ δ is closed unbounded of order type κ, for every δ ∈ S. If E ⊆ λ is any closed unbounded set, define

C | E = ⟨C_{δ} ∩ E | δ ∈ S ∩ E′⟩.

Here E′ = {δ ∈ E | E ∩ δ is unbounded in δ} is the set of accumulation points of E. Clearly E′ ⊆ E is closed unbounded. The sequence C | E is defined on S ∩ E′ in order to ensure that C_{δ} ∩ E is closed unbounded in δ.

We claim that for some closed unbounded set E ⊆ λ, C | E is clubguessing. (The theorem demands a sequence defined on every δ ∈ S, but this is trivially obtained once a guessing sequence is defined on a closed unbounded set intersected with S.)

To prove this claim, assume that it is false, and for every closed unbounded set E ⊆ λ there is some closed unbounded set D_{E} ⊆ λ not guessed by C | E. That is, for every δ ∈ S_{κ}^{λ} ∩ E′

C_{δ} ∩ E ⊈ D_{E}.

So we can define a decreasing (under inclusion) sequence of closed unbounded sets E^{α} ⊆ λ for α < κ^{+} by induction on α as follows.

1. E^{0} = λ.

2. If γ < κ^{+} is a limit ordinal, and E^{α} for α < γ are already defined, let E^{γ} = ⋂{E^{α} | α < γ}. Clearly E^{γ} ⊆ λ is closed unbounded.

3. If E^{α} is defined, then E^{α+1} = (E^{α}∩D_{E^{α}})′. So for every δ ∈ S_{κ}^{λ}∩E^{α+1}, C_{δ} ∩ E^{α} ⊈ E^{α+1}.

Let E = ⋂{E^{α} | α < κ^{+}}. Again E ⊆ λ is closed unbounded because cf(λ) > κ^{+}.

Now we get the contradiction. Take any δ ∈ S_{κ}^{λ} ∩ E. There exists some α < κ^{+} such that C_{δ} ∩ E = C_{δ} ∩ E^{α} (since the sets E^{α} are decreasing in ⊆ and C_{δ} has cardinality κ). So C_{δ} ∩ E^{α} = C_{δ} ∩ E^{α′} for every α′ > α, and in particular for α′ = α + 1. But as δ ∈ S_{κ}^{λ} ∩ E^{α+1}, C_{δ} ∩ E^{α} ⊈ E^{α+1}. ⊣

2.18 Exercise. 1. Club guessing is a relative of the diamond principle which gives much stronger guessing properties. For example, prove that ♢_{ω_{2}}^{+}, implies a sequence ⟨C_{δ} | δ ∈ S_{ω_{1}}^{ω_{2}}⟩ with C_{δ} closed unbounded in δ such that for every closed unbounded set E ⊂ ω_{2}, there exists a closed unbounded set D ⊆ ω_{2} such that for every δ ∈ S_{ω_{1}}^{ω_{2}} ∩ D, C_{δ} is almost contained in E (i.e. except a bounded set). Prove that it is not possible to have full guessing at a closed unbounded set. That is, it is not possible to require that C_{δ} ⊆ E for every δ ∈ S_{ω_{1}}^{ω_{2}} ∩ D.

2. Prove the club-guessing theorem for κ = ℵ_{0} as well.

Hint. For S ⊆ S_{ℵ_{0}}^{λ} fix C = ⟨C_{δ} | δ ∈ S⟩ where each C_{δ} is an ωsequence unbounded in δ. For every closed unbounded set E ⊆ λ define the “gluing to E” sequence C | E = ⟨C_{δ}^{∗} | δ ∈ S ∩ E^{∗}⟩ by

C_{δ}^{∗}(n) = max(E ∩ (C_{δ}(n) + 1)).

Try to prove that for some club E ⊆ λ, C | E is club guessing. Have enough patience for ω_{1} trials.

Club guessing is used in the following lemma which produces sequences that satisfy (∗)_{κ}.

2.19 Lemma. Suppose that

1. I is a proper ideal over A.

2. κ and λ are regular cardinals such that κ^{++} < λ.

3. f = ⟨f_{ξ} | ξ < λ⟩ is a sequence of length λ of functions in Ord^{A} that is <_{I}-increasing and satisfies the following requirement:

For every δ < λ with cf(δ) = κ^{++} there is a closed unbounded set E_{δ} ⊆ δ such that for some δ′ ≥ δ in λ

sup{f_{α} | α ∈ E_{δ}} <_{I} f_{δ′}.  (I.8)

Then (∗)_{κ} holds for f.

Proof. Let S = S_{κ}^{κ^{++}} be the stationary subset of κ^{++} consisting of all ordinals with cofinality κ. Fix a club-guessing sequence on S: ⟨C_{α} | α ∈ S⟩. So for every α ∈ S, C_{α} ⊆ α is closed unbounded, of order type κ, and for every closed unbounded set C ⊆ κ^{++} there is δ ∈ S such that C_{δ} ⊆ C.

Now let U ⊆ λ be an unbounded set, and we shall find X_{0} ⊆ U of order type κ such that ⟨f_{ξ} | ξ ∈ X_{0}⟩ is strongly increasing. For this we first define an increasing and continuous sequence ⟨ξ(i) | i < κ^{++}⟩ ⊂ λ of order-type κ^{++} by the following inductive procedure.

We start with an arbitrary ξ(0). For i limit, ξ(i) = sup{ξ(k) | k < i}. Suppose for some i < κ^{++} that {ξ(k) | k ≤ i} have been defined. For every α ∈ S define

h_{α} = sup{f_{ξ(k)} | k ≤ i ∧ k ∈ C_{α}}.  (I.9)

Then ask: is there an ordinal σ > ξ(i) below λ such that h_{α} <_{I} f_{σ}? If the answer is positive, let σ_{α} be the least such σ < λ, and, if negative, let σ_{α} be ξ(i) + 1.

Since λ > κ^{++} is regular, we can define

ξ(i + 1) > sup{σ_{α} | α ∈ S} with ξ(i + 1) ∈ U.

It follows, in case the answer for h_{α} is positive, that

h_{α} <_{I} f_{ξ(i+1)}.

Finally D = {ξ(k) | k ∈ κ^{++}} is closed and has order type κ^{++}. Let δ = sup D. Then D is closed unbounded in δ < λ, and cf(δ) = κ^{++}. By assumption there is a closed unbounded set E_{δ} ⊆ δ such that (I.8) holds. Thus for some f_{δ′}

sup{f_{ξ} | ξ ∈ E_{δ}} <_{I} f_{δ′}.  (I.10)

Observe that D ∩ E_{δ} is closed unbounded in δ, and thus C = {i ∈ κ^{++} | ξ(i) ∈ E_{δ}} is closed unbounded. Hence for some α ∈ S, C_{α} ⊆ C. So (I.10) implies that

sup{f_{ξ(i)} | i ∈ C_{α}} <_{I} f_{δ′}.  (I.11)

Let N_{α} ⊆ C_{α} be the set of non-accumulation points of C_{α}, that is those i ∈ C_{α} for which C_{α} ∩i is bounded in i. We shall prove that {f_{ξ(i)} | i ∈ N_{α}} is strongly increasing. Since ξ(i + 1) ∈ U for every i, the sandwich lemma (2.7) gives a strongly increasing subsequence of {f_{α} | α ∈ U} of order-type κ.

Claim. For every i < j both in C_{α}

sup{f_{ξ(k)} | k ≤ i ∧ k ∈ C_{α}} <_{I} f_{ξ(j)}.  (I.12)

Proof of the claim. Recall how f_{ξ(i+1)} was defined. We considered (I.9) and asked if h_{α} is <_{I} dominated by some f_{σ}. The answer was positive, since f_{δ′} is such a bound. Hence the claim and the lemma follow. ⊣

2.20 Exercise. Let κ and λ be regular cardinals with κ^{++} < λ, and let F be any function with dom(F) ⊆ [λ]^{<κ} and such that F (X) ∈ λ for X ∈ dom(F). Suppose that for every δ ∈ S_{κ^{++}}^{λ} there exists a closed unbounded set E_{δ} ⊆ δ such that [E_{δ}]^{<κ} ⊆ dom(F). Then the following set S is stationary: the set of all ordinal α ∈ S_{κ}^{λ} for which there exists a closed unbounded set D ⊆ α with the property that, for any a < b both in D, F ({d ∈ D | d ≤ a}) < b.

A typical application of Lemma 2.19 is the following

2.21 Theorem. Suppose that I is a proper ideal over a set of regular cardinals A, and λ is a regular cardinal such that ΠA/I is λ-directed. If ⟨g_{ξ} | ξ < λ⟩ is any sequence in ΠA, then there exists a <_{I}-increasing sequence f = ⟨f_{ξ} | ξ < λ⟩ of length λ in ΠA/I, such that g_{ξ} < f_{ξ+1} for every ξ < λ and (∗)_{κ} holds for f for every regular cardinal κ such that κ^{++} < λ and {a ∈ A | a ≤ κ^{++}} ∈ I. Hence if κ = |A|^{+} is such a cardinal, then by Theorem 2.15 and the fact that (∗)_{κ} holds, we have an exact upper bound g to the sequence f so that {a ∈ A | cf g(a) < κ} ∈ I.

Proof. We shall define a <_{I}-increasing sequence ⟨f_{ξ} | ξ < λ⟩ in ΠA/I as follows. At successor stages, if f_{ξ} is defined, let f_{ξ+1} be any function in ΠA that <-extends f_{ξ} and g_{ξ}.

1. At limit stages δ < λ there are two cases. In the first cf(δ) = κ^{++} where κ is regular and {a ∈ A | a ≤ κ^{++}} ∈ I. Then fix some E_{δ} ⊆ δ closed unbounded and of order type cf(δ), and define

f_{δ} = sup{f_{i} | i ∈ E_{δ}}.

Then f_{δ}(a) < a when a > κ^{++}, and thus f_{δ} ∈ ΠA/I since {a ∈ A | a ≤ κ^{++}} ∈ I.

2. If δ < λ, but case 1 above does not hold, let f_{δ} ∈ ΠA be any ≤_{I} upper bound of ⟨f_{ξ} | ξ < δ⟩ guaranteed by the λ-directedness assumption.

Now Lemma 2.19 implies that (∗)_{κ} holds for every regular cardinal κ of the required form. ⊣

In the following, we shall apply Lemma 2.19 (or rather its consequence Theorem 2.21 above) and obtain an important representation of successors of singular cardinals with uncountable cofinality. But first we introduce a notation.

2.22 Notation. Let X be a set of cardinals, then

X^{(+)} = {α^{+} | α ∈ X}

denotes the set of successors of cardinals in X.

2.23 Theorem (Representation of μ^{+} as true cofinality). Suppose that μ is a singular cardinal with uncountable cofinality. Then there exists a closed unbounded set C ⊆ μ such that

μ^{+} = tcf(ΠC^{(+)}/J^{bd})

where J^{bd} is the ideal of bounded subsets of C^{(+)}.

Proof. Let C_{0} ⊆ μ be any closed unbounded set of limit cardinals such that |C_{0}| = cf(μ) and all cardinals in C_{0} are above cf(μ). Clearly all cardinals in C_{0} that are limit points of C_{0} are singular cardinals, and hence we can assume that C_{0} consists only of singular cardinals.

Observe that ΠC_{0}^{(+)}/J^{bd} is μ directed, and in fact is μ^{+} directed since μ is a singular cardinal. Indeed, suppose that F ⊆ ΠC_{0}^{(+)} has cardinality < μ and define h(a) by h(a) = sup{f(a) | f ∈ F } for every a ∈ C_{0}^{(+)} above |F | (so that h(a) ∈ a), and h(a) is arbitrarily defined on smaller a’s. This proves that every subset of ΠC_{0}^{(+)} of cardinality < μ is bounded in <_{J^{bd}}. But then it follows that subsets of ΠC_{0}^{(+)} of cardinality μ are also bounded: decompose any such subset F = ⋃_{α<cf(μ)} F_{α} where each F_{α} has cardinality < μ, then bound each F_{α}, and finally bound the sequence of bounds.

Thus ΠC_{0}^{(+)}/J^{bd} is μ^{+} directed and we may construct a J^{bd} increasing sequence f = ⟨f_{ξ} | ξ < μ^{+}⟩ in ΠC_{0}^{(+)} such that (∗)_{κ} holds for every regular cardinal κ < μ (apply Theorem 2.21 in its simpler form in which there is no need to extend a given sequence g).

Theorem 2.15 implies that f has an exact upper bound h : C_{0}^{(+)} → Ord such that

{a ∈ C_{0}^{(+)} | cf(h(a)) < κ} ∈ J^{bd}  (I.13)

for every regular κ < μ. We may assume that h(a) ≤ a for every a ∈ C_{0}^{(+)}, since the identity function is clearly an upper bound to f.

2.24 Claim. The set {α ∈ C_{0} | h(α^{+}) = α^{+}} contains a closed unbounded set.

Proof. Suppose toward a contradiction that for some stationary set S ⊆ C_{0}, h(α^{+}) < α^{+} for every α ∈ S. Since all cardinals of C_{0} are singular, cf(h(α^{+})) < α for every α ∈ S. Hence (by Fodor’s theorem) cf(h(α^{+})) is bounded by some κ < μ on a stationary subset of α in S. But this is in contradiction to (I.13) above.

Thus we have proved the existence of a closed unbounded set C ⊆ C_{0} such that h(α^{+}) = α^{+} for every α ∈ C. We claim that μ^{+} = tcf(ΠC^{(+)}/J^{bd}). But this is clear since h ↾ C^{(+)}, which is the identity function, is an exact upper bound to the sequence ⟨f_{ξ} ↾ C^{(+)} | ξ < μ^{+}⟩ which is J^{bd} increasing and of length μ^{+}. ⊣

A somewhat stronger form of this theorem is in Exercise 4.17.

2.25 Exercise. Prove the following representation theorem for μ^{+} in case cf(μ) = ℵ_{0}.

2.26 Theorem. If μ is a singular cardinal of countable cofinality then for some unbounded set D ⊆ μ (of order type ω) of regular cardinals

μ^{+} = tcf(ΠD/J^{bd})

where J^{bd} is the ideal of bounded subsets of D. For example, there exists a set B ⊆ {ℵ_{n} | n < ω} such that tcf ΠB/J^{bd} = ℵ_{ω+1}.

Hint. Let C_{0} be any ω sequence converging to μ, consisting of regular cardinals. Repeat the proof above and define D = {cf(h(a)) | a ∈ C_{0}}. Then use Lemma 2.3.

The theory of exact upper bounds, which is the basis of the pcf theory, can be developed in various ways. For example [10] presents Shelah’s Trichotomy theorem, and extends it to further analyze the set of flat points. Suitably interpreted, Theorem 2.15 is equivalent to Theorem 18 of [10]. The following exercise establishes the connection between the Trichotomy and the bounding projection property.

2.27 Exercise. (The Trichotomy theorem.) Suppose that λ > |A|^{+} is a regular cardinal, and f = ⟨f_{ξ} | ξ < λ⟩ is an <_{I} increasing sequence. Consider the following properties of f and a regular cardinal κ such that |A| < κ ≤ λ:

Bad_{κ} There are sets of ordinals S(a) for a ∈ A such that |S(a)| < κ and sup of S <_{I}-dominates f, and there is an ultrafilter D over A, extending the dual of I, such that for every α < λ f_{α}^{+} <_{D} f_{β} for some β < λ (where f_{α}^{+} = proj(f_{α}, S)).

Ugly There exists a function g ∈ Ord^{A} such that, forming t_{α} = {a ∈ A | g(a) < f_{α}(a)}, the sequence ⟨t_{α} | α < λ⟩ which we know to be ⊆_{I} increasing does not stabilize modulo I. That is, for every α there is some β > α in λ such that t_{β} \ t_{α} ∈ I^{+}.

Good_{κ} There exists an exact upper bound g to the sequence f such that cf(g(a)) ≥ κ for every a ∈ A.

Prove that the bounding projection property for κ is equivalent with ¬Bad_{κ} ∧ ¬Ugly. Hence the Trichotomy theorem which says that if neither Bad_{κ} nor Ugly, then Good_{κ}.

2.28 Exercise. (Lemma 0.D, Chapter V, [12]) If λ is a regular cardinal and ∀μ < λ μ^{|A|} < λ, if f_{α} ∈ Ord^{A} for α < λ, then for some unbounded E ⊆ λ, for all α < β both in E, f_{α} ≤ f_{β} and {a ∈ A | f_{α}(a) = f_{β}(a)} does not depend on α, β in E.

Hence, if I is an ideal over A and f_{α} <_{I} f_{β} for all α < β, then (∗)_{λ} holds.

Hint. For a ∈ A fix some γ_{a} > sup{f_{α}(a) | α ∈ λ}. For α < λ, a ∈ A, define s^{α}(a) = {f_{β}(a) | β < α} ∪ {γ_{a}}. Define g_{α} = proj(f_{α}, s^{α}). Let T = {δ < λ | cf(δ) = |A|^{+}}. For α ∈ T there exists μ_{α} < α such that g_{α} = proj(f_{α}, s^{μ_{α}}). By Fodor’s theorem we may assume μ = μ_{α} is fixed on a stationary set T′ ⊆ T. Moreover, since s^{μ} has cardinality |μ| and |μ|^{|A|} < λ, we may assume that g_{α} = g is fixed for α ∈ T′′ ⊆ T′, stationary.

2.2. Application: Silver’s Theorem

One form of Silver’s theorem says that if κ is a singular cardinal of uncountable cofinality such that 2^{δ} = δ^{+} for a stationary set of δ’s in κ, then 2^{κ} = κ^{+}. A slightly more general form is the following

2.29 Theorem. (Silver [16]) Let κ be a singular cardinal with uncountable cofinality: ℵ_{0} < cf(κ) < κ. Suppose that there exists a stationary set of cardinals S ⊆ κ such that, for every δ ∈ S, δ^{cf(κ)} = δ^{+}. Then

κ^{cf(κ)} = κ^{+}

as well.

Proof. Assume that S ⊆ κ, of order type cf(κ), is a stationary set of cardinals such that for every δ ∈ S

δ^{cf(κ)} = δ^{+}.

We have established the existence of a closed unbounded subset C ⊆ κ with κ^{+} = tcf(ΠC^{(+)}/J^{bd}). So, by taking S ∩ C for S, we may conclude that ΠS^{(+)}/J_{bd} has true cofinality κ^{+} and let f = ⟨f_{ξ} | ξ ∈ κ^{+}⟩ be J^{bd} increasing and cofinal there.

Since λ^{cf(λ)} = λ^{+} for all λ ∈ S, there exists an encoding of all pairs ⟨λ, X⟩ where X ∈ [λ]^{cf(κ)} by ordinals in λ^{+}. Hence we can encode each X ∈ [λ]^{cf(κ)} by a function h_{X} ∈ ΠS^{(+)}, where h_{X}(λ^{+}) gives the code of X ∩ λ. Thus, if X ≠ Y then h_{X} and h_{Y} are eventually disjoint. Since each h_{X} is J^{bd} dominated by some f_{ξ} for xi ∈ κ^{+}, the following lemma concludes the proof of our theorem.

2.30 Lemma. For every function g ∈ ΠS^{(+)}, the collection

F = {X ∈ [κ]^{cf(κ)} | h_{X} <_{J^{bd}} g}

has cardinality ≤ κ.

Proof. Suppose that, on the contrary, |F | ≥ κ^{+}. For each δ ∈ S fix an enumeration of g(δ^{+}) ∈ δ^{+} that has order-type ≤ δ. Using this enumeration, h_{X}(δ^{+}) is “viewed” as an ordinal in δ, denoted k_{X}(δ) whenever h_{X}(δ^{+}) < g(δ^{+}). Thus for every X ∈ F, h_{X} is translated into a pressing down function defined on a final segment of S.

By Fodor’s theorem, for some stationary set S_{X} ⊆ S, k_{X} is bounded on S_{X}, say by δ_{X} < κ. Now the number of subsets of S is bounded by 2^{cf(κ)} < κ, and hence there exists a subset F_{0} ⊆ F of cardinality κ^{+}, a fixed stationary set S_{0}, and a fixed cardinal δ_{0} ∈ S such that S_{X} = S_{0} and δ_{X} = δ_{0} for every X in F_{0}. Moreover the translation function taking δ ∈ S_{0} to that ordinal in δ_{0} that indirectly encodes X ∩ δ can also be assumed to be independent of X ∈ F_{0}, since there are at most δ_{0}^{cf(κ)} = δ_{0}^{+} such functions. Yet this is absurd because the translation function of h_{X} completely determines X = ⋃{X ∩ δ | δ ∈ S_{0}}. A contradiction which proves the lemma. ⊣

2.31 Exercise. Show that the following form of Silver’s theorem is equivalent to 2.29 (cf. [7]). Let κ be a singular cardinal with uncountable cofinality: ℵ_{0} < cf(κ) < κ. Suppose that λ^{cf(κ)} < κ for all λ < κ, and there exists a stationary set of cardinals S ⊆ κ such that, for every δ ∈ S, δ^{cf(δ)} = δ^{+}. Then

κ^{cf(κ)} = κ^{+}

as well.

2.32 Exercise.

The proof given by Baumgartner and Prikry (in [1]) to Silver’s theorem simplifies the original proof, and is actually simpler than the proof given here which serves to illustrate some of the pcf concepts. In addition the Baumgartner–Prikry proof relies on very elementary notions. The following exercise describes that proof. Assume that κ is a singular cardinal with uncountable cofinality.

1. If S ⊂ κ is a stationary set such that δ^{cf(κ)} = δ^{+} for δ ∈ S, define on ΠS^{(+)} a relation R by f R g iff {α ∈ S | f(α^{+}) < g(α^{+})} is stationary. Prove that for every g the cardinality of R^{−1}g = {X ∈ κ^{cf(κ)} | h_{X} R g} is ≤ κ.

2. Prove that for every f, g ∈ ΠS^{(+)} that are eventually different either f R g or g R f. Take any collection X_{i} ∈ [κ]^{cf(κ)}, i < κ^{+}, of different subsets and consider H = ⋃_{i∈κ^{+}} R^{−1}h_{X_{i}}. If κ^{cf(κ)} > κ^{+} there must be some g ∉ H, and hence h_{X_{i}} R g for every i < κ^{+}. This is a contradiction.

2.3. Application: a covering theorem

In this subsection V denotes the universe of all sets, and U a transitive subclass containing all ordinals and satisfying the axioms of ZFC. (See, for example, Levy ([11] for the meaning of statements concerning classes.) If X and Y are sets of ordinals in V and U (respectively) and X ⊆ Y, then we say that Y covers X.

The ℵ_{0} covering property of U (or between U and V) is the statement that any countable set of ordinals X is covered by some countable set of ordinals Y in U (that is, Y is in U, and Y is countable in V). Similarly, for any cardinal κ, the ≤ κ covering property is that any set of cardinals X of cardinality ≤ κ is covered by some set in U that has cardinality ≤ κ in V. If the ≤ κ covering property holds for every cardinal κ, then we say that the “full” covering property holds for U: every set of ordinals X is covered by some set Y in U such that X and Y are equinumerous in V. The following theorem gives conditions by which the full covering property can be deduced from the countable covering property.

2.33 Theorem. (Magidor) Suppose U is a transitive class containing all ordinals and satisfying all ZFC axioms. Moreover, assume that

1. the GCH holds in U,

2. U and the universe V have the same cardinals, and moreover every regular cardinal in U remains regular in V.

Then the countable covering property for U implies the full covering property.

Proof. Observe first that if U and V have the same regular cardinals, they have the same cardinals and cf^{U}(κ) = cf^{V} (κ) for every ordinal. Also, for every set X ∈ U, |X|^{U} = |X|^{V}. We prove by induction on λ ∈ Ord that every X ⊆ λ is covered by some Y in U of the same V cardinality. Of course if X is bounded in λ then the inductive assumption applies, and hence we can consider only sets that are unbounded in λ.

If λ is not a cardinal, let |λ| be its cardinality. So |λ| < λ < λ^{+} in U as well since V and U have the same cardinals. Since λ and |λ| are equinumerous in U, the inductive assumption for |λ| implies that any subset of λ can be covered by a set in U of the same cardinality.

So we assume that λ is a cardinal. If it is a regular cardinal, then any unbounded X ⊆ λ is covered by λ itself. Hence we are left with the case that λ is a singular cardinal, in V and hence in U since both universe have the same regular/singular predicate. Again, if X ⊆ λ has cardinality λ then λ itself is a covering as required, and hence we may assume that |X| < λ.

Assume first that cf(λ) = ω. Then cf^{U}(λ) = ω as well. Suppose that an unbounded set X ⊆ λ of cardinality < λ is given. Take in U an increasing cofinal in λ sequence ⟨λ_{i} | i ∈ ω⟩. Since 2^{<λ} = λ is assumed in U, there exists in U an enumeration of all bounded subsets of λ of cardinality ≤ |X|. Now consider the sequence X ∩ λ_{i}, i ∈ ω (where X is the set to be covered) and cover first each X ∩λ_{i} by some Y_{i} ∈ U with |Y_{i}| = |X ∩λ_{i}|. Then define α_{i} ∈ λ to be the ordinal that encodes Y_{i} in U, and form the countable set A = {α_{i} | i ∈ ω} of ordinals that encode X. This countable set A can be covered by some countable set A′ in U, and we can define in U a cover

Y = ⋃{E ⊆ λ_{i} | E is encoded by some ordinal in A′ and |E| ≤ |X|}.

Clearly X ⊆ Y and |Y | = |X|.

Finally suppose that λ is a singular cardinal with uncountable cofinality, and it is here that the theory developed so far is employed. Since V and U have the same regular cardinals cf^{U}(λ) = cf(λ).

We work for a while in U and apply the Representation Theorem 2.23 to λ. In fact, we must analyze the proof and use the construction rather than the theorem. Recall that we took an arbitrary closed unbounded set C_{0} ⊆ λ consisting of singular cardinals, and such that |C_{0}| = cf(λ) < min C_{0}. Then we constructed a J^{bd} increasing sequence f = ⟨f_{ξ} | ξ < λ^{+}⟩ in ΠC_{0}^{(+)} such that for all limit ordinals δ < λ^{+} a closed unbounded set E_{δ} ⊆ δ was chosen with |E_{δ}| = cf(δ) < λ and then

f_{δ} =_{J^{bd}} sup{f_{i} | i ∈ E_{δ}}

was defined. All of this is done in U, but now we pass to V and deduce that (∗)_{κ} holds for every regular κ < λ (by Lemma 2.19). Hence f has an exact upper bound h such that {a ∈ C_{0}^{(+)} | cf(h(a)) < κ} ∈ J^{bd} for every κ < λ. Now the argument of Claim 2.24 applies, and there exists (in V) a closed unbounded set C ⊆ C_{0} such that {f_{ξ} ↾ C^{(+)} | ξ < λ^{+}} is cofinal in ΠC^{(+)}/J^{bd}.

We continue now the proof that any set X ⊆ λ of cardinality λ_{0} < λ can be covered in U by a set of the same cardinality. Since X is unbounded in λ, assume that λ_{0} ≥ cf(λ). For every α ∈ C_{0} cover X ∩ α by some Y_{α} ∈ U (a subset of α) of cardinality ≤ λ_{0}. We assume in U an enumeration of length α^{+} of all subsets of α of size ≤ λ_{0}. There is an index < α^{+} that encodes Y_{α} in U. The function d taking α^{+} ∈ C_{0}^{(+)} to that coding ordinal is defined in V and is bounded by some f_{ξ} ∈ U. Namely d ↾ C^{(+)} <_{J^{bd}} f_{ξ} ↾ C^{(+)}. In U, choose for every α ∈ C_{0} a function g_{α} : f_{ξ}(α^{+}) → α that is one-to-one. Then in V look at the values g_{α}(d(α^{+})) < α, and find a stationary set S ⊆ C on which these values are bounded, say by κ. The set {g_{α}(d(α)) | α ∈ S} ⊆ κ can be covered by some set Y in U that has the same cardinality (namely cf(λ)). Now look in U at the set ⋃_{α∈C_{0}} g_{α}^{−1}Y. Every index in g_{α}^{−1}Y represents a subset of α of cardinality ≤ λ_{0}, and hence this union which covers X has cardinality λ_{0}.

2.34 Exercise. There is actually no need to start with countable covering in order to deduce covering for all higher cardinals. The following generalization is left as an exercise.

2.35 Theorem. As in Theorem 2.33 assume that V and U ⊆ V have the same regular cardinals, and the GCH holds in U. Let λ_{0} be any cardinal such that every countable set of ordinals is covered by some set in U of cardinality ≤ λ_{0}. Then any set of ordinals X is covered by some set in U of cardinality |X| + λ_{0}.

3. Basic properties of the pcf function

For any set A of regular uncountable cardinals define

pcf(A) = {λ | for some ultrafilter U over A, λ = cf (ΠA/U)}.

Some easily verifiable properties:

1. If λ = tcf(ΠA/F) for some filter F over A, then λ ∈ pcf(A). (For any ultrafilter U that extends F λ = tcf(ΠA/U).)

2. A ⊆ pcf(A). Since for every a ∈ A we can take the principal ultrafilter over A concentrating on {a}.

3. A ⊆ B implies pcf(A) ⊆ pcf(B). Because every ultrafilter D over A can be extended to D′ over B, and the ultraproducts ΠA/D and ΠB/D′ are the same.

4. For any sets A and B, pcf(A ∪ B) = pcf(A) ∪ pcf(B). Indeed, if λ ∈ pcf(A ∪ B), and D is an ultrafilter over A ∪ B with ultraproduct of cofinality λ, then either A ∈ D or B ∈ D (or both) and hence λ ∈ pcf(A) or λ ∈ pcf(B). For the other direction use the previous item.

We say that A is an interval of regular cardinals if for some cardinals α < β, A is the set of all regular cardinals κ such that α ≤ κ < β. This term is slightly misleading because one may misinterpret it as saying that all cardinals between α and β are regular.

3.1 Theorem (The “no holes” argument). Assume that A is an interval of regular cardinals satisfying |A| < min A, and λ is a regular cardinal with sup A < λ. Let I be a proper ideal over A such that ΠA/I is λ directed. Then λ ∈ pcf(A).

Proof. We may assume that every proper initial segment of A is in I (or else substitute for A its first initial segment that is not in I.) It now follows that A is infinite and unbounded (without a maximum).

Theorem 2.21 gives an <_{I}-increasing sequence f = ⟨f_{ξ} | ξ ∈ λ⟩ in ΠA/I that satisfies (∗)_{κ} for every regular cardinal κ in A (and thus for smaller cardinals of course). In particular (∗)_{|A|^{+}} holds, and f has an exact upper bound h ∈ Ord^{A} such that

{a ∈ A | cf(h(a)) < κ} ∈ I  (I.14)

for every κ ∈ A (this by Theorem 2.15). Since the identity function id : A → A taking a to a is clearly an upper bound of f, h(a) ≤ a for I-almost all a ∈ A. Yet (I.14) implies that

{a ∈ A | cf(h(a)) < min A} ∈ I,

and hence we have min(A) ≤ cf(h(a)) ≤ a for I-almost all a ∈ A. Changing h on a null set, we may assume for simplicity that this holds for every a ∈ A, namely that

cf(h(a)) ∈ A for all a ∈ A

(as A is an interval of regular cardinals). Since the sequence f has length λ, Πh/I has true cofinality λ. Consequently Π_{a∈A}cf(h(a))/I has true cofinality λ as well. Since |A| < min A, Lemma 2.3 gives a proper ideal J on B = {cf(h(a)) | a ∈ A} ⊆ A, such that ΠB/J has true cofinality λ as well. So λ ∈ pcf(A). We note in addition that J is the Rudin–Keisler projection obtained via cf ∘ h, and hence (I.14) implies for every κ < sup(A) that B ∩ κ ∈ J. ⊣

Upon examination of the proof, the reader will notice that the following slightly stronger formulation of the theorem can be obtained. In this formulation the requirement that A is an interval is relaxed.

3.2 Theorem. Assume that A is a set of regular cardinals such that |A| < min A, and λ is a regular cardinal such that sup A < λ. Suppose that I is a proper ideal over A containing all proper initial segments of A and such that ΠA/I is λ-directed. Then λ ∈ pcf(A′) for some set A′ of regular cardinals such that 1. A′ ⊆ [min(A), sup(A)), and A′ is cofinal in sup(A).

2. |A′| ≤ |A|.

In fact, λ is the true cofinality of ΠA′/J for an ideal J over A′ that contains all bounded subsets of A′.

Proof. Follow the previous proof and let A′ be the set {cf(h(a)) | a ∈ A}. ⊣

3.3 Notation. The property |A| < min A assumed for the set of regular cardinals appearing in the theorem is so pervasive in the pcf theory that it ought to be given a name. Following [6] we say that a set of regular cardinals A is progressive if |A| < min A.

3.1. The ideal J_{<λ}

Let A be a set of regular cardinals. For any cardinal λ define

J_{<λ}[A] = {X ⊆ A | pcf(X) ⊆ λ}.

In plain words, X ∈ J_{<λ}[A] iff for every ultrafilter D over A such that X ∈ D, cf(ΠA/D) < λ. That is, X “forces” the cofinalities of its ultraproducts to be below λ.

Clearly J_{<λ}[A] is an ideal over A, but it is not necessarily a proper ideal since A ∈ J_{<λ}[A] is possible. However, if λ ∈ pcf(A), then J_{<λ}[A] is proper (A ∉ J_{<λ}[A], or else pcf(A) ⊆ λ shows that λ ∉ pcf(A)). When the identity of A is obvious from the context, we write J_{<λ} instead of J_{<λ}[A]. Remark that if A ⊆ B then J_{<λ}[A] = J_{<λ}[B] ∩ P(A).

Let J_{<λ}^{∗}[A] be the dual filter over A. Then

J_{<λ}^{∗}[A] = ⋂{D | D is an ulterafilter and cf(ΠA/D) ≥ λ}.

3.4 Theorem (λ-Directedness). Assume that A is a progressive set of regular cardinals. Then, for every cardinal λ, ΠA/J_{<λ}[A] is λ-directed: any set of less than λ functions is bounded in ΠA/J_{<λ}[A].

Proof. The theorem holds trivially if A ∈ J_{<λ}[A], since |ΠA/J_{<λ}| = 1 in this case. So we assume that J_{<λ} is a proper ideal over A. Let κ_{0} = min A be the first cardinal of A, and κ_{1}, κ_{2} be the second, third etc. cardinals of A. The case λ ≤ κ_{n} for n finite is quite obvious: if λ = κ_{n} then J_{<λ} = P({κ_{0}, …, κ_{n−1}}) and for every family F ⊆ ΠA of cardinality < λ, sup F ∈ ΠA, because (sup F)(a) = ⋃{f(a) | f ∈ F } < a, since |F | < λ ≤ a for every a ∉ {κ_{0}, …, κ_{n−1}}). So we can certainly assume that λ > κ_{n} for all n ∈ ω, and hence that {κ_{n}} ∈ J_{<λ}.

Since any null subset of A can be removed without changing the structure of ΠA/J_{<λ}, we may assume that |A|^{+}, |A|^{++}, |A|^{+3} ∉ A. That is we can assume that

|A|^{+3} < min A < λ.

We shall prove by induction on λ_{0} < λ that ΠA/J_{<λ} is λ_{0}^{+}-directed: for every F = {f_{i} | i ∈ λ_{0}} ⊆ ΠA a family of functions of cardinality λ_{0}, F has an upper bound in ΠA/J_{<λ}. The case λ_{0} < min(A) is obvious as we saw.

So let F = {f_{i} | i ∈ λ_{0}} ⊆ ΠA be a subset of ΠA where λ_{0} < λ and assume that ΠA/J_{<λ} is λ_{0}-directed. Our aim is to bound F in ΠA/J_{<λ}.

In case λ_{0} is singular, we take ⟨α_{i} | i < cf(λ_{0})⟩ increasing and cofinal in λ_{0}, and obtain g_{i} ∈ ΠA for every i < cf(λ_{0}) that bounds {f_{ξ} | ξ < α_{i}}. Then we apply the inductive assumption again to the sequence {g_{i} | i < cf(λ_{0})}, and obtain a bound to F.

Thus λ_{0} is assumed to be a regular cardinal above |A|^{+3}. We shall replace F by a J_{<λ} increasing sequence that satisfies (∗)_{κ} for κ = |A|^{+}. That is, using Theorem 2.21 we define a J_{<λ}-increasing sequence ⟨f′_{ξ} | ξ < λ_{0}⟩ satisfying (∗)_{κ} and such that f_{i} ≤ f′_{i}.

Hence we can assume that the sequence f = ⟨f_{i} | i < λ_{0}⟩ that we want to dominate satisfies (∗)_{|A|^{+}} and thus has an exact upper bound g ∈ Ord^{A} in <_{J_{<λ}[A]} (by Theorem 2.15).

Since the identity function taking a ∈ A to a is an upper bound of our sequence f, we may assume that g(a) ≤ a for all a ∈ A (by possibly changing g on a null set). We intend to prove that B = {a ∈ A | g(a) = a} ∈ J_{<λ}[A], and thus that g =_{J_{<λ}} g′ for some g′ ∈ ΠA which will show that g bounds f in ΠA/J_{<λ}[A].

Assume toward a contradiction that B ∉ J_{<λ}[A]. Then (by definition of J_{<λ}) there is an ultrafilter D over A such that B ∈ D and cf(ΠA/D) ≥ λ. Clearly D ∩ J_{<λ} = ∅, or else cf(ΠA/D) < λ. The sequence f of length λ_{0} < λ is necessarily bounded in ΠA/D and we let h ∈ ΠA/D be such a bound. So h(a) < g(a) for every a ∈ B (since g(a) = a for a ∈ B). Hence (by definition of an exact upper bound) there is some f_{i} in f such that h ↾ B <_{J_{<λ}[A]} f_{i} ↾ B. But this would imply h <_{D} f_{i}, which contradicts the definition of h as an upper bound. ⊣

3.5 Corollary. Suppose that A is a progressive set of regular cardinals. For every ultrafilter D over A

cf(ΠA/D) < λ iff J_{<λ}[A] ∩ D ≠ ∅.

Hence cf(ΠA/D) = λ iff J_{<λ^{+}} ∩ D ≠ ∅ and J_{<λ} ∩ D = ∅. Namely, cf(ΠA/D) = λ iff λ^{+} is the first cardinal μ such that J_{<μ} ∩ D ≠ ∅.

Proof. If J_{<λ}[A]∩D ≠ ∅ and X ∈ J_{<λ}[A]∩D, then by definition of X ∈ J_{<λ}

cf(ΠA/D) < λ.

On the other hand, if J_{<λ} ∩ D = ∅, then the above theorem stating that ΠA/J_{<λ} is λ-directed gives that ΠA/D is λ-directed as well. Thus cf(ΠA/D) < λ is impossible in this case. The additional conclusion of the corollary is easily derived. ⊣

This corollary allows us to investigate the relationship between J_{<λ}[A] and J_{<λ^{+}}[A]. By definition X ∈ J_{<λ^{+}}[A] iff X ⊆ A and for every ultrafilter D over A containing X, cf(ΠA/D) ≤ λ. For this reason, J_{<λ^{+}}[A] is also denoted J_{≤λ}[A].

If λ ∉ pcf(A), for example when λ is singular, then J_{<λ} = J_{≤λ}. However, if λ ∈ pcf(A) then J_{<λ}⊂J_{≤λ} (where ⊂ is the strict inclusion relation). Indeed, if D is an ultrafilter over A such that cf(ΠA/D) = λ, then by Corollary 3.5 applied to λ^{+}, J_{≤λ} ∩ D ≠ ∅, and certainly J_{<λ} ∩ D = ∅. This argument shows that there is a one-to-one mapping from pcf(A) into P(A). Namely choosing X_{λ} ∈ J_{≤λ} \ J_{<λ} for every λ ∈ pcf(A). Thus we have the following theorem which is not evident from the definition of pcf.

3.6 Theorem. If A is a progressive set of regular cardinals, then

|pcf(A)| ≤ |P(A)|

Another consequence of Theorem 3.4 is that max pcf A exists.

3.7 Corollary (Max Pcf). If A is a progressive set of regular cardinals, then the set pcf(A) contains a maximal cardinal.

Proof. Observe that if λ_{1} < λ_{2} are cardinals, then J_{<λ_{1}}[A] ⊆ J_{<λ_{2}}[A]. Define

I = ⋃{J_{<λ}[A] | λ ∈ pcf(A)}.

For every λ ∈ pcf(A) J_{<λ}[A] is a proper ideal on A, and hence I (being the union of a chain of proper ideals) is also a proper ideal.

Since I is a proper ideal it can be extended to a maximal proper ideal, and we let E be any ultrafilter over A and disjoint to I. Let μ = cf(ΠA/E). Since E is disjoint to I, it is disjoint to every J_{<λ}[A] for λ ∈ pcf(A), and hence cf(ΠA/E) ≥ λ by the previous corollary. That is μ = cf(ΠA/E) = max(pcf A). As an important consequence we note that μ = sup pcf(A) = max pcf(A) is a regular cardinal (since it is in pcf A). ⊣

3.8 Exercise. If λ is a limit cardinal then

J_{<λ}[A] = ⋃_{θ<λ} J_{<θ}[A].

Another way of writing this statement is that for every cardinal λ (not necessarily limit)

J_{<λ}[A] = ⋃_{θ<λ} J_{<θ^{+}}[A] = ⋃_{θ<λ} J_{≤θ}[A].

The no holes argument has the following consequence.

3.9 Theorem. Suppose that A is a progressive interval of regular cardinals. Then pcf(A) is again an interval of regular cardinals.

Proof. We may assume that A is infinite, as the finite case is clear. We may also assume that A has no last cardinal (and deduce the general theorem in a short argument). Let λ_{0} = max pcf(A). We must show that every regular cardinal in the interval [min(A), λ_{0}] is in pcf(A). Say μ = sup A. Since μ ∉ A (A has no maximum), μ is a singular cardinal (because A is progressive). Since A ⊆ pcf(A) and A is an interval of regular cardinals, the substantial part of the proof is in showing that any regular cardinal in (μ, λ_{0}] is in pcf(A). But if λ is a regular cardinal and μ < λ ≤ λ_{0}, then J_{<λ} is a proper ideal (since λ ≤ max pcf(A)). By Theorem 3.4, ΠA/J_{<λ} is λ-directed. Hence Theorem 3.1 applies, and λ ∈ pcf(A). ⊣

We can get some information even when A is not progressive.

3.10 Definition. Suppose that A is a set of regular cardinals and κ < min(A) is a cardinal. We define

pcf_{κ}(A) = ⋃{pcf(X) | X ⊆ A and |X| = κ}.

That is, pcf_{κ}(A) is the collection of all cofinalities of ultraproducts of A over ultrafilters that concentrate on subsets of A of power κ (or less).

Similarly to the previous theorem stating that pcf(A) of a progressive interval A is again an interval of regular cardinals, we have the following.

3.11 Theorem. If A is an interval of regular cardinals, and κ < min A. Then pcf_{κ}(A) is an interval of regular cardinals.

Proof. Define λ_{0} = sup pcf_{κ}(A), and let λ be a regular cardinal such that min(A) < λ < λ_{0}. Then for some X ⊆ A and such that |X| = κ, λ ≤ max pcf(X). Hence J_{<λ}[X] is proper, and we may assume that every initial segment of X is in J_{<λ}. As X is progressive, ΠX/J_{<λ} is λ-directed, Theorem 3.2 can be applied, and it yields that λ ∈ pcf(X′) for some X′ ⊆ A of cardinality ≤ |X|. Thus λ ∈ pcf_{κ}(A). ⊣

Yet another consequence of the λ-directedness of ΠA/J_{<λ} is the following

3.12 Theorem. Suppose that A is a progressive set of regular cardinals and B ⊆ pcf(A) is also progressive, then

pcf(B) ⊆ pcf(A).

Hence if pcf(A) is progressive, then pcf pcf(A) = pcf(A).

Proof. Suppose that μ ∈ pcf(B), and let E be an ultrafilter over B such that

μ = cf(Π_{b∈B} b/E).  (I.15)

For every b ∈ B fix an ultrafilter D_{b} over A such that

b = cf(ΠA/D_{b}).

Define an ultrafilter D over A by

X ∈ D iff {b ∈ B | X ∈ D_{b}} ∈ E.  (I.16)

We shall prove that μ = cf(ΠA/D), and hence that μ ∈ pcf(A).

Consider (I.15). If, for every b ∈ B, (b′, <_{b′}) is an ordering that has true cofinality b, then μ = cf(Π_{b∈B} b′/E) as well. Hence

μ = cf(Π_{b∈B}(ΠA/D_{b})/E).  (I.17)

It remains to implement this iterated ultraproduct as an ultraproduct of A over D. For this aim consider the Cartesian product B × A and the ultrafilter P defined on B × A by

H ∈ P iff {b ∈ B | {a ∈ A | ⟨b, a⟩ ∈ H} ∈ D_{b}} ∈ E.

For any pair ⟨b, a⟩ let r(⟨b, a⟩) = a be its right projection. The reader should prove the following isomorphism

3.13 Claim. Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩)/P ≅ Π_{b∈B}(ΠA/D_{b})/E.

Thus μ (an arbitrary cardinal in pcf(B)) is the cofinality of the ultraproduct Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩)/P. But the projection map r : B × A → A, shows that the ultrafilter D defined in (I.16) is the Rudin–Keisler projection of P, and we are almost in the situation of Lemma 2.3, which concludes that μ = cf(ΠA/D). However Lemma 2.3 cannot be used verbatim because |B × A| < min A is not assumed. All we know is that |B| < min B. Recall (Lemma 2.3) that we had a map from ΠA into Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩) carrying h ∈ ΠA to h̄ ∈ Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩) defined by

h̄(⟨b, a⟩) = h(a).

We have proved that this map induces an isomorphism denoted L of ΠA/D into Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩), but the problem is to prove that the image of L is cofinal there. Let λ = min B. We have assumed that |B| < λ, and we shall use the fact that the reduced product modulo J_{<λ}[A] is λ-directed as follows. Given any g ∈ Π_{⟨b,a⟩∈B×A} r(⟨b, a⟩) define for every b ∈ B the map g_{b} ∈ ΠA by

g_{b}(a) = g(b, a).

4. Generators for J_{<λ} 37

Then {g_{b} | b ∈ B} is bounded in ΠA/J_{<λ}[A] by some function h ∈ ΠA, and we thus have that g_{b} <_{J_{<λ}[A]} h for every b ∈ B. Hence

g_{b} <_{D_{b}} h

since J_{<λ} ∩ D_{b} = ∅ (because cf(ΠA/D_{b}) = b and λ ≤ b). So g <_{P} h̄ is concluded. ⊣

4. Generators for J_{<λ}

A very useful property of the J_{<λ} ideals is that for every cardinal λ ∈ pcf(A) there is a set B_{λ} ⊆ A such that

J_{<λ^{+}}[A] = J_{<λ}[A] + B_{λ}

which means that the ideal J_{<λ^{+}}[A] is generated by the sets in J_{<λ}[A] ∪ {B_{λ}}. That is, for every X ⊆ A, X ∈ J_{<λ^{+}} iff X \ B_{λ} ∈ J_{<λ}. So B_{λ} is a maximal set in J_{≤λ}[A] in the sense that if B_{λ} ⊆ C ∈ J_{≤λ} then C \B_{λ} ∈ J_{<λ}. The property that J_{≤λ}[A] is generated from J_{<λ}[A] by the addition of a single set is called normality.

Normality of λ ∈ pcf(A) is obtained by means of a universal sequence for λ, and these sequences are studied first.

4.1 Definition. Suppose that λ ∈ pcf(A). A sequence f = ⟨f_{ξ} | ξ < λ⟩ of functions in ΠA, increasing in <_{J_{<λ}}, is a universal sequence for λ if and only if, for every ultrafilter D over A such that λ = cf(ΠA/D), f is cofinal in ΠA/D.

4.2 Theorem (Universaly Cofinal Sequences). Suppose that A is a progressive set of regular cardinals. Then every λ ∈ pcf(A) has a universal sequence.

Proof. The proof is obvious in case λ = min A. (The functions f_{ξ} defined by f_{ξ}(a) = ξ will do.) Therefore we shall assume that |A|^{+} < min A < λ.

Suppose that there is no universal sequence for λ. This means that for every J_{<λ}-increasing sequence f = ⟨f_{ξ} | ξ < λ⟩ there is an ultrafilter D over A such that cf(ΠA/D) = λ but f is bounded in ΠA/D.

The proof is typical in that it makes |A|^{+} steps and obtains a contradiction from the continuous failure at every step.

So for each α < |A|^{+} we shall define a J_{<λ} increasing sequence f^{α} = ⟨f_{ξ}^{α} | ξ < λ⟩ in ΠA, and assume that no f^{α} is universal. The definition is by induction on α < |A|^{+} and the fact that ΠA/J_{<λ} is λ directed is used in this construction.

If we visualize the functions f_{ξ}^{α} as lying on a matrix ⟨ξ, α⟩ ∈ λ × |A|^{+}, then in each column α the functions f_{ξ}^{α} are <_{J_{<λ}} increasing with ξ, and in each row ξ the functions f_{ξ}^{α} are ≤ increasing with α.

To begin with f^{0} = ⟨f_{ξ}^{0} | ξ < λ⟩ is an arbitrary <_{J_{<λ}}-increasing sequence in ΠA/J_{<λ} of length λ.

At limit stages δ < |A|^{+} we define f^{δ} = ⟨f_{ξ}^{δ} | ξ < λ⟩ by induction on ξ < λ so that for every ξ < λ

1. f_{i}^{δ} <_{J_{<λ}} f_{ξ}^{δ} for i < ξ.

2. sup{f_{ξ}^{α} | α < δ} ≤ f_{ξ}^{δ}.

Suppose now that f^{α} is defined. Since it is not universal, there exists an ultrafilter D_{α} over A such that

1. cf(ΠA/D_{α}) = λ, and

2. the sequence f^{α} is bounded in <_{D_{α}}.

So we can choose f_{0}^{α+1} that bounds the sequence f^{α} in <_{D_{α}}. The sequence f_{i}^{α+1} for 0 < i < λ is defined inductively by requiring that

1. f^{α+1} is J_{<λ} increasing and cofinal in ΠA/D_{α}, and

2. f_{i}^{α+1} ≥ f_{i}^{α} (everywhere) for every i < λ.

To sum-up, we have constructed <_{J_{<λ}}-increasing sequences f^{α}, each of length λ, and ultrafilters D_{α} over A, for α < |A|^{+} so that:

1. for every i < λ, ⟨f_{i}^{α} | α < |A|^{+}⟩ is increasing in ≤ (i.e., for α_{1} < α_{2} < |A|^{+}, f_{i}^{α_{1}}(a) ≤ f_{i}^{α_{2}}(a) for every a).

2. f^{α} = ⟨f_{ξ}^{α} | ξ < λ⟩ is bounded in ΠA/D_{α} by f_{0}^{α+1}.

3. f^{α+1} is cofinal in ΠA/D_{α}.

Now let h = sup{f_{0}^{α} | α < |A|^{+}}. Then h ∈ ΠA, because |A|^{+} < min A. Find for every α < |A|^{+} an index i_{α} < λ such that h <_{D_{α}} f_{i_{α}}^{α+1}. This is possible since f^{α+1} is cofinal in ΠA/D_{α}. Now pick an ordinal i < λ such that i > i_{α} for every α < |A|^{+}. This is possible since λ > |A|^{+} is regular. So h <_{D_{α}} f_{i}^{α+1} for every α < |A|^{+}.

Define

A^{α} = ≤(h, f_{i}^{α}).

The sets A^{α} ⊆ A are increasing with α, that is A^{α} ⊆ A^{β} for α < β < |A|^{+} (since f_{i}^{α} ≤ f_{i}^{β}).

The contradiction is obtained when we show that A^{α} ⊂ A^{α+1} (strict inclusion) for every α < |A|^{+} (and contrast this with A^{α} ⊆ A). For this, observe the following two statements.

1. A^{α} ∉ D_{α}, because f_{i}^{α} <_{D_{α}} f_{0}^{α+1} ≤ h.

2. A^{α+1} ∈ D_{α}, because h <_{D_{α}} f_{i}^{α+1}.

⊣

If λ ∈ pcf(A) and D is an ultrafilter over A such that cf(ΠA/D) = λ, then A ∩ (λ + 1) ∈ D because otherwise {a ∈ A | a > λ} ∈ D and then cf(ΠA/D) > λ. Thus, if ⟨f_{ξ} | ξ ∈ λ⟩ is a universal sequence for λ, we may assume that f_{ξ}(a) = ξ for all a ∈ A \ λ.

4.3 Exercise. If λ = max pcf(A), then any universal sequence for λ is cofinal in ΠA/J_{<λ}

Universal sequences can be used to prove the following

4.4 Theorem. For every progressive set A of regular cardinals,

cf(ΠA, <) = max pcf(A).

Hence cf(ΠA, <) is a regular cardinal.

Proof. The partial ordering < in this theorem refers to the everywhere dominance relation on ΠA. The required equality is obtained by first proving ≥ and then ≤.

Suppose that λ = max pcf(A), and D is an ultrafilter over A such that λ = cf(ΠA/D). Then <_{D} extends < on ΠA. That is, for f, g ∈ ΠA, f < g implies f <_{D} g. This shows that any cofinal set in (ΠA, <) is also cofinal in (ΠA, <_{D}), and hence that cf(ΠA, <) ≥ cf(ΠA, <_{D}) = λ.

Now we must exhibit a cofinal subset of (ΠA, <) of cardinality λ in order to conclude the proof.

Fix for every μ ∈ pcf(A) a universal sequence f^{μ} = ⟨f_{i}^{μ} | i < μ⟩ for μ. Let F be the set of all functions of the form

sup{f_{i_{1}}^{μ_{1}}, f_{i_{2}}^{μ_{2}}, …, f_{i_{n}}^{μ_{n}}}

where μ_{1}, μ_{2}, …, μ_{n} is a finite sequence of cardinals in pcf(A) (with possible repetitions) and i_{k} < μ_{k} are arbitrary indices. (Recall the definition of sup{g_{1}, …, g_{n}}: at every a ∈ A it returns max{g_{1}(a), …, g_{n}(a)}). Clearly |F | = λ.

4.5 Claim. F is cofinal in (ΠA, <).

Proof of claim. Let g ∈ ΠA be any function there. Consider the following collection of subsets of A:

I = {>(f, g) | f ∈ F }.

(Recall that >(f, g) = {a ∈ A | f(a) > g(a)}.) This collection is closed under unions, that is

>(f_{1}, g) ∪ >(f_{2}, g) = >(sup{f_{1}, f_{2}}, g).

If A ∈ I, namely if > (f, g) = A for some f ∈ F, then evidently g < f as required. But otherwise we obtain a contradiction by extending I to a proper maximal ideal J, and considering μ = cf(ΠA/J). Then f^{μ}, the universal sequence for μ, is cofinal in ΠA/J, and at the same time it is ≤_{J} bounded by g since f ≤_{I} g for all f ∈ F. Yet this is obviously impossible, and thus the theorem is proved. ⊣

If f′ = ⟨f′_{ξ} | ξ < λ⟩ is universal sequence for λ, and if f = ⟨f_{ξ} | ξ < λ⟩ is another sequence in ΠA, <_{J_{<λ}}-increasing and dominating f′ (for all ξ′ < λ there is ξ < λ such that f′_{ξ′} ≤_{J_{<λ}} f_{ξ}) then clearly f is also universal for λ. Hence we can use Theorem 2.21 and deduce the following

4.6 Lemma. Suppose that A is a progressive set of regular cardinals, and λ ∈ pcf(A). Let μ be the least ordinal such that A ∩ μ ∉ J_{<λ}[A]. Then there is a universal sequence for λ that satisfies (∗)_{κ} with respect to J_{<λ}[A] for every regular cardinal κ such that κ < μ, and in particular for κ = |A|^{+}.

Proof. Observe first that μ ≤ λ + 1. (Let D be an ultrafilter over A such that λ = cf(ΠA/D). Then A ∩ (λ + 1) ∈ D, or else {a ∈ A | a > λ} ∈ D and then cf(ΠA/D) > λ. Thus λ ∈ pcf(A ∩ (λ + 1))). Observe also that μ = λ is impossible, since λ is regular and A ∩ λ is necessarily bounded in λ as |A| < min A ≤ λ. The case μ = λ + 1 is rather trivial: λ ∈ A and J_{<λ}[A] = P(A ∩ λ). In this case the functions defined by f_{ξ}(a) = ξ for all a ∈ A \ λ are as required (and (∗)_{λ} holds). So we assume that μ < λ and A ∩ μ is unbounded in μ.

Let ⟨fξ^{′} | ξ < λ⟩ be any universal sequence for λ. Theorem 2.21 can be applied to this sequence and to I = J_{<λ}. This gives a sequence f_{ξ} ∈ ΠA that dominates fξ^{′} and that satisfies (∗)_{κ} for every regular cardinal κ such that κ^{++} < λ and {a ∈ A | a ≤ κ^{++}} ∈ I. Thus (∗)_{κ} holds for every regular κ < μ. ⊣

We intend to prove next the existence of a generating set for J_{<λ^{+}}. For this we need first the following characterization of generators for J_{<λ^{+}}.

4.7 Lemma. If A is a progressive set of regular cardinals and B ⊆ A is any subset, then

J_{<λ^{+}}[A] = J_{<λ}[A] + B  (I.18)

if and only if

B ∈ J_{<λ^{+}}[A] and  (I.19)

If D is any ultrafilter over A with cf(ΠA/D) = λ then B ∈ D.

(I.20)

Proof. Assume first that (I.18) holds. Then (I.19) is obvious. We prove (I.20). If D is any ultrafilter over A with cf(ΠA/D) = λ, then D∩J_{<λ^{+}}[A] ≠ ∅, and if X ∈ D ∩ J_{<λ^{+}}[A] is any set in the intersection then (I.18) implies that X \ B ∈ J_{<λ}[A]. Since D ∩ J_{<λ} = ∅, B ∈ D follows.

Now assume that (I.19) and (I.20) hold, and we prove that J_{<λ^{+}}[A] = J_{<λ}[A] + B.

Since B ∈ J_{<λ^{+}}[A], J_{<λ^{+}}[A] ⊇ J_{<λ}[A] + B.

To prove J_{<λ^{+}}[A] ⊆ J_{<λ}[A] + B assume X ∈ J_{<λ^{+}}[A] and prove that X \B ∈ J_{<λ} as follows. Let D be any ultrafilter over A such that X \B ∈ D. Since X ∈ J_{<λ^{+}}, cf(ΠA/D) < λ^{+}. But cf(ΠA/D) = λ is impossible as B ∉ D and we assume (I.20). Hence cf(ΠA/D) < λ. ⊣

4.8 Theorem (Normality). If A is a progressive set of regular cardinals, then every cardinal λ ∈ pcf(A) is normal: there exists a set B_{λ} ⊆ A such that

J_{<λ^{+}}[A] = J_{<λ}[A] + B_{λ}.

Proof. By Lemma 4.6, there exists a universal sequence f = ⟨f_{ξ} | ξ < λ⟩ for λ that satisfies (∗)_{|A|^{+}}. Hence f has an exact upper bound h in Ord^{A}/J_{<λ}. Since the identity function is an upper bound of f, we can assume that h(a) ≤ a for every a ∈ A. Now define

B = {a ∈ A | h(a) = a}.

We are going to prove that B satisfies the two properties (I.19) and (I.20) which concludes the lemma and show that B is a generator for J_{<λ^{+}}. We first prove that B ∈ J_{<λ^{+}}[A]. If D is any ultrafilter over A containing B then

cf(ΠA/D) ≤ λ  (I.21)

is deduced in two steps. If D ∩ J_{<λ} ≠ ∅, then the strict inequality of (I.21) holds by definition of J_{<λ}. But if D ∩ J_{<λ} = ∅, then h remains the exact upper bound of the <_{D} increasing sequence f in <_{D} (just because D extends the dual filter of J_{<λ}). So cf(Πh/D) = λ. As h is =_{D} equivalent to the identity function over A, ΠA/D has cofinality λ.

To prove (I.20), suppose that D is an ultrafilter over A and cf(ΠA/D) = λ. IF B ∉ D then {a ∈ A | h(a) < a} ∈ D, and thus [h]_{D} (the =_{D}- equivalence class of h) is in ΠA/D. Yet D∩J_{<λ}[A] = ∅ (or else cf(ΠA/D) < λ), and this implies that f_{ξ} <_{D} h for every ξ < λ (because f_{ξ} <_{J_{<λ}} h). So that f is not cofinal in ΠA/D, in contradiction to f being a universal sequence for λ. ⊣

The generator set B_{λ} is not uniquely determined ,but if B_{1} and B_{2} are two generators (they both satisfy I.18), then the symmetric difference B_{1}△B_{2} is in J_{<λ}[A]. So generators are uniquely determined modulo J_{<λ}, and we can use a “generic” notation.

4.9 Notation. For a progressive set of regular cardinals A and for any cardinal λ ∈ pcf(A), B_{λ}[A] denotes a subset B ⊆ A such that (I.19) and (I.20) hold, or equivalently

J_{<λ^{+}}[A] = J_{<λ}[A] + B.  (I.22)

We also use the expression “B is a B_{λ}[A] set” if (I.22) holds for B. We often write B_{λ} instead of B_{λ}[A], when the identity of A is obvious.

The sequence ⟨B_{λ}[A] | λ ∈ pcf(A)⟩ is called a “generating sequence” for A, because the ideal J_{<λ} is generated by the collection {B_{λ_{0}} | λ_{0} < λ} (see Corollary 4.12). It is convenient to write B_{λ} = ∅ when λ ∉ pcf(A).

The following conclusion will be needed later on.

4.10 Lemma. Suppose that A is a progressive set of regular cardinals. If A_{0} ⊆ A and λ ∈ pcf(A_{0}), then B_{λ}[A_{0}] =_{J_{<λ}[A_{0}]} A_{0} ∩ B_{λ}[A]. (This justifies our inclination to write B_{λ} instead of B_{λ}[A_{0}].)

Proof. We prove (I.19) and (I.20) for A_{0} ∩ B_{λ}[A]. Clearly A_{0} ∩ B_{λ}[A] ∈ J_{≤λ}[A_{0}]. If D_{0} is any ultrafilter over A_{0} such that cf(ΠA_{0}/D_{0}) = λ, then A_{0} ∩ B_{λ}[A] ∈ D_{0} can be argued as followed. Assume A_{0} \ B_{λ}[A] ∈ D_{0}, and extend D_{0} to an ultrafilter over A, still denoted D_{0}. Then cf(ΠA/D_{0}) = λ and B_{λ}[A] ∉ D_{0} is in contradiction to (I.20). ⊣

For a progressive set A with λ = max pcf(A) and B a B_{λ}[A] set, we have by (I.20) that

A \ B_{λ} ∈ J_{<λ}  (I.23)

since A ∈ J_{<λ^{+}}[A]. Hence we can take B_{max(pcf(A))} = A.

We will conclude that the ideal J_{<λ}[A] is (finitely) generated by the sets {B_{μ}[A] | μ < λ} using the following “compactness” theorem, which says that any set X ∈ J_{<λ} is covered by a finite collection of B_{μ}’s for μ < λ.

4.11 Theorem. (Inductive Covering) Suppose that A is a progressive set of regular cardinals and ⟨B_{λ} | λ ∈ pcf(A)⟩ is a generating sequence for A, then for any X ⊆ A

X ⊆ B_{λ_{1}} ∪ B_{λ_{2}} … ∪ B_{λ_{n}}

for some finite set {λ_{1}, …, λ_{n}} ⊆ pcf(X).

Proof. This can be proved by induction on λ = max pcf(X), since X \B_{λ} ∈ J_{<λ} and so max pcf(X \ B_{λ}) < λ. ⊣

4.12 Corollary. If A is a progressive set of regular cardinals then for every cardinal λ, for every set X ⊆ A, X ∈ J_{<λ}[A] iff X is included in a finite union of sets from {B_{λ′} | λ′ < λ}.

Observe that λ ∉ pcf(A \ B_{λ}[A]). For let D_{0} be any ultrafilter over A_{0} = A \ B_{λ}[A]. Extend D_{0} to an ultrafilter D over A. Since ΠA_{0}/D_{0} is isomorphic to ΠA/D, it suffices to prove that cf(ΠA/D) ≠ λ. But since A_{0} is disjoint to B_{λ}[A], B_{λ}[A] ∉ D. So (I.20) implies this, and we have obtained the following result. A set B ∈ J_{<λ^{+}}[A] is a B_{λ} set if and only if λ ∉ pcf(A \ B).

If λ ∈ pcf(A) and f = ⟨f_{ξ} | ξ < λ⟩ is a universal sequence for λ, then the definition of B_{λ}[A] = {a ∈ A | h(a) = a}, where h is an exact upper bound of f, shows that ⟨f_{ξ} ↾ B_{λ} | ξ < λ⟩ is cofinal in ΠB_{λ}/J_{<λ}. This result is sufficiently interesting to be isolated as a theorem (and we give a somewhat different proof).

4.13 Theorem. If A is a progressive set of regular cardinals and λ ∈ pcf(A), then for some set B ⊆ A we have tcf(ΠB/J_{<λ}[B]) = λ. In fact, any universal sequence for λ is cofinal in ΠB_{λ}/J_{<λ} and thus shows that

tcf(ΠB_{λ}/J_{<λ}) = λ.  (I.24)

Proof. We know that there exists a universal sequence for λ and that there exists a generating set B_{λ}. We will prove that any universal sequence f = ⟨f_{ξ} | ξ < λ⟩ for λ is cofinal in ΠB_{λ}/J_{<λ}. That is, if h ∈ ΠB_{λ} is any function then

≤(f_{ξ} ↾ B_{λ}, h) ∈ J_{<λ} for some ξ < λ.

Otherwise the sets ≤(f_{ξ} ↾ B_{λ}, h) are positive and decreasing with ξ < λ (mod J_{<λ}). Hence there is a filter over B_{λ} containing them all and extending the dual filter of J_{<λ}[B_{λ}]. Extending this filter to an ultrafilter D over A, D∩J_{<λ}[A] = ∅ and the ultraproduct ΠA/D has cofinality λ (as B_{λ} ∈ D and D∩J_{<λ} = ∅). In this ultrapower h bounds all functions in f, in contradiction to the assumption that f is universally cofinal. Thus the restriction to B_{λ}[A] of any universal sequence for λ is cofinal in ΠB_{λ}/J_{<λ}. ⊣

In particular, (I.24) shows (again) that λ = max pcf(B_{λ}) whenever λ ∈ pcf(A). We have, more generally, the following characterization.

4.14 Lemma. The following are equivalent for every filter F over a progressive set of regular cardinals A and for every cardinal λ.

1. tcf(ΠA/F) = λ.

2. B_{λ} ∈ F, and F contains the dual filter of J_{<λ}[A].

3. cf(ΠA/D) = λ for every ultrafilter D that extends F.

In particular we get for every ultrafilter D that

cf(ΠA/D) = λ iff B_{λ} ∈ D and D ∩ J_{<λ} = ∅.  (I.25)

Equivalently,

cf(ΠA/D) = λ iff λ is the least cardinal such that B_{λ} ∈ D.  (I.26)

Proof. Fix a filter F and a cardinal λ. 1 ⟹ 3 is obvious. Assume 3 and we prove 2. Since cf(ΠA/D) = λ for every ultrafilter D that extends F, B_{λ} ∈ D for every such ultrafilter (by (I.20)). Hence B_{λ} ∈ F. It is clear that F contains the dual filter of J_{<λ}, or else an extension of F can be found that intersects J_{<λ} and thus has an ultraproduct with cofinality below λ.

Assume now 2, and then the fact already proved that tcf(ΠB_{λ}/J_{<λ}) = λ shows that tcf(ΠA/F) = λ (as ΠA/F and ΠB_{λ}/F are isomorphic, since B_{λ} ∈ F).

In particular, if D is an ultrafilter over A, then D ∩ J_{<λ} = ∅ iff the dual filter of J_{<λ} is contained in D. So that the equivalence of 1 and 2 of the lemma shows (I.25). ⊣

4.15 Exercise. 1. If D is an ultrafilter over a progressive set A, and λ is the least cardinal such that B_{λ} ∈ D, then λ = cf(ΠA/D).

2. If A is a progressive set of regular cardinals and E = pcf(A) is also progressive, then

pcf(B_{λ}[A]) =_{J_{<λ}[E]} B_{λ}[pcf(A)].

(Use Theorem 3.12.)

4.16 Exercise. If A is a progressive set of regular cardinals then for every cardinal λ, λ = max pcf(A) iff λ = tcf(ΠA/J_{<λ}) iff λ = cf(ΠA/J_{<λ}).

In Theorem 2.23 we have proved for μ, a singular cardinal with uncountable cofinality, that μ^{+} = tcf(ΠC^{(+)}/J^{bd}) for some closed unbounded set of cardinals C ⊂ μ. Since J_{<μ} = J_{<μ^{+}} ⊆ J^{bd}, an apparently stronger claim is obtained by asserting tcf(ΠC^{(+)}/J_{<μ}[C^{(+)}]) = μ^{+}.

4.17 Exercise (The Representation Theorem). If μ is a singular cardinal with uncountable cofinality, then for some closed unbounded set of cardinals C ⊆ μ, tcf(ΠC^{(+)}/J_{<μ}[C^{(+)}]) = μ^{+}. Thus μ^{+} = max pcf C^{(+)}.

Hint. Let C_{0} ⊆ μ be a closed unbounded set of limit cardinals such that μ^{+} = tcf(ΠC_{0}^{(+)}/J^{bd}). Then define C ⊆ C_{0} so that C^{(+)} = B_{μ^{+}}[C_{0}^{(+)}]. Prove that C_{0} \ C is bounded in μ. Then use Theorem 4.13.

4.18 Exercise. For any filter F over a progressive set A of regular cardinals, define

pcf_{F} (A) = {cf(ΠA/D) | D an ultrafilter over A that extends F }.

5. The cofinality of [μ]^{κ} 45

1. Prove that max pcf_{F} (A) exists.

Hint. Look at the minimal λ such that F ∩ J_{≤λ} ≠ ∅.

2. Deduce that cf(ΠA/F) = max pcf_{F} (A), so that the cofinality of this partial ordering is a regular cardinal.

3. If B ⊆ pcf_{F} (A) is progressive, then pcf(B) ⊆ pcf_{F} (A).

4. Suppose that A is a progressive interval of regular cardinals, and let F be the filter of co-bounded subsets of A (X ∈ F iff A\X is bounded in A). Then pcf_{F} (A) is an interval of regular cardinals.

5. The cofinality of [μ]^{κ}

Some of the most important applications of the pcf theory will be described in this section. For example that ℵ_{ω}^{ℵ_{0}} < ℵ_{(2^{ℵ_{0}} )^{+}}. For this result we investigate obedient universal sequences and their relationship with characteristic functions of elementary substructures. Some of the theorems about obedient sequences proved and used in this section will be applied in the following section to “elevated” sequences. These sequences are not obedient, but they share enough properties with the obedient sequences to enable uniform proofs. Hence our desire to deal here with these shared properties (I.32 and I.33) rather than with obedient sequences.

As usual, A is a progressive set of regular cardinals. Recall how B_{λ}[A] was obtained. First a universal sequence ⟨f_{ξ} | ξ < λ⟩ for λ was defined which satisfied (∗)_{|A|^{+}}, then an exact upper bound h was constructed, and finally the set B_{λ} = {a ∈ A | h(a) = a} was shown to generate J_{<λ^{+}}[A] over J_{<λ}[A]. Once this is done, we have greater flexibility in tuning-up B_{λ} by using elementary substructures, and we therefore say first a few words about these structures.

5.1. Elementary substructures

Elementary substructures are extensively used in the pcf theory and its applications, and in this section we study some basic properties of their characteristic functions.

Let Ψ be a “large enough” cardinal, and H_{Ψ} be the ∈-structure whose universe is the collection H_{Ψ} of all sets hereditarily of cardinality less than Ψ (which means having transitive closure of size < Ψ). The expression “large enough” depends on the context and means that Ψ is sufficiently large to include in H_{Ψ} all sets that were discussed so far. We also add to the structure H_{Ψ} a well-ordering <^{∗} of its universe. We shall seldom mention <^{∗} explicitly, but it allows us to assume that the objects we talk about are uniquely determined.

For the rest of this section κ denotes a regular cardinal such that |A| < κ < min(A).

5.1 Definition. An increasing and continuous chain of length λ of elementary substructures of H_{Ψ} is a sequence ⟨M_{i} | i < λ⟩ such that

1. Each M_{i} is an elementary substructure of H_{Ψ},

2. i_{1} < i_{2} < λ implies that M_{i_{1}} ⊂ M_{i_{2}}, and

3. for every limit ordinal δ < λ, M_{δ} = ⋃_{i<δ} M_{i} (this is continuity).

We say in this paper that an elementary substructure M ≺ H_{Ψ} is “κpresentable” if and only if M = ⋃_{i<κ} M_{i} where ⟨M_{i} | i < κ⟩ is an increasing and continuous chain of length κ such that

1. M has cardinality κ and κ + 1 ⊂ M.

2. For every i < κ, M_{i} ∈ M_{i+1}. (Thus M_{i} ∈ M_{j} for i < j.)

We do not make any assumption on the cardinality of M_{i} for i < κ, which may be κ or smaller than κ.

In order to define a κ-presentable elementary substructure define, inductively, the approaching structures M_{α}, and observe that each M_{α} (and even the sequence ⟨M_{α} | α ≤ β⟩) is an element of H_{Ψ} and thus can be incorporated in M_{β+1} ≺ H_{Ψ}.

We shall use the following observation. Let M̄_{α} denote the ordinal closure of M_{α} ∩ Ord. That is γ ∈ M̄_{α} iff γ ∈ M_{α} ∩ Ord or γ is a limit of ordinals in M_{α}. Since M_{α} ∈ M_{α+1} and M_{α} ⊂ M_{α+1}, M̄_{α} ∈ M_{α+1}, and M̄_{α} ⊆ M_{α+1}

For any structure N, we let Ch_{N} be the “characteristic function” of N. That is, the function defined on any regular cardinal μ such that ∥N∥ < μ by

Ch_{N}(μ) = sup N ∩ μ.

Then Ch_{N}(μ) ∈ μ since μ is regular and N is of smaller cardinality.

A very useful fact that we are going to prove is that if M is κ-presentable, then for every cardinals λ < μ, M ∩ μ can be reconstructed from M ∩ λ and the characteristic function of M restricted to the successor cardinals in the interval (λ, μ]. We shall use the following form of this fact.

5.2 Theorem. Suppose that M and N are elementary substructures of H_{Ψ}. Let κ < μ be any cardinals (κ is always regular uncountable).

1. If M ∩ κ ⊆ N ∩ κ, and, for every successor cardinal α^{+} ∈ M ∩ μ + 1,

sup M ∩ α^{+} = sup M ∩ N ∩ α^{+},  (I.27)

then M ∩ μ ⊆ N ∩ μ.

2. Therefore, if M and N are both κ-presentable and for every successor cardinal α^{+} ∈ μ + 1

sup M ∩ α^{+} = sup N ∩ α^{+},  (I.28)

then M ∩ μ = N ∩ μ.

Proof. This is a bootstrapping argument. We prove by induction on δ, a cardinal in the interval [κ, μ], that M ∩ δ ⊆ N ∩ δ. For δ = κ this is an assumption. If δ is a limit cardinal, then M ∩ δ ⊆ N ∩ δ is an immediate application of the inductive assumption that M ∩ δ′ ⊆ N ∩ δ′ for every cardinal δ′ in the interval [κ, δ). Assume now that M ∩ δ ⊆ N ∩ δ, and we shall argue for M ∩ δ^{+} ⊆ N ∩ δ^{+}. If δ^{+} ∉ M, then M contains no ordinals from the interval [δ, δ^{+}] and the claim is obvious. So assume that δ^{+} ∈ M. (And hence δ^{+} ∈ N since they have the same supremum below δ^{+}.) Let γ = sup(M ∩ δ^{+}) = sup(M ∩ N ∩ δ^{+}). Now if α ∈ M ∩ γ, then there exists some β ∈ M ∩ N ∩ γ such that α < β. Consider the structure (H_{Ψ}, ∈, <^{∗}) of which M and N are elementary substructures, and pick an injection f : β → δ that is minimal with respect to the well-ordering <^{∗} of H_{Ψ} Then f ∈ M ∩ N because f is definable from the parameter β. Since α ∈ M, f(α) ∈ M, and hence f(α) ∈ N. But then, applying f^{−1} in N, we get α ∈ N. Thus M ∩ β ⊆ N ∩ β.

For the second part of the theorem, let M = ⋃_{ξ<κ} M_{ξ} and N = ⋃_{ξ<κ} N_{ξ} be presentations for M and N. Observe that M ∩ κ = N ∩ κ = κ. Let α^{+} be any successor cardinal in the interval (κ, μ]. We assume that γ = Ch_{M}(α^{+}) = Ch_{N}(α^{+}). We claim that there is a subset of M ∩ N that is closed and unbounded in γ. Indeed, the approaching substructures M_{ξ} provide a closed unbounded sequence ⟨sup(M_{ξ} ∩ α^{+}) | ξ ∈ κ⟩ which is cofinal in γ. Likewise, N contains a closed unbounded sequence of ordertype κ cofinal in γ. The intersection of these closed unbounded sets is as required. Hence sup M ∩ α^{+} = sup N ∩ α^{+} = sup M ∩ N ∩ α^{+} holds and M ∩ μ = N ∩ μ is obtained by the first part of the theorem. ⊣

Recall that a sequence of functions in ΠA is universal for λ if it is J_{<λ} increasing and cofinal in ΠA/D whenever cf(ΠA/D = λ). Recall also (Equation I.3) that a sequence ⟨p_{ξ} | ξ < λ⟩ of members of a partial ordering (P, <_{P}) is persistently cofinal iff every member of P is dominated by all members of the sequence with a sufficiently large index.

5.3 Definition. We say that a sequence ⟨f_{ξ} | ξ < λ⟩ of functions in ΠA is persistently cofinal for λ if their restrictions to B_{λ} form a persistently cofinal sequence in ΠB_{λ}/J_{<λ}. Namely if for every h ∈ ΠA there exists ξ_{0} < λ such that

h ↾ B_{λ} <_{J_{<λ}} f_{ξ} ↾ B_{λ}

for all ξ_{0} ≤ ξ < λ (where B_{λ} = B_{λ}[A]).

For example, if ⟨f_{ξ} | ξ < λ⟩ is universal for λ then it is persistently cofinal (see Theorem 4.13), and if the functions F_{ξ} are such that f_{ξ} ≤_{J_{<λ}} F_{ξ} for all ξ < λ, then ⟨F_{ξ} | ξ < λ⟩ is also persistently cofinal, although it is not necessarily J_{<λ} increasing. Clearly, an arbitrary λ sequence in ΠA is universal for λ iff it is J_{<λ} increasing and persistently cofinal.

A basic observation which is used later to define the transitive generators is the following.

5.4 Lemma. Suppose that the progressive set A and the cardinal λ ∈ pcf(A) belong to an elementary substructure N ≺ H_{Ψ} so that N = ⋃_{α<κ} N_{α} where |A| < κ < min(A) is a regular cardinal, |N| = κ, κ + 1 ⊂ N, and ⟨N_{α} | α < κ⟩ is an increasing chain of elementary substructures of H_{Ψ}. If a sequence of functions f = ⟨f_{ξ} | ξ < λ⟩ ∈ N, with f_{ξ} ∈ ΠA, is persistently cofinal for λ, then for every ξ ≥ sup(N ∩ λ)

≤(Ch_{N}, f_{ξ}) = {a ∈ A | Ch_{N}(a) ≤ f_{ξ}(a)} is a B_{λ}[A] set.  (I.29)

Proof. Some preliminary notes are made first. Since κ < min A, we have that Ch_{N} ↾ A ∈ ΠA. Since A, λ ∈ N = ⋃_{α<κ} N_{α}, we may as well assume that A, λ, f ∈ N_{0} (or else re-enumerate the structures). Since |A| < κ and κ ⊂ N, A ⊂ N and we can assume that A ⊂ N_{0}. Since Ψ is large enough, all the pcf theory involved in defining B_{λ}[A] etc. can be done in H_{Ψ} and hence in N_{0}. We may assume again that a generating set B = B_{λ}[A] is in N_{0}. Suppose that ξ ≥ sup(N ∩ λ). To prove (I.29) we need two inclusions:

1. Ch_{N} ↾ B ≤_{J_{<λ}} f_{ξ} ↾ B, which shows that B ⊆_{J_{<λ}} ≤(Ch_{N}, f_{ξ}).

2. ≤(Ch_{N}, f_{ξ}) ∩ (A\B) ∈ J_{<λ}, which shows that ≤(Ch_{N}, f_{ξ}) ⊆_{J_{<λ}} B.

We prove 1. For every a ∈ A, if f_{ξ}(a) < Ch_{N}(a) then there exists an index α = α(a) < κ such that f_{ξ}(a) < Ch_{N_{α}}(a). Since |A| < κ there exists a single index α < κ such that, for every a ∈ A, f_{ξ}(a) < Ch_{N}(a) implies that f_{ξ}(a) < Ch_{N_{α}}(a). Hence for every a ∈ A

f_{ξ}(a) < Ch_{N}(a) iff f_{ξ}(a) < Ch_{N_{α}}(a).  (I.30)

But the sequence f is persistently cofinal in ΠB/J_{<λ}, and hence h ↾ B <_{J_{<λ}} f_{ξ} ↾ B for every h ∈ N ∩ ΠA, because ξ ≥ sup(N ∩ λ). In particular, for h = Ch_{N_{α}} ∈ N, we get

Ch_{N_{α}} ↾ B ≤_{J_{<λ}} f_{ξ} ↾ B (in fact <_{J_{<λ}}).

That is, {b ∈ B | f_{ξ}(b) < Ch_{N_{α}}(b)} ∈ J_{<λ}. Hence, by (I.30), {b ∈ B | f_{ξ}(b) < Ch_{N}(b)} ∈ J_{<λ}. Thus

Ch_{N} ↾ B ≤_{J_{<λ}} f_{ξ} ↾ B.

This proves 1.

Now we prove 2. That is

{a ∈ A \ B | Ch_{N}(a) ≤ f_{ξ}(a)} ∈ J_{<λ}.  (I.31)

As λ ∉ pcf(A \ B), J_{<λ}[A \ B] = J_{<λ^{+}}[A \ B] and hence Π(A \ B)/J_{<λ} is λ^{+}-directed, and f (with functions restricted to A\B) has an upper bound. Since f ∈ N, we have this upper bound in N. Let h ∈ N ∩ Π(A \ B) be an upper bound in <_{J_{<λ}} of the sequence f restricted to A \ B. Then

f_{ξ} ↾ (A \ B) <_{J_{<λ}} h < Ch_{N} ↾ (A \ B).

But this is exactly (I.31) ⊣

5.2. Minimally obedient sequences

Suppose that δ is some limit ordinal and f = ⟨f_{ξ} | ξ < δ⟩ is a sequence of functions f_{ξ} ∈ ΠA, where A is a set of regular cardinals and |A|^{+} ≤ cf(δ) < min(A) holds. For every closed unbounded set E ⊆ δ of order type cf(δ) let

h_{E} = sup{f_{ξ} | ξ ∈ E}.

That is, h_{E}(a) = sup{f_{ξ}(a) | ξ ∈ E}. Since cf(δ) < min(A), h_{E} ∈ ΠA. We say that h_{E} is the “supremum along E of the sequence f”. Observe that if E_{1} ⊆ E_{2} then h_{E_{1}} ≤ h_{E_{2}}. The following lemma says that among all functions obtained as suprema along closed unbounded subsets of δ there is a minimal one in the ≤ ordering.

5.5 Lemma. Let δ and f be as above (so |A| < cf(δ) < min(A) and f is a sequence of length δ of functions in ΠA). There is a closed unbounded set C ⊆ δ of order type cf(δ) such that

h_{C}(a) ≤ h_{E}(a)

for every a ∈ A and E ⊆ δ closed and unbounded (of order type cf(δ)).

Proof. Assume that there is no such closed unbounded set C ⊆ δ as required. We construct a decreasing sequence ⟨E_{α} | α < |A|^{+}⟩ of closed unbounded subsets of δ of order type cf(δ) each, such that for every α < |A|^{+}, h_{E_{α}} ≰ h_{E_{α+1}}. (Since |A| < cf(δ), at limit stages of the construction we may take the intersection of the clubs so far constructed.) Then find a single a ∈ A such that h_{E_{α}}(a) > h_{E_{α+1}}(a) for an unbounded set of indices α. Yet this is obviously impossible. ⊣

In applications of this lemma, an ideal J over A is assumed and the sequence ⟨f_{ξ} | ξ < δ⟩ is <_{J}-increasing. In that case, the minimal function f_{C} = sup{f_{ξ} | ξ ∈ C} ≤-bounds each f_{ξ}, for ξ ∈ C, and hence ≤_{J}-bounds all f_{ξ}’s for ξ < δ. This function f_{C} is called “minimal club-obedient bound of ⟨f_{ξ} | ξ < δ⟩”.

5.6 Definition (Minimally Obedient Universal Sequence). Suppose that λ is in pcf(A) and f = ⟨f_{ξ} | ξ < λ⟩ is a universal sequence for λ. Let κ be a fixed regular cardinal such that |A| < κ < min(A). We say that f is a “minimally obedient (at cofinality κ)” if for every δ < λ such that cf(δ) = κ, f_{δ} is the minimal club-obedient bound of ⟨f_{ξ} | ξ < δ⟩.

The universal sequence f is said to be “minimally obedient” if |A|^{+} < min(A) and it is minimally obedient for every regular κ such that |A| < κ < min(A).

Suppose that |A|^{+} < min(A) and λ ∈ pcf(A). In order to arrange a minimally obedient universal sequence for λ start with an arbitrary universal sequence ⟨f_{ξ}^{0} | ξ < λ⟩ and define the functions f_{ξ} by induction on ξ < λ such that:

1. f_{0} = f_{0}^{0}, and f_{ξ+1} is such that

max{f_{ξ}, f_{ξ}^{0}} < f_{ξ+1}.

2. At limit stages δ < λ with cf(δ) = κ and such that |A| < κ < min(A) let f_{δ} be the minimal club-obedient bound of ⟨f_{ξ} | ξ < δ⟩.

3. At limit stages δ < λ with cf(δ) not of that form use the fact that ΠA/J_{<λ} is λ-directed to define f_{δ} as a <_{J_{<λ}} bound of ⟨f_{ξ} | ξ < δ⟩.

Minimally obedient sequences will be used in conjunction with κ-presentable elementary substructures.

5.7 Lemma. Let A be a progressive set of regular cardinals, and κ be a regular cardinal such that |A| < κ < min(A). Suppose that

1. λ ∈ pcf(A),

2. f = ⟨f_{ξ} | ξ < λ⟩ is a minimally obedient at cofinality κ, universal sequence for λ, and

3. N ≺ H_{Ψ} (for Ψ large enough) is an elementary, κ-presentable substructure of H_{Ψ} such that λ, f, A ∈ N. (So A ⊂ N.)

Let N̄ denote the ordinal closure of N ∩ Ord, that is the set of ordinals that are in N or that are limit of ordinals in N. Then for every γ ∈ (N̄ ∩ λ) \ N there is a closed unbounded set C ⊆ γ ∩ N (of order-type κ) such that f_{γ} = sup{f_{ξ} | ξ ∈ C} and thus

f_{γ}(a) ∈ N̄ ∩ a for every a ∈ A.

In particular, for γ = Ch_{N}(λ), γ ∈ N̄ \ N, and f_{γ} = sup{f_{ξ} | ξ ∈ C} for a closed unbounded set C ⊆ γ ∩ N such that 1. each f_{ξ} is in N, and

2. for every h ∈ N ∩ ΠA

h ↾ B_{λ}[A] <_{J_{<λ}} f_{ξ} ↾ B_{λ}[A]

for some ξ ∈ C.

Proof. Since N is κ-presentable, N = ⋃_{α<κ} N_{α} is the union of an increasing and continuous chain such that N_{α} ∈ N_{α+1}. It follows for every γ ∈ N̄, that either γ ∈ N or cf(γ) = κ. Indeed, if γ ∈ N̄ \ N, then γ is a limit point of ordinals in N and yet γ is not a limit point of ordinals in any N_{α} (or else γ ∈ N̄_{α} ⊂ N). Hence sup(γ ∩ N_{α}) < γ and

E = {sup(γ ∩ N_{α}) | α < κ}

is closed unbound in γ and of order-type κ. Thus cf(γ) = κ. Observe that E ⊆ N, because N_{α} ∈ N implies that N̄_{α} ⊂ N and in particular sup(γ ∩ N_{α}) ∈ N.

Now take γ ∈ (N̄ ∩ λ) \ N and consider f_{γ}(a) for a ∈ A. Since cf(γ) = κ, f_{γ} is the minimal club-obedient bound of {f_{ξ} | ξ < γ}, and there is thus a closed unbounded set C ⊆ γ such that f_{γ} = f_{C}. It follows from the minimality of f_{C} that f_{C} = f_{C∩E} and we may thus assume at the outset that C ⊆ N. So f_{γ} = f_{C} = sup{f_{ξ} | ξ ∈ C} is the supremum of a set of functions that are all in N. (As C ⊂ N implies that f_{ξ} ∈ N for ξ ∈ C.) This shows that f_{γ}(a) ∈ N̄ for every a ∈ A.

In particular, if γ = Ch_{N}(λ), then γ < λ because κ < λ and N has cardinality κ. So γ ∈ N̄ \ N. Item 2 is a consequence of the fact that f is a universal sequence (see Theorem 4.13) and that C is unbounded in N ∩ λ. ⊣

The conclusions of lemmas 5.4 and 5.7 will be given names (I.32 and I.33) so that we can easily refer to these properties in the future. Let A be a progressive set of regular cardinals and suppose that κ is a regular cardinal such that |A| < κ < min A. Suppose that λ ∈ pcf(A), and f = ⟨f_{ξ} | ξ ∈ λ⟩ is a sequence of functions in ΠA. We shall refer to the following two properties of a κ-presentable N ≺ H_{Ψ} and a sequence f = ⟨f_{ξ} | ξ < λ⟩ such that f ∈ N.

If γ = Ch_{N}(λ), then
{a ∈ A | Ch_{N}(a) ≤ f_{γ}(a)}
is a B_{λ}[A] set.

(I.32)

If γ = Ch_{N}(λ), then

1. f_{γ} ≤ Ch_{N}.

2. For every h ∈ N ∩ ΠA there exists some d ∈ N ∩ ΠA such that

h ↾ B <_{J_{<λ}} d ↾ B and d ≤ f_{γ},

where B = B_{λ}[A].

(I.33)

We have seen that any persistently cofinal sequence for λ satisfies (I.32) (this is Lemma 5.4), and that any universal, minimally obedient sequence satisfies (I.33) as well (by Lemma 5.7).

Suppose that f is a sequence of length λ and N ≺ H_{Ψ} is κ-presentable and such that f ∈ N (so A, λ ∈ N). Suppose that both (I.32) and (I.33) hold. If γ = Ch_{N}(λ), then f_{γ} ≤ Ch_{N} by (I.33), and hence

{a ∈ A | Ch_{N}(a) = f_{γ}(a)}  (I.34)

is a B_{λ}[A] set by (I.32). We shall use this observation in the following.

5.8 Lemma. Suppose that A is a progressive set of regular cardinals and κ is a regular cardinal such that |A| < κ < min A. Suppose that λ_{0} ∈ pcf(A) and f^{λ_{0}} = ⟨f_{ξ}^{λ_{0}} | ξ < λ_{0}⟩ is a sequence of functions in ΠA Let N ≺ H_{Ψ} be a κ-presentable elementary substructure (Ψ is some large enough cardinal) such that A, λ_{0}, f^{λ_{0}} ∈ N. Suppose that N and f^{λ_{0}} ∈ N satisfy properties (I.32) and (I.33) for λ = λ_{0}. Put γ_{0} = Ch_{N}(λ_{0}) and define

b_{λ_{0}} = {a ∈ A | Ch_{N}(a) = f_{γ_{0}}^{λ_{0}}(a)}.

Then the following hold.

1. b_{λ_{0}} is a B_{λ_{0}}[A] set, namely

J_{≤λ_{0}}[A] = J_{<λ_{0}}[A] + b_{λ_{0}}.

2. There exists a set b′_{λ_{0}} ⊆ b_{λ_{0}} such that

(a) b′_{λ_{0}} ∈ N

(b) b_{λ_{0}} \ b′_{λ_{0}} ∈ J_{<λ_{0}}[A] (hence b′_{λ_{0}} is also a B_{λ_{0}} set).

Proof. Note that since f_{γ_{0}}^{λ_{0}} ≤ Ch_{N}, b_{λ_{0}} = {a ∈ A | Ch_{N}(a) ≤ f_{γ_{0}}^{λ_{0}}(a)}. We have already observed in the paragraph preceding the lemma that 1 holds.

We prove 2. As the definition of b_{λ_{0}} involves N and f_{γ_{0}}^{λ_{0}}, we do not expect that b_{λ_{0}} ∈ N. However we shall find an inner approximation b′_{λ_{0}} of b_{λ_{0}} that lies in N. If a ∈ A and f_{γ_{0}}^{λ_{0}}(a) < Ch_{N}(a), then there exists some α < κ such that f_{γ_{0}}^{λ_{0}}(a) < Ch_{N_{α}}(a) (because N = ⋃_{α<κ} N_{α}). Since |A| < κ, there is some large enough α < κ such that

f_{γ_{0}}^{λ_{0}}(a) < Ch_{N}(a) iff f_{γ_{0}}^{λ_{0}}(a) < Ch_{N_{α}}(a)

holds for every a ∈ A. Or equivalently (by negating both sides)

a ∈ b_{λ_{0}} iff Ch_{N_{α}}(a) ≤ f_{γ_{0}}^{λ_{0}}(a).

That is we have replaced the parameter N with N_{α} in the definition of b_{λ_{0}}, but γ_{0} is still a parameter not in N.

Since f^{λ_{0}} satisfies (I.33), there exists (for h = Ch_{N_{α}}) some function d ∈ N such that

1. Ch_{N_{α}} ↾ B_{λ_{0}} <_{J_{<λ_{0}}} d ↾ B_{λ_{0}} and

2. d ≤ f_{γ_{0}}^{λ_{0}}.

Define

b′_{λ_{0}} = {a ∈ A | Ch_{N_{α}}(a) ≤ d(a)}.

Now all parameters are in N and clearly b′_{λ_{0}} ∈ N. Property 1 above implies that for almost all a ∈ B_{λ_{0}}, Ch_{N_{α}}(a) < d(a) (i.e. except on a J_{<λ_{0}} set). Hence B_{λ_{0}} ⊆_{J_{<λ_{0}}} b′_{λ_{0}}. Property 2 implies that b′_{λ_{0}} ⊆ b_{λ_{0}}. ⊣

Suppose that for every λ ∈ pcf(A) we attach a certain B_{λ}[A] set b_{λ}^{∗}. Then the Inductive Covering Theorem (4.11) gives a finite set λ_{0}, …, λ_{n−1} of pcf(A) cardinals such that A = b_{λ_{0}}^{∗} ∪ ⋯ ∪ b_{λ_{n−1}}^{∗}. Now let N ≺ H_{Ψ} be such that A ∈ N and assume that the sets b_{λ}^{∗} are chosen in N for each λ ∈ pcf(A) ∩ N. Then the covering cardinals λ_{0}, …, λ_{n−1} can be found in N, even when the map λ ↦ b_{λ}^{∗} is not in N. To prove that, we define a descending sequence of cardinals λ_{0} > ⋯ λ_{i} by induction on i, starting with λ_{0} = max pcf(A), so that the following two conditions hold.

1. λ_{i} ∈ N.

2. If A_{k} = A \ (b_{0}^{∗} ∪ ⋯ ∪ b_{k−1}^{∗}) ≠ ∅, then λ_{k} = max pcf(A_{k}).

Since b_{0}^{∗}, …, b_{k−1}^{∗} are in N, A_{k} ∈ N as well, and hence λ_{k} ∈ N (whenever A_{k} ≠ ∅ and λ_{k} is defined). It follows from lemmas 4.14 and 4.10 that λ_{0} > λ_{1} > ⋯ > λ_{k}. Hence, for some k, A_{k} = ∅, and then A = b_{0}^{∗}∪⋯∪b_{k−1}^{∗}.

Here is a main result saying that the number of characteristic functions Ch_{N} ↾ A is bounded by max pcf(A).

5.9 Corollary. Suppose that A is a progressive set of regular cardinals, κ is a regular cardinal such that |A| < κ < min(A), and N with A ∈ N is a κ-presentable elementary substructure N ≺ H_{Ψ} and containing, for every λ ∈ pcf(A)∩N, a sequence f^{λ} = ⟨f_{ξ}^{λ} | ξ < λ⟩ that satisfies properties (I.32) and (I.33). Then there are cardinals λ_{0} > λ_{1} ⋯ > λ_{n} in N ∩ pcf(A) such that

Ch_{N} ↾ A = sup{f_{γ_{0}}^{λ_{0}}, …, f_{γ_{n}}^{λ_{n}}},  (I.35)

where γ_{i} = Ch_{N}(λ_{i}).

Proof. We employ Lemma 5.8, which assigns B_{λ}[A] sets, b′_{λ} ∈ N, for every λ ∈ pcf(A) ∩ N, so that

b′_{λ} ⊆ {a ∈ A | Ch_{N}(a) = f_{Ch_{N} (λ)}^{λ}(a)}.  (I.36)

By the Inductive Covering procedure explained above, for some λ_{0}, …, λ_{n−1} in pcf(A) ∩ N

A = b′_{λ_{0}} ∪ ⋯ ∪ b′_{λ_{n−1}}.

Since property (I.33) ensures that f_{Ch_{N} (λ)}^{λ} ≤ Ch_{N}, (I.36) implies that (I.35) holds. ⊣

Application: the cofinality of ([μ]^{κ}, ⊆)

For cardinals κ ≤ μ, let [μ]^{κ} denote the collection of all subsets of μ of size κ. Under the inclusion relation ⊆ this collection is a partial ordering, and we denote its cofinality cf([μ]^{κ}, ⊆). Likewise, [μ]^{<κ} is the collection of all subsets of μ of cardinality less than κ. For example, if μ is a regular cardinal then the collection of all proper initial segments of μ is cofinal in [μ]^{<μ}.

One reason for the importance of studying cf([μ]^{κ}, ⊆) is the relationship

|[μ]^{κ}| = cf([μ]^{κ}, ⊆) · 2^{κ}  (I.37)

and its applications to cardinal arithmetic (which we shall see). The proof of (I.37) is quite simple. Suppose that cf([μ]^{κ}, ⊆) = λ and let Y = {Y_{i} ∈ [μ]^{κ} | i < λ} be cofinal. A one-to-one map from [μ]^{κ} to Y × 2^{κ} can be defined as follows. For every E ∈ [μ]^{κ} find some E ⊆ Y_{i}. Since Y_{i} ∼ κ, E is isomorphic to some subset S of κ, and then we map E to ⟨Y_{i}, S⟩.

We record some relatively simple facts about cofinalities of [μ]^{κ}.

5.10 Lemma. For any cardinal μ:

1. If κ_{1} < κ_{2} then

cf([μ]^{κ_{1}}, ⊆) ≤ cf([μ]^{κ_{2}}, ⊆) · cf([κ_{2}]^{κ_{1}}, ⊆).

2. If μ_{1} < μ_{2} then cf([μ_{1}]^{κ}, ⊆) ≤ cf([μ_{2}]^{κ}, ⊆).

3. Suppose that κ ≤ μ and E ⊆ [μ]^{κ} is cofinal. Then there exists a cofinal set in ([μ^{+}]^{κ}, ⊆) of cardinality |E| · μ^{+}.

Proof. We prove the third item. For every μ ≤ γ < μ^{+} let f_{γ} be a bijection from γ to μ. Then the collection of all sets of the form f_{γ}^{−1} X, where X ∈ E, is cofinal and of cardinality |E| · μ^{+}. ⊣

A consequence (which can be proved by induction) is that for every n < ω, cf([ℵ_{n}]^{ℵ_{0}}, ⊆) = ℵ_{n}.

The first application of the pcf theory to the subset cofinality question is the following

5.11 Theorem. Suppose that μ is a singular cardinal, and κ < μ is an infinite cardinal such that the interval A of regular cardinals in (κ, μ) has size ≤ κ. Then

cf([μ]^{κ}, ⊆) = max pcf(A).

Proof. Let μ and κ be as in the theorem. Define

A = {γ | γ is a regular cardinal and κ < γ < μ}.

We assume that |A| ≤ κ, so that A is a progressive interval of regular cardinals. To prove the theorem, we first prove the easier inequality ≥. Let {X_{i} | i ∈ I} ⊆ [μ]^{κ} be cofinal and of cardinality cf([μ]^{κ}, ⊆). Define h_{i} = Ch_{X_{i}} ↾ A. That is, h_{i}(a) = sup a ∩ X_{i} for a ∈ A. Then {h_{i} | i ∈ I} is cofinal in (ΠA, <). (Since for every f ∈ ΠA the range of f is a subset of μ of size ≤ |A| ≤ κ, and is hence covered by some X_{i}. So f ≤ h_{i}.) But we know that the cofinality of (ΠA, <) is max pcf(A), and hence |I| ≥ max pcf(A).

Now we prove the ≤ inequality. We assume first that |A| < κ and prove the ≤ inequality for this case. Then we can obtain the |A| = κ case by applying the first case to κ^{+} (instead of κ) and using

cf([μ]^{κ}, ⊆) ≤ cf([μ]^{κ^{+}}, ⊆) · κ^{+}.

So assume that |A| < κ (and hence κ is uncountable). We plan to present a cofinal subset of [μ]^{κ} of cardinality max pcf(A). Fix for every ρ ∈ pcf(A) a minimally obedient (at cofinality κ) universal sequence for ρ, and let f = {f^{ρ} | ρ ∈ pcf(A)} be the resulting array of sequences. In fact, we let f be the minimal such array in the well-ordering <^{∗} of H_{Ψ}, so that f ∈ M for every M ⊆ H_{Ψ} such that A ∈ M. Let M be the collection of all substructures M ≺ H_{Ψ} that are κ-presentable and such that A ∈ M (so A ⊆ M). We know that (I.32) and (I.33) hold. Consider the collection F = {M ∩ μ | M ∈ M}. This collection is clearly cofinal in [μ]^{κ}, since for any set X ∈ [μ]^{κ} a structure M ∈ M can be defined so that X ⊆ M (or even X ∈ M). We shall prove that |F | ≤ max pcf(A). We know (by Corollary 5.9) that for every M ∈ M, Ch_{M} ↾ A is the supremum of a finite number of functions taken from the array {f^{ρ} | ρ ∈ pcf(A)}, which contains max pcf(A) functions. Hence it suffices to prove that whenever M, N ∈ M are such that Ch_{M} ↾ A = Ch_{N} ↾ A, then M ∩μ = N ∩μ. But this is exactly Theorem 5.2. ⊣

The theorem just proved (5.11) has important consequences for cardinal arithmetic which we shall explore now. Look, for example, at μ = ℵ_{ω}, κ = ℵ_{0}, and A = {ℵ_{n} | 1 < n < ω}. Then

cf([ℵ_{ω}]^{ℵ_{0}}, ⊆) = max pcf(A).

Similarly, for every n < ω, cf([ℵ_{ω}, ⊆]^{ℵ_{n}}, ⊆) = max pcf(A). Hence

cf([ℵ_{ω}]^{ℵ_{n}}, ⊆) = cf([ℵ_{ω}]^{ℵ_{m}}, ⊆)

for every n, m < ω.

Since A is an interval of regular cardinals, pcf(A) is also an interval of regular cardinals (Theorem 3.9) containing all regular cardinals from ℵ_{2} to max pcf(A). Hence if we write max pcf(A) = ℵ_{α}, then |α| = |pcf(A)| follows. Yet |pcf(A)| ≤ 2^{ℵ_{0}} (Theorem 3.6). Thus cf([ℵ_{ω}]^{ℵ_{0}}, ⊆) = ℵ_{α} for α < (2^{ℵ_{0}})^{+}. Thus we have proved the following theorem.

5.12 Theorem. cf([ℵ_{ω}]^{ℵ_{0}}, ⊆) < ℵ_{(2^{ℵ_{0}} )^{+}}.

An immediate conclusion is

5.13 Theorem. ℵ_{ω}^{ℵ_{0}} < ℵ_{(2^{ℵ_{0}} )^{+}}.

Proof. If 2^{ℵ_{0}} > ℵ_{ω} (equality is impossible by König’s theorem) then ℵ_{ω}^{ℵ_{0}} = 2^{ℵ_{0}}, and then 2^{ℵ_{0}} ≤ ℵ_{2^{ℵ_{0}}} implies the theorem as a triviality. So we assume that 2^{ℵ_{0}} < ℵ_{ω}.

Suppose that ℵ_{α} = cf([ℵ_{ω}]^{ℵ_{0}}, ⊆). We have proved in the preceding theorem that α < (2^{ℵ_{0}})^{+}. Let {X_{i} | i < ℵ_{α}} ⊆ [ℵ_{ω}]^{ℵ_{0}} be cofinal. So [ℵ_{ω}]^{ℵ_{0}} ⊆ ⋃{P(X_{i}) | i < ℵ_{α}}. Hence |[ℵ_{ω}]^{ℵ_{0}}| ≤ 2^{ℵ_{0}} · ℵ_{α} = ℵ_{α} < ℵ_{(2^{ℵ_{0}} )^{+}}. ⊣

We want to generalize this theorem to arbitrary singular cardinals ℵ_{δ} such that δ < ℵ_{δ}. A straightforward generalization gives the following which we leave as an exercise: If δ is a limit ordinal such that δ < ℵ_{δ}, then

cf([ℵ_{δ}]^{|δ|}, ⊆) < ℵ_{(2^{|δ|})^{+}}

and hence

ℵ_{δ}^{|δ|} < ℵ_{(2^{|δ|})^{+}}.

We shall describe now a tighter bound: ℵ_{δ}^{cf(δ)} < ℵ_{(|δ|^{cf(δ)})^{+}}.

As in the proof for bounding ℵ_{ω}^{ℵ_{0}}, which consists in first evaluating the cofinality of ([ℵ_{ω}]^{ℵ_{0}}, ⊆), here too we first investigate cardinalities of covering sets. For cardinals μ ≥ τ a cover for [μ]^{<τ} is a collection C of subsets of μ such that for every X ∈ [μ]^{<τ} there exists Y ∈ C with X ⊆ Y. For cardinals μ ≥ θ ≥ τ, cov(μ, θ, τ) is the least cardinality of a cover for [μ]^{<τ} consisting of sets taken from [μ]^{<θ}. So cov(μ, θ, τ) measures how many sets, each of cardinality < θ, are needed to cover every subset of μ of cardinality < τ. For example, cf([μ]^{κ}, ⊆) = cov(μ, κ^{+}, κ^{+}). We shall prove the following.

5.14 Theorem. Suppose that μ is a singular cardinal, and κ < μ a regular cardinal. Let A be the set of all regular cardinals in the interval [κ^{++}, μ). If |A| ≤ κ, then

cov(μ, κ^{+}, cf(μ)^{+}) = sup pcf_{cf(μ)}(A).

(See Definition 3.10 for pcf_{cf(μ)}(A).)

Before proving this theorem, let’s see how it can be employed.

5.15 Corollary. Suppose that δ is a limit ordinal such that δ < ℵ_{δ}. Then

cov(ℵ_{δ}, |δ|^{+}, cf(δ)^{+}) < ℵ_{(|δ|^{cf(δ)})^{+}}

and hence

ℵ_{δ}^{cf(δ)} < ℵ_{(|δ|^{cf(δ)})^{+}}.

Proof. Suppose that δ is a limit ordinal such that δ < ℵ_{δ}. Let μ = ℵ_{δ}, and κ = |δ|^{+}. Define A as the set of all regular cardinals in the interval (κ++, μ]. So |A| ≤ |δ|. By Theorem 5.14, there exists a collection {X_{i} | i ∈ I}, where X_{i} ∈ [μ]^{κ} and |I| = sup pcf_{cf(μ)}(A), such that for every Z ∈ [ℵ_{δ}]^{cf(μ)}, Z ⊆ X_{i} for some i ∈ I. Yet, by Theorem 3.11, pcf_{cf(μ)}(A) is also an interval of regular cardinals, containing all regular cardinals in the interval [κ^{++}, ℵ_{α}) where ℵ_{α} = sup pcf_{cf(μ)}(A). Now |pcf_{cf(μ)}(A)| ≤ |[A]^{cf(μ)}| · 2^{cf(μ)} ≤ |δ|^{cf(μ)}. It follows (see the proof in the following paragraph) that α < (|δ|^{cf(μ)})^{+}. That is, |I| < ℵ_{(|δ|^{cf(δ)})^{+}} (as cf(μ) = cf(δ)). Hence |[ℵ_{δ}]^{cf(δ)}| < κ^{cf(δ)} · ℵ_{(|δ|^{cf(δ)})^{+}}. Thus ℵ_{δ}^{cf(δ)} < ℵ_{(|δ|^{cf(δ)})^{+}} as required.

We prove that α < (|δ|^{cf(μ)})^{+}. Since δ < |δ|^{+} ≤ (|δ|^{cf(μ)})^{+}, it follows that the interval (ℵ_{δ}, ℵ_{(|δ|^{cf(μ)})^{+}}) contains (|δ|^{cf(μ)})^{+} regular cardinals. But the interval of regular cardinals in (ℵ_{δ}, ℵ_{α}) is included in pcf_{cf(μ)}(A) and contains ≤ |δ|^{cf(μ)} regular cardinals. Hence α < (|δ|^{cf(μ)})^{+}. ⊣

We proceed now with the proof of Theorem 5.14. Let κ < μ and |A| ≤ κ be as in the theorem. Since A is cofinal in μ and |A| ≤ κ, cf(μ) ≤ κ. Let ρ = cf(μ) be the cofinality of μ. We shall prove that cov(μ, κ^{+}, ρ^{+}) = sup pcf_{ρ}(A).

For the ≥ inequality, we must prove that cov(μ, κ^{+}, ρ^{+}) ≥ λ for every λ ∈ pcf_{ρ}(A). That is, if A_{0} ⊆ A is of cardinality ρ we want to prove that cov(μ, κ^{+}, ρ^{+}) ≥ max pcf(A_{0}). So let {X_{i} | i ∈ I} be a covering of [μ]^{cf(μ} with sets X_{i} of cardinality ≤ κ. For each X_{i} define h_{i} = Ch_{X_{i}} ↾ A_{0}. Then {h_{i} | i ∈ I} is cofinal in (ΠA_{0}, <), and hence |I| ≥ max pcf(A_{0}).

For the ≤ inequality, we must provide a covering set for cov(μ, κ^{+}, ρ^{+}) of cardinality sup pcf_{ρ}(A).

For every λ ∈ pcf_{ρ}(A), λ ∈ pcf(A) as well, and we fix a minimally obedient at cofinality ρ^{+} sequence f^{λ} = ⟨f_{ξ}^{λ} | ξ < λ⟩ of functions in ΠA that is universal for λ.

For every α < μ such that cf(α) = ρ^{+}, let E_{α} ⊆ α be a closed unbounded subset of α of order type ρ^{+}.

Define F as the collection of all functions of the form sup{f_{α_{1}}^{λ_{1}}, ⋯, f_{α_{n}}^{λ_{n}}} where λ_{i} ∈ pcf_{ρ}(A) and α_{i} < λ_{i}. Clearly F has cardinality sup pcf_{ρ}(A). For every f ∈ F let

E(f) = ⋃{E_{f(a)} | a ∈ A and cf(f(a)) = ρ^{+}}

Then the cardinality of E(f) is at most κ^{+}. Let

K(f) = Skolem(E(f) ∪ κ^{+}) ≺ H_{Ψ}

be the Skolem hull (closure) of E(f) ∪ κ^{+}. We remind the reader that the structure H_{Ψ} includes a class well-ordering <^{∗} of all sets, and hence there is a countable set of Skolem functions for H_{Ψ} so that X ≺ H_{Ψ} iff X is closed under all of these Skolem functions. The cardinality of K(f) is κ^{+}.

Clearly K = {K(f) | f ∈ F} has cardinality ≤ sup pcf_{ρ}(A). Our aim now is to show that

K covers [μ]^{cf(μ)}.

Since cf([κ^{+}]^{κ}, ⊆) = κ^{+}, this yields that

cov(μ, κ^{+}, cf(μ)^{+}) = sup pcf_{cf(μ)}(A).

Let Z ⊂ μ be of size ρ = cf(μ). Define ⟨M_{i} | i < ρ^{+}⟩ an increasing and continuous chain of elementary substructures M_{i} ≺ H_{Ψ}, each of cardinality ρ, such that A, Z ∈ M_{0} and Z ⊂ M_{0}. Let M = ⋃_{i<ρ^{+}} M_{i} be the resulting ρ^{+}-presentable structure.

For every a ∈ A∩M (and in fact for every a ∈ A), Ch_{M}(a) has cofinality ρ^{+}. Indeed ⟨Ch_{M_{i}}(a) | i < ρ^{+}⟩ is increasing, continuous and with limit Ch_{M}(a). There is another closed unbounded sequence in Ch_{M}(a) which interests us, namely E_{Ch_{M} (a)}, and we consider the intersection of these two closed unbounded sets. So there exists a closed unbounded set D_{a} ⊆ ρ^{+} such that for every i ∈ D_{a}

Ch_{M_{i}}(a) ∈ E_{Ch_{M} (a)}.  (I.38)

For every i < ρ^{+}, M_{i} has cardinality ρ and hence D(i) = ⋂{D_{a} | a ∈ A ∩ M_{i}} is closed unbounded in ρ^{+}. Form the diagonal intersection D = {j ∈ ρ^{+} | ∀i < j (j ∈ D(i))}. Fix any j_{0} ∈ D′ (a limit point of D). For every a ∈ A ∩ M_{j_{0}} there exists some j_{1} < j_{0} such that a ∈ A ∩ M_{j_{1}}. If j_{1} < i ≤ j_{0} and i ∈ D, then i ∈ D(j_{1}) and hence i ∈ D_{a}. So Ch_{M_{i}}(a) ∈ E_{Ch_{M} (a)}. Thus ⟨Ch_{M_{i}}(a) | j_{1} < i < j_{0} ∧ i ∈ D⟩ is a sequence of ordinals in M_{j_{0}} ∩ E_{Ch_{M} (a)} that tends to Ch_{M_{j_{0}}} (a) (whenever j_{0} ∈ D′ and a ∈ A ∩ M_{j_{0}}).

Define A_{0} = A ∩ M_{j_{0}}. Then A_{0} ∈ [A]^{cf(μ)}, and A_{0} ∈ M. We plan to apply Corollary 5.9 to A_{0}, ρ^{+} and M (substituting A, κ, and N there). For every λ ∈ pcf(A_{0}), λ ∈ pcf_{cf(μ)}(A) and the sequence ⟨f_{ξ}^{λ} ↾ A_{0} | ξ < λ⟩ is, in M, universal for λ and minimally obedient at ρ^{+}. Hence, by 5.9,

Ch_{M} ↾ A_{0} = f ↾ A_{0} for some f ∈ F.  (I.39)

Since Z ⊆ M_{j_{0}}, the following proves that Z ⊆ K(f).

Claim. M_{j_{0}} ∩ μ ⊆ K(f).

By Lemma 5.2, this is a consequence of the following

5.16 Lemma. For every successor cardinal σ^{+} ∈ M_{j_{0}} ∩ μ

sup (M_{j_{0}} ∩ σ^{+}) = sup (M_{j_{0}} ∩ K(f) ∩ σ^{+}).

Proof. Assume that σ^{+} ∈ M_{j_{0}} ∩ μ. If σ^{+} ≤ κ^{+}, then κ^{+} ⊆ K(f) implies the lemma immediately. So assume that σ^{+} > κ^{+}, and hence that σ^{+} ∈ A ∩ M_{j_{0}} = A_{0}. Now (I.39) implies that Ch_{M}(σ^{+}) = f(σ^{+}) = α. Hence cf(α) = ρ^{+} and E_{α} ⊆ E(f) ⊆ K(f). The sequence ⟨Ch_{M_{i}}(σ^{+}) | j_{1} < i < j_{0} ∧ i ∈ D⟩ is unbounded in Ch_{M_{j_{0}}} (σ^{+}), as we have observed above, and thus shows that the lemma is correct. ⊣

5.17 Exercise. 1. Let μ, κ, and A be as in Theorem 5.14. Suppose that |A| ≤ κ. Prove that

cov(μ, κ^{+}, ℵ_{1}) = sup pcf_{ℵ_{0}}(A).

Conclude that if δ < ℵ_{δ} is a limit ordinal, then

ℵ_{δ}^{ℵ_{0}} < ℵ_{(|δ|^{ℵ_{0}} )^{+}}.

Hint. By induction on μ.

2. Suppose that δ is a limit ordinal such that for every cardinal μ < δ μ^{ℵ_{0}} < δ. Then ℵ_{δ} satisfies the same property, namely for every μ < ℵ_{δ}, μ^{ℵ_{0}} < ℵ_{δ}.

Hint. w.l.o.g. δ < ℵ_{δ}. Prove that μ^{ℵ_{0}} < ℵ_{δ} by induction on μ < ℵ_{δ}.

6. Elevations and transitive generators

Given a progressive set A of regular cardinals, we have proved the existence of generating sets B_{λ} = B_{λ}[A]. Suppose that N is such that A ⊆ N ⊆ pcf(A) and B = ⟨B_{λ} | λ ∈ N⟩ is a generating sequence (defined only for λ in N). Then B is said to be smooth (or transitive) if for every λ ∈ N and θ ∈ B_{λ}, B_{θ} ⊆ B_{λ}.

This definition is trivial when B_{θ} = {θ} (that is when θ ∉ pcf(A ∩ θ)). However, we shall be interested in A’s for which θ ∈ pcf(A ∩ θ) is possible for θ ∈ A. The reason for considering subsets N of pcf(A) in this definition, rather than the whole pcf(A) (which would be most desirable) is that we only know to prove the existence of smooth sequences for sets N of cardinality min(A).

Our aim is to obtain transitive generators; they will be useful in proving, for example, that for every progressive interval of regular cardinals A, |pcf(A)| < |A|^{+4}. However, there is still some material to cover beforehand.

Fix a progressive set A of regular cardinals and let κ be a regular cardinal such that |A| < κ < min(A). For every λ ∈ pcf(A) let f^{λ} = ⟨f_{ξ}^{λ} | ξ < λ⟩ be a universal sequence for λ which is minimally obedient (at cofinality κ). It is convenient to assume that for a ∈ A \ λ, f_{ξ}^{λ}(a) = ξ. The elevation of the array ⟨f^{λ} | λ ∈ pcf(A)⟩ is another array ⟨F^{λ} | λ ∈ pcf(A)⟩ of persistently cofinal sequences defined below, and which will be shown to satisfy properties (I.32) and (I.33).

For every finite, decreasing sequence λ_{0} > λ_{1} > ⋯ > λ_{n} of cardinals such that λ_{0} ∈ pcf(A) and λ_{i+1} ∈ A ∩ λ_{i} for i < n, and for every ordinal γ_{0} ∈ λ_{0}, define a sequence γ_{1} ∈ λ_{1}, …, γ_{n} ∈ λ_{n} by

γ_{i+1} = f_{γ_{i}}^{λ_{i}}(λ_{i+1}).  (I.40)

So γ_{1} = f_{γ_{0}}^{λ_{0}}(λ_{1}), γ_{2} = f_{γ_{1}}^{λ_{1}}(λ_{2}), etc. until γ_{n} = f_{γ_{n−1}}^{λ_{n−1}}(λ_{n}). Now define the elevation function El_{λ_{0},...,λ_{n}} on λ_{0} by

El_{λ_{0},...,λ_{n}}(γ_{0}) = γ_{n}.

We say that the last value obtained, γ_{n}, is reached from f_{γ_{0}}^{λ_{0}} via the descending sequence λ_{0} > λ_{1} > ⋯ > λ_{n}.

Fix a cardinal λ_{0} ∈ pcf(A). We want to define the elevated sequence F^{λ_{0}}, first on A ∩ λ_{0}. Given any λ ∈ A ∩ λ_{0}, let F_{λ_{0},λ} be the set of all finite, descending sequences ⟨λ_{0} > λ_{1} > ⋯ > λ_{n}⟩ leading from λ_{0} to λ_{n} = λ, such that λ_{i} for i > 0 are all in A. For every γ_{0} ∈ λ_{0} we ask whether there is a maximal value among

{El_{λ_{0},...,λ_{n}}(γ_{0}) | ⟨λ_{0}, …, λ_{n}⟩ ∈ F_{λ_{0},λ}}.

If this set contains a maximum, let F_{γ_{0}}^{λ_{0}}(λ) be that maximum, and otherwise put F_{γ_{0}}^{λ_{0}}(λ) = f_{γ_{0}}^{λ_{0}}(λ). In case λ ∈ A and λ ≥ λ_{0}, define F_{γ_{0}}^{λ_{0}}(λ) = γ_{0}. So F^{λ_{0}} = ⟨F_{γ}^{λ_{0}} | γ < λ_{0}⟩ with F_{γ}^{λ_{0}} ∈ ΠA is defined.

The elevated array ⟨F^{λ_{0}} | λ_{0} ∈ pcf(A)⟩ thus defined will give the required transitive generating sequence. Observe first that

f_{γ}^{λ_{0}} ≤ F_{γ}^{λ_{0}} for every γ < λ_{0}.

This is so because El_{λ_{0},λ}(γ_{0}) = f_{γ_{0}}^{λ_{0}}(λ) for every λ ∈ A ∩ λ_{0}; so that this original value is among the values considered for maximum. Hence

F^{λ_{0}} is persistently cofinal for λ_{0}.

This shows that Lemma 5.4 can be applied and property (I.32) holds whenever F^{λ} ∈ N (and N is κ-presentable).

Another observation concerns any κ-presentable elementary substructure N ≺ H_{Ψ} such that A, ⟨f^{λ} | λ ∈ pcf(A)⟩ ∈ N. Being definable, the elevated array is also in N. Even though each f^{λ} is assumed to be minimally obedient, the elevated sequence F^{λ} is not any more club-obedient. We have however the following consequence of Lemma 5.7.

6.1 Lemma. If λ_{0} ∈ pcf(A) ∩ N and γ_{0} = Ch_{N}(λ_{0}), then for every λ ∈ A ∩ λ_{0}, F_{γ_{0}}^{λ_{0}}(λ) ∈ N̄ ∩ λ. (Where N̄ is the ordinal closure of N.) Thus the elevated sequence F^{λ_{0}} satisfies (I.33). Namely,

1. F_{γ_{0}}^{λ_{0}}(λ) ≤ Ch_{N}(λ) for every λ ∈ A, and

2. for every h ∈ N ∩ ΠA there exists some d ∈ N ∩ ΠA such that

h ↾ B <_{J_{<λ_{0}}} d ↾ B and d ≤ F_{γ_{0}}^{λ_{0}}

where B = B_{λ_{0}}[A].

Proof. Observe first that A ⊆ N, λ ∈ N, and F_{λ_{0},λ} ⊆ N. Consider any ⟨λ_{0}, …, λ_{n}⟩ ∈ F_{λ_{0},λ} and the ordinals γ_{i} defined by (I.40). It follows from Lemma 5.7 that γ_{i} ∈ N̄. If γ_{i} ∈ N then obviously γ_{i+1} = f_{γ_{i}}^{λ_{i}}(λ_{i+1}) ∈ N. If, however, γ_{i} ∈ N̄ \ N, then Lemma 5.7 yields that f_{γ_{i}}^{λ_{i}}(a) ∈ N̄ for every a ∈ A, and in particular γ_{i+1} ∈ N̄. Thus El_{λ_{0},...,λ_{n}}(γ_{0}) ∈ N̄ and hence F_{γ_{0}}^{λ_{0}}(λ) ∈ N̄ ∩ λ.

Thus (I.33)(1) holds for F^{λ_{0}}. Since f^{λ_{0}} ≤ F^{λ_{0}}, where f^{λ_{0}} is universal and minimally obedient at κ, (I.33)(2) holds as well. ⊣

6.2 Lemma. Let A, f, and N be as in the previous lemma. Suppose that λ_{0} ∈ pcf(A) ∩ N, γ_{0} = Ch_{N}(λ_{0}) and λ ∈ A ∩ λ_{0}.

1. If for some descending sequence λ_{0} > ⋯ > λ_{n} = λ in F_{λ_{0},λ}

El_{λ_{0},...,λ_{n}}(γ_{0}) = Ch_{N}(λ).

Then Ch_{N}(λ) is the maximal value in {Elλ̄(γ_{0}) | λ̄ ∈ F_{λ_{0},λ}} and hence

Ch_{N}(λ) = F_{γ_{0}}^{λ_{0}}(λ).

2. Suppose that

F_{γ_{0}}^{λ_{0}}(λ) = γ.

For any a ∈ A ∩ λ, if

F_{γ}^{λ}(a) = Ch_{N}(a),

then

F_{γ_{0}}^{λ_{0}}(a) = Ch_{N}(a)

as well.

Proof. Item 1 says that if some descending sequence leading from λ_{0} to λ reaches Ch_{N}(λ), then no sequence reaches a higher value. But this is clear from Lemma 6.1 since Ch_{N}(λ) is the maximal possible value.

Item 2 uses Item 1. It says that if γ can be reached from f_{γ_{0}}^{λ_{0}} by a finite descending sequence leading to λ, and if there is another sequence leading from λ to a, so that Ch_{N}(a) can be reached from f_{γ}^{λ}, then Ch_{N}(a) can be reached already from f_{γ_{0}}^{λ_{0}} via the concatenation of these descending sequences (and no higher value can be reached—by 1). ⊣

Now we can get our transitive generating sequence.

6.3 Theorem (Transitive Generators.). Suppose that A is a progressive set of regular cardinals, and |A| < κ < min(A) is a regular cardinal. Let ⟨f^{λ} | λ ∈ pcf(A)⟩ be an array of minimally obedient (at cofinality κ) universal sequences. Let N ≺ H_{Ψ} be an elementary substructure that is κ-presentable and such that A, ⟨f^{λ} | λ ∈ pcf(A)⟩ ∈ N. Let ⟨F^{λ} | λ ∈ pcf(A)⟩ be the derived elevated array. For every λ_{0} ∈ pcf(A) ∩ N put γ_{0} = Ch_{N}(λ_{0}) and define

b_{λ_{0}} = {a ∈ A | Ch_{N}(a) = F_{γ_{0}}^{λ_{0}}(a)}.

then the following hold:

1. Every b_{λ_{0}} is a B_{λ_{0}}[A] set, namely

J_{≤λ_{0}}[A] = J_{<λ_{0}}[A] + b_{λ_{0}}.

2. There exists sets b′_{λ_{0}} ⊆ b_{λ_{0}}, for λ_{0} ∈ pcf(A) ∩ N, such that

(a) b_{λ_{0}} \ b′_{λ_{0}} ∈ J_{<λ_{0}}[A].

(b) b′_{λ_{0}} ∈ N (but the sequence ⟨b′_{λ_{0}} | λ_{0} ∈ pcf(A) ∩ N⟩ is not claimed to be in N).

3. The collection ⟨b_{λ} | λ ∈ pcf(A) ∩ N⟩ is transitive; which means that if λ_{1} ∈ b_{λ} then b_{λ_{1}} ⊂ b_{λ}.

Proof. The elevated sequence F^{λ_{0}}satisfies properties (I.32) (because it is persistently cofinal) and (I.33) (as shown in Lemma 6.1). Thus items 1 and 2 of our lemma follow from Lemma 5.8. Observe that b_{λ_{0}} ⊆ λ_{0} + 1, since B_{λ_{0}} ∈ J_{<λ_{0}^{+}}.

Transitivity (item 3) relies on Lemma 6.2. Suppose that λ_{0} ∈ pcf(A)∩N and λ_{1} ∈ b_{λ_{0}}. This means

Ch_{N}(λ_{1}) = F_{γ_{0}}^{λ_{0}}(λ_{1})

where γ_{0} = Ch_{N}(λ_{0}). Say Ch_{N}(λ_{1}) = γ_{1}. We have to show that b_{λ_{1}} ⊂ b_{λ_{0}} in this case. So assume that a ∈ b_{λ_{1}}. This means

Ch_{N}(a) = F_{γ_{1}}^{λ_{1}}(a).

Now Lemma 6.2(2) applies and yields

F_{γ_{0}}^{λ_{0}}(a) = Ch_{N}(a)

which gives a ∈ b_{λ_{0}}. ⊣

Localization

Localization is the following property of the pcf function which will be proved in this subsection.

If A is a progressive set of regular cardinals and B ⊆ pcf(A) is also progressive, then for every λ ∈ pcf(B) there exists B_{0} ⊆ B such that |B_{0}| ≤ |A| and λ ∈ pcf(B_{0}).

The localization property implies that there exists no B ⊆ pcf(A) with |B| = |A|^{+} and such that b > max pcf(B ∩ b) for every b ∈ B. For indeed if there were such B it would be progressive, and if we define λ = max pcf(B), then λ is not in the pcf of any proper initial segment of B. In fact, λ > max pcf(B_{0}) for any proper initial segment B_{0} of B. It is this conclusion, the simplest case of localization, which is proved first.

6.4 Theorem. Assume that A is a progressive set of regular cardinals. Then there is no set B ⊆ pcf(A) such that |B| = |A|^{+}, and, for every b ∈ B, b > max pcf(B ∩ b).

Proof. Assume on the contrary that A is as in the theorem and yet, for some B ⊆ pcf(A) of cardinality |A|^{+}, b > max pcf(B ∩ b) for every b ∈ B. Since A is progressive |A| < min A, and in case |A|^{+} ∈ A we may remove the first cardinal of A and assume that |A|^{+} < min A. The set E = A∪B of cardinality |A|^{+} thus satisfies |E| < min E and the Transitive Generators Theorem 6.3 can be applied to E.

Find a κ-presentable elementary substructure, N ≺ H_{Ψ}, that contains A and B where κ = |E|. Let ⟨b_{λ} | λ ∈ pcf(E) ∩ N⟩ be the set of transitive generators (subsets of E) as guaranteed by Theorem 6.3. Let b′_{λ} ∈ N be such that b′_{λ} ⊆ b_{λ} and b_{λ} \ b′_{λ} ∈ J_{<λ}.

Since |A| < |B| we can find an initial segment B_{0} ⊆ B of cardinality |A| such that if an arbitrary a ∈ A is in some b_{β}, β ∈ B, then it is already in some b_{β} with β ∈ B_{0}. Namely

∀a ∈ A [ (∃β ∈ B) a ∈ b_{β} ⟹ (∃β ∈ B_{0}) a ∈ b_{β} ].  (I.41)

Let β_{0} = min(B \ B_{0}). So B_{0} = B ∩ β_{0} and B_{0} ∈ N.

Claim. There exists a finite descending sequence of cardinals λ_{0} > ⋯ > λ_{n} in N ∩ pcf(B_{0}) such that

B_{0} ⊆ b_{λ_{0}} ∪ ⋯ ∪ b_{λ_{n}}.  (I.42)

Proof. In fact we shall find a finite sequence λ_{0}, …, λ_{n} ∈ N ∩ pcf(B_{0}) such that B_{0} ⊆ b′_{λ_{0}} ∪ ⋯ ∪ b′_{λ_{n}}. The proof is the same as that of Theorem 4.11, but one must be a little bit more careful to ensure that the pcf indexcardinals are in N.

So let λ_{0} = max pcf(B_{0}). Clearly λ_{0} ∈ N and hence b′_{λ_{0}} ∈ N. So B_{1} = B_{0} \ b′_{λ_{0}} ∈ N, and λ_{1} = max pcf(B_{1}) ∈ N ∩ λ_{0}. Next define B_{2} = B_{1} \ b′_{λ_{1}} etc. The point is that we have B_{i} ∈ N since b′_{λ_{i−1}} ∈ N, and we must stop with B_{n+1} = ∅ after a finite number of steps since λ_{0} > λ_{1} . . .. Since b′_{λ_{i}} ⊆ b_{λ_{i}}, (I.42) holds.

The following claim will bring the desired contradiction and thus prove the theorem. Recall that β_{0} = min(B \ B_{0}) and thus β_{0} > max(pcf(B_{0})) ≥ λ_{0}, …, λ_{n}. Since β_{0} ∈ pcf(A), β_{0} ∈ pcf(b_{β_{0}} ∩ A) (or else β_{0} ∈ pcf(A \ b_{β_{0}}) which is impossible by Lemma 4.14). Yet the following inclusion shows that this is impossible.

6.5 Claim. b_{β_{0}} ∩ A ⊆ b_{λ_{0}} ∪ … ∪ b_{λ_{n}}.

Proof. Consider any cardinal a ∈ b_{β_{0}} ∩ A. Then

a ∈ b_{β}

for some β ∈ B_{0} (by I.41). As B_{0} ⊆ b_{λ_{0}} ∪ ⋯ ∪ b_{λ_{n}}, β ∈ b_{λ_{i}} for some 0 ≤ i ≤ n. But transitivity implies

b_{β} ⊆ b_{λ_{i}}

and hence

a ∈ b_{λ_{i}}

as required. This claim shows that max pcf(b_{β_{0}} ∩ A) < β_{0}, and yet β_{0} ∈ pcf(b_{β_{0}} ∩ A) which is a contradiction! ⊣

Now we pass to the general case and prove the localization theorem.

6.6 Theorem (Localization). Suppose that A is a progressive set of regular cardinals. If B ⊆ pcf(A) is also progressive, then for every λ ∈ pcf(B) there exists B_{0} ⊆ B with |B_{0}| ≤ |A| and such that λ ∈ pcf(B_{0}).

Proof. We prove by induction on λ that for every A and B as in the theorem the conclusion holds for λ. Replacing B with B_{λ}[B], we may assume that λ = max pcf(A).

6.7 Claim. We may assume that the set λ ∩ pcf(B) has no maximal cardinal.

Proof. Suppose on the contrary the existence of some λ_{0} = max (λ ∩ pcf(B)). It is easy to remove λ_{0} by defining

B_{1} = B \ B_{λ_{0}}[B].

Then λ ∈ pcf(B_{1}) still holds since B_{λ_{0}} ∈ J_{<λ}. We can now replace B with B_{1}, and repeat, if necessary, this procedure a finite number of times until the claim holds (for some B_{k} which is renamed B).

We shall find now a set C ⊆ λ ∩ pcf(B) of cardinality ≤ |A| such that λ ∈ pcf(C). Such C is necessarily progressive. Together with the inductive hypothesis this will conclude the proof; because for every γ ∈ C we can pick B(γ) ⊆ B of cardinality ≤ |A| and such that γ ∈ pcf B(γ), and then define B_{0} = ⋃_{γ∈C} B(γ). Since C ⊆ pcf(B_{0}), λ ∈ pcf(B_{0}) will then follow from λ ∈ pcf(C) (by Theorem 3.12). So the following is the last piece of the proof.

6.8 Claim. There exists a set C ⊆ λ∩pcf(B) of cardinality ≤ |A| and such that λ ∈ pcf(C).

Proof. Assume no such C exists. We shall construct a sequence ⟨γ_{i} | i ∈ |A|^{+}⟩ of cardinals in pcf(B) such that

γ_{i} > max pcf {γ_{j} | j < i}.

This will contradict Theorem 6.4.

So suppose that C = {γ_{j} | j < i} have been defined. Then

λ > max pcf(C).

Indeed λ = max pcf(C) is impossible by our assumption that no such C exists, and λ < max pcf(C) is impossible since pcf(C) ⊆ pcf(B) and λ = max pcf(B). We can find now γ_{i} ∈ pcf(B) above max pcf(C) (recall that pcf(B) has no maximum below λ). ⊣

7. Size limitation on pcf of intervals

This relatively short section is devoted to a theorem which occupies a central place in the pcf theory and to a famous application:

ℵ_{ω}^{ℵ_{0}} < max{(2^{ℵ_{0}})^{+}, ℵ_{ω_{4}}}.

The reader will notice that many of the ingredients developed so far appear in its proof. We know that for any A progressive set of regular cardinals the cardinality of pcf(A) does not exceeds 2^{|A|}, and it is an open question whether |pcf(A)| ≤ |A| or not. At present the following theorem with its enigmatic appearance of the number four is the best result.

7.1 Theorem. Let A be an interval of regular cardinals such that |A| < min A. Then

|pcf A| < |A|^{+4}.

Proof. Suppose that A is as in the theorem a progressive interval of regular cardinals, but |pcf(A)| ≥ |A|^{+4}. Say |A| = ρ. The following proof provides a sequence B of length ρ^{+} of cardinals in pcf(A) such that each cardinal b ∈ B is above max pcf(B ∩ b). This, of course, will be in contradiction to Theorem 6.4.

Let S = S_{ρ^{+}}^{ρ^{+3}} be the set of ordinals in ρ^{+3} that have cofinality ρ^{+}. Choose a club guessing sequence ⟨C_{k} | k ∈ S⟩. So for every closed unbounded set E ⊆ ρ^{+3} there exists some k ∈ S such that C_{k} ⊂ E.

Consider the cardinal sup(A), and let σ be that ordinal such that ℵ_{σ} = sup(A). Since pcf(A) is an interval of regular cardinals (by Theorem 3.9), and since we assume that pcf(A) has cardinality at least ρ^{+4}, any regular cardinal in {ℵ_{σ+α} | α < ρ^{+4}} is in pcf(A).

We intend to define a closed set D ⊂ ρ^{+4} of order-type ρ^{+3}, D = {α_{i} | i < ρ^{+3}}, and the impossible sequence of length ρ^{+}, B, will be a subset of {ℵ_{σ+α}^{+} | α ∈ D}. The definition of the ordinal α_{i} is by induction on i < ρ^{+3}.

1. For i = 0, α_{0} = 0.

2. If i < ρ^{+3} is a limit ordinal, then α_{i} = sup{α_{j} | j < i}.

3. Suppose that {α_{j} | j ≤ i} have been defined for some i < ρ^{+3}, and we shall define α_{i+1}. Consider i + 1 ⊂ ρ^{+3} as an isomorphic copy of {α_{j} | j ≤ i}. For every k ∈ S look at the set C_{k} ∩ (i + 1) and define the set of cardinals e_{k} = {ℵ_{σ+α_{j}} | j ∈ C_{k} ∩ (i + 1)}. Then the set of successors e_{k}^{(+)} = {γ^{+} | γ ∈ e_{k}} is a set of regular cardinals, and we ask whether max pcf(e_{k}^{(+)}) < ℵ_{σ+ρ^{+4}} or not. There are ρ^{+3} such questions, and therefore we can define α_{i+1} < ρ^{+4} so that α_{i} < α_{i+1} and the following holds. For every k ∈ S, if max pcf(e_{k}^{(+)}) < ℵ_{σ+ρ^{+4}}, then max pcf(e_{k}^{(+)}) < ℵ_{σ+α_{i+1}}.

So D = {α_{i} | i < ρ^{+3}} is defined. Let δ = sup D. Then μ = ℵ_{σ+δ} is a singular cardinal of uncountable cofinality (that is, of cofinality ρ^{+3}). The Representation Theorem (Exercise 4.17) can be applied now. So there exists a closed unbounded set C ⊆ D such that

μ^{+} = max pcf({ℵ_{σ+α}^{+} | α ∈ C}).  (I.43)

The closed unbounded set D is isomorphic to ρ^{+3}, and C is transformed under this isomorphism to a closed unbounded set E ⊆ ρ^{+3}. That is

E = {i ∈ ρ^{+3} | α_{i} ∈ C}.

By the club-guessing property, there exists k ∈ S such that C_{k} ⊂ E. If C′_{k} denotes the non-accumulation points of C_{k}, we claim that B = {ℵ_{σ+α_{j}}^{+} | j ∈ C′_{k}} has the (impossible) property excluded by Theorem 6.4. Since the order-type of C_{k} is ρ^{+}, that of C′_{k} is also ρ^{+}. It suffices to prove for every i ∈ C_{k} that

max pcf({ℵ_{σ+α_{j}}^{+} | j ∈ C_{k} ∩ (i + 1)}) < ℵ_{σ+α_{i+1}}.  (I.44)

Consider the definition of α_{i+1}. The set e_{k} = {ℵ_{σ+α_{j}} | j ∈ C_{k} ∩ (i + 1)} was defined, and since e_{k}^{(+)} ⊆ {ℵ_{σ+α}^{+} | α ∈ C}, (I.43) implies that max pcf(e_{k}^{(+)}) ≤ μ^{+}. So the answer to the question for e_{k} was “yes”, and as a result (I.44) holds. ⊣

This theorem leads to surprising applications. Consider for example A = {ℵ_{n} | n ∈ ω}. Then cf([ℵ_{ω}]^{ℵ_{0}}, ⊆) = max pcf(A) by Theorem 5.11. But pcf(A) is an interval of regular cardinals of size < ℵ_{4}. Hence if we write max pcf(A) = ℵ_{α}, then α < ω_{4}. Thus

cf([ℵ_{ω}]^{ℵ_{0}}, ⊆) < ℵ_{ω_{4}}.

This result holds even if 2^{ℵ_{0}} is larger than ℵ_{ω_{4}}. It follows now immediately that if 2^{ℵ_{0}} < ℵ_{ω} then ℵ_{ω}^{ℵ_{0}} < ℵ_{ω_{4}}. Shelah emphasizes that the former result (concerning the cofinality of [ℵ_{ω}]^{ℵ_{0}}) is more basic, and hence one should ask questions concerning cofinalities rather than cardinalities, if one wants to get (absolute) answers.

Generalizing this, we have:

7.2 Theorem. If ℵ_{δ} is a singular cardinal such that δ < ℵ_{δ} then

cf([ℵ_{δ}]^{|δ|}, ⊆) < ℵ_{(|δ|^{+4})}.

Proof. Write |δ| = κ. Then κ < ℵ_{δ} and if A is the interval of regular cardinals in (κ, ℵ_{δ}) then |A| ≤ |δ| = κ and A is a progressive set. Theorem 5.11 applies with μ = ℵ_{δ} and it yields

cf([ℵ_{δ}]^{κ}, ⊆) = max pcf(A).

But A is an interval of regular cardinals, and hence |pcf(A)| < |A|^{+4}, by Theorem 7.1. This implies that max pcf(A) < ℵ_{δ+(|A|^{+4})} ≤ ℵ_{|δ|^{+4}}. Hence cf([ℵ_{δ}]^{κ}, ⊆) < ℵ_{(|δ|^{+4})}. ⊣

We are now able to deduce the following application to cardinal arithmetic.

7.3 Theorem. Suppose that δ is a limit ordinal and |δ|^{cf(δ)} < ℵ_{δ}. Then

ℵ_{δ}^{cf(δ)} < ℵ_{(|δ|^{+4})}.

Proof. Since |δ|^{cf(δ)} < ℵ_{δ}, δ < ℵ_{δ}. It follows from the cofinality theorem above that

ℵ_{δ}^{cf(δ)} ≤ |δ|^{cf(δ)} · cf([ℵ_{δ}]^{|δ|}, ⊆) < ℵ_{δ} · ℵ_{(|δ|^{+4})}.  (I.45)
⊣

8. Revised GCH

The generalized continuum hypothesis (G.C.H) saying that 2^{κ} = κ^{+} for every (infinite) cardinal κ is readily seen to be equivalent to the statement that for every two regular cardinals κ < λ we have λ^{κ} = λ. In [13] Shelah considers a “revised power set” operation λ^{[κ]} defined as follows:

λ^{[κ]} = min{|P| | P ⊆ [λ]^{≤κ} and ∀u ∈ [λ]^{κ}∃P_{0} ⊆ P (|P_{0}| < κ ∧ u = ⋃ P_{0})}.

An inductive proof can show that the G.C.H. is equivalent to the statement that for every regular cardinals κ < λ, λ^{[κ]} = λ. The “revised” G.C.H theorem says that for “many” pairs of regular cardinals we have λ^{[κ]} = λ.

8.1 Theorem (Shelah’s Revised G.C.H). If θ is a strong limit uncountable cardinal, then for every λ ≥ θ, for some κ_{0} < θ, for every κ_{0} ≤ κ < θ

λ^{[κ]} = λ.

The proof that we give here is adopted from a later article ([15]) of Shelah, and it relies on two notions that we have to investigate first, pcf_{σ−com}(A) and T_{D}(f).

8.2 Definition. Let λ > θ ≥ σ = cf(σ) be cardinals.

1. We say that P ⊆ [λ]^{≤θ} is a (< σ)-base for [λ]^{≤θ} if every u ∈ [λ]^{≤θ} is the union of fewer than σ members of P. That is, for some P_{0} ⊆ P, |P_{0}| < σ, and u = ⋃ P_{0}.

2. We define λ^{[σ,θ]} = min{|P| | P ⊆ [λ]^{≤θ} is a (< σ) − base for [λ]^{≤θ}}. We have λ^{[σ]} = λ^{[σ,σ]}. In a similar fashion define λ^{[σ,<θ]}. It is the minimal cardinality of a set P ⊆ [λ]^{<θ} so that every u ∈ [λ]^{<θ} is a union of fewer than σ members of P.

3. We say that P ⊆ [λ]^{θ} is (< σ)-cofinal in [λ]^{θ} if every u ∈ [λ]^{θ} is included in the union of fewer than σ members of P. That is, for some P_{0} ⊂ P, |P_{0}| < σ, and u ⊆ ⋃ P_{0}.

4. We define λ^{⟨σ,θ⟩} = min{|P| | P ⊆ [λ]^{θ} is (< σ)-cofinal in [λ]^{θ}}. Define λ^{⟨σ⟩} = λ^{⟨σ,σ⟩}.

For a regular infinite cardinal σ and a set A of regular cardinal define

pcf_{σ−com}(A) = {tcf(ΠA/F) | F is a σ−complete filter over A and tcf(ΠA/F) exists}.

(A filter is σ complete if it is closed under the intersections of less than σ members of the filter.)

Clearly, A ⊆ pcf_{σ−com}(A) ⊆ pcf(A).

Define J_{<λ}^{σ−com}[A] ⊆ P(A) by the formula X ∈ J_{<λ}^{σ−com}[A] iff X ⊆ A and whenever F is a σ-complete filter over A with X ∈ F and such that tcf(ΠA/F) exists, then tcf(ΠA/F) < λ. Equivalently,

J_{<λ}^{σ−com}[A] = {X ⊆ A | pcf_{σ−com}(X) ⊆ λ}.

Clearly, J_{<λ}[A] ⊆ J_{<λ}^{σ−com}[A]

8.3 Lemma. J_{<λ}^{σ−com}[A] is a σ-complete ideal.

Proof. Suppose that X_{i} ∈ J_{<λ}^{σ−com}[A] for every i < σ^{∗} where σ^{∗} < σ. We prove that X = ⋃_{i<σ^{∗}} X_{i} ∈ J_{<λ}^{σ−com}[A]. So let F be a σ-complete filter over A containing X and such that tcf(ΠA/F) = τ exists. We must show that τ < λ. Assume that F is proper (the cofinality of a reduced product by a trivial, that is non-proper, filter is 1). For every i < σ^{∗} consider the filter F + X_{i} (defined as the collection of all subsets of A that contain a set of the form A ∩ X_{i} for A ∈ F). If for some i < σ^{∗}, F_{i} = F + X_{i} is proper, then it is a σ-complete filter containing X_{i} and such that tcf(ΠA/F_{i}) = τ (extending the filter F will not change the cofinality of the existing reduced product). But as X_{i} ∈ J_{<λ}^{σ−com}[A], we get τ < λ.

If, for every i < σ^{∗}, F + X_{i} is trivial, then X \ X_{i} ∈ F. Hence the intersection of these sets which is the empty set is in F, and thus F is trivial. ⊣

8.4 Lemma. Suppose that A is a progressive set of regular cardinals and λ = max pcf(A). Then X ∈ J_{<λ}^{σ−com}[A] iff X is a union of < σ members of J_{<λ}[A]. That is, J_{<λ}^{σ−com}[A] is the σ-completion of J_{<λ}[A].

Proof. The previous lemma implies that any set in the σ-completion of J_{<λ}[A] is in J_{<λ}^{σ−com}[A].

Assume X ∈ J_{<λ}^{σ−com}[A]. Since λ = max pcfA, there are f_{ζ} for ζ < λ that are increasing and cofinal in ΠA/J_{<λ}[A] (Exercise 4.3, or Theorem 4.13). Let J^{com} be the σ-completion of J_{<λ}[A] ∪ (A \ X). If X ∉ J^{com} then J^{com} is a proper σ complete ideal over A containing A \ X, and the same sequence of f_{α}’s demonstrates that tcf(ΠA/J^{com}) = λ. Which contradicts X ∈ J_{<λ}^{σ−com}. Hence X ∈ J^{com}. ⊣

We now strengthen the lemma by removing the assumption that λ = max pcf(A).

8.5 Theorem. Let A be a progressive set of regular cardinals, and σ a regular cardinal. Then J_{<λ}^{σ−com}[A] is the σ-completion of J_{<λ}[A].

Proof. We prove by induction on μ that for every progressive set A of regular cardinals with μ = max pcf(A), for every cardinals λ and σ (regular), J_{<λ}^{σ−com}[A] is the σ-completion of J_{<λ}[A].

We know already that J_{<λ}[A] ⊆ J_{<λ}^{σ−com}[A] and that J_{<λ}^{σ−com} is σ-complete. It remains to prove that any X ∈ J_{<λ}^{σ−com}[A] is a union of less than σ sets from J_{<λ}[A]. If μ < λ then X ∈ J_{<λ}[A] and this case is uninteresting. In case λ ≤ μ, X ∈ J_{<μ}^{σ−com}[A]. So by the previous lemma, X is a union of less than σ sets from J_{<μ}[A]. But the inductive assumption can be applied to each one of these sets, and the lemma follows since σ is regular. ⊣

Another characterization of the ideal J_{<λ}^{σ−com}[A] is provided by the following theorem dealing with the cofinality of product of cardinals under the < relation: f < g iff for every a ∈ dom(f) f(a) < g(a).

We know (Theorem 4.4) that X ∈ J_{<λ}[A] iff cf(ΠX) < λ. For a similar characterization of J_{<λ}^{σ−com} we need the following definition. Let X be a set of regular cardinals with min X ≥ σ. If F ⊆ ΠX, we say that F is (< σ)-cofinal iff for every f ∈ ΠX there is a set F_{0} ⊆ F with |F_{0}| < σ and such that f < sup F_{0}. In other words, the functions formed by taking the supremum of fewer than σ functions from F form a cofinal set in ΠX. The (< σ)-cofinality of ΠX is the smallest cardinality of a (< σ)-cofinal subset.

8.6 Theorem. Suppose that A is a progressive set of regular cardinals, σ ≤ min A is a regular cardinal, and σ ≤ cf(λ). Define

J = {B ⊆ A | B = ∅ or ΠB has (< σ)-cofinality < λ}

Then J = J_{<λ}^{σ−com}[A].

Proof. We first prove that J ⊆ J_{<λ}^{σ−com}. Suppose B ∈ J and let D be a σ-complete filter over A containing B and such that tcf(ΠA/D) exists and is equal to λ′ ≥ λ. This will lead to a contradiction, thereby proving that B ∈ J_{<λ}^{σ−com}. Since tcf(ΠA/D) = λ′, λ′ is a regular cardinal and there is an increasing sequence S in ΠA/D of length λ′ that is cofinal in ΠA/D. By definition of B ∈ J, there is a set F ⊆ ΠB of cardinality < λ that is (< σ)-cofinal. For every f ∈ F there is a function s ∈ S such that f <_{D} s (f is defined on B and s on A, but as B ∈ D, this makes sense). Since λ′ is regular and bigger than |F|, there is a single s ∈ S such that f <_{D} s for every f ∈ F. Since F is (< σ)-cofinal, s <_{D} sup F_{0} for some F_{0} ⊆ F of size < σ. But as D is σ-complete, and f <_{D} s for every f ∈ F_{0}, sup F_{0} ≤_{D} s as well. This is a contradiction, and thus J ⊆ J_{<λ}^{σ−com}[A].

Clearly J_{<λ}[A] ⊆ J (by Theorem 4.4). If we prove that J is σ-complete then J_{<λ}^{σ−com}[A] ⊆ J follows from the previous theorem.

So let σ^{∗} < σ and X_{i} ∈ J for i < σ^{∗} be given. We shall prove that X = ⋃_{i<σ^{∗}} X_{i} ∈ J. For every i < σ^{∗} we have a (< σ)-cofinal set P_{i} ⊆ ΠX_{i} of cardinality < λ. Then P = ⋃_{i<σ^{∗}} P_{i} has cardinality < λ because σ ≤ cf(λ). The domain of each function in P_{i} is X_{i}, but we can extend it arbitrarily on X and then P can be considered as a subset of ΠX. Clearly P is (< σ)-cofinal. ⊣

8.7 Theorem. Suppose that:

1. λ > θ > σ > ℵ_{0} are given, where θ is regular, σ < cf(λ), and 2^{<θ} ≤ λ.

2. For every A ⊆ Reg ∩ λ \ θ, if |A| < θ then A ∈ J_{≤λ}^{σ−com}[A].

Then λ = λ^{[σ,<θ]}.

Proof. Fix χ large enough, and let M ≺ H(χ) be an elementary substructure of cardinality λ and such that λ + 1 ⊂ M. We shall prove the following claim which yields the theorem:

M ∩ [λ]^{<θ} is a (< σ)-base for [λ]^{<θ}.

For this, we need the following lemma.

8.8 Lemma. With the same assumptions of the theorem and on M. Let g : κ → λ and f : κ → λ + 1 be given with κ < θ, f ∈ M, and such that ∀a ∈ κ g(a) ≤ f(a). Then there is a collection Φ ⊆ M of functions from κ to λ such that the following hold:

1. |Φ| < σ.

2. For every p ∈ Φ, g ≤ p ≤ f (that is, for all a ∈ κ, g(a) ≤ p(a) ≤ f(a)).

3. For every a ∈ κ, if g(a) < f(a), then for some p ∈ Φ g(a) ≤ p(a) < f(a).

Proof. Think of f as an “approximation from above” in M to the function g (which is not in M, or else the theorem is trivial). The set Φ is not required to be a member of M, and each function of Φ (if different from f) is a better approximation that lies in M. For each a ∈ κ, if f(a) is not the best approximation, then Φ contains a function that gets a better value at a.

Fix in M a sequence ⟨C_{δ} | δ ≤ λ, δ ∈ lim λ⟩ such that C_{δ} ⊆ δ is unbounded in δ and of order-type cf(δ).

Define the following subsets of κ:

E_{0} = {a < κ | g(a) = f(a)}
E_{1} = {a < κ | g(a) < f(a), f(a) is a successor ordinal}

E_{2} = {a < κ | g(a) < f(a), f(a) ∈ lim and cf(f(a)) < θ}

E_{3} = κ \ (E_{0} ∪ E_{1} ∪ E_{2}).

Since 2^{<θ} ≤ λ, any bounded subset of θ is in M. So each E_{ℓ} is in M. We define h on κ as follows. For a ∈ E_{0}, h(a) = f(a). For a ∈ E_{1}, h(a) + 1 = f(a). For a ∈ κ \ (E_{0} ∪ E_{1}), h(a) = min C_{f(a)} \ g(a).

Obviously h ↾ E_{0} ∪ E_{1} ∈ M. We prove that h ↾ E_{2} ∈ M as well. By definition h ↾ E_{2} is a function in Π_{δ∈E_{2}}C_{f(δ)}. But θ is regular, and since |E_{2}| < θ and cf f(δ) < θ, f ↾ E_{2} is bounded below θ, and hence |Π_{δ∈E_{2}}C_{f(δ)}| ≤ 2^{<θ} ≤ λ.

So Π_{δ∈E_{2}}C_{f(δ)} ⊂ M, and hence h ↾ E_{2} ∈ M.

There is no reason to assume that h ↾ E_{3} is in M, but we shall find a set Φ of size < σ as required by the lemma. Define A = {cff(a) | a ∈ E_{3}}. Then A ⊆ λ + 1 \ θ is a set of regular cardinals of size ≤ κ, and so A ∈ J_{≤λ}^{σ−com}[A]. As σ ≤ cf(λ), there is (by Theorem 8.6) a family F of size ≤ λ that is (< σ)-cofinal in ΠA. Since A ∈ M we can have F ∈ M and F ⊂ M. Since κ < min A and A ⊂ Reg, F yields a family of functions, F′ ⊂ Π_{δ∈E_{3}}C_{f(δ)} = P that is (< σ)-cofinal in P. As h ↾ E_{3} ∈ P, there is a set F_{0} ⊆ F′ of size < σ such that h ↾ E_{3} < sup F_{0}. If e ∈ F_{0}, then e(δ) < f(δ) but e(δ) < g(δ) is possible. So we correct each e ∈ F_{0} and define:

e′(δ) = \begin{cases}e(δ) & if g(δ) ≤ e(δ), \\ f(δ) & otherwise. \end{cases}

Then e′ ∈ M because e, f ∈ M and every subset of κ is in M. The collection {h ↾ (E_{0}∪E_{1}∪E_{2})^{⌢}e′ | e ∈ F_{0}} is as required, and the lemma is proved. ⊣

We continue now with the proof of the theorem. So let u ∈ [λ]^{<θ} be given and we shall find a subset of M ∩ [λ]^{<θ} of cardinality < σ whose union is u. Let κ = |u| < θ be the cardinality of u and take an enumeration g : κ → u. We shall define by induction on n ∈ ω a set Φ_{n} of functions from κ to λ such that the following holds.

1. Let f_{0} : κ → λ + 1 be defined by f_{0}(a) = λ. Then Φ_{0} = {f_{0}}.

2. For every n, Φ_{n} ⊂ M and |Φ_{n}| < σ. If f ∈ Φ_{n} then g ≤ f.

3. For every f ∈ Φ_{n} and a ∈ κ such that g(a) < f(a) there exists p ∈ Φ_{n+1} such that g(a) ≤ p(a) < f(a).

This is easily obtained by the lemma.

Let Φ = ⋃_{n<ω} Φ_{n}. Then |Φ| < σ. For any f ∈ Φ, the set

E(f) = {f(a) | a ∈ κ and f(a) = g(a)}

is in M (because f is, and any subset of κ). We have u = ∪{E(f) | f ∈ Φ} because if x ∈ u then x = g(a) for some a ∈ κ, and g(a) < f_{0}(a). There exists a sequence f_{n} ∈ Φ_{n} so that if g(a) < f_{n}(a) then f_{n+1}(a) < f_{n}(a). And necessarily for some n g(a) = f_{n}(a). So a ∈ E(f_{n}). This ends the proof of Theorem 8.7. ⊣

The following corollary shows that the theorem above can also be applied when cf(θ) < σ.

8.9 Corollary. Suppose that:

1. λ > θ > σ = cf(σ) > ℵ_{0} are given, where cf(θ) < σ < cf(λ), and 2^{<θ} ≤ λ.

2. For every A ⊆ Reg ∩ λ + 1 \ θ, if |A| < θ then A ∈ J_{≤λ}^{σ−com}[A].

Then λ = λ^{[σ,<θ]}.

Proof Fix a sequence ⟨θ_{i} | i < cf(θ)⟩ of regular cardinals that is cofinal in θ and such that σ < θ_{i} for all i. We claim for every i < cf(θ) that the assumptions of Theorem 8.7 hold for λ > θ_{i} > σ, and hence λ = λ^{[σ,<θ_{i}]} follows. But this clearly implies that λ = λ^{[σ,<θ]}.

For the claim, we must prove that if θ′ < θ is regular then for every A ⊆ Reg ∩ λ + 1 \ θ′, if |A| < θ′ then A ∈ J_{≤λ}^{σ−com}[A]. Suppose for a contradiction that this is not the case, and for some σ-complete filter D over A ⊂ Reg ∩ λ + 1 \ θ′ we have tcf(ΠA/D) = λ_{0} > λ. We may assume that A ⊂ θ, that is, we may assume that A ∩ θ ∈ D, or else A \ θ is not D-null and then it can be added to D without changing the true cofinality of the reduced product, which contradicts the assumptions of the theorem.

If for every i < cfθ A \ θ_{i} ∈ D, then by the σ-completeness of D and the fact that cf(θ) < σ, we get a contradiction. So for some i A∩θ_{i} is not D-null. But then D′ = D+A∩θ_{i} is σ-complete and it follows that the true cofinality of ΠA/D′ remains λ_{0}. Yet this is impossible since (θ_{i})^{|A∩θ_{i}|} ≤ 2^{<θ} ≤ λ.

8.1. T_{D}(f)

Let J be an ideal over a cardinal κ. We recall some definitions. The collection of positive sets is denoted J^{+}. The corresponding dual filter is denoted J^{∗}. If R is a relation, if f and g are functions defined on κ, then we defined f R_{J} g if and only if {i ∈ κ | f(i) R g(i)} ∈ J^{∗}. We also write f R_{J^{+}} g for {i ∈ κ | f(i) R g(i)} ∉ J. That is, f(i) R g(i) occurs positively.

Thus f ≠_{J} g means that {i ∈ κ | f(i) = g(i)} ∈ J, and f =_{J^{+}} g means that ¬f ≠_{J} g.

Let κ be a cardinal and D a filter over κ. Consider the <_{D} ordering on Ord^{κ}. For f ∈ Ord^{κ}, Π_{i<κ}f(i) is denoted Πf, and Π_{i<κ}f(i)/D is denoted Πf/D. (We consider only functions f such that f(i) > 0 for i ∈ κ).

For F ⊂ Πf, we say that F is a set of pairwise “D-different” functions, if for every distinct f_{1}, f_{2} ∈ F we have f_{1} ≠_{D} f_{2}. For any f ∈ Ord^{κ}, define

T_{D}(f) = sup{|F| | F ⊆ Πf is a set of pairwise D-different functions}

(This is called T_{D}^{0}.)

8.10 Theorem. Suppose that D is a filter over κ, f ∈ Ord^{κ} and T_{D}(f) = λ. If 2^{κ} < λ then the supremum in the definition of T_{D}(f) is attained. In fact, if 2^{κ} < λ and F ⊂ Πf is any maximal family of pairwise D-different functions, then |F| = λ. Thus T_{D}(f) can be redefined in case 2^{κ} < λ as the cardinality of any maximal set of pairwise D-different functions below f.

Proof. Suppose on the contrary that F ⊂ Πf is maximal but |F| < λ. Let G ⊂ Πf be a collection of pairwise D-different functions such that

|G| > |F| + 2^{κ}.  (I.46)

For every g ∈ G we can find f = f(g) ∈ F such that X(g) = {i ∈ κ | f(i) = g(i)} is not D-null. As (I.46), there are two distinct functions g_{1} and g_{2} in G such that f(g_{1}) = f(g_{2}) and X(g_{1}) = X(g_{2}). But this implies that g_{1} and g_{2} agree on a non-null set which is a contradiction to the assumption that the functions in G are pairwise D-different. ⊣

An obvious observation which turns out to be crucial is the following.

8.11 Lemma. If tcf(Πf/D) exists, then T_{D}(f) ≥ tcf(Πf/D).

Proof. If tcf(Πf/D) = λ, then there exists a <_{D} increasing sequence of length λ, and hence a set of cardinality λ of pairwise D-different functions.

⊣

Assume now that σ is a regular uncountable cardinal, and D is a σcomplete filter over κ. Then Πf/D is well-founded. This is used in the following.

8.12 Lemma. Suppose that σ is a regular uncountable cardinal and D is a σ-complete filter over κ. Suppose f ∈ Ord^{κ} and T_{D}(f) ≥ λ where 2^{κ} < λ. Then for some g ≤_{D} f we have T_{D}(g) = λ.

Proof. Let g ≤_{D} f be minimal in the ≤_{D} ordering such that T_{D}(g) ≥ λ. Suppose for a contradiction that T_{D}(g) > λ. There is a set {f_{α} | α < λ^{+}} of pairwise D-different functions in Πg. For α < λ^{+} define

u_{α} = {β < λ^{+} | f_{β} <_{D} f_{α}}.

If, for some α, |u_{α}| ≥ λ, then u_{α} proves that T_{D}(f_{α}) ≥ λ in contradiction to the minimality of g. Hence |u_{α}| < λ for every α < λ^{+}.

But now we can apply the Free Mapping theorem of Hajnal and obtain F ⊆ λ^{+}, of cardinality λ^{+} such that α ∉ u_{β} (and β ∉ u_{α}) for every α ≠ β in F. (The argument in short is the following. First, we can find λ_{0} < λ such that |u_{α}| = λ_{0} for unboundedly many α < λ^{+}. Re-enumerating, we may assume |u_{α}| = λ_{0} for every α. On those α < λ^{+} with cofinality λ_{0}^{+} we bound u_{α} ∩ α in α, and use Fodor’s lemma.)

Hence there are f_{α} ∈ Ord^{κ} for α < (2^{κ})^{+} such that f_{α} ≰_{D} f_{β} whenever α ≠ β. But this is impossible in view of the Erdos-Rado partition theorem (2^{κ})^{+} → (κ^{+})_{κ}^{2}. Indeed, for α < β < κ^{+} define h(α, β) as some i < κ such that f_{β}(i) < f_{α}(i). Then h has no infinite homogeneous set, which contradicts the Erdos-Rado theorem. Thus T_{D}(g) = λ.

Observe that since 2^{κ} < λ, L = {a ∈ κ | g(a) ∈ lim} is not null in D, and hence we may assume without loss of generality that it is in D. (Or else let h <_{D} g be such that g(a) = h(a) + 1 for every a ∉ L, and h(a) = g(a) on L. Let f_{α}, for α < λ, exemplify T_{D}(g) = λ. By minimality of g, there are λ functions f_{α} that are equal to h on a positive subset of κ \ L. Since 2^{κ} < λ, two such functions are equal on a positive set, which is impossible.) ⊣

The following is one of the two main arguments used in the proof of the revised GCH theorem.

8.13 Theorem. Assume that λ > θ ≥ σ = cf(σ) > κ are cardinals such that:

1. θ^{κ} = θ.

2. If τ < σ then τ^{κ} < σ.

3. J is an ideal on κ.

4. There is a sequence λ̄ = ⟨λ_{i} | i < κ⟩, λ_{i} < λ, such that

(a) T_{J}(λ̄) = λ,

(b) λ_{i}^{⟨σ,θ⟩} = λ_{i} for every i < κ.

Then λ^{⟨σ,θ⟩} = λ. (If we also assume 2^{θ} ≤ λ, then evidently λ^{[σ,θ]} = λ.)

Proof. In the proof, we actually weaken the requirement T_{J}(λ̄) = λ to the following conjunction.

1. There are f_{α} ∈ Π_{i<κ}λ_{i}, for α < λ, such that α ≠ β ⟶ f_{α} ≠_{J} f_{β},

2. There are g_{α} ∈ Π_{i<κ}λ_{i}, for α < λ, such that for every f ∈ Π_{i<κ}λ_{i} there exists α < κ with f =_{J^{+}} g_{α}.

Fix a sequence of pairwise D-different functions f_{α} ∈ Π_{i<κ}λ_{i}, for α < λ, as in 1 above.

For every i < κ we assume λ_{i}^{⟨σ,θ⟩} = λ_{i}, so there exists a family P_{i} ⊆ [λ_{i}]^{θ} of cardinality λ_{i} that is (< σ)-cofinal in [λ_{i}]^{θ}.

Since |P_{i}| = λ_{i}, Π_{i∈κ}P_{i} is isomorphic to Π_{i<κ}λ_{i}. So there is (by 2 above) a family {g_{α} | α < λ} ⊂ Π_{i∈κ}P_{i} such that for every g ∈ Π_{i∈κ}P_{i} there is α < λ with g =_{J^{+}} g_{α}.

For every g ∈ Π_{i∈κ}P_{i} and A ∈ J^{+}, let g|` A be the restriction of g to A, and Πg ↾ A is Π_{i∈A}g(i). We define

F(g|` A) = {ζ ∈ λ | ∀i ∈ A f_{ζ}(i) ∈ g(i)}.

In other words, F(g ↾ A) is the set of ζ ∈ λ such that f_{ζ} ↾ A ∈ Πg ↾ A. Observe that if A ⊂ B ⊆ κ, then F(g ↾ A) ⊇ F(g ↾ B).

8.14 Claim. For every g ∈ Π_{i∈κ}P_{i} and A ∈ J^{+}, |F(g ↾ A)| ≤ θ.

Since g(i) ∈ P_{i} ⊆ [λ_{i}]^{θ}, |Π_{i∈A}g(i)| ≤ θ^{κ} = θ. So, if |F(g ↾ A)| > θ, we would have ζ ≠ ζ′ in λ with f_{ζ} ↾ A = f_{ζ′} ↾ A. But as A ∈ J^{+}, this contradicts f_{ζ} ≠_{J} f_{ζ′} and proves the claim.

8.15 Claim. Every u ∈ [λ]^{θ} is included in a union of fewer than σ sets of the form F(g_{α} ↾ A). That is, the collection F = {F(g_{α} ↾ A) | α < λ, A ∈ J^{+}} is (< σ)-cofinal in [λ]^{θ}.

Observe first that as |F| ≤ λ · 2^{κ} = λ, this claim proves the theorem. Given u ∈ [λ]^{θ} define for every i < κ

u_{i} = {f_{α}(i) | α ∈ u}.

Then u_{i} ∈ [λ_{i}]^{≤θ} and hence there is P_{i}^{u} ⊂ P_{i} with |P_{i}^{u}| < σ and such that u_{i} ⊆ ⋃ P_{i}^{u}. Since σ is regular, some τ < σ bounds all the cardinals σ_{i} = |P_{i}^{u}|, and, as τ^{κ} < σ, we have that |Π_{i∈κ}σ_{i}| < σ. So

G = Π_{i∈κ}P_{i}^{u}

is a subset of Π_{i∈κ}P_{i} of size < σ. The following two lemmas finish the proof of our claim.

8.16 Lemma. u ⊆ ⋃{F(g) | g ∈ G}.

Proof. If ζ ∈ u then f_{ζ}(i) ∈ u_{i} for every i ∈ κ. Thus f_{ζ}(i) ∈ ⋃ P_{i}^{u} for every i < κ, and we can find g ∈ G such that f_{ζ}(i) ∈ g(i) for all i < κ. Namely, ζ ∈ F(g) as required.

8.17 Lemma. For every g ∈ G there is α < λ and A ∈ J^{+} such that F(g) ⊆ F(g_{α} ↾ A). Thus as |G| < σ, u is contained in the union of fewer than σ sets of the form F(g_{α} ↾ A).

Proof. For every g ∈ G there is some α < λ such that g =_{J^{+}} g_{α}. Which means that for some A ∈ J^{+}, g ↾ A = g_{α} ↾ A. We already observed that F(g) ⊆ F(g ↾ A), and hence the lemma follows. So Theorem 8.13 is proved. ⊣

We shall use a variant of Theorem 8.13 in which the assumption θ^{κ} = θ is replaced with the assumption that θ is a strong limit cardinal with cf(θ) < σ.

8.18 Corollary. Assume that λ > θ > σ = cf(σ) > κ are cardinals such that:

1. θ is a strong limit cardinal and cf(θ) < σ.

2. If τ < σ then τ^{κ} < σ.

3. J is an ideal on κ.

4. There is a sequence λ̄ = ⟨λ_{i} | i < κ⟩, λ_{i} < λ, such that

(a) T_{J}(λ̄) = λ,

(b) λ_{i}^{⟨σ,θ⟩} = λ_{i} for every i < κ.

Then λ^{⟨σ,θ⟩} = λ.

Proof. Fix a cofinal in θ sequence ⟨θ_{ϵ} | ϵ < cf(θ)⟩ such that θ_{ϵ}^{κ} = θ_{ϵ} and σ < θ_{ϵ} for every ϵ. (Start with any cofinal sequence, and replace θ_{ϵ} with (θ_{ϵ})^{κ} if necessary.)

Consider any ϵ < cf(θ). Observe that for every i < κ we have λ_{i} = λ_{i}^{[σ,θ_{ϵ}]}. This follows immediately from the assumptions that θ is a strong limit cardinal with cf(θ) < σ, and such that λ_{i} = λ_{i}^{⟨σ,θ⟩}. Hence Theorem 8.13 is applicable (with θ_{ϵ} in the role of θ) and λ = λ^{⟨σ,θ_{ϵ}⟩}. Since this holds for every ϵ < cf(θ), we get λ = λ^{⟨σ,θ⟩}. ⊣

8.2. Proof of the revised GCH

We prove the following form of the revised G.C.H.

8.19 Theorem. If θ is a strong limit singular cardinal, then for every λ ≥ θ, for some σ < θ,

λ = λ^{[σ,θ]}.

Proof. Let σ_{0} = (cfθ)^{+}.

The theorem is proved by induction on λ. For λ = θ, λ = λ^{[σ_{0},θ]}, and the family of all bounded subsets of θ is an evidence for this equality. (Any subset of θ is a union of cf(θ) bounded subsets.)

We note for clarification that the induction can easily proceed in case cfλ ≠ cfθ, and so we may assume that cfλ = cfθ. However, we shall not make any use of this in the following proof.

Case 1: For every A ⊆ Reg∩λ\θ, if |A| < θ then A ∈ J_{≤λ}^{σ_{0}−com}[A].

In this case the inductive assumption is dispensable and Corollary 8.9 yields immediately that λ = λ^{[σ_{0},<θ]}.

Case 2: Not Case 1:

For some A ⊆ Reg ∩ λ \ θ with |A| < θ, A ∉ J_{≤λ}^{σ_{0}−com}[A].

Hence there is a σ_{0}-complete filter D over A, where |A| = κ < θ, such that tcf(ΠA/D) > λ. Say f : κ → A enumerates A. By Lemma 8.11, T_{D}(f) ≥ tcf(ΠA/D) > λ. By Lemma 8.12, there exists g ≤ f defined over κ so that T_{D}(g) = λ.

We claim that {i < κ | g(i) ≥ θ} ∈ D. If not, then {i < κ | g(i) < θ} is D-positive. But since cf(θ) < σ_{0} and D is σ_{0}-complete, there is θ′ < θ so that X = {i < κ | g(i) < θ′} is D-positive. Hence tcf(Πg ↾ X) = λ. But this is impossible since θ is strong limit and 2^{θ′} < θ.

So we can assume now that for every i < κ, g(i) ≥ θ. Hence by the inductive assumption there is σ(i) < θ so that

g(i) = g(i)^{[σ(i),θ]}.  (I.47)

Since cf(θ) < σ_{0} and D is σ_{0}-complete, there is σ, such that κ, σ_{0} < σ < θ and {i < κ | σ(i) < σ} is D-positive. For notational simplicity we assume that σ(i) < σ for all i < κ. Take σ_{1} = (σ^{κ})^{+}. Now apply Corollary 8.18 to λ > θ > σ_{1} > κ. This yields λ^{⟨σ_{1},θ⟩} = λ, but since θ is a strong limit cardinal with cf(θ) < σ_{1} we obtain λ^{[σ_{1},θ]} = λ.

⊣

We note that Theorem 8.1 did not make the assumption that θ is a singular cardinal, but Theorem 8.19 did. To see how 8.1 can be derived from 8.19, we argue as follow in case θ is a regular uncountable strong limit cardinal. There is a stationary set S ⊂ θ of strong limit singular cardinals. So if λ ≥ θ, then Theorem 8.19 applies to each θ′ ∈ S, and λ = λ^{[σ(θ′),θ′]} follows for some σ(θ′) < θ′. By Fodor’s theorem, there is fixed σ < θ such that σ = σ(θ′) for a stationary set of cardinals θ′ ∈ S. This gives λ = λ^{[σ,<θ]}. So obviously for every σ ≤ κ < θ, we get λ = λ^{[κ]}.

8.3. Applications of the revised GCH

Two applications are given here, the first to the existence of diamond sequences and the second to cellularity of Boolean algebras. Both use the following immediate corollary of the revised GCH theorem.

If α ≥ ℶ_{ω} then for some regular uncountable σ < ℶ_{ω} there is a collection P_{α} ⊆ [α]^{σ} where |P_{α}| = |α| and such that for each x ∈ [α]^{σ}, for some p ∈ P_{α}, p ⊆ x.

(I.48)

To begin this section we recall that for a stationary set S ⊆ λ^{+}, ◇_{λ^{+}}^{−}(S) is the following diamond statement: there is a sequence ⟨S_{α} | α ∈ S⟩ where S_{α} ⊂ P(α), |S_{α}| ≤ λ, and for every A ⊆ λ^{+}, {α ∈ S | A ∩ α ∈ S_{α}} is a stationary set.

A beautiful argument of Gregory proves that if 2^{λ} = λ^{+} and λ^{ℵ_{0}} = λ, then ◇_{λ^{+}}^{−}(S_{ω}^{λ^{+}}) where S_{ω}^{λ^{+}} is the stationary set of ordinals in λ^{+} of cofinality ω. (There are stronger formulations, but this suffices to demonstrate the application we have in mind.) To prove this theorem, let {X_{i} | i < λ^{+}} be an enumeration of all bounded subsets of λ^{+}. For every α < λ^{+} define S_{α} as the collection of all subsets of α that are formed by taking countable unions of sets from {X_{i} | i < α}. Since |α|^{ℵ_{0}} ≤ λ, |S_{α}| ≤ λ. Now, if A ⊆ λ^{+} is given, then the set, C, of α < λ^{+} for which ∀ζ < α ∃i < α (A ∩ ζ = X_{i}) is closed unbounded in λ^{+}. If α ∈ C and cf(α) = ω then A ∩ α ∈ S_{α}.

The revised GCH enables in many cases a stronger theorem in which λ^{ℵ_{0}} = λ is not required.

8.20 Theorem. If λ ≥ ℶ_{ω} and 2^{λ} = λ^{+}, then ◇_{λ^{+}}^{−} holds.

Proof. As before, let {X_{i} | i < λ^{+}} enumerate all bounded subsets of λ^{+}. ℶ_{ω} is the first strong limit cardinal, and the revised GCH theorem applies to λ ≥ ℶ_{ω}. So there is σ < ℶ_{ω} such that (I.48) holds for some family P ⊆ [λ]^{σ}.

For every α in the interval [λ, λ^{+}), |α| = λ and hence P can be transformed into a family P_{α} ⊂ [α]^{σ} such that (I.48) holds (same σ for all α’s). Now we define S_{α} as the collection of all subsets of α obtained as unions of the form ⋃{X_{i} | i ∈ B} where B ∈ P_{α}. So |S_{α}| ≤ λ.

The argument to prove that ⟨S_{i} | i < λ^{+}⟩ is a diamond sequence is now familiar. Let A ⊆ λ^{+} be any set. There is a closed unbounded C ⊂ λ^{+} as before so that for α ∈ C and ζ < α there is i < α such that A∩ζ = X_{i}. Now pick any α ∈ C such that cf(α) = σ. Pick an increasing sequence ⟨α_{ϵ} | ϵ < σ⟩ cofinal in α, and for each ϵ < κ find i(ϵ) < α such that A ∩ α_{ϵ} = X_{i(ϵ)}. Define u = {i(ϵ) | ϵ < σ}. Observe that if K ⊆ σ is any unbounded subset of σ then ⋃{X_{i(ϵ)} | ϵ ∈ K} = A ∩ α. For some B ∈ P_{α}, i(ϵ) ∈ B for unboundedly many ϵ < σ. Hence A ∩ α = ⋃{X_{i} | i ∈ B} ∈ S_{α}. ⊣

8.21 Definition. A subset X of a Boolean algebra is μ-linked if there is a function h : X → μ such that x ∧ y ≠ 0_{B} whenever h(x) = h(y).

Our aim is to prove the following theorem from [14]. (For background and motivation and additional results consult [14] and [5]).

8.22 Theorem. Assume that μ = μ^{<ℶ_{ω}}. If B is a c.c.c. Boolean algebra of cardinality ≤ 2^{μ}, then B is μ-linked.

The proof which follows is an example of an induction that relies on the revised GCH. Since B satisfies the countable chain condition, its completion has cardinality ≤ |B|^{ℵ_{0}} ≤ 2^{μ}, and so we can assume that B is a complete Boolean algebra (and when we prove that it is μ-linked then the original algebra which is embedded in its completion is also μ-linked).

We prove by induction on λ, a cardinal such that μ ≤ λ ≤ 2^{μ}, that any subset of B of cardinality λ is μ directed. This is obvious for λ = μ, or when cf(λ) ≤ μ (and the inductive claim holds for smaller cardinals), and so we may assume that cf(λ) > μ. There are several ingredients in the proof of this theorem, and so it is postponed until the required preparations are made.

8.23 Definition. Let C be a Boolean algebra, and D ⊆ C a subalgebra. For any x ∈ C let F_{x} = {d ∈ D | x ≤ d} be the filter generated by x. For a cardinal θ the following property is denoted (∗∗)_{θ} (for the pair D and C):

(∗∗)_{θ} For every x ∈ C there is F ⊆ F_{x} of cardinality ≤ θ and such that for every b ∈ F_{x} there is a ∈ F such that a ≤ b.

In other words, F_{x} is generated by a subset of cardinality ≤ θ.

8.24 Lemma. Let θ, μ, and κ be cardinals such that θ, μ ≤ κ. Suppose that C is a Boolean algebra with a decomposition C = ⋃_{α<κ} C_{α}, where the sequence of Boolean subalgebras C_{α} is increasing and continuous (for limit δ, C_{δ} = ⋃_{i<δ} C_{i}). Assume the following:

1. C_{0} = ∅.

2. Each C_{α} is μ-linked.

3. Property (∗∗)_{θ} holds for each of the pairs C_{α}, C.

Let χ be a large enough cardinal and consider the structure H_{χ} (with some well ordering of its universe, and with C and its decomposition as constants). Suppose that M_{1} and M_{2} are two elementary substructures of H_{χ} that are isomorphic with an isomorphism g : M_{1} → M_{2} that is the identity on κ ∩ M_{1} ∩ M_{2}. Suppose in addition that θ ⊂ M_{1} ∩ M_{2}, and that M_{1} ∩ μ = M_{2} ∩ μ.

Then for every x ∈ M_{1} ∩ C,

x ∧ g(x) ≠ 0_{C}.

Proof. The rank of an element c ∈ C is the least ordinal τ such that c ∈ C_{τ}. Since C_{0} = ∅, the rank of c is a successor ordinal (below κ) such that c ∈ C_{α+1} \ C_{α}. Take x ∈ M_{1} of minimal rank α + 1 such that x ∧ g(x) = 0_{C} and we shall obtain a contradiction.

Case 1. α ∈ M_{1} ∩ M_{2}. So g(α) = α. Let h : C_{α+1} → μ be the least function (in the well-ordering of H_{χ}) given by the assumption that C_{α+1} is μ-linked. So h ∈ M_{1} ∩ M_{2}, and since h is definable from α we have g(h) = h (as g(α) = α). Say h(x) = η ∈ μ. As M_{1} ∩ μ = M_{2} ∩ μ, we have g(h(x)) = g(η) = η. But g(h(x)) = g(h)(g(x)) = h(g(x)). So h(g(x)) = η, and hence h(x) = h(g(x)) which implies that x and g(x) have non-zero meet in C.

Case 2. α ∈ M_{1} \ M_{2}, and hence α ≠ g(α). Suppose that g(α) < α (case g(α) > α is symmetric). Say g(x) = y, and g(α) = β. Then β + 1 is the rank of y. Let α_{1} ≤ α be the least ordinal in M_{1} that is strictly above β. Since β + 1 ≤ α_{1}, y ∈ C_{α_{1}}. Property (∗∗)_{θ} of the pair C_{α_{1}} and C implies the existence of F ⊆ F_{x} of cardinality ≤ θ that generates F_{x}. As x and y are disjoint, the complement, −y, of y is in F_{x} and hence there is a ∈ F that is disjoint from y. Since α_{1} and x are in M_{1}, we have F_{x} and F in M_{1} as well. But as θ is included in M_{1}, F ⊂ M_{1} and hence a ∈ M_{1} follows. The rank of a is α_{2} + 1 ≤ α_{1}. The minimality of α_{1} implies that α_{2} < β (equality if impossible because β is not in M_{1}). But now we can apply a similar argument to F_{y} and discover b ∈ C_{β} ∩ M_{2} that is disjoint to a. Say u ∈ M_{1} is such that g(u) = b. Then u ∈ C_{α} and hence x_{0} = u ∧ a is in C_{α}. Since b ∈ F_{y}, u ∈ F_{x}, and hence x_{0} is in F_{x} too. In particular, x_{0} ≠ 0_{C}. But g(x_{0}) = b ∧ g(a) and x_{0} is disjoint to b ∧ g(a) because already a is disjoint to b. So x_{0} is disjoint to g(x_{0}), in contradiction to the minimality of the rank of x. ⊣

Here is a lemma which is an immediate consequence of the useful Engelking and Karlowicz theorem [3]; we state it for reference and will return to its proof later on.

8.25 Lemma. If μ^{θ} = μ then there is a map τ : [2^{μ}]^{θ} → μ such that if τ(M_{1}) = τ(M_{2}) then M_{1} and M_{2} have the same order-type (as subsets of the ordinal 2^{μ}) and the order isomorphism g : M_{1} → M_{2} is the identity on M_{1} ∩ M_{2}.

8.26 Corollary. Suppose that θ < μ < κ ≤ 2^{μ} are cardinals such that μ^{θ} = μ. Let C be a Boolean algebra of cardinality ≤ 2^{μ}, and suppose that C = ⋃_{α<κ} C_{α} where the C_{α} form an increasing and continuous sequence of subalgebras such that: C_{0} = ∅, each C_{α} is μ-linked, and (∗∗)_{θ} holds for each pair C_{α}, C. Then C is μ-linked.

Proof. Let χ be large enough and H_{χ} the structure of set of cardinality hereditarily less than χ, with a well-ordering of the universe and C as a constant. For every a ∈ C find M(a) ≺ H_{χ} of cardinality θ and such that θ ⊂ M(a). With each M = M(a) we associate the following three parameters.

1. M ∩ μ ∈ [μ]^{θ}. So there are μ such parameters.

2. τ(M ∩ 2^{μ}), where τ : [2^{μ}]^{θ} → μ is the map from the lemma above.

3. The isomorphism type of M(a) (with a as a parameter). Since 2^{θ} ≤ μ there are ≤ μ such types.

The map taking a ∈ C to the three parameters associated with M(a) proves that C is μ-linked. For if M(a) and M(b) have the same parameters then a ∧ b ≠ 0_{C} by the following argument. Let g : M(a) → M(b) be the isomorphism given by item 3. Then g(a) = b, and we plan to apply Lemma 8.24. This is possible because (1) τ(M(a) ∩ 2^{μ}) = τ(M(b) ∩ 2^{μ}) implies that g is the identity on 2^{μ} ∩ M(a) ∩ M(b), (2) θ ⊂ M(a) ∩ M(b) by assumption, and (3) M(a) ∩ μ = M(b) ∩ μ because this is the first of the three parameters. ⊣

Recall that λ ≤ 2^{μ}, B is a complete c.c.c. Boolean algebra of cardinality ≤ 2^{μ}, and every subset of B of cardinality < λ is μ-linked. Our aim is to prove that any X ⊆ B of cardinality λ is μ-linked. We intend to use Corollary 8.26, and we must find C ⊆ B with X ⊆ C and such that the premises of 8.26 hold.

For every α such that ℶ_{ω} ≤ α < λ we have a regular uncountable cardinal σ(α) < ℶ_{ω} and a family P_{α} ⊆ [α]^{σ(α)} such that (I.48) holds. Since cf(λ) ≠ ω (in fact cf(λ) > μ) there is an unbounded set E ⊂ λ such that for some fixed σ we have σ = σ(α) for every α ∈ E. The symbols E and σ retain this meaning throughout the proof. We define θ = 2^{<σ}.

8.27 Lemma. Let χ > 2^{μ} be large enough. Suppose that M_{i} ≺ H_{χ}, for i < δ, are such that:

1. cf(δ) > σ.

2. B, E ∈ M_{0} and ℶ_{ω} ⊂ M_{0}.

3. M_{i} ⊂ M_{j} for i < j and M_{i} ∈ M_{i+1}.

4. |M_{i}| < λ, and M_{i} ∩ λ ∈ λ.

Then for M = ⋃_{i<δ} M_{i} and B_{0} = B ∩M, (∗∗)_{2^{<σ}} holds for the pair B_{0} and B.

Proof. Given x ∈ B consider F_{x} ⊂ B_{0}, the filter of members of B_{0} that are greater than x. We want to find F ⊆ F_{x} of cardinality ≤ θ = 2^{<σ} that generates F_{x}. We choose a_{ζ} ∈ F_{x} for ζ < σ by the following inductive procedure. Suppose that A_{ζ} = {a_{ϵ} | ϵ < ζ} is already chosen. Let G_{ζ} = {∧Z | Z ⊆ A_{ζ} and Z ∈ M}. So G_{ζ} is the collection of all elements of B that can be formed by taking meets of subsets of A_{ζ} that happen to be in M. Clearly A_{ζ} ⊆ G_{ζ} ⊆ F_{x}. Since |A_{ζ}| < σ, |G_{ζ}| ≤ 2^{<σ}. If there exists a ∈ F_{x} not covered by any b ∈ G_{ζ}, then let a_{ζ} be such a. If there is no such a, then the procedure stops and F = G_{ζ} is as required. We shall prove that the construction cannot proceed for every ζ < σ. Suppose it does, and consider A = {a_{ζ} | ζ < σ}. Since cf(δ) > σ there is i < δ with A ⊂ M_{i}. As |M_{i}| < λ there is, already in M_{i+1} an ordinal α ∈ E such that |M_{i}| < α. So α + 1 ⊂ M_{i+1} and hence also P_{α} ⊂ M_{i+1}. Viewing the universe of M_{i} as a copy of an ordinal < α, the set A is a subset of α of cardinality σ, and we have some p ∈ P_{α} such that p ⊆ A. Since ℶ_{ω} ⊂ M_{i+1}, each subset of p is also in M_{i+1}. It follows that for every a_{ζ} ∈ p, A_{ζ} ∩ p ∈ M and hence a_{ζ} ≱ ∧(A_{ζ} ∩p). Thus ∧(A_{ζ} ∩p)−a_{ζ} ≠ 0_{B} is a sequence of σ pairwise disjoint members of B, which contradicts the c.c.c. since σ is uncountable. ⊣

We can complete now the proof of Theorem 8.22. We are assuming that λ ≤ 2^{μ}, cf(λ) > μ, μ^{<ℶ_{ω}} = μ, and every subset of B of cardinality smaller than λ is μ-linked. A set X ⊆ B of cardinality λ is given, which we want to show that is μ-linked. Pick χ large enough and define M_{i} ≺ H_{χ}, for i < cf(λ) = κ, such that

1. M_{i} is increasing and continuous with i. |M_{i}| < λ, and λ ∩ M_{i} ∈ λ.

2. X ∈ M_{0}, μ + 1 ⊂ M_{0}, and X ⊂ M = ⋃_{i<κ} M_{i}.

We shall prove that B ∩ M is μ-linked, and hence that X is μ-linked. For any set R of ordinals, let nacc(R) denotes those α ∈ R that are not accumulation points of R (for some β < α R ∩ (β, α) = ∅).

Let R ⊂ κ be a closed unbounded set such that cf(α) > σ for every α ∈ nacc(R). Then, for δ ∈ nacc(R), Lemma 8.27 applies to the sequence ⟨M_{i} | i < δ⟩ and hence the pair B ∩ M_{δ}, B satisfies (∗∗)_{θ} (θ = 2^{<σ}). But, then it follows that (∗∗)_{θ} holds for every δ ∈ R for the pair B ∩ M_{δ}, B. Because if cf(δ) > σ then the lemma applies, and if cf(δ) ≤ σ then δ is a limit of ≤ σ non-accumulation points of R, and hence (∗∗)_{θ} holds for B∩M_{δ} by accumulating ≤ σ sets, each of cardinality ≤ θ.

Now let ⟨ρ_{i} | i < κ⟩ be an increasing and continuous enumeration of R, and define C_{i} = B ∩ M_{ρ_{i}}, C = B ∩ M. Then Corollary 8.26 applies with θ = 2^{<σ} and yields that B ∩ M is μ-linked. This proves Theorem 8.22.

For completeness we review the theorem of Engelking and Karlowicz that was used in the proof.

8.28 Theorem ([3]). Assume that θ and μ are cardinals such that μ^{θ} = μ. Then there are functions f_{ξ} : 2^{μ} → μ, for ξ < μ, such that if A ⊂ 2^{μ}, |A| ≤ θ, and f : A → μ, then there is ξ < μ such that f ⊂ f_{ξ}.

Proof. It is convenient for the proof to see 2^{μ} as the set of functions from μ to 2. A “template” is a triple (D, S, F) where D ∈ [μ]^{θ}, S ⊂ 2^{D} and |S| ≤ θ (S is a set of functions from D to 2), and F : S → μ. The number of possible templates is μ.

For any template T = (D, S, F) we define f_{T} on 2^{μ}. If α ∈ 2^{μ} and α ↾ D ∈ S, then we define f_{T} (α) = F (α ↾ D) (if α ∉ 2^{μ} then f_{T} (α) is any value).

Given any A ⊂ 2^{μ}, |A| ≤ θ, and f : A → μ, Find D ∈ [μ]^{θ} such that α_{1} ↾ D ≠ α_{2} ↾ D whenever α_{1} ≠ α_{2} are in A. S = {a ↾ D | a ∈ A}. For every s ∈ S there is a unique a ∈ A such that s = a ↾ D and we define F (s) = f(a). Then f ⊂ f_{T}. ⊣

We can prove now Lemma 8.25. Clearly the map assigning to each X ∈ [2^{μ}]^{θ} its order-type (in θ^{+}) ensures that two sets are isomorphic if they have the same value. The problem is to ensure that two isomorphic sets have an isomorphism that is the identity on their intersection. Given X ∈ [2^{μ}]^{θ}, let f_{X} be the collapsing map which assigns to each x ∈ X the order-type of x ∩ X. Then there is some ξ < μ such that f_{X} ⊂ f_{ξ} (by the Engelking and Karlowicz theorem). Let’s color X with ξ (say the first one). Now if X and Y in [2^{μ}]^{θ} have the same order-type and the same color ξ, then the isomorphism of X onto Y is the identity on X ∩Y since it is equal to g_{2}^{−1} ∘g_{1} where g_{1} = f_{ξ} ↾ X and g_{2} = f_{ξ} ↾ Y.

Bibliography

[1] J. E. Baumgartner and K. Prikry. Singular cardinals and the generalized continuum hypothesis. American Mathematical Monthly (1977), 108–113.

[2] M. R. Burke and M. Magidor. Shelah’s pcf theory and its applications. Annals of Pure and Applied Logic, 50(3) (1990), 207–254.

[3] R. Engelking and M. Karlowicz. Some theorems of set theory and their topological consequences. Fundamenta Math. 57, (1965) 275–285.

[4] J. Gregory. Higher Souslin trees and GCH. J. Symb. Logic 41 (1976), 663-671.

[5] A. Hajnal, I. Juhasz, and Z. Szentmiklossy. On CCC boolean algebras and partial orders. Comment. Math. Univ. Carolinae 38, 3 (1997) 537– 544.

[6] M. Holz, K. Steffens, E. Weitz. Introduction to Cardinal Arithmetic. Birkhauser 1999.

[7] T. Jech. Set Theory. Second edition, Springer 2002.

[8] T. Jech. Singular cardinals and the pcf theory. The bulletin of Symbolic Logic, Vol. 1 (1995), 408–424.

[9] A. Kanamori. The Higher Infinite. Springer-Verlag, 1994.

[10] M. Kojman. Exact upper bounds and their uses in set theory. Annals of Pure and applied Logic 92 (1998), 267–282.

[11] A. Levy. Basic Set Theory. Dover (revised edition) 2002.

[12] S. Shelah. Cardinal Arithmetic. Oxford University Press 1994.

[13] S. Shelah. The Generalized Continuum Hypothesis revisited. Israel J. of Math. 116 (2000) 285–321.

[14] S. Shelah. Cellularity of free products of boolean algebras (or topologies). Fundamenta Math. 166 (2000) 153–208.

[15] S. Shelah. More on the revised GCH and middle diamond. (SH829)

[16] J. Silver. On the singular cardinals problem. Proc. 1974 Int’l Congress of Mathematicians.