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

Categories

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\stackrel{f}{\to }B$.

The composition operation joins up pairs of arrows when possible and a category is closed under arrow composition, so if $A\stackrel{f}{\to }B$, $B\stackrel{g}{\to }C$, then there is an arrow $A\stackrel{g\circ f}{\to }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\to 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 ${\varphi }_g:G\to G$, ${\varphi }_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,\varphi :G\to H$ then $h\circ \varphi \circ g$ is equal to the arrow associated with the element $h\varphi (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\to \mathbb{N}$ of the objects.
• There is an $E_n$-decidable indexing $i:Hom\to \mathbb{N}$ of the arrows.
• There are $E_n$-computable functions $\iota :i(Hom)\to o(Obj)$ and $\tau :i(Hom)\to 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)\to 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\to D$ is $E_m$-computable if there exist $E_m$-computable functions $o_F:o_C(obj(C))\to o_D(obj(D))$ and $i_F:i_C(hom(C))\to 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!