Skip to main content

Computable categories

So I read a bit about categories after Peter Hines came up to talk to us.


A category C is a collection of objects obj(C) (or just Obj), a collection of arrows (or morphisms) hom(C) (or just Hom), and an arrow composition operation such that there is an identity arrow for each object.

An arrow has a single source object and a single target object, and is written AfB.

The composition operation joins up pairs of arrows when possible and a category is closed under arrow composition, so if AfB, BgC, then there is an arrow AgfC.

Arrow composition is associative, so (fg)h=f(gh).

A functor F is a structure-preserving map between categories. So F:CD maps Xobj(C) to F(X)obj(Y), and fhom(X) to F(f)hom(Y). Structure-preserving means we require that F(fg)=F(f)F(g).

Groups and categories

Any group can be thought of as a category – there is one object, and the arrows are the group elements. You could associate to each element g an automorphism of the group ϕg:GG, ϕg(x)=gx. There is an identity arrow (the identity element), and the composition operation is the group multiplication, which is associative.

Suppose you have two groups. You can make a category with them both in, just by taking the disjoint union of the respective individual categories. If you have a homorphism between the two groups, you can add that in as an arrow and everything still works – if you have gG,hH,ϕ:GH then hϕg is equal to the arrow associated with the element hϕ(g).

If you have another arrow going the other way from H to G, that looks just like a free product with amalgamation, right? And why not have loads of groups with all sorts of homomorphisms going between them? Fgoagog!

One of the things I was going to look at next was other kinds of group extensions apart from Bass-Serre graphs of groups. If I phrase the computability stuff in terms of categories, then all you have to do is say what the homomorphisms are and I can construct a computable function representing the group.

Computable categories

So I need to define a computable category.

A category C=(Obj,Hom,circ) is En-computable if:

  • There is an En-decidable indexing o:ObjN of the objects.
  • There is an En-decidable indexing i:HomN of the arrows.
  • There are En-computable functions ι:i(Hom)o(Obj) and τ:i(Hom)o(Obj) associating with each arrow its source and terminal objects.
  • There is an En-computable composition function c:i(Hom)×i(Hom)i(Hom) satisfying c(i(f),i(g))=i(fg).

All of o,i,ι,τ and c together is called an En-computable index of C.

Given two En computable categories C and D, a functor F:CD is Em-computable if there exist Em-computable functions oF:oC(obj(C))oD(obj(D)) and iF:iC(hom(C))iD(hom(D)).

So, my first task will be to rewrite the index for the free group in this category language, which should carry across directly. Then, for any finitely-presented group G, I can write down the functor mapping the appropriate free group to G. To get the fundamental group of a graph of groups, I just need to extend the index a bit and define how the composition function acts on the edge homomorphisms. After that, we’ll see about pregroups!