Re: Category Theory from RFC Walters' book

Re: Category Theory from RFC Walters' book

[puite]

> 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

Re: Category Theory from RFC Walters' book

[Ronnie Brown]

It could be useful to mention the paper

29 #1239 Higgins, Philip J., Algebras with a scheme of operators. Math. Nachr. 27
1963 115--132. (Reviewer: A. Heller) 18.10

which discusses partial algebras at an early date.

Ronnie Brown

Till Mossakowski wrote:

> >It is folklore that the method of generators and relations works for any
> >essentially algebraic theory with finitary operators, as well as for some
> >more general ones. "Algebraic" means defined by operators and equational
> >laws (could be many-sorted); "essentially" means that the operators may be
> >partial, with their domains of definition described by finite sets of
> >equations.
>
> >I wish I knew of an introductory text describing the techniques at this
> >level of generality, but unfortunately I'm not aware of any - maybe somebody
> >can suggest one. Manes's book "Algebraic Theories" is quite good on the
> >algebraic case.
>
> @BOOK{Reichel,
> AUTHOR = "Horst Reichel",
> TITLE ="Initial Computability, Algebraic Specifications and Partial Algebras",
> PUBLISHER = "Oxford Science Publications",
> YEAR = 1987}
>
> contains an elementary introduction to essentially algebraic theories;
> also, the theory of categories is used as an example.
>
> Till Mossakowski
>
> -----------------------------------------------------------------------------
> Till Mossakowski                Phone +49-421-218-4683, monday: +49-4252-1859
> Dept. of Computer Science       Fax +49-421-218-3054
> University of Bremen            till@informatik.uni-bremen.de
> P.O.Box 330440, D-28334 Bremen  http://www.informatik.uni-bremen.de/~till
> -----------------------------------------------------------------------------

--
Prof R. Brown,
School of Informatics, Mathematics Division,
University of Wales, Bangor
Dean St., Bangor,
Gwynedd LL57 1UT, United Kingdom
Tel. direct:+44 1248 382474|office:     382475
fax: +44 1248 361429
World Wide Web:
home page: http://www.bangor.ac.uk/~mas010/
(Links to survey articles:
Higher dimensional group theory
Groupoids and crossed objects in algebraic topology)

Symbolic Sculpture and Mathematics:
http://www.cpm.sees.bangor.ac.uk/sculmath/
Centre for the Popularisation of Mathematics
http://www.cpm.sees.bangor.ac.uk/
Raising Public Awareness of Mathematics
http://www.cpm.sees.bangor.ac.uk/rpamath/

RE: Category Theory from RFC Walters' book

[Steve Vickers]

> 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. 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:
>
> 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.
>
> 2) Given generators and relations are we guaranteed to get a category?

It is folklore that the method of generators and relations works for any
essentially algebraic theory with finitary operators, as well as for some
more general ones. "Algebraic" means defined by operators and equational
laws (could be many-sorted); "essentially" means that the operators may be
partial, with their domains of definition described by finite sets of
equations.

The way the method works is that from the presentation by generators and
relations one can derive a universal property of the desired algebra, so the
problem is whether an algebra does indeed exist with that property. If it
does, then it is unique up to isomorphism.

The theory of categories is essentially algebraic, so generators and
relations for a category do present a category.

I wish I knew of an introductory text describing the techniques at this
level of generality, but unfortunately I'm not aware of any - maybe somebody
can suggest one. Manes's book "Algebraic Theories" is quite good on the
algebraic case.

Here's a sketch of a formal system.

>>>>>>>>>>>>>>>>>>>>>>>>
Terms are of two sorts: object and arrow.

Term formation is by function symbols s, t, i and c, with the obvious
arities, for source, target, identity and composition. (Note at this level
that a term exists for the composite of any two arrows, regardless of
whether they are composable.)

Equality of terms is symmetric and transitive, but _not_ reflexive.

Rules include the following (x and y are objects, f and g are arrows).

  f=g |- s(f)=s(g)
  f=g |- t(f)=t(g)
  x=y |- i(x)=i(y)
  f1=f2, g1=g2, t(f1)=s(g1), t(f2)=s(g2) |- c(f1,g1)=c(f2,g2)

Also rules for the usual equational laws of category theory (associativity
etc.), and

  |- u=u    for each generator u (object or arrow)
  |- r        for each equational relation r

The category is then got by taking all terms z for which z=z, modulo
equality.
<<<<<<<<<<<<<<<<<<

Steve Vickers.