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 \(\circ\) 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 \(A \overset{f}{\rightarrow} B\).

The composition operation joins up pairs of arrows when possible and a category is closed under arrow composition, so if \(A \overset{f}{\rightarrow} B\), \(B \overset{g}{\rightarrow} C\), then there is an arrow \(A \overset{g \circ f}{\rightarrow} C\).

Arrow composition is associative, so \((f \circ g) \circ h = f \circ (g \circ h)\).

A functor \(F\) is a structure-preserving map between categories. So \(F: C \rightarrow D\) maps \(X \in obj(C)\) to \(F(X) \in obj(Y)\), and \(f \in hom(X)\) to \(F(f) \in hom(Y)\). Structure-preserving means we require that \(F(f \circ g) = F(f) \circ 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 \(\phi_g : G \rightarrow G\), \(\phi_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 \(g \in G, h \in H, \phi: G \rightarrow H\) then \(h \circ \phi \circ g\) is equal to the arrow associated with the element \(h \phi(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 \(E_n\)-computable if:

  • There is an \(E_n\)-decidable indexing \(o: Obj \rightarrow \mathbb{N}\) of the objects.
  • There is an \(E_n\)-decidable indexing \(i: Hom \rightarrow \mathbb{N}\) of the arrows.
  • There are \(E_n\)-computable functions \(\iota : i(Hom) \rightarrow o(Obj)\) and \(\tau : i(Hom) \rightarrow o(Obj)\) associating with each arrow its source and terminal objects.
  • There is an \(E_n\)-computable composition function \(c: i(Hom) \times i(Hom) \rightarrow i(Hom)\) satisfying \(c( i(f), i(g) ) = i(f \circ g)\).

All of \(o, i, \iota, \tau\) and \(c\) together is called an \(E_n\)-computable index of \(C\).

Given two \(E_n\) computable categories \(C\) and \(D\), a functor \(F: C \rightarrow D\) is \(E_m\)-computable if there exist \(E_m\)-computable functions \(o_F : o_C(obj(C)) \rightarrow o_D(obj(D))\) and \(i_F : i_C(hom(C)) \rightarrow i_D(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!