D IAGRAMMES L. C OPPEY Actes des journées E.L.I.T. (Univ. Paris 7. 27 juin-2 juillet 1988) Diagrammes, tome 24 (1990), p. 33-76 © Université Paris 7, UER math., 1990, 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/ OIAORATiriEe VOLUME ACTES OES JOURNEES CUNIV. PARIS 7. GRAPHES L. 24 E. L.. I . T . 27 JUIN-2 JUILLET 199«) STRUCTURAUX Coppey En hommage à Claude Lévi-Strauss, en hommage à la mémoire de Charles Ehresmann, à la mémoire des victimes de la gare de Lyon (27 juin 1988) Le texte qui suit développe quelques idées exposées dans une conférence que j'ai faite aux Journées E.L, I.T., le 27 Juin 1983, intitulée; 0-algèbres,Il déborde assez largement la conférence proprement dite, mais, en cela, je ne me démarque pas des autres conférenciers qui ont bien voulu nous remettre un texte, pour publication dans DIAGRAMMES Ce même jour, tandis que j'achevais cette conférence, un terrible accident de chemin de fer se produisait en gare de Lyon, faisant cinquante six morts et de nombreux blessés, J'aurais pu être parmi eux si je n'avais pas quelque peu abusé du temps de mon auditoire, Je dédie ce texte à toutes les victimes de cet accident, Q8APHE3 STRUCTURAUX 0. QUELQUES STRUCTURES DE BASE POUR DEFINIR LES STRUCTURES, Reprenant des définitions plus ou moins classiques, nais reprenant aussi le titre même de l'article que nous leur consacrions, il y a quelques années déjà CS.B.D.S, ], nous voulons seulement rendre plus lisible l'introduction qui suit [cf. § 1], Sur le style adopté, il y a toujours à redire: s'il n'est pas trop formalisé, on s'en émeut, et s'il prend une tournure trop technique ou trop à l'emporte pièce, on s'en émeut encore, Dans le premier cas, on évoque inévitablement le 'baratin', dans le second, on avoue n'y rien comprendre, ce qui, comme chacun sait, veut dire très exactement le contraire, et n'est, de ce fait, qu'une simple étape dans toute entreprise de récupération. J'ai allègrement papillonné entre le "je", le "on" et le "nous", et, à l'instar des lépidoptères, j'ai su, chaque fois, tant bien que mal, choisir ma fleur. J'aurais dû citer plusieurs fois le magnifique ouvrage de C. Lévi-Strauss La pensée sauvage [P, E.N.S.] (1962), ainsi que les nombreux travaux originaux de C, Ehresmann sur les structures et leurs graphes d'hypermorphismes, et plus particulièrement ici: Catégories et Structures [C.A. S, T, ] (1965) et Introduction to the theory of structured catégories [I.T.S.C. ] (1966), mais en fait, il s'agit de beaucoup plus que de simples citations. Aussi, j'invite le lecteur à se (re)plonger dans ces admirables textes et à y découvrir, avec tout l'enthousiasme nécessaire, les liens qu'ils ont avec les modestes lignes qui suivent. On pourra s'étonner de trouver peu de 'résultats' (sous leurs formes traditionnelles qui ont noms: lemmes, théorèmes, propositions, corollaires, et j'en passe). C'est tout simplement que le sujet ne s'y prête pas, ce qui ne diminue en rien l'intérêt que l'on peut a priori lui porter. On m'a déjà expliqué qu'un étroit rapport existait entre la valeur 'intrinsèque' d'un texte (mathématique) et la proportion 'idéale' des théorèmes et définitions qui s'y trouvent, Je laisse ces savants calculs aux experts, mais en retour, je souhaite vivement qu'ils me disent les retombées prochaines de ces quelques 10* théorèmes (nouveaux?!) produits ces trente dernières années, dont aucun n'a encore fourni autre chose que des miettes de gloire à leur auteur, 35 QRAPHE3 STRUCTURAUX Structures de base. En préambule, notons que la spécification d'une classe dite d'objets (i.e, la structure a minima de graphe orienté) n'est pas toujours signifiative des structures dont nous allons (re)préciser les définitions, mais disons qu'elle facilite l'intelligence qu'on peut en avoir, en en fournissant une possible réalisation graphique. Un graphe orienté G est constitué de: - deux ensembles: celui dit des objets de G, noté Ob(G), et celui dit des flèches de G, noté F K G ) , - deux applications a et B de F K G ) dans Ob(G) fournissant pour chaque flèche x sa source oc(x) et son but B(x) , Remarque, Par élément d'un graphe orienté G, on entend plutôt une flèche de G, dont on précise la source et le but; on écrit alors plutôt [x: A •* B] au lieu de [x c F K G ) , A = y.x Deux éléments d'un système multiplicatif ne peuvent donc se composer que s'ils se 'suivent', mais ce n'est en général pas suffisant. De plus, le composé de deux éléments consécutifs, lorsqu'il existe, est bien disposé conformément au graphe type ci-dessus, Remarque, Ici, quoique ce ne soit pas tout à fait 'évident', la classe d'objets ne joue 'aucun' rôle, relativement à la structure de graphe orienté sous-jacente (cf, encore le préambule). Plus précisément, soit S = (S, C, k) ce qu'on pourrait appeler un système multiplicatif 'sans objets', i,e.; S est un ensemble, C est un sous-ensemble de SxS et k est une application de C dans S, On peut lui faire correspondre canoniqueraent (i.e. librement) un système multiplicatif au sens précédent, en définissant pour S (qui devient un ensemble de flèches) un ensemble d'objets S Q et deux applications, source et but, a et B, de S dans S 0 , convenables. Voici cette construction (c'est une extension de Kan bien simple, mais dois-je faire une telle remarque, ou attendre qu'inévitablement on me la fasse un jour ?) Soient S m et S to deux copies disjointes de S et S . + S b leur somme disjointe; soient a et b les deux injections canoniques de S vers S.+S b l Soit R la relation d'équivalence dans S.+S* engendrée par la relation binaire constituée de tous les couples suivants: (a(y),b(x)), (b(z),b(y)), (a(z),a(x)) , pour (y, x) c C et où z = y.x . Soit S 0 = (S.+Sb)/R et ÏÏ le passage au quotient, On pose alors a = T-a et B = ¥-b. Il est clair que le graphe orienté ainsi défini est sous-jacent cette fois au système multiplicatif S pour lequel on garde, sciemment, la même notation (S, C, k). Désormais, et pour la raison dite dans le préambule, nous considérerons la structure multiplicative avec son graphe orienté sous-jacent; on se gardera bien de croire que celle-ci est toujours la structure libre construite ci-dessus; nous avons seulement fait observer que cette structure (quoique compatible 37 QRAPHC3 STRUCTURAUX avec la composition partielle) ne joue pas de rôle spécifique dans la composition des ... flèches de 3 , Un graphe multiplicatif G5 est constitué d'un système multiplicatif, encore noté G = (G, C, k) et d'une loi 'fournissant les identités' i : G 0 -» G, dans le sens suivant: (i) oc.i = B-i = Idoo , soit graphiquement o. i(A) , qu'on note encore IdA ou 1A> (ii) V A c G o # IA est neutre au sens fort, c'est-à-dire: V x : A 4 B , le composé x. 1A existe et vaut x , et V y : C H A , le composé 1A. y existe et vaut y , Remarques. La loi i ne figure pas dans la notation de G . En effet, son existence est seule en cause, étant donné le point de vue que nous avons adopté sur les systèmes multiplicatifs, La loi qui fournit les identités est assimilable à une propriété que peut avoir ou non un système multiplicatif, Ici, quoique ce soit parfaitement 'évident', la classe des identités peut être adjointe librement et ne joue 'aucun' rôle (mais quoi donc alors jouera un rôle, à ce jeu ?!) Faisons observer toutefois qu'il s'agit ici encore de calculs de structures libres ni plus ni moins triviaux que tout autre calcul de structures libres (algébriques ! ), donc d'extensions de Kan. On verra plus loin qu'il est naturel aussi d'envisager des graphes multiplicatifs partiels (la partialité valant pour les objets, leurs identités, la faculté de certaines flèches d'être neutres, etc.,, ) Un graphe multiplicatif est dit associatif lorsque tous composés des mêmes éléments, dans le même ordre, sont égaux dès lors qu'ils sont définis, On notera bien, à cet égard, que l'associativité portant sur trois éléments n' entraîne rien en général.,, Plus précisément, il existe des genres d'associativité intermédiaires entre 'rien' et l'associativité ci-dessus, mais nous n'en (re)parlerons pas ici (cf. [P, T,6. M, ] et [S, B.D. S,]) 38 GRAPHES STRUCTURAUX Une précatégorie C3 = (G, C, k) est un graphe multiplicatif satisfaisant l'axiome dit d' associativité forte suivant: V x, y, z c G, si (2. y).x ou z, (y, x) est défini, les deux le sont et sont égaux, Une précatégorie est un graphe multiplicatif associatif, L'inverse n'est pas vrai, puisque l'axiome de forte associativité comporte en lui une clause d'existence qui ne saurait en aucun cas provenir de 'simples égalités de composés supposés déjà donnés'. Là aussi, il est possible de définir d'intéressantes notions d'associativité intermédiaires entre l'associativité cidessus qu'on peut qualifier de faible et l'associativité forte. Dans une précatégorie, l'usage de parenthèses est inutile, puisque le raisonnement (usuel) prouvant que l'associativité à 3 entraîne l'associativité à n est applicable, Plus précisément, on montre que si un composé de n éléments, dans un certain ordre, avec une certaine disposition cohérente de parenthèses, est défini, alors tout composé de ces mêmes éléments, dans le même ordre, avec n'importe quelle disposition cohérente de parenthèses, est défini et égal au premier composé, On notera bien que la clause d'existence figurant dans l'axiome de forte associativité est l'élément indispensable qui rend possible (d'un point de vue graphique) la démonstration d'un énoncé du type: [Assoc. à 3] * [V n ) 3 [Assoc, à n]] Insistons aussi sur le fait que, dans une précatégorie, la condition a(y) = jj(x) q u i ^ t nécessaire pour l'existence du composé y.x n'est nullement suffisante, Une catégorie est justement, de ce point de vue, une précatégorie dans laquelle la condition de composabilité oc(y) = B(x) est aussi suffisante, Morphismes de base, Soient G et G 1 deux graphes orientés, Un homomorphisme h de source G et de but G' est un couple d'applications qu'on peut noter (FKh), Ob(h)): 39 QRAPHCS STRUCTURAUX Fl(h): F K G ) -> F K G ' ) Ob(h): Ob(G) -» Ob(G' ) qui commutent aux applications sources et buts. Il faut, en général, se donner effectivement FI(h) et Ob(h). Mais on pourra aussi supposer que la condition de surjectivité de (oc, B) est remplie, auquel cas il est clair que FI(h) (qu'on peut noter h plus simplement) détermine Ob(h). De toute manière la notation h privilégie FI (h) de la même manière que G privilégie, par convention, F K G ), Soient S = (S, C, k) et S ' = (S', C , k') deux systèmes multiplicatifs. Un homomorphisme h de source S et de but S ' est déjà un homomorphisme entre les graphes orientés sous-jacents [h est donc donné comme application de S dans S', indépendamment du fait qu'elle détermine ou non Ob(h) : Ob(S) -> Ob(S')], En outre, h doit satisfaire l'axiome suivant: (H) V (y, x) c C [(hy, hx) € C ' et hy, hx = h(y,x) ] Les homomorphismes se composent de façon évidente et constituent une catégorie S y m ( r e l a t i v e à un univers U qu'on ne mentionnera pas explicitement dans les notations !) Une correspondance c entre systèmes m u l t i p l i c a t i f s , de source S et de but S ' , est déjà un homomorphisme entre les graphes orientés sous-jacents [c est donc donnée comme application de S dans S ' , indépendamment du f a i t qu'elle détermine ou non Ob(c) : Ob(S) 4 Ob(S') ] . En outre, c doit satisfaire l'axiome suivant: (K) V(y,x) c S x S [ [ ( y , x ) cC, (cy,cx) c C ] * cy.cx = c(y.x) ] Les correspondances se composent de façon naturelle et constituent, de ce fait, non pas une catégorie, mais seulement un graphe multiplicatif C o m (relatif à U ) . Plus précisément, pour que c: S -» S * etc': S'i -> S " soient c opposables et de comoposé c'-c: S -» S " U faut (et il suffit) que S ' i = S ' et que c'-c définisse bien une correspondance de S vers S " (axiome (K)). Le graphe multiplicatif G o m est associatif (au sens faible), mais ce n'est pas une précatégorie. 40 GRAPHES STRUCTURAUX Bien sûr, on dispose aussi de notions d'homomorphismes et de correspondances entre graphes multiplicatifs, précatégories et catégories. Entre catégories, les notions d'homomorphisme et de correspondance se confondent. Remarque sur les éléments neutres et les identités. Dans un système multiplicatif S = (S, C, k), on a la notion d'élément neutre, au sens faible suivant: on dit que e c S est un élément neutre à droite de S si et seulement si l'axiome suivant est vérifié: (U*) V x c S [ (x,e) € C * x.e = x ] On définit de même les éléments neutres à gauche ou neutres (bilatères), Toute identité est, par définition, neutre (bilatère), mais un élément neutre à gauche ou à droite n'est pas forcément neutre et un élément neutre n'est pas forcément une identité. Comme pour la composabilité, comme pour l'associativité, comme pour les données d'objets ou identités, les données d'éléments neutres peuvent être partielles; elles peuvent aussi être 'modulées' de bien des façons jusqu'à devenir des identités (à gauche, à droite ou bilatères) etc... Autant c'est bien l'endroit et le moment de signaler ce genre de développements possibles, autant il n'est pas utile d'y procéder vraiment ici, 41 QRAPHE3 STRUCTURAUX 1, INTRODUCTION. Un des objectifs de cet exposé est de montrer que les graphes multiplicatifs (appelés aussi, plus récemment, graphes compositifs ou compographes afin d'éviter la confusion avec une éventuelle et indépendante donnée de produit tensoriel <8>) interviennent à tous les niveaux dès qu'on veut parler de présentations de structures, Une première observation consiste en ceci: un graphe multiplicatif C3 = (G, C, k) est justement une manière de présenter une catégorie G par générateurs et relations: - les flèches de G (ou G) (de G ) , sont les éléments générateurs - si G n'a pas d'autres composés que les composés (dits triviaux) avec les identités, alors la catégorie G est la catégorie (dite libre) des chemins propres de G, qu'on note L_(G)), - si G a des composés non triviaux (2 = y,x, où y et x ne sont pas des identités), alors la catégorie (dite libre engendrée par G, ou présentée par G) n'est autre que le quotient de L_(G) par la relation d'équivalence r<=» compatible (avec source, but et composition des chemins) engendrée par C ; on peut encore la noter L(G3); l'application canonique qui à x fait correspondre sa classe modulo To définit un forteteur <3 -» L_(<3) qui a la propriété universelle requise. Une deuxième observation renforce la première, au niveau de la théorie classique des esquisses: une esquisse (classique) El est constituée d'un graphe multiplicatif muni de cônes (projectifs et inductifs) distingués, destinés à devenir des cônes limites (projectives et inductives) dans les modèles (ou réalisations) de ladite esquisse EL, Ainsi, une esquisse peut être vue comme système de générateurs et relations d'une catégorie à limites (ou type) et ce, 43 QAAPHC8 STRUCTURAUX indépendamment du fait que le langage des esquisses permet de décrire 'tous les types1 de structures (au moins ceux dits classiquement du premier ordre, et relatifs à E E n s ) . Historiquement, on s'est moins attaché (en dehors d'un groupe assez restreint d'élèves de C. Ehresmann) à étudier de tels systèmes générateurs (i.e. des esquisses de telle ou telle forme) que les types (théories) qu'elles engendrent. Citons: - du point de vue dit syntaxique, les topos (géométriques) ou catégories de faisceaux, les théories de Lawvere, les types de Bénabou,.., - du point de vue dit sémantique, les catégories localement oc-présentables de Gabriel-Ulmer, les catégories multia-présentables de Diers, puis les catégories polyprésentables, qui chronologiquement viennent très nettement après les catégories 9-modelables de Lair (que d'aucuns rebaptisent aujourd'hui - est-ce vraiment en souvenir de Grothendieck ? catégories accessibles). Notons que la seule terminologie employée, concernant justement ces catégories de modèles, montre à quel point le problème de la recherche systématique de systèmes de générateurs et relations (i.e, d'esquisses, par exemple) de formes particulières s'est posé dès le début (i.e. dans les années 1970), L'emploi du qualificatif 'présentable' en témoigne, Nous avons séparé, en les citant, les points de vue syntaxique et sémantique, Quelques mots seulement de cette fausse (apparente) opposition, Un type (i,e, une esquisse de forme bien particulière qu'on ne discutera pas ici) décrit des structures, tout comme la catégorie-même de ces structures est sa propre description, Alors, il n'y a là que l'inévitable question de la dualité. Mais elle n'est pas aussi centrale qu'on peut (ou veut) le croire. Ce n'est pas la dualité qui trace une quelconque 'limite infranchissable1 entre syntaxe et sémantique. Le couple syntaxe-sémantique est plus essentiellement du genre 'inclusion', l'un n'étant qu'un 'complété spécifique' de l'autre. Ce que doit à la dualité l'opposition syntaxe-sémantique que nous avons qualifiée de fausse opposition, peut fort bien être gommé en effet, Le rapport entre syntaxes de O-algèbres et triples 44 GRAPHES fournira, remarque. plus STRUCTURAUX loin, un exemple naturel à l'appui de cette Un autre point de vue pour décrire (au moins) l'algèbre sur une catégorie, sans doute issu de la topologie algébrique, et, plus précisément, de la considération des résolutions (objets simpliciaux, etc..,), est celui des monades (ou triples), A toute monade T" sur une catégorie G est associée sa catégorie d'algèbres Alg(~T) au dessus de G , Ce qui a beaucoup séduit à une époque déjà ancienne (et qui séduit toujours d'ailleurs !) c'est la forme générique des descriptions d'une monade et de ses algèbres, indépendante de telle ou telle monade T", de telle ou telle catégorie G : - équations d'une monade, qui ne sont autres, dans leur forme, que celles qui génèrent toutes les équations de type face et dégénérescence d'un ensemble simplicial, et c'est bien ce qui explique qu'historiquement les monades générales en soient issues, - équations d'une algèbre, qui sont, dans leur forme, celles de la monade, parce qu'une algèbre de monade n'est qu'une 'contingence' - au niveau de l'objet sous-jacent et des relations particulières qui la définissent comme algèbre - de la monade. Chaque T"-algèbre est quotient (canonique) d'une T-algèbre libre, laquelle admet une description uniforme (i.e, indépendante de l'objet de base qui l'engendre), Ne reste alors que la monade particulière "T, laquelle offre, à un degré supplémentaire de généralité une structure uniforme, indépendante de son contexte (cf. esquisse de monade, etc..) Ce point de vue possède sa version syntaxique, de forme invariable (i.e, indépendante de telle ou telle monade) , dans la considération de la catégorie dite de Kleisli K K T ) , qui en un certain sens, doit être interprétée comme la syntaxe complète engendrée par T : on retrouve (au moins) une catégorie comme syntaxe, mais là les limites n'ont aucun rôle à jouer, puisqu'une telle syntaxe revient à se donner toutes les algèbres libres, i.e, autant d'objets qui n'ont pas à être présentés comme limites d'autres objets, puisqu'ils sont déjà donnés comme tels. Encore faut-il alors, pour récupérer toutes les algèbres, effectuer (calculer !) certains conoyaux de paires contractiles, 45 GRAPHES STRUCTURAUX c'est-à-dire certaines limites inductives, d'un genre bien p a r t i c u l i e r , s o i t en usant de notations s i u s u e l l e s que nous n'éprouvons pas l e besoin d'en rappeler l a s i g n i f i c a t i o n : 2 (L X,yx) Le x l (LX,jix) 0 XX, •) où i l y a finalement, pour d é c r i r e une T - a l g è b r e , tous les générateurs possibles ( = tout X ! ) e t toutes les r e l a t i o n s possibles ( c f . l e couple ( L 0 , j i x ) ) . On n ' e s t pas l o i n de l a tautologie, Le souci de mettre au point les systèmes de générateurs e t r e l a t i o n s pour l e s monades, au même t i t r e donc que les esquisses sont l e s systèmes de générateurs e t r e l a t i o n s pour les types, d a t e à peu près de l a même époque ( 7 0 - 7 1 - 7 2 ) ( c f , [T.A.E.P. ] , ( a ) e t ( b ) ) , e t , f a u t - i l l e souligner ( j e pense que oui ! ) , i l s ' a g i t du t e x t e i n i t i a l sur ce s u j e t . Puis, ceci é t a n t f a i t , i l a f a l l u comparer avec l e point de vue des esquisses : foncteurs esquissés - t r i p l a b i l i t é - e t c . , . On pourra utilement ( r e ) l i r e [T.F.A, E. ] e t [ E . T . S . R . ] à ce propos, Plus récemment, d é s i r a n t donner de ces travaux de 1971-72 une formulation actualisée, plus opératoire (cf, par exemple: [S, B.D.S, ] , [C.A, P,E. ] , [A, M. E. N, ] e t c . . . ) j ' a i p r i s conscience que t o u t « é t a - o b j e t pouvait ( d e v a i t ) ê t r e d é c r i t par générateurs e t r e l a t i o n s , q u ' i l s ' a g i s s e des catégories de base, des syntaxes d 1 algèbres (ou de s t r u c t u r e s plus générales) , des algèbres elles-mêmes, des homomorphismes entre e l l e s , des v a r i a t i o n s de syntaxes (en plus ou en moins ! ) , e t c . , .La s t r u c t u r e de base s e m b l a i t ê t r e c e l l e de graphe m u l t i p l i c a t i f , Qu'on songe un peu, dans l e même sens, à ce q u ' i l est convenu d ' a p p e l e r le préfabriqué1. Les graphes m u l t i p l i c a t i f s e x i s t e n t : ce sont les matériaux de construction modernes; ils remplacent avantageusement les ensembles qui n é c e s s i t a i e n t , i l y a peu encore, beaucoup de ciment et de sueurs. Je n ' a i pas l a f a i b l e s s e de c r o i r e que l e s choses s ' a r r ê t e r o n t l à , soyons modernes, i , e , de n o t r e temps: n i a t t a r d é s tristement dans un passé passé, n i p r é c i p i t é s bêtement dans un avenir à v e n i r . Pour plus de 46 GRAPHES réflexion sur ce point Baudelaire [A.R, 0,M.] , (très STRUCTURAUX important) j'invite à (re)lire L'exposé proprement dit comportera alors trois parties: - Catégories de base, - Syntaxes de O-algèbres. - O-algèbres et homomorphismes, Chacune de ces parties ne tend qu'à viser l'objectif dont il vient d'être question dans cette trop brève introduction. 47 GRAPHES STRUCTURAUX 2. CATEGORIES DE BASE. La définition d'une syntaxe de O-algèbres suppose fourni un cadre 'sémantique' sous forme, par exemple, d'une catégorie G , dite catégorie de base, qui elle-même peut être 'présentée* de bien des façons différentes, par exemple: - G est donnée comme la catégorie des modèles (ou réalisations) d'une esquisse E dans une autre catégorie M , elle-même donnée auparavant ... - G est donnée comme catégorie de O-algèbres sur une autre catégorie G ' préalablement définie ... - G est donnée comme catégorie de modèles d'une théorie définie elle-même dans un autre langage, etc ,., Cette catégorie de base G fournira une partie du langage syntaxique à définir (cf.§ 3) : ce sont des objets, arités ou coarités de lois, et des flèches, qui sont certaines de ces lois, dites encore naturelles. C'est dire que du point de vue des O-algèbres, il n'est guère possible d'opérer une séparation nette entre syntaxe et sémantique, C'est pourquoi on peut, dans la désignation-même d'une syntaxe rappeler, par choix d'un adjectif approprié, la catégorie de base G ; c'est ainsi, et par exemple, qu'on aura des syntaxes d'algèbres (et donc des algèbres): ensemblistes , lorsque G = E E n s , catégoriques , lorsque C s C a - b , graphiques , lorsque C = G r a (orientés ou non), (graphico)multiplicatives , lorsque G = S y m , ,,, Concrètement, la catégorie de base G sera elle-même donnée (à un certain niveau) par un (ou plusieurs) graphe(s) multiplicatif (s). liais remarquons que rien, a priori, ne nécessite que G soit une catégorie, On souhaite que ses objets soient des structures, et ses flèches des 'liens' entre ces structures, par exemple de type homomorphismes ou correspondances, 49 GRAPHES STRUCTURAUX Nous avons déjà d é c r i t , dans le § 1, un exemple s i g n i f i c a t i f d ' o b j e t de base G qui n ' e s t pas naturellement une catégorie: i l s ' a g i t du graphe m u l t i p l i c a t i f C o r * des correspondances entre systèmes multiplicatifs. Cet objet G o m engendre une catégorie, qui n ' e s t pas une 'catégorie l i b r e ' (dans l ' a b s o l u ! ) . Ce n ' e s t pas un graphe m u l t i p l i c a t i f fortement a s s o c i a t i f , mais seulement a s s o c i a t i f , Notons au passage que C o i n possède toutes les limites p r o j e c t i v e s ( p e t i t e s ) , qu'on prenne les indexations de c e l l e s - c i avec ou sans leur compositions, Ces l i m i t e s se c a l c u l e n t en f a i t comme dans E n s (le 'foncteur d'oubli* naturel C o r * -> E r - i - s les crée et les r e f l è t e , . , ) , I l en est de même pour toutes les sommes ( p e t i t e s ) , mais pas pour les conoyaux, Précisons q u ' i l s ' a g i t i c i de l a n o t i o n usuelle de l i m i t e , a s s o r t i e de toutes les clauses d'existence (exigée) des composés prévus dans l'expression de la p r o p r i é t é u n i v e r s e l l e , Sans nous étendre i c i sur cette question, indiquons cependant q u ' i l existe, pour l e s graphes m u l t i p l i c a t i f s , une n o t i o n de l i m i t e ( p r o j e c t i v e ou i n d u c t i v e ) plus s u b t i l e que c e l l e qui vient d ' ê t r e évoquée, et qu'en général, ces l i m i t e s ne sont pas préservées (en t a n t que t e l l e s ) lorsqu'on passe à l a catégorie l i b r e engendrée, A p a r t l'exemple des correspondances entre les (des) systèmes m u l t i p l i c a t i f s (ou graphes m u l t i p l i c a t i f s , ou précatégories) nous n'avons pas encore proposé d'exemples 'concrets* de graphes multiplicatifs de 'grande t a i l l e ' , I l y a, bien sûr, la p o s s i b i l i t é q u i consiste à s'emparer d'une grande catégorie naturelle (EZin-s, S y m , <3m, ftfa, K - V e c t , T~<=>p>, e t c . , . , e t c . . . ) et d'en ' r e t i r e r a r t i f i c i e l l e m e n t de la composition' (avec ou sans les composés concernés), On mesure aussi bien l ' a r b i t r a i r e de cette manipulation que son e f f i c a c i t é à produire de nombreux exemples ! Venons-en donc à des exemples de grands graphes m u l t i p l i c a t i f s G tout à f a i t n a t u r e l s et qui rendent compte de l ' i d é e simple déjà formulée, à savoir que; 2 = y,x sera d é f i n i lorsqu'une c e r t a i n e c o n d i t i o n , p l u s que purement graphique [oc(y) = B(x)] sera remplie, S o i t U un univers e t f : U -4 U une a p p l i c a t i o n 'choix de sous-ensemble', i,e, : V A c U [ f(A) <= A ] , On f a i t 0 correspondre à f le système m u l t i p l i c a t i f E L Y - I S , suivant; 50 GRAPHES STRUCTURAUX - les objets de EIr-is, e sont les ensembles de U , - les flèches de E n s f ° sont les fonctions (ou applications partielles) entre ensembles (éléments de U ) . Si x : A -• B est une telle fonction, on notera Ax son domaine de définition et xA son image. - la composition des fonctions est la suivante: x : A -* B et y : B, -4 C sont composables si et seulement si: (i) B = Bi [condition graphique usuelle], (ii) V a c f(A) n Ax [x(a) e By] , condition dépendant globalement de i et, localement, de x et de y, - dans ce cas, la composée, notée y.,x n'est autre que la composée usuelle des fonctions, En général, E E n s , ° n'est pas un graphe multiplicatif: en effet, s'il doit y avoir une identité en A c U , ce ne peut être évidemment que l'application identique 1A : A -» A , Or, 1A n'est identité qu'à gauche: pour tout x : C -* A de but A , 1A-x est défini et vaut bien x, par contre, la condition pour que x-lA soit défini (et égal à x !) est très exactement f(A) <= Ax, Cette dernière remarque justifie à elle seule que l'on s'intéresse au sous-système multiplicatif de E n s f ° , qu'on note EliriS/, et qui est, lui, un graphe multiplicatif: x : A -» B est une flèche de E n s , si et seulement si f(A) <= Ax, i,e. la fonction x est définie au moins sur f(A), Le graphe multiplicatif E E r i s , est trivialement associatif, nais ce n'est pas une précatégorie; plus précisément El f i s , admet le déplacement de parenthèses vers la gauche: si (z-y)-x est défini, alors z-(y-x) l'est aussi et est égal, tandis que 2-(y-x) peut être défini sans pour autant que (z-y)-x le soit, On dispose bien évidemment des notions de précatégorie gauche, droite, bilatère ,,, Quelques remarques de calcul dans les graphes El in -s* trouvent leur place ici, 51 multiplicatifs GRAPHES STRUCTURAUX Soit A (c U ) un objet de El in s , ; à tout ensemble intermédiaire E entre les ensembles f(A) et A correspond la flèche iA. E : A -* A , qui est la restriction de l'identité de A à E, Soit x ; A -* B une flèche de E n s ; , On remarque que: - la condition xf(A) «= f(B) entraîne que y-x est défini, mais ce n'est pas une condition nécessaire, - x.iA. E est toujours défini, car la condition coraposabilité se réduit ici à f(A) <= Ax, (ii) de - la composée x-iA.c : A 4 B n'est autre que la restriction de x à E, qui a pour domaine de définition l'ensemble Ax n E; en particulier, x-iA,e = x si et seulement si Ax <= E; on peut dire que iA. c est 'neutre à droite' pour les fonctions dont le domaine est dans E ; de manière imagée, iA. E est d'autant plus 'neutre à droite' que E est grand, - en désignant par F un ensemble intermédiaire entre les ensembles f(B) et B , on voit que iB. F-x est défini si et seulement si x(f(A)) <= F et la composée n'est autre, dans ce cas, que la restriction de x à l'ensemble des éléments de Ax dont l'image est dans F ; en particulier, i8.F-x = x si et seulement si xA <= F ; on peut dire que ie. F est 'neutre à gauche' pour les fonctions dont l'image est dans F et de manière imagée, iB. R est d'autant plus 'neutre à gauche' que F est grand, - pour A c U , E et F intermédiaires entre f(A) et A , on a l'égalité : iA. E-iA. F = iA. ^-i A . c * *A. E~F. - ainsi, tout ensemble E intermédiaire entre f(A) et A fait office de calibrage plus ou moins fin (relatif à f). La catégorie E Z n - s , " des applications entre ensembles de la forme f(A) (A c U ) apparaît comme sous-objet naturel de EEr-i<5f , lorsqu'on identifie une telle application x : f(A) •* f(B) à la fonction x : A -» B qui lui correspond. De même la catégorie E I T - Ï S , * * des applications entre ensembles (éléments de U ) apparaît comme sous-objet (naturel) de EEinsf, Il y a d'ailleurs bien d'autres sous-objets intéressants de E n S / qui sont des catégories, 52 GRAPHES STRUCTURAUX On dispose d'une relation d'ordre naturelle entre les fonctions de choix f, f',.,., à savoir: f E n S / ° (resp, E n s f ) définit un foncteur : G0** -• S Y S (resp, G ° * -> G R M ) , où G est la catégorie associée à l'ensemble ordonné des fonctions de choix (relatives  U ) f décrit ci-dessus et S Y S : (resp, G R M ) est la 'très grande1 catégorie des 'grands* systèmes (resp. graphes) multiplicatifs, localement petits cependant, catégories qui contiennent G f t T " , 'très grande' catégorie des 'grandes' catégories, localement petites cependant ,,. La catégorie E n s ° des applications partielles (relative à KJ) correspond au choix constant " f = • " et la catégorie E n s des applications (relative à U ) correspond au choix maximum pour f (à savoir : V A € U , f(A) = A !) , Concernant le problème de 'taille1, qui préoccupe certains (une formule d'ordre supérieur, un décret d'ordre inférieur, ou un peu de bon sens, devrait pouvoir faire l'affaire! ) , ajoutons cette définition-réflexion (intéressante) : appelons secteur de partialisation le support de f (i.e. l'ensemble (resp. la classe) des ensembles A c U satisfaisant f(A) * A ). Eh bien, le secteur de partialisation peut être 'petit', i.e. être un ensemble objet de U .On en tirera les conclusions que l'on veut, mais qui ne sauraient être dénuées d'intérêt (merci!) Quelques variantes qui ne prétendent nullement épuiser les possibilités, pas plus que le sujet, suggéreront, je l'espère, une théorie générale (que d'aucuns développeront avec tout l'art voulu ..,) , et voici donc de nombreux autres exemples fort naturels ! 53 GRAPHES STRUCTURAUX Nous gardons les mêmes notations que ci-dessus, Pour être flèche de E n s / , la condition imposée à une flèche x : A -> B est f(A) <= Ax . Il est intéressant de varier cette condition, par exemple, comme suit : - Ax <= f(A) (correspond à l'idée de fonctions dont un domaine minimum de non-définition est prescrit, à savoir l'ensemble A\f(A) >, - xA <= f(B) (correspond à l'idée de fonctions dont l'image ne peut excéder un ensemble prescrit, à savoir l'ensemble f(B) ), - xA => f (B) , - des conjonctions (ou disjonctions) de telles conditions du genre : [f(A) <= Ax] et (ou ou) [xA <= f(B)] etc,,, La composabilité des flèches admet elle-même bien des variantes possibles, De tels éléments x : A -> B avec condition(s) à la source et (ou ou) au but peuvent être appelés fonctions calibrées (par f) ; on peut imaginer des calibrages distincts pour source et but etc..Enfin, les calibrages peuvent être plus 'subtiles' que ceux associés (ici) à des fonctions de choix de calibrage: on peut penser à des calibrages liés à la satisfaction de formules d'ordre supérieur dans E n s ,., On peut remplacer, dans tout cela, les ensembles par des objets préalablement donnés (par exemple ceux d'un topos) et les choix de sous-ensembles "/(A) <= A" par des choix (canoniques? cohérents?) de sous-objets, Un autre procédé, sans doute plus général que le précédent, peut produire de grands systèmes (graphes) multiplicatifs assez naturels, qui ne sont pas des catégories, Soit G une "grande esquisse", appartenant à une classe C d'esquisses, qui peut elle-même être esquissable (par exemple, la catégorie des types, i.e,, à peu près, des catégories complètes, cocomplètes, et où toutes les limites voulues sont distinguées), 54 GRAPHES STRUCTURAUX Soit donné aussi un C-cographe multiplicatif r dans la catégorie E s c z ] des esquisses, dans le sens précis suivant, qui correspond à une "réalisation" d'une certaine C-esquisse de cographe multiplicatif dans ( E s c q , G ) : - on dispose de trois esquisses E 0 J 1 l •— 2, - on dispose d'homomorphismes spécifiques entre esquisses; a, B : E 0 4 E i ; v,, v2, k ; E , -> E 2 , ces - on dispose des égalités : vt-B = v2-a , k-oc = v, -a , k-B = v2-B - on désigne par w, et v 2 les coprojections de E t vers la somme amalgamée E « . » (w,-B = w2-a ) de a et de B, et par j ; E « , ^ E 2 l'unique homomorphisme tel que ; j-w, = v, et j-w2 = v2, On impose à j d'être un C-épimorphisme. Nous pouvons alors décrire le 'grand système multiplicatif G*~ suivant : - 0b(<3^) n'est autre que l'ensemble des réalisations de E 0 dans G, - F l ( G r ) n'est autre que l'ensemble des réalisations de E i dans suivant: - ses objets sont ceux de O c provenant de D , donc aussi de B dans le cas algébrique, qui seul nous occupe ici (on ne se privera pas de dire: ceux de D , ou de B , appliquant ainsi le vieux principe qui consiste à désigner une classe d'équivalence par l'un de ses représentants), et C lui-même s'il n'est pas déjà compté, - ses flèches sont celles (provenant) de D , celles allant de D o . ou Bo» vers C, dans G , et l'identité de C, si elle n'est pas déjà comptée, - ses couples copposables (et les composés afférents) sont tous ceux qui existent dans D c # - l'objet pointant est C, On pourrait aussi prendre pour D < c > le sous-graphe plein de D c ayant pour objets ceux de " D " et "C", ce qui ne serait pas tout à fait le même choix (a priori, plus de flèches de N G " y figureraient..,) Remarque 6. En opposition avec la remarque 2, on peut dire ceci; considérer un foncteur J : B 4 G au lieu d'une inclusion n'est pas une généralisation trop gratuite; il peut même y avoir intérêt à généraliser un peu plus , et prévoir, par exemple, un foncteur J : B 4 Diag(G) où Diag(G) est la catégorie des petits diagrammes dans G . Un objet de Diag(C) est un foncteur D d'un (petit) graphe (multiplicatif) I vers G et une flèche de D : I 4 G vers D': JT 4 G est un couple (F,t) formé d'un foncteur F : I 4 J et d'une transformation naturelle t : D 4 D'-F , et si C n'est donné que comme graphe multiplicatif, on sait qu'il existe bien des variantes naturelles (cf. [P.T.G.M, ]) de la notion de transformation naturelle, allant de la plus 'pauvre', purement graphique, à la plus 'riche', qui redonne les transformations naturelles usuelles, pour peu qu'on passe à la catégorie libre engendrée. Ainsi les arités ou coarités se trouvent en quelque sorte éclatées par rapport à la situation antérieure, laquelle est récupérée en choisissant les indexations triviales convenables 59 GRAPHES STRUCTURAUX Remarque 7, Prolongeant la remarque 6, on peut aussi envisager des C-syntaxes 'tramiques' (ou déclaratives): D est alors le graphe multiplicatif sous-jacent à une,., trame (cf, [T,S,T.S,] à ce sujet), Remarque 8, Pour une 'catégorie' de base G fixée, on dispose de la notion naturelle d1 homomorphisme entre G-syntaxes suivante: un G-homomorphisme h de D = (J, K) vers D% = (J', K') est un couple h = (ho* h,) d'homomorphismes entre graphes multiplicatifs: hoï B 4 B ' et h, = D 4 D ' satisfaisant les égalités suivantes : J'«h0 s J et K'-ho = h,.K. Le cas le plus fréquent est celui où B et B ' sont des sousgraphes multiplicatifs de G , où h 0 est une inclusion (de B dans B ! ) et où K et K' sont fidèles et bijectifs sur les objets, Alors la somme amalgamée D ' c de J' et K' (identifiée à D ' ) peut être regardée comme un surgraphe multiplicatif de la somme amalgamée D c de J et K (identifiée à D), elle-même regardée comme un surgraphe multiplicatif de G . Moins formellement, un G-homomorphisme consiste ici, alors, à ajouter (éventue1lement) : - des lois, naturelles ou formelles, - des objets, arités ou coarités, de G , - des équations, Remarque 9, Il se peut que l'injection (supposée reconnue) de C dans D c i ou de D o dans D ' c (ou les deux ) ne tienne en tant qu'injection que grâce à un défaut d'associativité de D , Donnons cet exemple formel: soient f, g, f,, f2 € G , des lois naturelles, et soient tti, a2, tt3 € D \ G , des lois formelles; supposons que l'on dispose des équations suivantes: a 2 = «3,«i # f2.«a a g . f i. 4>i = f , f2.»3 = fiJ alors on a; f2.(a3.«>i) = g tandis que (f2, 03).»i = f , 60 GRAPHES STRUCTURAUX Pour les D-algèbres courantes (cf § 4) ce défaut peut être corrigé en décrétant l'égalité (i.e, "f = g"), d'où la relative nécessité de K. On perd l'injectivité, de ce point de vue, mais on est renvoyé à la remarque 4, Remarque 10. A l'inverse de ce qui a été dit dans la remarque 8, on peut vouloir garder la même partie purement syntaxique, à savoir un foncteur tel que K ; B 4 D , et faire varier la sémantique de base, i.e. G , en se donnant par exemple un foncteur (voire une correspondance) F; G 4 G ' . Alors, même si au départ on avait une inclusion (de B dans C ) pour J, on retrouve un premier foncteur de syntaxe J' = F.J qui n'est une inclusion qu'à la condition que F en soit une lui-même ! Ceci justifie en partie que dans la définition générale on ait envisagé pour J d'être un foncteur général,et pas seulement une inclusion. Remarque 11, On verra au paragraphe suivant que de tels homomorphismes induisent des comparaisons simples (i.e. fonctorielles) entre les catégories d'algèbres associées aux syntaxes source et but: pour G fixé (remarque 8) la comparaison induite est contravariante tandis que pour K: B 4 D fixé (remarque 10) elle est covariante, Remarque 12. Bien évidemment, on peut superposer (en les assouplissant même) les deux genres d'homomorphismes entre syntaxes dont il vient d'être question, Indépendamment, il convient de noter encore ceci: il arrive, très naturellement, que des syntaxes différentes aient même 'indexation' (i.e,: même foncteur K: B 4 D ) et même catégorie de base G , et ne soient pourtant même pas comparables (grâce à un homomorphisme, ou autre correspondance, même assoupii(e)), L'exemple typique de ce phénomène (répétons-le très naturel!) est le suivant: soit 9 : I 4 J un foncteur entre petits graphes multiplicatifs; soit C a t ( f ) la catégorie des catégories à extensions de Kan (choisies) le long de «p; on a montré (voir [C.A.P, E, ], par exemple, nais avec d'autres notations) que C a t ( < p ) était une catégorie de D^-algèbres pour une certaine 61 GRAPHES STRUCTURAUX syntaxe catégorique D^ 3 (J^, K) (donc ici: C = C a t , mais ce pourrait être tout aussi bien < 3 m m , voire S y m , en tout cas pas en général Q r a - cf. par exemple [A.M.E, N, ] ). Dans [C.A.P.E,], on s'est attaché à bien montrer justement que le foncteur K : B 4 D , dit d'indexation, pouvait être choisi indépendamment de 9, mais aussi indépendamment du fait qu'on choisisse C a t , G 3 m m , ou même S y m comme catégorie de base, Par contre le choix de 9 détermine pratiquement celui de J J * -> On désigne par < X , Y > soit l'habituelle catégorie des foncteurs de X dans Y , soit tout autre objet qui en t i e n t lieu, et qui n'est donc pas forcément une catégorie, comme on le sait [P.T.G.M. ] , surtout s i Y n'est pas une catégorie ! Dans ce qui suit, la catégorie E n s n'est pas immédiatement substituable par d'autres catégories (ou graphes m u l t i p l i c a t i f s ) , mais, avec des adaptations qui ressortent à la fois de la routine catégorique (cf, catégories structurées, catégories dominées, V - c a t é g o r i e s , , , ) et d'une lecture attentive de tout ce qui précède, i l est l o i s i b l e de procéder à de t e l l e s substitutions, chaque fois que l'on peut, Soit H : G 4 < B ° ^ , E n < s> le composé du foncteur de Yoneda G 4 et du foncteur d'oubli J * (composition à droite par J): ( C ^ E n s > 4 ( B ^ E n s ) , 63 GRAPHES STRUCTURAUX On dispose aussi de l'oubli K* (composition à droite par K) ; 4 , La catégorie A l ç g ^ des D-algèbres est alors le produit fibre (dans la . ,. catégorie des .,, catégories) de H et K*. La notion de D-algèbre est ainsi introduite indirectement (ou globalement si l'on préfère) par l'intermédiaire de sa 'catégorie' , La définition de l'objet ftlg0 est susceptible de variantes liées à la structure (globale) des objets tels que G , D c i E T T I S , et des morphismes tels que H, K, etc,,., de leur composabilité, bref de la structure globale (catégorie ou autre, à limites (choisies), cartésienne (fermée), etc..) qu'ils peuvent définir et au sein de laquelle A l o j o n'est qu'un objet possible, Revenant à la situation du début, on en arrive à la définition directe (ou locale si l'on préfère) de D-algèbre, qui n'est autre qu'une K*-structure F au dessus d'un objet (foncteur) du type H(C), On dit encore que le couple (C, F) est une D-algèbre sur l'objet C, Entre autre, pour tout objet B de B , on a F(B) = Homc(JB, C), et, pour toute flèche b: B' 4 B telle que Jb; JB' 4 JB c C , F(Kb) = Homc(Jb, C) est l'application de Homc(JB, C) dans Homc(JB',C) qui à x: JB 4 C fait correspondre le composé x.Jb: JB' 4 C, Pour simplifier les notations, mais aussi pour donner la préférence au cas où J est une inclusion, et sans risque majeur de se tromper (eu égard à tout ce qui précède), nous écrirons x-b au lieu de x, Jb. Par analogie, il peut être intéressant de noter, aussi, pour a: KB' 4 KB élément de D , la valeur de F(a)(x) sous forme d'un composé x*a, mais, afin de rappeler que ce composé dépend ici effectivement de F, on préférera une notation du genre x-Fa , Cela étant, si z" = z' -z est une des équations de la syntaxe D (que z, z', z" soient des flèches de G ou non, et l'équation donnée une des équations de G ou non), la ' fonctorialité1 de F se traduit par la condition d'associativité suivante (qui contient en elle-même la définition des composés en cause): V x: B 4 C € F(B) [ X-P(Z'.Z) = (x-Fz').Pz) ] Nous renvoyons à la remarque 3 (suivante) pour plus de détails, 64 GRAPHES STRUCTURAUX Un homomorphisme h: (C, F) 4 (C',F'), de source (C,F) et de but (C',F') est déterminé par une flèche h: C 4 C vérifiant l'axiome (H) suivant: (H) V e: B' 4 B € D , x; B 4 C € G , [F'UKh.x) = h, (F(tt)(x))] Entre autre, pour tout objet B de B , h(B) : F(B) 4 F'(B) est l'application de composition (à gauche) par h : x 4 h,x (cette application pourrait être, de bien des manières, partielle, structurée, plus formelle, etc.. c'est en ce sens que doivent être comprises, puis appliquées maintenant, un certain nombre de remarques faites jusqu'ici). Pour toute flèche y: B' 4 B c G , h(y) n'a de sens naturel qu'à la condition que H(h); H(C) 4 H(C ) définisse bien une transformation naturelle, laquelle, en l'objet B de B , se traduit par la condition d'associativité suivante (qui suppose tous les composés en cause définis): V x: B 4 C € F(B) [ (h-x).y = h-(x-y) ] Dans l'immédiat, par analogie, il peut être intéressant de noter, pour a; B' 4 B élément de D , la valeur réputée commune de F'(tt)(h,x) et de h.(F(a)(x)) sous l'une ou l'autre formes respectives suivantes : (h-x)-a ou h-(x-ô), mais en rappelant qu'ici certains des composés peuvent dépendre effectivement des algèbres source et but de h (i.e, de F et F'), soit en utilisant la notation introduite ci-dessus: (h-x)-Fa = h-(x.Fa). Les définitions et observations précédentes conduisent à associer à une D-algèbre (C, F) le graphe multiplicatif D C c.^> pointé suivant: - ses objets sont ceux de D c provenant de D , et C luimême s'il n'est pas déjà compté, - ses flèches sont celles (provenant) de D , celles allant de D o vers C, et l'identité de C elle-même si elle n'a pas déjà été comptée, - ses couples composables (et les composés afférents) sont tous ceux qui existent dans D c » et ceux de la forme x-Fa décrite ci-dessus, où »: B' 4 B € D et où x est un élément de C de sorte B, - l'objet pointant est C. 65 GRAPHES STRUCTURAUX Remarque 1, La dualité (B o p > , D ° * \ . . ) se manifeste donc simplement, au niveau des algèbres, par le fait qu'on dispose de nouveaux composés à droite. Remarque 2. On ne doit pas confondre ce graphe multiplicatif D< c .^> avec le graphe multiplicatif D 0 / C , qui, lui, ne dépend pas de F, Un objet du graphe multiplicatif Dc/C est une flèche (particulière) de D C C . F > J lequel est un graphe pointé par C, donc pointu! Remarque 3, Dans le cas où J et (ou ou) K ne seraient pas fidèles, il pourrait être judicieux de remplacer le graphe multiplicatif D 0 par un graphe multiplicatif ayant toujours les mêmes objets (identifiables à certains objets de G ) mais plus de flèches (en gardant la multiplicité de celles-ci telle qu'elle est dans B ) . Le mieux serait d'ailleurs de garder une trace concrète de J et de K en ajoutant: - pour tout objet B de B , deux flèches, jB:B 4 JB et ke: B 4 KB, - pour toute flèche b: B 4 B' de B , les équations exprimant la commutâtivite des carrés suivants: B -*> JB -±> KB Jb Kb B' -> JB' Je- 66 -> KB' GRAPHES STRUCTURAUX Remarque 4, Donnons une précision utile concernant l'associativité liée à une algèbre (C, F) donnée. Soient donc x: B 4 C c F K G ) , z': B' 4 B et z; BM 4 B* c opposables dans D , de sorte que l'on a bien les égalités suivantes: x-F(z'-z) = F(z'.z)(x) = F(z)F(z')(x) = F(z)(x-Fz') = (x-Fz').Fz , (F foncteur) Une telle associativité ne fait que traduire, comme déjà dit, la fonctorialité de F, Par contre, (x-Fz')-Fz peut être défini sans que z'-z (et a fortiori x-F(z'*z)) le soit. Autrement dit, la fonctorialité de F se manifeste par la possibilité de certains déplacements de parenthèses vers la gauche. Remarque 5. Le graphe multiplicatif (syntaxico-sémantique-local ) D < c > se trouve ainsi étendu en le graphe multiplicatif D < C . R > > qui ne comporte que plus de composition, et plus d1 associativité, comme on l'a déjà souligné. Remarque 6. Les remarques précédentes, plus particulièrement la dernière, suggèrent à l'évidence une triple généralisation possible pour une algèbre F; - tout d'abord, on pourrait n'avoir à se donner, en guise d'algèbre F (sur C), qu'un surgraphe multiplicatif (toujours pointé en C) du graphe multiplicatif D C C > J satisfaisant certaines règles d'associativité (dont il conviendrait de préserver le caractère global, par opposition au caractère local lié à l'algèbre particulière F), - ensuite, on imagine aisément qu'une algèbre puisse avoir plusieurs objets, voire quelques flèches et quelques composés de flèches aussi, bref un diagramme I à valeurs 67 GRAPHES STRUCTURAUX dans G sous-jacent, et pas seulement un objet C sousjacent; il conviendrait alors de substituer à D < c > un graphe multiplicatif D, qu'on définit facilement, - enfin, et c'est peut-être l'essentiel, on pourrait convenir de ne définir que certains composés x-Fe , dans lesquels a serait toujours un élément syntaxique (€ D ) et où x serait toujours un 'élément' de I , i.e, une flèche de G , de source le but de e et de but un objet Ci de C , indexé par un objet de I , Quant aux lois qui présideraient à la partialisation (car il s'agit bien de cela), elles devraient garder un statut minimum global (i.e, indépendant de l'algèbre F en question) du genre: - le composé x-F« n'est défini que si x factorise d'au moins une façon à travers un diagramme <6(F, a) donné (i.e, qui fait partie des données de la structure F), diagramme dont la forme peut être constante par rapport à F ou à a, ou encore du genre: - le composé x-F4> est défini, mais sa valeur y, bien qu'ayant pour source la source de a, aurait un but non forcément égal au but d de x, mais un objet (ou pourquoi pas un diagramme) relié à Cz (par exemple, par une transformation naturelle). Il va de soi que ces digressions sont pratiquement sans fin, mais ici, il faut bien que je m'explique un peu: 1) il me semble avoir montré assez largement que l'exercice qui consiste à généraliser a priori n'est pas en soi bien difficile, 2) une généralisation peut, malgré les apparences, ne pas en être vraiment une, dans la mesure où elle ne débouche pas forcément sur de nouveaux champs d'application, de nouveaux résultats, 3) cependant, elle présente toujours l'intérêt minimum qui consiste à faire voir les choses d'une autre manière, et 68 GRAPHES c'est cette autre nouveau, STRUCTURAUX manière qui peut générer vraiment du 4) sur le terrain de la généralisation, on trouve toutes sortes de chasseurs, plus ou moins habiles; il n'y a aucune honte à en faire partie, mais gare aux flèches perdues... 5) il y a aussi l'habillage qu'on donne aux choses. Il me semble qu'on confond de plus en plus habillage et généralisation, C'est ainsi que certains, passés grands couturiers, n'ont plus qu'une idée en tête: vous vendre trois paires de chaussettes pour le prix d'une ! J'ai bien compris l'ennui que ce texte, voué presqu'exclusivement aux graphes multiplicatifs, pouvait dégager, Alors les quelques réflexions précédentes assureront au moins la récréation. Soit h; (C,F) 4 (C',F') un homomorphisme entre D-algèbres. On peut lui associer le graphe multiplicatif f léché D<^> suivant: - ses objets sont ceux de D c provenant de D , et C et C eux-mêmes s'il ne sont pas déjà comptés, - ses flèches sont celles (provenant) de D , celles allant de D o vers C et C , la flèche h, et les identités de C et de C elles-mêmes si elles n' ont pas déjà été comptées, - ses couples composables (et les composés afférents) sont tous ceux qui existent dans D c , ceux de la forme x-Fa décrite plus haut, où a: B1 4 B € D et où x est un élément de C (ou de C ) de sorte B, et ceux de la forme h-(x.Fo) décrite plus haut, - la flèche fléchante est h. On peut toujours associer un tel graphe multiplicatif D < ^ > à une flèche h: C 4 C , qui ne soit pas nécessairement un homomorphisme entre les algèbres (C,F) et (Cf,F') (ce pourrait être seulement une 'correspondance1, par exemple), Le fait que h soit un homomorphisme se traduit par la présence dans D < ^ > de suffisamment d* associativité, plus précisément toutes les égalités possible du genre: (h-x)-F <Ù = h-(x-F«), pour x et u variables. 69 GRAPHES STRUCTURAUX La structure de telles égalités nous incite à faire au moins deux observations importantes: - un symbole d'algèbre figure en indice du symbole de composition dans chacun des deux membres réputés égaux et ce symbole (F ou F' !) occupe la même place dans les deux cas, - comme pour toute égalité, l'interprétation en termes de réécriture offre a priori deux possibilités (d'orientation), qu'on peut accepter ou refuser - là n'est pas la question -, mais on doit noter que le déplacement de parenthèses vers la droite est contraire au sens naturel de 1'homomorphisme h (F 4 F'), et donc il correspond au sens (F' 4 F), ce qui, au delà de la simple lapalissade, exprime qu'on va dans le sens "moins d'algèbre, plus de syntaxe", tant il est vrai qu'un homomorphisme conduit toujours vers une structure plus riche ou plus contrainte (voire les deux à la fois). Il convient alors d'établir un parallèle avec ce qui se passe dans le graphe multiplicatif (pointé) D < C . F > associé à une algèbre (C,F). Considérons donc une égalité d'associativité du genre: (x-Fa)-Fa* = x-F(tt-o'). - le symbole d'algèbre figure en indice du symbole de composition dans chacun des deux membres réputés égaux, mais ici, il figure deux fois lorsque les parenthèses sont à gauche et une fois lorsqu'elles sont à droite, autrement dit le déplacement de parenthèses vers la droite correspond encore au sens "moins d'algèbre, plus de syntaxe", mais cette covariance se manifeste ici de façon comptable (2 4 1) tandis que, dans le cas d'un homomorphisme, elle se manifeste de manière moins apparente (cf, la deuxième observation ci-dessus), l'aspect comptable (1 4 1) étant 'neutre', De cette analyse, on retiendra donc que les déplacements de parenthèses vers la droite, dans les graphes multiplicatifs associés, s'accompagnent d'une élimination partielle de l'algèbre au profit de la syntaxe, ce qui suggère fortement de nouvelles manières possibles et relativement systématiques de traiter l'algèbre dans une catégorie ou un système multiplicatif plus général, 70 GRAPHES STRUCTURAUX Nous allons finir par quelques réflexions simples qu'inspire le point de vue (très/trop général) de la réécriture que nous venons d'évoquer. Appelons élément d'algèbre généralisé un triplet E = (h, x, u) dans lequel, pour fixer un cadre minimum: - o;B' 4 B est une loi d'une G-syntaxe D , - x:B 4 C est un élément de C de sorte B (cf. fin du §4), - h: (C, F) 4 (C',F') est un homomorphisme entre D-algèbres, Ainsi dispose t-on des éléments (cf, fin du §4) suivants: - h , x , (à , h-x , x-e , (h-x)-F« , h-F(x.«) , On peut dire que a est la partie syntaxique de E , x la partie élémentaire (au sens du §4) de E , et h sa partie sémantique; on peut qualifier le composé commun (h.x)-Fe = h-F(x-a) d'élément (au sens du §4) sous-jacent à E, En présence d'un élément généralisé E = (h, x, a), trois types naturels de décomposition se présentent, qui donnent lieu à deux possibilités de réécriture, au moins: 1) h = h2lXi où h2; (C,,FT) 4 (C',F') est un homomorphisme et x,:C 4 C, un élément de C, de sorte C (on précisera éventuellement composable avec x), pas nécessairement sousjacent à un homomorphisme, Alors, on peut convenir de réécrire E en E' = (h2, Xi-x, (à), qui peut correspondre au sens "moins d'algèbre, plus de syntaxe" (estimant par là que h 2 est 'plus court' que h, ou, ce qui ne revient pas forcément au même, que x,-x est 'plus long' que x - mais cette appréciation est, à ce niveau de généralité, parfaitement arbitraire). Inversement, toujours avec le même arbitraire, si on a reconnu que x pouvait se décomposer en h,-x^, où h,: (C",F") 4 (C*,F') est un homomorphisme d'algèbres, on peut convenir de réécrire E = (h, x, e) en E" = (h.h^Xz, e) voulant 'augmenter' la composante sémantique de l'élément généralisé E, 71 GRAPHES STRUCTURAUX Ce sont des structures locales de réécriture qui devraient permettre de décider de l'opportunité d'aller vers plus de syntaxe ou plus de sémantique, et non des règles générales (i.e, structures globales), 2) x = x2-a, où x2: B, 4 C est un élément de C de sorte B,, et où »,: B 4 Bi est une loi (naturelle ou non) de la syntaxe D . Alors, si le composé