Properties of $\mathbf{Cat}$

Let $\mathbf{Cat}$ be the category of small categories.

(1) Is $\mathbf{Cat}$ complete?

(2) Is $\mathbf{Cat}$ cocomplete?

Remark(Jan. 11, 2013) Of course, the question is implicitly asking for a proof if the answer is affirmative. It's easy to see that $\mathbf{Cat}$ has products and equalizers. Hence it is complete. However, I'm not sure it is cocomplete. Since it clearly has coproducts, the question is reduced to whether it has coequalizers or not. Let $F, G \colon \mathcal{C} \rightarrow \mathcal{D}$ be functors. Ittay Weiss wrote that a coequalizer is the quotient of $\mathcal{D}$ by the congruence generated by equating $F(X)$ with $G(X)$. It is easy to define the congruence on $Ob(\mathcal{D})$ generated by equating $F(X)$ with $G(X)$. However, I have no idea how to define the congruence on $Mor(\mathcal{D})$ generated by equating $F(X)$ with $G(X)$.

Edit(Jan. 17, 2013) To the downvoters, why don't you reset your votes? The question is clearly important in category theory. I know you don't like me, but the question has nothing to do with your liking towards me. I'm saying this not because I care reps, but because the negative votes are sending wrong signals to the users.

Solution 1:

$Cat$ is both small complete and small cocomplete. It is not large complete nor large cocomplete since it is not a poset.

The only non-trivial part of the proof of small completeness and small cocompleteness is the construction of coequalizers. An explicit, and rather elementary, construction of coequalizers is given in the article generalized congruences; epis in Cat, TAC 1999. The notion of coequalizer (as well as that of epi) in the category of small categories was proved to be non-elementary (in a precise logic theoretic meaning) by John Isbell in 1968 in the article "Epimorphisms and dominions III".

Solution 2:

Theorem. The category $\mathsf{Cat}$ of small categories is complete and cocomplete.

Proof. If $\{C_i\}_{i \in I}$ is a small diagram of categories, then define their limit $C$ by $\mathrm{Ob}(C) = \mathrm{lim}_i \mathrm{Ob}(C_i)$ and $\mathrm{Mor}(C) = \mathrm{lim}_i \mathrm{Mor}(C_i)$, with the obvious source, target and identity maps induced by the ones of the $C_i$ and the functoriality of $\lim$. Similarily, if $f = (f_i) : (x_i) \to (y_i)$ and $g = (g_i) : (y_i) \to (z_i)$ are composable morphisms, define $g \circ f = (g_i \circ f_i)$. It is easy to verify that $C$ is, in fact, a category, and that the obvious projections $C \to C_i$ satisfy the universal property of a limit.

The construction of $\mathrm{colim}_i C_i$ is more subtle. Consider the functor $\mathsf{Cat} \to \mathsf{Set}$, $C \mapsto \lim_i \hom(C_i,C)$. We want to show that it is representable, using Freyd's Representability Criterion (Mac Lane, Categories for the Working Mathematician, Theorem V.6.3). We already know that $\mathsf{Cat}$ is complete, and the functor is obviously continuous. Therefore, it suffices to verify the solution set condition.

Consider the cardinal $\kappa = \aleph_0 \cdot \sum\limits_{i \in I} \# \mathrm{Mor}(C_i)$. Let $S$ be the set (!) of all categories whose object and morphism sets are subsets of $\kappa$. Observe that every category with $\# \mathrm{Mor} \leq \kappa$ is isomorphic to some category in $S$.

Let $\{F_i : C_i \to C\}$ be a compatible family of functors. Define a subcategory $C' \subseteq C$ as follows. Objects are those of the form $F_i(x)$ with $x$ is an object of $C_i$ and $i \in I$. A morphism in $C'$ is a morphism in $C$ which can be factored as $y_0 \to y_1 \to \dotsc \to y_n$, where each $y_j \to y_{j+1}$ lies in the image of some $F_i$. We allow $n=0$, which corresponds to the identity morphism. Clearly, $C'$ is a subcategory of $C$, and each $F_i$ factors through $C'$. The family $\{C_i \to C'\}$ is still compatible since $C'$ is a subcategory of $C$. Now basic cardinal arithmetic gives us $\# \mathrm{Mor}(C') \leq \sum_{n \in \mathbb{N}} \kappa^n = \kappa$. Hence, $C'$ is isomorphic to some object in $S$ and we are done. $ ~~\square$

Remark. The same proof can be used to show that $\mathrm{Mod}(T)$ is complete and cocomplete, where $T$ is an algebraic theory. But I don't think that $\mathsf{Cat}$ is algebraic, because the composition is only defined partially.

Perhaps $\mathrm{Mor} : \mathsf{Cat} \to \mathsf{Set}$ is monadic? A theorem of Linton (see Coequalizers in categories of algebras) says that $\mathsf{Mod}(T)$ is complete and cocomplete for every monad $T$ on $\mathsf{Set}$.

Solution 3:

Awodey goes into some detail on the construction of congruences, generators and coequalizers in Cat in chap. 4. Exercises 6-8 address the same matter. These exercises (and others) are solved here:

http://www.andrew.cmu.edu/course/80-413-713/hw/sol.pdf

Solution 4:

At the end of this very long an clumsy answer, I recall a very interesting general construction of lax, pseudo and strict (co)limits in $\mathbf{Cat}$, which I learned from Jean Benabou.