D IAGRAMMES L. C OPPEY Leçons commentées sur les monades Diagrammes, tome 34 (1995), p. 11-89 © Université Paris 7, UER math., 1995, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ DIAGRAMMES VOLUME 34, 1995 LEÇONS COMMENTEES SUR LES MONADES* L. Coppey Université Paris 7, U.F.R. de Mathématiques Tours 45-55-5ème étage 2y place Jussieu 75251 Paris CEDEX 05 FRANCE coppey@n*athp 7.jussieu.fr Sommaire Introduction. 1. Les conoyaux contractiles. 2. Monades et algèbres de monades. 3. Exemples de monades dans Ens . 4. Catégorie de Kleisli. D-syntaxes de Coppey. Ce texte est un développement de trois exposés faits par l'auteur, en octobre et novembre 1994. au groupe de travail Esquisses et Calcul formel (L. Coppey. D. Duval, C. Lair, J.-C. Reynaud. P. Sénéchaud) tenu dans le cadre du séminaire Catégories et Strucutres de l'Université Paris 7. Introduction. Le mieux consiste, je pense, à reprendre, avec des modifications mineures et quelques ajouts, le commentaire que j'ai consacré aux monades dans l'introduction de mon article Graphes structuraux , paru dans Diagrammes, Vol.24, Paris, (1990), et dont, au passage, je recommande vivement la lecture «...Unpoint de vue pour décrire efficacement l'algèbre dans une catégorie C consiste à étudier les diverses catégories de réalisations dans C d 'esquisses (projectives)... » «...Un autre point de vue pour décrire (au moins) de l'algèbre sur une catégorie C, 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.. » «...A toute monade T sur une catégorie est associée sa catégorie d'algèbres Alg(T ) au dessus de C. Ce qui a séduit à une époque déjà « ancienne » (années 66-72 en gros), et qui séduit encore aujourd'hui, 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 sur telle ou telle catégorie C: • équations d'une monade T sur C, • équations d'une algèbre, qui sont, à peu de chose près, semblables à celles de la monade, parce qu'une T-algèbre sur un objet C de C n'est qu'une contingence de la monade, au niveau de l'objet C, dit sous-jacent, et des relations particulières qui la définissent comme algèbre (voir plus loin le passage de \iç à 0 ...) ; chaque algèbre apparaît comme quotient canonique d'une T-algèbre libre, laquelle admet une description uniforme, donnée par l'expression (en C) des transformations naturelles définissant la monade... Si la description des monades abstraites revêt ce caractère uniforme, et tout compte fait assez simple (cf. § 1 et 2) c'est bien parce qu'elle prétend unifier, assez brutalement, toutes sortes de situations algébriques sur C dans un schéma unique, qu'on peut qualifier de calculatoire, mais qui sans doute aussi est trop général: en gros, il s'agit de calculer des termes abstraits en s'en donnant une présentation à deux niveaux (ou degrés) de liberté: le premier niveau correspond à celui des algèbres de termes (ou écritures) qui sont des algèbres 13 libres et le second niveau à celui des algèbres « deux fois libres », l'exemple simple est celui du calcul d'un mot dans un monoïde M : on commence par le présenter comme une simple écriture, c'est-à-dire en fait comme un « composé » de ses lettres (c'est le premier degré de liberté), et, si chaque lettre est elle-même le résultat d'un calcul du même genre, dans le monoïde en question, la condition d'algébricité explique que le calcul d'un élément du monoïde, partant d'un mot de mots, peut se faire en deux temps, et de deux manières (conduisant bien sûr au même résultat) en suivant l'un des deux chemins horizontaux suivants. Calcul global formel (concaténation des mots) Elément du monoïde M t Calcul du mot dans le monoïde M Calcul local réel (calcul de chaque mot du mot de mots) Si l'on ajoute à cela qu'une lettre peut toujours 's'identifier' à un mot à une lettre, on dispose alors de 'retours' évidents (par rapport au sens des calculs) et on voit apparaître ce dessin 'abstrait', dit du conoyau contractile. n —> i—i n <•— i—i < > qui est soumis à quelques équations simples (cf. § 1 et 2), et qui rend assez bien compte de Funiformité des descriptions monadiques dont j'ai parlé plus haut. 14 1. Les conoyaux contractiles. Considérons le graphe à composition (partielle) M suivant, défini par générateurs et relations: • les générateurs sont les flèches du graphe ci-dessous, y compris les identités en les objets A, BetC: -> C d d] ° • les relations sont spécifiées par les quatre équations suivantes ncl n°2 n°3 n°4 q d 0 = lc g d 1 =1 B f d, = d 0 .q q.f = q.g En toute rigueur, il conviendrait d'ajouter à la description graphique de M les flèches non figurées 1A, 1B , le , f.di = d0q , q.f = q.g . On peut identifier M à une esquisse sans cônes distingués: c'est l'esquisse des conoyaux contractiles. Soit en effet M > K une réalisation de M dans une catégorie K , i.e. un foncteur de M dans K . On obtient, dans K , un conoyau R(q) du couple (R(f) , R(g)) d'un type bien particulier; en effet, on a: • R(q).R(f) = R(q.f) = R(q.g) = R(q)R(g), d'une part, 15 • si R(B) > X est telle que h.R(f) = h.R(g) , une factorisation h de h à travers R(q) doit satisfaire. îî.R(q) = h , donc h.R(q).R(d0) = h.R(d0), donc ïî = h.R(d0) ! et effectivement cette flèche ïï est bien une factorisation de h à travers R(q) puisque l'on a: ïï.R(q) = h.R(d0).R(q) (équation n°l) = h.R(do.q) = h.R(fdi) (Rfoncteur) (équation n°3) = h.(R(f)R(di)) (Rfoncteur) = (h.R(f))R(di) (K catégorie) = (h.R(g)).R(d,) (hypothèse) = h.(R(g).R(di)) (K catégorie) = h.R(gdi) = h. (Rfoncteur) (équation n°2) On aura remarqué que ce calcul utilise: • l'équation n°l de M pour définir le seul candidat h possible, • les trois équations n°2, n°3, n°4, chacune une fois, pour prouver que h est un bon candidat, • la structure de catégorie K (associativité de la composition, unitarités.. ) et la structure du foncteur M > K, bref, à peu près exactement (i.e ni plus ni moins que) ce qu'on s'est donné Il s'agit bien d'un conoyau d'un genre particulier, car si q est conoyau du couple (f, g) dans K, il n'y a pas en général de flèches d0 , di (dites retours) permettant de définir un foncteur M R > K tel que R(f) = f , R(g) = g , R(q) = q , etc..On dit qu'il s'agit d'un conoyau contractile. Evidemment, un conoyau contractile est préservé par tout foncteur F, puisque si M —^-> K et K —?-> L sont des foncteurs, alors M —> L en est encore un ! F Un conoyau d'une catégorie K qui est préservé par tout foncteur K > L est appelé 16 conoyau absolu. On vient donc de rappeler qu'un conoyau contractile est un conoyau absolu, mais les conoyaux absolus ne sont pas forcément contractiles Notons au passage la caractérisation des conoyaux absolus qui « ressemble » aux équations abstraites de définition de M On emploie à cet effet des notations analogues, dans K, à celles utilisées pour décrire M . Soit donc un conoyau absolu dans K: B -> C g Lorsqu'on applique le foncteur Hom(C, -) : K > Ens, on obtient donc encore un conoyau dans Ens, à savoir Hom(C,B)- Hom(C,A -> Hom(C,C) g* où h^ (avec h = f, g, q, ...) désigne la composition à gauche par h de flèches venant de C. En appliquant le foncteur Hom(B, -) de K vers Ens, on obtient encore un conoyau dans Ens, à savoir. Hom(B,A) Hom(B,B) •> Hom(B,C) .B où h* (avec h = f, g, q,...) désigne la composition à gauche par h de flèches venant de B. Pour X = B ou C, on sait que Hom(X,C) est (à bijection unique-canonique près) le quotient de Hom(X,B) par l'équivalence engendrée par la relation élémentaire 8¾ ô' si et 17 seulement s'il existe X > A telle que f* (a) = ô et g* (a) = ô', soit encore f a = ô et g.a = ô' . Bien sûr une telle relation élémentaire n'est en général ni réflexive, ni symétrique, ni transitive. De ces deux conoyaux ensemblistes, on tire les informations particulières suivantes: • il existe (au moins) une flèche d0 e Hom(C,B) telle que q* (d0) = le , soit q.do = le , • et comme qf(do.q) = qd0.q = q = q?(le), on voit que d0.q et 1B sont équivalentes modulo (f*B, g? ), c'est-à-dire qu'il existe une suite d] , d 2 , ... , dn de flèches B >A telle que les égalités suivantes soient satisfaites. gdi = 1B f.di = gd 2 fd 2 = gd 3 fdn-i = gd n = d0q Ainsi, l'analogue de l'équation n°3 pour les conoyaux absolus n'est pas l'égalité « f.di = do q », mais seulement l'équivalence « fdi ^ d0.q » qui vient d'être décrite. Il n'est pas difficile alors de vérifier que tout ceci caractérise intrinsèquement (i.e. dans K) le fait que q est un conoyau absolu du couple (f, g) Revenons aux conoyaux contractiles pour en donner quelques modèles minimaux (ou réalisations, réputées plus « concrètes »), et qui sont assez standard. 1.1. Le modèle ensembliste « minimum ». Nous posons: A = {ai,a 2 ,aa} B = {b,,b 2 } q , f, g , do, di désignent respectivement les applications suivantes: • B—^C • A est définie par q(bi) = q(b2) = c > B et A —5—> B sont définies par: 18 C = {c}; • f(ai) = b, f(a.) = b 2 , • g(ai) = b, g(aO = b 2 , • f(a2) = b, g(a2) = b 2 , • C —^-> B et B —^-> A sont définies par. • do(c) = bi, • di(bi) = a] di(b2) = a2. On observera que: • q , f , g sont surjectives, • do, di sont injectives, • f et g sont égales sur {ai , a3} et ne diffèrent qu'en a 2 , lequel élément de A fait office <¥ aiguillage, lorsque, parti de B avec di , puis arrivé en A, on veut retourner en B (par 1.2. f ou g) Le modèle ensemble-ordonné-iste « minimum ». On peut préciser le modèle ensembliste précédent en structurant A , B et C en ensembles ordonnés (A , <), (B , <), (C , <) • pour A : ai < a2 comme foncteur de C vers B, • di , comme foncteur de B vers A, envoie c sur b i , envoie bi sur ai , et envoie w sur u . A ce point, et en interprétant le composé de deux flèches consécutives —^->—^ comme le résultat d'un calcul prenant x comme argument (ou donnée de départ) et (p comme ensemble de règles de calcul (ou programme) [ x -> cp(x) ] , alors f et -> g sont les premières phases de deux calculs à deux temps, conduisant au même résultat -> -> > • dans le cas de f, il s'agit du calcul de u(ai) , précédant celui de v(u(ai)), lequel sera -> exécuté dans la phase correspondant à q -> -> [ w( b i ) = c ] . ( l) u(a,) -> c = v(u(a,)) v v W J • dans le cas de g , il s'agit du calcul de v(u), précédant celui de (v(u))(ai), lequel sera exécuté dans la phase correspondant encore à q ( ai g ,v(u) y [ w( b i ) = c ] : i? -• c = (v(u))(ai) w Ainsi: • le calcul correspondant à f peut être qualifié de local et réel ( b i = u( a i )) ; • le calcul correspondant à g peut être qualifié de global et formel ( w = v(u)), reprenant ainsi les expressions employées dans l'introduction. 21 1.5. Le modèle «graphe à composition» «intéressant» « minimum ». C'est un modèle, dans la catégorie des graphes à composition, suggéré par le modèle catégorique précédent. Ses objets A , B , C sont les « relâchés » des objets A , B, C, dans le sens où on n'exige plus l'associativité : -•;'' w b A = B = /1 .•"'•' w'b les flèches f et g entre A et B sont définies par • f(a) = b f(v) = w f(u) = P(b) = a(w), de sorte que l'on a f(ua) = f (a) = b • g (a) = b' et f(v(ua)) = wb , g (v) = w' g (u) = p(b') = a(w'), de sorte que l'on a: g (vu) = w' et g ((vu)a) = w'b' . Bien sûr, q^ égalisera les deux composés wb et w'b' sur c , en envoyant w et w' sur P(c). Pour être plus complet, ce modèle doit comporter aussi les retours do et di dont la définition est évidente. 22 1.6. Autres modèles dérivés possibles. On peut encore assouplir le modèle précédent dans la catégorie des graphes à réécriture d'objets ... par exemple. Nous arrêtons cependant ici cette liste de modèles, pour ne pas trop alourdir. D'autres modèles « concrets » apparaîtront naturellement dans les paragraphes suivants, ce sont d'ailleurs eux qui, par leurs incessantes apparitions dans la théorie des monades, m'ont incité à « isoler » le conoyau contractile pour en faire l'analyse séparée qu'on vient de lire 23 2. Monades et algèbres de monades. La catégorie C c des transformations naturelles entre foncteurs de C vers C (ou endofoncteurs de C ) possède une structure supplémentaire: c'est aussi un monoïde ; • soient X : S -> T et X': S' -> T' deux transformations naturelles, alors on dispose de la transformation naturelle « composée » X' X : S'S —> T'T , qui en un objet C donné est définie de l'une ou l'autre façon: S'T(C) (rxy S'S(C) -> T'T(C) T(lc) À' S(C) T'S(C) • On a bien X'KD S'(?ir) = T'(^c) Â'sic» , car >.' est une transformation naturelle de S' vers T' et on vérifie sans peine les points suivants : • cette loi est associative, possède un élément neutre, qui n'est autre que la transformation naturelle identique du foncteur identique de C, ainsi Cc est bien un monoïde et cette structure de monoïde se « restreint » à la classe d'objets Ob(Cc), qu'on peut identifier aux transformations naturelles identiques, et n'est autre, de ce fait, que la classe des endofoncteurs de C , munie de la composition usuelle des foncteurs, • les lois «.» et « » sont permutables, dans ce sens que l'on a : (V2.V1XX2.X1) = (V 2 V 2 ).(X 2 A,i) • On peut encore dire qu'en désignant par x la loi de monoïde jusqu'ici notée sans symbole particulier, x : C c x C c -> C c est un foncteur: en effet, l'élément (X'2, X2) est composable avec l'élément (k\ ,À,i) si et seulement si deux, et dans ce cas on a: 25 X W i et X2.X1 sont définis tous T((X'2,X2).(V,,X,)) = x(A.'2.X',,X2.X,) = (V2.X',)(X2.X,) = X(V2,X2).T(V,Al) On peut aussi dire que la composition dans la catégorie C c définit un homomorphisme de monoïdes: posons C c * C c = { (X2, X\) \ \i\\ soit défini }. On voit que C c * C c est un sous-monoïde du monoïde produit C c x C c : en effet, soient (?t2, Xi), (W, X'i) G C C *C C , alors ( U ^ W O G C ' * ^ ' , car (Jft'iXi) = p(X',)p(X,) et a(X'2X2) = a(V2)a(X2), d'où, puisque a(X'2) = P(X'i) et a(X2) = p(À,i) , les composés ci-dessus sont encore égaux, et la composition k = « . » : C c * C c —> C c est un homomorphisme de monoïdes, c'est-à-dire que l'on a k[T((V2,XU(X 2 ,X,)] = k[x(V2,X2),T(V,,X0] = T(V2,X2).X(X'i^i) = T[k(V2,Vi),k(X2,X,)] = (V2.V1KX2.XO. Cette loi de monoïde ( x , s'il faut à tout prix la désigner) ne sera vraiment utilisée parla suite que pour des composés, à gauche ou à droite, d'une transformation naturelle X : S -> S' avec un foncteur T (identifié à Idi T —» T !) : on écrira ainsi TX TS —> TS' et XT : ST -» S'T, sachant qu'en un objet C de C , on a: Tlc= T(Xc) : TS(C) -> TS'(C) XTc = XT(C): ST(C) -> S'T(C). 2.1. Définition d'une monade dans une catégorie C. [Pendant longtemps les monades se sont aussi appelées des « triples », car leur désignation pratique mobilise trois symboles - cf. ci-dessous. Le moins qu'on puisse dire est qu'il eût mieux valu les appeler des « doubles », puisqu'elles sont constituées de deux transformations naturelles - cf. encore ci-dessous. Le choix, qui prévaut actuellement, du mot « monade » a l'indiscutable avantage de trancher la question entre « double » et « triple »; pourtant je trouve ce choix assez malheureux, et j'aurai bientôt l'occasion d'expliquer 26 pourquoi; quant à la possible référence à Spinoza, je la laisse à ceux pour qui la culture est affaire de vernis]. Une monade dans C est un « triplet » T = (T, s , \x) constitué de deux transformations naturelles 8 et [i, qui ont pour but commun un endofoncteur T de C , et pour sources respectives Idc et T2. Ainsi, en un objet C de C , on dispose des flèches 8c : C -> TC et |ic : T2C -> TC , en opposition : C -> TC <- T2C . De plus, ces données sont soumises aux axiomes suivants. • (Ui) \i.zT = U , soit en tout objet C : ne sT c = I^C&TC = hc , • (U2) |i.T8 = le , soit en tout objet C : |ic Tsc = |ic T(8c) = ITC , • ( i T | i = |u |iT , soit en tout objet C: (icT|Lic = \Xc T(|ic) = l^cltT c = I^CIITC (A) Classiquement, on dit que (U), conjonction logique de (Ui) et (U2), est l'axiome d' « unitarité » et que (A) est l'axiome d' « associativité » de la monade. Cette terminologie me paraît tout aussi malheureuse que le choix du mot « monade », et pour les mêmes raisons; on verra cela plus loin En un objet C, on obtient ainsi, et au moins, le dessin suivant: 8c TC TC T|ic Analysons, pour chacun de ces conoyaux contractiles, en quoi ils sont bien des réalisations du conoyau contractile abstrait M décrit dans le paragraphe 1. A cet effet, nous respectons l'ordre des 4 équations concernant justement q, g, f, do, di , ce qui permet de retrouver aisément quelle flèche est réalisation de quelle flèche. • pour (i) : • HC.£TC = le est l'expression de (Ui) en C, • HTC.£T2C = 1T2C e s t l'expression de (Ui) en TC, i.e. après application de T à C, • T|IC-£T2C = £TC|IC est l'expression de la naturalité de s en [ic. • |OcT|ic = MC-MTC est l'expression de (A) en C ; • pour (ii) : • Hc-Tsc = ITC est l'expression de (U2) en C, • T|iC T28c = T(nc.Tec) = 1T2C est l'expression de (U2) en C, puis application de T, • |iTcT28C = T8c|ic est l'expression de la naturalité de [i en e c , • MCMTC = |ic-T|ic est l'expression de (A) en C . On notera bien les points suivants: • la répartition de (Ui) et (U2) entre (i) et (ii) respectivement, • l'inversion du sens de l'égalité (A) entre (i) et (ii) (échange des rôles de |iT c et T|iC)> 28 • l'échange des rôles de e et |i entre (i) et (ii). Il y a une parfaite symétrie entre les deux situations, compte tenu de l'échange des rôles entre |iT et T|i d'une part et entre e et |i d'autre part. Ceci peut paraître étrange à qui « connaît » la théorie des monades (voir aussi plus loin les exemples de monades et d'algèbres). Il y a à ce phénomène une explication qui viendra techniquement après. En fait, si la situation peut paraître quelque peu ambiguë, c'est dû au fait que, naturellement en C, ne présente à la fois le caractère d'objet (algèbre libre engendrée par C) et le caractère de flèche (présentation libre de l'algèbre libre engendrée par C). Je reviendrai sur tout cela. L'esquisse de conoyau contractile peut être structurée en « esquisse » de monade : • en y ajoutant deuxflèches:d -i (qui se réalisera en e) et d'o (qui se réalisera en Te), • en imposant aux objets d' « opérer » partiellement sur les flèches (et donc aussi sur euxmêmes, quand on les identifie à leurs flèches neutres), conformément au schéma suivant, qui reprend en partie les notations propres aux monades afin de décrire cette « opération partielle formelle » de la manière la plus suggestive et sans doute la plus rapide possible ( T, TT = T2,..., Te, eT,..., T|i, |aT, ..) : T3 T <" En fait, en reprenant ce qui est dit plus haut, à part les données (naturelles), e et \i9 on retrouve deux flèches , Te et eT, qui jouent le rôle de d0, et trois flèches , T2e, TeT, eT 2 , qui jouent le rôle de di (seules T2e et eT2 ont, de ce point de vue, une interprétation stricte, à savoir celle indiquée ci-dessus, la flèche TeT restant pour l'instant une flèche de « soudure » dont le rôle n'est pas clair). 29 On peut encore dire, en privilégiant eT , eT2,... par rapport à Te , T2e , TeT,... qu'en un objet C de C, on dispose d'une réalisation de conoyau contractile. T2C , TC -—<.--• Ter à deux « différences » près : • il y a une flèche « supplémentaire » (côté conoyau), c'est Tec , par exemple, avec l'équation « supplémentaire » \xc Te c = ITC , équation qui ne résulte pas des naturalités de e et de |i, ni des autres équations de monade, • il y a une flèche « inutile » en principe, c'est eT 2 c (qui réalise di) ; l'inutilité de la faire figurer, en l'objet C (pour la version « monade ») tient aux deux raisons suivantes: • l'égalité T|iC&T2c = ETCMC est contenue dans la donnée de e comme transformation naturelle (en Me 0 > • l'égalité jiTc 8T2C = 1T2C est inscrite, au même titre que l'égalité \iç.e-rc = ITC dans l'axiome (Ui) de monade, plus précisément, c'est une donnée qui ressort plutôt du décalage de C vers TC, puisqu'elle correspond à q.do = 1, mais en TC au lieu de C. Remarquons enfin qu'on n'a pas représenté ec : C -> TC , qui aurait du mal ici à figurer comme réalisation de do seul, dépourvue a priori des réalisations concommitantes de q, f, g, ...En fait cela tient au rôle hybride déjà souligné de la flèche |ic. Bien évidemment, ces équations de base d'une monade, qui s'expriment donc (naturellement en C) dans C c , engendrent d'autres équations, en tous degrés, par exemple entre les transformations naturelles entre T p l , T p , Tpl , pour tout p > 1. Nous laissons cela en exercice. Je n'ignore pas que le choix du mot « monade » n'a de judicieux que l'allusion qu'il autorise à 1' « esquisse » ci-dessus et à la structure de monoïde de C c , indiquée au début. 30 2.2. Homomorphismes entre monades. Soient T = (T, s, \x) et T* = ( T \ e \ | . 0 deux monades sur une même catégorie C Ce sont donc des réalisations (ou modèles) de T« esquisse de monade » décrite cidessus dans C c , regardée comme catégorie munie de l'opération naturelle des objets sur les flèches déterminée par i (cf le début du paragraphe) A ce titre, ce sont au moins des foncteurs de M vers C c , et par conséquent on sait qu'un homomorphisme de T vers T'est défini au moins par une transformation naturelle h T —> T' entre ces foncteurs Cependant je laisserai la ce point de vue qui m'entraînerait trop loin Il faut remarquer encore que la naturalité à elle-seule intervient ici à deux niveaux différents d'une part, comme il vient d'être dit , entre foncteurs de M vers Cc , et d'autre part entre foncteurs de C dans C Aussi il me semble utile de définir directement ( « à la main » ) ce qu'est un tel homomorphisme h T —> T* Un homomorphisme h T —» T' est une transformation naturelle h T —> T' telle que le diagramme ci-dessous commute h: > T'° avec les conventions naturelles suivantes • h° est la transformation naturelle identité de Idc , • h1 est la transformation naturelle h , • h2 est un abrégé de T'h hT = h F Th 31 Ces homomorphismes se composent naturellement, et on obtient ainsi la catégorie Mon(C) des monades sur C et homomorphismes entre elles Cette construction (C |—> Mon(C)) n'est pas fonctorielle 2.3. Algèbres d'une monade. Soit T = (T, s, |.i) une monade sur une catégorie C On dit que (C, 0) est une T-algèbre sur l'objet C si 0 est une flèche de source TC et de but C satisfaisant les équations suivantes • 0 ec = l e , dite abusivement (cf les exemples) loi limitante , • 0 T(0) = 0 |Ac , dite abusivement (cf les exemples) loi d"associativité , de sorte que TC est un conoyau contractile dans C (pour lequel on a repris les notations standard introduites au paragraphe 1 ), la correspondance est la suivante, au niveau des équations • n°l q d0 = le correspond à la loi dite d'unitarité , soit 0 e c = le , • n°2 g di = 1B = ITC correspond à l'axiome (Ui) des monades, soit |^c £TC = ITC, • n°3 f.di = d0 q est l'expression de la naturalité de e en 0, soit T(0).eTc = e c .0, • n°4 q f = q g correspond à la loi dite d'associativité, soit 0 T(0) = 0|a c . Etant données deux T-algèbres (C,0) et (C',0'), on dit que h : (C,0) -> (C',0') est un homomorphisme d'algèbres si h C —» C est une flèche de C satisfaisant h0 =0'T(h) 32 Si h (C,0) -» (C',0^) et k (C',0') -> (C",0") sont deux homomorphismes d'algèbres, la flèche composée k h C —> C" définit encore un homomorphisme d'algèbres de source (C,0) et de but (C",0"), dit compose de h et de k, et noté k h (C,0) -> (C",0 M ) On obtient de la sorte la catégorie Alg(T) dite des algèbres de la monade T • ses objets sont les algèbres (C,0), où C est un objet de la catégorie C , • ses flèches sont les homomorphismes h (C0) -> (C',0'), où h . C -> C est une flèche de la catégorie C, • sa composition est celle indiquée ci-dessus On dispose alors de deux foncteurs naturels • le foncteur d'oubli Ui Alg(T) —> C , défini par • Ui(C,0) = C , pour toute algèbre ( C 0 ) , • U](h) = h , pour tout homomorphisme h . (C,0) —> (C',0'), • le foncteur « algèbre libre » Lj C —> Alg(T), adjoint à gauche de Ui, défini par • L! (C) = ( T C u r ) , pour tout objet C de C, • L,(h) = Th (TCnc)-> (TC\|ic ) , pour toute flèche h C-> C de C En effet, on vérifie successivement les points suivants • pour tout objet C de C, (TC,|ic) est une algèbre sur TC on a d'une part, |i c £TC = ITC (telle est l'expression de raxiome (Ui) en C) et d'autre part, \iç (iTe = Me T(ic (telle est l'expression de l'axiome (A) en C), • pour toute flèche h C —> C de C , Th TC —> T C définit un homomorphisme Th de source (TC,|ie) et de but (T'Cne ) , car |i est une transformation naturelle de T2 vers T, donc on a bien, en C \xc T2h = Th |AC , • soit (C',0) une algèbre en C et f C —> C une flèche de C, s'il existe un homomorphisme f : (TC,|Lic) —> (C',0) qui « prolonge » f, c'est-à-dire tel que f tç = f, alors f vérifie 0 T f = f |ic puisque c'est un homomorphisme d'algèbres , et en composant avec Tec à droite, on trouve la valeur nécessaire unique possible de f, à savoir f = 0 Tf Te c = 0 T(f e c ) = 9Tf ; 33 et f satisfait bien les conditions requises, à savoir • (0 Tf) Se = 0 (Tf 8c) = 0 (ec f) = (0 Ec-) f = f, et • (0 Tf) n c - 0 (Tf |.ic) = 0 (Me- T2f) - (0 \xc ) T2f = (0 T0 ) T2f = 0 T(0 Tf), ce qui achève de prouver que (TC,(ic) est bien une algèbre libre engendrée par C, avec comme « plongement » e c C —> TC (en général, e c n'est pas un monomorphisme, et l'emploi du terme « plongement » est donc abusif) Bien évidemment, cette correspondance (C —» (TC,|ic)) se prolonge en un foncteur adjoint à gauche Lj de Ui (voir la description générale d'un tel « prolongement », dans le paragraphe intitulé « Monade associée à une adjonction ») 2.4. Création des conoyaux de paires contractiles. Le foncteur Ui a la propriété suivante , dite de « création des conoyaux des paires contractiles » : • soient f et g des homomorphismes de même source (Ci, 0i ) et de même but (C, 0), supposons que f ( = U] f ) et g ( = Ui g ) ont un conoyau contractile q (on reprend les notations do et di du premier paragraphe), alors il existe une unique algèbre (Co, 0o ) telle que q définisse un homomorphisme d'algèbres q (C , 0 ) —> (Co, 0o ) qui est un conoyau de f et g On dit encore que (Co, 0o ) est F algèbre quotient de (C , 0 ) par q (ou (f,g) ) a) Construction de 0 O . Comme q C —» Co est un conoyau contractile, il est absolu, et donc il est préservé par T = UiL] ; Tq est donc un conoyau (absolu) de Tf et Tg dans C . D'autre part, on a les égalités suivantes • (q.0).Tf = q (0Tf) = q.(f.0i), car f est un morphisme de 0i vers 0, • (q 0).Tg = q. (0 Tg) = q.(g.0i), car g est un morphisme de 0i vers 0, et comme q f = q g , il en résulte que q 0 coégalise Tf et Tg, il existe donc une unique flèche 0O TC 0 ->C 0 telle que 0O Tq = q.0 34 b) (Co, 0o ) est une T-algèbre et q : (C, 0) -> (C0, 0O ) est un homomorphisme. On a déjà (0O sCo ) q = 0o (Eco q) = 0o (Tq ec) , par naturalité de e, = (0o Tq) £e = (q 0) Er , par construction de 0 O , = q (0 te) = q , car 0 est une T-algèbre , on en déduit que 0O Eco = Idco Ensuite, en posant 0 = 0 T0 = 0 \ic , on peut reprendre mot à mot l'argument qui a servi à construire 0O et en remarquant que T2q est un conoyau (absolu) de T2f et T2g , il existe donc une unique flèche ©o telle que 0 ( , T2q = q 0 , or cette flèche est aussi bien 0o T0O que 0o.|iai , qui sont de ce fait égales (0O T0O) T2q = 0o T(0O Tq) = 0O T(q 0) - (0U Tq) T0 = q 0 T0 = q 0 ^ = q 0 = 0o Tq | ^ = (0o |Lico ) T : q , 0o est bien une T-algèbre et q définit un homomorphisme q (C, 0) -» (Co, 0o ) , puisque, par construction . 0O Tq = q 0 c) q est un conoyau de f et g dans Alg(T). C'est déjà un coégalisateur, puisque q f = q g dans C , soit alors h (C,0) -> (C',0') un homomorphisme d'algèbres qui coégalise f et g , comme q est un conoyau de f et g , il existe un unique h' Co -> C tel que h' q = h Montrons que h' définit en fait un homomorphisme h' de (C0 0o) vers (C\ 0 ' ) , c'est-à-dire que 0' Th' = hf 0O Or on a (0'.Th')Tq = 0'T(h'q) = 0' Th = h 0 = (h' q) 0 = h'(q 0) = h'(0 O Tq) = (h'0 O ) Tq, et comme Tq est un conoyau, on peut conclure que 0\Th' = h' 0O Nous verrons que cette propriété (dite « critère de monadicité de J.Beck ») caractérise à isomorphisme près les foncteurs tels que Ui parmi les foncteurs bien fidèles : on appelle ainsi tout foncteur U qui satisfait la propriété suivante si U(h) = U(h') et si h et h' ont même source, alors h = h' (notion qui, sous cette forme, est due à C Ehresmann); un foncteur bien fidèle est évidemment fidèle, et de plus, si U(k) = Idc , alors k = IdA où A est la source de k. 35 2.5. Monade associée à une adjonction. Supposons donnée une catégorie (de structures) A au dessus de C, i e un foncteur (d'oubli) U A —> C , supposons que tout objet C de C engendre une structure libre L(C) relativement à U c'est dire qu'il existe un morphisme Ec C -> UL(C), tel que le couple ( L(C), Ec ) possède la propriété universelle suivante: V A, objet de A, V f • C -> U(A), 3' f L(C) -> A tel que U(f ) £e = f, On dit encore que tout morphisme f C —» U(A) , de source C et de but sous-jacent à une structure A, se « prolonge » de manière unique en un homomorphisme f L(C) —> A entre structures, l'équation U(f ) Ec = f exprimant justement ce « prolongement » , en général , un morphisme tel que £e n'est pas un « plongement », i e un monomorphisme, et c'est pourquoi l'expression « prolongement de f » pour qualifier f est quelque peu abusive Un choix C h^ ( L(C), zc ) , pour tout objet C de C, détermine alors univoquement un foncteur adjoint à gauche de U, noté encore L . soit g . C —> C un morphisme de C , on dispose de la flèche f C —» UL(C') définie par f = s c g de but sousjacent à la structure L(C'), la propriété universelle de (L(C), EC ) s'applique et fournit un f . L(C) —> L(C') unique « prolongeant » f, on pose f = L(g), et on a UL(g) EC = £c g On vérifie sans peine que L est bien un foncteur adjoint à gauche de U , de plus la dernière égalité traduit la « naturalité » de la famille (eç)ç e CMO , i e le fait qu'elle définit bien une transformation naturelle E Idc -» UL . Ainsi s'amorce dans C une certaine monade dite associée à l'adjonction (U,L,E). Posons en effet T = UL , on dispose déjà de la transformation naturelle E Idc —> T ; reste à définir alors la transformation naturelle \i T2 -> T 36 • tout d'abord, soit A un objet de A , c'est une U-structure au dessus de UA et Idiw est une flèche de C de but UA particulière, par la propriété universelle de structure libre, il existe donc une unique flèche dans A, soit ôA LUA —> A , telle que UôA £i A = Idi A -de plus, la famille (ôAK e OHM définit une transformation naturelle de LU vers Id\ en effet, si g A -> B est une autre flèche de A , on trouve g ôA = ÔB LU(g) comme unique flèche qui « prolonge » Ug UA —» UB en un homomorphisme h LUA —> B • U(gô A )£iA = (UgUô A ).£iA = Ug.(U8A.EiA) = Ug , mais aussi • U(ô B LUg).£ l A = (U5B ULUg) EL-A = UÔB(£rB Ug) = (U8 B Em) Ug = Ug • soit alors C un objet de C , on peut appliquer ce qui vient d'être dit en choisissant A = LC, il en résulte qu'il existe une unique flèche he L(TC) -> LC telle que Uh r .£Te = IdTc , c'est la flèche h c = ôi_c , on pose alors [ic = Uhe une transformation naturelle qui n'est autre que La famille (h c = SLC)C e OHO définit 5L, avec les conventions de notations introduites au début de cette section, de même, la famille (|ic)c e <>b<<. définit une transformation naturelle qui n'est autre que (.1 = UôL Vérifions que T = (T, E, |i) est bien une monade dans C On doit montrer la validité des axiomes (U) et (A) de monade • (Ui) pour tout objet A de A, on a Uô A £i A = Idr A , en particulier en A = LC, il vient bien UÔLC £IXC = I d u c , soit encore \ic Zjr = IdTc , donc \x ET = l c • (U 2 ) pour tout objet C de C, on a (|i c T E C ) EC = (UôLc U L E C ) Se = UôLe ( U L E C EC) = U6LC-(EIXC ^C) , car E est naturelle, = (UÔLC.ELXC)EC = Ec , et la propriété de structure libre pour LC entraîne alors |ic TE C = Id-rc , on observera bien qu'on vient d'utiliser. • le fait que (LTC, E T C) est une structure libre sous la forme UÔLC-EIIX = IdTc , • le fait que (LC , E C ) est une structure libre sous forme de simplification par s c , • le fait que E est naturelle, 37 ceci explique en partie pourquoi une monade donne naissance, pour chaque objet C, à, non pas un seul, mais deux conoyaux contractiles apparemment symétriques, de même but TC. • (A) pour tout objet C de C, on a : |ic.T|ic = |ic T(jic) = UôLc UL(Uôic) = U(ôLc LUôLc) , par définition de (.1, = U(ÔLC.ÔLIXC) = U(SLCÔLTC) = par naturalité de ô, = UÔLC UÔLTC = M-C-M-TC , par définition de \x , on a donc bien |i.T|i = |i|iT . La naturalité de ô est donc l'argument essentiel ici , mais cette naturalité est aussi celle qui assure la propre naturalité de j.i (de T2 vers T) ; en ce sens, on peut dire que l'axiome d'associativité de monade « prolonge » la naturalité de |i (c'est ce point précis qui est à l'origine des D-algèbres et de leurs syntaxes) : tout se passe « comme si » les flèches \xç étaient de la forme T( ) , ce qui n'est pas le cas en général Nous reviendrons plus loin sur ce point, à propos des D-algèbres 2.6. Foncteur de comparaison tTEilenberg-Moore. Partons maintenant d'une situation d'adjonction (U, L, E) A —» C , par la construction précédente, on dispose alors de la monade T = (T, E, |i) dans C associée. A cette monade est associée la situation d'adjonction algébrique décrite plus haut et dont nous reprenons les notations : (Ui, Li, E) : Alg(T) —» C Notons bien qu'il s'agit du mêmes ! Le foncteur de comparaison d'Eilenberg-Moore K A —» Alg(T) est Tunique foncteur possible qui commute à la fois avec les oublis U et Ui et leurs adjoints L et Li dans le seul sens possible : Ui K = U et Fi = KF Examinons cela de plus près • soit A une U-structure (objet de A), et C = UA, soit ôA l'unique homomorphisme (flèche de A) de LC vers A tel que UôA Se = Idc ; posons G = Uô A , on a déjà 0.E C = Idc ; de plus on trouve: G T(6) = UÔA ULUÔA = U(ÔA.LUÔA) = U(8A.8LVA) , car ô LU -> 1A est naturelle, = U(ÔA.5LUA) = U8A.UÔLUA = 0.^C ; ainsi G est une algèbre sur C = UA , 38 • la flèche ôA LC —> A coégalise les deux flèches LU6A et ôLe , car ô est naturelle, mais ce n'est pas en général un conoyau de ces deux flèches. • montrons que KA est nécessairement égal à (C, G) • d'abord K(LUA) = K(LC) = LjC = (TC, \xc ), de même K((LU)2A) = K(LTC) = L,TC = (T2C , |ATc ). • ensuite, UIK(ÔLC) = U&LC = \xc , par définition de |ic , d'où K(ÔLC) = \ic , où |ic (T2C, |iTc) -> (TC, |ac ) est défini par n c , • demême K(LUÔ0 = L,(6) (T2C, |.iTr) -> (TC, \\r ) , soit G (TC, |i c ) —> (C, G) l'homomorphisme de T-algèbres qui présente (C, G) comme quotient de (TC, |.ir ), comme K(ôA) et G ont même source (TC,|ic) et même projection G par Ui et que Ui est bien fidèle , on voit que K(ôA ) = G , et en particulier, KA , but de K(ôA ) est bien égal au but de G, c'est-à dire à (C, G) • Soit alors h A -> B un homomorphisme entre U-structures (i e une flèche de A) , K(h) est un homomorphisme de T-algèbres, de source K(A) = (C, 6 ) , où C = UA et G = UôA. de but K(B) = ( C , G') ,où C = UB et 9 , = UôB , de flèche sous-jacente U,K(h) = Uh , cet homomorphisme (c'en est bien un car ô est naturelle) est complètement déterminé 2.7. Monadicité et critère de Beck. On dit que U A -> C est monadique (on peut préciser « à isomorphisme près ») s'il possède un adjoint à gauche L et si le foncteur de comparaison K : A -> Alg(T) qui s'en déduit, comme indiqué ci-dessus, est un isomorphisme. Dans ce cas, U hérite de la plupart des propriétés de Ui (toutes celles qui sont transportables par isomomorphisme). Par exemple, U est bien fidèle et U crée les conoyaux de paires contractiles. La réciproque constitue ce qu'on appelle le critère de J Beck si U. A -> C a un adjoint à gauche, si U est bien fidèle et si U crée les conoyaux de paires contractiles, alors U est monadique. 39 En effet, soit (U, L, E) un choix d'adjonction (il en existe par hypothèse) pour le foncteur U, soit T = (T, E, |.I) la monade associée , et soit K A -> Alg(T) le foncteur de comparaison qui s'en déduit Construisons alors l'inverse H de K Soit (C, G) une T-algèbre sur C Le couple (LG, ôix ) se projette dans C, par le foncteur U, sur le couple (T9, (ic ), on a vu que, dans C, la flèche G est conoyau (contractile) du couple (TG, |icX les retours do et di étant respectivement dans ce cas Ec et Sic , comme U crée les conoyaux de paires contractiles, on peut conclure que (LG, ôLc ) a un conoyau A. au dessus de G , ce conoyau est déterminé uniquement puisque U est bien fidèle , soit A le but de X , on pose H(C,G) = A Soit maintenant f (C, G) -> (C\6') un homomorphisme de T-algèbres On dispose du couple (LG', ôLe ) et de son conoyau À' dans A au dessus de G' La flèche X* L(f) coégalise le couple (LG, ôLe ) X" Lf LG = A/ L(f G) = X' L(G' Tf) , car f (C, G) -> (C',G') un homomorphisme, = VLV LULf = À'ÔLC LU(Lf) , car X" coégalise (LG',ôLe ), = V Lfôie , car ô LU -» Id\ est naturelle, et comme X est conoyau de (LG, Si e ) . il existe une unique flèche f : A -> A' dans A telle que f X = À' Tf , on pose alors H(f) = f Il reste à vérifier que H est un foncteur et que c'est bien Tinverse de K C'est facile, mais instructif • H est un foncteur Soient f (C, G) -> (C\ G') et g ( C , G') -> (C", G") deux homomorphismes d'algèbres composables, soit h = gf (C, G) -> (C", G") leur composé , Soient A*, X\ A," les conoyaux associés respectivement aux algèbres (C, 6) , ( C , G'), (C",G") par la construction précédente de H, alors H(h) = h est l'unique flèche telle que h.A, = A.".Th, or avec H(g) H(f) = g f on a g f . * = g (f *) = g A/Tf=A/\Tg.Tf = A/'T(gf) = X"Th • HK = IdA . Soit A un objet de A . Par la propriété universelle de structure libre, ôA est l'unique flèche dans A de LC vers A telle que UôA EC = le , par définition de K, on a déjà les égalités K(A) = (UA, UôA) = (C, G) , par définition de H, X satisfait aussi UA, = 6 ; on a donc les égalités UA, = UôA = G , et il s'en suit que A, = ôA puisque ces flèches ont même source et 40 que U est bien fidèle , remarquons aussi que la famille (A,(ce, ) ( C , G') un homomorphisme d'algèbres, on a K(H(f)) = K(f) = f, car K(H(f)) est une flèche au dessus de f, de source (C,G) et de but (C',6') en effet, au niveau des objets, on a bien K(A) = (C, G) et K(A') = (C',G'), d'après la remarque précédente (X = SA et X" = 5A ) • K H = Id Alger» Soit (C, G) une T-algèbre sur C, on sait que G est conoyau contractile du couple suivant (TG, |ic ) = U>U (LG, 5Lr ) , par construction de H, l'objet A = H(C, G) est le but du conoyau X de (LG, 5Lc ) qui se projette sur G et on a déjà remarqué que, dans ce cas, on a X = SA , alors, par construction de K, on a bien K(A) = (C, G), soit KH (C, G) = (C, G) Enfin, si f (C, G) —> (C1, G1) est un homomorphisme d'algèbres au dessus de f (= Ui (f)), on trouve que KH(f) ^ f, car ce sont des flèches de même source et même but au dessus de f, et Ui est fidèle ' Le caractère formaliste de cette preuve masque un peu son extrême simplicité. • d'abord on n'a pas eu besoin de la création de tous les conoyaux de paires contractiles mais seulement de ceux des paires (LG, 5Lc ) , • ensuite, l'essentiel de la preuve consiste à remarquer que ces conoyaux définissent les Ustructures comme quotients nature/s des structures libres qu'elles engendrent (la famille (X{cs) ) «ce» e OJX Aigd)) définit une transformation naturelle) Le critère de Coppey est beaucoup moins formel, on peut l'énoncer ainsi • si le foncteur U : A -> C est définissable, à isomorphisme au dessus de C près, comme un oubli de D-algèbres pour une C-syntaxe D, et s'il possède un adjoint à gauche, il est monadique • la réciproque est triviale, lorsqu'on dispose de la catégorie de Kleisli associée à une monade elle n'est rien d'autre en effet qu'une C-syntaxe complète standard pour les foncteurs Alg(T) —> C , où T est une monade sur C 41 On dispose avec les D-algèbres d'une notion de foncteur algébrique indépendante du fait que ce foncteur ait un adjoint à gauche ou non Ces questions sont développées au paragraphe 4, après l'étude de quelques exemples. En particulier, on y établira la validité du critère de Coppey en passant par le critère de Beck, ce qui est très instructif encore 42 3. Exemples de monades dans Ens. Voici avec quelques commentaires appropriés les premiers exemples, plus ou moins classiques, de monades dans Ens 3.1. Les monoïdes. 3.1.a. L'endofoncteur M . A tout ensemble X on fait correspondre l'ensemble M(X) des mots de l'alphabet X, le mot vide compris, on note [xi, x2, , xn] le mot formé des lettres xi, x2, , xn, et 0 le mot vide Cette correspondance (X —> M(X)) se prolonge en un foncteur si l'on définit, pour toute application f X -» Y, l'application M(f) M(X) -> M(Y) par M(f)(2) = 0 , e t M(f)[X].\:, 3.1.b. , Xn] == [fXi, fx 2 , , fxn] La transformation naturelle £. Pour chaque ensemble X, l'application 8\ X —> M(X) , qui à une lettre x fait correspondre le mot à une lettre [x] (auquel on l'identifie parfois) est bien définie et naturelle, de sorte qu'on dispose d'une transformation naturelle 8 IdEns -> M en effet, si f X - > Y est une application, on a to f)(x) = MflM) = [fit] = M(f)([x]) = (M(f) ex)(x) 3.1.C La transformation naturelle H- Pour chaque ensemble X, on définit l'application | i \ , dite d' «effacement des parenthèses », qui a pour source M(M(X)) = M2(X) et pour but M(X), par H\([mi, m2, , mn]) = mi m2 mn, où mi, m2, ., mn sont des mots en les lettres de X, et mi m2 mn leur composé (on dit aussi concaténé) c'est le mot constitué des lettres des mots mj , m 2 , . m n , dans cet ordre. Si 43 l'on schématise chaque mot (élément de M(X)) m, par une parenthèse d'indice 1, et le mot de mots (élément de M2(X) ) par une parenthèse d'indice 2, alors la composition « abstraite », dans M(X) , est schématisée par l'effacement des parenthèses « intérieures» (d'indice 1), et renommage de la parenthèse « extérieure »( l'indice 2 devenant 1 f) [[ J i , [ , ] i , , [ , ] i ] 2 3.1.d. -> [ , , , , .,,.]i Vérification et interprétation des axiomes de monade, pour M. • (Ui) |i\ E\L\ = KL\ exprime qu'étant donné un mot m , on le récupère tel quel, lorsque l'ayant traité comme mot de mots à une seule lettre . [m] , on supprime la parenthèse [ ] • (U2) |i\ Ms.\ = IMX exprime qu'étant donné un mot m = [xi, x2, , xn] (ou 0 ) , on le récupère tel quel, lorsque partant du mot de mots à une lettre m = [[xj], [x2] .., [xn]] , on en constitue le composé, par effacement des parenthèses (intérieures !) • (A) |i\ (i\ix = \X\ M|A\ exprime une propriété de «permutation» que possède l'opération d'effacement des parenthèses si l'on part de m = [mu /??2, mot de (mots de mots mx = [n\\ , , m2 , , = ni] m2 , mp] , qui est un , mni. x ] ) , le mot composé m du composé m mv , est égal au composé du mot de mots m" = [mi , , mp ], obtenu en composant d'abord chacun des mots m, , ce qui fournit les mots-lettres m, = mi., mni , du mot m" à composer , les deux mots m et m\ éléments de M2(X), ont même composé dans M(X) si m = [ [ m i i , m 2 i , ., mn] i ] 2 , [mi.2, m2 2 ,mri22]2, alors m = \i\j\(nt) = [m n , m2J , , m„i.i, mi 2 , m22 , ., m^ 2 , /w'= M|i\ 2 , cette dernière égalité a bien un sens puisque la loi - est partout définie et associative . Remarques. La loi dite d'unitarité, pour l'algèbre (X, 0) oblige au choix 0([x]) = x, aucun lien a priori avec l'unitarité de e dans (X, *). La loi dite d'associativité correspond très exactement à la permutation possible des effacements de parenthèses, qui elle-même résulte bien de l'associativité de la loi * du monoide (X, •); plus précisément, c'est une conséquence du théorème affirmant que, pour des lois binaires partout définies, l'associativité portant sur 3 variables entraîne l'associativité portant sur un nombre quelconque de variables (résultat complètement faux pour les lois partielles), on vérifie sans peine que cette loi oblige alors à la définition proposée ci-dessus de 0 , dans le troisième cas ' 46 Le choix de 0(0) = e est imposé encore par la loi dite d'associativité de la Malgèbre , en effet, posons 0(£) = u , et, pour tout x G X, posons m = [[x], 0 ] (resp [0,[x]]), on doit avoir, pour x eX, les égalités suivantes 0 MQ(m) = 0(x,u) = x*u = 0 \.i\(m) = 0([x])= x (resp et 0 MQ(m) = 0(u,x) = u*x = 0 \i\(m) = 9([x])= x ), donc u est bien élément neutre dans (X, * ) , un tel élément est unique, donc u = e ! 3.2. Les semi-groupes. 3.2.a. L'endofoncteur S . A tout ensemble X on fait correspondre l'ensemble S(X) des mots de l'alphabet X, le mot vide non compris Cette correspondance (X -> S(X)) se prolonge de manière naturelle en un foncteur encore noté S. S est bien défini, y compris en X = 0 , où l'on a S(0) = 0 ' 3.2.b. Les transformations naturelles & et H On les définit de manière tout à fait analogue au cas des monoides. Rappelons simplement les formules • Z\ (x) = [x] , pour x G X et X * 0 , quant à c 0 . 0 —» 0 c'est simplement Id 0 , • |ix([mi , m 2 , ... , mn]) = mi m2 . mn, pour X * 0 , tandis que |i 0 = Id 0 encore 3.2.C. S = (S, 8, \x) est une monade. La vérification est en tout point semblable à celle qui vient d'être faite pour M. Les mêmes remarques sont à faire sur les effacements de parenthèses . . Bien noter que la monade S est triviale en X = 0 . quel que soit p > 0 , S p (0) = 0 , et e 0 = \x M , en effet, distinguons d'abord les transformations naturelles 8 et (i des deux monades par un indice supérieur convenable , soit m = [xi, x2, que m = |a'\ (m) où m = [[x\ ], [x2], , xn] e S(X) , il est clair , [xn]] , mais comme on doit avoir i |AS = |AM i2 et que, pour tout x e X , o n a i([x]) = x et donc \2{m) = m , il vient ix(m) = ix |i s x (m) = [iXl(m) = m Il n'y a pas de morphisme dans l'autre sens il suffit de regarder en X = 0 ce qui se passe ' 3.3. Les magmas. Un mot non associatif d'un alphabet X est un couple (m, d) constitué d'un mot m G S(X) (voir ci-dessus) et d'une disposition cohérente de parenthèses d à n places, n étant le nombre de lettres du mot m ; ainsi, par exemple, ( xyzt , < , < . , . » , . ) mot non associatif, qu'on écrit plus usuellement sous la forme < x Y donnée, par S'(f)(m , ô) = (S(f)(m) , ô) Ce foncteur est sous- jacent à une monade S' = (S', z\ |i') La transformation naturelle e' est définie en X par e\\(x) = ( x, ) La transformation naturelle |i' est défini en X de la manière suivante soit ( m \ 8 ) un élément de S'2(X) , ainsi m ' est un mot de mots non associatifs , soit par exemple m' = (mi , di) (m2 , d2) (mp , dp) et ô est une disposition cohérente de parenthèses à p places , alors |i' x ( /77 ' , ô ) = (m , d) où le mot m = mi m2 mp est le concaténé du mot de mots [mi , m : , , dp) est , mp ] et ou la disposition d = ô(di , d2 , obtenue en encapsulant les dispositions de parenthèses nécessaires parmi les d, afin de les insérer dans ô comme s'il s'agissait d'éléments Prenons cet exemple ô = < , >, et si di = , < , > , d2 = , et d. = « , > , > , , alors d s'obtient en plaçant d'abord (di),(d 2 ) et (dO aux places réservées dans ô, puis en transformant les parenthèses ordinaires ( ) en parenthèses < > , là où c'est nécessaire, on obtient d'abord < ( , < . , > ) , ( , ) > , ( « . , > , > , ) , puis la disposition cohérente . d = « < » < » <« > > > Supposons que les trois mots m, soient les suivants ni] = xyz , m2 = ab , rrh = qrst , alors on trouve |i' x (< ( xyz , , < , >) ( ab , , ) > ( qrst, « . , ( xyzabqrst, « >,.>,.)) ,< , » ,< , » ,< « ., >, >, >) Si l'on emploie la notation simplifiée, il convient d'indexer les deux niveaux de parenthésages correspondant à M'(X) et M'2(X) respectivement, on écrira donc ( m ', ô ) = <2 i >i i >2 i s >i t >i 49 puis (m ,d) = ] >] i >i } s >] t >i L'opération n \ apparaît alors de ce point de vue comme une simple identification de niveaux de parenthèses II est clair que cette opération est « associative » dans le sens réservé à ce mot pour les monades Il est clair enfin que les S'-algèbres s'identifient aux magmas, une structure de magma sur X étant simplement la donnée d'une loi binaire partout définie sur X ! Il est manifeste qu'un magma peut être ou non associatif II est alors flagrant que la loi dite d'associativité pour les algèbres d'une monade n'a pas grand chose à voir avec l'associativité (éventuelle) d'un magma 3.4. Opérations à gauche d'un monoïde sur les ensembles. Soit M* un monoïde, d'élément neutre e 3.4.a. L'endofoncteur Mx-. A tout ensemble X il fait correspondre l'ensemble produit cartésien MxX A toute application f X - » Y il fait correspondre l'application Mxf par (Mxf)(m, x) = (m, f(x)) 3.4.b. La transformation naturelle &M*. Elle est définie en X par • 8 M \(x) = (e,x),si X * 0 , • et si non eM*0 = Id 0 50 M*X—>MxY définie La transformation naturelle |aM*. 3.4.C. Elle est définie en X par • [i\r x ((m',(m, x))) =(m'-m,x) 3.4.d. La monade M*x- = (Mx-, eM*, (aN1* ). Vérifions les axiomes de monades (Uj), (U2) et (A) • |.i M \ . £ M \i>\ ( m , x ) = MM \ ( e , (m , x)) = ( e-m , x) = (m , x), • nNI*x M*c M *(m,x) = |.iN1\ ( m , (e , x)) = ( m - e , x ) = (m , x) Ici , il faut être de bonne foi, les axiomes d'unitarité (à gauche et à droite) de la monade correspondent exactement aux axiomes d'unitarité (à gauche et à droite) dans le monoïde donné M* ' • |i M \- (M*|AM\) (m", (m' , (m, x)) = | i M \ ( m", (m'* m , x) = (m"*(m'-m), x) MM\ • A u x (m", (m' , (m, x)) = j i M \ ( m"-m',(m,x)) = ( ( m " * m > m , x), qui sont bien égaux puisque M est associatif La bonne foi oblige encore à noter que l'axiome d'associativité de la monade correspond exactement dans ce cas à l'axiome d'associativité du monoïde donné M* ! 3.4.e. Algèbres de la monade M*x-. Une M-x-algèbre sur l'ensemble X s'identifie naturellement à une action à gauche de M* sur X Rappelons qu'une action à gauche cp de M* sur X consiste en la donnée d'une application cp MxX —> X satisfaisant les deux conditions suivantes, où on écrit m* 9 xpour cp(m,x) • V XGX . e»q>x = x , • V m, m' E M , V xeX (m'* m)*vx = m'*(p(m- XxM et f H fxM ( (fxM)(x,m) = (f(x),m) ) , • la transformation naturelle e est définie en X par s x (x) = (x,e) • la transformation naturelle |iM est définie en X par |iM* ((x,m),m') = (x, m*m') On vérifie sans peine qu'il s'agit bien d'une monade et qu'une -xM*-algèbre sur X s'identifie naturellement à une action à droite de M sur X, c'est-à-dire la donnée d'une application ç> de XxM vers X satisfaisant les deux conditions suivantes, où on écrit x * 9m pour (p(x,m) : • V xeX : x*q,e = x , • V m, m' G M , V xeX : x*

X2 et f h-> f , définie par (x,y) h^ (f(x),f(y)), • la transformation naturelle ô est définie en X par ô x (x) = (x,x), • la transformation naturelle |a est définie en X par |iX((x,y),(z,t)) = (x,t) . On laisse au lecteur le soin de vérifier (à la main !) qu'il s'agit bien d'une monade dans la catégorie des ensembles, qu'il existe plusieurs autres monades du même genre ayant le même endofoncteur sous-jacent. 52 Soit X un ensemble On appelle décomposition de X en produit de deux facteurs la donnée d'un couple (ri,r 2 ) de relations d'équivalence sur X tel que, si qi et q2 désignent les surjections canoniques respectives de X sur X!x\ et XT 2 , alors (X, qi , q2 ) est un produit naturalisé de X/n et X/r2 Une autre définition est la suivante appelons prédécomposition de X en produit de deux facteurs la donnée d'un triplet (Xj, X 2 , y) tel que y est une bijection de X sur le produit cartésien Xi x X2 . Considérons deux prédécompositions (Xi , X2 , y) et (Yj ,Y2 , y') de X comme équivalentes s'il existe un couple d'applications (fi , f2) (Xi , X2 ) —> (Yi ,Y2) tel que fi x f2 soit une bijection « échangeant » y et y' , i e telle que (fi x f2) 0 y = y' . Cette relation est à l'évidence réflexive et transitive, elle n'est pas symétrique (uniquement à cause du cas de l'ensemble 0 ) mais sa symétrisée est bien une équivalence Une classe d'équivalence de prédécompositions s'identifie alors naturellement à une décomposition de X en produit de deux facteurs On notera bien ceci si X * 0 et si (fi , f2) . (Xi , X2 ) -> (Yi ,Y2) rend équivalentes les deux prédécompositions (Xj, X 2 , y) et (Yj ,Y 2 , y') de X, alors fi et f2 sont nécessairement des bijections Autrement dit, la relation définie ci-dessus est bien une équivalence lorsqu'on exclut l'ensemble vide Une (-):- algèbre s'identifie naturellement à une décomposition de X en produit de deux facteurs Voici plus de détails • Soit (X, 0) une (-)2- algèbre , posons xy = 0(x,y) , cette loi ( (x,y) t-> xy ) est idempotente et associative • idempotente, i e x2 = x , c'est la traduction de 0 6X = Idx , • associative, soit q = ((x,x),(y,z)), on a 0 [i\ (q) = xz , et 0 02 (q) = x2(yz) = x(yz), de même, en partant de q' = ((x,y),(z,z)) on trouve xz = (xy)z ? donc, non seulement la loi est associative, mais on a : V x,y,z : xyz = xz . A (X,0) on peut faire correspondre alors le couple d'équivalences (ri , r2) dont les classes sont respectivement, x mod ri = xX et x mod r2 = Xx Supposons xX n x'X * 0 et soit y e x X n x'X; il existe u et v tels que y = xu = x ' v ; soit z = x t E x X , z : = x t = xut = x'vt G x'X , donc xX c x'X , on a de même x'X c xX, d'où xX = x'X , ceci prouve que ri est bien une équivalence , de même pour r2 53 De plus, l'application canonique y : X -> X/ri x X/r2 qui à x G X fait correspondre (xX, Xx) est bijective : • injective: si on a xX = yX et Xx = Xy , il existe u et v tels que y2 = xu = vx ; alors on a: x = xuvx = y2 = y ; • surjective. soit (Ci , C2 ) G XJÎ\ X X/r2 , Ci n C 2 n'est pas vide car si X] GCI et x2 GC 2 , alors xix2 G Ci n C 2 ; ainsi y(xix2) = (Ci, C2). • Soit (ri , r2) une décomposition de X , on définit l'algèbre correspondante 0 X2 —> X de la manière suivante: soit (x,y) G X2 ; au couple ( C i = x mod ri , C2 = y mod r2 ) correspond un élément bien précis de X, puisque l'application canonique y: X —>X/ri x X/r2 est une bijection , on peut préciser que cet élément z n'est autre que l'unique élément de l'intersection d n C 2 ; on pose z = 0(x,y). Vérifions que (X,0) est une (-)2- algèbre sur X: • « unitarité » ; soit x G X , x mod ri n x mod r2 n'a qu'un élément, ce ne peut être que x, d'où 0S X (x,x) = 0(x,x) = x , • « associativité » ; on doit montrer que V (x,y), (z,t) G X2, 9(0(x,y),0(z,t)) = 0(x,t), posons: Ci = x mod T\, C2 = y mod r 2 , C'i = z mod ri , C'2 = t mod r2, par définition, on a 0(x,y) - x mod ri et 0(x,y) - y mod r2 , 0(z,t) - z mod r2 et G(z,t) - t mod r2 , on obtient alors ceci 0(0(x,y),0(z,t)) ~ 0(x,y) - x mod ri , donc 0(0(x,y),0(z,t)) - x mod ri ; de même, 0(0(x,y),0(z,t)) - 0(z,t) - t mod r 2 , donc 0(0(x,y),0(z,t)) - t mod r2 , comme le seul élément possible ~ x mod ri et ~~ t mod r2 est par définition 0(x,t), on obtient bien l'égalité voulue 3.7. Décompositions d'un ensemble en produit de trois facteurs. Contrairement à ce qu'on pourrait croire, le cas de trois facteurs ne se déduit pas, de manière simple, du cas de deux facteurs. Bien sûr les décompositions en trois admettent une description en termes de décompositions en deux, comme on est en droit de s'y attendre, mais le processus récurrent par lequel on accède aux décompositions en n facteurs démarre en fait à n = 3 comme nous allons le voir Définissons la monade (-)3 = ( (-)3 , ô , \i ) suivante 54 • l'endofoncteur (-)' est défini par X »-> X' et f H» f, définie par (x,y,z) f-> (f(x),f(y),f(z)). • la transformation naturelle ô est définie en X par ô\ (x) = (x,x,x), • la transformation naturelle |LI est définie en X par Hx( (x,y,z), (x',y',z'), (x'\y",z") ) = (x, y', z") On laisse au lecteur le soin de vérifier (à la main ') qu*il s'agit bien d'une monade dans la catégorie des ensembles, qu'il existe plusieurs autres monades du même genre ayant le même endofoncteur sous-jacent Soit X un ensemble On appelle décomposition de X en produit de trois facteurs la donnée d'un triplet (ri , r 2 , u) de relations d'équivalence sur X tel que, si q} , q2 et q^, désignent les surjections canoniques respectives de X sur XAj , X;r2 et X/u alors (X, qi, q2, qO est un produit naturalisé de X/n , X/r2 et X/u Une autre définition est la suivante appelons prédécomposition de X en produit de trois facteurs la donnée d'un quadruplet (Xi, X 2 , X* , y) tel que y est une bijection de X sur le produit cartésien Xi x X2 x X^ Etant données deux prédécompositions (Xi, X2 , X-, , y) et (Yi ,Y2 , Y; , y') de X , on les considère comme équivalentes s'il existe un triplet d'applications (fi , f2 , f,) (Xi , X2 , X. ) -> (Y, ,Y 2 , Y* ) tel que fi xf2xf, soit une bijection « échangeant » y et y' , i e telle que (fj x f2 xf,) 0 y = y' Cette relation est à révidence réflexive et transitive, elle n'est pas symétrique (uniquement à cause du cas de l'ensemble 0 ) mais sa symétrisée est bien une équivalence Une classe d'équivalence de prédécompositions s'identifie alors naturellement à une décomposition de X en produit de trois facteurs On notera bien ceci si X * 0 et si (fi, f2, U ) (Xi , X 2 , X3) -> (Yi ,Y 2 ,Yi) rend équivalentes les deux prédécompositions (Xi, X 2 , X^, y) et (Y! ,Y2 ,Y 3 , y') de X, alors fi, f2 et U sont nécessairement des bijections Autrement dit, la relation définie ci-dessus est bien une équivalence lorsqu'on exclut l'ensemble vide Une (-)J- algèbre s'identifie naturellement à une décomposition de X en produit de trois facteurs Voici plus de détails • Soit (X, 0) une (-)3- algèbre , posons xyz = 0(x,y,z) , cette loi ( (x,y,z) h-> xyz ) est « idempotente » et « associative », dans le sens suivant 55 • « idempotente », i e xs = x , c'est la traduction de 0 ô\ = Id\ • « associative », et c'est ici qu'il y a une différence avec le cas n = 2 , et que s'amorce la récurrence dont il a été question plus haut, cette loi ternaire n'est pas associative dans le sens classique (qui stipulerait (xyz)tu = x(yzt)u = xy(ztu)), par contre, elle est représentable par deux lois binaires, de la manière suivante Posons x*i y = xyy et x *2 y = xxy , alors, quels que soient x,y,z on a (x *i y)*2 z = x *i (y *2 z) = xyz , les lois *i et *2 étant elles mêmes associatives , en effet d'abord , pour la loi *i (x ., y ) •! z = (xyy)zz = 0 o 0 3 ( (x,y,y),(z ? z,z),(z,z î z) ) , or 0 o n ( (x,y,y),(z,z,z),(z,z,z) ) = 0 (x,z,z) = xzz = x .] z , x*j (y-i z) = x(yzz)(yzz) = 0 o 0'((x,x,x),(y,z,z),(y\z,z)) , et 0 o |i ((x,x,x),(y,z,z),(y,z,z)) = 0 (x,z,z) = xzz = x M z , donc (x *i y ) *i z = x *i (y *] z) = x *} z , puis, pour la loi *2 (x *2 y ) -2 z = (xxy)(xxy)z = 0 0 0 ^ ( (x,x,y),(x,x,y),(z,z,z) ) , or 0 o |i ( (x,x,y),(x,x,y),(z,z,z) ) = 0 (x,x,z) = xxz = x *2 z , x *2 (y *2 z) = xx(yyz) = 0 QQ* ((x,x,x),(x,x,x),(y,y,z)) , et 0 o |A ((x,x,x),(x,x,x),(y,y,z)) = 0 (x,x,z) = xxz = x *2 z ; donc (x *2 y ) *2 z = x *2 (y -2 z) = x *2 z , enfin,on a (x-iy). 2 z = (xyy)(xyy)z = 0 O 0 ' ( (x,y,y),(x,y,y),(z,z,z) ) = 0 (x,y,z) = xyz , et x ,, (y *2 z) = x(yyz)(yyz) = 0 o 0 ' ( (x,x,x),(y,y,z),(y,y,z) ) = 0(x,y,z) = xyz ; donc (x *i y ) *2 z = x *i (y *2 z) = xyz . La loi d'associativité qui résume les trois cas consiste à dire qu'on peut écrire sans parenthèses tout composé possible de gauche à droite du moment qu'on effectue les composés selon *i toujours avant les composés selon *2 '• la dernière lettre à droite des composés selon *i est aussi la première lettre à gauche des composés selon *2, d'où les trois lettres résultantes , exemple : 56 x *i y », z .] t *i u *2 a *2 b *2 c = xuc . A (X,0) on peut faire correspondre alors le triplet d'équivalences (ri , r2 , u) dont les classes sont respectivement x mod ri = xXX et x mod r2 = XxX et x mod r3 = XXx . Supposons xXX r^ x'XX * 0 , soit t G XXX n x'XX, il existe v et w tels que t = xvw, il existe aussi v' et w' tels que t = x'v'w' , soit z = xpq G XXX , z = xpq = (xvw)pq = tpq = (x'v'w')pq = x'pq G X'XX , donc xXX e x'XX , on a de même x'XX c xXX, d'où l'égalité xXX = x'XX , ceci prouve que n est bien une équivalence, de même pour r2 et n De plus, l'application canonique y X -> X/n x X/r2 x X^u qui à x G X fait correspondre (xXX, XxX, XXx ) est bijective • • injective si on a xXX = yXX , XxX = XyX et XXx = XXy , il existe v et w , u' et w', u " et v" tels que y = xvw = u'xw' = u"v"x , alors on trouve x = x' = (xvw)(u'xw , )(u ,, v"x) = y = y ; • surjective soit ( d , C 2 , CO G X/T} X X/r2 < X/u , Ci n C 2 n C^ n'est pas vide, en effet, si xi eCi , x2 GC2 et x; G C; alors xix2x* G Ci n C2 n C^ ; donc y(x,x2xO = (C],C2,CO Soit (ri , r 2 , u) une décomposition de X On définit l'algèbre correspondante 0 Xs —> X de la manière suivante soit (x,y,z) G X\ au triplet (Ci, C 2 , CO dans lequel Ci = x mod ru C2 = y mod r2 et C-, = z mod u , correspond un élément bien précis de X , puisque l'application canonique y X -> X/n x X/r2 x X/u est une bijection , on peut préciser que cet élément t n'est autre que Tunique élément de l'intersection Ci n C2 n C* , dans ce cas, on pose t = 0(x,y,z) Vérifions que (X,0) est une (-)**- algèbre sur X • « unitarité » ; soit x G X , x mod ri D X mod r2 r^ x mod r$ n'a qu'un élément, ce ne peut être que x, d'où 0 ô x (x,x,x) = 0(x,x,x) = x , • « associativité » , on doit montrer que V(x,y,z),(x\y\z'),(x",y",z")eX\ e(e(x,y,z),e(x',y',2'),e(x",y",2")) = 9(x,y\z"); posons donc: Ci = x mod ri, C2 = y mod Ï2, C? = z mod r3 , d = x'modr t , C'2 = y'modr2, C\= z'modn , C", = x"modr,, C"2 = y"modr 2 , C"3 = z"modr, , par définition, on a alors 57 0(x,y,z) - x mod ri , 0(x,y,z) - y mod r2 et 0(x,y,z) - z mod r* , 0 ( x \ y \ z V x' mod ri ,0(x',y',z') - y'mod r2 et 0 ( x \ y ' , z ' ) - * mod r, , 0(x'\y",z") - x" mod r,, 0(x",y",z") - y" mod r2 et 0 ( x " y \ z O - z" mod r,; on obtient alors ceci 0(0(x,y,z),0(x',y',z'),0(x",y",z"))-0(x,y,z)- x mod r,, 0(0(x,y,z),0(x',y',z'),0(x",y",z"))-0(x',y',z')- y' modr 2 , 0(0(x,y,z),0(x',y',z'),0(x",y",z"))-0(x",y",z")- z" mod*, comme le seul élément possible - x mod ri , - y' mod r2 et - z" mod n est par définition 0(x,y',z " ) , on obtient bien l'égalité voulue Soit (X, 0) une (-)3- algèbre , un élément t G X « coordonnées » (tXX , XtX , XXt) où, comme on l'a vu admet alors le système de {t} = tXX r^ XtX n XXt Il y a bien d'autres systèmes de coordonnées possibles pour un point t G X donné, en particulier ceux qui mettent enjeu les lois déduites de 0 , que nous avons notées *i et *2 , il y a aussi d'autres lois binaires associées à 0 Nous ne faisons que mentionner ici ces questions 3.8. Décompositions d'un ensemble en produit de n facteurs. Indiquons seulement les résultats qui généralisent le cas n = 3 sans démonstration On définit la monade (-)n = ( (-)n , ô , n ) par > l'endofoncteur (-)n est défini par X H> X" et f h-> fn, où fn est donnée par. (xi, x 2 , x 3 , , xn ) H> (f(xi), f(x2), flxO, , flta) ) > la transformation naturelle ô est définie en X par Sx (x) = (x,x,x, ., x ) , > la transformation naturelle |i est définie en X par | A X ( ( X l l , X i 2 , X13, . . , X i n ) ( x 2 i , X 2 2 , X 2 3, ., X 2 n ) , ., (Xni, X„2, X„3 , • -, X™,)) = ( X n , X 2 2 , X ^ , 58 , Xnn ) On laisse au lecteur le soin de vérifier (à la main ') qu'il s'agit bien d'une monade dans la catégorie des ensembles, qu'il existe plusieurs autres monades du même genre ayant le même endofoncteur sous-jacent Soit X un ensemble On appelle décomposition de X en produit de n facteurs la donnée d'un n-uplet (ri , r 2 , u , , rn) de relations d'équivalence sur X tel que, si Qi 9 ¢2 , q^, , qn désignent les surjections canoniques respectives de X sur XJv\ , X/r2 , XM , .. , X/r n , alors (X, (q,) j < x < n ) est un produit naturalisé des (X/r, ) i <, < n Une autre définition est la suivante appelons prédécomposition de X en produit de n facteurs la donnée d'un couple ((X,) i <, < n , y) tel que y est une bijection de X sur le produit cartésien J J X. Etant données deux prédécompositions ((X,) i <, < n , y) et ((Y,) i <, < n , y') l ' . I L D de X, on les considère comme équivalentes s'il existe un n-uplet d'applications (f, ) i <, < „ (X,) i <, < n -> (Y,) i <, < n tel que [ \ fx soit une bijection « échangeant » y et y' , i e telle 1 que 1 1 f o y = y' i - n Cette relation est à l'évidence réflexive et transitive, elle n'est pas symétrique (uniquement à cause du cas de l'ensemble 0 ) mais sa symétrisée est bien une équivalence Une classe d'équivalence de prédécompositions s'identifie alors naturellement à une décomposition de X en produit de n facteurs On notera bien ceci si X * 0 et si (f, ) i < , < n (X,) i <, < „ -» (Y,) i <, < n rend équivalentes les deux prédécompositions ((X,) i <, < n , y) et ((Y,) i <, < n , y') de X, alors les f, sont nécessairement des bijections Autrement dit, la relation définie ci-dessus est bien une équivalence lorsqu'on exclut l'ensemble vide Une (-)"- algèbre s'identifie naturellement à une décomposition de X en produit de n facteurs Voici plus de détails • Soit (X, 0) une (-)"- algèbre , posons xjx2x3 . xn = 0(xî? x2, x v , xn) , cette loi est « idempotente » et « associative », dans le sens suivant • idempotente, i.e x n = x , c'est la traduction de 0 ô x = Idx , • associative, pas dans le sens classique, par contre, elle est «représentable » par n-1 lois binaires , de la manière suivante : posons : x*i y = xyy . y (1 x, puis n-1 y ) x*2 y = xxy...y (2 x, puis n-2 y ) 59 x *i y = xx.xyy y (k x, puis n-k y ) x *n i y = xx...xy (n-1 x, puis 1 y ) , alors, les lois (•>, ) ,< i X de la manière suivante, soit (x,) i dans lequel Ci = x, mod r, , 1 < i < n , il lui 1 i i < n correspond un élément x bien précis de X, puisque l'application y.X -^ ] j X/r f 1 i i < n canonique est une bijection ; c'est l'unique élément de Q C t , 1 i i < n dans ce cas, on pose 0 ((x,) i <, < n ) = x On vérifie sans peine que cette application 0 est bien une (-)"- algèbre sur X . 60 On peut dire que (C,)i <, X < applications possibles X , 0 ou O e' et |a' sont définies à partir des uniques >1< q 2 en appliquant successivement les foncteurs I' * et XH ' Le fait qu'il s'agit bien d'une monade dans Ens résulte très exactement de la structure de conoyau contractile ensembliste « minimum » présentée au tout début et mettant en jeu les ensembles 1, 2 et 3 i Ceci ouvre la voie à d'autres généralisations possibles de telles monades dans les catégories cartésiennes fermées II est intéressant de noter aussi la signification des flèches |iT et Tu , après application des transpositions cartésiennes voulues: il s'agit simplement des applications x, 3 k H » XJ k k et x , } k f-> x , , k qui sont coégalisées par composition avec |i en l'application xj j k i-> x, k , on retrouve dans la notation indicielle elle-même la structure d'aiguillage soulignée à propos du conoyau ensembliste minimum (i,j,k) -> (i,k,k) - • (i,k) et 61 (i,j,k) -> (i,i,k) -> (i,k) Si (p I —> J est une application donnée entre ensembles, il en résulte naturellement un morphisme 9* (-)J —> (-)1 entre monades , d'où des comparaisons entre décompositions Cette correspondance est fonctorielle et rend compte des questions d'associativité et de permutation des facteurs dans les structures de décomposition • On peut conduire l'étude dans certaines catégories à produits choisis La caractérisation des catégories pour lesquelles les algèbres des monades « puissances » s'interprètent effectivement comme des structures de décomposition figure au chapitre 1 de ma thèse, lequel développe une partie de mes travaux antérieurs sur les catégories à décompositions algébriques (cf Esquisses mathématiques,^ 14, Paris 7, 1971, ou Note aux C.R.A.S. Paris, Septembre 1971, par exemple) • On peut remplacer I par une catégorie d'indexation dans la catégorie des catégories. Ceci permet de couvrir, par exemple, le cas des décompositions en produits semi-directs. Des développements en ce sens se trouvent dans Esquisses mathématique s,n° 14, 2eme partie, Paris 7, 1971, et sont simplement repris plus en détail au chapitre 2 de ma thèse 3.10. Survol de quelques autres exemples classiques. • T(X) = X+l , avec un s et un (i évidents, c'est encore le conoyau ensembliste minimum qui explique ici la structure monadique Les algèbres sont les ensembles pointés et les homomorphismes les applications qui préservent le pointage • T(X) = X+A, avec un 8 et un (i évidents, une algèbre sur X s'identifie à une application de A dans X . • T(X\ = P(X) ensemble des narties de X z(x) - lx\ et ufXï = I IX ; une aloèhre sur XeX X s'identifie à une structure de treillis complet (existence de sup quelconques) sur X. 62 • T(X) = £f(X), ensemble des ultrafiltres de X , e(x) est l'ultrafiltre trivial des surensembles de x, |i(U) est l'ultrafiltre vers lequel U converge dans l'espace compact totalement discontinu £f(X), dit compactifié de C ech de l'espace discret X on identifie X à une partie de £f(X), i e z X —» £f(X) à une simple inclusion, dans ce cas l'ultrafiltre U a une trace u sur X, qui converge dans £f(X) vers u ! En effet, étant donnée une partie A de X, il revient au même de dire « A G U » ou « u G A » (dans ce cas u est pensé comme point de 2f(X)). Une algèbre sur X s'identifie à une structure de compact sur X , on peut noter que la propriété (A) des algèbres ( G.|i\ = 0.T0 ) exprime, en le généralisant, le bien-fondé du procédé diagonal de Cantor dans le calcul des limites de limites Les homomorphismes sont les applications continues entre compacts 3.11. Plus qu'un simple exemple. Soit X une signature unisorte (on admet les arités infinies, sans autre problème que celui des « tailles » qu'il conviendrait de préciser taille de chaque arité et taille del). A tout ensemble X on peut faire correspondre l'ensemble des termes de la signature construits à partir des éléments de X pris comme symboles de variables. Soit T(X) = Termv(X) cet ensemble; X H» T(X) se prolonge naturellement en un endofoncteur T de Ens, on définit alors e . X —> T(X) et p, T2(X) -» T(X) de la manière suivante e(x) = x et |i(t) = t où t désigne un terme en les variables t, G Termv(X) et t désigne le terme obtenu en substituant à chaque t, figurant comme symbole de variable dans t son expression explicite comme terme en les « variables » de X Par exemple, soient f et g d'arités 2, et y d'arité 1, soient ti = fxgyyz et t2 = gyxyu, si t = gti ft2x (X est considéré ici comme sous-ensemble de TX), alors le terme t , obtenu par substitution, n'est autre que t = gfxgyyzfgyxyux On vérifie sans peine que ces données constituent une monade TV dans Ens Une TV-algèbre sur X s'identifie naturellement à ce qu'on appelle plus couramment une Z-algèbre, ou « réalisation de I en X » c'est la donnée d'une famille d'opérations (kf)f e v sur X, indexée par I , l'opération kf : Xa(t) —> X ayant pour arité l'arité de f 63 Un homomorphisme h (X, (kf)f € i) -> (X', (k'f)f € v) étant défini par une application h X -> X' compatible avec les opérations, i e V f G I , h 0 kf = k'f 0 ha(t) On peut préciser ici diverses choses d'abord T est limite inductive canonique dans Enshns des foncteurs (-)1 , où I, ensemble, est compté autant de fois qu'il y a d'éléments ueT(I), la coprojection o\. u (-/ -> T étant définie en X par ai. u . x ( (-)1 où s I -> J est une application telle que T(s)(u) = v , et se réalisant bien sûr en la flèche (-)s dans Ens h n s , on a bien dans ce cas ai u (-)s = Gi^ On écrit T = Lim (-)1 et on retient que cette limite se calcule « point par point » Bien sûr, si l'on n'impose aucune limitation aux ensembles I (i e si on les prend tous1) on est en train d'écrire qu'un endofoncteur T que/conque de Ens est toujours limite inductive canonique d'indexation « énorme » des (-)\ ce qui est assez trivial (Yoneda maximum!) Si l'on dispose d'une I-algèbre au sens classique (X, (kf)f € :), alors pour tout terme ueT(I) on définit, en X, l'opération dérivée 0 i u X1 -> X en reprenant la construction récurrente des termes supposons que u = f Ui u2 un . est un terme et que les opérations 0 i. ui , 0 i. u 2 , 0 1 un , ont déjà été définies, alors on a 0 i u(cp)= kf(Gi.ui (cp). G 1 u 2 ( < p ) , . © i un(cp), ), la récurrence s'amorçant ainsi V i G I, 0 i., (cp) = (p(i) Revenant à notre histoire de limite inductive, on voit bien que dans le cas d'une signature S, on peut limiter l'indexation aux seuls ensembles I qui sont des représentants des arités des opérations dérivées de la signature (les éléments de T(l) en sont des écritures') La signature I représente donc une économie de définition de la monade TV Indépendamment de ces questions de taille d'indexation de limite, indiquons encore comment on récupère la TV-algèbre (X, 0) associée à (X, (kf)f e s) : il suffit de prendre la limite des 0 1. u (en X) , car la famille (0 1. u ) a. 1» (en X) est compatible et la limite T = Lim (-)1 se calcule, comme déjàdit, « point par point » , il existe donc une seule application I.u 0 : TX -> X telle que 0 0 o 1. u = 0 1. u Sans entrer plus avant dans le sujet, j'ajoute qu'il s'agit de « plus qu'un simple exemple » car le cas des théories équationnelles se traite de manière tout à fait analogue 64 (il convient d'ajouter les contraintes syntaxiques équationnelles dans les prises de limites cidessus'), et on obtient alors toutes les monades dans Ens ells sont donc des quotients de monades du genre TV On est en droit de se demander alors ce qu'apporte la théorie des monades par rapport à la théorie des « théories équationnelles » . Rien si on reste dans Ens, et même moins que rien, si l'on tient à l'économie, ajoutons pour être juste un peu plus que rien si on tient à l'élégance et à l'uniformité1 L'intérêt véritable des monades est de pouvoir quitter la catégorie des ensembles pour faire de l'algèbre abstraite. Mais alors, on est en droit de se demander encore pourquoi on ne pourrait pas « translater » à une catégorie C quelconque le point de vue (générateur) des signatures et des théories équationnelles La réponse est « bien évidemment, c'est possible, et c'est facile , il suffit d'ajouter l'idée de co-arité pour les lois structurantes et de considérer que ces arités ou co-arités ne vont plus être des ensembles, mais des objets de la catégorie C dans laquelle on travaille à l'algèbre »' J'ai donné cette réponse dès 1970-71 avec les D-algèbres et leurs syntaxes et j'ai du la répéter au moins une fois tous les 3 ans depuis' Je vais d'ailleurs me livrer à cet exercice triennal {triade n) au paragraphe suivant et établir alors que les syntaxes de D-algèbres sur C sont les « systèmes-de-générateurs-etrelations » des monades dans C Encore une remarque pour finir ce paragraphe Le point de vue des esquisses (mis au point en 1966 par C Ehresmann) consiste d'emblée à tout abstraire de toute catégorie de base C qui pourrait être donnée' Les arités ou co-arités, sources et buts des lois abstraites sont des objets abstraits, des relations naturelles sont à prévoir entre certains de ces objets, indiquant lesquels se déduisent d'autres et comment c'est le rôle des cônes distingués (projectifs et inductifs) et ce point de vue recouvre largement celui des théories dites du 1CT ordre, comme C.Lair et RGuitart l'ont montré dès 1982 (in Limites et co-limites pour représenter les formules) Dans le même ordre d'idées, C.Lair a mis au point un système analogue aux esquisses pour décrire les théories d'ordre supérieur ce sont les trames en 1987 (in Trames et sémantiques catégoriques des systèmes de trames) et puis les patchworks (cf. par exemple les exposés de C.Lair, aux journées Esquisses et types de structures, qui se sont tenues à Paris en Juillet 1992- voir aussi son article Eléments de théorie des patchworks) 65 Repensant alors au point de vue intermédiaire que constituent les D-algèbres et leurs syntaxes, point de vue plus contextuel (la structure (des objets) de C intervient explicitement) on est en droit de se demander encore bien des choses ! 66 4. Catégorie de Kleisli. D-syntaxes de Coppey. Soit T = (T, e, u) une monade dans la catégorie C Le critère de Beck fait clairement apparaître que toute T-algèbre (C. 9) est repérable comme conoyau contractile canonique d'un couple de flèches, à savoir le couple (T0 , u r ) On observera au passage que, la connaissance de 0 étant par nature indissociable de celle de T6, cette caractérisation des algèbres de monade revêt nécessairement un caractère un peu abstrait • La flèche 0 est aussi F homomorphisme canonique qui présente (C. 0) comme quotient de l'algèbre libre (TC, [ic ) engendrée par l'objet C T0 -> (TC,Ur) (T'CUir) n< (C0) (TCm ) En particulier, la flèche (.ic est l'homomorphisme canonique qui présente (TC, |ac ) comme quotient de l'algèbre doublement libre engendrée par C (ou algèbre libre engendrée par TC i) TUr .» (T'CUT'C) (T2C,uTc) Hc Un- (TC,u c ) (T2C,uTc) Uc et on reconnait là l'axiome (A), dit d'associativité , de la monade 67 Ainsi, le processus de reconstruction des T-algèbres à partir des seules algèbres libres est déjà présent dans la description de celles-ci On peut donc considérer que la connaissance des seules algèbres libres de la monade est en soi une description syntaxique (générale) de toutes les algèbres, c'est précisément le rôle joué par la catégorie KI(T), dite de Kleisli, de la monade T, dont nous allons préciser quelques descriptions équivalentes. 4.1. Catégorie de Kleisli Kli(T) (Version 1). • Ses objets sont ceux de C • Un morphisme de C vers C n'est autre qu'un homomorphisme entre les algèbres libres engendrées respectivement par C et C ; on écrira f C -*i C ou f (LC,|ic ) —> (LC,|ic- ) selon qu'on considère f comme morphisme de Kli(T) ou comme homomorphisme d'algèbres • La composition correspond à celle des homomorphismes soient f C -*] C et g C -*i C" deux morphismes consécutifs, leur composé correspondant à Thomomorphisme h = g.f h = g 0i f est la flèche de K1(T) (LC,|ac ) -> (LC",|ic ) • Si l'endofoncteur T de la monade est injectif sur les objets, Kli(T) peut être définie plus rapidement comme étant la sous-catégorie pleine de Alg(T) dont les objets sont les algèbres libres 4.2. Catégorie de Kleisli K12(T) (Version 2). • Ses objets sont ceux de C • Un morphisme de C vers C n'est autre qu'une flèche dans C de C vers T C , avant d'établir l'équivalence des deux points de vue, on écrira f : C -*2 C' ou f C -> T C selon qu'on considère f comme flèche de la catégorie K12(T) ou comme flèche de C . • La composition s'effectue ainsi soient f . C -*2 C et g : C ->2 C" deux flèches consécutives de K12(T), la flèche composée h = g D2 f est celle qui correspond à la flèche h = |i C " T(g).f C ->TC", on remarque que f : C -> T C s'écrit aussi \iç T(f) s c puisque l'on a : \ic T(f).6c = |IC-.STC-. f = f , par naturalité de 8, , d'après l'axiome d'unitarité de monade, 68 de sorte que h = \xc T(g) \.ic T(f) z< • Sous cette forme, il est clair que la composition est associative puisque le composé de 3 flèches consécutives fi C -*: Ci , f: Ci -*2 C2 et U C2 -» 2 C peut s'écrire f; o: f: o: fi = |ic> T(fO |Lic2 T(f 2 ).|i n .T(fi) e n • Pour f C -*2 C' donné, on voit que Se : C -*2 C est neutre à droite car f o2zc = [iç T(f) zc = |i c Zjr f = f, 8c* . C -*2 C' est neutre à gauche car ecosf = 4.3. |ic-.T(ec*) f = f Catégorie de Kleisli K13(T) (Version 3). On définit d'abord une certaine catégorie Tr(C) de trios de C ses objets sont les flèches zc , C G Obj(C), ses flèches sont les triplets (zc , h , zc ) où h TC -> T C est une flèche de C , elles se composent « comme les h » , selon le schéma suivant On définit alors K13(T) comme la sous-catégorie de Tr(C) engendrée par les flèches de l'un des types suivants (pour une justification des qualificatifs donnés à ces types, je renvoie à l'introduction et aux divers exemples de la section précédente) Tf J ->» T C TC 8c T2r type réel 8c OU ^ type formel 8TC TC 69 ^c TC 8c Il résulte facilement des axiomes de monade que toute flèche de KI3(T) peut s'écrire comme composée de deux flèches seulement (une de chacun des types ci-dessus) dans l'ordre suivant Tf TC type réel Ce HD >TD type formel 8TTJ C _> TD TD 8D D et ce, de manière unique, laissant la vérification complète en exercice (très instructif au demeurant), je souligne juste ce point, dont on a effectivement besoin l'endofoncteur T d'une monade a toujours une certaine propriété de fidélité qu'on peut qualifier de « fidélité à la Kleisli , version 2 », et que voici si f et g C —» TD sont telles que T(f) = T(g) alors f = g En effet, on a T(f) £c = T(g) Sr , d'où 8TD f = 8TD g . puisque 8 est naturelle, et en composant à gauche par \.iD , il vient bien f = g 4.4. Equivalence des trois définitions. Il est clair que les trois classes d'objets sont naturellement isomorphes à la classe des objets de C , chaque flèche 8c déterminant sa source C et réciproquement Toute flèche de la forme h = |aD T(f) TC -> TD définit en fait un homomorphisme d'algèbres h (TC, [ic ) -> (D, \iD ) , car \iD T(h) = nD T(|iDT(f)) =HD HTD.T 2 (1)= [iDJ(f).[ic = h.[iC , et réciproquement, tout homomorphisme h : (TC, |ic ) -> (D, HD ) peut s'écrire sous cette forme h = HD-T(f) avec f = h.Sc , en effet, \xD T(h 8C) = \XD T(h) T(ec) = h [ic T(zc) = h ! 70 Ces deux remarques et le fait que la composition dans Kli(T) et dans K13(T) est en fait une composition dans C prouvent que Kli(T) et K13(T) sont deux catégories isomorphes Soit f C -*i C ; f TC -> T C définit donc un homomorphisme de (TC, U-c ) vers (TC, u r ) et f = f.ec- : C -> TC'définit donc une flèche f : C -*2 C , réciproquement, si la flèche f : C -» 2 C' est donnée , alors f = u c T(f) : TC -» T C définit un homomorphisme f : C - » i C , ces correspondances sont inverses l'une de l'autre, toujours d'après les remarques précédentes D'autre part, si f : C -*i C et g : C -»i C" sont composables et si h : C -»i C" est leur composée, on a: go:f = Uc-T(g)f =u c -.T(gSc). f.sc = g.UcT(ec)f.£c = g.f.sc = h.e c = h , c'est-à-dire que Klj(T) et K12(T) sont bien isomorphes On observera que c'est sans doute ici, dans la comparaison de Kli(T) et K12(T), que la symétrie des rôlesjoués par s et u, apparaît le plus clairement Désormais nous pouvons écrire K1(T) au lieu de KI,(T), K12(T) ou K13(T) et parler de « la » catégorie de Kleisli, ce qui ne dispense pas d'avoir à préciser parfois la version de K1(T) avec laquelle on travaille 4.5. Adjonction naturelle associée à K1(T). Soit T une monade dans C et KI(T) sa catégorie de Kleisli associée. Choisissons la version 1 de K1(T) On définit un foncteur L0 : C -> K1(T) en posant • pour tout objet C de C , L0(C) = C, • pour toute flèche f : C -> C de C , L0(f) = T(f) : C-ï^C On dispose aussi du foncteur naturel U0 : Kli(T) -> C qui à une flèche g: C -», C de Kli(T) fait correspondre la flèche déjà notée g TC -> T C . Le composé U0.Lo n'est autre que T et on vérifie sans peine (et surtout exactement avec les mêmes arguments que ceux utilisés précédemment pour établir les isomorphismes entre les 3 versions de K1(T) ) que (U0, U , e) est une adjonction dont la monade associée dans C n'est autre que T. Enfin, soit U : A -> C un foncteur d'oubli et (U, L, s)A une adjonction au dessus de C de monade associée T dans C, alors il existe un unique foncteur K' : K1(T) -> A satisfaisant à la fois U.K'=U 0 et L = K ' U 71 Introduisons la catégorie Fact (T) des factorisations de la monade T • ses objets sont les adjonctions (U, L, z)\ au dessus de C ayant T pour monade associée, • une flèche (U,L,S)A —> (U',L',8')v n'est autre qu'un foncteur O A —> A' satisfaisant U'O = U et L' = OL (la composition des flèches étant évidente) Cette catégorie possède au moins les deux objets (Ui ,Li ,8).^7, et (U0 ,L0 ,8)KKT> , de plus, (Ui Xi,8).\ig(T) est un objet final de FactÇT) (propriété du foncteur de comparaison d'Eilenberg-Moore) et (Uo ,Lo ,8)KKT) est un objet initial de FactÇÏ) K1(T) On montre facilement que Alg(T) Fact(T) est à limites projectives et inductives « quelconques », une fois précisées les inévitables questions de taille1 4.6. Catégorie de Kleisli comme syntaxe complète. Voici une version légèrement modifiée de la catégorie de Kleisli K13(T) d'une monade, c'est une certaine catégorie KT définie par générateurs et relations. Soit donc comme auparavant une monade T dans C (on conserve toutes les notations standard déjà introduites). Soit F le graphe orienté ayant pour objets les objets de C et ayant pour flèches d'une part les flèches de C et d'autre part une famille de flèches nouvelles indexée par les objets de C , soit (//c TC =o C) c e objDeFl(C) fofir - fie o \ic , -/inoT(f) L'interprétation de ces relations est claire . • les premières permettent de récupérer au moins la structure de C dans KT , • le sens des deuxièmes et troisièmes est qu'en chaque objet C, fie représente une T-algèbre potentielle sur C, on convient d' «étendre » T en U ' 0 K T -» C défini par U'o (fie) = Hc , • les quatrièmes égalités indiquent que cette représentation potentielle est naturelle par rapport aux flèches de C Si j'ai dit que U'o « étendait » T C —> C , c'est que j'ai simplement fait allusion au foncteur canonique L"0 qui est obtenu en composant les flèches canoniques de la construction de KT à partir de C C -> F -> LF -> KT et qui joue le rôle d'inclusion, bien qu'en général il ne soit ni injectif, ni fidèle On a bien le triangle commutatif de foncteurs -* KT Par contre, le foncteur U'o est fidèle, ceci résulte essentiellement du fait que si l'on a T(f) = T(g) dans C, alors f = g dans KT (i e L'0(f) = L' 0 (g), alors même que f et g peuvent être distinctes!), en effet, en usant ici du symbole d'équivalence ~~, pour éviter toute confusion, on trouve, pour f et g C -> C et f - f o l e - f o Me o zc - fie o Tf o 8c , g - g o le - g o Mco zc - /^oTg08c d'où f~~g puisque Tf= Tg par hypothèse 73 , On observera encore que si l'oubli K1(T) -> C est effectivement fidèle, il n'est pas bien fidèle en général prenons la version 2 de K1(T) et soient k_ C ->2 C' et k' C -» 2 C" deux flèches de même source et telles que U(k) = U(k'), alors on voit que \xc- T(k) = lie • T(k'), d'où, par composition à droite avec &c et naturalité, k = k' (c'est la fidélité de T « à la Kleisli »), on ne peut pas en conclure que k = k' parce qu'on ne sait pas si C = C", bien que T C = TC" 1 Si, par exemple, T est injectif sur les objets, alors U est bien fidèle. On vérifie sans difficulté que (U'o, L' 0 , 8)KT et (U 0 , L 0 , 8)KI(T) sont isomorphes dans FactÇï) Avec cette interprétation de la catégorie de Kleisli, on peut dire qu'une Talgèbre en C n'est qu'une concrétisation 0 de fie . 4.7. Algèbres et opérations à droite de la catégorie de Kleisli. Nous devons préciser techniquement la dernière remarque et tout d'abord définir la notion de catégorie d'opérateurs à droite Soit K une catégorie et soit E = (E r )c e obnk» un multi-ensemble indexé par les objets de K, soit E*K l'ensemble des couples (x,f) de ExK tel que X G E D , O Ù D est le but de f On dit que K opère à droite sur E , si l'on s'est donné une application cp . E*K —> E ayant les propriétés suivantes, où x*f est écrit pour cp(x,f) • V (x,f) G E*K , x*f G Ec , où C est la source de f , • V C G Obj(K) V x G Ec , x*Idc = x , • V (g,f) couple composable de K de but D, V x G E D , (x*g)*f = x*(g f) On note une telle opération à droite de K sur E par (E,(P)K OU simplement (E,(p) s'il n'y a pas de confusion. Un morphisme de (E,(p) vers (E',cp') est défini par la donnée d'une multi-application indexée soit h = (hc)c € obj(K>, chaque h c étant une application de Ec dans E' c , satisfaisant la condition suivante V (x,f) G E*K , f C ->D, hc(x*f ) = hD(x)*f Ces morphismes se composent de façon évidente et on dispose alors de la catégorie Ens-K des K-opérations à droite, et de son foncteur d'oubli vers la catégorie des multi- 74 ensembles U Ens-K -> EnsGbj(Kop' Bien sûr, Ens-K s'identifie canoniquement a la catégorie des foncteurs de Kop vers Ens et U s'interprète alors comme le foncteur « restriction » à la classe Ko = Obj(Kop) i On définit de manière analogue, avec des notations adaptées évidentes, la notion de catégorie d'opérateurs à gauche et celle de morphisme entre K-opérations à gauches, puis la catégorie K-Ens et son oubli V K-Ens -> Ens obj ' K) Bien sûr , K-Ens s'identifie canoniquement à la catégorie des foncteurs de K vers Ens , et V s'interprète alors comme le foncteur « restriction » à K0 = Obj(K) ' Notons au passage que les foncteurs U et V sont tous deux monadiques et ce pour des raisons tout à fait semblables à celles indiquées à propos des actions à gauche et à droite d'un monoïde fixe M* (cf exemples 3.4 et 3.5) l'interprétation d'un foncteur F Kop —> Ens (resp F K —> Ens) en terme d'opération à droite (resp à gauche) sur un multi-ensemble est tout à fait utile pour se convaincre qu'il s'agit d'opérations partout définies, donc algébriques, relativement à la catégorie EnsKo ' Nous verrons même à quel point il est complètement trivial d'obtenir ces monadicités en appliquant le critère de Coppey Les axiomes ci-dessus (d'opération à droite de K) incitent a représenter les éléments indexés de E par des flèches, plus précisément, écrivons x r pour signifier que x G E c , par convention, la source de xr est C, et on peut lui attribuer un but arbitraire, on peut convenir utilement, mais ce n'est qu'une possibilité, que les x c ont un but commun nommé (E,cp) f Une opération de K à droite s'interprète alors comme une extension de la composition dans K Remarques analogues pour les opérations à gauche. On obtient des dessins du genre suivant Opération à gauche de K sur E (E,(P) (x*f)*g Opération à droite de K sur E 75 Ces « cônes » sont bien évidemment isomorphes aux duaux des cônes limites du lemme de Yoneda (tout foncteur est limite canonique des foncteurs Home ) On peut dire qu'ils en sont ici une bonne « abstraction », quoique pour les opérations à gauche il vaut mieux prendre le dual du cône dessiné, i.e. interpréter K comme (Kop)op ' Arrêtons là ces digressions graphiques sur les foncteurs, (bien qu'il soit possible de les conduire beaucoup plus loin et que l'exercice en vaut la peine ) A toute algèbre (C,0) d'une monade T correspond une opération à droite naturelle de KT sur le multi-ensemble & = (CD))D e ob, D, on a x * e f = x *e (fio oTf 0 8D ) = 0Tx.(Tf 8D ) = 0 Tx (ED f) = 0 (Tx 8D) f = 0.(s c x) f = x f, et donc l'opération *e prolonge bien l'opération naturelle de composition dans C Une remarque s'impose ici: on a vu que L'0 C —> KT n'est pas fidèle en toute généralité et on serait facilement tenté de croire que l'opération à droite de KT sur C est mal définie: si on a deux flèches f, g : D -> C telles que f * g et f ~~ g, comment concilier les égalités suivantes le *e f = lc*eg = le o f = le o g = f = g , nécessaires, avec l'inégalité f * g 9 La réponse est simple, s'il y a une T-algèbre 0 en C, et si f ~ g , alors on a nécessairement f = 0.8c f = G.Tf.SD = 0Tg.8 D = 0.8c g = g , autrement dit, le cas de figure envisagé est impossible ' 76 Réciproquement, si une telle opération (C , Ens, encore appelé « réalisation ») On a même noté au passage que l'oubli Ui Alg(T) -> C des T-algèbres, monadique par définition, est une « restriction » du foncteur monadique U Ens-KT -> EnskT0 canonique Ens-Ki Alg(T) U U, (voc(C) = C') Co C Ens (Ko = Co) voç- L'idée des D-syntaxes d'algèbres est de fournir directement (à la place de KT, donc de T ) un système générateur D de KT, sans même connaître T par avance, sans même supposer 77 qu'existe une telle monade T ! C'est dire que le foncteur d'oubli (des algèbres), défini plus loin, n'est même pas supposé avoir un adjoint ! Ceci va mettre en jeu : • Certains objets de C seulement, et non pas tous a priori (comme dans KT), mettons B 0 ; ils vont servir d'arités ou co-arités (concrètes) aux lois. • Certaines lois (flèches) ayant pour sources et buts les objets de B0 ; les unes sont des lois formelles (i.e. ne figurent pas dans C) et d'autres sont des lois naturelles (i.e. sont des flèches de C) , évidemment la catégorie de Kleisli KT , avec toutes ses flèches de la forme / = fiD o f, où fio : TD -> D est formelle et f est naturelle, est surabondante (syntaxe trop riche n ). • Certaines équations (égalités entre composés de ces lois) Les relations qui définissent KT comme quotient de LF sont elles aussi nettement surabondantes (cf. les commentaires les concernant, au paragraphe 6 de cette section) Ces données se rassemblent en une seule: celle d'un foncteur bijectif sur les objets, soit I : B —> D, ayant pour source un certain sous-graphe (à compositions) B de la catégorie C, et pour but un graphe (a compositions) D Si I est fidèle, on peut simplifier encore une telle donnée, en disant que D est un surgraphe (à compositions) d'un sous-graphe (à compositions) B de C Comme je l'ai déjà fait remarquer (par exemple dans mon article « graphes structuraux », cité dans l'introduction), on peut, sans inconvénient majeur, estimer qu'on est toujours dans ce cas-là, parce qu'on peut en fait s'y ramener Désormais, on fera donc «comme si . », en particulier le symbole de composition de C et de D sera le même, La lettre « D », comme lettre générique, me paraît assez bien choisie: • De même que la lettre « C » est la première du mot « catégorie » et désigne donc très naturellement la «catégorie de base » , « D » est la première lettre du mot « données » (ou « data », pourquoi pas 9 ), et désigne donc très naturellement une « donnée supplémentaire, ri analogie et exemple on peut toujours décrire un groupe G par générateurs et relations en convenant de choisir systématiquement pour générateurs tous les éléments de G et pour relations toutes les relations existant dans G! Cà marche pour tous les groupes, ce n'est pas faux, mais ce n'est pas très économique, surtout si le but recherché est seulement de définir les groupes 78 attachée à C » pour y faire un certain type d "algèbre, le fait que D suppose donnée une portion de C (appelée B ci-dessus) n'est pas gênant, au contraire une telle donnée D n'est pas purement syntaxique les objets de C mis en cause ( B0 - D0 ) et certaines lois dites naturelles (Br^D) sont des éléments sémantiques (ou contextuels) (ou co-syntaxiques) de D. • Il se trouve, le hasard faisant bien les choses, que « D » est aussi la première lettre du mot « définition » et rappelle donc que la donnée D est en soi une définition d'un certain type d'algèbre dansC • Il y a d'autres raisons, moins sérieuses, comme celle-ci: D est la première lettre disponible après C dans l'alphabet Je me devais bien de fournir ces quelques explications, après m'être si vilainement acharné sur « triples » et « monades » Comme en 1971, je ne donnerai pas les exemples qui viennent immédiatement à l'esprit et qui sont fort nombreux Je ne vais pas non plus réécrire tout ce qui existe sur le sujet, ou réécrire l'histoire, quoique sur ce dernier point, il y ait encore beaucoup à dire ou à redire, inlassablement Juste ceci cependant si les seuls exemples pratiques ne concernaient que le cas de C = Ens, serait-il judicieux de développer toutes ces considérations allant des monades aux Dalgèbres sur une catégorie C générale ° Les catégoriciens, particulièrement, ne connaissent-ils pas d'autres objets que les ensembles n 4.9. Catégorie des D-algèbres. Soit donc D une syntaxe d'algèbres sur C et B0 * D0 la classe (petite ou non !) des objets de C mis en cause par D On dispose bien évidemment des notions d'opération à droite de D sur les multi-ensembles (EB)B€BO indexés par B 0 , d'homomorphisme entre telles opérations, on dispose donc de la catégorie Ens-D des opérations à droite sur les multi-ensembles indexés par B 0 , et du foncteur d'oubli naturel U : Ens-D -> Ens monadique (voir plus loin) 79 qui est Une D-algèbre 0 sur un objet C de C est alors une opération à droite de D sur C qui prolonge la composition naturelle par les flèches de C , on écrira x *H d au lieu de 0(x,d), pour tout couple de flèches consécutives, d B' —> B e D e t x B — » C e C , e t Ton a par définition • x *e d = x . d , si d € C, • (x *0 d ) *e d' = x *n (d d') pour tout couple composable (d, d') dans D Un homomorphisme h (C,0) —> (C',0') est une flèche h C —> C telle que • h (x *e d) = (h . x) *o d chaque fois que x *e d est défini Ces homomorphismes se composent naturellement et on dispose alors de la catégorie Alg(D) des D-algèbres et de son oubli vers C, soit UD Alg(D) —> C et on a un carré commutatif de foncteurs analogue au précédent canonique Alg(D) - ^ Ens-D U UD (vo»(C) = Cl) Ens Bo (D 0 = B0) vos 4.10. Critère de Coppey. Le fait pour un foncteur d'oubli d'avoir un adjoint à gauche ne dit rien sur son éventuel caractère algébrique C'est ce que nous allons montrer. On peut déjà se convaincre intuitivement de cela en proposant des exemples d'oublis ayant un adjoint à gauche et pour lesquels le foncteur de comparaison d'Eilenberg-Moore n'est pas un isomorphisme, l'exemple « bateau » est celui de l'oubli U : Top -» Ens de la structure d'un espace topologique; tout ensemble E engendre une structure libre à savoir l'espace discret (E,Td) sur 80 E, la monade associée à cette adjonction est particulièrement triviale c'est la monade identique sur Ens , dont la catégorie d'algèbres est (à isomorphisme canonique près) Ens , le foncteur de comparaison n'est autre que U (à isomorphisme canonique près) , on peut dire encore que la partie algébrique du foncteur U est réduite à sa plus simple expression ldEns II n'est pas difficile de produire , autant qu'on en veut, de tels exemples . Théorème (Coppey, 1971) Les foncteurs d'oubli tels que UD Alg(D) -> C sont bien fidèles et créent les conoyaux de paires contractiles Corollaire Si un foncteur d'oubli de D-algèbres possède un adjoint à gauche, il est monadique Corollaire (Critère de Coppey) Soit U A —> C un foncteur d'oubli de structures ayant un adjoint à gauche U est monadique si et seulement si il existe une syntaxe D telle que U soit isomorphe à UD au dessus de C Je suis un peu confus de devoir énoncer de tels corollaires, qui sont des conséquences parfaitement naturelles, immédiates, et triviales du théorème, mais l'expérience m'a appris qu'il était prudent de le faire, si on veut éviter que d'autres, pas forcément bien intentionnés, s'en chargent en « tirant la couverture a eux » Démonstration du théorème (se référant explicitement au « critère de Beck ») Soit D une syntaxe d'algèbre sur C et UD Alg(D) —> C le foncteur d'oubli associé, il est évidemment bien fidèle Soient alors (C,0) et (C',0') deux D-algèbres et f, g . C -> C deux flèches qui définissent des homomorphismes de D-algèbres, soit enfin q C —> Z un conoyau contractile de (f, g), il existe donc deux flèches (de retours !) s , t telles que q f = q g , q s = 1 , f t = 1 , g.t = s q On doit simplement établir que Z porte une structure naturelle de D-algèbre , soit (Z,Q, qui fait de q un homomorphisme de (C,0) vers (Z,Q (c'est nécessairement le « conoyau créé » que l'on cherche! ) Soit x : B -> Z une flèche de C et d B' -> B une flèche de D. • Valeur nécessaire de x *c d . Puisque q doit être un homomorphisme, on doit avoir q.((s.x)*ed) = (q(sx))* c d = ((qs).x)* c d = x *c d , et on dispose donc de la définition suivante de l'opération Ç . x *ç d = q ((s x) * e d) • Ç prolonge l'opération naturelle de composition dans C : supposons d € C, on voit que 81 x * c d = q ( ( s x ) * e d ) = q((sx).d) = (q s) (x d) = x d Ç est bien une opération à droite de D sur Z1 soit donc (d, d") un couple composable dans D et ô = d d' le composé correspondant, on doit établir que (x *c d ) *c d' = x *c ô On a en effet (x *c d ) *c d' = q [(s q ((s x) *e d)) *e d'] , par définition de Ç , = q[(gt((sx)* e d))*e(T], car sq = gt , = q[g[(t((sx)* 0 d))*e d']] , car g (C',0')-> (C,0) est un homomorphisme, = (q g).[(t ((s x) * e d)) *«• d ' ] , car la composition est associative dans C , = (q f) [(t ((s x) *„d)) *«• d'] , car q g - q f , = q [f [0 ((s x) *ed)) *e d']] , car la composition est associative dans C , = q[(ft ((sx)* e d))*ed'] , car f. (C',0') -> (C,0) est un homomorphisme, = q [((sx)*«d)*ed'] , car f t = 1 , = q [(s.x)* e (d.d')] , car (C,0) est une D-algèbre , = q [ (sx) * 0 ô] , car d d' = 5 , = x *c ô , par définition de l'opération ^ • q (C,0) -> (Z,C) est bien un conoyau dans Alg(D) , soit h (C,0) -» (D,À) un homomorphisme d'algèbres qui coégalise f et g , comme q est un conoyau dans C de f et g, il existe une unique flèche k Z -» D telle que k q = h , reste à établir que cette flèche k (Z,Q -> (D,À,) est bien un homomorphisme , or on voit que k.( x *c d) = k [ q ((s x) * e d) ] , par définition de C , = (k q)((sx) *«d) , car la composition est associative dans C , = h((sx)* H d) , car kq = h, = (h.(sx))*>.d , car h : (C,0)-> (D,\) est un homomorphisme, = ((h.s).x) *>.d , car la composition est associative dans C , = (k.x) *>. d , car h.s = k est l'unique flèche telle que k q = h, [(hs).q = h(s.q) = h.(gt) = (hg).t = (h f) t = h (f t) = h ] et ceci achève de prouver que k : (Z,Q -» (D,X) est bien un homomorphisme. Pour finir, j'insiste sur deux choses qui apparaissent clairement ici • La démonstration n'est qu'une succession de déplacements de parenthèses portant sur des mots de longueur 7 au plus et de substitutions de valeurs relatives à diverses équations Elle 82 établit ainsi des propriétés d'associativité (partielle), on peut, par exemple, écrire l'élément de C suivant q g t.s.xd.d', dans le contexte d'algèbres précisé ci-dessus, sans qu'il y ait le moindre risque de confusion: on peut l'interpréter à volonté comme étant: ((q g t s.x) *çd) *çd', ou (q g) ((t s x) *e- (d d')), ou (q g) (t.((s x) • e d ) ) * ^ ' ) , ou ..., un bon exercice consistant à écrire toutes les manières possibles B' l'associativité dans C a été soulignée exprès pour bien mettre en évidence ce que cette démonstration doit à la structure de « co-syntaxe » (ici c'est une catégorie C, elle pourrait bien être elle-même définie par « générateurs et relations» , etc. ) : l'associativité de C n'est ni plus ni moins indispensable que les autres pour obtenir Talgébricité voulue de UD 4.11. Exemple d'application. Etablissons qu'un foncteur comme U : Ens-D -> EnsBo , où B0 = Obj(D) est monadique A l'évidence il admet un adjoint à gauche : soit (E B )B e Bo un objet de Ens ° , il engendre la structure libre ( ( E D B ) B e B<> ,

X' si et seulement si il existe des entiers ni , n2 , ... , np et pour chaque indice i , 0 < i < p-1 , 83 une disposition cohérente de parenthèses permettant de calculer dans D l'élément CM à partir du sous-chemin (d n , d n +1 , ... , d n ) de x (par convention, no = 1) La relation d'équivalence >< engendrée par t> est la suivante: x ^ ^ X si e t seulement si il existe lu Xi, ,X2n i tels que x = Xi > X2 < X3 >•••< X 2n-i = x' Un chemin modulo les équations de D est une classe d'équivalence modulo >< • Définissons alors l'opération cp: soit (x, c) E E D B , X = (di , d 2 , ... ,dn ) un représentant de c, et d : B " -» B e D , on pose (x,c) % d = (x, c') où c' est la classe d'équivalence du chemin (di , d 2 , ... ,dn , d) modulo >< , c'est bien un élément de EDB , et il est évident que si l'on a x > X' = ( c i , c 2 , ... , c p ) alors on a (di , d 2 , ... ,d n , d) > (d , c2 , ... , cp , d), et donc, (x,c) *v d est bien défini . Si d = 1B et (x,c) G EDB , on a: (x,c) % 1B = (x,c), car (d u d2,...,dn ,1B) > (di , d 2 , ,dn ). Supposons d.d' défini dans D, on a (di , d 2 , ... ,d n , d , d') > (dj , d2 , ... ,dn , d d') de sorte que ((x,c) % d) % d') - (x,c) * 9 (d.d'). Ainsi ((EDB)B e obj(B), cp ) est bien une opération à droite de D Pour chaque B G B 0 , on dispose de l'application canonique: sB EB —> EDB qui est définie par sB(x) = (x,l B ) modulo >< . Soit alors ((F B ) Be Bo , MO une opération à droite de D sur le multi-ensemble (FB) B € B0 et (fB) B e BO : (EB) B e B0 -> (FB) B € BO une multi- application, Celle-ci se « prolonge » de manière unique en un homomorphisme entre opérations à droite : (hB) B € Bo : ((EDB) B e BO , cp) ~> ((FB) B € B0 ,V|/) en ce sens que: V B G B0, hB 0 £B = fB, on doit prendre hB (x,c) = (...((fB(x) %di) *H/d2) *w ...) *^ dn) , si (di , d2 , ... ,dn ) est un représentant de c modulo x La monadicité est établie automatiquement dès lors qu'on peut donner de la structure d' « opération à droite de D sur un multi-ensemble » une définition à la manière D-algèbres (ce n'est pas le même « D » , mais presque, et ce n'est pas un hasard, si on a bien suivi tout ce qui s'est passé jusqu'ici!). Nous sommes donc dans la catégorie C = Ens80 et on veut définir un sur-graphe D d'un sous-graphe B de C de sorte qu'une structure ((EB) B e B« , cp) apparaisse bien comme une opération à droite de D sur & , où C = (EB) B e B« , étendant l'action naturelle de B Or ceci est parfaitement trivial, mais vaut d'être détaillé au moins une fois! A tout objet D de D , faisons correspondre le multi-ensemble D* suivant: D* = (D B )B e BO OÙ DB = 0 si B * D et ° D = {*} (ensemble à 1 élément) , le graphe à composition (partielle) D a pour objets les multi-ensembles D * , D É Obj(D), ses flèches autres que les identités sont toutes « formelles »: 84 à toute flèche d : D' —> D de D correspond une flèche formelle d : D \ —» D» , la composition dans D est celle « copiée » de D , bref, D est canoniquement isomomorphe à D, il est clair alors qu'une /)-algèbre sur C = (E B ) B e Bo s'identifie à une opération à droite de D sur le multiensemble C = (E B )B e BO , essentiellement parce qu'une flèche dans C de D* = (D B )B e BO vers C = (E B )B € BO s'identifie à un élément de ED (image de *). A travers cet « exemple » on comprend pourquoi la monadicité « générale » est toujours du type de celle d'« opération à droite d'un graphe à composition sur un multiensemble », laquelle structure généralise celle d' « opération à droite d'un monoïde sur un ensemble ». Ainsi peut-on organiser la défense du mot « monade » dans le méchant procès que je lui ai fait, conscient que le bon choix technique aurait pu être « graphe-à-compositionnade », dont la joliesse est douteuse ! Remarquons, pour finir, qu'on peut substituer au foncteur yoB : C -> Ens foncteur de Yoneda v* : C -> EnsB°P et au foncteur U : Ens-D -> EnsBo d'oubli associé à l'inclusion B e D , soit V Ens -» Ens Ens-D -> Ens le le foncteur , ou plus symétriquement , ou encore Ens-D -> Ens-B , ce foncteur V est lui-même monadique et son adjoint à gauche n'est autre que l'extension de Kan le long de l'inclusion B c D canonique EnsD°P = Ens-D Alg(D) V Ur (vB(f)= Hom(f,-) ) C -^ Ens B = Ens-B VB Un argument simple permet alors de déduire la monadicité de UD de celle de V, puisque UD apparaît alors comme l'image réciproque de V le long de VB (produit fibre) Ce paragraphe 4 est entièrement contenu (avec des notations et une terminologie légèrement différentes) dans mon texte original paru sur ce sujet, en 1972: 85 Théories algébriques et extension de préfaisceaux, Cahiers de topologie et géométrie différentielle, Volume XIII, 1 et Compléments, Volume XIII, 3. La monadicité des extensions de Kan le long d'un foncteur bijectif sur les objets a fait l'objet de plusieurs exposés au Séminaire C.Ehresmann en 1968 et 1969, j'en ai parlé à l'époque sous la forme de catégories de triangles de foncteurs d'hypermorphismes et foncteurs d'oublis entre elles (un hypermorphisme étant la « trace laissée » par l'opération d'un morphisme f : A -> B sur une structure S « au-dessus de A » , on écrit fS pour la structure but et F hypermorphisme peut être noté (f,S) : S -> fS ). A plusieurs endroits de ce texte, j'ai fait part de réflexions plus personnelles, concernant par exemple la terminologie ou les dates, etc..et si je n'ai pas hésité parfois à me mettre en avant, c'est qu'il fallait bien combler des omissions qui figurent explicitement dans un texte assez récent sur la question, et dont le principal intérêt m'a paru résider justement dans ces omissions. A mon tour d'omettre ... une telle citation ! 86 Bibliographie. L. Coppey • Notes aux Comptes Rendus de l'Académie des Sciences de Paris • Factorisations d'un cotriple. juillet 1970 • Morphismes et co-morphismes de cotriples, juillet 1970. • Algèbres de décompositions dans les catégories, septembre 1971 • Morphismes entre catégories avec modèles, Série des Esquisses Mathématiques, N° 8, Paris, 1970. [Développement des deux premières notes ci-dessus On y trouve, avec une terminologie et des notations différentes de celles employées ici, les descriptions et propriétés des catégories Fact (T) et K1(T). Deux idées, nouvelles à l'époque Tr morphismes, et non seulement objets, peuvent servir de modèles dans la théorie de Tierney-Applegate, Q considération d'atlas maximaux ] • Observations sur les triples et les actions de monoïdes, Travaux du Séminaire de Catégories, Amiens, 1970-1971 [Les monades d'opérations à droite de catégories sur les multi-ensembles jouent un rôle de premier plan dans la théorie des triples Introduction aux théories de Linton et au travail de Mânes - sur la structure du monoïde de T(l)] • Théories algébriques et extensions de préfaisceaux, Cahiers de Topologie et Géométrie Différentielle, Vol XIII, 1, Paris, 1972 [Contient en substance les paragraphes 2 et 4 du présent texte II s'agit encore d'opérations de catégories Quelques maladresses insignifiantes, facilement repérables et réparables, y figurent et justifient en partie le texte suivant ] • Compléments à l'article précédent, Cahiers de Topologie et Géométrie Différentielle, Vol.XIII, 4, Paris, 1972 [Une syntaxe d'algèbres sur une catégorie C est fournie, cette fois, par un graphe à composition (partielle) (ou graphe multiplicatif au sens d'Ehresmann) et non forcément par une sur-catégorie de C: c'est l'un des intérêts spécifiques des syntaxes d'algèbres ] Décompositions algébriques de structures en produits, Collection « Esquisses Mathématiques », N° 14, Paris, 1971. [Développement très détaillé de la 3 e Note aux C R A S. ci-dessus Calculs des monades «puissances», figurant ici au paragraphe 3 On y trouve en particulier les lois de « monoides-bandes » V x,y,z xyz = xz] 87 • Algèbres de décompositions et précatégories, Thèse d'Etat (Amiens, 1978) Diagrammes, Sup Vol N° 3, Paris, 1980. [Au chapitre 1, caractérisation des catégories dites algébriques, i.e. dans lesquelles les algèbres des monades « puissances » s'interprètent comme les décompositions en produits de facteurs. On n'y fait que reprendre en l'améliorant sur quelques points le texte précédent de 1971. Le cas de l'ensemble 0 y est « écarté » bien inutilement - cf la bonne définition des classes d'équivalence de prédécompositions, au paragraphe 3, ici La thèse comporte 5 chapitres, dont un d'arithmétique, assez long, qui nécessiterait à lui seul encore bien des développements ] • Problèmes typiques concernant les graphes multiplicatifs, Diagrammes, Vol. N° 3, Paris, 1980 [Etude de diverses questions techniques soulevées par le passage « obligé » des catégories aux graphes multiplicatifs foncteurs d'hypermorphismes, « plongement » de Yoneda, classification des produits tensoriels de graphes multiplicatifs; catégories de parenthésages, etc .] • Structures de base pour définir les structures, Diagrammes, Vol N° 7, Paris, 1982 [Ou les D-algèbres « revisitées » par l'auteur. L'accent est mis sur les structures non associatives On y trouve la mise en cause de la structure de catégorie de base C qu'on suggère de remplacer éventuellement par des graphes multiplicatifs particuliers La notion d'étages d'algébricité « empilés les uns sur les autres » y figure explicitement en finale Le texte proprement dit est divisé en 12 parties inégales dont l'ordre n'est pas évident ] • Catégories de Peano, catégories algorithmiques, récursivité, Diagrammes, Vol. N° 12, Paris, 1984 [Comporte 4 parties relativement indépendantes une sur les catégories à extensions de Kan le long de » - > 0 dites catégories de Peano, une autre sur la triplabilité des catégories à limites (et plus généralement à extensions de Kan) choisies sur les catégories, à la manière des Z>-algèbres - exemples naturels et inévitables qui bien malheureusement ne figuraient pas dans les textes de 1971 et 1972, une encore sur catégories et récursivité primitive, une enfin sur les algèbres partielles et la non-monadicité des catégories de Peano sur les graphes] • Graphes structuraux, Diagrammes, Vol. N° 24, Paris, 1990 [Ce texte reprend un par un tous les points techniques soulevés par l'étude des Z)-algèbres, de leurs syntaxes et co-syntaxes On y met en lumière d'une part la symétrie entre syntaxe et sémantique (y compris dans l'écriture des éléments 88 ou éléments généralisés), d'autre part l'unification possible des définitions et démonstrations de base sous forme de déplacements de parenthèses, un peu comme suggéré ici, au paragraphe 4, dans la démonstration du critère de Coppey. On propose une interprétation du sens des déplacements de parenthèses, liée à l'échange entre syntaxe et sémantique] L.Coppey et C.Lair • Algébricité, Monadicité, Esquissabilité, Non Algébricité, Diagrammes, Vol. N° 13, Paris, 1985. [Ce texte est de loin le plus développé et le plus élaboré au sujet des Dalgèbres On y trouve toutes les précisions techniques voulues sur des questions variées comparaison systématique des 3 points de vue possibles, monades / Z)-algèbres / esquisses, syntaxes complètes, foncteurs fondamentaux, construction des algèbres libres dans les catégories ayant suffisamment de colimites, rang d'algébricité (aux trois points de vue cités), algèbres partielles (divers types de partialités sont analysés) dont la considération est fortement motivée par les constructions d'algèbres libres voir aussi la partie 4 de « Catégories de Peano, catégories algorithmiques, récursivité». Le degré d'algébricité est introduit Exemples où 2 étages d'algébricité correspondent quand-même au degré 1 (catégories à limites choisies au dessus des graphes) Un autre exemple (justement celui des catégories de Peano au dessus des graphes) où ce degré est 1/2] RGuitart et C.Lair • Limites et co-limites pour représenter les formules, Diagrammes, Vol N° 7, Paris, 1982 C.Lair, • Trames et sémantiques catégoriques des systèmes de trames, Diagrammes, Vol. N° 18, Paris 1987. • Eléments de théorie des patchworks, Diagrammes, Vol. N° 29, Paris 1993. Malgré les apparences, cette bibliographie n 'est pas partisane. Simplement, elle comble, et seulement sur le sujet qui nous intéresse ici, un vide manifeste mainte s fois constaté! 89