author Jim Pryor Tue, 2 Nov 2010 12:00:27 +0000 (08:00 -0400) committer Jim Pryor Tue, 2 Nov 2010 12:00:27 +0000 (08:00 -0400)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

index 25528cb..0c139c6 100644 (file)
@@ -21,10 +21,12 @@ Monoids
-------
A **monoid** is a structure `(S, *, z)` consisting of an associative binary operation `*` over some set `S`, which is closed under `*`, and which contains an identity element `z` for `*`. That is:

-       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
+<blockquote><pre>
+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`
+</pre></blockquote>

Some examples of monoids are:

@@ -41,11 +43,13 @@ When a morphism `f` in category **C** has source `C1` and target `C2`, we'll wri

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:C1->C2: id[C2] o f = f = f o id[C1]
+<blockquote><pre>
+(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<sub>E</sub>, which is such that for every morphism `f:C1->C2`: 1<sub>C2</sub> o f = f = f o 1<sub>C1</sub>
+</pre></blockquote>

-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.
+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.

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.)

@@ -70,7 +74,7 @@ A **functor** is a "homomorphism", that is, a structure-preserving mapping, betw

(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(id[C1]) = id[F(C1)].
+       (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(1<sub>C1</sub>) = 1<sub>F(C1)</sub>.
(iv) "distribute over composition", that is for any morphisms f and g in **C**: F(g o f) = F(g) o F(f)

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`.
@@ -211,8 +215,8 @@ The standard category-theory presentation of the monad laws
In category theory, the monad laws are usually stated in terms of `unit` and `join` instead of `unit` and `<=<`.

(*
-       P2. every element C1 of a category **C** has an identity morphism id[C1] such that for every morphism f:C1->C2 in **C**: id[C2] o f = f = f o id[C1].
-       P3. functors "preserve identity", that is for every element C1 in F's source category: F(id[C1]) = id[F(C1)].
+       P2. every element C1 of a category **C** has an identity morphism 1<sub>C1</sub> such that for every morphism f:C1->C2 in **C**: 1<sub>C2</sub> o f = f = f o 1<sub>C1</sub>.
+       P3. functors "preserve identity", that is for every element C1 in F's source category: F(1<sub>C1</sub>) = 1<sub>F(C1)</sub>.
*)

Let's remind ourselves of some principles: