Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

Exercise 42 - Chapter 3 : The category of categories

edited June 2018

Back in the primordial ooze, there is a category Cat in which the objects are themselves categories.

Your task here is to construct this category.

1. Given any category $$\mathcal{C}$$, show that there exists a functor $$id_C : \mathcal{C} \rightarrow \mathcal{C}$$, known as the identity functor on $$\mathcal{C}$$, that maps each object to itself and each morphism to itself.
2. Note that a functor $$\mathcal{C} \rightarrow \mathcal{D}$$ consists of a function from $$Ob(\mathcal{C})$$ to $$Ob(\mathcal{D})$$ and for each pair of objects $$c_1 , c_2 \in \mathcal{C}$$ a function from $$\mathcal{C}(c_1 , c_2 )$$ to $$\mathcal{D}(F(c_1 ), F(c_2 ))$$.
3. Show that given $$F : \mathcal{C} \rightarrow \mathcal{D}$$ and $$G : \mathcal{D} \rightarrow \mathcal{E}$$, we can define a new functor $$F.G : \mathcal{C} \rightarrow \mathcal{E}$$ just by composing functions.
4. Show that there is a category, call it Cat, where the objects are categories, morphisms are functors, and identities and composition are given as above.

• Options
1.
edited August 2018
1. The definition above satisfies the requirements (in Def. 3.34) for defining a candidate for a functor, so only the two conditions must be checked. $$\forall c\in\mathcal{C}$$, $$\mathrm{id}_\mathcal{C}(\mathrm{id}_c)=\mathrm{id}_c=\mathrm{id}_{\mathrm{id}_\mathcal{C}(c)}$$. $$\mathrm{id}_\mathcal{C}(g\circ f)=g\circ f=\mathrm{id}_\mathcal{C}(g)\circ\mathrm{id}_\mathcal{C}(f)$$. So, the identity map is a functor.

2. Functors will be morphisms in Cat, so for composition to be defined it will be necessary that the sets of objects and morphisms match.

3. Let $$f_\mathrm{Ob}:\mathrm{Ob}(\mathcal{C})\to\mathrm{Ob}(\mathcal{D})$$, be the object function for $$F$$, $$f_{\mathrm{Mor}(c_1,c_2)}:\mathcal{C}(c_1,c_2)\to\mathcal{D}(F(c_1),F(c_2))$$, be the morphism function (one for each, possibly trivial, pair of objects in $$\mathcal{C}$$), and $$g_\mathrm{Ob}$$, $$g_{\mathrm{Mor}(d_1,d_2)}$$ be the corresponding functions for $$G$$. $$g_\mathrm{Ob}\circ f_\mathrm{Ob}:\mathrm{Ob}(\mathcal{C})\to\mathrm{Ob}(\mathcal{E})$$. Setting $$F(c_1)=d_1$$ and $$F(c_2)=d_2$$, one has that $$g_{\mathrm{Mor}(d_1,d_2)}\circ f_{\mathrm{Mor}(c_1,c_2)}:\mathcal{C}(c_1,c_2)\to\mathcal{E}(G(d_1),G(d_2))$$ $$=\mathcal{E}(G(F(c_1)),G(F(c_2)))$$. So, composing the functions associated with the functors yields functions for a candidate to be a functor (from $$\mathcal{C}$$ to $$\mathcal{E}$$). Since $$F$$ and $$G$$ are functors, $$f_{\mathrm{Mor}(c,c)}(\mathrm{id}_c)=\mathrm{id}_{f_\mathrm{Ob}(c)}$$ and $$g_{\mathrm{Mor}(d,d)}(\mathrm{id}_d)=\mathrm{id}_{g_\mathrm{Ob}(d)}$$ for all $$c\in\mathcal{C}$$ and $$d\in\mathcal{D}$$. Take $$d=f_\mathrm{Ob}(c)$$ and $$e=g_\mathrm{Ob}(d)$$, then $$g_{\mathrm{Mor}(d,d)}(f_{\mathrm{Mor}(c,c)}(\mathrm{id}_c))$$ $$=g_{\mathrm{Mor}(d,d)}(\mathrm{id}_{f_\mathrm{Ob}(c)})$$ $$=g_{\mathrm{Mor}(d,d)}(\mathrm{id}_d)$$ $$=\mathrm{id}_{g_\mathrm{Ob}(d)}$$ $$=\mathrm{id}_e$$ $$=\mathrm{id}_{(g_\mathrm{Ob}\circ f_\mathrm{Ob})(c)}$$. Since $$F$$ and $$G$$ are functors, $$f_{\mathrm{Mor}(c_1,c_3)}(h\circ k)$$ $$=f_{\mathrm{Mor}(c_2,c_3)}(h)\circ f_{\mathrm{Mor}(c_1,c_2)}(k)$$ and $$g_{\mathrm{Mor}(d_1,d_3)}(h'\circ k')$$ $$=g_{\mathrm{Mor}(d_2,d_3)}(h')\circ g_{\mathrm{Mor}(d_1,d_2)}(k')$$, for all $$c_1,c_2,c_3\in\mathcal{C}$$, $$h\in\mathcal{C}(c_2,c_3)$$, $$k\in\mathcal{C}(c_2,c_3)$$, $$d_1,d_2,d_3\in\mathcal{D}$$, $$h'\in\mathcal{D}(d_2,d_3)$$, and $$k'\in\mathcal{D}(d_2,d_3)$$. Let $$e_i=g_\mathrm{Ob}(d_i)=g_\mathrm{Ob}(f_\mathrm{Ob}(c_i))\,\,i\in\{1,2,3\}$$, $$k'=f_{\mathrm{Mor}(c_1,c_2)}(k)$$, $$h'=f_{\mathrm{Mor}(c_2,c_3)}(h)$$, $$k''=g_{\mathrm{Mor}(d_1,d_2)}(k')$$, $$h''=g_{\mathrm{Mor}(d_2,d_3)}(h)$$. $$(g\circ f)_{\mathrm{Mor}(c_1,c_3)}(h\circ k)$$ $$=g_{\mathrm{Mor}(d_1,d_3)}(f_{\mathrm{Mor}(c_2,c_3)}(h)\circ f_{\mathrm{Mor}(c_1,c_2)}(k))$$ $$=g_{\mathrm{Mor}(d_1,d_3)}(h'\circ k')$$ $$=g_{\mathrm{Mor}(d_2,d_3)}(h)\circ g_{\mathrm{Mor}(d_1,d_2)}(k')$$ $$=h''\circ k'')$$, where $$k'':e_1\to e_2$$ and $$h'': e_2\to e_3$$. So, $$G\circ F$$ is a functor (from $$\mathcal{C}$$ to $$\mathcal{E}$$).

4. The collection of objects is the collection of (small) categories. The set of morphisms for each pair of objects is the set of functors between each pair of (small) categories. Existence of identities and composites was checked in 1. and 3. above. So, it is enough to check unitality and associativity. Let $$F:\mathcal{C}\to\mathcal{D}$$ be a functor. $$\mathrm{id}_\mathcal{D}\circ F$$ $$=F$$ $$=F\circ\mathrm{id}_\mathcal{C}$$, since the identity functors do nothing to their categories (i.e., the functions that they are associated with are identity functions, and so compose trivially, giving the same function they started with. So, the the same is true for the identity functors.). Associativity of functor composition follows from the associativity of function composition for the object and morphism functions. Thus, Cat is a category.

Comment Source:1. The definition above satisfies the requirements (in Def. 3.34) for defining a candidate for a functor, so only the two conditions must be checked. \$$\forall c\in\mathcal{C}\$$, \$$\mathrm{id}\_\mathcal{C}(\mathrm{id}\_c)=\mathrm{id}\_c=\mathrm{id}\_{\mathrm{id}\_\mathcal{C}(c)}\$$. \$$\mathrm{id}\_\mathcal{C}(g\circ f)=g\circ f=\mathrm{id}\_\mathcal{C}(g)\circ\mathrm{id}\_\mathcal{C}(f)\$$. So, the identity map is a functor. 2. Functors will be morphisms in **Cat**, so for composition to be defined it will be necessary that the sets of objects and morphisms match. 3. Let \$$f_\mathrm{Ob}:\mathrm{Ob}(\mathcal{C})\to\mathrm{Ob}(\mathcal{D})\$$, be the object function for \$$F\$$, \$$f_{\mathrm{Mor}(c_1,c_2)}:\mathcal{C}(c_1,c_2)\to\mathcal{D}(F(c_1),F(c_2))\$$, be the morphism function (one for each, possibly trivial, pair of objects in \$$\mathcal{C}\$$), and \$$g_\mathrm{Ob}\$$, \$$g_{\mathrm{Mor}(d_1,d_2)}\$$ be the corresponding functions for \$$G\$$. \$$g_\mathrm{Ob}\circ f_\mathrm{Ob}:\mathrm{Ob}(\mathcal{C})\to\mathrm{Ob}(\mathcal{E})\$$. Setting \$$F(c_1)=d_1\$$ and \$$F(c_2)=d_2\$$, one has that \$$g_{\mathrm{Mor}(d_1,d_2)}\circ f_{\mathrm{Mor}(c_1,c_2)}:\mathcal{C}(c_1,c_2)\to\mathcal{E}(G(d_1),G(d_2))\$$ \$$=\mathcal{E}(G(F(c_1)),G(F(c_2)))\$$. So, composing the functions associated with the functors yields functions for a candidate to be a functor (from \$$\mathcal{C}\$$ to \$$\mathcal{E}\$$). Since \$$F\$$ and \$$G\$$ are functors, \$$f\_{\mathrm{Mor}(c,c)}(\mathrm{id}\_c)=\mathrm{id}\_{f\_\mathrm{Ob}(c)}\$$ and \$$g\_{\mathrm{Mor}(d,d)}(\mathrm{id}\_d)=\mathrm{id}\_{g\_\mathrm{Ob}(d)}\$$ for all \$$c\in\mathcal{C}\$$ and \$$d\in\mathcal{D}\$$. Take \$$d=f_\mathrm{Ob}(c)\$$ and \$$e=g_\mathrm{Ob}(d)\$$, then \$$g\_{\mathrm{Mor}(d,d)}(f\_{\mathrm{Mor}(c,c)}(\mathrm{id}\_c))\$$ \$$=g\_{\mathrm{Mor}(d,d)}(\mathrm{id}\_{f\_\mathrm{Ob}(c)})\$$ \$$=g\_{\mathrm{Mor}(d,d)}(\mathrm{id}\_d)\$$ \$$=\mathrm{id}\_{g\_\mathrm{Ob}(d)}\$$ \$$=\mathrm{id}\_e\$$ \$$=\mathrm{id}\_{(g\_\mathrm{Ob}\circ f_\mathrm{Ob})(c)}\$$. Since \$$F\$$ and \$$G\$$ are functors, \$$f_{\mathrm{Mor}(c_1,c_3)}(h\circ k)\$$ \$$=f_{\mathrm{Mor}(c_2,c_3)}(h)\circ f_{\mathrm{Mor}(c_1,c_2)}(k)\$$ and \$$g_{\mathrm{Mor}(d_1,d_3)}(h'\circ k')\$$ \$$=g_{\mathrm{Mor}(d_2,d_3)}(h')\circ g_{\mathrm{Mor}(d_1,d_2)}(k')\$$, for all \$$c_1,c_2,c_3\in\mathcal{C}\$$, \$$h\in\mathcal{C}(c_2,c_3)\$$, \$$k\in\mathcal{C}(c_2,c_3)\$$, \$$d_1,d_2,d_3\in\mathcal{D}\$$, \$$h'\in\mathcal{D}(d_2,d_3)\$$, and \$$k'\in\mathcal{D}(d_2,d_3)\$$. Let \$$e_i=g_\mathrm{Ob}(d_i)=g_\mathrm{Ob}(f_\mathrm{Ob}(c_i))\,\,i\in\\{1,2,3\\}\$$, \$$k'=f_{\mathrm{Mor}(c_1,c_2)}(k)\$$, \$$h'=f_{\mathrm{Mor}(c_2,c_3)}(h)\$$, \$$k''=g_{\mathrm{Mor}(d_1,d_2)}(k')\$$, \$$h''=g_{\mathrm{Mor}(d_2,d_3)}(h)\$$. \$$(g\circ f)\_{\mathrm{Mor}(c\_1,c_3)}(h\circ k)\$$ \$$=g_{\mathrm{Mor}(d_1,d_3)}(f_{\mathrm{Mor}(c_2,c_3)}(h)\circ f_{\mathrm{Mor}(c_1,c_2)}(k))\$$ \$$=g_{\mathrm{Mor}(d_1,d_3)}(h'\circ k')\$$ \$$=g_{\mathrm{Mor}(d_2,d_3)}(h)\circ g_{\mathrm{Mor}(d_1,d_2)}(k')\$$ \$$=h''\circ k'')\$$, where \$$k'':e_1\to e_2\$$ and \$$h'': e_2\to e_3\$$. So, \$$G\circ F\$$ is a functor (from \$$\mathcal{C}\$$ to \$$\mathcal{E}\$$). 4. The collection of objects is the collection of (small) categories. The set of morphisms for each pair of objects is the set of functors between each pair of (small) categories. Existence of identities and composites was checked in 1. and 3. above. So, it is enough to check unitality and associativity. Let \$$F:\mathcal{C}\to\mathcal{D}\$$ be a functor. \$$\mathrm{id}\_\mathcal{D}\circ F\$$ \$$=F\$$ \$$=F\circ\mathrm{id}_\mathcal{C}\$$, since the identity functors do nothing to their categories (i.e., the functions that they are associated with are identity functions, and so compose trivially, giving the same function they started with. So, the the same is true for the identity functors.). Associativity of functor composition follows from the associativity of function composition for the object and morphism functions. Thus, **Cat** is a category.