The Story of Generators – 3 (Existence)

October 2, 2012 at 15:32 | Posted in Uncategorized | Leave a comment

The Exact Upper Bound Argument

Let us assume that {A} is as usual, with {\lambda\in{\rm pcf}(A)}. If we want to produce a generator for {\lambda}, we saw last time that what we need is a universal sequence for {\lambda} that in addition possesses an exact upper bound modulo {J_{<\lambda}[A]}.

I don’t want to make an excursion into the theory of exact upper bounds, as there have been many high quality write-ups of this material already: in addition to Section 2.1 of the Abraham/Magidor article, there are also some materials due to Kojman that do an excellent job of exposing this material. The point is that one can use results of Shelah to modify the universal sequence so that it ends up with an exact upper bound, and then we get generators by the previous post.

Instead of re-hashing such arguments, I offer the following direct route from universal sequences to generators. The proof takes advantage of the ideal {I[\lambda]}, and we will see similar arguments shortly when we talk about transitivity of generators. The argument is based on the exposition of generators given in the Burke-Magidor pcf paper. It turns out that framing things in terms of {I[\lambda]} simplifies things considerably.

From universal sequences to generators

Theorem 1 Suppose {A} is a progressive set of regular cardinals and {\lambda\in{\rm pcf}(A)}. Then there is a generator for {\lambda}.

Proof: We can assume that {\lambda>|A|^{++}}. (If either {|A|^+} or {|A|^{++}} are in {A}, then they have generators consisting of singletons.)

Let {\bar{f}=\langle f_\alpha:\alpha<\lambda\rangle} be a universal sequence for {\lambda}, that is, a sequence such that

  • {\alpha<\beta\Longrightarrow f_\alpha<_{J_{<\lambda}[A]} f_\beta}, and
  • {\langle f_\alpha:\alpha<\lambda\rangle} is cofinal in {\prod A/D} whenever {D} is an ultrafilter on {A} satisfying {{\rm cf}(\prod A/D)=\lambda}.

Such sequences exist by Theorem 4.2 of the Abraham/Magidor article, or see Lemma 2.1 on page 327 of Cardinal Arithmetic.

Let {\kappa=|A|^+}. Since we have assumed {\kappa^+<\lambda}, we know there is a stationary set {S\subseteq S^\lambda_\kappa} lying in the ideal {I[\lambda]}. (See the first section of [Sh:420], or Theorem 3.18 in my own Handbook article.)

This means that there is a family {\bar{C}=\langle C_\alpha:\alpha<\lambda\rangle} and a club {E\subseteq\lambda} such that

  • {C_\alpha} is a closed (possibly bounded) subset of {\alpha}
  • if {\beta\in{\rm nacc}(C_\alpha)} then {C_\beta=C_\alpha\cap\beta}, and
  • if {\delta\in E\cap S} then {C_\delta} is club in {\delta} of order-type {\kappa}.

For each {\alpha<\lambda} with {C_\alpha\neq\emptyset}, we define

\displaystyle  f^*_\alpha=\sup\{f_\beta:\beta\in C_\alpha\}. \ \ \ \ \ (1)

If {C_\alpha=\emptyset}, we set {f^*_\alpha=f_\alpha}.

Since {\prod A/J_{\leq\lambda}[A]} is {\lambda^+}-directed, we can find a single function {h} bounding the collection {\{f^*_\alpha:\alpha<\lambda\}} modulo {J_{\leq\lambda}[A]}.

Now we let {N} be an elementary submodel of {H(\chi)} for some sufficiently large regular cardinal {\chi} such that

  • {A}, {\bar{f}}, {\bar{C}}, {E}, {S}, {h}, and {\lambda} are all in {N}
  • {|N|<\lambda}
  • {N\cap\lambda} is an ordinal {\delta\in S}

This is possible because {S} is stationary in {\lambda}.

We define

\displaystyle  B:=\{\theta\in A: h(\theta)<f^*_\delta(\theta)\}. \ \ \ \ \ (2)

We prove that {B} is a generator for {\lambda}. Part of this is simple, as by choice of {h} we know {B\in J_{\leq\lambda}[A]}. To finish, we must establish the following:

Proposition 2 If {D} is an ultrafilter on {A} with {{\rm cf}(\prod A/D)=\lambda}, then {B\in D}.

The proof is not difficult, but the following lemma is critical.

Lemma 3 {B\in N}.


This is where the {I[\lambda]} assumption pays dividends. Note that {\delta\in E} as {E\in N}, and therefore we know that {C_\delta} is club in {\delta} with order-type {\kappa}.

Given {\alpha<\beta} in {{\rm nacc}(C_\delta)}, we know that {C_\alpha= C_\delta\cap\alpha} is an initial segment of {C_\beta= C_\delta\cap\beta}, and both are initial segments of {C_\delta}. Thus

\displaystyle  f^*_\alpha\leq f^*_\beta\leq f^*_\delta. \ \ \ \ \ (3)

Given {\theta\in A} and {\xi<f^*_\delta(\theta)}, we know there is a {\gamma\in C_\delta} with {\xi<f_\gamma(\theta)}. Since {C_\delta} is cofinal in {\delta}, we know {\min(C_\delta\setminus(\gamma+1))} is an ordinal {\alpha} in {{\rm nacc}(C_\delta)} and {\gamma\in C_\alpha= C_\delta\cap\alpha}. Thus {\xi<f_\alpha^*(\theta)}, and we see

\displaystyle  f^*_\delta=\sup\{f^*_\alpha:\alpha\in{\rm nacc}(C_\delta)\}. \ \ \ \ \ (4)

In particular, if {h(\theta)<f^*_\delta(\theta)}, then there is an {\alpha(\theta)<\delta} such that

\displaystyle  \alpha\in {\rm nacc}(C_\delta)\setminus\alpha(\theta)\Longrightarrow h(\theta)<f^*_\alpha(\theta). \ \ \ \ \ (5)

Since {C_\delta} is club in {\delta} with order-type {\kappa>|A|}, we can find a single {\alpha\in{\rm nacc}(C_delta)} such that for all {\theta\in A},

\displaystyle  h(\theta)<f^*_\delta(\theta)\Longleftrightarrow h(\theta)<f^*_\alpha(\theta). \ \ \ \ \ (6)

In particular,

\displaystyle  B=\{\theta\in A: h(\theta)<f^*_\delta(\theta)\}=\{\theta\in A: h(\theta)<f^*_\alpha(\theta)\}. \ \ \ \ \ (7)

The set on the right is definable from parameters available in {N} (both {h} and {f^*_\alpha} are there), and therefore {B\in N}. \Box

Let us return now to the proof of Proposition 2.

Proof: By way of contradiction, suppose {D} is an ultrafilter on {A} forming a counterexample. Since {B} is in {N}, we can assume that {D} is in {N} as well (this is the key point).

This sequence {\bar{f}} is universal for {\lambda} and therefore the collection {\{f_\alpha:\alpha<\lambda\}} is cofinal in {\prod A/D}. Since {D\cap J_{<\lambda}[A]=\emptyset}, we know furthermore that the sequence {\langle f_\alpha:\alpha<\lambda\rangle} is {<_D} increasing.

Thus, there is an {\alpha^*<\lambda} such that {h<_D f_\alpha} whenever {\alpha^*\leq\alpha<\lambda}. Again, we may assume that {\alpha^*} is in {N} (and hence less than {\delta=N\cap\lambda}).

Choose {\beta\in C_\delta} greater than {\alpha^*} and let {\alpha=\min(C_\delta\setminus(\beta+1)}. Then {\alpha\in{\rm nacc}(C_\delta)} and {C_\alpha= C_\delta\cap\alpha}. In particular, {\alpha\in N} and {\beta\in C_\alpha}

So we have

\displaystyle  h<_D f^*_\alpha\leq f^*_\delta. \ \ \ \ \ (8)

One the other hand, since {B\notin D} we know

\displaystyle  f^*_\delta\leq_D h. \ \ \ \ \ (9)

But now we have obtained a contradiction. \Box

Proposition 2 taken together with the fact that {B\in J_{\leq\lambda}[A]} easily establishes that {B} is a generator for {\lambda}, so we are done. \Box


The Story of Generators – 2

October 1, 2012 at 14:22 | Posted in Uncategorized | Leave a comment

Finding Generators

Theorem 1 Suppose

  • {A} is a progressive sequence of regular cardinals
  • {\lambda\in{\rm pcf}(A)}
  • {\bar{f}=\langle f_\alpha:\alpha<\lambda\rangle} is a universal sequence for {\lambda}
  • {g} is an exact upper bound for {\bar{f}} modulo {J_{<\lambda}[A]}
  • {B=\{\theta\in A:g(\theta)=\theta\}}

Then for any ultrafilter {D} on {A},

\displaystyle  {\rm cf}(\prod A/D)=\lambda \text{ if and only if } B\in D \text{ and }D\cap J_{<\lambda}[A]=\emptyset. \ \ \ \ \ (1)

What does this have to do with generators? Just note the following:

Corollary 2 Under the assumptions of the theorem, we have {J_{\leq\lambda}[A]=J_{<\lambda}[A]+B}, hence {B} is a generator for {\lambda}.

Proof: If {D} is an ultrafilter on {A} containing {B}, then either {D} meets {J_{<\lambda}[A]} or it does not. In the first case, the cofinality of {\prod A/D} is less than {\lambda} by definition of {J_{<\lambda}[A]}, and in the second case the cofinality is exactly {\lambda} by the conclusion of the theorem. In either case, the cofinality is at most {\lambda} and so {B} is in {J_{\leq\lambda}[A]} and we have

\displaystyle  J_{<\lambda}[A]+B\subseteq J_{\leq\lambda}[A]. \ \ \ \ \ (2)

For the other inclusion, suppose {B^*} is in {J_{\leq\lambda}[A]} but not in {J_{<\lambda}[A]+B}. Let {D} be an ultrafilter on {A} containing {B^*} but disjoint to {J_{<\lambda}[A]+B}. Since the cofinality of {\prod A/D} is {\lambda}, we have contradicted the conclusion of the theorem. \Box

Digression on exact upper bounds

Before proving Theorem~1, we need to say a few words about exact upper bounds because different authors treat them in slightly different ways. Let us assume that {g} is an exact upper bound for {\bar{f}} mod {J_{<\lambda}[A]} just as in the statement of the theorem. It is easy to see

\displaystyle  \{\theta\in A: g(\theta)=0\text{ or }\theta<g(\theta)\}\in J_{<\lambda}[A], \ \ \ \ \ (3)

and so our {g} is equal mod {J_{<\lambda}[A]} to a function {g^*} satisfying

\displaystyle  0<g^*(\theta)\leq\theta\text{ for all }\theta\in A. \ \ \ \ \ (4)

If we define {B^*:=\{\theta\in A:g^*(\theta)=\theta\}}, then {B^*} and {B} are equal modulo the ideal {J_{<\lambda}[A]}, and for any ultrafilter {D} on {A} disjoint to {J_{<\lambda}[A]}, we have {B\in D} if and only if {B^*\in D}.

The point of the above is that we can replace {g} by {g^*} and not change anything, so we may as well assume that our function {g} satisfies

\displaystyle  0<g(\theta)\leq \theta\text{ for all }\theta\in A. \ \ \ \ \ (5)

Proof of Theorem

Proof: Suppose first that {D} is an ultrafilter on {A} containing {B} but disjoint to {J_{<\lambda}[A]}. The sequence {\bar{f}} is {<_D}-increasing, so if we can show it is cofinal in {\prod A/D} we will know that the cofinality of {\prod A/D} is exactly {\lambda}.

Suppose {h\in \prod A}. Then by setting {h} equal to zero outside of {B} we produce a function {h^*} that is equal to {h} mod {D} and less than {g} everywhere. Our assumptions on {g} then give us an {\alpha} such

\displaystyle  h^*<_{J_{<\lambda}[A]} f_\alpha, \ \ \ \ \ (6)

and since {D\cap J_{<\lambda}[A]=\emptyset}, we achieve

\displaystyle  h=_D h^*<_D f_\alpha, \ \ \ \ \ (7)

as required.

For the other direction, suppose by way of contradiction that {D} is an ultrafilter on {A} satisfying {{\rm cf}(\prod A/D)=\lambda} with {B\notin D}.

Outside of the set {B}, we have {g(\theta)<\theta} and so {g} is {D}-equivalent to a function {g^*\in\prod A}. Since {\bar{f}} is universal for {\lambda}, there is an {\alpha<\lambda} such that {g^*<_D f_\alpha} and hence

\displaystyle  g<_D f_\alpha \ \ \ \ \ (8)

as well.

But {g} is an exact upper bound for {\bar{f}} mod {J_{<\lambda}[A]}, and so

\displaystyle  f_\alpha\leq_{J_{<\lambda}[A]} g. \ \ \ \ \ (9)

Since the cofinality of {\prod A/ D} is {\lambda} we know {D\cap J_{<\lambda}[A]=\emptyset}, and therefore

\displaystyle  f_\alpha\leq_D g. \ \ \ \ \ (10)

Putting all of this together yields

\displaystyle  f_\alpha\leq_D g <_D f_\alpha, \ \ \ \ \ (11)

and this is a contradiction. \Box

The Story of Generators 1

October 1, 2012 at 12:10 | Posted in Uncategorized | Leave a comment


I’m not sure exactly where things left off, so I’ll just begin with a series of posts on generators for pcf. I will also try to keep the posts short so that I can ease back into the routine of writing them.

Let us assume that {A} is a progressive set of regular cardinals, and {\lambda\in{\rm pcf}(A)}. I will assume we know already some of the basics about the ideal {J_{<\lambda}[A]} and I will use these facts without much comment.

What we want to look at is the existence of a generator for {\lambda}: we will sketch the proof that the ideal {J_{\leq\lambda}[A]} is generated over {J_{<\lambda}[A]} by a single set {B_\lambda}. And I do mean “sketch”, as the details are worked out nicely in Section 4 of the Abraham/Magidor article in the Handbook of Set Theory.

Universal Sequences

We’ll start with the following definition:

Definition 1 Suppose {\lambda\in{\rm pcf}(A)}. A sequence {\bar{f}=\langle f_\alpha:\alpha<\lambda\rangle} of functions in {\prod A} is a universal sequence for {\lambda} if

  • {\bar{f}} is {<_{J_{<\lambda}[A]}}-increasing, and

  • {\bar{f}} is cofinal in {\prod A/D} whenever {D} is an ultrafilter on {A} with {\lambda={\rm cf}(\prod A/D)}.

Universal sequences are tightly related to the existence of generators for pcf, as we shall see. I want to point out the following result:

Theorem 2 Suppose {A} is a progressive set of regular cardinals and {\lambda\in{\rm pcf}(A)} Then the following statements are equivalent:

  1. There is a universal sequence for {\lambda}.
  2. There is a family {F\subseteq \prod A} such that for any ultrafilter {D}, if {\prod A/D} has cofinality {\lambda} then {F} remains unbounded in {\prod A/D}.
  3. There is a family {\langle B_\alpha:\alpha<\lambda\rangle} of subsets of {A} such that
    • {\alpha<\beta\Longrightarrow B_\alpha\subseteq B_\beta} modulo {J_{<\lambda}[A]}, and
    • {J_{\leq\lambda}[A]} is the ideal generated by {J_{<\lambda}[A]} together with the sets {\{B_\alpha:\alpha<\lambda\}}.

The above is basically Fact 2.2 on page 13 of Cardinal Arithmetic, and it follows quite easily from the work done in the first section of the book. (The 3rd statement says, in the notation of the book, that {\lambda} is semi-normal.) Abraham and Magidor develop basic pcf theory in a slightly different order, and deriving the above result from the material they present prior to defining universal sequences is a bit more difficult.

Of course, the main point is the following result:

Theorem 3 If {A} is a progressive set of regular cardinals, then every {\lambda\in{\rm pcf}(A)} has a universal sequence.

Again, we will not prove the above as this is Theorem 4.2 of the Abraham-Magidor article, and their proof is quite clear.

What have we learned from the above? We have outlined the first steps towards proving that generators exist. Putting the two theorems presented here together, we see that if {\lambda\in{\rm pcf}(A)}, then {J_{\leq\lambda}[A]} is pretty simply generated over {J_{<\lambda}[A]}.

In our next post, we’ll see how “tuning up” a universal sequence leads to the existence of generators.

Create a free website or blog at
Entries and comments feeds.