D IAGRAMMES

A NDRÉE C. E HRESMANN
Colimits in free categories
Diagrammes, tome 37 (1997), p. 3-12
<http://www.numdam.org/item?id=DIA_1997__37__3_0>

© Université Paris 7, UER math., 1997, tous droits réservés.
L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/

DIAGRAMMES

VOLUME 37 ,1997

COLIMITS IN FREE CATEGORIES
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.

1. 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 spécial: a connected diagram has a colimit only if it "fills up"
into a sup-lattice with linear upper sections; and if it isfinite,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 "catégories with
diagonals" which are catégories in which each morphism is an epimorphism and a
monomorphism, and each commutative square has 2 diagonals. Thèse conditions are
satisfied both by free catégories and by groupoids.
The problem of characterizing colimits in graphs (i.e., in free
catégories) has arisen in connection with the modélisation of natural Systems such as
biological or neural Systems. Indeed, in a séries of papers with J.-P. Vanbremeersch since
1986, we hâve developed a model based on category theory, where the émergence of
complex objects is modelled by a completion process. The présent 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 (gênerai)
catégories, instead of considering only graphs as some people hâve advocated.

2.

Catégories with diagonals.

We introduce a condition on a category which is satisfied both in free
catégories and in groupoids.
Let C be a category. I f / a n d / are two morphisms with the same domain, we
say t h a t / dominâtes f\ï there exists a d such that / = d.f.
DEFINITION 1. 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
A

(*)

then either/ dominâtes/or/dominâtes/.
In other terms, the square has a "second diagonal" d which satifies either d.f = f or
d.f = / ; a s / a n d / 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.fx). 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
(xty)={z\x<z<y).
Let G be a (multi)graph; we recall that the category of paths of G,
denoted by C(G)9 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 concaténation.

It is known that C(G) is the free object generated by G with respect to the forgetful
functor from the category of catégories to the category of (multi)graphs. We will say that
a category C is û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 décomposition as a
path of the graph.
l)Let us consider a commutative square (*). The first diagonal gf = g'f admits a
unique décomposition as a path (^,....,5^ of G, a n d / / , g and g' must be sub-paths of
this path. Thus there exist integers/? < n and q < n such that:
/ = (s^.^sj

and

/ = (^,...,5^,

g = (sm...,sp+]) and g' = (sn,...,sq+]).
Ifp < q , t h e n / dominâtes/and the path d = (sqt....fsp+]) is a second diagonal of the
square in C.
2) If we suppose that gf = g'f, we are in the same situation, but w i t h / = / , that is
p = q. It follows that g = g' , and / 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 .
3)Finally i f / i s 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/is
an identity. END OF PROOF.

3.

Filling of a diagram.
Let us define "filled sub-categories".

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 AT and if d is a morphism of C with g' = d.g , then d is
inK.
For 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 object s as M,

and it is the union of the increasing séquence of sub-categories (Rn) constructed by
induction as foliows:
• RQ is the sub-category generated by M; it is obtained by adding to M ail the
composites in C of morphisms in M,
• if Rn is constructed, then Rn+l is the sub-category generated by the sub-graph whose
arrows are the morphisms doîC such that there exist g and gr in Rn with g' = dg.
Indeed, the union R of thèse Rn is filled: if g' = dg with g and gf in R , then there is an
integer/? such that g and g' are in Rp, so that d must be in Rp+U and a fortiori in R.

We are going to apply this construction to associate to a diagram in C
a "filled" diagram defining the same cônes.
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 sfe/c/j of P and dénote by
S° the set of its vertices; for each / in S°, we dénote by Pi its image by P.
We associate to P the induced category P*(C) in which the objects are the
vertices / of S and the morphisms from / to^ are the triples (ifj) where/is a morphism
in C from Pi to Pj. We hâve a faithful functor F from P Y Q to C which maps (ifj) o n / .
P YQ contains as a sub-graph the set M of triples of the form (i,P(s)J) where 5 is an
arrow from i toj in S .
DEFINITION. The filled sub-category of P*(C) generated by Mis 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 Pf.
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 ail the morphisms of C are epimorphisms, there is a 1-1
correspondence between the cônes with basis P and the cônes with basis the filled
pattern P': R(P) -» C associated to P.
PROOF. 1) Let c be a cône with basis P and vertex A. It is defined by a family (ci) of
morphisms from Pi to A, for each i in AS°, such that :
(a)

cj.P(s) = ci for each arrow s from / toj in S.

Let us prove that this family also détermines a cône with basis P'. From the above
construction, R(P) is the union of an increasing séquence of sub-categories R„ oîP*(C)\
we inductively "extend" the cône c into a cône with basis the restriction rn of P ' to Rn as
follows.

For each (i,P(s)J) in M, the equality (a) entails:
cj.P'(i,P(s)j) = ci.
Hence the family (ci) détermines a cône with basis the restriction of P ' to M, and
therefore also a cône with basis the restriction of P ' to the sub-category RQ ofR(P)
generated by M, since we hâve only to add composites of morphisms in M.
Let us assume that c extends into a cône with basis rn. To get Rn+l we add the
composites of the triples (j,df) in P*(C) such that there exist (UgJ) and (Ug'J') in R„
with dg = g'. To prove that c extends into a cône with basis rn+u it is sufficient to
prove that for such a d we hâve:
(b)

cj = cf.P'(j,d,f) = cf.d.

Pi
Now as (ci) defines a cône with basis rn, we hâve the equalities
cj.P'(igj) = ci = cj'.P'(Ug\f) ,
from which we deduce:
Çj.g = ci = cj'.g' = cf.dg,
hence (b), since g is an epimorphism.
Thus by induction we extend c into a cône with basis the union R(P) of the catégories
2) Conversely, if c' is a cône with basis P', the (c'i) also define a cône with basis the
restriction of P f to M, or equivalently a cône with basis P. END OF PROOF.
COROLLARY. P has a colimit A iffits filledpattern P1 admits A as a colimit.
The interest of this corollary is that the study of colimits can be replaced by the study of
colimits offilledpatterns.

4.

Colimits in catégories 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 5 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 cône c with basis P (a fortiori ifP has a colimit), then R(P) defines a preorder
on S°, which, for each object i, induces a linear order on the upper section iK formed
by ail éléments greater than i.IfS 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 cône with basis the
filled pattern F: 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,gj) et (i,g'J) are two
such morphisms, the composites of g and gr with cj are equal to ci, hence g = g' since cj
is an monomorphism by hypothesis. We will write:
i <j

if there exists (UgJ) in R(P) .

2) Let us prove that the preorder induced on the set iK is a linear order, i.e., that if/ <j
and / < / , thenj a n d / are comparable. There exist (UgJ) and (Ug'J9) in R(P), and
cj.g = ci = cf.g'.
The diagonal condition implies that either g dominâtes g' or g' dominâtes g, so that there
exists a d with dg = g', or respectively with dg' = g . But then Q,dJ'), resp. (j\dj) is a
morphism in R(P) which must belong to the filled sub-category R(P). It means that j < /
or, resp.,/ <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./ a n d / hâve an upper bound in the preorder. The connectedness
means that there exists a zig-zag of morphisms oîR(P) linkingy t o / . 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:
/

/,i

h

Asj and /' are greater than ilt they are comparable (part 2); in the same way /' a n d / are
comparable. So we are in one of the 3 following cases:

• j < i < / or j > i > / , so that y a n d / are bounded by the greatest of them,
• j a n d / are bounded by i,
• j a n d / are greater than /, in which case we already know that they are comparable.
By induction each zig-zag can be replaced by such a zig-zag. END OF 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 cône with basis P, and then the colimit is
trivial More precisely in this case, R(P) defines a sup4atticial 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 hâve seen in Theorem 1 that, if there exists a cône with basis P, the
category R(P) defines a preorder on S° in which 2 objects are upper bounded. Such a
preorder on a finite set has a supremum z/, 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). END OF PROOF.
COROLLARY 2. Let P be a finite diagram in a category with diagonals. Ifit 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 ofafree category by adjonction of colimits of finite
connected diagrams cannot be a free category.

The preceding results hâve some conséquences in the case of nonconnected 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 Sk of S admits a
trivial colimit Lh and the colimit ofP is the coproduct of thèse Lk.
PROOF. The colimit cône with basis P has a sub-cone with basis the restriction Pk of P
to any connected component Sk of S. The conditions of Corollary 1 are then satisfied by
Pk and this Corollary ensures that Pk admits a trivial colimit Lk. Since S is the sum of the
1¾ it follows from the transitivity of colimits that P admits a colimit A iff A is the
coproduct of thèse Lk .Let us remark that R(P) is the sum of the filled sub-categories
R(PjJ . END OF PROOF.
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. And the
existence of coproducts is very limited.

5.

Colimits in free catégories and in groupoids.
Let us prove :

THEOREM 3. Let P: S -ïC be a connected diagram in a free category which admits a
colimit. IfP is injective, then the preorder defined on S° by R(P) is an order and, for
each object i ofS, the upper section iK is isomorphic to an interval (finite or not) ofthe
set ofintegers.
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,/ < i and i <j yield i =j. Indeed they mean that there exist
morphisms (jfi) and (UgJ) in R(P), and their composite (Ug.fi) is a "closed" morphism
in a preorder, hence an identity. It follows that g./is an identity, which is impossible in a
free category unless/is an identity (Proposition 1). But in this case, this identity is the
image by P of both i and y and, since P is injective, / =j .
2) Let / be an object for which there exists a j strictly greater than / . Let us prove that
there is at most a finite set of objects between / and j . By définition ofthe order, there
exists a unique (ifj) in R(P). If/' is between / and y , there exist morphisms (i,d,V) and
(i\d'J) in R(P), and the composite (Ud'.dJ) is in R(P). Since there is at most one
morphism in R(P) from i to j9 we deduce: / = d'.d . N o w / 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 ofthe factors ofthe path/. As/has only a finite number, say n, of such
factors, and as P is injective, there is at most n-\ objects from i and j , and the first of
them is the successor of i, while the last one is the predecessor of/ .
Hence the linear order induced on the set i* is discrète, and each intermediate object has
a successor and a predecessor. Thèse conditions imply that f is isomorphic to an interval
of N. This interval is finite if it admits a supremum (for example if S° is finite), infinité
otherwise. END OF PROOF.
COROLLARY. Let P be a connected finite diagram in a free category, which is
injective. Then P admits a colimit A iffit détermines an arborescence K on S° with A as
its root and with an arrow from i toj iff j is the successor of i in the order defined by
R(P).

We finally consider diagrams in a groupoid C.lîz = (fh.../J is a zigzag from A to B in C, we deduce from z a path from A to B by induction in replacing^
by its inverse if^ is not composable with^^; the composite of this path is called the
composite ofz.
THEOREM 4. Let P: S -> C be a diagram in a groupoid.
(a)

IfP admits a colimit, this colimit is trivial.

10

(b)

P admits a colimit iff the following conditions are satisfied:
(i)

the composites of the images by P of two zig-zags from i to j in S are
equal,

(ii)

either S is connected or the full sub-category of C generated by the
image ofP is isomorphic to a groupoid of pairs.

PROOF. 1) If c is a colimit cône with basis P, then each ci is invertible, so that each Pi is
also a colimit of P.
In this case, let us show that the condition (i) is fiilfilled. If z is a zig-zag in S from / toj
and/the composite of its image by P, the triple (i,fj) belongs to the filled sub-category
R(P). Now Theorem 1 (which applies to a groupoid since it is with diagonals) ensures
that there is at most one morphism from /' to j in R(P). It follows that / is also the
composite ofthe image by P of any other zig-zag from z toy in S.
The condition (ii) is also verified, because if S is not connected, the colimit of P is the
coproduct of the colimits Lk of the restriction of P to the components Sk of S
(Theorem 2). Each Lk is the image of an object of Sk , and the coproduct cannot exist
unless there is one and only one morphism in C between two such objects.
2) Conversely, let us suppose that the condition (i) is satified.
If S is connected, we define a cône c with basis P as follows: we choose an / and take for
ci the identity of P/ ; we define cj, for any other/ as the composite ofthe image by P of
a zig-zag from / toj in S. From Corollary 1 of Theorem 1, the existence of this cône
implies that P admits a colimit.
If the full sub-category generated by P(S) "is" a groupoid of pairs, each diagram in such a
category admits for colimit any ofthe objects Pi. END OF PROOF.
COROLLARY. A diagram P into a (non-trivial) group admits a colimit iff S is
connected and the condition (i) ofthe Theorem is satisfied.
THEOREM 5. AU the preceding results can be transposed to characterize the diagrams
P which admit limits in a free category or in a groupoid C.
Indeed such a limit is a colimit ofthe diagram in the opposite category deduced from P,
and the opposite of a free category or of a groupoid is ofthe same type.

6.

Application.

To conclude, I'H say some words on the motivation of this paper. The
problem of characterizing colimits in free catégories has arisen in connection with the
modeling of natural Systems such as biological or neural Systems.

11

Indeed, in a séries of papers with J.-P. Vanbremeersch since 1986 (cf. [2] and
[3] for a mathematical présentation), we hâve developed a model for such evolutionary
hierarchical complex Systems, in which the formation of higher order objects is
represented by a completion process, so that an object of order n becomes the colimit in
the completion of a diagram of lower order objects. Now some people hâve doubted that
the use of catégories instead of only graphs (or equivalently, free catégories) was
necessary. The fact that the class of free catégories is not closed for the completion
process (Corollary 3 of Theorem 1) proves that our model could not be developed in the
simpler framework of graphs.
In particular, to model a neural System, it is not sufficient to consider the graph
Neur formed by its neurons and the synapses between them; we hâve to define the
category of neurons C as a quotient ofthe category of paths of Neur, roughly identifying
two synaptic paths which transmit a neural impulse in the same way (cf. [4] for a précise
construction). Then a cohérent assembly of neurons (as those which médical imaging has
shown to be activated by a mental task) becomes represented by the colimit of a
connected diagram in a completion of C. The interest of this construction is that the
completion détermines what are the "good" morphisms between such assemblies. The
description of such morphisms is one of the main problems for the neuroscientists (cf.
Bienenstock and von Malsburg [1]) and it cannot be solved with usual "graph" models
where an assembly is just represented by a sub-graph of Neur. Moreover our
construction can be iterated, to model the formation of "assemblies of assemblies of...
neurons" representing more and more complex mental events.

7.

Références.

1.

Bienenstock, E. & von der Malsburg, C, Statistical coding and short-term synaptic plasticity,
in Disordered Systems and biological organization, NATO NASI Séries 20, Springer, 1986.

2.

Ehresmann, A.C. & Vanbremeersch, J.-P., Outils mathématiques pour modéliser les systèmes
complexes, Cahiers Top. et Géom. Diff. Cal. XXXIII-3 (1992), 225-236.

3.

Ehresmann, A.C. & Vanbremeersch, J.-P., Multiplicity Principle and Emergence in Memory
Evolutive Systems, J. of Systems Analysis, Modelling, Simulation 26 (1996), 81-117.

4.

Ehresmann, A.C. & Vanbremeersch, J.-P., Hierarchical Evolutive Systems, in Proceedings 8th
international conférence of Cybernetics and Systems, New York 1990, Vol. 1, The NIJT Press,
Newark, 1991, 320-327.

5.

Lair, C, Sur le genre d'esquissabilité des catégories modelables (accessibles) possédant les
produits de deux, Diagrammes 35, Paris, 1996.
Faculté de Mathématique et Informatique
33 rue Saint-Leu
F-80039 AMIENS - FRANCE

12