example of algebraic theory,free product completion,graphs

73 Views Asked by At

Let us denote by $\def\Graph{{\sf Graph}}\Graph$ the category of directed graphs $G$ with multiple edges: they are given by a set $G_v$ of vertices, a set $G_e$ of edges, and two functions from $G_e$ to $G_v$ determining the target ($\tau$) and the source ($\sigma$) of every edge. The morphisms are called graph homomorphisms: given graphs $G$ and $G'$, a graph homomorphism is a pair of functions $h_v\colon G_v \to G'_v$ and $h_e\colon G_e \to G'_e$ such that the source and the target of every edge are preserved.

NOW,An algebraic theory is a small category $T$ with finite products. An algebra for the theory $T$ is a functor $A\colon T \to {\sf Set}$ preserving finite products. We denote by $\def\Alg{\mathop{\rm Alg}}\Alg T$ the category of algebras of $T$. Morphisms, called homomorphisms, are the natural transformations; that is, $\Alg T$ is a full subcategory of the functor category ${\sf Set}^T$ .

Q.HOW algebraic theory of $\Graph$ ($T_\Graph$) arises as the free completion, of the category $C$ consisting of two parallel arrows from $e$ to $v$: $\tau$, $\sigma$, under products--what graph determines the $A$-image of a word in $\{e,v\}^*$ and a pair $(a, \alpha)$;see below.

Here,free completion under products in a category $C$ can be described as the category of all words over $\mathop{\rm obj} C$ (the set of objects of $C$); that is, objects have the form of $n$-tuples $c_0\ldots c_{n-1}$, where each $c_i$ is an object of $C$ (and where $n$ is identified with the set $\{0,\ldots, n − 1\}$), including the case $n = 0$ (empty word). Morphisms from $c_0\ldots c_{n-1}$ to $c'_0\ldots c_{k-1}'$ are pairs ($a$, $\alpha$) consisting of a function $a\colon k \to n$ and a $k$-tuple of $C$-morphisms $\alpha = (\alpha_0, \ldots, \alpha_{k-1})$ with $\alpha_i\colon c_{a(i)} \to c'_i$.