2.5.12 Exercises
1. Show that the composite of semigroup (respectively monoid) homomorph-isms is a semigroup (respectively monoid) homomorphism.
2. Prove Proposition 2.5.10.
3. Prove Proposition 2.5.11.
4.† Exhibit two distinct isomorphisms between the monoid with underly-ing set{0,1,2,3} and addition (mod 4) as operation and the monoid with underlying set{1,2,3,4} and multiplication (mod 5) as operation.
5. Using the terminology of 2.5.7, show that iff is an isomorphism then so isf∗.
2.6 Constructions on categories
If you are familiar with some branch of abstract algebra (for example the the-ory of semigroups, groups or rings) then you know that given two structures of a given type (e.g., two semigroups), you can construct a ‘direct product’
structure, defining the operations coordinatewise. Also, a structure may have substructures, which are subsets closed under the operations, and quotient structures, formed from equivalence classes modulo a congruence relation.
Another construction that is possible in many cases is the formation of a
‘free’ structure of the given type for a given set.
All these constructions can be performed for categories. We will outline the constructions here, except for quotients, which will be described in Sec-tion 3.5. We will also describe the construcSec-tion of the slice category, which does not quite correspond to anything in abstract algebra (although it is akin to the adjunction of a constant to a logical theory). You do not need to be familiar with the constructions in other branches of abstract algebra, since they are all defined from scratch here.
2.6.1 Definition A subcategory D of a category C is a category for which:
S–1 All the objects ofD are objects ofC and all the arrows ofDare arrows ofC (in other words,D0⊆C0 andD1⊆C1).
S–2 The source and target of an arrow ofD are the same as its source and target inC (in other words, the source and target maps forD are the restrictions of those forC). It follows that for any objectsAand B of D, HomD(A, B)⊆HomC(A, B).
S–3 IfAis an object ofD then its identity arrow idAinC is inD.
S–4 Iff :A−→B andg:B−→C inD, then the composite (in C)g◦f is in Dand is the composite inD.
2.6.2 Examples As an example, the category Fin of finite sets and all functions between them is a subcategory ofSet, and in turn Setis a sub-category of the sub-category of sets andpartialfunctions between sets (see 2.1.12 and 2.1.13). These examples illustrate two phenomena:
(i) If A and B are finite sets, then HomFin(A, B) = HomSet(A, B). In other words, every arrow ofSetbetween objects ofFinis an arrow of Fin.
(ii) The category of sets and the category of sets and partial functions, on the other hand, have exactly the sameobjects. The phenomenon of (i) does not occur here: there are generallymany more partial functions between two sets than there are full functions.
Example (i) motivates the following definition.
2.6.3 Definition IfDis a subcategory ofC and for every pair of objects A,B ofD, HomD(A, B) = HomC(A, B), thenD is afull subcategory of C.
ThusFinis a full subcategory ofSet butSet is not a full subcategory of the category of sets and partial functions.
Example 2.6.2(ii) also motivates a (less useful) definition, as follows.
2.6.4 Definition IfD is a subcategory of C with the same objects, then Dis a widesubcategory ofC.
Thus in the case of a wide subcategory, only the arrows are different from those of the larger category. In 2.7.13 we provide an improvement on this concept.
As an example,Set is a wide subcategory of the categoryPfn of sets and partial functions.
2.6.5 Example Among all the objects of the category of semigroups are the monoids, and among all the semigroup homomorphisms between two monoids are those that preserve the identity. Thus the category of monoids is a subcategory of the category of semigroups that is neither wide nor full (for the latter, see 2.5.4).
As it stands, being a subcategory requires the objects and arrows of the subcategory to be identical with some of the objects and arrows of the category containing it. This requires an uncategorical emphasis on what something is instead of on the specification it satisfies. We will return to this example in 2.8.13 and again in 3.1.7.
2.6 Constructions on categories 37 2.6.6 The product of categories IfC andDare categories, the prod-uctC×Dis the category whose objects are all ordered pairs (C, D) withC an object ofC andD an object ofD, and in which an arrow (f, g) : (C, D)
−→(C0, D0) is a pair of arrowsf :C−→C0 inC andg:D−→D0 inD. The identity of (C, D) is (idC,idD). If (f0, g0) : (C0, D0)−→(C00, D00) is another arrow, then the composite is defined by
(f0, g0)◦(f, g) = (f0◦f, g0◦g) : (C, D)−→(C00, D00)
2.6.7 The dual of a category Given any categoryC, you can construct another category denoted Cop by reversing all the arrows. The dual or oppositeCopof a category C is defined by:
D–1 The objects and arrows ofCop are the objects and arrows ofC. D–2 Iff :A−→B inC, thenf :B−→Ain Cop.
D–3 Ifh=g◦f inC, thenh=f ◦g inCop.
The meaning of D–2 is that source and target have been reversed. It is easy to see that the identity arrows have to be the same in the two categories C andCop and that C–1 through C–4 of Section 2.1 hold, so thatCop is a category.
2.6.8 Example IfM is a monoid, then the opposite of the categoryC(M) is the category determined by a monoidMop; ifxy=z in M, then yx=z inMop. (Hence if M is commutative thenC(M) is its own dual. Compare Exercise 6 of 3.3.) Similar remarks may be made about the opposite of the categoryC(P) determined by a posetP. The opposite of the poset (Z,≤), for example, is (Z,≥).
2.6.9 Both the construction of the product of two categories and the con-struction of the dual of a category are purely formal concon-structions. Even though the original categories may have, for example, structure-preserving functions of some kind as arrows, the arrows in the product category are simply pairs of arrows of the original categories.
Consider Set, for example. Let A be the set of letters of the English alphabet. The functionv:A−→ {0,1}that takes consonants to 0 and vowels to 1 is an arrow ofSet. Then the arrow (idA, v) : (A, A)−→(A,{0,1}) of Set×Setis not a function, not even a function of two variables; it is merely the arrow of a product category and as such is an ordered pair of functions.
A similar remark applies to duals. InSetop,v is an arrow from{0,1}to A. And that is all it is. It is in particularnot a function from{0,1}toA.
Nevertheless, it is possible in some cases to prove that the dual of a familiar category is essentially the same as some other familiar category.
One such category isFin, see 3.4.6.
The product of categories is a formal way to make constructions depen-dent on more than one variable. The major use we make of the concept of dual is that many of the definitions we make have another meaning when applied to the dual of a category that is often of independent interest. The phrasedual conceptor dual notionis often used to refer to a concept or notion applied in the dual category.
2.6.10 Slice categories If C is a category and A any object of C, the slice categoryC/Ais described this way:
SC–1 An object ofC/Ais an arrowf :C−→AofC for some objectC.
SC–2 An arrow ofC/A fromf :C −→A tof0 :C0−→Ais an arrow h:C
−→C0with the property thatf =f0◦h.
SC–3 The composite ofh:f −→f0 andh0:f0−→f00 ish0◦h.
It is necessary to show that h0 ◦h, as defined in SC–2, satisfies the re-quirements of being an arrow fromf tof00. Leth:f −→f0andh0:f0−→f00. This meansf0◦h=f andf00◦h0=f0. To show that h0◦h:f −→f00 is an arrow ofC/A, we must show that f00◦(h0◦h) =f. That follows from this calculation:
f00◦(h0◦h) = (f00◦h0)◦h=f0◦h=f
The usual notation for arrows inC/Ais deficient: the same arrowhcan satisfyf =f0◦handg=g0◦hwithf 6=gor f06=g0 (or both). Thenh:f
−→f0 andh:g−→g0aredifferent arrows ofC/A.
2.6.11 The importance of slice categories comes in part with their connec-tion with indexing. AnS-indexed set is a setX together with a function τ:X−→S. Ifx∈X andτ(x) =sthen we say xis of types, and we also refer toX as atyped set.
The terminology ‘S-indexed set’ is that used by category theorists. Many mathematicians would cast the discussion in terms of the collection{τ−1(s)| s∈S} of subsets of X, which would be called a family of sets indexed byS.
2.6.12 Example The set G=G0∪G1 of objects and arrows of a graph G is an example of a typed set, typed by the functionτ :G−→ {0,1} that takes a node to 0 and an arrow to 1. Note that this depends on the fact that a node is not an arrow:G0andG1are disjoint.
2.6.13 Indexed functions A function from a setX typed byS to a set X0 typed by the same set S that preserves the typing (takes an element of type s to an element of type s) is exactly an arrow of the slice category Set/S. Such a function is called anindexed functionortyped function.
2.6 Constructions on categories 39 It has been fruitful for category theorists to pursue this analogy by thinking of objects of any slice categoryC/Aas objects ofC indexed byA.
2.6.14 Example A graph homomorphism f : G −→ H corresponds to a typed function according to the construction in Example 2.6.12. How-ever, there are typed functions between graphs that are not graph homo-morphisms, for example the function from the graph (1.1), page 9, to the graph (1.3), page 10, defined by
17→1,27→n, a7→0, b7→0, c7→succ
This is not a graph homomorphism because it does not preserve source and target.
2.6.15 Example Let (P, α) be a poset and letC(P) be the corresponding category as in 2.3.1. For an elementx∈P, the slice categoryC(P)/xis the category corresponding to the set of elements greater than or equal tox.
The dual notion of coslice gives the set of elements less than or equal to a given element.
2.6.16 The free category generated by a graph For any given graph G there is a category F(G) whose objects are the nodes of G and whose arrows are the paths inG. Composition is defined by the formula
(f1, f2, . . . , fk)◦(fk+1, . . . , fn) = (f1, f2, . . . , fn)
This composition is associative, and for each objectA, idAis the empty path from A to A. The category F(G) is called the free category generated by the graphG. It is also called thepath categoryofG.
2.6.17 Examples The free category generated by the graph with one node and no arrows is the category with one object and only the identity arrow, which is the empty path. The free category generated by the graph with one node and one loop on the node is the free monoid with one generator (Kleene closure of a one-letter alphabet); this is isomorphic with the nonnegative in-tegers with + as operation.
The free category generated by the graph in Example 1.3.8 has the fol-lowing arrows
(a) An arrow id1: 1−→1.
(b) For each nonnegative integer k, the arrow succk :n−→n. This is the path (succ,succ, . . . ,succ) (koccurrences ofsucc). This includesk= 0 which gives idn.
(c) For each nonnegative integerk, the arrowsucck◦0 : 1−→n. Herek= 0 gives 0 : 1−→n.
Composition obeys the rulesucck ◦succm=succk+m.
2.6.18 It is useful to regard the free category generated by any graph as analogous to Kleene closure (free monoid) generated by a set (as in 2.3.9).
The paths in the free category correspond to the strings in the Kleene closure.
The difference is that you can concatenate any symbols together to get a string, but arrows can be strung together only head to tail, thus taking into account the typing.
In 13.2.3 we give a precise technical meaning to the word ‘free’.
2.6.19 Exercises
1. LetM be a monoid. Show that the opposite of the categoryC(M) deter-mined byM is also the category determined by a monoid, calledMop. 2. Do the same as the preceding exercise for posets.
3. Give examples of posetsP,QandRfor whichC(P) (the category deter-mined by the poset) is a wide but not full subcategory ofC(Q) andC(P) is a full but not wide subcategory ofC(R).
4.† Show by example that the requirement S–3 in 2.6.1 does not follow from the other requirements.