DIAGRAMMES 37 (1997)

**COLIMITS
IN FREE CATEGORIES**

*by** Andrée C. EHRESMANN*

**RESUME.**
Le but de cet article est de montrer que seuls des diagrammes très particuliers,
qu'on caractérise, peuvent avoir une (co)limite dans
la catégorie des chemins d'un graphe. En particulier un diagramme connexe fini
a une (co)limite seulement s'il détermine une arborescence,
et dans ce cas la (co)limite est sa racine, donc est
triviale.

**Introduction**

The aim of this paper is to characterise the types of diagrams which admit a (co)limit in a free category, i.e. in the category of paths on a graph. We prove that such diagrams are very special: a connected diagram has a colimit only if it "fills up" into a sup-lattice with linear upper sections; and if it is finite, the colimit is its supremum; if it is also injective, then it corresponds to an arborescence whose root is the colimit.

The main part of the study is done in what we call "categories with diagonals" which are categories in which each morphism is an epimorphism and a monomorphism, and each commutative square has 2 diagonals. These conditions are satisfied both by free categories and by groupoids.

The problem of characterizing colimits in graphs (i.e., in free categories) has arisen in connection with the modelisation of natural systems such as biological or neural systems. Indeed, in a series of papers with J.-P. Vanbremeersch since 1986, we have developed a model based on category theory, where the emergence of complex objects is modelled by a completion process. The present results show that this process cannot be done in the sole framework of graphs, since they imply that the completion of a free category is not free. This vindicates our recourse to (general) categories, instead of considering only graphs as some people have advocated.

**1.
Categories with diagonals.**

We introduce a condition on a category which is satisfied both in free categories and in groupoids.

Let *C* be a category.
If* f* and *f'* are two morphisms with the same domain, we say that
*f'* *dominates* *f* if there exists a *d* such that *f'
= d.f* .

**Definition.** A category *C* is said to be *with
diagonals* if each morphism is both an epimorphism
and a monomorphism and if it satisfies the following "diagonal
condition":

For each commutative square

(1)

then
either *f'* dominates *f* or *f* dominates *f'* .

In other terms, the square
has a "second diagonal" *d* which satisfies either *d.f**
= f'* or *d.f**' = f
;* as *f* and *f'* are epimorphisms,
this *d* is unique, and it also makes commutative the triangle with *g*
and *g'* .

For example, a groupoid
is always with diagonals (we take *d = f'.f*^{-1}). We are going to prove that the category
of paths on a graph is also with diagonals. The category defining an order <
is with diagonals iff it induces a linear order on each interval

(*x,**y*)
= { *z* | *x < z < y* }.

Let *G* be a (multi)graph;
we recall that the category of paths of *G*, denoted by *C(**G)*,
is defined as follows:

- its
objects are the vertices of *G* ;

- the
morphisms from *A* to *B* are the paths from *A* to *B*
in *G* ;

- the composition is the concatenation.

It is known that *C(**G)*
is the free object generated by *G* with respect to the forgetful functor
from the category of categories to the category of (multi)graphs. We will say
that a category *C* is a *free category* if it is the category of
paths of some graph.

**Proposition 1.**** ***A free category C is a category with diagonals in which the identities are the
sole invertibles.*

**Proof.** Let *C = C(G)*.
Then each morphism of *C* admits a unique decomposition
as a path of the graph.

a) Let
us consider a commutative square (1). The first diagonal *g.f**
= g'.f'* admits a unique decomposition as a path
(*s*_{n}*,....,s _{1}*)
of

*f = (s*_{p}*,...,s _{1})*
and

*g = (s*_{n}*,...,s _{p}*

If *p < q ,* then *f'* dominates *f*
and the path *d = (s*_{q}*,....,s*_{p}_{+1}*)* is a second diagonal of the square in *C*.

b) If we suppose that *g.f** = g'.f* , we are in the same situation, but with *f' = f* , that
is *p = q* . It follows that *g = g' ,* and *f*
is an epimorphism. It is also a monomorphism,
because it is an epimorphism in the opposite category of *C*, which is
just the free category of paths of the graph opposite to *G*
.

c) Finally if *f*
is invertible, its composite with its inverse should be an identity, and an
identity cannot be the composite of a path with factors which are not identities;
hence *f* is an identity.

**2.
Filling of a diagram**

**Definition.** Let *C* be a category; a *filled
sub-category *of *C* is a sub-category *K* such that, if *g*
and *g'* are morphisms of *K* and if *d* is a morphism of *C*
with *g' = d.g* , then *d* is in *K* .

**Example.** A filled sub-category of a groupoid is just
a sub-groupoid.

Let *M* be a sub-graph
of the category *C *. As an intersection of filled
sub-categories is a filled sub-category, *M* is contained in a smallest
filled sub-category *R* of *C*, said to be *the filled sub-category
generated by* *M*. It has the same objects as *M*, and it is the
union of the increasing sequence of sub-categories (*R** _{n}*) constructed by induction as follows:

- *R*_{0} is the sub-category generated by *M*; it is obtained
by adding to *M* all the composites in *C* of morphisms in *M*.

- If *R** _{n}*
is constructed, then

We are going to apply this
construction to associate to a diagram in *C* a "filled" diagram
defining the same cones.

Let *P:
S* ® *C* be a diagram in *C*, i.e., *S* is a graph and *P* is
a homomorphism from *S* to the (graph underlying the) category *C*.
We call *S* the *sketch* of *P* and denote by *S*° the set
of its vertices; for each *i* in *S*°, we denote by *Pi* its image by
*P*.

We associate to *P*
the *induced category* *P*(C)* in which the objects are the vertices
*i* of *S* and the morphisms from *i* to *j* are the triples *(i,f,j)*
where *f* is a morphism in *C* from *Pi* to *Pj*. We have a faithful functor *F* from *P*(C)*
to *C* which maps *(i,f,j)* on *f* .

*P*(C)* contains
as a sub-graph the set *M* of triples of the form *(i,P(s),j)*
where *s* is an arrow from *i* to *j* in *S* .

**Definition.** The filled sub-category of *P*(C)*
generated by *M* is denoted by *R(P)*, and the functor from *R(P)*
to *C* restriction of *F* is called the *filled pattern *associated
to *P*, denoted by *P'*.

**Remark.** C. Lair [5] gives a one-step construction
of the category *R(**P)* (when *P* is a functor) and of the
functor *P'*, which he calls a saturated diagram.

**Proposition 2.** *If all the morphisms of C are epimorphisms, there is a *1-1 *correspondence between
the cones with basis P and the cones with basis the filled pattern P': R(P)
*®* C associated to P.*

**Proof**.
1° Let *c* be a cone with basis *P* and vertex
*A*. It is defined by a family *(ci)* of morphisms from *Pi* to *A*, for each
*i* in *S*°, such that

(1) *cj.P**(s)**
= ci* for each arrow *s* from *i* to *j* in *S* .

Let us prove that this family also determines a cone
with basis *P'*. From the above construction, *R(P)* is the union
of an increasing sequence of sub-categories *R** _{n}* of

a) For each *(i,P(s),j)*
in *M*, the equality (1) entails:

* cj.P'(i,P(s),j)
= ci .*

Hence the family *(ci)*
determines a cone with basis the restriction of *P'* to *M*, and therefore
also a cone with basis the restriction of *P'* to the sub-category *R*_{0}
of *R(**P)* generated by *M* , since
we have only to add composites of morphisms in *M* .

b) Let us assume that *c* extends
into a cone_{ }with basis *r** _{n}*.
To get

(2)
* cj = cj'.P'(j,d,j') = cj'.d .*

Now as *(ci)* defines
a cone with basis *r** _{n}* , we have the equalities

*cj.P**'(i,g,j) = ci = cj'.P'(i,g',j') ,*

from which we deduce:

*cj.g** = ci = cj'.g' = cj'.d.g* ,

hence
(2), since *g* is an epimorphism.

Thus by induction we extend
*c* into a cone with basis the union *R(**P)* of the categories *R** _{n}* .

2° Conversely,
if *c'* is a cone with basis *P'*, the *(c'i)*
also define a cone with basis the restriction of *P'* to *M*, or equivalently
a cone with basis *P*.

**Corollary .**

The interest of this corollary is that the study of colimits can be replaced by the study of colimits of filled patterns.

**3.
Colimits in categories with diagonals.**

Our aim is
to characterize the diagrams *P: S* ® *C* which admit a colimit in a category with
diagonals *C* . Such a diagram is *connected*
if *S* is connected; it is *finite* if the set *S*° of vertices
of *S* is finite. In particular we'll prove that the colimit of a connected
finite diagram is always *trivial* (i.e., it is the image of one of the
objects of *S*).

**Theorem 1.*** Let P: S *®* C be a diagram in a category C with diagonals. If there exists a cone c with
basis P (a fortiori if P has a colimit), then R(P)
defines a preorder on S°, which, for each object i
, induces a linear order on the upper section i*^{<}*
formed by all elements greater than i . If S is also connected, then the preorder is sup-latticial (i.e., any two objects are upper bounded). *

**Proof**.
The preceding Proposition asserts that *c* extends into a cone with basis
the filled pattern *P': R(P)* ® *C* generated by *P*.

1° Let us show that *R(**P)* defines a preorder on the set *S*°
of its objects, which means that there is at most one morphism between two objects.
Indeed, if *(i,g,j)*
et *(i,g',j)* are two such morphisms, the composites
of *g* and *g'* with *cj* are equal
to *ci* , hence *g = g'* since *cj*
is an monomorphism by hypothesis. We will write:

*i** < j* if there exists *(i,g,j)*
in * R(P)* .

2° Let us prove that the
preorder induced on the set *i*^{<}
is a linear order, i.e., that if *i** <
j* et *i** < j' ,* then *j* and *j'* are
comparable. There exist *(i,g,j)* and *(i,g',j')* in *R(P)*, and

*cj.g** = ci = cj'.g' .*

The diagonal condition implies that either *g*
dominates *g'* or *g'* dominates *g* ,
so that there exists a *d* with *d.g**
= g'* , or respectively with *d.g**' = g* . But then *(j,d,j')*, resp. *(j',d,j)* is a morphism in *R(P)* which must belong
to the filled sub-category *R(P)*. It means that *j < j'* or, resp.,
*j' < j .*

3° Let us assume that *R(**P)* is connected (for instance it is true if
*S* is connected), and let us prove that 2 objects *j* and *j'*
have an upper bound in the preorder. The connectedness means that there exists
a zig-zag of morphisms of *R(**P)*
linking *j* to *j'* . It is sufficient to prove that this zig-zag
can be replaced by 2 morphisms with the same codomain. Let us first consider
the case of the zig-zag:

As *j* and *i* are
greater than *i*_{1}, they are comparable (part 2); in the same way *i*
and *j'* are comparable. So we are in one of the 4 following cases:

*j < i
< j' or* * j > i > j'*
, so that *j* and *j'* are bounded by the greatest of them;

*j*
and *j'* are bounded by *i* ;

*j*
and *j'* are greater than *i*, in which
case we already know that they are comparable.

By induction each zig-zag can be replaced by such a zig-zag, and this ends the proof..

**Corollary 1**.* Let P: S *®* C be a connected finite diagram in a category
with diagonals. P has a colimit iff there exists a
cone with basis P, and then the colimit is trivial.
More precisely in this case, R(P) defines a sup-latticial
preorder on S° with linear upper sections, and it has a supremum
u , whose image Pu by P is the colimit of P and of
the filled pattern P' associated to P.*

**Proof.** We have seen in Theorem 1 that, if there
exists a cone with basis *P*, the category *R(**P)*
defines an order on *S*° in which 2 objects are upper bounded. Such a preorder
on a finite set has a supremum *u*, which is a final object in *R(**P)*.
It follows that *Pu* is the colimit of the filled
pattern *P'* associated to *P*, hence of *P* (from Proposition
2).

**Corollary 2.*** Let P be a finite diagram in a category with diagonals. If it admits a colimit
which is not trivial, then it cannot be connected; if it is connected, the colimit
does not exist or is trivial.*

**Corollary 3.*** The completion of a free category by adjonction of
colimits of finite connected diagrams cannot be a free category.*

* *The preceding results have some consequences
in the case of non-connected diagrams.

**Theorem 2.*** Let P: S *®* C be a finite diagram in a category with diagonals. If P admits a colimit,
the restriction of P to each connected component S*_{k}* of S admits a trivial colimit L*_{k}*, and the colimit of P is the coproduct of
these L _{k} .*

**Proof.*** *The colimit cone with basis *P* has
a sub-cone with basis the restriction *P** _{k}* of

So the study of colimits of finite diagrams in a category with diagonals is reduced to that of coproducts, since any colimit is either trivial or a coproduct of trivial colimits. The existence of coproducts is very limited.

**4. Colimits in free categories and in groupoids**

**Theorem 3.** *Let P: S *®* C be a connected diagram in a free category which admits a colimit. If P is
injective, then the preorder defined on S° by R(P) is an order and, for each
object i of S, the upper section i ^{<}
is isomorphic to an interval (finite or not) of the set of integers. *

**Proof.**** **1° Let us prove that the preorder defined
on *S*° by *R(P)* in Theorem 1 is an order, i.e., that the relations
*j < i* and *i**
< j* yield *i** = j*. Indeed they
mean that there exist morphisms *(j,f,i)* and *(i,g,j)* in *R(P)*, and their composite *(i,g.f,i)*
is a "closed" morphism in a preorder, hence an identity. It follows
that *g.f* is an identity, which is impossible
in a free category unless *f* is an identity (Proposition 1). But in this
case, this identity is the image by *P* of both *i* and *j* and, since *P* is injective, *i**
= j .*

** **2**° **Let *i*
be an object for which there exists a *j* strictly greater than *i* . Let us prove that there is at most a finite set of objects
between* i* and *j* .
By definition of the order, there exists a unique *(i,f,j)*
in *R(P)*. If *i**'* is between *i*
and *j* , there exist morphisms *(i,d,i')*
and *(i',d',j)* in *R(P)*, and the composite
*(i,d'.d,j)* is in *R(P)*. Since there is
at most one morphism in *R(**P)* from *i*
to *j*, we deduce: *f = d'.d* . Now *f* is a path of the graph *G* generating
*C*, so that the paths *d* and *d'* are sub-paths of this path.
It follows that *Pi'* is the end of one of the factors of the path *f*
. As *f* has only a finite number, say *n*, of such factors,
and as *P* is injective, there is at most *n-*1 objects from *i*
and *j* , and the first of them is the successor
of *i* , while the last one is the predecessor
of *j* .

Hence the linear order
induced on the set i^{<} is discrete, and each intermediate object
has a successor and a predecessor. These conditions imply that *i*^{<} is isomorphic to an interval of **N**.
This interval is finite if it admits a supremum (for
example if *S*° is finite), infinite otherwise.

**Corollary**.
*Let P be a connected finite diagram in a free category, which is injective.
Then P admits a colimit A iff it determines an arborescence
K on S° with A as its root and with an arrow from i
to j iff j is the successor of i
in the order defined by R(P). *

We finally consider diagrams
in a groupoid *C*. If *z = (f*_{1}*,...,f*_{n}*)* is a zig-zag from
*A* to *B* in *C*, we deduce from *z* a path from *A*
to *B* by induction in replacing *f*_{p}