# 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.

-
(I'm voting to leave open.) –  rschwieb Jan 9 '13 at 20:12
I noticed a tremendously distracting amount of chaff here, so I removed it. Makoto, if you feel like you have more to say, I recommend opening a dedicated chat room. If you something in particular to ask the community, I would say that you should make or find the appropriate meta post (I presume you know much about this). Don't clutter the main site with accusations that other questions had similar demonstrations of OP effort and yet did not get downvoted, or bickerings with the community, or whatnot. –  mixedmath Jan 10 '13 at 20:51
He has explained the deletion. Any further comments continuing to clutter the main site will be removed as well. –  Mariano Suárez-Alvarez Jan 11 '13 at 4:51
A rather detailed construction of coequalizers seems to be given here: Bednarzyk, Borzyszkowski, Pawlowski, Concrete (co)constructions in the category of small categories. –  Martin Jan 11 '13 at 5:06
@Martin Thank you so much. –  Makoto Kato Jan 11 '13 at 6:03

$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".

-
Maybe all that could have done so decided not to. –  Mariano Suárez-Alvarez Jan 10 '13 at 21:00
Ittay: I commend your patience, and I upvoted your answer. I would like to add that at a Q&A site such as this one, there are any number of reasons why someone would or would not answer or help a question asker. For example, I would understand if you were to never help or answer a question from Makoto again, especially if he offends you. –  mixedmath Jan 10 '13 at 21:04
@mixedmath Please be aware that there may be many people who want to know answers to my questions. –  Makoto Kato Jan 10 '13 at 21:28
@Makoto Kato: To be fair: it seems to me that Mac Lane sketches everything needed to establish the existence of colimits in sections II.7 and II.8 of his book. Similar descriptions are given by Gabriel-Zisman in their book on calculus of fractions. I linked to that article in order to calm down the debate, not to provide you with a pretext to heaten it up again. I think insisting that Ittay Weiss was wrong or careless (implicit in your comments) is unnecessary. He gave a two-line answer to what initially was a three-line question, so it seems this aggressive tone is uncalled-for. –  Martin Jan 11 '13 at 19:43
@MakotoKato For the time being I abandon the construction since I don't have time right now to do it properly. Please refrain from pinging me on this or any subject. I would also appreciate it if you don't stalk my activity on the site nor scold me for not distributing my time according to your priorities. –  Ittay Weiss Jan 25 '13 at 9:04

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}$.

-
unfortunately Cat is not monadic over Set. You proof is a nice application of the Adjoint Functor Theorem that avoids the details of the direct constructions of coequalizers! –  Ittay Weiss Jan 13 '13 at 20:08
@IttayWeiss You know that the adjoint functor theorem is non-trivial while the quotient categories defined by Mac Lane Chapter II is not. –  Makoto Kato Jan 14 '13 at 0:17
@ Makoto Kato, I'm not sure what you mean by that comment. Can you please explain how does it relate to my comment? –  Ittay Weiss Jan 14 '13 at 0:27
@IttayWeiss Before I explain, I would like to know if you agree with my comment or not. By the way, please don't place a space between the first and the last names of mine. If you do, I may not notice your comment to me. –  Makoto Kato Jan 14 '13 at 0:49
Just read Mac Lane, it is not that hard. It starts with the observation that a complete category $C$ with a weakly initial set $S$ has an initial object (just take the limit of $S \to C$!). Applying this to the category of elements $\int F$ for a functor $F : C \to \mathsf{Set}$ gives Freyd's criterion for representability. And this is what I need in the proof, not the Adjoint Functor Theorem (which also follows by applying the observation to certain slice categories). –  Martin Brandenburg Jan 14 '13 at 16:39

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

-
Dear Magma, Thanks for your contribution. Since some readers might miunderstand, please forgive me to state this again. The Awodey's definition of a congruence is not sufficient for constructing a coequalizer in $\mathbf{Cat}$ in general. The correct definition of the congruence is defined in the following artice. Bednarzyk, Borzyszkowski, Pawlowski, Concrete (co)constructions in the category of small categories.citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.5522 –  Makoto Kato Jan 12 '13 at 23:19
In fact, the link only contains basic material about special(!) quotient categories also explained in the second chapter of Mac Lane's book. This doesn't answer the question. –  Martin Brandenburg Jan 13 '13 at 1:35
Dear @MakotoKato I am not able to access the BBP article. If you consider that it has the correct definition of congruence, I would be very interested to see it. You could post it as an answer to your own question (this is a perfectly accepted practice) and I would be more than happy to upvote your answer. –  magma Jan 13 '13 at 20:04
@magma You can search for the BBP article by its title using Google. Then you will find a postscript file of it. You can read it online, though you may not download it. –  Makoto Kato Jan 13 '13 at 20:41
@MakotoKato got it, thanks –  magma Jan 13 '13 at 21:26
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.