Frédéric Wang    About    Mathematics    Computer Science    Miscellaneous    Archive

Shelah’s PCF theory

I have recently started to read a bit about Shelah’s theory of possible cofinalities. It is a quite interesting topic in Set Theory that I have wanted to study for a long time, but I did not really find time until now. I am going to give an overview in this blog post for people who are interested but also mostly to help me organizing my ideas and understanding of this subject.

First, this theory originated from (infinite) cardinal arithmetics, which is itself the Cantor’s invention that marked the birth of Set Theory. The addition and multiplication of infinite cardinals are trivial, since we have


The exponentiation is much more difficult (and interesting!). Here is Theorem 5.20 from Thomas Jech’s book "Set Theory":

Theorem 0.1

Let λλ be an infinite cardinal. Then for all infinite cardinal κκ, the value of κλκ^{λ} is computed as follows, by induction on κκ:

  1. 1.

    If κλκ\leq λ then κλ=2λκ^{λ}=2^{λ}.

  2. 2.

    If there exists some μ<κ\mu<κ such that μλκ\mu^{λ}\geq κ, then κλ=μλκ^{λ}=\mu^{λ}

  3. 3.

    If κ>λκ>λ and μλ<κ\mu^{λ}<κ for all μ<κ\mu<κ, then

    1. (a)

      if cf(κ)>λ\operatorname{cf}(κ)>λ, then κλ=κκ^{λ}=κ,

    2. (b)

      if cf(κ)λ\operatorname{cf}(κ)\leq λ, then κλ=κcfκκ^{λ}=κ^{\operatorname{cf}κ}

This theorem reduces the problem of exponentiation to the determination of the continuum function κ2κκ\mapsto 2^{κ} and, on singular cardinals κκ, of the gimel function κ(κ)=κcfκκ\mapsto\operatorname{\gimel}(κ)=κ^{\operatorname{cf}κ} . There are simular reductions of infinite sums and products to sup\sup and exponentation operations, so computing these two functions is the crucial point of cardinal arithmetics.

Set theorists proved by forcing that we can not really say more about the value of the continuum for regular cardinals. Indeed, the only constraints are that the function must be increasing and must satisfy some consequences of König’s theorem (namely 2κ>κ2^{κ}>κ and cf(2κ)>κ\operatorname{cf}(2^{κ})>κ).

At the opposite it turns out that more properties can be proved for the singular case. For instance, we have the striking bound of (ω)\operatorname{\gimel}(ℵ_{ω}) mentioned on Shelah’s Web Archive:

Theorem 0.2
(ω)=ω020+ω4\operatorname{\gimel}(ℵ_{ω})=ℵ_{ω}^{ℵ_{0}}\leq 2^{ℵ_{0}}+ℵ_{ω_{4}}

Shelah developed his PCF theory in order to obtain these kinds of results. The basic idea is to consider an "interval" of regular cardinals AA i.e. with the property that any regular cardinal between two elements of AA is itself an element of AA. Then we define the set of possible cofinalities of ultraproducts of AA:

pcf(A)={cf(A/U)|U is an ultrafilter on A}\operatorname{pcf}(A)=\left\{\operatorname{cf}{\left(\prod A/U\right)}|U\text{ is an ultrafilter on }A\right\}

where A/U\prod A/U is a totally ordered set: an ordinal function is smaller than another if it is smaller "almost everywhere" (i.e. on an element of the ultrafilter UU). The cofinality of such a totally ordered set is defined in a similar way as for cardinals: it is shortest length of an unbounded sequence.

Now, A/U\prod A/U is a topological space (a basis is naturally given by the open intervals with respect to the total order) and so we can use topological methods to get information on it. In particular, this provides information on A\prod A, which in turn provides infomation on |A|\left|\prod A\right|, the infinite product of the (regular) cardinals in AA.

For example, if A={n}n=0A={\left\{\aleph_{n}\right\}}_{n=0}^{\infty} and if we assume that ω\aleph_{\omega} is strong limit then one can show that pcf(A)\operatorname{pcf}(A) is itself an interval of regular cardinals and has a maximum element which is 2ω2^{\aleph_{\omega}}. So its elements are in the sequence of cardinals

minpcf(A)=α,α+1,α+2,,α+λ=maxpcf(A)=2ω\min{\operatorname{pcf}(A)}=\aleph_{\alpha},\aleph_{\alpha+1},\aleph_{\alpha+2 },\ldots,\aleph_{\alpha+\lambda}=\max{\operatorname{pcf}(A)}=2^{\aleph_{\omega}}

and obviouly, α+λ|pcfA|\alpha+\lambda\leq{\left|\operatorname{pcf}A\right|}. But the size of pcfA\operatorname{pcf}A is not greater than the number of ultrafilters of AA, which are sets of subsets of the countable set AA i.e. there are at most 2202^{2^{\aleph_{0}}} many of them. Since we assume that ω\aleph_{\omega} is a strong limit cardinal, we have α+λ220<ω\alpha+\lambda\leq 2^{2^{\aleph_{0}}}<\aleph_{\omega} and finally

Theorem 0.3

If ω\aleph_{\omega} is a strong limit cardinal then


These are of course just two examples of what we can say about the values of the continuum and gimel functions at a singular cardinal (here for ω\aleph_{\omega}, the smallest infinite singular cardinal). Several other results are known and the PCF theory also applies to other areas than cardinal arithmetics. Many beautiful topics that I would like to learn about…