+ +-for all `s1`, `s2`, `s3` in `S`: -(i) `s1*s2` etc are also in `S` -(ii) `(s1*s2)*s3` = `s1*(s2*s3)` -(iii) `z*s1` = `s1` = `s1*z` -

+ for all s1, s2, s3 in S: + (i) s1*s2 etc are also in S + (ii) (s1*s2)*s3 = s1*(s2*s3) + (iii) z*s1 = s1 = s1*z +Some examples of monoids are: @@ -39,15 +40,15 @@ Categories ---------- A **category** is a generalization of a monoid. A category consists of a class of **elements**, and a class of **morphisms** between those elements. Morphisms are sometimes also called maps or arrows. They are something like functions (and as we'll see below, given a set of functions they'll determine a category). However, a single morphism only maps between a single source element and a single target element. Also, there can be multiple distinct morphisms between the same source and target, so the identity of a morphism goes beyond its "extension." -When a morphism `f` in category **C** has source `C1` and target `C2`, we'll write `f:C1->C2`. +When a morphism `f` in category

+-(i) the class of morphisms has to be closed under composition: where `f:C1->C2` and `g:C2->C3`, `g o f` is also a morphism of the category, which maps `C1->C3`. -(ii) composition of morphisms has to be associative -(iii) every element `E` of the category has to have an identity morphism 1_{E}, which is such that for every morphism `f:C1->C2`: 1_{C2}o f = f = f o 1_{C1}-

+ (i) the class of morphisms has to be closed under composition: where f:C1->C2 and g:C2->C3, g o f is also a morphism of the category, which maps C1->C3. + (ii) composition of morphisms has to be associative + (iii) every element E of the category has to have an identity morphism 1These parallel the constraints for monoids. Note that there can be multiple distinct morphisms between an element `E` and itself; they need not all be identity morphisms. Indeed from (iii) it follows that each element can have only a single identity morphism. @@ -70,16 +71,18 @@ Some examples of categories are: Functors -------- -A **functor** is a "homomorphism", that is, a structure-preserving mapping, between categories. In particular, a functor `F` from category **C** to category **D** must: +A **functor** is a "homomorphism", that is, a structure-preserving mapping, between categories. In particular, a functor `F` from category_{E}, which is such that for every morphism f:C1->C2: 1_{C2}o f = f = f o 1_{C1}+

+ (i) associate with every element C1 of-A functor that maps a category to itself is called an **endofunctor**. The (endo)functor that maps every element and morphism of **C** to itself is denoted `1C`. +A functor that maps a category to itself is called an **endofunctor**. The (endo)functor that maps every element and morphism ofCan element F(C1) ofD+ (ii) associate with every morphism f:C1->C2 ofCa morphism F(f):F(C1)->F(C2) ofD+ (iii) "preserve identity", that is, for every element C1 ofC: F of C1's identity morphism inCmust be the identity morphism of F(C1) inD: F(1_{C1}) = 1_{F(C1)}. + (iv) "distribute over composition", that is for any morphisms f and g inC: F(g o f) = F(g) o F(f) +