Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 14, 2019

The Myths of Presentability and the Sharply Large Filter

Posted by Mike Shulman

The theory of locally presentable and accessible categories and functors is an elegant and powerful tool for dealing with size questions in category theory. It contains a lot of powerful results, many found in the standard reference books Locally presentable and accessible categories (by Adamek and Rosicky) and Accessible categories (by Makkai and Pare), that can be quoted without needing to understand their (sometimes quite technical) proofs.

Unfortunately, there are a couple of such “results” that are occasionally quoted, but are actually nowhere to be found in AR or MP, and are in fact false. These are the following claims:

Myth A: “If 𝒞\mathcal{C} is a locally λ\lambda-presentable category and μ\mu is a regular cardinal with μλ\mu\ge\lambda, then every μ\mu-presentable object of 𝒞\mathcal{C} can be written as a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects.”

Myth B: “If F:𝒞𝒟F:\mathcal{C}\to \mathcal{D} is an accessible functor between locally presentable categories, then FF preserves μ\mu-presentable objects for all sufficiently large regular cardinals μ\mu.”

Below the fold I will recall the definitions of all these words, and then discuss how one might fall into believing these myths, why they are is not true, and what we can do about it.

Definitions: A cardinal number λ\lambda is regular if the union of <λ\lt\lambda sets of cardinality <λ\lt\lambda still has cardinality <λ\lt\lambda. Any successor cardinal (i.e. one of the form α+1\aleph_{\alpha+1}) is regular, and ZFC does not prove there exist any others. A category is λ\lambda-small if its set of arrows has cardinality <λ\lt\lambda, and λ\lambda-filtered if every λ\lambda-small diagram in it admits some cocone. An object XX is λ\lambda-presentable (sometimes called “λ\lambda-compact”) if the covariant hom-functor Hom(X,)Hom(X,-) preserves λ\lambda-filtered colimits. A locally λ\lambda-presentable category (sometimes called simply a “λ\lambda-presentable category”, but that properly refers to a λ\lambda-presentable object in CatCat) is a cocomplete locally small category with a small dense subcategory consisting of λ\lambda-presentable objects. And a functor between locally λ\lambda-presentable categories is λ\lambda-accessible if it preserves λ\lambda-filtered colimits.

Thus a locally presentable category, though large, is “determined by a small amount of information”. So Myth A is an intuitively appealing statement that past some point, the objects of “all higher cardinalities” are “determined” by those of “cardinality” λ\lambda, and similarly Myth B says that past some point accessible functors “preserve size”. And indeed, there are several true statements with similar intuitive meanings; the following facts can be found in AR and MP:

  1. If λμ\lambda\le \mu, then every λ\lambda-presentable object is μ\mu-presentable, and any μ\mu-small colimit of μ\mu-presentable objects is again μ\mu-presentable. In particular, Myth A has a true converse: any μ\mu-small colimit (λ\lambda-filtered or not) of λ\lambda-presentable objects is μ\mu-presentable.

  2. If 𝒞\mathcal{C} is locally λ\lambda-presentable and μ\mu is a regular cardinal with μλ\mu\ge\lambda, then every μ\mu-presentable object of 𝒞\mathcal{C} can be written as a μ\mu-small (not necessarily λ\lambda-filtered) colimit of λ\lambda-presentable objects (Remark 1.30 in AR).

  3. If 𝒞\mathcal{C} is λ\lambda-accessible and μ\mu is a regular cardinal with μλ\mu\rhd\lambda (a “sharp” cardinal inequality — see below), then every μ\mu-presentable object of 𝒞\mathcal{C} can be written as a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects (Remark 2.15 in AR).

  4. If FF is an accessible functor, then there is a regular cardinal κ\kappa such that FF preserves μ\mu-presentable objects for any regular cardinal μ\mu with μκ\mu\rhd\kappa.

Facts (2) and (3) say that if we weaken the conclusion of Myth A by removing λ\lambda-filteredness of the colimit, or strengthen the hypotheses by assuming μλ\mu\rhd\lambda rather than μλ\mu\ge \lambda, then it becomes a true statement. (Actually AR proves only that every μ\mu-presentable object is a retract of a colimit of the above forms. In case (3) the retract can be eliminated using Proposition 2.3.11 of MR; eliminating the retract in case (2) is discussed here.) Similarly, fact (4) says that Myth B becomes true if we restrict the cardinals μ\mu appearing in it to those with μκ\mu\rhd\kappa.

(In passing, it’s worth noting that Myth A implies Myth B, and similarly fact (3) implies fact (4). Let F:𝒞𝒟F:\mathcal{C}\to \mathcal{D} be an λ\lambda-accessible functor between locally λ\lambda-presentable categories, and let κ\kappa be such that whenever XX is λ\lambda-presentable, F(X)F(X) is κ\kappa-presentable. Such a κ\kappa always exists, since there is only a set of isomorphism classes of λ\lambda-presentable objects in 𝒞\mathcal{C}, and every object of 𝒟\mathcal{D} is presentable for some cardinal. Then if every μ\mu-presentable object XX in 𝒞\mathcal{C} is a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects, then FF preserves this colimit as it is λ\lambda-accessible. Thus F(X)F(X) is a μ\mu-small (λ\lambda-filtered) colimit of κ\kappa-presentable objects, and hence μ\mu-presentable.)

Evidently the difference between the true facts (3) and (4), on one hard, and the false Myths A and B, on the other hand, lies in the difference between \le and \lhd. In particular, it’s important that for a given λ\lambda it is not true that λμ\lambda\lhd \mu for all sufficiently large μ\mu. Saying λμ\lambda\lhd\mu doesn’t mean that μ\mu is “a lot bigger” than λ\lambda (indeed it doesn’t have to be very much bigger at all, e.g. λλ +\lambda \lhd \lambda^+ whenever λ\lambda is regular, where λ +\lambda^+ denotes the smallest cardinal larger than λ\lambda). Instead it is more of a “large cofinality” assertion for μ\mu with respect to λ\lambda. (The pronunciation of λμ\lambda\lhd\mu as “λ\lambda is sharply smaller than μ\mu” is, I think, rather unhelpful in this regard, but I haven’t heard any other suggestions either.)

In fact, although I have never seen this in print, I believe that fact (3) above is actually an if-and-only-if. That is, if every μ\mu-presentable object of a locally λ\lambda-presentable category can be written as a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects, then λμ\lambda\lhd\mu. The standard set-theoretic definition of λμ\lambda\lhd\mu is that for any set XX with cardinality |X|<μ|X|\lt\mu, the poset P λ(X)P_\lambda(X) of subsets of cardinality <λ\lt\lambda has a μ\mu-small cofinal subset. Now consider the category SetSet, in which the μ\mu-presentable objects are the sets of cardinality <μ\lt\mu; thus if every μ\mu-presentable object of SetSet can be written as a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects, then whenever |X|<μ|X|\lt\mu we have Xcolim iIX iX\cong \colim_{i\in I} X_i where II is μ\mu-small and λ\lambda-filtered and each |X i|<λ|X_i|\lt\lambda. Let AA be the μ\mu-small set of all the images q i(X i)Xq_i(X_i) \subseteq X of the coprojections q i:X iXq_i:X_i\to X, each of which is λ\lambda-small. Then AA is cofinal in P λ(X)P_\lambda(X), since for any λ\lambda-small subset YXY\subseteq X the inclusion YXY\hookrightarrow X must factor through some X iX_i (since YY is λ\lambda-presentable and the colimit is λ\lambda-filtered), hence Yq i(X i)Y \subseteq q_i(X_i).

Since it’s known that λμ\lambda\le\mu does not imply λμ\lambda\lhd\mu, we can transport such a counterexample (e.g. 2.13(8) in AR) to construct an explicit counterexample to Myth A. Let α\alpha be any infinite cardinal, such as 0\aleph_0, and λ=α +\lambda = \alpha^+, which is regular. Let β\beta be a cardinal of cofinality α\alpha — e.g. if α= 0\alpha=\aleph_0 then we could take β= ω\beta = \aleph_\omega — and set μ=β +\mu = \beta^+. Let XX be a set of cardinality β\beta; then XX is μ\mu-presentable in SetSet, but it is not a μ\mu-small λ\lambda-filtered colimit of λ\lambda-presentable objects.

To see this, note that since β\beta has cofinality α\alpha, we can write X= n<αX nX = \bigcup_{n\lt\alpha} X_n where each X nX_n has cardinality |X n|<β|X_n|\lt \beta. Suppose X=colim iIY iX = \colim_{i\in I} Y_i for a μ\mu-small category II and λ\lambda-presentable sets Y iY_i; we will show II is not λ\lambda-filtered. Since II is μ\mu-small, it has cardinality β\le \beta, so we can choose a surjection f:Xob(I)f:X\to ob(I). Since each |X n|<β|X_n|\lt\beta, the set of objects {f(x)xX n}ob(I)\{f(x) \mid x\in X_n\}\subseteq ob(I) also has cardinality <β\lt\beta, and since each Y iY_i also has cardinality <λ\lt\lambda, the subset W n= xX nq f(x)(Y f(x))XW_n = \bigcup_{x\in X_n} q_{f(x)}(Y_{f(x)}) \subseteq X (where q i:Y iXq_i:Y_{i}\to X is the colimit coprojection) has cardinality <βλ=β\lt \beta\cdot\lambda = \beta.

Since XX has cardinality β\beta, there is some element of XW nX\setminus W_n; define g:αXg:\alpha \to X such that g(n)XW ng(n)\in X\setminus W_n for all nn. Since α\alpha is a λ\lambda-presentable set, if the colimit were λ\lambda-filtered then gg would factor through some Y iY_i. But then there would be an xXx\in X with f(x)=if(x) = i, and an n<αn\lt\alpha with xX nx\in X_n, so that gg is contained in W nW_n, contradicting our choice of gg such that g(n)W ng(n) \notin W_n.

So Myth A is false. Myth B is also false; a counterexample from Remark 3.2(4) of Abstract elementary classes and accessible categories by Beke and Rosicky is the endofunctor of SetSet defined by F(X)=X IF(X) = X^I for any infinite set II. Namely, let α=|I|\alpha = |I|, let β\beta be any cardinal of cofinality α\alpha, and let μ=β +\mu=\beta^+. Then μ\mu is regular, but FF does not preserve μ\mu-presentable objects. Specifically, let XX be of cardinality β\beta (hence is μ\mu-presentable); I claim |F(X)|>β|F(X)|\gt \beta, hence is not μ\mu-presentable.

I guess this is a fairly standard fact in cardinal arithmetic, but not being an expert in that subject, I found it helpful to spell out the relevant “diagonal argument”. Note first that the cofinality assumption implies that X= iIX iX = \bigcup_{i\in I} X_i with |X i|<β|X_i|\lt \beta. Suppose for contradiction we have a surjection f:XF(X)=X If:X\to F(X) = X^I; define g:IXg:I\to X as follows. Given ii, the set B i={f(x)(i)xX i}XB_i = \{f(x)(i) \mid x\in X_i \}\subseteq X has cardinality |X i|<β\le |X_i| \lt\beta. Choose g(i)XB ig(i) \in X \setminus B_i, which is nonempty since |X|=β>|B i||X|=\beta \gt |B_i|. Then gX Ig\in X^I cannot be in the image of ff, since if f(x)=gf(x) = g then xX ix\in X_i for some ii, hence g(i)=f(x)(i)B ig(i) = f(x)(i) \in B_i, contradicting our choice of g(i)g(i).

So far I’ve found half a dozen claims on the Internet and in published papers that amount to Myth A and/or Myth B, sometimes leading to incorrect statements. But I will not point any specific fingers — except at myself! In Theorem 3.1 of arXiv:1307.6248 I claimed that some functor preserves κ\kappa-presentable objects for all cardinal numbers κ>|𝒞|\kappa\gt |\mathcal{C}|, which is not in fact the case. This was pointed out to me by Raffael Stenzel, and in trying to figure out exactly what was true in that case, I realized it was an instance of Myth B and started noticing these myths in other places too.

Fortunately, appeals to these myths can almost always be replaced by the true facts (3) and (4) above, at the cost of sometimes changing the statements of theorems. Our first thought about how to phrase them might be “there are arbitrarily large regular cardinals μ\mu such that…”, but there is a problem with this. Namely, suppose I have a couple lemmas, say Lemma 1 and Lemma 2, that both begin with a quantification like this, and now I want to use them both to prove a theorem. Almost certainly I’ll need to find one regular cardinal μ\mu that satisfies both Lemma 1 and Lemma 2. But simply knowing that there are arbitrarily large μ\mu satisfying Lemma 1, and arbitrarily large μ\mu satisfying Lemma 2, doesn’t tell me that there are arbitrarily large (or indeed even any) μ\mu that satisfy both.

Now this isn’t a very big problem, because for any set of regular cardinals λ i\lambda_i there are arbitrarily large regular cardinals μ\mu such that λ iμ\lambda_i \lhd \mu for all ii. This follows from the same argument: whenever ν\nu is such that λ iν\lambda_i \le \nu for all ii, then λ i(2 ν) +\lambda_i \lhd (2^\nu)^+ for all ii. But it means that the statements of our lemmas need to be stronger: instead of “there are arbitrarily large regular cardinals μ\mu such that…” we should say “there is a regular cardinal λ\lambda such that for any regular cardinal μ\mu with μλ\mu\rhd\lambda, …”.

This phrasing is admittedly a bit unlovely, but I think it can be made slightly nicer. Define a class of regular cardinals to be sharply large if it contains a class of the form {μμλ}\{ \mu \mid \mu \rhd \lambda \} for some λ\lambda. Then we can state our lemmas as “there is a sharply large class of regular cardinals μ\mu such that …”, or even “the class of regular cardinals μ\mu such that … is sharply large”. And when putting together multiple lemmas to prove a theorem, we can just use the fact that the intersection of any set of sharply large classes is again sharply large — in other words, the sharply large classes form a “set-complete filter” on the class of regular cardinals.

Posted at March 14, 2019 9:29 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3097

3 Comments & 0 Trackbacks

Re: The Myths of Presentability and the Sharply Large Filter

Some random comments:

I don’t think you gave a definition of “λ\lambda-accessible category” (as in fact 3) when you defined all the other things. Or maybe you wanted to say “λ\lambda-presentable” there?

Lurie has similar statements in his development of accessible \infty-categories in HTT, though (if I remember correctly) his version of the “sharp inequality” is defined a little differently than the one in AR.

If 3 really is an if-and-only-if, then I would want to call \unlhd the “accessibility partial ordering” of regular cardinals, since then λμ\lambda\unlhd \mu if and only if every λ\lambda-accessible category is μ\mu-accessible.

Posted by: Charles Rezk on March 16, 2019 4:17 PM | Permalink | Reply to this

Re: The Myths of Presentability and the Sharply Large Filter

Yes, I neglected to define accessible categories, but I might as well have said “locally λ\lambda-presentable” in fact 3 since the post is mainly about that case. Accessible categories are “like locally presentable ones, but need not be complete and cocomplete”. Facts 1, 3, and 4 are all true about accessible categories, but not I believe fact 2 since an accessible category doesn’t necessarily have enough non-filtered colimits.

And yes, Lurie uses a version of the sharp inequality that’s a priori a bit stronger, but apparently GCH implies that they coincide. I haven’t tried to figure out whether the ordinary version of the sharp inequality would also work in the \infty-category case.

“Accessibility partial ordering” isn’t bad. Would you then suggest something like “accessibly large” instead of “sharply large” for the associated filter? (It’s unfortunate, though, that “accessible” and “inaccessible” have very little to do with each other…)

Posted by: Mike Shulman on March 17, 2019 4:30 AM | Permalink | Reply to this

Re: The Myths of Presentability and the Sharply Large Filter

I’m surprised nobody called me on this yet:

A cardinal number λ\lambda is regular if the union of <λ\lt\lambda sets of cardinality <λ\lt\lambda still has cardinality <λ\lt\lambda. Any successor cardinal (i.e. one of the form α+1\aleph_{\alpha+1}) is regular, and ZFC does not prove there exist any others.

… except for 0\aleph_0.

… and 11 and 22.

Posted by: Mike Shulman on March 22, 2019 12:43 AM | Permalink | Reply to this

Post a New Comment