```+	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: - (a) finite strings of an alphabet A, with * being concatenation and z being the empty string +* finite strings of an alphabet `A`, with `*` being concatenation and `z` being the empty string +* all functions `X->X` over a set `X`, with `*` being composition and `z` being the identity function over `X` +* the natural numbers with `*` being plus and `z` being `0` (in particular, this is a **commutative monoid**). If we use the integers, or the naturals mod n, instead of the naturals, then every element will have an inverse and so we have not merely a monoid but a **group**.) +* if we let `*` be multiplication and `z` be `1`, we get different monoids over the same sets as in the previous item. - (b) all functions X->X over a set X, with * being composition and z being the identity function over X +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." - (c) the natural numbers with * being plus and z being 0 (in particular, this is a ). If we use the integers, or the naturals mod n, instead of the naturals, then every element will have an inverse and so we have not merely a monoid but a .) +When a morphism `f` in category C has source `C1` and target `C2`, we'll write `f:C1->C2`. - (d) the natural numbers with * being multiplication and z being 1 constitute a different monoid over the same set as in (c). +To have a category, the elements and morphisms have to satisfy some constraints: +
```+	(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 1E, which is such that for every morphism f:C1->C2: 1C2 o f = f = f o 1C1
+```
+These 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. -2. Categories -------------- -A is a generalization of a monoid. A category consists of a class of elements, and a class of 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 given 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." +A good intuitive picture of a category is as a generalized directed graph, where the category elements are the graph's nodes, and there can be multiple directed edges between a given pair of nodes, and nodes can also have multiple directed edges to themselves. (Every node must have at least one such, which is that node's identity morphism.) -When a morphism f in category C has source c1 and target c2, we'll write f:c1->c2. -To have a category, the elements and morphisms have to satisfy some constraints: - (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 id[e], which is such that for every morphism f:a->b: - id[b] o f = f = f o id[a] +Some examples of categories are: -These 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. +* Categories whose elements are sets and whose morphisms are functions between those sets. Here the source and target of a function are its domain and range, so distinct functions sharing a domain and range (e.g., sin and cos) are distinct morphisms between the same source and target elements. The identity morphism for any element/set is just the identity function for that set. +* any monoid `(S,*,z)` generates a category with a single element `x`; this `x` need not have any relation to `S`. The members of `S` play the role of *morphisms* of this category, rather than its elements. All of these morphisms are understood to map `x` to itself. The result of composing the morphism consisting of `s1` with the morphism `s2` is the morphism `s3`, where `s3=s1*s2`. The identity morphism for the (single) category element `x` is the monoid's identity `z`. -Some examples of categories are: +* a **preorder** is a structure `(S, <=)` consisting of a reflexive, transitive, binary relation on a set `S`. It need not be connected (that is, there may be members `x`,`y` of `S` such that neither `x<=y` nor `y<=x`). It need not be anti-symmetric (that is, there may be members `s1`,`s2` of `S` such that `s1<=s2` and `s2<=s1` but `s1` and `s2` are not identical). Some examples: - (a) any category whose elements are sets and whose morphisms are functions between those sets. Here the source and target of a function are its domain and range, so distinct functions sharing a domain and range (e.g., sin and cos) are distinct morphisms between the same source and target elements. The identity morphism for any element is the identity function over that set. + * sentences ordered by logical implication ("p and p" implies and is implied by "p", but these sentences are not identical; so this illustrates a pre-order without anti-symmetry) + * sets ordered by size (this illustrates it too) - (b) any monoid (S,*,z) generates a category with a single element x; this x need not have any relation to S. The members of S play the role of *morphisms* of this category, rather than its elements. The result of composing the morphism consisting of s1 with the morphism s2 is the morphism s3, where s3=s1+s2. The identity morphism on the (single) category element x is the monoid's identity z. + Any pre-order `(S,<=)` generates a category whose elements are the members of `S` and which has only a single morphism between any two elements `s1` and `s2`, iff `s1<=s2`. - (c) a <= is a binary relation on a set S which is reflexive and transitive. It need not be connected (that is, there may be members x,y of S such that neither x<=y nor y<=x). It need not be anti-symmetric (that is, there may be members s1,s2 of S such that s1<=s2 and s2<=s1 but s1 and s2 are not identical). - Some examples: - * sentences ordered by logical implication ("p and p" implies and is implied by "p", but these sentences are not identical). - * sets ordered by size - Any pre-order (S,<=) generates a category whose elements are the members of S and which has only a single morphism between any two elements s1 and s2, iff s1<=s2. +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: +
```+	(i) associate with every element C1 of C an element F(C1) of D
+	(ii) associate with every morphism f:C1->C2 of C a morphism F(f):F(C1)->F(C2) of D
+	(iii) "preserve identity", that is, for every element C1 of C: F of C1's identity morphism in C must be the identity morphism of F(C1) in D: F(1C1) = 1F(C1).
+	(iv) "distribute over composition", that is for any morphisms f and g in C: F(g o f) = F(g) o F(f)
+```