# Computable categories

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\left(C\right)$ (or just Obj), a collection of arrows (or morphisms) $hom\left(C\right)$ (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 $\left(f\circ g\right)\circ h=f\circ \left(g\circ h\right)$.

A functor $F$ is a structure-preserving map between categories. So $F:C\to D$ maps $X\in obj\left(C\right)$ to $F\left(X\right)\in obj\left(Y\right)$, and $f\in hom\left(X\right)$ to $F\left(f\right)\in hom\left(Y\right)$. Structure-preserving means we require that $F\left(f\circ g\right)=F\left(f\right)\circ F\left(g\right)$.

## 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}\left(x\right)=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 \left(g\right)$.

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=\left(Obj,Hom,circ\right)$ 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\left(Hom\right)\to o\left(Obj\right)$ and $\tau :i\left(Hom\right)\to o\left(Obj\right)$ associating with each arrow its source and terminal objects.
• There is an ${E}_{n}$-computable composition function $c:i\left(Hom\right)×i\left(Hom\right)\to i\left(Hom\right)$ satisfying $c\left(i\left(f\right),i\left(g\right)\right)=i\left(f\circ g\right)$.

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}\left(obj\left(C\right)\right)\to {o}_{D}\left(obj\left(D\right)\right)$ and ${i}_{F}:{i}_{C}\left(hom\left(C\right)\right)\to {i}_{D}\left(hom\left(D\right)\right)$.

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!