Ultrafilters VII: Large Cardinals

In order for a true believer to really know Mount Everest, he must slowly and painfully trudge up its forbidding side, climbing the rocks amid the snow and the slush, with his confidence waning and his skepticism growing as to the possibility of ever scaling the height. But in these days of great forward leaps in technology, why not get into a helicopter, fly up to the summit, and quickly survey the rarefied realm — all while having a nice cup of tea?

-Akihiro Kanamori and Menachem Magidor,

“The evolution of large cardinal axioms in set theory.”

In our discussion of ultrafilters, we have thus far focussed on ultrafilters on countable sets (the natural numbers, mainly). Today, in the last installment of our miniseries, we move higher. Much higher.

The standard axioms of set theory (Zermelo-Fraenkel with Choice (or ZFC, for short)), imply the existence of what most people would consider to be quite large cardinal numbers. Even the smallest infinite cardinal, \aleph_0, so far exceeds our everyday experience as to be almost ungraspable. But this is, of course, only the beginning. Recall, that, for a cardinal \kappa, 2^\kappa denotes the cardinality of the power set of a set of cardinality \kappa. Since the Power Set Axiom is one of the axioms of ZFC, we get the existence of 2^{\aleph_0}, also known as \beth_1. By Cantor’s theorem, \beth_1 > \aleph_0. Continuing, we find \beth_2 = 2^{\beth_1}, \beth_3 = 2^{\beth_2}, and so on, an increasing sequence of cardinals. But we are, of course, not done. A different axiom of ZFC (called Replacement) ensures the existence of a cardinal called \beth_\omega, the least cardinal bigger than \beth_n for all n \in \mathbb{N}. But now, of course, we have \beth_{\omega+1} = 2^{\beth_\omega}, and you know how the story continues.

We can conceive of some cardinals, though, that are so large that they cannot be proven to exist by the axioms of ZFC. What do I mean by this? Recall that, as a set, we often identify a cardinal with the least ordinal of its size, i.e. the set of all ordinals of strictly smaller size. Recall also that a cardinal \kappa is regular if, whenever A \subseteq \kappa and A is unbounded in \kappa, then |A| = \kappa. And some new terminology: we say that a cardinal \kappa is strong limit if, whenever, \lambda < \kappa, we also have 2^\lambda < \kappa.

Note that \beth_\omega is a strong limit cardinal. To see this, suppose \lambda < \beth_\omega. Then there is n \in \mathbb{N} such that \lambda \leq \beth_n. But then 2^\lambda \leq 2^{\beth_n} = \beth_{n+1} < \beth_\omega. \beth_\omega, however, is not regular. If A = \{\beth_n \mid n \in \mathbb{N}\}, then A is unbounded in \beth_\omega, but |A| = \aleph_0 < \beth_\omega.

Are there any regular strong limit cardinals? Well, yes. \aleph_0 does the trick. (Exercise: Why?) Are there any others? Uncountable regular strong limit cardinals are called strongly inaccessible cardinals. It turns out that, if the axioms of ZFC are consistent, they cannot prove the existence of strongly inaccessible cardinals. To see why, we need a few words about the universe of set theory. Traditionally, we think of the universe of set theory (named V) as being built up cumulatively as a hierarchy of sets V_\alpha, where \alpha ranges over all ordinals. The hierarchy is increasing, i.e. if \alpha < \beta, then V_\alpha \subset V_\beta, and every set in V is contained in some V_\alpha. It turns out that, if \kappa is a strongly inaccessible cardinal, then all of the axioms of ZFC are already true in V_\kappa. Therefore, if there is a strongly inaccessible cardinal and \kappa is the least one, then V_\kappa is a model of all of the axioms of set theory in which there are no strongly inaccessible cardinals (if a cardinal \lambda is strongly inaccessible in V_\kappa, then it would really be strongly inaccessible, contradicting the minimality of \kappa). A more subtle argument, using Gödel’s Second Incompleteness Theorem, shows that, working in ZFC, the consistency of ZFC does not imply the consistency of ZFC together with the existence of a strongly inaccessible cardinal.

(Incidentally, V_{\aleph_0} satisfies all of the axioms of ZFC with one crucial exception: the Axiom of Infinity, which simply asserts the existence of an infinite set. All of the sets in V_{\aleph_0} are finite! This shows that the Axiom of Infinity cannot be derived from the others.)

The assertion that there is a strongly inaccessible cardinal (together with ZFC) therefore transcends ZFC and is one of the weakest in a hierarchy of axioms known as large cardinal axioms. Roughly speaking, a large cardinal is a type of cardinal whose existence is not implied by the axioms of ZFC. Strongly inaccessible cardinals, then, are among the smallest of the commonly studied large cardinals.

Let’s jump into the helicopter employed by Kanamori and Magidor in their magisterial 1978 survey paper and go a bit higher. In fact, quite a bit higher; in the interest of time, we will skip over much of the landscape and only touch on a few highlights of the large cardinal hierarchy.

In previous posts, we touched on infinite Ramsey theory. In particular, we proved the following theorem:

Infinite Ramsey Theorem: For every function f:[\aleph_0]^2 \rightarrow \{0,1\}, there is an infinite H \subseteq \aleph_0 that is homogeneous for f, i.e. there is a fixed value i \in \{0,1\} such that, for all \{m,n\} \in [H]^2, f(\{m,n\}) = i.

It is natural to wonder whether this can be generalized to cardinals higher than \aleph_0. Namely, we may ask the following question:

Higher Infinite Ramsey Question: Is there a cardinal \kappa > \aleph_0 such that, for every function f:[\kappa]^2 \rightarrow \{0,1\}, there is H \subseteq \kappa such that |H| = \kappa and H is homogeneous for f? In the notation of our last post, is there \kappa > \omega such that \kappa \rightarrow (\kappa, \kappa)^2?

There is a nice argument (which we will omit) showing that \aleph_1 does not have this property. In fact, perhaps somewhat surprisingly, if \kappa > \omega and \kappa \rightarrow (\kappa, \kappa)^2, then \kappa must be strongly inaccessible! Much more is in fact true: if \kappa > \omega and \kappa \rightarrow (\kappa, \kappa)^2, then \kappa must be the \kappa^{\mathrm{th}} strongly inaccessible cardinal!

If \kappa > \omega and \kappa \rightarrow (\kappa, \kappa)^2, then we say that \kappa is a weakly compact cardinal. The assertion that there is a weakly compact cardinal is therefore a large cardinal axiom much stronger than the assertion that there is a strongly inaccessible cardinal.

Weakly compact cardinals, while still somewhat small in the large cardinal hierarchy, are, to my mind, among the most interesting large cardinals. This is due, in large part, to the delightful fact that there are many equivalent definitions of weakly compact cardinals that, at first glance, have little to do with one another (mathematicians love this – it provides some evidence that the notion we have isolated is a natural and important one). I will not explain any of these equivalent definitions, but I present some of them here for the sake of poetry.

Theorem: Suppose \kappa > \omega is a cardinal. Then the following conditions are all equivalent to one another, and all characterize weak compactness.

  1. \kappa \rightarrow (\kappa, \kappa)^2.
  2. \kappa is strongly inaccessible and has the tree property.
  3. \kappa is \Pi^1_1-indescribable.
  4. L_{\kappa\kappa} satisfies compactness for collections of sentences using at most \kappa non-logical symbols.
  5. For all R \subseteq V_\kappa, there is a transitive set X such that \kappa \in X and a subset S \subseteq X such that \langle V_\kappa, \in, R \rangle \prec \langle X, \in, S \rangle .
  6. For every \kappa-model M, there is a \kappa-model N and an elementary embedding j:M \rightarrow N such that \mathrm{crit}(j) = \kappa and j,M \in N.

Onward and upward, and, at our next stop, ultrafilters will re-enter the picture. Recall that, if \mathcal{U} is an ultrafilter, then any finite intersection of sets in \mathcal{U} is itself in \mathcal{U}. What if we demand more? Let us make the following definition.

Definition: Suppose \mathcal{U} is an ultrafilter and \kappa is a cardinal. Then \mathcal{U} is \kappacomplete if, whenever, X is a collection of sets in \mathcal{U} and |X| < \kappa, then the intersection of all of the sets in X is in \mathcal{U}.

Thus, any ultrafilter is \aleph_0-complete. Moreover, we now have the language to describe our next large cardinal notion: a cardinal \kappa > \omega is measurable if there is a non-principal, \kappa-complete ultrafilter on \kappa.

It turns out that all measurable cardinals are weakly compact and, as in the jump from strongly inaccessible to weakly compact, we have in fact moved up in size significantly: if \kappa is measurable, then \kappa is the \kappa^{\mathrm{th}} weakly compact cardinal.

Even larger large cardinals can also be formulated in terms of ultrafilters. To give their definition, we need some notation. Suppose \kappa \leq \lambda are cardinals. Then \mathcal{P}_\kappa(\lambda) = \{X \subseteq \lambda \mid |X| < \kappa \}. We say a cardinal \kappa is \lambdasupercompact if there is a \kappa-complete, normal, fine ultrafilter on \mathcal{P}_\kappa(\lambda) (don’t worry about the definitions of ‘normal’ or ‘fine’; they are technical conditions asserting that the ultrafilter is ‘nice,’ in a certain sense). \kappa is supercompact if \kappa is \lambda-supercompact for all \lambda \geq \kappa.

We are quite high up now, and the air is getting thin. Supercompact cardinals frequently appear in my own work; the existence of all of these nice ultrafilters gives one quite a bit of power (suspiciously much power, it sometimes seems). It will not surprise you to learn that supercompact cardinals are measurable and, in fact, if \kappa is supercompact, then \kappa is the \kappa^{\mathrm{th}} measurable cardinal.

lc_diagram
A diagram of some large cardinal notions, arranged in order of consistency strength. Source: The Higher Infinite, by Akihiro Kanamori.

This is all well and good, but why, you might ask, should we study these large cardinals, much less believe that they exist (or, at least, consistently exist)? There are a number of answers to this, and we can’t possibly go into the depths of the arguments here, but I will present a few responses.

  • Large cardinal axioms conform with an intuition that the universe of sets should be as rich as possible, and denying the existence of large cardinals seems to many people to be needlessly restrictive.
  • Many large cardinal axioms generalize properties that hold at \aleph_0 (or, sometimes, of the class of all ordinals). This includes most of what we have seen today: if we did not require large cardinals to be uncountable, then \aleph_0 would be strongly inaccessible, weakly compact, and measurable (under the definitions given here). It would seem strange if \aleph_0 were the only cardinal satisfying these properties.
  • Efficacy: Positing the existence of large cardinals can solve a number of problems that could not be solved without them. Somewhat surprisingly, some of these problems are about objects that are quite small (compared to the large cardinals), such as the set of real numbers.
  • Aesthetics: The fact that, for example, weakly compact cardinals have so many equivalent formulations is highly pleasing and suggests that the notion is a valuable and important one. More broadly, the fact that the large cardinal notions we study, coming from different sources and having seemingly unrelated definitions, form a nice, mostly linear hierarchy, might count as evidence that we are on the right track.

One must be careful, though, lest the helicopter crash. At the end of his 1967 PhD thesis, Reinhardt proposed a large cardinal that was a natural generalization of those considered thus far and that came to be known as a Reinhardt cardinal. In a striking turn of events, soon thereafter, Kunen proved that Reinhardt cardinals are inconsistent with ZFC! Since then, we have been edging closer and closer to this chasm of inconsistency, defining stronger and stronger large cardinal axioms that stop just short of falling prey to Kunen’s proof. The fact that none of these axioms has yet been proven inconsistent (and not for lack of trying) may give us confidence in their use, but there is always the slim chance that one of them will be proven outright false, an occurrence that would be exhilarating and calamitous in equal measure. We end with another evocative quote from Kanamori and Magidor.

Of course, the sky looks highly unapproachable from the ground. But in the current climate of relative consistency results and the Axiom of Determinacy, we are not afraid to get into our mental helicopters and, Icarus-like, soar unashamedly in speculative altitudes implicit in forms of statements like “if there is a measurable cardinal, then…” If the sun begins to melt the wax on our wings, we can always don the formalist parachute by saying that these are interesting implications of ZFC.

 

 

Advertisements

Ordinals

Note: If you need a refresher on well-orderings, ordinals, and cardinals, check out the Ordinals and Cardinals page.


When I was in elementary school, a tiny part of the mathematics curriculum, a few minutes in fourth grade, was the distinction between ‘ordinal numbers’ and ‘cardinal numbers.’ We were vaguely told that ordinal numbers dealt with order and cardinal numbers dealt with amount, and things were pretty much left at that. I remember feeling vaguely dissatisfied with this lesson and, looking back at it, I recognize it as representative of a somewhat common occurrence in the post-New Math American classroom. A very interesting topic (in this case, ordinals vs. cardinals) was brought up, and basically none of what makes it interesting was discussed.

In this case, the basic issue is that we talked about ordinals and cardinals (and everything else in mathematics) solely in the context of finite numbers (this is entirely understandable; we were, after all, in fourth grade). And, in the realm of the finite, ordinals and cardinals are pretty much the same! Given, say, four indistinguishable objects, there is only one essentially distinct way to well-order them. There’s a first element, a second, a third, and a fourth. That’s it! Each finite cardinal corresponds to a finite ordinal, and vice versa, and no conceptual clarity is gained from making a distinction between the two.

(The reader may rightly accuse me of being a little harsh here and of purposely conflating the common and technical usages of the term ‘ordinal number.’ The ‘ordinal numbers’ we saw in elementary school were of the form ‘first,’ ‘second,’ ‘third,’ etc. I still maintain, though, that the difference we were taught between finite ordinals and finite cardinals is uninteresting and misleading. The mere act of counting a finite set imposes an order on it, and the type of this order is unique. It is of course important to learn the words ‘first,’ ‘second,’ ‘third,’ etc., but that is not what this lesson was doing. (I’d also be happy to be proven wrong about this – if you had a very different experience, either as a student or as a teacher, let me know!))

The situation changes as soon as we reach the infinite. Given a countable infinity of indistinguishable objects (one for each natural number), there are many essentially distinct ways of well-ordering them. One can, for example, order them like the natural numbers (this corresponds to the ordinal \omega). One could set one object aside, order the others like the natural numbers, and then put the set-aside object at the end (this corresponds to the ordinal \omega + 1 and is easily seen to be distinct from the first ordering, as it has a largest element while the first does not). One could divide the objects into two infinite sets, order them both like the natural numbers, and put one set after the other (this corresponds to the ordinal \omega + \omega. There are in fact uncountably many different ways to well-order this set of objects, each corresponding to a different ordinal \alpha, where \alpha < \omega_1 (recall that \omega_1 is the least uncountable ordinal).

The world of countable ordinals is a fascinating and confusing place, and some people spend much of their careers studying just these objects. Let me give you one example. We will first need some notation. Suppose that \alpha, \beta, and \gamma are ordinals and n is a natural number. Recall that, as a set, an ordinal is considered to be the set of all ordinals smaller than it. Also, recall that [\gamma]^n stands for the set of all subsets of \gamma of size n. Then

\gamma \rightarrow (\alpha, \beta)^n

stands for the following assertion: whenever f is a function, f:[\gamma]^n \rightarrow \{0,1\}, there is either a set X \subseteq \gamma of order-type \alpha such that, for all x \in [X]^n, f(x) = 0, or there is a set Y \subseteq \gamma of order-type \beta such that, for all y \in [Y]^n, f(y) = 1. This is thus a statement in Ramsey Theory, introduced in a previous post. In that post, we proved the Infinite Ramsey Theorem, a special case of which can be rephrased in our new terminology as:

for all n < \omega, \omega \rightarrow (\omega, \omega)^n.

This statement becomes false when we replace \omega by \omega_1. In fact, it fails already for n=2, which we denote by

\omega_1 \not\rightarrow (\omega_1, \omega_1)^2.

There is a lot to say about this that we won’t bring up here. For example, in our next post, we will consider the question of whether there are any cardinals \kappa > \omega for which

\kappa \rightarrow (\kappa, \kappa)^2

is true. There is also a great deal to be said about slightly weakening the above false statement about \omega_1 and asking:

for which ordinals \alpha < \omega_1 is \omega_1 \rightarrow (\omega_1, \alpha)^2 true?

This question gets quite complicated but is fairly well understood. However, as soon as we replace the ‘2’ with a ‘3’, our current understanding becomes quite poor. For example, the following seemingly basic question is wide open:

Is it the case that, for all \alpha < \omega_1, \omega_1 \rightarrow (\alpha, 4)^3 is true?

The answer is ‘yes’ for all \alpha \leq \omega^2 + 1 and ‘no’ for \alpha = \omega_1. In between, we have no idea.

For an extensive tour of the countable ordinals, I highly recommend you take a look at the recent series at John Baez’s excellent blog, Azimuth (the first installment is here). Also, make sure to visit David Madore’s delightful interactive visualization of the countable ordinals.