Re: Category Theory from RFC Walters' book

[<puite@math.uu.nl>]

> Hello Category Theory community,
> 
> I am rereading RFC Walters' "Categories and Computer Science".
> In chapter 1 Section 3 (starting on pg . 10), Walters discusses the
> the notion of generators and relations to generate categories. He
> gives several examples of this concept. 

On "generators":
Given a graph (set of objects and set of (formal) arrows between objects),
the original objects together with the finite *paths* (f,g,h,...,k) in 
this graph (as morphisms) constitute a category (called 
the "free category on this graph"):
    - identities are the empty paths;
    - composition is concatenation of paths.

On "relations":
Given a category and a relation R on its arrows (i.e. a subset of A x A)
relating only arrows with the same domain and codomain, let R' be the
smallest congruence relation containing R.
  [A congruence relation S is an equivalence relation (i.e. S is 
   reflexive, symmetric and transitive) that moreover 
   is closed under composition: aSb and cSd imply (a.c)S(b.d).]
  [Check that the " *smallest* congruence relation containing R " 
   is a well-defined notion, as the class of congruence relations containing R
   is closed under arbitrary intersections. So the intersection of those
   congruence relations containing R is also a congruence relation 
   containing R, indeed the smallest one.]
Now the original objects together with the congruence classes [f] of R' 
(as morphisms) constitute a category (called the quotient category):
    - identities are the classes of the identities [1];
    - the composite [f].[g] is by definition [f.g], which is well-defined.

There is a more explicit/constructive description of R' in terms of R.
Consider the following relation:
aR"b  iff  there exist n \geq 0 and an n-chain: 
           (n+1) morphisms  a_0, a_1, ..., a_n such that
              a = a_0;  
              a_n = b;  
              for all 0 \leq i < n there are morphisms u,v,c,d such that
                 a_i = u.c.v and a_{i+1} = u.d.v  and  either cRd  or  dRc
This clearly is a congruence relation containing R, whence R' \subseteq R".
The other way around, you show by induction on n that every n-chain is
between R'-congruent formulas. Hence R' = R".

There is much more to say about presentations in general, but I hope the
above details for categories answer your questions. 
Let me briefly return to your specific example:

> E.g. "Example 15. Consider
> the category presented by one object A, one arrow e:A->A, and the
> one relation e.e.e.e = 1subA. From this, he deduces by hand the
> category has additional arrows e .e, e.e.e. I have two questions:

Observe that the free category on this graph (one object, one arrow)
has infinitely many arrows:  (); (e); (e,e); (e,e,e); (e,e,e,e); ...
Let us denote them by e^0, e^1, e^2, e^3, e^4, ... 
Recall that these arrows are actually the paths in the graph, and 
that they are all different!
According to your example R = { (e^4,e^0) }.
Check that R' = R" = { (e^n,e^m) | n-m is a 4-fold }.
Check that there are only four congruence classes in the quotient
category: [e^0], [e^1], [e^2], [e^3].
An example of a composite: [e^2].[e^3] = [e^2.e^3] = [e^5] = [e^1].
 
> 1) Walters shows that e.e.e = e is not "deducible". What kind of
>      formal system/inference rule system is "at  work" here that
>      allows us to deduce
>      formally any additional arrows and allows us to deduce
>      arrow relations from the "axiom" relation, i.e. e.e.e.e = 1subA??
>     Is this some kind of equational logic? Please specify in detail.

You do not deduce additional arrows; the arrows are the original paths.
R' can be described by the following deductive system:
  axioms: the instances of R and reflexivity;
  rules:  symmetry, transitivity, closure.

> 2) Given generators and relations are we guaranteed to get a category?

Yes, since we agreed upon considering the smallest congruence relation 
containing your relations.

Regards, 

Quintijn Puite