D IAGRAMMES L. C OPPEY Quelques problèmes typiques concernant les graphes multiplicatifs Diagrammes, tome 3 (1980), exp. no 2, p. C1-C46 © Université Paris 7, UER math., 1980, 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, Vol. 3 , 1980. QUELQUES PROBLEMES TYPIQUES CONCERNANT LES GRAPHES MULTIPLICATIFS• L. Coppey. Introduction. Dans cet article, nous étudions d'un point de vue catégorique la structure de graphe multiplicatif qui est plus générale que celle de catégorie, en ce sens que la loi de composition des flèches n'est pas supposée associative et que la condition "source de l'existence du composé y = but de x " n'implique pas a priori y.x . Les graphes multiplicatifs interviennent à plusieurs titres en mathématiques: principalement en tant que "systèmes de générateurs et de relations" pour les catégories. Ainsi, ils permettent de "présenter" les types de structures et de les étudier efficacement, c'est-à-dire d'obtenir des résultats d'algèbre universelle qui ne soient pas des tautologies. On rencontre aussi les graphes multiplicatifs dans les problèmes d'associativité ou de cohérence. L'étude qui suit ne prétend pas être exhaustive, ni même procéder d'un ordre immuable. Elle tend cependant à suggérer que certaines questions sont à ce point typiques des graphes multiplicatifs qu'elles ne se posent même pas quand C 2 il s'agit des deux cas extrêmes que constituent les catégories et les graphes orientés; par exemple, la classification des produits tensoriels (unitaires) fermés, la non naturalité du plongement de Yoneda, la "vraie notion" d'associâtivité. Dans ce numéro de Diagrammes, on trouvera le début de cette étude. Une suite, avec des applications, paraîtra dans d'autres volumes. 1. Graphes multiplicatifs, foncteurs, transformations naturelles. Un graphe multiplicatif (noté aussi G est la donnée d'un ensemble G ) et d'une loi de composition binaire partielle (notée en général par un point) sur G , satisfaisant les deux conditions suivantes: - unitarité: chaque élément f de té à droite, dite source de f et notée d(f) , et une unique unité à gauche, dite but de f et notée c(f) , - cohérence : lorsque le composé avoir d(g.f) = d(f) , G g.f possède une unique uni- est défini, on doit c(g.f) « c(g) et d(g) = c(f) . Si l'ensemble des couples composables de aux seuls couples triviaux du type alors on dit que G (f,d(f)) G est réduit ou (c(f),f) , est ion graphe orienté. Les catégories, de ce point de vue, sont des graphes multiplicatifs satisfaisant en outre les deux axiomes suivants: - associativité forte: si h.(g.f) ou (h.g).f alors ces deux composés sont définis et égaux, est défini, C 3 - composabilité: si d(g) « c(f) , alors g.f est défini. Si l'axiome de composabilité seul n'est pas satisfait, on dit qu'on a une précatégorie. Introduisons les notations particulières suivantes. Si G est un graphe multiplicatif, on désigne par: - G o l'ensemble de ses unités, • G*G l'ensemble de ses couples composables, ( G * G , si l'on veut préciser "pour la loi T " ) , - G le graphe orienté sous-jacent à G (oubli des couples composables non triviaux), - d et c : G ( dj et cT e' (et les applications "source" et "but" , si l'on veut préciser "pour la loi > e' - f: e but > G f un élément f de G de source s'appelle aussi une flèche de On emploie, de préférence, les lettres e T " ), et de G ). G , H , K , X , Y , Z , pour désigner des graphes multiplicatifs ou des précatégories et on réserve les lettres A , B , C ,D catégories. La lettre désigne "la catégorie des ensembles" E pour désigner des sans préjuger de sa taille. Soient que 9: G G et > G G' 1 deux graphes multiplicatifs. On dit est une application si c'est, en fait, un homomorphisme entre les graphes orientés sous-jacents, i. e. si 9 commute avec d pratique de terminologie plongement de Yoneda). et c . Il s'agit là d'une convention (voir le paragraphe concernant le C 4 Une application que fois que g.f défini dans G' 9: G > G' est défini dans et égal à est un foncteur si, cha- G , alors 9(g).9(f) est 9(g.f). Les applications et les foncteurs se composent de façon évidente; on désigne par R (resp. fp- ) la catégorie des applications (resp. des foncteurs) entre graphes multiplicatifs. Soient 9 et 9' : G > G' deux applications entre graphes multiplicatifs. Une transformation une famille et (t ) de flèches de G t: 9 , où > 9' est d(t ) = 9(e) c(t ) s 9'(e). Une telle transformation est dite naturelle si, pour toute flèche f: e 9'(f).t sont définis et égaux dans © et t f.9(f) e > e' de G , les composés G' . Ces deux notions sont deux cas particuliers "extrêmes", comme nous allons le voir au §2, Quant à la composition des transformations naturelles, il n'y en a pas une qui "s'impose a priori": voici donc une première question, typique des graphes multiplicatifs. 2. Produits tensoriels (unitaires) et fermetures. 2.1. Types^de^carres. La plupart du temps, il faut se résoudre, dans les dessins de graphes multiplicatifs, à représenter effectivement toutes les flèches en présence; par exemple, les "carrés" dans un graphe multiplicatif peuvent avoir l'un des cinq aspects suivants: Ces types de carrés fournissent une première classification des produits tensoriels fermés de /7— . Pour les décrire complètement, nous aurions voulu utiliser des symboles suggestifs, c'est-à-dire géométriques, c'est-à-dire encore dont le dessin soit à ce point précis qu'une démonstration concernant les objets ainsi représentés devienne presque inutile. Mal- C 6 heureusement, les machines à écrire ne font pas assez de géométrie et nous avons du choisir d'autres symboles; cependant, nous invitons le lecteur à consulter le "lexique des notations" ci-dessous ( ), où il trouvera traduits en "symboles préférés" ceux du texte (plus pratiques typographiquement). Nous nous sommes inspiré des symboles employés par C. Ehresmann. L'apparition de nouveaux symboles du lexique est mentionnée en marge du texte par le signe — > . Lexique des notations. Le symbole du texte est à gauche, sa traduction préférée est à droite. —> C 0 °1 D A •1 "2 : 2 "3 : 3 S en B 0 •2 B 02 en D * . t ( ) . "Nous laissons au lecteur le soin de découvrir les règles qui gouvernent l'emploi des symboles de composition", (introduction de "Catégories et Structures", par C. Ehresmann, Dunod, Paris 1965) • C 7 Dans la suite, pour désigner les cinq types précédents de carrés dans G , on utilise donc les cinq symboles res- -> pectifs suivants: C , C -> nérique étant simplement , C« 9 C- , C. ; la notation géC . Dans ces conditions, l'ensemble des carrés de type G est noté C de CG . Etant donné un carré de type mine un carré de type Cn c un carré ayant de type C c~ , il déter- sous-jacent, noté simplement Inversement, étant donné cc C , soit de type c C c . , il existe au plus pour carré de type Cr sous-jacent. Les cinq types cités précédemment s'impliquent les uns les autres selon le schéma suivant: % ' ce qui doit être rapproché, ici, du fait que les deux diagrammes suivants représentent des sommes amalgamées dans la catégorie [J~ des foncteurs: am /K k* C 8 H> 2.2. Les graphes multiplicatifs (doubles) Soit c G un graphe multiplicatif et soient et = deux carrés de type -> c et a' s b C0 dans f c' , noté et BG . c ..c y'.y , x'.x G ; le composé horizontal de est défini si, et seulement si, sont définis dans G ; dans ce cas le composé est: C . . C Gb jjk «5 X 1 .X Dans l'ensemble CG , la loi de composition horizon- tale se précise de la manière suivante: - cc et c' est défini et C G* *°C = sont composables si, et seulement si, c',.c (c'^cj^ existe; dans ce cas on pose **C'C * Avec les notations précédentes pour c et c' , remar- quons que, si les composés y.a , y 1 .a' , (y'.y).a (b'.x').x b'.(x'.x) sont définis, si et ne l'est pas, alcrs C 9 c',, ..c_ est défini, tandis que c' ..cn , et a fortiori C °1 C1 °2 2 c'„ ..c„ , ne le sont pas; pourtant c* et c„ existent C C C 5 °3 bien. On peut concevoir que 3 cp et c' 3 existent, que de plus a' = b , y».(y.a) = y'.(af.x) = (bf.x').x = (y'.a').x , bien que c'..c ne soit pas défini. En échangeant les rôles joués par (b,a) et (y,x) dans un carré c , on obtient un carré symétrique, noté c* , (précisément, on permutte a et x , b et y ) . Par définition, — ^ on dit que le composé vertical c':c est défini si, et seulement si, le composé horizontal c'*..c* est défini et, dans ce cas, on pose c':c s (c'*..c*)* . A côté de la nature des carrés d'un graphe multiplicatif (types C Q , C , C 2 , G- , C. ), il y a la façon de les composer: on vient de définir les lois .. et : ; celles-ci peuvent être renforcéer. de plusieurs façons, que nous indiquons par un symbole adéquat, dans le cas horizontal, en nous limitant aux seuls cas utiles à la description de toutes les structures multiplicatives unitaires bi-fermées de ff- • Ainsi: —5> - c1 .. c est défini si, et seulement si, c'..c est défini et (y'.y).a et y1.(y.a) sont définis et égaux; — b - c' ..p c est défini si, et seulement si, c'..c est défini et b'.(x'.x) et (b'.xf)»x sont définis et égaux; — > - c1 ..^ c est défini si, et seulement si, c1 ..p c sont définis; c' ... c et dans tous ces cas, le composé est encore c'..c • Ces lois de composition binaires partielles, ... , ..^ , C 10 ... , se précisent encore dans la loi *—v les : .. GG , comme on l'a montré pour . Elles se symétrisent aussi en des lois vertica- , »2 f "3 • Dans la suite, nous utilisons les notations génériques suivantes : —•> — pour une loi horizontale , —î> | pour une loi verticale , —^ — pour la symétrisée d'une loi horizontale (c'est donc une loi verticale), —^ }* pour la symétrisée d'une loi verticale (c'est donc une loi horizontale). On établit facilement la: Proposition. Pour que (CG, — ) et (CG, — ) soient des graphes multiplicatifs, quel que soit le graphe multiplicatif G , il faut et il suffit que, dans le tableau suivant, figure le chiffre \ ^ 3 .. (T) "1 "2 "3 1 au point de coordonnées °o c 1 G 2 (C, — ) : C 3 °4 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 C 11 On établit tout aussi aisément que: Proposition. Si (CG, — multiplicatifs, alors ) et (CG, — (CG, |*) , I ) sont des graphes est un graphe multipli- catif double, dans le sens que l'égalité suivante a lieu dès que les composés (entre éléments de CG ) écrits sont bien définis : (yf — y) I (*' — x) = (y- j x') — (y l x) . Ceci définit donc 1+4+4+16+16 = 41 doubles, dont sont symétriques, c'est-à-dire satisfont 13 graphes multiplicatifs l'égalité des lois Le graphe multiplicatif double i té plus simplement j = 0 et et k = 0 ) . On définit ainsi 41 fp G (où 1 .. la catégorie B (C.G, ... , :, ) j est no- K : correspondent à «i foncteurs H:, de des foncteurs entre graphes multiplicatifs /P? vers la catégorie àes foncteurs doubles entre graphes multiplicatifs doubles: nous les appelons des opérateurs tensoriels et un graphe multiplicatif double du type S., G s'ap- pellera une structure tensorielle. Pour parvenir à décrire (et classifier) toutes les structures multiplicatives unitaires bi-fermées sur fP il nous manque encore un opérâteur tensoriel que nous allons décrire maintenant. Les 41 graphes multiplicatifs doubles précédents se pré- sentent tous comme constitués d'un ensemble ( CG ) muni de deux lois de graphes multiplicatifs permutables ( — et | ). Disons que de tels graphes multiplicatifs doubles sont réductibles . Par contre, la èïns 42 structure tensorielle associée à G , C 12 notée H'G, fournit un exemple de graphe multiplicatif double non réductible. La voici décrite de façon "ensembliste" (ceci est voulu, bien que ce ne soit pas la manière la plus satisfaisante de présenter les choses!): parmi toutes les structures sous-jacentes eme naturelles à H'G , on trouve la 41 structure tensorielle A sme B^,G ; cette 41 structure tensorielle admet d'ailleurs H'G comme sous-structure! De plus, l'ensemble des couples (c',c) de carrés de type C. , composables pour la loi :-. , est muni de la loi de composition horizontale ..' pour laquelle (c' ,c ) ..' (c',c) est défini si, et seulement si, C = ( c ^ ..5 c') :5 (c1 ..^ c ) = ( c ^ :^ c^) ..^ (c' :^ c) est défini et les diagonales de c et c' sont composables et de composé la diagonale de C . Dans ce cas, le composé (c' , c ) ..' (c',c) est simplement (c' ..^ c',0. .., c ) . Enfin, l'ensemble des couples (cf ,c) de carrés de type C. , composables pour la loi ..^ , est muni d'une loi de composition verticale :f analogue qui fait de l'application ((0^,^),(^,0)) > ((0^,0^,(0^0)) une bijection entre l'ensemble des couples (de couples composables) composables pour la loi ..' et l'ensemble des couples (de couples composables) composables pour la loi :' Avant de classifier toutes les structures multiplicatives unitaires bi-fermées sur fp (ce qui sera fait au 2.3 ) , revenons brièvement sur les graphes multiplicatifs doubles et, en particulier sur ceux qui sont réductibles. Soit (#,T) et (?!,JL) deux graphes multiplicatifs de même ensemble sous-jacent t> . On peut munir l'ensemble t * % de la loi de composition naturelle déduite de A. et que nous no- C 13 {$*$)*(%£%) tons encore 1 : ples de couples ((z' ,z1),(z' ,z)) tels que z' l z ' , z * z et ce cas on pose (z' ,z ) l(z' ,z) = (z' 1 z' ,z JLz). De même, on munit de T est l'ensemble des cou, z'T z , (z' JL z' )T (z A Z ) soient définis et dans ¢ * ¢ et encore notée d'une structure naturelle déduite T . Se donner un sous-graphe multiplicatif (?» £ z' T z (# * ¢, 1') ?!f-L) (donc de même ensemble sous-jacent de $ J; ^ )a pour "effet" de "réduire l'ensemble des couples (de couples) composables" sans changer "la valeur des composés" : - « * ¢) *, « * ¢) c (?; * ¢) * {% * ¢) , Posons alors les définitions suivantes: 1. Un bigraphe multiplicatif est la donnée d'un triplet B s (#t T t ± ) tel que: (i). (¢, T ) et catifs et (^,l) sont des graphes multipli- (#~ , T ) et (# > l ) en sont des sous- graphes multiplicatifs, (ii). d- , c T : (¢,1) &x , c ) : (¢,1 ) >(*,!) et > (?»f~0 sont des foncteurs; 2. Un graphe multiplicatif double (ou graphe multiplicatif dans fp ) est la donnée d'un quintuplet D = (¢, T , 1 î T' ,1 ') tel que: (i). (¢,7 , j^ ) est un bigraphe multiplicatif, (ii). ( # * # , ! • ) \ (# * #f T 1 ) et 1 graphes multiplicatifs de sont des sous- (# * ¢,1 ) et ^ * ¢,7) respectivement, (iii). l'application s qui à ((z^ 9z^), (z' ,z)) as- C 14 socie ((z* ,z'),(z1,z)) établit une bijection ei • * 4 - (* * ¢) *f « * t) et (* * ¢) », W * « . s(^) (iv). 7 : (* * * , 1 ') 1 : (# * ¢, T ! ) > teurs. > (¢,1) et (¢,7) sont des fonc- Les morphismes entre bigraphes multiplicatifs (resp. graphes multiplicatifs doubles) se définissent bien naturellement; on obtient donc deux catégories, notées respectivement /7"%> et /F, . Remarquons que^dans les définitions ci-dessus, certaines conditions sont redondantes, mais ceci est voulu pour mettre en évidence la symétrie des structures en question. Le foncteur d'oubli U : [P> /7~ 2 admet un adjoint L^ et un co-adjoint L* . Pour décrire les graphes multiplicatifs doubles libre L^B et colibre L*B engendrés par le bigraphe multiplicatif B = (¢, 7 , 1 ) , il suffit pratiquement d'expliciter, dans chacun des cas, l'ensemble %. (puis de vérifier les conditions voulues . . . ) : - dans le cas libre, ¢, est le sous-ensemble de 4 {% * ¢) x (# * ¢) formé des éléments ayant l'une des formes ( ( z ' ^ z ^ , ^ z'^djz^) ou ((cL z,,c1 z),(z',z)) ou encore ((c^ z fz )f(c-. z,z)) ou enfin ((z'1,dT z'^^z',(!_ z')); - dans le cas colibre, ¢. est le sous-ensemble de 4 (# * #) x (# S ¢) formé des éléments ((z^ 9z ) ,(z' ,z)) tels que (z* T z ) 1 (z' 1 z) et (z' 1 z') 1 (z i z) soient définis et égaux. Soit D un objet de fp2 ; P osons B = U ( D ) ' alors L^B est une sous-structure de D et D une sous-structure de L*B . Les foncteurs L^ et L* sont des foncteurs sections C 15 globales de U (l'analogie avec la topologie est évidente: topologies discrète, et grossière). Les graphes multiplicatifs doubles réductibles sont les objets de la forme L*B . Dans la description des structures tensorielles, on a impliet fP* citement identifié L *(/7"V 2 c l e s t b i e n e n c e sens qu'on a dit des structures tensorielles S^.G qu'elles étaient réductibles et qu'aussi 2ÇJ3 était sous-jacente à H'G . 2.3» Les_foncteurs "Hom internes" et produits tensoriels. Etant donnés deux graphes multiplicatifs X désigne par (X,Y) l'ensemble des foncteurs de X Etant donné un graphe multiplicatif double et un graphe multiplicatif noté à /Y,D/ est sition de et D = (¢,7,15 T ', 1 ' ) Y , on définit un nouveau graphe, (Y,^ , en convenant que /Y,D/ , notée aussi G :Y ~? ¢ y€Y,et pour tout ¢ est muni de la (l , 1') sert à définir la loi de compoi , en imposant que, si sont deux foncteurs, le composé est défini si, et seulement si, tout vers Y . /Y,D/ , de la manière suivante: l'ensemble sous-jacent loi 7 ; "l'autre loi" F et Y , on (F(y),G(y)) € ¢ * ¢ F 1 G , pour ((F(y' ) ,G(y' )) ,(F(y) ,G(y))) (jf* « (y',y) € Y * Y *f (j* • *) ; dans ce cas, on pose (FlG)(y) = F(y)lG(y) et on constate d'une part que FJ.G est bien un foncteur de Y vers Z et, d'autre part, que /Y,D/ = ((Y,D), 1 ) est bien un graphe multiplicatif. Soient alors deux graphes multiplicatifs rateur tensoriel H tons volontairement Y et Z . A tout opé- correspond un "Hom interne" que nous noH(Y,Z) et qui est défini par: H(Y,Z) = /Y,HZ/ . C 16 A chaque opérateur tensoriel H correspond maintenant un "produit tensoriel" , noté aussi H , dont nous donnons ici une définition explicite, en fonction des possibles de H , et ce lorsque X et Y 42 valeurs sont deux gra- phes multiplicatifs donnés: - l'ensemble sous-jacent à + XxY U X X H., Y est xY = b(X x Y) , si i = 0, + X x Y , si i = 1,2,4 , + la somme fibrée sion XxY \/ X x Y de l'inclub(X x Y) ^ X x Y avec elle-même (alors b(X x Y) c nous notons (x,y)1 et (x,y)^ les deux copies distinctes du même couple (x,y) de que (X x Y) ), lors- i = 3 ; - l'ensemble sous-jacent à X H' Y est XxY, - dans chacun de ces cas les applications source et but sont évidentes et les composés triviaux aussi; - pour décrire les couples composables non triviaux de X H Y , nous utilisons, par convention, les notations suivantes: + " . " est une unité générique, + les couples (de couples) écrits dans la suite sont censés être composables dans le graphe multiplicatif produit cartésien XxY, + dans ce cas, la valeur du composé est la même que dans ce produit cartésien (elle ne sera donc explicitée que lorsque i = 3 , pour préciser l'indice 1 ou 2 ), par exemple, si nous écrivons ((x',.)(x,y)), ceci signifie que: C 17 + (x',x) appartient à X * X + c(y) = . , et y appartient à Y , + tous les couples composables de ce genre sont retenus comme couples composables pour la structure décrite et la valeur du composé est -pour tout 0^i44 , tout 0.^0^3 (x1.x,y) j et tout couples (de couples) ((x',.),(x,.)) et composables dans X B* Y , 0 4 k { 3 , les ((.,y')»(..y)) sont jk - les couples composables supplémentaires de X H^ Y nsont, en Jk fonction des valeurs de i , j , k : + ((-»y)»(x,.)) » dès que i = 1, + ((x,.)»(«»y)) . dès que i = 2 , + ((.,y)i(x,.)) et ((x,.)»(.»y)) i dès que i . 4 , + ((««yO.Cx.y)) , dès que i ^ 3 et j = 1, + ((x'.y'hO.y)) , dès que i ^ 3 et j = 2, + ((.,y'),(xfy)) et et ((x',y'),(.,y)) , dès que i 4 3 0 = 3 = 2 + 1 , + ((x»,.)»(x,y)) , dès que i i 3 et k = 1 , + ((x»,y'),(x,.)) , dès que i 4 5 et k = 2 , + ((x\.),(x,y)) et ((x',y'),(x,.)) , dès que i ^ 3 et k = 3 = 2 + 1 , + ((«»y)»(x,.)) (dont le composé est ((*:,.)>(•,y)) (de composé + ((•»y')t(x,y)1) i s 3 et j = 1, (x,y) (x,y)2 ) , dès que (de composé (x,y».y)1 ) et i = 3 , ) dès que C 18 + ((x',yf)2,(.,y) ) que + i = 3 et j = 2 , ((• fy'^Uiy)-,) f ((x ,y')2,(.,y)) que + i=3 et (de composé (de composé (x',y'.y)2 ) , dès (x'.x,y)2 ) , dès + ((x^yO-jf (x>-) (de composé que i s 3 et k = 2 , (x'.x,y') ),dès + (x'.x,y)2 ) et i s 3 (de composé et k = 1 , ((x',.),(x,y)2) (de composé (x'.x,yf) ((x',y').,,(x,.)) (décomposé i = 3 ),dès que et k = 3 = 2 + 1 ; - les couples composables de X B' Y autrement dit, X H' Y en posant sont les ((x1,y'),(x,y)), est le produit cartésien . Ayant un opérateur tensoriel H* (x,y'.y)1 ) et j = 3 = 2 + 1, ((x',.),(x,y)2) que que (x f ,y r .y) 2 ) dès (de composé H* = B?\ H , on définit son symétri- , si H = B1, , et B* = H' , si B = B' . Avec les notations précédentes, nous pouvons donc énoncer: Théorème. Quelle que soit la valeur prise par le symbole mi les 42 possibles H., multiplicatifs et B (par- et B' ), quels que soient les graphes X , Y , Z , les égalités W(p)(x,y) = F(x)(y) W*(F)(x,y) = F(y)(x) définissent des bijections naturelles en X , Y , Z : W (X,H(Y,Z)) — - * > (XHY,Z) < de sorte que le bifoncteur - H - : fp W* x fp (Y,B*(X,Z)) , -5> fp termine une structure multiplicative bi-fermée unitaire sur défp C 19 (d'unité 1 ) dont B(-,-) fp res. Ceci munit donc de et B*(-,-) 42 sont les fermetu- structures multiplicatives bi-fermées unitaires: il n'y en a pas d'autres* Preuve. Elle est évidente si l'on veut bien se convaincre que les symboles "préférés" du lexique des notations sont effectivement préférables. En effet, ils suggèrent aussitôt les seules formes possibles de co-graphes multiplicatifs doubles standards dans fp (au sens de gories algébriques" , par "Fermeture standard de caté- F. Foltz et C. Lair, dans les Cahiers de Topologie et Géométrie Différentielle, Vol. XVIII,1 , Amiens 1977). Remarquons, par contre (et pour des raisons analogues), qu'il y a encore exactement unitaires seulement 13 structures multiplicatives fermées à gauche et tiplicatives unitaires seulement d'unité à droite et à gauche 13 structures mul- fermées à droite 1 ) sur la catégorie (toutes fp : - pour les "structures gauches", le produit tensoriel est défini par X IS^ Y = X B* re sur la colonne i Y , lorsque le chiffre et la ligne 1 figu- k dans le tableau (T) pré- cédent , - pour les "structures droites", le produit tensoriel est défini par X H3; Y = X E1. re sur la colonne i Y , lorsque le chiffre et la ligne Précisons que, sur ces - il y en a 14 68 k du tableau 1 f igu- (T). produits tensoriels: qui sont symétriques, ce sont les B. et H' , jJ - la somme fibrée de B fc et H lfel sur HÛQ est B i + j» f k + k' ' C 20 - les seuls produits tensoriels associatifs sont B^ et H' (dans ce cas, les adjonctions de fermeture peuvent donc s'écrire de façon interne : H(X,B(Y,Z)) ^ H(XHY,Z) ^ B(Y,B(X,Z)) ) . Pour le prouver, si l'on veut éviter d'avoir à dessiner des cubes, il suffit de procéder comme suit: -si i ^ 0 , en considérant ((.,(x,y)),(x',(.,.))) que i = 1 est à éliminer et en considérant ((x,(.,.)),(.,(x',y'))) on voit que i = 2 est aussi à exclure, - on en déduit donc que -si i ^3 i = 3 t en considérant et aussi j =r k = 3 * ((.,(x,y) ),(x',(.,.))) ainsi que ((•t(x,y)2),(x',(.,.))) , on prouve aisément que (.,(x,y)?) on voit devraient avoir même image (.,(¾^)^ et ((.jX^y). , ce qui n'est pas possible, - il reste i = 4 (et j s k s } ) , mais en considérant ((x,(x',y')),(.,(x ,y ))) , on trouve encore une impossibilité. 3. Fibrations et d -foncteurs. 3.1. Aspect syntaxique de certainsjnorphismes de ff • Sans formaliser les questions de taille, indiquons simplement que, parmi les objets de /7 , on trouve aussi bien les "petits" graphes multiplicatifs catégories comme E ,E , R G ,H ,K ... que les "grosses" , lorsque: - R est la catégorie des relations entre ensembles, - E est la sous-catégorie de R formée des applications partiel- est la sous-catégorie de E formée des applications . les, - E C 21 Soit A: G v> R une application (morphisme de Il lui correspond le graphe multiplicatif H. /7 ) . défini comme suit: - ses éléments sont les triplets (y,f,x) où appartient à G , x A(e) , y A(e') x appartient à > e' appartient à et x/A(f)/y ,qu'il faut lire " A(f) met en relation et y "; - la composition dans H. s'effectue ainsi: est défini si, et seulement si, y1 = y , g.f G f: e (z,g,yf).(y,f,x) est défini dans et x/A(g.f)/z ; dans ce cas, le composé est L'application p :H > G ,définie par (z,g.f,x). p (y,f,x) s f , est un foncteur fidèle. Inversement, soit p: H lui correspond l'application 3> G un foncteur fidèle. Il A :G > R définie comme suit: - Ap(e) = p~ 1 (e)n H Q - pour f: e existence > e' d'un h € H , £ G , alors tel que x/A (f)/y équivaut à 1' d(h) = x , c(h) = y et p(h) = f . Le problème de l'équivalence entre la donnée d'une application G > R , d'une part, et la donnée d'un foncteur fidèle H > G , d'autre part, pose celui de la défini- tion "naturelle" des morphismes; nous sommes ainsi renvoyés aux structures tensorielles Puisque R HR . est une catégorie, il n'y a plus que deux structures tensorielles à distinguer: B,L& et B'R (types C 22 de carrés: C-. , ou non commutatif, et C. , ou commutatif ; dans ces deux cas, il n'y a qu'une seule loi de composition horizontale possible et une seule loi de composition verticale possible). A ce sujet, nous renvoyons à "Algebraic catégories with few monoïdal biclosed structures or none", par F. Foltz, C. Lair, G. M. Kelly, dans le Journ. of pure and applied Algebra, 17, 1980, 171-177. Soit t: A -5> R une transfonnation -> A' : G (resp. une transformation naturelle); on lui fait correspondre une application T: G — -> û.R ) en -=> C,fi (resp. T: G 4 posant : A'(f) \X T(f) = si f: e >e' appartient à Inversement, à une application G . -5* C^R T: G - (resp. T: G — — > CJR ) on fait correspondre une transformation (resp. une transformation naturelle) entre applications de G vers R. Dans la suite, nous employons indifféremment l'un ou l'autre de ces points de vue ( familles t(e) / r applications de G O vers CR ). Ces remarques valent aussi quand on remplace R par n'importe quelle autre catégorie (même non associative)* Soit toujours t: A ->R ->A' une transfor- mation entre applications. On a fait correspondre à les deux foncteurs fidèles p.: H. -> G et p A' A et A' H A* -> G C 23 Maintenant, on fait correspondre à t un span de foncteurs: En effet, considérons les quintuplets (y',y,f,x',x) tels que: - f: e > e' appartient à G , - (y,f,x) appartient à H - x/te/x' et (y',f,x') appartient à H., , et y/t el /y' . Deux tels quintuplets (y',y ,f.,x',x ) et (y',y,f,x',x) sont composables si, et seulement si: - (y^f^x^.fr^x) et (y^ ,f1 ,x^) .(y' ,f ,x') sont définis respectivement dans H et H., , dans ce cas le composé n'est autre que (y',y.,f..f,x',x) . L'ensemble de ces quintuplets, muni de cette loi de composition, devient un graphe multiplicatif H. . Les foncteurs q et q t sont définis, alors, comme suit: - qA(y',y»f»x',x) = (y,f,x) , - qA,(y',y,i'»x,,x) = (y'.f^') . Ainsi, le carré C 24 est commutatif. De plus, le crochet de q duit fibre de p. et p., et q , vers le pro- est un monomorphisme. Inversement, soit T un carré commutatif de foncteurs tel que dèles et que le crochet de (p,p') (q»q') p p1 et soient fi- vers le produit fibre de soit un monomorphisme (la fidélité de q et q1 en dé- coule alors). On lui fait correspondre: - les applications A et P - la transformation t: A A , : G >R comme ci-dessus, P > A , grâce à l'équivalence /•q(x) a x *A e /x' < z = > 3 ^ T tel que | et ^q'(x) =x' Entre la non commutativité et la commutativité des carrés de R , il y a une notion intermédiaire, propre à cette catégo- rie: l'implication,liée à la relation d'inclusion entre ensembles (plus généralement, cette notion intermédiaire a un sens dès qu'on se trouve, à la place de R , dans un grapne multipli- cati f "ordonné"). Introduisons simultanément notation, définition et terminologie. Soit r (r 1f r',r,r 0 ) un carré dans . On dit que c'est un d -carré R , de source r et de but (ou carré source) si, et C 25 seulement si, r'.r0 S ^1^ (l'implication part de la source), ce qu'on dessine ainsi: L'ensemble des carrés sources est une sous-catégorie C,R de C-R . On définit de même la sous-catégorie C-R j mée des carrés buts (ou (resp. au but c de CL for- J c -carrés). Bien sûr, on a l'égalité: C4R = 4 Une transformation T: G source C R C .R n C R . d e -> CJ* est dite naturelle à la ; des deux cotés ) si, et seulement si, elle factorise à travers C,R (resp. C R ; C.R ) . Pour abréger, on parle simplement de x-transfoxmation (x pouvant être: vide, d , c ) . Soit toujours mation, T: G — t: A •> C-R ->A' -> R une transf or- l'application correspondante et le carré de foncteurs (qu'on appellera aussi relation entre les foncteurs fidèles pA et p f ) associé par la construction ci-dessus. On montre alors sans peine que: C 26 - T est une d -transformation si, et seulement si, q.t est d-étalant , - T est une c -transformation si, et seulement si, q. c-étalant, est Ici, pour un foncteur q: H > G , d-étalant (resp. c-étalant) signifie que, si f € G et e £ H sont tels que q(e) s d(f) (resp. q(e) = c(f) ),alors il existe f €.H satisfaisant d(f) = e (resp. c(f) s e ) et q(f) = f . Soient t: A > A' et t': A' > A" deux transformations entre applications de G vers R ; leur composée est définie point par point (voir la fin du §2) par l'égalité (dans R ) : - pour tout e€.G f (t't) = t'.t * o ' v 'e e e En termes d'applications T et T' vers qui correspond à t't. Soient H **/ H A'~ t ^A^ "S^A» \ < CLR , c'est et H *N G J / V T':T VX^A" . A^ \ « VN> G I^ÈT les relations entre foncteurs fidèles associées. Pour obtenir la relation (q A »q A „) entre p et p „ correspondait à t't, on doit: - faire le produit fibre canonique de p. - faire le produit fibre (3, s) de et p.ff , soit (^AM^AI) » H lf , C 27 - prendre le crochet de - prendre l'image dans Alors qA et q.tf (qA»s,qA„.s) H^,, , de ce crochet, soit sont les restrictions à jections canoniques de H .„ vers H et H. f , H „ H ,, . des pro- respective- ment. En résumé, nous voyons que la catégorie des transformations entre applications de G vers R est équivalente à celle des relations entre foncteurs fidèles de but G (pour être précis, il conviendrait ici de préciser les questions de taille). Nous dirons aussi que l'équivalent syntaxique ( ) de la notion de transformation entre applications vers R est la notion de relation entre foncteurs fidèles. Sans décrire explicitement les règles de traduction "syntaxe-sémantique", ce que nous réservons pour un prochain travail, nous donnons ici quelques traductions parmi les plus utiles: - à une application p: H nent de > G G (i. e. > ti correspond un d(f) = d(g) et d-foncteur p(f) = p(g) entraî- f s g ; c'est la notion de foncteur d'hypermorphismes C. Ehresmann), - à une application p: H 1 > G G (i. e. > S correspond un étalement un d-foncteur satisfaisant, en outre, 1 dp" (f) =p" (d(f)) ) , ( ) . De façon très informelle, j'appelle pour le moment syntaxe de G ce qui est au dessus de G et sémantique de G ce qui est en dessous. L'important est de connaître les règles de traduction. C 28 - à la propriété pour F: G v> R d'être un foncteur, il cor- respond les propriétés, pour p: H (C) et >> G , que l'on a notées (D) ci-dessous, dites de relèvement des compositions et des décompositions respectivement: (C), d(g) s c(f) et (p(g),p(f) A' : G ^E corres- G , soit P p' G où. p et p' sont fidèles et P est un foncteur partiel . Un exemple typique (et dont nous aurons fondamentalement besoin par la suite) est fourni par le plongement de Yoneda, qui n'a plus rien de naturel (et c'est ... normal)» En effet, 9 soit - Y (ef) = e £ G : en définissant o £ f6G / - Y (g): Y (e') d(f) s e et Y par: e * c(f) = e' } , si > Y (e") est l'application partielle "composition par g (quand elle est possible)" , si dans G , e' € G , g: e' >e' c 29 on voit que Soit Y : G e h: e 1 > E est une application. > e ; la famille tions partielles Y, f: Y (e r ) n, e (Y, >Y e d'applica- (e') décrites par e^ les compositions à droite par termine une transformation f) t ^ h (quand c'est possible) Y, : Y > Y n e :G déE . e. Alors il est clair qu'il revient au même de dire: - soit que tous les Y sont des foncteurs ou que G est une précatégorie, - soit que toutes les Y. sont naturelles ou que G est une catégorie . Rendre naturels les plongement de Yoneda de façon universelle est donc une expression beaucoup trop vague. En réalité, on peut le faire précisément de plusieurs façons. Nous ne les exposerons pas toutes ici, réservant la fin de ce paragraphe à une seule d'entre elles sous son aspect syntaxique. 3*2. Pibration libre engendrée par un d-foncteur. Soit p: H f> G un d-foncteur. Nous voulons construi- re un triangle commutatif de foncteurs i où p _ -> H est une fibration, qui soit universel parmi les trian- gles de source p et de but une fibration. c 30 La construction de p consite en l'alternance dénombra- ble de deux constructions: (a), forcer un foncteur de but fixé à avoir les propriétés (C) et (D) , (b). forcer un foncteur à être un d-foncteur. Ces deux constructions sont traitées séparément et successivement. Pour ce qui est du point (a) , soient deux ensembles suivants, attachés à - C est l'ensemble des couples p(g).p(f) est défini dans pas défini dans - D G , C p: H — — — > (g,f) €. H x H d(g) = c(f) et et D G : les tels que g.f n'est H , est l'ensemble des triplets (h,g,f) € H x(G * G) tels que p(h) = g.f , il n'existe pas de couples (g,f)€H * K satisfaisant (on remarquera h = g.f , p(g) = g , p(f) = f que cette dernière condition n'est pas essentielle pour la construction de tir d'un objet p H ; il peut être intéressant, quitte à par"plus gros" que celui qui suit, et dont on prendra de toute façon un quotient, d'éliminer des conditions du genre "il n'existe pas ..." qui ne s'esquissent pas projectivement). On considère alors le graphe multiplicatif tant à H obtenu en ajou- H : - de nouveaux éléments indexés par C et D , - de nouveaux couples composables. Pour ce qui concerne les nouveaux éléments, à chaque appartenant à x = (g>f) C , on fait correspondre un nouvel élément hx c 31 tel que d(h ) = d(f ) et c(h ) s c(g) . A chaque triplet y = (h»£>£) appartenant à D , on fait correspondre trois nouveaux éléments b et c(b ) = c(h) d(b ) s c(a ) = e et , e a tels que d(a ) = d(h) , (ce dernier étant donc une nouvelle unité). Pour ce qui concerne les nouveaux couples composables, mis à part les couples triviaux (où figurent une unité au moins), ce sont: - les couples éléments de si C pour lesquels on a g.f = h , x = (g,f) , - les couples (b ,a ) , où «/ b .a = h . y y On étend p: H y = (h,g,£) € D , pour lesquels «y > G en un foncteur p,.: H. ,P1^V posant: p ^ l ^ ) = p(g).p(f) , P-,(a ) = f p (e ) = d(g) = c(f) ; de sorte que l'inclusion est un foncteur et que 2> G = £ i..: H en et > II. p 1 .i. = p • Soit i' H > H' un triangle commutatif de foncteurs tel que p' bration. Alors il existe un unique foncteur i': H. satisfaisant p. i'.i s i' et soit une fi3* H' p'.i' = P 1 . Mais, à ce stade, n'est plus, en général,un d-foncteur; de plus, il ne véri- fie pas encore les conditions (C) et (D) , bien qu'on les ait "forcées" une fois. Il est inutile d'itérer la construction précédente pour forcer les propriétés (C) et (D) à être satisfaites puisqu'un quotient ultérieur détruira (C) ! (les C 32 propriétés brable). (C) et (D) seront récupérées à la limite dénom- Pour ce qui concerne la construction (b) (forcer un foncteur à être un d-foncteur), soir p: H > G un foncteur; désignons par H- le graphe symétrisé du graphe orienté H dans lequel on distingue les deux sous-grapnes orientés opposés H et H ° P . Une d-connexion de source e et de but e' est un chemin dans Hg de source e et de but e' ayant une structure particulière relative à p . Pour décrire précisément celle-ci, il convient d'abord de définir certaines suites de multi-indices. Le symbole s , où u s + 1 , désigne une suite finie non vide d'entiers consécutifs supérieurs ou égaux à 1 , croissante si u s -1 , décroissante si u = 1 ; on convient d'écrire les suites de droite à gauche ; d(s ) est le premier nombre de la suite s (i. e. le plus à droite) et c(s ) est le dernier (i. e. le plus à gauche) ; si u = -1 , on a d(s U ) ^ c(s U ) et si u = 1 , on a d(s ) ^ c(s ) . On considère, alors, les suites de suites s , soit U U 2n-1 / 2n 2n 2n-1 1 x 3 = s ,s ^ 2n 2n-1 ' mmm ' s 1 > ayant les propriétés suivantes: k "v - u, SB (-1) , (alors, on pose pour simplifier, s, = s ) , - d ( s ^ a c(s 2n ) ©t c(s k ) « d ( s k + 1 ) ) si k = 1, ... ,2n-1 . A une telle suite de suites s , on fait correspondre la suite s des couples (k,m) , où m figure dans s , totalement ordonnée par la relation suivante: - (k',m') ^, (k,m) si, et seulement si, k' >y k et, si k' = k m1 ^ m lorsque u. = +1 , et m' > m , lorsque u. = -1 . C 33 A tout élément (k,m) satisfaisant u, = -1 , on associe alors son écran dans la suite s de la manière suivante: c'est l'élément (k ,ra) , où k est le plus petit entier strictement plus grand que k satisfaisant m € s, + ; étant donnée la structure de s , l'écran (k ,m) de (k,m) est toujours défini et u(k + ) = 1 . Nous pouvons maintenant définir une d-connexion de e vers e': c'est un chemin dans EL de source e et de but e' ayant la propriété d'être indexé par un ensemble totalement ordonné du type s décrit ci-dessus, soit (f/. N ) / . * ^ ** , tel que: tk,mj vk,m; € s f € - ( k . m ) S , si ^ = 1 , et f ( k i B ) € H°P , si ^ . - 1 . - si (k ,m) est l'écran de (k,m) , alors p(f/,+ x) s p(f/ v La relation r dans H^ formée des couples (f,f) tels que: - il existe une d-connexion de source - d(f) et de but d(f') , p(f) = p ( f ) , est alors une relation d'équivalence bicompatible (i. e. compatible avec c et d et la composition) et compatible avec p , d'où l'on déduit un triangle commutatif où H = H/r . Evidemment, le foncteur p est un d-foncteur et c'est la solution du problème universel de plongement d'un foncteur dans >)• C 34 un d-foncteur de même but (la vérification, aisée, est laissée au soin du lecteur). C'est aussi la solution du problème universel de plongement d'un foncteur dans un d-foncteur de but éventuellement distinct. En alternant les constructions (a) et (b) et en passant à la limite dénombrable, on construit donc la fibration libre engendrée par un foncteur. On remarquera que ces constructions sont du type "extensions de Kan" , envisagées sous leur aspect syntaxique (d'autres disent "interne"). Je signale aussi que j'ai exposé ce genre de constructions au Séminaire Ehresmann en ... 1967• Les textes, rédiges à cette époque, n'ont pu être publiés ... En 1971, j'ai montré comment ces questions interviennent dans l'étude générale des structures algébriques: je renvoie le lecteur (intéressé ou honnête) au seul texte que j'ai publié à ce sujet en 1972 ( ) ; il y a d'ailleurs des erreurs et des maladresses facilement décelables. Certains catégoriciens ont largement développé ce point de vue, avec élégance et succès: qu'ils se considèrent tous comme cités ici en bloc. Pour plus de détails, j'invite le lecteur: (i) à consulter les longues bibliographies qui existent sur le sujet, (ii) à ne pas oublier d'y rayer la référence ( ) ci-dessous, si, par nasard elle s'y trouvait. ( ).Cahiers de Topologie et Géométrie Différentielle, Vol. XIII,1 et XIII,4 , Dunod, Paris 1972. C 35 4. Associativités dans les graphes multiplicatifs. 4.1. La ^^^égorie^des^parenthèsages. /f\J Construisons, d'abord, une catégorie Elle a pour objets les entiers strictement positifs. Ses flèches sont les suivantes: - Hom(n,p) = 0 , si n <^ p , - Hom(n,n) n'a qu'un élément, l'identité, - Hom(n,p) , pour tout p < n , est constitué des (n-p)-up- lets de nombres entiers la condition s = (k , ... ,kA ) satisfaisant n-p ' 1' 1 ^ k, ^ n-i , pour i = 1,2, ... ,n-p . La composition s'effectue par simple juxtaposition des suites d'entiers, l'identité en n devant s'interpréter comme "la suite vide en n " . La notation f: n > p d'entiers qui détermine A l'objet n de //\f s est la suite f . /A/ On peut donner de signifie que une autre description. faisons correspondre la catégorie engendrée par le graphe n 0 > 1 î> 2 ... — ^ n . a a 1 2 n est une sous-catégorie pleine de m . a Pour m ^ n , n Soit k un entier compris entre pond le foncteur "face" P.: n^l - F. (a.) = a. , si k N i' -W -W 1 et n-1 ; il lui corres> n_ , défini par: i < k , 1 ' - V1 ,ak » = V1 »si j > k • Evidemment, à une flèche n jr ^ kT* P ^ n-p'* * * » y de ^ corres- C 36 pond une suite de tels foncteurs, à savoir: £ ^ p+1 P *k n-p ^ p+2 ... n-1 P « i n-p-1 ^ n , P 1 >%• de sorte que //V apparaît comme catégorie duale de la caté- gorie libre engendrée par les foncteurs Intuitivement, les flèches a. F, : n-1. > n . doivent être regardées com- me des "places possibles de flèches " dans une catégorie ou un graphe multiplicatif et la flèche duale de P : n-1 ^ n peut être interprétée comme "l'effacement d'un objet" (l'objet k de n ) correspondant à un placement élémentaire de parenthèses (composition de IN a, et a, . ) . Géométriquement, apparait comme catégorie libre engendrée par le graphe suivant: < t < r Comme les placements élémentaires de parenthèses pour aboutir à une disposition cohérente comportent un certain arbitraire dans l'ordre où ils sont effectués, nous devons procéder à un quotient de //\/ pour obtenir la catégorie, recher- chée, des parenthèsages. Il nous faut, tout d'abord, introduire quelques opérations simples sur Sur les couples d'entiers nit l'opérateur les suites d'entiers. (m,n) , tels que n ^ m+2 , on défi- t , dont l'effet est donné par: - t(m,n) s (n-1,m) . L'opérateur inverse tels que p ^ q+1 t"* agit sur les couples d'entiers (p,q) et son effet est • t" (p,q) = (q,p+l). évidemment donné par: C 37 Ceci étant, on étend ces opérateurs partiels aux suites finies d'entiers de la manière qui suit. Soit s- = (k une suite d'entiers positifs ou nuls et î pris entre 1 et r ; si t" $(k. -.fk.) est défini, on note et si i un indice com- désigne l'un des symboles d'entiers obtenue à partir de par ... ,k.) 1f s t ou î.(s) la suite en y remplaçant (k. 1,k.) (k' + 1 ,k!)=t(k i + 1 ,k.). /A/* à.es suites finies d'entiers, on s'inté- Dans l'ensemble resse alors à l'équivalence g " s as t.s " . Ainsi, on a s ^ engendrée par les relations s' si, et seulement si, l'une des conditions ci-dessous est vérifiée: - s =s s' , î - il existe une suite finie de symboles , ... ,t n î que ... î °k n s s mod Ç s' . il existe un et un seul représentant, s«- , sur lequel l'opérateur çon (i.e. si tels °k i Dans la classe noté soit défini et égal à i t ne peut agir d'aucune fa- s„ = (k , ... ,k.) , alors on a k. ^ k. .+l).Par exemple, si s = (8,10,1,140,80,82,81) , on obtient S N = 057,73,77,78,9,8,1). On dira que le de s mod Ç est la forme norma- à laquelle on peut l'identifier. Il est clair que l'équivalence £ de monoïde de sN /V* > de est compatible avec la loi sorte que /ty*/£ monoïde, dont la loi de composition notée est encore un ° s'exprime en ter- mes de formes normales par: - s' • s N = (s^s N ) N . La catégorie des parenthèsages tions, un quotient strict de f^ est, dans ces condi- //V . En effet, on remarque d'abord que si f : n > p est une C 38 flèche de /A/ et si t.s est défini, alors 1 est encore une flèche de équivalence € n > p V ^ /A/ > qu'on note î.f ; ainsi 1' se transporte en une équivalence ^ dans /A/ » compatible et élémentaire (en ce sens que et g: n si: - s ,• > q sont équivalentes mode m = n ,p = q , P La catégorie S'vs'). = /A/ / Ç 4 u e l'on obtient est celle des parenthèsages. L'interprétation de flèches de f : m —-fcp s si, et seulement n vers P est la suivante: les 1 s'identifient naturellement aux dis- positions cohérentes de parenthèses portant sur une flèche D: n > p n places, s'identifie naturellement à la don- née d'un ensemble totalement ordonné de p dispositions cohé- rentes de parenthèses portant respectivement sur n , n^ ... , n places , où nA+n~+ ... +n = n . P 1 2 p On remarquera aussi que: - cette façon "catégorique" de décrire les parenthèsages est bien adaptée aux systèmes binaires partiels, non forcément associatifs, dont les graphes uultiplicatifs sont un exemple typique ; - l'homomorphisme "longueur d'une suite" passe au quotient par ?f la catégorie /A/ catégorie comma de , soit (resp. P 1 1: /Ty* l/£ : /A/*/? ^ /// ^> IN S ) est une sous-catégorie de la (resp. l/Ç ). On peut aussi munir la catégorie P d'une structure mul- tiplicative. Etant donnée une suite d'entiers tier p , on désigne par s s = (k , ... ,k.) et un en- la suite d'entiers (k+p, ... ,k.+p) C 39 Si f: m ' > p et g: n s t on pose fBg = ra+n — ; IN i^v/ une flèche de p> q sont deux flèches de s > p+q , qai est bien encore SpS /A/ • Cette loi B est associative, mais non IN*/N commutât ive et elle ne définit pas un bifoncteur Par contre, elle est comptatible avec l'équivalence — ^ IN * Ç et au quotient elle définit cette fois un bifoncteur, encore noté 3 , (P de sorte que Soit G ,B) est une catégorie multiplicative. L(G) la ca- > e' de L(G) d'éléments de G sa- un graphe multiplicatif. On note tégorie de ses chemins . Un morphisme C: e (f , ... 9f+) est la donnée d'une suite tisfaisant: - d(f^ = e et , c(f.) = d(f. +1 ) , si i = 1, ... ,n-1 c(f ) x n' Comme pour la catégorie /A/ , la composition s'effectue par juxtaposition des suites, lorsque celle-ci a un sens. Les unités de L(G) l'unité e s'identifient à celles de de L(G) G et, pour e £G s'interprète comme la suite vide en Enfin, on remarquera que la construction syntaxique (interpréter G L(-) , e . est purement comme une réalisation de l'esquis- se de graphe multiplicatif). On dispose maintenant d'une opération naturelle de la catégorie P des parenthèsages sur la catégorie mins d'un graphe multiplicatif quelconque G . En effet, soit D: n de C: e une flèche de que > e' D opère sur >p C , et on note des che- P et soit de longueur n ; on dit une flèche L(G) L(G) D*C le résultat de cette opé- ration, si et seulement si les p renthèses représentées par s'appliquent effectivement au che- D dispositions cohérentes de pa- C 40 min C (c'est-à-dire correspondent à un calcul que l'on peut effectuer dans G sur les éléments constitutifs de obtient alors un chemin de longueur Il est clair que, si de P et si D': p C ); on p : c'est D*C . > q est un autre morphisme D'*(D*C) ou (D'.D)*C est défini, les deux sont définis et égaux (on peut donc ici supprimer la parenthèse!). On remarquera également que cette opération naturelle de sur L(-) est purement syntaxique. Soit toujours G un graphe multiplicatif. Nous allons construire maintenant la 2-catégorie des programmes de Si P D Ê/P formelle" opère sur G • C £ L(G) , nous disons que la "flèche C — r — > D*C est un programme dans G (c'est un hypermorphisme dans la terminologie générale de C. Ehresmann), L'opération de p sur L(G) confère aussitôt à l'ensemble G une structure de catégorie ayant pour des programmes dans objets les chemins de G et pour laquelle la composition s'y fait en série. La structure multiplicative de P permet de composer les pro- grammes en parallèle. En effet, 3oit 1 C et des éléments de P composables, D et D D*C et D'*C définis, alors on voit que C .C des programmes t C— — > D*C et e' vers C — ~ > D'*C . se trouve ainsi structuré PLG : à chaque couple correspond la catégorie les 0-morphismes). (D'3D)*(C .C) est > (D f *C) .(D*C) est le composé parallèle en une 2-catégorie notée les chemins de et supposons (D'*C ).(D*C); dans ce cas nous di- L'ensemble des programmes dans G tés de G des chemins ! défini et égal au composé sons que C e (e',e) d'uni- PI£(e',e) qui a pour objets (on doit évidemment adjoindre aussi C 41 4»2. Associativités. On dispose d'une notion "naturelle" d'associativité. Supposons, en effet que G tons est un graphe multiplicatif et no- N(G) la catégorie libre engendrée par G . Ehresmann l'a construite comme quotient de la catégorie libre des chemins propres L C.G3 par l'équivalence bicompatible engendrée par la relation identifiant (g,f) et (g,f) £ G * G . Désignons alors par (g.f) , dès que n^: G > N(G) la "projection canonique" . Nous disons que G est associatif si, et seulement si, nn est un monomorphisme. Dans ces conditions, nous pouvons énoncer la: Proposition. Pour qu'un graphe multiplicatif G soit asso- ciatif, il faut et il suffit que la condition suivante soit satisfaite: ( A ) . Chaque composante connexe de chaque catégorie PLG(e',e) contient au plus un objet (i. e. un chemin de gueur G ) de lon- 1. Preuve. Soit M(G) l'ensemble des composantes connexes des catégories PLG(e',e) (entre autres éléments, il y a les composantes des chemins du genre (e) , où e <£ G ) . La composition en parallèle des programmes de G est compa- tible avec la relation de connexité; en effet, étant donnée une connexion (D , ... ,D ) de C vers C , on peut tou- jours, quitte à ajouter des programmes npu':res aux endroits convenables, supposer que: (i). n est assez grand et impair, (ii). les programmes ont le sens indiqué, soit: + + c i, T ! — ^ cv fc-i uk Je C, r >C k-l iJk K , si k est impair, , si est p a i r , k C 42 + C n » C et C = C 0 n Etant données deux connexions, l'une de C vers C et l'autre de C vers C' , grâce à la remarque précédente, on peut supposer qu'elles se présentent toutes deux comme suit: ° — > C 1 < — C alors, si »Ci < C 2 °n-1~>C Ci C' C .C est défini dans ' > G' , L(G) , les composés C'.C (et d'ailleurs les C. .C. aussi) le sont et J i C'.C >CÎ.C i < C'.CC' ^ C d n 1 1 D^SD1 D^HD2 * ^ n-1 >C'.C D^HD n met en connexion C'.C et C'.C . Dans ce cas, M(G), muni de la composition (passée au quotient) devient une catégorie dont les unités sont les classes des chemins (e) , où e €: G Q . Le graphe multiplicatif G se plonge naturellement dans M(G) en faisant correspondre à f 6 G la classe m G (f) , modulo la connexité, du chemin (f) . Puisque (g,f) — r — > (g.f) est un programme dans G , lorso que (g,f) £ G * G ( D étant la classe de 2 ~ 7 T p > 1 d a n s P ) , il est clair que m Q : G > M(G) est un foncteur. Soit alors F: G > B un foncteur de but une catégorie B ; soit C = (f , ... ,f ) € L(G) et C* la classe de C modulo la connexité ; si F est un prolongement possible de F à M(G) le long de nu , on doit nécessairement avoir: F(C) = F(f n ) F(^) ; ceci définit F car la quantité de droite ne dépend pas du re- C 43 présentant C de C choisi, puisqu'elle est calculée dans une catégorie. Il est clair que que M(G) F est un foncteur, de sorte est aussi catégorie libre engendrée par le graphe multiplicatif G et nu le projecteur correspondant. Donc il existe un isomorphisme unique tel que nu X'-IIU = n^ ; n- nu > N(G) est un mono si, et seulement si, l'est et la condition tion du fait que £f : M(G) (A) n'est qu'une autre formula- est justement un mono. Ceci achève la preuve de la proposition. On peut aussi définir d'autres notions d'associativité. L'associativité "traditionnelle" , portant sur trois éléments x , y , z , s'exprime ainsi pour les lois binaires partielles: (tA). si (x.y).z et x.(y.z) sont définis, ils sont égaux. Il est clair qu'un tel axiome a quelques conséquences dans un graphe multiplicatif mais il n'autorise pas, à lui seul, la suppression des parenthèses. Quelques auteurs (Dedecker, en particulier) ont pensé à renforcer 1'axiome (tA) en un axiome (fA) , que nous qualifions pourtant d'axiome faible d'associativité; nous l'énonçons, dans notre formalisme: (fA). si tels que D et D': n D*C et D'*C (fA) et Les axiomes î> 1 sont des éléments de soient définis, alors P D*C = D'*C . (A) ne sont pas équivalents comme le montre le contre exemple suivant d'un graphe multiplicatif G. faiblement associatif, mais non associatif: - G. est le graphe multiplicatif représenté ci-dessous (où cer- taines flèches ne figurent pas) et pour lequel la structure est précisée par les équations qui suivent: C 44 X 2* X 1 = y x 2*71 = u y v ' V3=v 3' > X 3 *X2 = X S ' 7* - 7 o = y"c > ss X y 6 6 74-(75^) = (74.75)^ On remarquera que: - dans G„ -1 ', on voit que Xg partir de x,1 , x 2 , x^ , x^ et y, ont pu être construits à et y1 , y 2 , y ,y respectiv- C 45 ment, sans avoir besoin de composer v et u ; on peut ajouter, d'ailleurs, d'autres composés (par exemple v.x- = x. .x,- , x^.u = Xc-x-, t 74»7c * v.y 2 , y^.u = y^.y1 ... ) et constitu- er ainsi d'autres contre exemples car tant qu'on n'ajoute pas v.u le graphe multiplicatif obtenu reste faiblement associatif mais non associatif puisque x^ et y,- sont identifiés dans N(G) (ceci résoud un problème posé dans ma Thèse, chapitre 3 > Amiens 1978 ) ; - il faut bien évidemment faire ici le rapprochement entre ces contre exemples et les graphes multiplicatifs doubles S., G et B'G ; - la proposition précédente revient à présenter quotient de L(G)\L(G) N(G) et non comme quotient de comme L £ G j , ce qui met en évidence le rôle des parenthèses; en d'autres termes, la condition (A) est la version syntaxique (i. e. esquissable) de la définition sémantique d'un graphe multiplicatif associatif; de ce point de vue, le résultat énoncé dans la proposition qui précède est évidemment très lié à l'étude générale des conditions syntaxiques de plongement d'une structure algébrique dans la structure algébrique libre (d'un type "plus fort") qu'elle engendre (voir "Conditions syntaxiques de plongement" I et II, par C. Lair, Diagrammes 2 et 3 ) : ce n'est pas encore clair (ou "qu'Lair"!) que ce n^en soit qu'un cas particulier. On peut aussi renforcer ( A ) en l'axiome d'associativité forte: (FA), si l'un des deux composés x.(y.z) ou (x.y).z est dé- fini, les deux le sont et sont égaux. On appelle alors précatégorie tout graphe multiplicatif forte- C 46 ment associatif, i. e. vérifiant (FA). Nous avons montré (Thèse, Chapitre 3> Amiens 1978) qu'effectivement (et ce n'est pas trivial) l'axiome axiome (FA) implique 1' (A) • Bien entendu, les exemples abondent de graphes multiplicatifs associatifs qui ne sont pas des précatégories. En voici un: Ce graphe est bien associatif mais ce n'est pas une précatégorie car Xp.x x-..(xp.x ) n'est pas défini; en ajoutant un élément seulement on obtient encore un graphe associatif qui n'est toujours pas une précatégorie. En tout cas, ces diverses associativités se définissent syntaxiqueraent en précisant des propriétés de l'opération de P sur L(G) ... (à suivre)