The n-Category Café

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 $\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 $X$ is $\lambda$-presentable (sometimes called “$\lambda$-compact”) if the covariant hom-functor $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 $Cat$) 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 $F$ is an accessible functor, then there is a regular cardinal $\kappa$ such that $F$ 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:\mathcal{C}\to \mathcal{D}$ be an $\lambda$-accessible functor between locally $\lambda$-presentable categories, and let $\kappa$ be such that whenever $X$ is $\lambda$-presentable, $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 $X$ in $\mathcal{C}$ is a $\mu$-small $\lambda$-filtered colimit of $\lambda$-presentable objects, then $F$ preserves this colimit as it is $\lambda$-accessible. Thus $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 $X$ with cardinality $|X|\lt\mu$, the poset $P_\lambda(X)$ of subsets of cardinality $\lt\lambda$ has a $\mu$-small cofinal subset. Now consider the category $Set$, in which the $\mu$-presentable objects are the sets of cardinality $\lt\mu$; thus if every $\mu$-presentable object of $Set$ can be written as a $\mu$-small $\lambda$-filtered colimit of $\lambda$-presentable objects, then whenever $|X|\lt\mu$ we have $X\cong \colim_{i\in I} X_i$ where $I$ is $\mu$-small and $\lambda$-filtered and each $|X_i|\lt\lambda$. Let $A$ be the $\mu$-small set of all the images $q_i(X_i) \subseteq X$ of the coprojections $q_i:X_i\to X$, each of which is $\lambda$-small. Then $A$ is cofinal in $P_\lambda(X)$, since for any $\lambda$-small subset $Y\subseteq X$ the inclusion $Y\hookrightarrow X$ must factor through some $X_i$ (since $Y$ is $\lambda$-presentable and the colimit is $\lambda$-filtered), hence $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 $\aleph_0$, and $\lambda = \alpha^+$, which is regular. Let $\beta$ be a cardinal of cofinality $\alpha$ — e.g. if $\alpha=\aleph_0$ then we could take $\beta = \aleph_\omega$ — and set $\mu = \beta^+$. Let $X$ be a set of cardinality $\beta$; then $X$ is $\mu$-presentable in $Set$, 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 = \bigcup_{n\lt\alpha} X_n$ where each $X_n$ has cardinality $|X_n|\lt \beta$. Suppose $X = \colim_{i\in I} Y_i$ for a $\mu$-small category $I$ and $\lambda$-presentable sets $Y_i$; we will show $I$ is not $\lambda$-filtered. Since $I$ is $\mu$-small, it has cardinality $\le \beta$, so we can choose a surjection $f:X\to ob(I)$. Since each $|X_n|\lt\beta$, the set of objects $\{f(x) \mid x\in X_n\}\subseteq ob(I)$ also has cardinality $\lt\beta$, and since each $Y_i$ also has cardinality $\lt\lambda$, the subset $W_n = \bigcup_{x\in X_n} q_{f(x)}(Y_{f(x)}) \subseteq X$ (where $q_i:Y_{i}\to X$ is the colimit coprojection) has cardinality $\lt \beta\cdot\lambda = \beta$.

Since $X$ has cardinality $\beta$, there is some element of $X\setminus W_n$; define $g:\alpha \to X$ such that $g(n)\in X\setminus W_n$ for all $n$. Since $\alpha$ is a $\lambda$-presentable set, if the colimit were $\lambda$-filtered then $g$ would factor through some $Y_i$. But then there would be an $x\in X$ with $f(x) = i$, and an $n\lt\alpha$ with $x\in X_n$, so that $g$ is contained in $W_n$, contradicting our choice of $g$ such that $g(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 $Set$ defined by $F(X) = X^I$ for any infinite set $I$. Namely, let $\alpha = |I|$, let $\beta$ be any cardinal of cofinality $\alpha$, and let $\mu=\beta^+$. Then $\mu$ is regular, but $F$ does not preserve $\mu$-presentable objects. Specifically, let $X$ be of cardinality $\beta$ (hence is $\mu$-presentable); I claim $|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 = \bigcup_{i\in I} X_i$ with $|X_i|\lt \beta$. Suppose for contradiction we have a surjection $f:X\to F(X) = X^I$; define $g:I\to X$ as follows. Given $i$, the set $B_i = \{f(x)(i) \mid x\in X_i \}\subseteq X$ has cardinality $\le |X_i| \lt\beta$. Choose $g(i) \in X \setminus B_i$, which is nonempty since $|X|=\beta \gt |B_i|$. Then $g\in X^I$ cannot be in the image of $f$, since if $f(x) = g$ then $x\in X_i$ for some $i$, hence $g(i) = f(x)(i) \in B_i$, contradicting our choice of $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 $\lambda_i$ there are arbitrarily large regular cardinals $\mu$ such that $\lambda_i \lhd \mu$ for all $i$. This follows from the same argument: whenever $\nu$ is such that $\lambda_i \le \nu$ for all $i$, then $\lambda_i \lhd (2^\nu)^+$ for all $i$. 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.