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₁) of G, and f, f', g and g' must be sub-paths of this path. Thus there exist integers p < n and q < n such that 

f = (s_p,...,s₁)     and     f' = (s_q,...,s₁),

g = (s_n,...,s_p+1)  and  g' = (s_n,...,s_q+1).

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₀ 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 R_n+1 is the sub-category generated by the sub-graph whose arrows are the morphisms d of C such that there exist g and g' in R_n with g' = d.g.           Indeed, the union R of these R_n is filled: if g' = d.g with g and g' in R , then there is an integer p such that g and g' are in R_p , so that d must be in R_p+1, 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 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 P*(C); we inductively "extend" the cone c into a cone with basis the restriction r_n of P' to R_n as follows.

   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₀ 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 R_n+1 we add the composites of the triples (j,d,j') in P*(C) such that there exist (i,g,j) and (i,g',j') in R_n with d.g = g' . To prove that c extends into a cone with basis r_n+1, it is sufficient to prove that for such a d we have:

            (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. P has a colimit A iff its filled pattern P' admits A as a colimit.

            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₁, 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 P to any connected component S_k of S . The conditions of Corollary 1 are then satisfied by P_k  and this Corollary ensures that P_k admits a trivial colimit L_k. Since S is the sum of the S_k  it follows from the transitivity of colimits that P admits a colimit A iff A is the coproduct of these L_k . Let us remark that R(P) is the sum of the filled sub-categories R(P_k) .

            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₁,...,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 by its inverse if f_p is not composable with f_p-1; the composite of this path is called the composite of z . 

Theorem 4. Let P: S ® C be a diagram in a groupoid.

            a) If P admits a colimit, this colimit is trivial.

            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, and

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

Proof. 1° If c is a colimit cone 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 fulfilled. If z is a zig-zag in S from i to j and f the composite of its image by P, the triple (i,f,j) 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 i to j in R(P). It follows that f is also the composite of the image by P of any other zig-zag from i to j in S.

- The condition (ii) is also verified, because if S is not connected, the colimit of P is the coproduct of the colimits L_k of the restriction of P to the components S_k of S (Theorem 2). Each L_k is the image of an object of S_k , and the coproduct cannot exist unless there 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 cone c with basis P as follows: we choose an i and take for ci the identity of Pi ; we define cj, for any other j, as the composite of the image by P of a zig-zag from i to j in S. From the corollary of Theorem 1, the existence of this cone implies that P admits a colimit.

- If the full sub-category generated by C "is" a groupoid of pairs, each diagram in such a category admits for colimit any of the objects Pi .

Corollary. A diagram P into a (non-trivial) group admits a colimit iff S is connected and the condition (i) of the Theorem is satisfied.

Theorem 5. All 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 of the diagram in the opposite category deduced from P, and the opposite of a free category or of a groupoid is of the same type.

5. Application

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

            Indeed, in a series of papers with J.-P. Vanbremeersch since 1986 (cf. [2] and [3] for a mathematical presentation), we have 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 have doubted that the use of categories instead of only graphs (or equivalently, free categories) was necessary. The fact that the class of free categories 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 have to define the category of neurons C as a quotient of the category of paths of Neur, roughly identifying two synaptic paths which transmit a neural impulse in the same way (cf. [4] for a precise construction). Then a coherent assembly of neurons (as those which medical 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 determines 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 iterarated, to model the formation of "assemblies of assemblies of... neurons" representing more and more complex mental events.

References

1.  Bienenstock, E. & von der Malsburg, C., Statistical coding and short-term synaptic plasticity, in Disordered systems and biological organization, NATO NASI Series 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. Cat. 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, Amsterdam (1996) (in print).

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

5.  Lair, C., Esquissabilité des catégories modelables (accessibles) possédant les produits de deux, Rapport de recherche 96-002, Université Paris 7, 1996.

Faculté de Mathématique et Informatique 33 rue Saint-Leu  F-80039 AMIENS. France