# Definition of the subcategory in book "Category Theory for Computing Science"

The subcategory is defined in the book "Category Theory for Computing Science" as follows: (https://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf)

2.6.1 Definition A subcategory $$\mathscr{D}$$ of a category $$\mathscr{C}$$ is a category for which:

S–1 All the objects of $$\mathscr{D}$$ are objects of $$\mathscr{C}$$ and all the arrows of $$\mathscr{D}$$ are arrows of $$\mathscr{C}$$ (in other words, $$\mathscr{D}_0$$$$\mathscr{C}_0$$ and $$\mathscr{D}_1$$$$\mathscr{C}_1$$).

S–2 The source and target of an arrow of $$\mathscr{D}$$ are the same as its source and target in $$\mathscr{C}$$ (in other words, the source and target maps for $$\mathscr{D}$$ are the restrictions of those for $$\mathscr{C}$$). It follows that for any objects A and B of $$\mathscr{D}$$, Hom$$_\mathscr{D}$$ (A, B) ⊆ Hom$$_\mathscr{C}$$ (A, B).

S–3 If A is an object of $$\mathscr{D}$$ then its identity arrow id$$_A$$ in $$\mathscr{C}$$ is in $$\mathscr{D}$$.

S–4 If f:A → B and g:B → C in $$\mathscr{D}$$, then the composite (in $$\mathscr{C}$$) g◦f is in $$\mathscr{D}$$ and is the composite in $$\mathscr{D}$$.

I wonder why S-2, S-3, and S-4 are required. Couldn't they be derived from D being a category and S-1?

• Presumably the authors take a stance where a category is some collection of objects, some collection of arrows, and then some extra data telling you which of the arrows are identities, how to compose arrows, etc. In particular, this data is not "attached" to the arrows themselves, so it's not enough to just specify you want a subcollection of the arrows and objects; you also need to explicitly say that you want to carry over all of the structure, too. Commented Jun 24 at 16:07
• This type of thing is not unique to category theory. For example, a subset of a group which itself forms a group need not be a subgroup; for it to be a subgroup you need to know that its operations (product, identity, inverse) are the restrictions of those on the original group. Commented Jun 24 at 16:17

It seems like there may still be some lingering confusion despite the other answers so I'm just adding this to complement them.

To see why the conditions for subcategory are necessary, you need to look back at their definition of category $$\mathscr{C}$$ which is a graph (directed, multi, with loops) together with operations defining composite and identity arrows which satisfy certain properties. If you look back at their definition of graph, you'll see that it consists of objects (nodes) $$C_0$$ and arrows (edges) $$C_1$$ together with two functions $$\mathop{\mathrm{source}}:C_1\to C_0\quad\text{and}\quad\mathop{\mathrm{target}}:C_1\to C_0$$

Importantly, source and target objects are not "intrinsic" to an arrow! They're assigned by these two functions! Similarly the identity function for the category $$1_{(-)}:C_0\to C_1$$ assigns an identity arrow to each object, so the identity arrow for an object is not "intrinsic" to that object.

So the whole category is really a giant tuple $$\mathscr{C}=(C_0,C_1,\mathop{\mathrm{source}},\mathop{\mathrm{target}},1_{(-)},\circ)$$ where here $$\circ:C_2\to C_1$$ denotes the composition function defined on pairs of composable arrows. (I can't bring myself to use their exact notation.)

Now for another category $$\mathscr{D}$$ to be a subcategory of $$\mathscr{C}$$, it's not enough that $$D_0\subseteq C_0$$ and $$D_1\subseteq C_1$$, you also need to know that the operations in $$\mathscr{D}$$ (source, target, identity, composite) are the restrictions of the corresponding operations in $$\mathscr{C}$$, because again that information is not intrinsic to the objects and arrows themselves. That's exactly what their conditions for subcategory say.

• I finally realized what I had been thinking wrong. Until you pointed it out, I thought an arrow had a source and a target object. I was convinced. Thank you all very much. Commented Jun 25 at 2:01

Here is a (hopefully helpful) example, building on @blargoner's comment. You may know that any group $$G$$ can be viewed as a category, where there is a single object and there is one morphism for each element of $$G$$. Composition of morphisms corresponds to multiplication in the group.

Consider the category $$C_n$$ corresponding to the cyclic group of order $$n$$. Then we can view $$C_2$$ as sitting inside $$C_3$$ and satisfying S-1: there is only one object in each category, so that's easy, and then just match up the morphisms in $$C_2$$ with two of the three morphisms in $$C_3$$. S-1 and S-2 will be satisfied, but unless you chose carefully, S-3 may not be, and S-4 certainly will not be. In the group-as-category setting, subcategories (satisfying all four properties) will correspond precisely to subgroups.

• I understand that S-1 alone may not satisfy S-4. However, I am still unconvinced about S-2 and S-3. Is the following idea wrong? For any f ∈ D1, since D1 ⊆ C1 (S-1), f ∈ C1. Because f in D is equal to f in C, it stands to reason that the respective sources and targets are equal. Besides, by assumption, D is a category, so if A ∈ D0 then naturally idA ∈ D1. Then it follows that idA ∈ C1 since D1 ⊆ C1 (S-1). Therefore, S-2 and S-3 are not required. Commented Jun 24 at 21:25
• When you write down '$\text{id} A$', you need to specify which category you're working in. The whole point is that $\text{id}^D A$ may not be the same element of $C_1$ as $\text{id}^C A$, unless you require it. Commented Jun 24 at 22:18
• For example, suppose that $C$ is a category with one object $X$ and two morphisms $1_X : X \to X$ (the identity morphism of $X$ in $C$) and $a: X \to X$, with $a \circ a = a$. Let $D$ be the subcategory consisting of the object $X$ and the morphism $a$, which we now declare to be the identity morphism for $X$ in $D$. Then S-1, S_2, and S-4 are satisfied, but not S-3. Commented Jun 24 at 22:21

All that S-1 requires is that the collection of objects (resp. morphisms) of $$\mathcal{D}$$ be "less" than or equal to that of $$\mathcal{C}$$, in the sense of cardinality. For example, if $$\mathcal{C}$$ is the discrete category on three objects $$\{a, b, c\}$$ with only the identity morphisms $$\{1_a, 1_b, 1_c\}$$, you can consider the following pathological example for $$\mathcal{D}$$:

$$a \overset{1_c}{\to} b$$

Here we've just technically reused the morphisms and objects of $$\mathcal{C}$$ to build $$\mathcal{D}$$, but they don't inherit their categorical role from $$\mathcal{C}$$: $$1_c$$ is not the identity of any object in $$\mathcal{D}$$.

In this example, $$\mathcal{D}$$ is not a subcategory of $$\mathcal{C}$$ in any reasonable sense, hence the need for a better definition.

• Not sure about the downvote--the example is correct, but it's of course not true that a subcategory has to be smaller than the supercategory in cardinality, any moreso than is true for a subset. Commented Jun 24 at 17:09
• @KevinCarlson You're right, I meant $\leq$. Edited. Commented Jun 24 at 17:18
• That's still pretty unusual phrasing--there are many ways for $A$ to be a subset of $B$ even once you know $|A|\le |B|$--but fair enough. Commented Jun 24 at 22:34