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

index 41b17c5..3c80bbb 100644 (file)
@@ -1,7 +1,9 @@
**Don't try to read this yet!!! Many substantial edits are still in process.
Will be ready soon.**

-**Caveats**: I really don't know much category theory. Just enough to put this
+Caveats
+-------
+I really don't know much category theory. Just enough to put this
together. Also, this really is "put together." I haven't yet found an
authoritative source (that's accessible to a category theory beginner like
myself) that discusses the correspondence between the category-theoretic and
@@ -26,24 +28,25 @@ A **monoid** is a structure `(S, *, z)` consisting of an associative binary oper

Some examples of monoids are:

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

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 `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:c1->c2:
-               id[c2] o f = f = f o id[c1]
+       (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]

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

@@ -52,31 +55,28 @@ Some examples of categories are:

*      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 is the identity function over 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.
+*      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`.

-*      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).
+*      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:

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

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

3. 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 `C` to category `D` must:

-<OL type=i>
-<LI>associate with every element c1 of C an element F(c1) of D
-<LI>associate with every morphism f:c1->c2 of C a morphism F(f):F(c1)->F(c2) of D
-<LI>"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)].
-<LI>"distribute over composition", that is for any morphisms f and g in C:
-               F(g o f) = F(g) o F(f)
-</OL>
+       (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)].
+       (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`.

@@ -90,53 +90,54 @@ I'll assert without proving that functor composition is associative.
-------------------------
So categories include elements and morphisms. Functors consist of mappings from the elements and morphisms of one category to those of another (or the same) category. **Natural transformations** are a third level of mappings, from one functor to another.

-Where G and H are functors from category C to category D, a natural transformation eta between G and H is a family of morphisms eta[c1]:G(c1)->H(c1) in D for each element c1 of C. That is, eta[c1] has as source c1's image under G in D, and as target c1's image under H in D. The morphisms in this family must also satisfy the constraint:
+Where `G` and `H` are functors from category `C` to category `D`, a natural transformation `eta` between `G` and `H` is a family of morphisms `eta[c1]:G(c1)->H(c1)` in `D` for each element `c1` of `C`. That is, `eta[c1]` has as source `c1`'s image under `G` in `D`, and as target `c1`'s image under `H` in `D`. The morphisms in this family must also satisfy the constraint:
+
for every morphism f:c1->c2 in C:
eta[c2] o G(f) = H(f) o eta[c1]

-That is, the morphism via G(f) from G(c1) to G(c2), and then via eta[c2] to H(c2), is identical to the morphism from G(c1) via eta[c1] to H(c1), and then via H(f) from H(c1) to H(c2).
+That is, the morphism via `G(f)` from `G(c1)` to `G(c2)`, and then via `eta[c2]` to `H(c2)`, is identical to the morphism from `G(c1)` via `eta[c1]` to `H(c1)`, and then via `H(f)` from `H(c1)` to `H(c2)`.

How natural transformations compose:

-Consider four categories B,C,D, and E.
-Let F be a functor from B to C; G,H, and J be functors from C to D; and K and L be functors from D to E. Let eta be a natural transformation from G to H; phi be a natural transformation from H to J; and psi be a natural transformation from K to L. Pictorally:
+Consider four categories `B`, `C`, `D`, and `E`. Let `F` be a functor from `B` to `C`; `G`, `H`, and `J` be functors from `C` to `D`; and `K` and `L` be functors from `D` to `E`. Let `eta` be a natural transformation from `G` to `H`; `phi` be a natural transformation from `H` to `J`; and `psi` be a natural transformation from `K` to `L`. Pictorally:
+
+       - B -+ +--- C --+ +---- D -----+ +-- E --
+                | |        | |            | |
+        F: ------> G: ------>     K: ------>
+                | |        | |  | eta     | |  | psi
+                | |        | |  v         | |  v
+                | |    H: ------>     L: ------>
+                | |        | |  | phi     | |
+                | |        | |  v         | |
+                | |    J: ------>         | |
+       -----+ +--------+ +------------+ +-------

-- B -+ +--- C --+ +---- D -----+ +-- E --
-     | |        | |            | |
- F: ------> G: ------>     K: ------>
-     | |        | |  | eta     | |  | psi
-     | |        | |  v         | |  v
-     | |    H: ------>     L: ------>
-     | |        | |  | phi     | |
-     | |        | |  v         | |
-     | |    J: ------>         | |
------+ +--------+ +------------+ +-------
+Then `(eta F)` is a natural transformation from the (composite) functor `GF` to the composite functor `HF`, such that where `b1` is an element of category `B`, `(eta F)[b1] = eta[F(b1)]`---that is, the morphism in `D` that `eta` assigns to the element `F(b1)` of `C`.

-Then (eta F) is a natural transformation from the (composite) functor GF to the composite functor HF, such that where b1 is an element of category B, (eta F)[b1] = eta[F(b1)]---that is, the morphism in D that eta assigns to the element F(b1) of C.
+And `(K eta)` is a natural transformation from the (composite) functor `KG` to the (composite) functor `KH`, such that where `c1` is an element of category `C`, `(K eta)[c1] = K(eta[c1])`---that is, the morphism in `E` that `K` assigns to the morphism `eta[c1]` of `D`.

-And (K eta) is a natural transformation from the (composite) functor KG to the (composite) functor KH, such that where c1 is an element of category C, (K eta)[c1] = K(eta[c1])---that is, the morphism in E that K assigns to the morphism eta[c1] of D.

+`(phi -v- eta)` is a natural transformation from `G` to `J`; this is known as a "vertical composition". We will rely later on this, where `f:c1->c2`:

-(phi -v- eta) is a natural transformation from G to J; this is known as a "vertical composition". We will rely later on this, where f:c1->c2:
phi[c2] o H(f) o eta[c1] = phi[c2] o H(f) o eta[c1]
-                               -------------
-               by naturalness of phi, is:
-                               --------------
+
+by naturalness of phi, is:
+
phi[c2] o H(f) o eta[c1] = J(f) o phi[c1] o eta[c1]
-              --------------
-               by naturalness of eta, is:
-                 --------------
+
+by naturalness of eta, is:
+
phi[c2] o eta[c2] o G(f) = J(f) o phi[c1] o eta[c1]
-    -----------------                 -----------------
-Hence, we can define (phi -v- eta)[c1] as: phi[c1] o eta[c1] and rely on it to satisfy the constraints for a natural transformation from G to J:
-    -----------------                 -----------------
+
+Hence, we can define `(phi -v- eta)[c1]` as: `phi[c1] o eta[c1]` and rely on it to satisfy the constraints for a natural transformation from `G` to `J`:
+
(phi -v- eta)[c2] o G(f) = J(f) o (phi -v- eta)[c1]

I'll assert without proving that vertical composition is associative and has an identity, which we'll call "the identity transformation."

-(psi -h- eta) is natural transformation from the (composite) functor KG to the (composite) functor LH; this is known as a "horizontal composition." It's trickier to define, but we won't be using it here. For reference:
+`(psi -h- eta)` is natural transformation from the (composite) functor `KG` to the (composite) functor `LH`; this is known as a "horizontal composition." It's trickier to define, but we won't be using it here. For reference:

(phi -h- eta)[c1]  =  L(eta[c1]) o psi[G(c1)]
=  psi[H(c1)] o K(eta[c1])
@@ -145,11 +146,11 @@ Horizontal composition is also associative, and has the same identity as vertica