D IAGRAMMES L. C OPPEY C. L AIR Algébricité, monadicité, esquissabilité et non-algébricité Diagrammes, tome 13 (1985), p. 1-112 © Université Paris 7, UER math., 1985, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Diagrammes, Vol. 13 , 1985. A.M.S. Sub. Class. 18 C 10 , 18 C 15, 18 C 20 , 18 A 10. Algébricité, monadicité, esquissabilité et non-algébricité . L. Coppey et C. Lair. INTRODUCTION. Ce travail répond à une question posée par A. Burroni en Novembre 1983, au Séminaire de Théorie des Catégories de l'Université Paris 7: - la catégorie des (petites) catégories munies d r un choix d'extensions de Kan inductives, le long du foncteur 1^ > ( IN, + ) , est-elle une catégorie d'algèbres graphiques (au sens de (A.L.G.R.)) ou encore, ce qui est équivalent dans ce cas, est-elle "monadique" sur la catégorie Graph des graphes (orientés)? S'il nous paraît opportun de donner, ici et maintenant, la réponse à cette question, ce n'est évidemment pas pour prouver une éventuelle sagacité supérieure ou une possible rapidité plus grande à résoudre ex nihilo un problème neuf par "nature" (quitte à déposséder celui qui serait alors son découvreur de cette nouveauté). C'est, bien au contraire, pour saisir une occasion supplémentaire de (ré-)affirmer qu'un cadre théorique convenable et des méthodes appropriées existent depuis longtemps (1972 pour le premier, 1975 pour les secondes) et qui sont adaptés à un traitement assez systématique de ce problème (comme à d'autres, dont la "nature" n'est ni plus ni moins importante ou consistante!). Qu'est-ce d'autre, en effet, qu'une algèbre graphique (au sens de (A.L.G. R.) ), sinon une algèbre d'une syntaxe (au sens de (T.A.E.P.), dégagé dès 1972) particulière sur la catégorie particulière Graph ; et quelle serait la "nature" immanente particulière de la catégorie Graph qu'au- cune autre catégorie ne recèlerait? De même, de quelle "essence" profonde la question précédente (et, avec elle, sa réponse) serait-elle douée, que ni la question suivante, ni sa réponse (fournie dès 1975 en (E.S.T.R.)) n'auraient l'heur de posséder: - la catégorie des (petites) catégories munies d'un choix d'extensions de Kan (inductives et/ou projectives),le long d'un ensemble de foncteurs donnés entre petites catégories, est-elle monadique sur Cat ? On comprendra donc que nous ayons cru nécessaire de développer, dans le présent travail, nettement plus que la seule preuve technique de la réponse à la question initiale. D'autant que les "initiateurs" de ce cadre théorique convenable et de ces méthodes appropriées ont tout de même leurs mots à écrire, après ceux qui en ont tant écrit, si longtemps après, en se contentant, pour les uns, de banalités affligeantes et en se réfugiant, pour les autres, dans une admiration mystique et passive des quelques expédients techniques finalement utilisés pour traiter (malgré tout, et lorsqu'ils y parviennent) quelques cas particuliers. Et quels autres mots écrire, sinon ceux permettant de présenter, à nouveau et avec la plus grande précision possible, ce cadre, ces méthodes, leurs développements (nombreux, depuis 1972, et qu'un lecteur sérieux peut trouver facilement dans les différents textes publiés, depuis cette date, par les deux auteurs) et les quelques (rares) travaux qui en sont à l'origine ou ont pu fournir des compléments réellement utiles? La théorie "générale" de l'algébricité, au sens de (T.A.E.P.), admet exactement les deux origines suivantes: - d'une part, les travaux de F. E. J. Linton (voir (A.O.F.S.)) où la catégorie de Kleisli d'une monade te) £ JT sur une catégorie (localement peti- est interprétée comme une "sur-catégorie" de £ , dont les objets sont les sortes ou arités du type de structures que déterminent les algèbres de H , dont les flèches (essentiellement, celles qui n'appartien- nent pas à C ) en sont les lois de composition et dont les diagrammes commutâtifs en représentent les "axiomes": de ce point de vue, la catégorie de Kleisli de H est donc la syntaxe diagrammatique complète (en ce sens qu'elle contient "toutes" les lois et "toutes" les équations valides) des algèbres de IT , - d'autre part, les travaux de C. Ehresmann (voir (E.T.S.A.)) où une présentation d'un type de structures (à l'aide de lois, génératrices de lois dérivées, et d'axiomes, dont on peut déduire des théorèmes) est représentée à l'aide d'une esquisse, c'est-à-dire, notamment, par un graphe multiplicatif (qui est un système de générateurs et relations pour une catégorie): ainsi, une telle syntaxe diagrammatique n'est pas en général complète, mais elle engendre toujours une syntaxe complète . Dans ces conditions, il est naturel de poser, en toute généralité, qu'une syntaxe d'algèbres sur une catégorie £ est (voir Part. I, §1) un sur-graphe multiplicatif d'un sous-graphe multiplicatif de £ : c'est une présentation d'un type de structures algébriques dont les objets de £ peuvent être, éventuellement, munis, et elle engendre toujours une syntaxe complète, i. e. une sur-catégorie de £ . Il est alors utile de comparer ce point de vue à celui de la monadicité, dont il est, en partie, issu (voir Part. I, §2): un foncteur vers £ esc algébrique s'il est le foncteur "objet (de £ ) sous-jacent" de la catégorie des algèbres d'une syntaxe d'algèbres sur C • Lorsqu'il admet un adjoint à gauche (ce qui n'est pas toujours le cas), il est nécessairement monadique (c'est ce point, essentiel, qui fut souligné dès 1972 en (T.A.E.P.)). Réciproquement, un foncteur vers £ , admettant un adjoint à gauche et monadique,est toujours algébrique (pour la syntaxe que constitue la catégorie de Kleisli de la monade associée). Pratiquement, on peut souhaiter contrôler la taille, ou mieux le degré de completude éventuelle, d'une syntaxe, i. e. n'engendrer, à partir d' une syntaxe d'algèbres sur £ , qu'une sur-catégorie d'une sous-catégorie donnée (qui limite cette taille ou ce degré) de C (voir Part. I, §3). Ceci est à rapprocher (voir Part. I, §4) du point de vue de la "monadici- té partielle", développé en 1975 par Y. Diers (voir (F.D.C.A.)): un foncteur algébrique en son sens l'est nécessairement au sens de la Part. I, §1. Réciproquement, un foncteur algébrique dans ce dernier sens l'est nécessairement au sens de Y. Diers, dès lors qu'il admet un adjoint à gauche partiel (ce qui n'est pas toujours le cas). Nous considérons donc (à la suite de (T.A.E.P.)) que ce qui caractérise l'algébricité d'un foncteur n'est pas qu'il possède un adjoint à gauche (total ou partiel) et qu'il soit alors (totalement ou partiellement) monadique, mais plutôt (ou seulement) qu'il est associé à une syntaxe d'algèbres explicite (complète ou non). Il n'en demeure pas moins qu'un tel foncteur algébrique peut posséder un adjoint à gauche. C'est là, simplement, une de ses propriétés éventuelles supplémentaires, liée tant à la forme particulière de la syntaxe d'algèbres considérée qu'à celle de la catégorie dans le langage de laquelle cette syntaxe est décrite. Ainsi, si C possède toutes les limites inductives petites et si les sortes de la syntaxe d'algèbres (supposée petite) sur (où £ sont autant d'objets ^-présentables de £ <* est un ordinal régulier donné) , un foncteur algébrique asso- cié à cette syntaxe possède toujours un adjoint à gauche: il est donc monadique et, de plus, la monade associée est de rang <* . Ceci suggère l'étude générale de la notion de rang d'algébricité (voir Part. II, §1): une syntaxe d'algèbres sur la catégorie quelconque £ est de rang objets oc , si elle est petite et si tous ses objets sont des «.-présentables de £ . Il est alors facile de comparer, comme précédemment, les foncteurs de rang <* (ou rang oc-algébriques) dans ce sens aux foncteurs monadiques de c* .(voir Part. II, §2). Plus substantiellement encore, si £ est une catégorie localement présentable (au sens de (L.P.L.G.)) ou, ce qui est équivalent, si est la catégorie des réalisations d'une esquisse initiale o(£ 0<>-projec- tive (au sens de (E.T.S.A.), dont (T.A.E.P.) est également en partie issu, comme signalé plus haut), nous établissons (voir Part. II, §3) que, pour un foncteur sont équivalentes : U A > £ , les trois propriétés suivantes - U admet un adjoint à gauche et est oc-monadique, - U est cX-algébrique, - U est oC-sur-esquissable, au sens de (E.S.T.R.) (i. e. une catégorie de réalisations d'une esquisse A est oc-projective dont tous les objets, ou sortes, sont déduits des objets de l'esquisse initiale par limites projectives). Ainsi, dans ce cas, les méthodes syntaxiques, initiées notamment en (E.S.T.R.) , dès 1975, sont applicables, dès lors que l'on cherche à tester l'algébricité, ou la non-algébricité, d'un foncteur U: A >£. La construction (dans les conditions évoquées plus haut) d'un adjoint à gauche à un foncteur £ cC-algébrique montre que tout objet de engendre une algèbre libre qui est limite inductive OC-filtrante d'algèbres "partielles" (voir Part. III, §*t): au moins dans son sens intuitif, il s'agit là d'une pratique finalement très courante (voire systématique). Et qui suggère une étude plus précise de la notion d'algèbre partielle. Si B_ est un sous-graphe multiplicatif de de £ , alors quand B B_ agit et si varie dans la classe des objets de d'algèbres sur £ , un tel C B_ , i. e. si Hom (B,C): ainsi, à toutes flèches > C de sur c) une flèche Hom p (B,C), D D est une syntaxe est muni d'une structure d'algèbre, met- A, dès lors que cette action canonique de c: B' est un objet B^ . Si, de surcroît, B_ admet un prolonge- ment en une action (par "composition formelle") de bles C (par composition) sur les ensembles est un sur-graphe multiplicatif de tons £ d: B I) sur les ensem•B' de D et £ , "consécutives", est associée (par action de d c . d : B ^ C* de £ . De ce point de vue A (déduit de (A.O.F.S.)), il est naturel de considérer que C n'est muni que d'une structure d'algèbre partielle , mettons tion canonique (totale) de tielle (i. e. au moyen A' , dès que l'ac- B^ admet un prolongement en une action par- de fonctions et non d'applications) de D sur les ensembles Hom (B,C): ainsi, seules certaines flèches consécutives d: B de formelle >B' £ et c: B' >C de £ admettent une composée c • d dans £ . Autrement dit, une algèbre partielle est A' un système de générateurs et relations pour une algèbre totale ce qui n'est pas fait pour surprendre l'intuition!) , mais très exactement dans le sens où un graphe multiplicatif (ou encore un système de structures, au sens de (c. A.S.T.)) est un système de générateurs et relations pour une catégorie (ou pour une espèce de structures, au sens de (C .A .S . ! • ) ) ; c'est d'ailleurs ce point qui justifie les développements ultérieurs du premier des deux auteurs (voir (P.C. G. M.) et (S.B.D. S.)). Nous reprenons ce point de vue (initié dès 1972, en (T.A.E. P, )) dans deux cas particuliers (de contraintes sur le genre de partialité des algèbres partielles considérées): ceux des méta-algèbres (voir Part. III, §1) et des para-algèbres (voir Part. III, §2), qui permettent d'exprimer précisément comment une algèbre libre est limite d'algèbres partielles (mais, pour quelques développements complémentaires sur ce sujet, on pourra consulter (C.A.P.E.)). On connaît le critère de monadicité de J. Beck (voir, par exemples, (C.F.W.M.)) pour un foncteur admettant un adjoint à gauche. On connait, aussi, le critère (plus général) d'algébricité (en son sens) de Y. Diers (voir (F.D.C.A.)), pour un foncteur admettant un adjoint à gauche partiel. Nous ne donnons pas d'autre critère (i. e. d'autre condition nécessaire et suffisante) d'algébricité (au sens de la Part. I, §l)pour un foncteur. Il y a à cela plusieurs raisons. Remarquons, tout d'abord, que le critère de monadicité de J. Beck n'est pas (malgré la simplicité de son énoncé) d'une application aisée (ce qui ne nuit en rien à son intérêt théorique - qui nous est utile): il est rare que l'on puisse calculer aisément les conoyaux de paires, même "au dessus" de paires contractiles, dans une catégorie ... dont on ignore même si elle est monadique. C'est d'ailleurs l'une des raisons qui ont conduit à la mise en oeuvre des méthodes utilisées en (E.S.T.R.). De même, le critère d'algébricité de Y. Diers est d'une application pratique encore plus aléatoire (ce qui ne nuit pas plus à son intérêt théorique): on ignore même, a priori, quels types de limites (de toute façon plus complexes que les conoyaux) calculer. Il nous a donc paru inutile de "compléter" ces deux critères, satisfaisants sur le plan théorique, d'un troisième encore moins applicable ! C'est aussi que le problème de l'agébricité d'un foncteur U: A ^£ ne se pose pas toujours, dans la pratique, ex abrupto. Plus précisément 7 il se pose souvent sous la forme suivante (classique, abordée en (D.I.L.A.)): - sachant que U': A' > £ est algébrique et que U": A l'est aussi, le foncteur composé U = U'.U" > A' l'est-il ? (on pourrait, plus généralement, supposer que U est un composé de plus de deux foncteurs algébriques, rejoignant ainsi complètement le point de vue des "étages" d'esquissabilité abordé en (E.S.T.R.)). Toujours est-il que ce n'est que pour ce type de foncteurs, qualifiés de sous-algébriques (voir Part. IV, §1), que nous énonçons une condition suffisante (i. e. pratique) d'algébricité; d'ailleurs, c'est à ce propos, et dans ce but, que la considération de syntaxes non nécessairement complètes (i. e. de présentations) s'avère tout à fait essentielle (voir Part. IV, §2). Nous consacrons enfin la Partie V à quelques exemples génériques. Essentiellement, nous reprenons celui, qui n'était pas du tout choisi eu hasard, traité en (E.S.T.R.) dès 1975 (voir Part. V, §1): la catégorie des (petites) catégories munies d'un choix d'extensions de Kan (inductives et/ou projectives), le long d'un ensemble donné de foncteurs entre catégories petites, est algébrique sur Cat. Nous montrons aussi comment des modifications ou spécifications quasi-mécaniques de ce type de structures conduisent (notamment, en utilisant la condition d'algébricité des foncteurs sous-algébriques établie dans la partie IV) à des situations d'algébricité sur Graph: - la catégorie des petites catégories munies d'un choix de noyaux et/ou conoyaux isotropes, est algébrique sur Graph (ce qui est obtenu d'une manière différente de celle que nous avions élaborée antérieurement, en même temps qu' A. Burroni et indépendamment), ou encore à des situations de non-algébricité sur Graph: - la catégorie des petites catégories de Peano n'est pas algébrique sur Graph, ce qui répond à la question évoquée dès le début. Nous ne tirons aucune gloire particulière d'avoir pu fournir les réponses à quelques questions particulières ... qui sont, aujourd'hui bien à la mode. Nous n'en tirons, non plus, aucune conséquence philosophique ou idéologique (sinon que la mode n'est pas étrangère à l'idéolo- gie). Par contre, nous constatons que, décidément oui, un cadre théorique convenable et des méthodes appropriées existent, et depuis longtemps, qui intègrent complètement ces quelques questions particulières et audelà . PARTIE I : ALGEBRICITE 10 1. Algébricité. A. - On dit que D A = (£,B^,J: B_ gèbres (sur £ ) si, et seulement si: - £ - > D) est une syntaxe d'al- est une catégorie localement petite, B_ est un sous-graphe multiplicatif de £ , - J: B_ > £ est un foncteur, bijectif sur les objets, (voir (T.A.E.P.) et (S.B.D.S.)). B. - Soit D A ment petite £ • On dit que une syntaxe d'algèbres sur la catégorie locale- (C,F) est une DA-algèbre (sur £ ) si, et seulement si: - C est un objet de £ , - F: £ > Ens est un foncteur, - le diagramme de foncteurs suivant est commutâtif: B° P Homp(-,C) £ Jop > D° P = H(C) I Bop Ens (alors, pour toute flèche d: J(B) > J(B') de D et toute flèche c: B° > C de £ , on pose c . d = F(d)(c) ) , F (voir (T.A.E.P.) et (S.B.D.S.)). De même, on dit que (c,c*): (C,F) > (C',F9) est un homomorphisme de la DA-algèbre (C,F) vers la DA-algèbre (C',F') si, et seulement si: 11 - c: C -> C - c: F -> F 1 : D•°P. est une flèche de -> Ens C , est une transformation naturelle (nécessairement unique) - le diagramme suivant, de foncteurs et transformations naturelles, est commutâtif: >°P -*> D°P H(C) F' Bien entendu, les D*-algèbres (resp. les homomorphismes entre D*-algèbres) sont les objets (resp. les flèches) d'une catégorie, que l°on note D*-Alg , et l'on dispose des deux foncteurs d'oubli cano- niques U D *: D*-Alg - -> C (C,F) *- H* C et ^P U' D . : DA-Alg - -» Ens— (C,F) fEvidemment, la catégorie Proposition 1. Si D*-Alg D * = (£,B^, J : B^ sur la catégorie localement petite est caractérisée comme suit: > D) est une syntaxe d'algèbres £ , alors le diagramme de foncteurs suivant est un produit fibre: DA-Alg Ens- -> F 12 C. Si D Soit A £ une catégorie localement petite. = (£,B,J: B > D) et sont deux syntaxes d'algèbres sur D' A = (£,B',Jf: B' £ , on dit que GA = (D' A ,G,D A ): D' A > DA est un C-homomorphisme si, et seulement si: - B_° est un sous-graphe multiplicatif de - G: D' - le diagramme de foncteurs suivant est commutatif: Si > D GA : D , A -> D') B_ , est un foncteur, > D A est un £-homomorphisme, il induit un fonc- teur d"oubli canonique GA-Alg: DA-Alg (C,F) | > D'A-Alg > (C,F.G°P) qui rend commutatif le diagramme de foncteurs suivant: DA-Alg -> D' -Alg GA-Alg Bien entendu, les syntaxes d'algèbres sur £ (resp. les £-ho- momorphismes) sont les objets (resp. les flèches) d'une catégorie, que l'on note tique: £-Synt , et l'on dispose d'un foncteur canonique, dit séman- 13 H U_ : (£-Synt)Nop DA (où CaT > CaT/£ > (UD*: D A - A l g - — * £ ) * désigne la catégorie des catégories localement petites). D. - Soit £ une catégorie localement petite. Si U: A > £ est un foncteur où A est une catégorie localement petite, on lui associe la syntaxe d'algèbres D(U) A = (£,B(U),J(U): B(U) > D(U)) sur £ , définie comme suit (voir aussi (F.O.S.A.) et (A.O.F.S.)): - B(U) = £ , - D(U) est la catégorie image pleine (voir (A.O.F.S.)) du foncteur £ > (EnsA)op C \ > Homc(C,U(-)) , - J(U) est le foncteur, associé, défini comme suit J(U): B(U) = £ C I Nous dirons que D(U) A > D(U) > (C,Homc(C,U(-)) est la syntaxe complète d'algèbres engendrée par U . Plus particulièrement,si D A est une syntaxe d'algèbres sur £ , on note DA = £(UDA>)A et l'on dit aussi que c'est la syntaxe complète d'algèbres engendrée par DA En tout état de cause, on dispose donc d'un foncteur, dit syntaxe, D(-) A : CaT/£ U i > (£-Synt)°P -> D(U) A Clairement, on a: Proposition 2, Si £ est une catégorie localement petite, lefoncteur syntaxe D(-) A :CaT/C > (£-Synt) op est adjoint à gauche du foncteur sémantique U_ : (£-Synt) op > CaT/C . 14 On en déduit que, pour toute syntaxe d'algèbres on dispose d'un DA , sur £ , C-homomorphisme (co-unité de la co-monade associée à l'adjonction de la proposition 2 - voir aussi (T.A.E.P.) ): S* ! E* > £* tel que G D '(d: D - > D')l où > Hom„(C,Un*(-)) : DA-Alg n.: Hom-CCSU-^C-)) > Ens est la transformation naturelle telle que: - pour toute DA-algèbre (C,F) , on a nd(C,F) = F(d) . De même, pour tout foncteur U: A > £ , où A est une catégorie localement petite, on dispose d'un foncteur de comparaison: > D(U)A-Alg K(U): A > (U(A), evA: D(U)°P A i > Ens) tel que: evA: D(U)°P > Ens (C,Homc(C,U(-)) H--*> Homc(C,U(A)) , rendant commutatif le diagramme de foncteurs suivant: A — > D(U)A-Alg K(U) U D(U)' (qui définit l'unité de la monade associée à l'adjonction de la proposition 2). Enfin, il est facile d'établir que la monade et la co-monade, associées à l'adjonction de la proposition 2, sont idempotentes. 15 E. Si Soit £ U: A une catégorie localement petite. > £ est un foncteur, où A est une catégorie lo- calement petite, on dit qu'il est algébrique (sur £ ) modulo DA si, et seulement si: - il existe une syntaxe d'algèbres D A ble > £ A -Alg I: A sur £ et un foncteur inversi- rendant commutatif le diagramme de foncteurs suivant : •> D -Alg Il convient de remarquer qu'un même foncteur algébrique sur phes (dans £ U: A modulo deux syntaxes d'algèbres sur > C peut être C non isomor- £-Synt). D A et On dit que deux syntaxes d'algèbres D' A sur C sont C- isovalentes si, et seulement si, l'une des deux conditions équivalentes suivantes est vérifiée: - le foncteur U ^ : DA-Alg - le foncteur U D f *: D'A-Alg >£ est algébrique modulo > £ est algébrique modulo Plus particulièrement, nous dirons qu'un GA: D 1 * > DA est une D' A , DA . £-homomorphisme C-isologie et que D' A est C-isologue à DA si, et seulement si: - le foncteur induit £ A -Alg: DA-Alg > D'A-Alg est inversible. Il convient encore de remarquer que deux syntaxes d'algèbres gues sont évidemment £-isolo- £-isovalentes mais que la réciproque n'est pas vraie. Dans ces conditions, nous avons: 16 Proposition 3. Si C est une catégorie localement petite, alors : DA sur £ , le C-homomorphisme ca- est une C-isologie induisant un foncteur - pour toute syntaxe d'algèbres nonique G * :D A A > D G *-Alg: DA-Alg > DA-Alg K(U D *): DA-Alg > DA-Alg , inverse du foncteur de comparaison DA et - deux syntaxes d'algèbres D'A sur £ sont C-isovalentes si, et seulement si, elles engendrent deux syntaxes complètes d'algèbres DA et D'A qui sont C-isomorphes (i. e. isomorphes dans la catégorie £-Synt ) , - deux syntaxes d'algèbres sur £ ment si, elles sont sont C-isovalentes si, et seule- C-isologues à une même troisième. De même, nous avons: Proposition 4. £i U: A > £ est un foncteur entre deux catégories localement petites, alors: - le foncteur U est algébrique sur £ si, et seulement si, il est algébrique modulo la syntaxe complète d'algèbres £(U) A sur £ qu'il engendre, - le foncteur U est algébrique sur £ foncteur de comparaison - le foncteur sur £ > £(U)A-Alg K(U): A D(U) A le foncteur U est inversible, est algébrique modulo une syntaxe d'algèbres si_, et seulement si, DA est d'algèbres - U si, et seulemenent si, le engendrée par C-isologue à la syntaxe complète U , est algébrique modulo une syntaxe d'algèbres sur £ s_i, et seulement si, les syntaxes complètes d'algèbres et £* sur £ , respectivement engendrées par U isomorphes. £A £A D(U)A elt DA , sont £- 17 2. Algébricité et monadicité. A. Si Soit £ une catégorie localement petite. IT = (T,u,m) est une monade sur £ , nous lui associons les deux diagrammes commutatifs de foncteurs suivants: ou: - ir £" (resp. Kleisli) de - H V £ ) est la catégorie d' Eilenberg-Moore (resp. de IT , (resp. V ) est adjoint à gauche de cette adjonction induit la monade U IT (resp. U -JJ. ) et IT , (voir (C.F.W.M.)). De même, si U: A > £ est un foncteur, où A gorie localement petite, admettant un adjoint à gauche cette adjonction induit une monade IT = (U.V,u,m) est une catéV: £ et l'on dispose des deux diagrammes commutatifs de foncteurs suivants: où K est le foncteur de comparaison (voir (C.F.W.M.)). On dit, alors, que U est monadique sur C > A , si, et seulement si: 18 ir - le foncteur de comparaison K: A > C est inversible. B. - Soit IT = (T,u,m) une monade sur la catégorie localement petite C • Notons : " 2.1 - £ • - D^ " J la catégorie image pleine de V JT: — ^ — 7T le :£ >£ , foncteur associé. > Alors, DJJ.* = (£*2.ir'JTrs *LTT £ T F ) est * évidemment, une syntaxe d'algèbres sur £ , dite canoniquement associée à la monade ]T. De même, notons: - £' le sous-graphe multiplicatif de £ ^ flèches suivantes: + ((^VJJXC): V^CC) c: C > C» de C , + C contenant les seules > V ^ C O . C ) , pour toute flèche (T(C), mci V Œ (T(C)) > V E (C),C) , pour tout objet de £ (où nu est l'unique flèche de £ _ telle que U E C \ ) ' U T X C ) = Id T(C) >• 2 — — + (T (C),mc.mr. v,C) , pour tout objet C de £ , + (T(C)fm .V (c) f C f ) , pour toute flèche de £ , c: C > C et tel que: + si d et d' sont deux flèches de D' (donc aussi de D f f ), composables dans D _ , dont le composé d'.d appartient à D' , alors elles sont également composables dans D 1 (et leur composé est, nécessairement, d'.d ), " J i r s - i — > -i la restriction de J j r ijr > £^ > 19 - G : D' Alors, > D le foncteur injection canonique. D' A = (£,B_' ,J' : B/ > D') est, évidemment, une syn- taxe d'algèbres sur £ , dite naturellement associée à la monade et G ]r A = ( E ^ f G j ^ D ^ " ) : D ^ * est u n * £ff" IT, C-homomorphisme. Dans ces conditions, il est facile de vérifier que (voir (T.A.E.P.)): Proposition 5. Si^ IT est une monade sur la catégorie localement petite £ , alors: ir - le foncteur U ir :£ > £ est algébrique sur £ , modulo la syntaxe d*algèbres £ - ^ canoniquement associée à IT , H IT - le foncteur U : £ > £ est algébrique sur £ , modulo la , A syntaxe d'algèbres £ 7r naturellement associée à IT , - le C-homomorphisme G-,A : £' A > Ë T T * e s t u n e C-isologie, par les syntaxes complètes d'algèbres sur £ , respectivement engendrées U , D' A C. - Soit Si £ canonique A e£ D _ A £ , sont C-isomorphes et C-isomorphes à D™*. une catégorie localement petite. est une syntaxe d'algèbres sur £ , le foncteur d'oubli U A : DA-Alg > £ n'admet pas, en général, d'adjoint à gauche: c'est là son seul défaut de monadicité (!) car on a (voir (T.A.E.P.)): Proposition 6. Si_ £ A est une syntaxe d'algèbres sur la catégorie lo- calement petite £ , alors le foncteur u n* : DA-Alg • > £ crée les conoyaux absolus (i. e. il vérifie le critère de Beck - voir par exemple (C.F.W.M.)). Preuve. On sait que le diagramme commutatif de foncteurs suivant est un produit fibre: DA-Alg Ens- 20 De plus: - H commute aux conoyaux absolus (puisqu'ils sont absolus!), J° P - Ens commute aux limites inductives petites (puisqu'elles se D°P B°P calculent point par point, tant dans Ens— que dans Ens— ) mais, de plus, il les crée (puisque On conclut facilement. J est bijectif sur les objets). Fin de la preuve. De la proposition 6 précédente, résulte immédiatement que: Proposition 7. DA £i localement petite £ est une ,syntaxe d'algèbres sur la catégorie et si le foncteur IL.* : £ A -Alg met un adjoint à gauche, alors il est monadique sur > £ ad- £ . Nous fournissons à la proposition 20 (Part. II, §1, E.) une condition suffisante pour qu'un foncteur D. - U-* admette un adjoint à gauche. Des propositions 5 et 7 précédentes, nous déduisons évi- demment que : Proposition 8. Si U: A > £ est un foncteur entre deux catégo- ries localement petites et admettant un adjoint à gauche, alors il est monadique sur £ si, et seulement si, il est algébrique sur £ . 21 3. Sortes et espèces d'algébricité. A. - Soit £ une catégorie localement petite et £' une sous-catégorie pleine de £ . On dit qu'une syntaxe d'algèbres sur £ - £ est de sorte £' DA = (£,!B,J: B_ > D) si, et seulement si: est un sous-graphe multiplicatif de £' • On note, alors, (£,£')-Sort la sous-catégorie pleine de £-Synt dont les objets sont ces syntaxes d'algèbres de sorte £' De même, on dit qu'un foncteur U: A > £ , où sur £. A est une catégorie localement petite, est algébrique de sorte £' £ si, et seulement si: - U est algébrique sur £ te £' sur modulo une syntaxe d'algèbres de sor- sur £ . B. - Soit £ une catégorie localement petite et £' une sous-catégorie pleine de £ . Si U: A > £ est un foncteur, où localement petite, on note - B^OJ) = c» - sur £ D^,(U) est la sous-catégorie pleine de (C,Hom (C,U(-))) , où J t (U): B^0(U) teur J(U): B(U) est un objet quelconque de C , >D(U) . est la syntaxe complète d'algèbres de sor- engendrée par U . En particulier, si sons C D(U) dont les objets ^- > D> f(U) est le foncteur restriction du fonc- Nous dirons que £ r t (U) A te £' telle que: , *—v» sont les est une catégorie D ^ O O " = (£#^,(11),:^,(U) : ^,(U) — > D ^ O O ) la syntaxe d°algèbres de sorte £' - A DA ^PQ A = 2c»^UnA^A d'algèbres de sorte C est une syntaxe d'algèbres sur £ , nous poet 1 , o n dit q u e c sur C ' e s t la syntaxe complète engendrée par DA 22 En tout état de cause, nous disposons d'un foncteur (encore) appelé syntaxe (de sorte £'): Dpç(-)A C. - Soit £ : CaT/C > (C,C')-Sort . une catégorie localement petite et £' sous-catégorie pleine de Si U: A >£ une £ . est un foncteur, où localement petite, on dit qu'il est A est une catégorie C-localement petit si, et seulement si: la catégorie (qu'il engendre) D^,(U) ment petite. est locale- "" On note alors CaT/(£,£') la sous-catégorie pleine de dont les objets sont ces foncteurs CaT/£ £•-localement petits. En particulier, on dit qu'une syntaxe d'algèbres DA sur £ est >£ est £'- C-localement petite si, et seulement si: le foncteur d'oubli canonique localement petit. Notons U *: £ A -Alg % "" i': £ ' >£ le foncteur injection canonique, a- lors il est trivial de constater que: Proposition 9. Si^ £ est une catégorie localement petite, si en est une sous-catégorie pleine et si teur, où A > £ U: A est un fonc- est une catégorie localement petite, admettant un adjoint à gauche, alors En particulier, si DA U ment petite sur £ . D. - £ Soit £A A U *: D -Alg >£ £ admet un est une syntaxe d'algèbres une catégorie localement petite et sous-catégorie pleine de i'- C'-localement petit. est une syntaxe d'algèbres sur foncteur d'oubli canonique joint à gauche, alors est un foncteur £' et si le i'-ad- C'-locale- £' une £ . On dit qu'une syntaxe d'algèbres DA sur C est d'espèce C 23 si, et seulement si: - D A est de sorte - D* est £' , £'-localement petite. On note alors (£,£')-Esp la sous-catégorie pleine de dont les objets sont ces syntaxes d'algèbres d'espèce De même, on dit qu'un foncteur U: A (£,£')-Sort £' sur A est une > £ , où catégorie localement petite, est algébrique d'espèce £' £ • si, et seulement si: - U est algébrique sur ce £' £ modulo une syntaxe d'algèbres d'espè- sur £ . E. - Soit £ une catégorie localement petite et sous-catégorie pleine de £' une £ • Clairement, on a: Proposition 10. Si^ £ C' est une catégorie localement petite et si en est une sous-catégorie pleine, alors le foncteur syntaxe de sorte (resp. d'espèce) £' : > ((£,£')-Sort)°P I^.C-r: CaT/£ U (resp. i > 2c' ( " ) A | s C a T / ( £ ' £ 9 ) ^.(u)" >((£,£')-Esp)° P > 2c' (U) * U « ) est adjoint à gauche du foncteur (restriction du foncteur) semantique: ((£,£')-Sort)°P DA (resp. U n * *> CaT/£ > : ((£,£')-Esp)°P DA • UT > CaT/(£,£') > UD. On en déduit que, pour toute syntaxe d'algèbres (resp. d'espèce) C sur C , on dispose d'un ). DA de sorte £-homomorphisme (co- 24 unité de la co-monade associée à l'adjonction de la proposition 10): Wi"—"Se*' restriction de A G : DA > D* . De même, pour tout foncteur (en particulier, pour tout foncteur localement petit) U: A > £ , où A £'- est une catégorie locale- ment petite, on dispose d'un foncteur de comparaison: >D cf (U) A -Alg K C ,(U): A op > ( U ( A ) ' e v C ',A S 2c' ( U )N A | (où, pour tout objet A de A , ev , — du foncteur *Ens) est le foncteur restriction U ,A ev. ) rendant commutatif le diagramme de foncteurs sui- vant: -*> D - . o j r - A i g K cf (U) (qui définit l'unité de la monade associée à l'adjonction de la proposition 10). On en déduit facilement que: Proposition 11. £i C est une catégorie localement petite et si £' en est une sous-catégorie pleine et dense, alors : - pour toute syntaxe d'algèbres C , le C-homomorphisme - — — — — — — — — — — —— induisant un foncteur Gnq A DA de sorte (resp. d'espèce) £' :D Q, pD A — est une C-isologie —H> ——————— — > D^ G 9 n*-Alg : D^^-Alg du foncteur de comparaison K Ç (U D *): DA-Alg - deux syntaxes d'algèbres DA £' sur £ sont et D'A sur A > DA-Alg —————-^ inverse > D-^-Alg , de sorte (tesp. d'espèce) C-isovalentes si, et seulement si, elles engen- 25 drent deux syntaxes complètes d'algèbres (resp. d'espèee) £' - sur £ qui sont ÎL,* et DI, A de sorte C-isomorphes, deux syntaxes d'algèbres de sorte (resp. d'espèce) £' sont C-isovalentes si, et seulement si, elles sont sur £ C-isologues à une même troisième syntaxe complète d'algèbres de sorte (resp. d' espèce) £' sur £ . De même, nous avons: Proposition 12. Si^ £ est une catégorie localement petite, si en est une sous-catégorie pleine et si teur (resp. un foncteur U: A > £ C'-localement petit), où A £' est un foncest une caté- gorie localement petite, alors : - le foncteur U est algébrique de sorte (resp. d'espèce) £ si, et seulement si, il est algébrique sur complète d'algèbres £^t(U) qu'il engendre, "" sur le foncteur £ C sur est algébrique de sorte (resp. d'espèce) C > £ CÇ (U) A -Alg le foncteur £ U si, et seulement si, £^Ç(U)A drée par ~~ D A de sorte (resp. d'espèce) U , le foncteur U D A est £ £C0(U)A sur C C-isologue à la syntaxe de sorte (resp. d'espèce) £' est algébrique de sorte (resp. d'espèce) engen- £' D A de sorte (resp. d'espèce) £ $ modulo une syntaxe d'algèbres sur C est inversible, est algébrique de sorte (resp. d'espèce) C complète d'algèbres - modulo la syntaxe de sorte (resp. d'espèce) £ 9 modulo la syntaxe d'algèbres sur C sur sii, et seulement si, le foncteur de comparaison K C ,(U): A - U A C sur C si^, et seulement si, les syntaxes complètes d'algèbres et D^,* de sorte (resp. d'espèce) drées respectivement par U et D A , sont £' sur £ , engen- C-isomorphes. Evidemment, ces deux propositions 11 et 12 signifient que, lorsque £' est une sous-catégorie pleine et dense de £ , les monades et co- monades associées aux adjonctions de la proposition 10, sont idempotentes. 26 4. Algébricité d'espèce C et i'-algébricité (au sens de Diers). A. - Soit £ une catégorie localement petite et sous-catégorie pleine et dense de £ . On note £' une i': £' > £ le foncteur injection canonique. TE = (E,e: £'° P On rappelle (voir (F.D.C.A.)) que est une - £ - e: > E) i'-théorie si, et seulement si: est une catégorie localement petite, c .o P _ La catégorie E est un foncteur bijectif sur les objets. C TE * des ]E-algèbres est alors définie par le produit fibre de foncteurs suivant: „TE .op EnsAinsi, si JE = (E,e) est une i'-théorie, elle s'identifie E o p A = (C,C',e°P) , de sorsur £ , particulière. De plus, la catégorie £ TE des te op. ]E-algèbres est canoniquement isomorphe à la catégorie £ HA -Alg à la syntaxe (Complète) d'algèbres des E p A-algèbres. B. - Soit £ une catégorie localement petite et sous-catégorie pleine et dense de £ . On note £' une i': £' > £ le foncteur injection canonique. On dit ( v o i r (F.D.C.A.)) qu'une i ' - t h é o r i e IE = ( E , e ) gébrique s i , et seulement s i : - e ° P : C« ?op admet un i'-adjoint à droite. est al- 27 Il est facile de vérifier que (voir aussi Proposition 13. £i £B £ (T.A.E.P.) et (F.D.C.A.)): est une catégorie localement petite, si est une sous-catégorie pleine et dense de £ f > £ gne par i : £ ' et si on dési- le foncteur injection canonique, alors TE = (E,e: £ ' o p > E ) est algébrique si, et TE TE seulement si, le foncteur U :£ > C admet un i'-adTE TF — — — — —joint à gauche V : £ ' > C une i'-théorie En conséquence, en vertu de la proposition 9, une i'-théorie algébrique E op A JE s'identifie à une syntaxe (complète) d'algèbres , d'espèce C C. - Soit £ sur C , particulière. une catégorie localement petite et sous-catégorie pleine et dense de £ . On note C i': £' une > £ le foncteur injection canonique. > £ est un foncteur, où A petite, admettant un i'-adjoint à gauche V: £• > A , on ]E(U) = (E(U),e(U): £'° P > E(U)) Si U: A note (voir (F.D.C.A.)) la est localement i'-théorie algébrique engendrée par U , i. e . la i'-théo- rie (dont il est facile de vérifier qu'elle est algébrique) t e l le que: - £(U) (et est la catégorie image pleine de V : C e(U)°P: £ ' > E(U)°P > A est le foncteur qui s'en déduit). Alors, on dit (voir (F.D.C.A.)) que U est i'-algébrique s i , et seulement si: - il existe un foncteur inversible I:.A > C commutatif le diagramme de foncteurs suivant: A > £E E(U JE ) rendant commutatif le diagramme de foncteurs suivant: > EOJ^) E e(U) TE (et, bien entendu, le foncteur gébrique). U TE :£ > £ est i'-al- Clairement, on a: Proposition 14. Si £ est une catégorie localement petite, si £' en est une sous-catégorie pleine et dense, si i•: £' > £ désigne le foncteur injection canonique et si U: A > £ est un foncteur, où A est une catégorie localement petite, admet- tant un i*-adjoint à gauche, alors : - la syntaxe d*algèbres £(U) A d'espèce £' sur £ , canoniquement associée à la i'-théorie algébrique E(U), engendrée par U , est C-isomorphe à la syntaxe complète d'algèbres D(U) A d'espèce £' sur £ , engendrée par U , - si le foncteur ce £' sur £ . En particulier, si - U est i'-algébrique, il est algébrique d'espè- TE est une les syntaxes d'algèbres Eop A i'-théorie algébrique, alors : et £(11^)°13 A sur £ , canoniquement associées à la théorie E(U TE ) respectivement, sont P complète d'algèbres £ ° r 9 E°P * , A d'espèce i'-théorie d'espèce £• TE et à la i'- C-isomorphes à la syntaxe £' sur £ , engendrée par 29 - le foncteur d*oubli canonique Cf que d'espèce D. - Soit sur £ £• est algébri- sur £' une £ . £ , si i': £' DA foncteur injection canonique et si C -> C : £ une catégorie localement petite et est dense dans bres d'espèce TE TE C . sous-catégorie pleine de Si U > £ désigne le est une syntaxe d'algè- C , le foncteur U D* S £A~A16 n'admet pas, en général, de i'-adjoint à gauche: c'est là son seul défaut de " i'-algébricité " Proposition 15. £' Si^ £ ! En effet, nous avons: est une catégorie localement petite, si en est une sous-catégorie pleine d'algèbres de sorte nonique A U *: £ -Alg absolues, où i': C' C et si DA est une syntaxe sur C , alors le foncteur d'oubli ca- > £ crée les limites inductives -> £ désigne le foncteur injection ca- i •- nonique (i. e. il vérifie le "critère de Beck généralisé" du Théorème 5.1. de (F.D.C.A.)). Preuve. On sait que le diagramme commutatif de foncteurs sui- vant est un produit fibre: DA-Alg De plus : - H commute aux limites inductives - Jop Ens i'-absolues (par définition), commute aux limites inductives petites (puisqu'elles se D op B op calculent point par point, tant dans mais, de plus, il les crée (puisque Ens— J On conclut facilement. Fin de la preuve. que dans Ens— ) est bijectif sur les objets). 30 De la proposition 15 précédente, nous déduisons immédiatement que: Proposition 16. £' £i £ est une catégorie localement petite, si en est une sous-catégorie pleine et dense, si désigne le foncteur injection canonique, si d'algèbres d'espèce C A sur i•: £• — > £ est une syntaxe et si le foncteur d'oubli cano- nique U A : D -Alg il est i?'*-algébrique (au sens de Diers). E. - > £ C D A admet un i'-adjoint à gauche, alors Des propositions 14 et 16 qui précèdent, nous conclu- ons que: Proposition 17. £i £' £ est une catégorie localement petite, si en est une sous-catégorie pleine et dense, si désigne le foncteur injection canonique et si un foncteur, où tant un A U: A i': £' > £ > £ est est une catégorie localement petite, admet- iw-adjoint à gauche, alors il est i'-algébrique (au sens de Diers) si, et seulement si, il est algébrique d'espèce C sur C . PARTIE II : RANG D'ALGEBRICITE 32 1. g-algébricité. A. - Soit Si a C B. - une catégorie localement petite. est un ordinal régulier, on note rie pleine de bles de £ £ a-présenta- (voir (L. P. L. G. )). Il est facile de vérifier que: a est un ordinal régulier, si tégorie localement petite et si C la sous-catégo- dont les objets sont tous les objets Proposition 18. £i sorte C sur £A est une ca- est une syntaxe d'algèbres de U * : DA-Alg £ , alors le foncteur les limites inductives (petites) £ > £ crée q-filtrantes. De même, on a: Proposition 19. Si_ a est un ordinal régulier, si tégorie localement petite q-filtrantes et si te sur nique U * : DA-Alg C. - Soit On dit que - £ £A est une syntaxe d'algèbres de sor- £ , alors la catégorie mites inductives petites possède toutes les li- y commute. D A = (£,£,J: B_ £ £ A -Alg q-filtrantes et le foncteur d'oubli cano- > £ A est une ca- possédant toutes les limites inductives petites C £ > D) une syntaxe d'algèbres. est petite si, et seulement si: est un graphe multiplicatif petit. D. - Soit £ une catégorie localement petite et q un ordi- nal régulier. On dit qu'une syntaxe d'algèbres DA sur sur £ • si, et seulement si: - £A est petite, - £A est une syntaxe de sorte C £ est de rang q 33 On dit qu'un foncteur localement petite, est - U q U: A > £ , où A est une catégorie q-algébrique si, et seulement si: est algébrique sur £ modulo une syntaxe d'algèbres de rang sur £ • Ainsi, en vertu des propositions 18 et 19 précédentes, un foncteur q-algébrique sur tes et, si £ C crée les limites inductives petites q-filtran- possède toutes ces limites, il y commute. E. - Montrons, maintenant, que: Proposition 20. S£ q est un ordinal régulier, si £ est une caté- gorie localement petite possédant toutes les limites inductives petiDA tes et si est une syntaxe d'algèbres de rang q A le foncteur U *: D -Alg Preuve. Soit C On note > £ sur £ , alors admet un adjoint à gauche. un objet de £ • [J>C] le graphe multiplicatif (évidemment petit) tel que: - QjfC]] contient le graphe multiplicatif à pour toute flèche d: J(B) J(B) , et,pour toute flèche £/C , > J(B') de D , n'appartenant pas e 1 : B' > C de £ , (d,e') est objet de [J,C] , - a un objet supplémentaire (i. e. différent des précédents) [J,C] noté - 1, pour tout objet B ((B,e),l): (B,e) - > C et et toute flèche > 1 est flèche de pour toute flèche e: B de £ b: B e': B' > B' > C de £ , et toutes flèches telles que ((B',e'),l).((B ,e),b,(B',e')) est défini dans ((B,e),l) . On dispose alors d'un foncteur canonique: [[J,C]]: [J,C] > C [J,C] , dé £ de £ e: B >£ e'.b = e , alors [J,C] et vaut 34 dont la restriction à B/C B/C est le foncteur: > £ > £ canonique injection et tel que: - Œ J >c]](i) = c , - pour tout objet B de £ et toute flèche on a: [[j,C]]((B,e),l) = e , - pour toute flèche d: J(B) à J ( £ ) , et pour toute flèche [[j,C]](d,e') = B . > J(B') e ' : B' e: B > C de £ de £ , n'appartenant pas > C de C , on a: Comme £ possède toutes les limites inductives petites, le foncteur Q_J,CJJ: LJfcJ > £ admet donc un cône limite inductive (s;« Œ J , C ] ] ( Z ) > S(C))z€[j>c] . Ainsi, on dispose: - de la flèche s(C) = s'J :([[j,C]](l) = C) - pour toute flèche d: J(B) à J(£) , et pour toute flèche > S(C) de £ , > J(B') de D , n'appartenant pas e': B' > C de £ , de la flèche: e ' , \ d = S?d e') : (Œ J ^]](d,e') = B) > S(C) de C S(C) ^a'e J - pour toute flèche b: B > B' de B et toute flèche e': B'—> C de £ , de la flèche: " W ) ^ ^ = S ( C ) * e '- b = S(B,e'.b) = s(B',e')-^J^]((B,e'.b),b,(B',e')) de source B et de but S(C) , dans C . Clairement, l'application, ainsi définie, qui à tout objet associe S(C) , se prolonge canoniquement en un foncteur: S: £ et la famille naturelle: C de C >£ (s(c))Cç0bC d é f i n i t » b i e n entendu, une transformation "" s : Idc > S :C >£ 35 Dans ces conditions, si - CQ = C et " c - pour toute flèche est un objet de c > o > C C l ' d: J ( B ) de C , e' . > J(B') de D et toute flèche = e• . d :B > C. . d 0,1 Alors, si 1< p C et d'une "composition p a r t i e l l e " d: J(B) 1 S(C) et si les conditions suivantes sont vérifiées: c de £ , on pose: Cx = S(C) , 0,l = s ( C ) s e' : B' C > J(B') de p' qui, à toute f l è c h e D et à toute f l è c h e e ' : B' > Cûfl — associe la flèche e' . d : B > Cfi t 3 111 < prt < p • < p C c)pour tous £ , l e diagramme de e ' : B' e' . de D > Cûlf de P ,fcJ e': B' > Conf e)pour tous et p"» < p« < 3 • < 3 , d°: J ( B ' ) flèche p...fP.. e": B" b: B > B' de , pour toute flèche de P P fP suivant commute: C , on a: P — J ( b ) = cfilf p i . e ' . b 3"' < 3 " < 3' < 3 , et toute flèche £ , pour toute f l è c h e P",p' d)pour tous C , P»',P' 1 < p" < p' < p et toute f l è c h e de C , — P j3",|3' b)pour tous de p d: J ( B ) — * > J ( B ' ) C , on a: — P fP pour t o u t e s f l è c h e s > J(B") de £ , composables dans > Cgttt de £ , on a: p..fp. d: J(B)—> J ( B ' ) £ , et pour toute 36 (c B"' B"* e,,) ,p P (d''d) = (e" ' . d') 3,,,,P" 3",3» . d , 3",g' on note: s(cp) v >cp+1 la flèche (inductivement) universelle de que £A est petite et £ £ (et qui existe bien puis- possède toutes les limites inductives peti- tes) telle que: - pour tout te flèche P' < p , toute flèche de £ uR.s(Cfi).(e' . d) = up.((cfif fi.e') . d) P P P P 3 P'.P ' S(Cp) , e': B' > Cg t - pour tout P' < p d': J(B') > J(B") e": B" > cpt de d: J(B) de et tou- £ , on a: , toutes flèches de > J(B') d: J(B) > J(B') £ , composables dans et £ , et toute flèche £ , on a: u B .((e" . d') . d) = uft.((cpt p P',p S(Cp) B , < 8 , c„.„ =u p p .e") 'p . d), s(c p ) et l°on pose: - pour tout pour toute flèche e *: B ' > Cfi, , d: J(B) e* q' < q les conditions D et et toute flèche p < q' a) à e) précédentes sont vérifiées, on note: = 2 ¾ (c p % p:C B t -^ B ) 3 f < 3 < a , p < q', on a donc: - la co-projection associée cfi : CQ > C f p q P 9 oc che d: J(B) £ , la flèche: de > r est un ordinal limite et si, pour tout V et, pour tout > J(B') • C . d = ufi.((cfi, _.e') . d) . P P P',3+1 'P S(C a ) P P De même, si .sCC ).c > J(B') de £ p,a' et toute flèche p+1 a ' p,p+i et, pour toute flè- e ' : B' > CR de 37 Ainsi, si d: J ( B ) e ' : B' > C > J(B') e s t une f l è c h e de e s t une f l è c h e de a D et si C , i l e x i s t e (puisque - indépendant de la représentation est A un o b j e t q - p r é s e n t a b l e de £ - l a s y n t a x e au moins un P < q e t une f l è c h e e ' : B' P que: c Q . e ' = e ' . A l o r s , on p o s e : P>ot p - e' . d = c . (e' . d) , P F P+1'a p,P+l et il n'est pas difficile de vérifier que B' DA é t a n t de r a n g q ) > CQ de C t e l l e p — e'. d , ainsi défini, est F e' choisie. Il en résulte e' de P immédiatement que (C ,F) est bien une DA-algèbre, librement engendrée par £ (relativement au foncteur U_A ) . Fin de la preuve. En vertu de cette proposition 20, nous pouvons donc énoncer: Proposition 21. £i q est un ordinal régulier, si £ est une caté- gorie localement petite possédant toutes les limites inductives petites et si U: A > £ admet un adjoint à gauche. est un foncteur q-algébrique, alors il 38 2. q-algébricité et A. - Soit £ q-monadicité. une catégorie localement petite et une monade sur la catégorie rang - C . Si q est un ordinal régulier, on q si, et seulement si: le foncteur T: £ >£ F = (T,u,m) rappelle que IT est de commute aux limites inductives (petites) q-filtrantes. Il est facile de vérifier que: Proposition 22. Si q est un ordinal régulier, si rie localement petite et si IT est une catégo- est une monade de rang alors le foncteur d'oubli canonique tes inductives (petites) £ U :£ q sur C , > C crée les limi- C est une caté- q-filtrantes. De même, on a: Proposition 23. Si q est un ordinal régulier, si gorie localement petite possédant toutes les limites inductives petites q-filtrantes et si IT est une monade sur £ , alors les trois condi- tions suivantes sont équivalentes: TT TT (i) le foncteur U : £ petites q-filtrantes, (ii) la monade IT (iii) la catégorie > £ est de rang £ q , possède toutes les limites inductives petites q-filtrantes et le foncteur B. - commute aux limites inductives U1: C^ > C les crée. Soit £ une catégorie localement petite un foncteur, où A est une catégorie localement petite, admettant un adjoint à gauche V: £ Si q U: A > C > A . est un ordinal régulier, on dit que si, et seulement si: et U est q-monadique 39 - U est monadique, la monade che de H = (U.V,u,m) , associée à l'adjonction de V à gau- U , est de rang q . Clairement, on a, en vertu des propositions 7 et 19: Proposition 24. £i q est un ordinal régulier, si £ est une catégorie localement petite possédant toutes les limites inductives > £ petites q-filtrantes et si U: A est un foncteur, où A est une catégorie localement petite, q-algébrique sur £ tant un adjoint à gauche, alors il est C. - Soit £ q-monadique sur £ • une catégorie localement petite et q nal régulier (rappelons qu'alors on note de £ et admet- C un ordi- la sous-catégorie pleine dont les objets sont les objets q-présentables de £ ). On dit que £ est localement q-générable (modulo C ) si, et seulement si : - £' est une sous-catégorie pleine de tion canonique C > C - £' est petite, - C est dense dans £ , - pour tout objet D. - Soit ment q C et le foncteur injec- est une équivalence, de £, la catégorie C'/C un ordinal régulier et £ q-générable modulo Si C C est q-filtrante. une catégorie locale- . TT = (T,u,m) est une monade .(de rang q ) sur £ , nous notons: " V I T =¾ » - D _ la sous-catégorie pleine de dont les seuls objets sont les conque de C , - J _ :B _ q, E -q, F D™ (voir Part. I, §2, B. ) — Il " G [ | il (C,V (C)) , où C est un objet quel- > D -, le foncteur restriction de J ^ , -a, IT IT 40 - G :D w > D le foncteur injection canonique. q> n ~€tt il —il Dans ces c o n d i t i o n s , i l e s t t r i v i a l de constater que -a* n q, n q, n -q, ir est une syntaxe d'algèbres de rang q G -tx»ii sur £ et que a,ir* ! W—*»v* est un £-homomorphisme. De même, notons: - B' TT la sous-catégorie pleine de C dont les seuls objets ~ (Xf il 2 "" sont les C , T(C) et T (C) , où C est un objet quelconque de C , -a - DJ F l e sous-graphe m u l t i p l i c a t i f p l e i n (pour l e s f l è c h e s et l a compo- "—(X 9 II sition) de £' (voir Part. I, §2,B.) dont les seuls objets sont les images par J' de ceux de B' , n —q, u - J' _, : B f _, > D' ^ le foncteur restriction de J' , q, H -q, H - D' le foncteur injection canonique. J M q , T£ - q , T£ —IT Il est tout aussi facile de constater que -q, H q, H q, T£ -q, H -q, H est une syntaxe d^algèbres (qui n'est pas en général de rang q ) sur £ et que rt A • n' * > D' A a,ir • ^x, ir -ir est un £-homomorphisme. Clairement, nous avons alors: Proposition 25. £i q est un ordinal régulier, si £ est une catégorie localement q-générable et si IT est une monade de rang q sur £ , alors : - les C-homomorphismes G *i D * — des C-isologies, -q» n -cet n sont > D * et G' *i £• *—»• * — ir — q, u. -a> ir —n 41 TT - les syntaxes d'algèbres B. ) sont - — — — U "^ : C ^ — > C — TT - et — D^9(U -ç^ ) A (voir Part. I, §3, C-isomorphes, le foncteur — D * -q,Il le foncteur U est algébrique sur — C ' modulo *, £• ~\L9 U- — TT :£ > £ est q-algébrique sur £ modulo Sx.** * Il en résulte que: Proposition 26. £i q est un ordinal régulier, si rie localement q-générable et si U: A > £ £ est une catégo- est un foncteur, où A est une catégorie localement petite, admettant un adjoint à gauche et q-monadique sur E. - Soit £ , alors il est q q-algébrique sur £ . un ordinal régulier. Il est facile de vérifier que, si £ est une catégorie localement q-générable qui possède toutes les limites inductives petites, alors elle est localement q-présentable et inversement (voir (L. P. L. G. ) et (es. es.)). Des propositions 21, 24 et 26 précédentes résulte donc que: Proposition 27, Si localement a est un ordinal régulier, si q-présentable et si U: A > £ £ est une catégorie est un foncteur, où A est une catégorie localement petite, alors les deux conditions suivantes sont équivalentes : (i) U (ii) U admet un adjoint à gauche et est est q-algébrique sur £ . q-monadique sur £ , 42 3. q-algébricité et A. - Soit q On dit que q-sur-esquissabilité. un ordinal régulier. /£/ = (£,P) est une esquisse de rang q (voir (E.T.S.A.) ) si, et seulement si: - £ est un graphe multiplicatif petit, - P est un ensemble de cônes projectifs de indexés par des catégories Si /£/ £ (dits (UstJURllés) q-petites. est une esquisse de rang R: /£/ — > Ens q , on dit que est une réalisation (ou modèle, ou faisceau) de /£/ si, et seule- ment si: - R: £ > Ens - l'image par R est un foncteur, de tout cône distingué (i. e. de tout élément de est une limite projective de Ens. /S/ Alors, on note Ens — la sous-catégorie pleine de objets sont ces réalisations. s Ens— dont les B. - Soit Si est une catégorie localement petite, on dit qu'elle est £ q-esquissable q P) un ordinal régulier. (modulo /£/ ) si, et seulement si: /S/ - il existe une esquisse /£/ de rang q telle que £ et Ens — soient des catégories équivalentes. Rappelons que (voir (L.P.L.G.) et (C.S.C.S.)): Proposition 28. Si q est un ordinal régulier et si £ est une caté- gorie localement petite, alors les deux conditions suivantes sont équivalentes: (i) £ est une catégorie q-esquissable, (ii) C est une catégorie localement q-présentable. 43 C - Soit q un ordinal régulier. Si /£/ = (£,P) et /S'/ = (£',P') sont deux esquisses de rang q , on dit que /H/: /£•/ > /S/ est un homomorphisme si, et seulement si: - H: £5« > £ est un foncteur, - H(P') est inclus dans P . Un tel homomorphisme induit, évidemment, un foncteur d'oubli canonique: Ens /H /: Ens'*' R I > Ena&' > R.H Rappelons que ("théorème du faisceau associé"): Proposition 29. Si q est un ordinal régulier et si /H/:/S'/ > /S/ est un homomorphisme entre deux esquisses de rang q , alors le foncteur d'oubli canonique Ens/»/: Ens'i' > Ens'* 7 possède un adjoint à gauche et commute aux limites inductives petites q-filtrantes. D. - Soit q Si /£/ et p /H/: /£ / un ordinal régulier. /£'/ sont deux esquisses de rang q , on dit que > /£/ est un sur-homomorphisme si, et seulement si (voir (E.S.T.R.), (E.D.S.A.), (C.S.T.R.) et (S.B.D.S.)): - /H/: /£ r / > /£/ est un homomorphisme, - pour tout cône projectif distingué de base le foncteur: 9 : I I « (s : S > S ) de /S/, "~ > £ > sT il existe un foncteur 0': £ > £• tel que H.9' = 0 (autrement dit: tout cône projectif distingué de /S/ "est à base dans /S'/ " ) , - tout objet de S , qui n'est pas image par H d'un objet de S' , est sommet drun cône projectif distingué de /S/. 44 E. - Soit q un ordinal régulier et C une catégorie locale- A est une catégorie lo- ment q-présentable. Si U: A > £ est un foncteur, où calement petite, nous dirons qu'il est q-sur-esquissable (modulo /H/) si, et seulement si: - U crée les isomorphismes (i. e. : pour tout objet A de flèche inversible inversible a: A c: U(A) > A' > C de A - il existe un sur-homomorphisme £ ~ A et toute de £ , il existe une unique flèche telle que U(a) * c ) , > /£/ , entre esquisses /S/ de rang q , et deux équivalences de catégories A ^ > Ens — et > Ens — /H/:/£'/ rendant commutatif le diagramme de foncteurs suivant: A ^ > Ens'S/ Ens /H / U Ç ^ > Ens'âV Dans ces conditions, on a (voir (E.S.T.R.), (E.D.S.A.) et (C.S.T.R.)): Proposition 30. £i q rie localement A est un ordinal régulier, si q-présentable et si U: A > £ C est une catégo- est un foncteur, où est une catégorie localement petite, alors les trois conditions sui- vantes sont équivalentes: (i) U admet un adjoint à gauche et est q-monadique sur £ , (ii) U est q-algébrique sur £ , (iii) U est q-sur-esquissable. Preuve. La proposition 27 indique déjà que (i) implique (ii) (et lui est même équivalente, ce que nous ignorons délibérément ici!). Supposons que U £* de rang q est q-algébrique sur £ sur £ . Comme £ modulo la syntaxe d'algèbres est localement q-présentable, la 45 sous-catégorie pleine C de - C C , dont les objets sont tous les — £ , contient une s o u s - c a t é g o r i e p l e i n e est une équivalence, est petite, -q - C est dense dans - /£/ = (£,P) est bien un sur-homomorphisme entre esquisses de rang q foncteur U: A > £ est q-esquissable modulo et que le /H/ . La condi- tion (ii) implique donc la condition (iii). Si U: A > £ homomorphisme est un foncteur /H/: /S'/ > /£/ q-sur-esquissable modulo un surentre esquisses de rang q , on dispose d'un diagramme commutatif de foncteurs: £' , 46 * Ens& Ens U /H/ > Ens/i'/ Y et YB Ainsi, U admet un adjoint à gauche, puisqu'il en est ainsi de où sont des équivalences. (d'après la proposition 29). Comme £ 7H/ Ens possède toutes les limites induc- tives petites le cas de le cas de est q-filtrantes (puisqu'il est facile d'établir que c'est /S '/ Ens — ) et comme U commute avec ces limites (puisque c'est /H/ Ens , en vertu de la proposition 29), pour montrer que U q-monadique, il suffit d'établir (d'après la proposition 22) qu'il est monadique. Comme U fit donc de montrer que crée (par hypothèse) les isomorphismes, il suf/H/ crée, à isomorphisme près, les conoyaux Ens absolus. Supposons donc que r,r': R .. . R- 1 l est une paire de flèches de Ens/s«/ — et que le diagramme commutatif de Ens /s/ suivant: rH R X .H -> R 2 .H -» K r'H est un conoyau absolu. Alors, c'est aussi un conoyau absolu (et calculé S' point par point) dans la catégorie de foncteurs Ens— . Si l'on considère le conoyau (calculé point par point) représenté par le diagramme S commutatif de Ens— suivant: •* R 2 -> F il existe, par conséquent, une unique équivalence naturelle g: K — > F.H 47 rendant commutatif le diagramme de Ens— suivant: F.H rH -> V H R^H r'H K Mais, si (Sj.: S /S/ , de base S est I^I€I un c ° n e P r ° J e c t i f distingué dans le foncteur 9: I -> S -> S, I h il existe, par hypothèse, un foncteur 9': I > S• I »tel que ->SÎ H.9'°« = 9 . On a donc, successivement: - F(S) = coker ( = coker R (S) ( lim _> R 2 (s) ) (R (S ) ^ R 2 (Sj) ) ) ICI = (puisque R. et R_ sont des réalisations) coker ( lim (R ,H(S«) l i <« lim ( coker (R^HCSJ ) I€I ^ R2.H(Sp) ) -> ^ R 2 > H ( S p )) I€I (puisque les conoyaux considérés sont absolus) = r-lim I€I (K(S«) ) * = flim (F.H(S')) Par conséquent, F Fin de la preuve. = ^lim (F(S T )) est une réalisation de . /S/ . D'où la conclusion. PARTIE III : ALGEBRES PARTIELLES 49 1. Méta-algèbres. A. - Si D est un graphe multiplicatif, on note multiplicatif subdivision de D , i. e. §D le graphe le graphe multiplicatif tri- vial tel que (voir (C.F.W.M.)): - tout objet D de D est objet de - toute flèche d - si d: D > D' est une flèche de et (d,2): d > D' sont deux flèches de de D Alors, à tout foncteur &F: §D > Ens §D , est objet de F: D° P §D , D , alors (d,l): d > D §D . > Ens , on associe le foncteur tel que: - pour tout objet D de - pour toute flèche d: D D , on a &F(D) = F(D) , > D' , on a &F(d,l) = F(d) et &F(d,2) = I d p ^ . Clairement, l'application qui à tout objet F de Ens— associe 1' §D objet &F de Ens — se prolonge canoniquement en un foncteur: D° P &: Ens- §D > Ens - (la raison de la dualité intervenant ici n'est que de pure commodité). B. - Soit £ une catégorie localement petite et D* une syntaxe d'algèbres sur £ . On dit que (C,p: X > C,G) est une D*-méta-algèbre si, et seulement si , (voir aussi (S.B .D.S. )):• - p: X > C - G: §D > Ens l'application ture de - est une flèche de £ , est un foncteur (et, pour toute flèche d de D , G(d,l) est une loi de composition partielle de la struc- DA-méta-algèbre considérée), pour tout objet D = J(B) de D , on a G(D) = Homc(B,C) , 50 - pour toute flèche d: J(B) > J(B«) de D , on a: D , on a: G(d) = Homc(B',X) , - pour toute flèche d: J(B) > J(B') de G(d,2) = Homc(B',p) , - pour toute flèche b: B > B* de B , on a: G(J(b),l)=Homc(B,p).Homc(b,X) . De même, on dit que homomorphisme de la DA-méta-algèbre gèbre - x: X (.C,p°,G') > X1 > (C,,p,,Gt) est un (c,x): (C,p,G) (C,p,G) vers la D*-méta-al- si, et seulement si: et c: C commutatif le diagramme de > C' C sont deux flèches de £ rendant suivant: X > c P' Ens pour toute flèche d: J(B) > J(B') de D , le diagramme de suivant est commutatif: Hom0(B', X) Homc(B,C) G(d,l) Homc(B',x) , Homc(B ,X') Homc(B,c) G'(d,l) -> Homc(B,C') Dans ces conditions, on note D*-Métalg objets (resp. les flèches) sont ces momorphismes entre la catégorie dont les D*-méta-algèbres (resp. les ho- D*-méta-algèbres). Alors, on dispose des deux foncteurs: 51 Domet^ : D*-Métalg -> C (C,p: X -5> C,G) *- -*• X ((c,x):(C,p,G)-3> (CSpSG*)) H et D A -Métalg Codomet * : -> C (C,p: X -> C,G) »- -> C ((c,x):(C,p,G)-> (C',p',G')) • -^ c ainsi que de la transformation naturelle: TÏ^A :DometD* > Codomet *:D*-Métalg telle que, pour toute - D*-méta-algèbre -> C (C,p,G) , on a: IT D A(C,P,G) = p . De même, on dispose du foncteur injectif: DA-mét: D*-Alg -> DA-Métalg (C,F) h > (C,Idc: C -> C,&F) ((c,c): (C,F)—> (C',F')) I > (c,c) de sorte que le diagramme de foncteurs et transformations naturelles suivant est commutatif: DA-mét A D -Alg -> DA-Métalg Codomet, C. - Montrons que: Proposition 31. £i £ est une catégorie localement petite possédant 52 DA toutes les petites limites inductives et si taxe d'algèbres sur est une petite syn- £ , alors le foncteur Domet *: DA-Métalg > £ admet un adjoint à gauche. Preuve. Comme D A est petite, les considérations et constructions du début de la preuve de la proposition 20, Part. II, §1, B. , dont nous reprenons les notations, s'appliquent encore. On dispose donc d'un foncteur S: £ > £ , construit à l'aide de (calculées dans la catégorie s: Id - si £ ) et d'une transformation naturelle > S . De plus, pour tout objet d: J(B) est une flèche de > J(B') limites inductives C de est une flèche de D C , on sait que: et si c: B' — > C £ , on dispose d'une flèche c . d = G p (d,l)(c) : B c S(C) > S(C) de £ , il est alors facile de vérifier que bien une (S(C), s(C): C — > S(C),G C ) D*-meta-algèbre , librement engendrée par au foncteur Domet A ) . Fin de la preuve. C est (relativement 53 2. Para-algèbres. A. - Soit £ une catégorie localement petite et DA une syn- taxe d'algèbres sur £ . On dit que (C,q: Y DA-para-algèbre si, > H(C),G) est une et seulement si, (voir aussi (S.B.D.S.)): - C est un objet de - op Y: B_ - q: Y > Ens C , est un foncteur, > H(C) = Homr,(-,C), _op L - G: §D plication > Ens est une transformation naturelle, j D est un foncteur (et, pour toute flèche d de D , l'ap- G(d,l) est une loi de composition partielle de la structure de DA-para-algèbre considérée), - pour tout objet D = J(B) de - pour toute flèche d: J(B) — * > J(B') de - pour toute flèche d: J(B) D , on a G(D) = Hom (B,C), D , on a G(d ) = Y(B'), > J(B') de D , on a: G(d,2) = q(B') , - pour toute flèche b: B > B' de B , on a: G(J(b),l) = q(B).Y(b) . De même, on dit que (c,y): (C,q,G) A momorphisme de la D -para-algèbre > (C',q',G') est un bQ- (C,q,G) vers la DA-para-algèbre (C',q',G'; si, et seulement si: - c: C > C est une flèche de £ > - y: Y > Y' est une transformation naturelle, - le diagramme de transformations naturelles suivant est commutatif: Y > Hom£(-,C)( gop q' J Homc(-,c). fiop -> Hom(,(-,C,)| Bop 54 - pour toute flèche Ens -> J(B') d: J(B)- de D , le diagramme de suivant est commutatif: -> Hom c (B,C) Y(B') G(d,l) Hom (B,c) y(B') G'(d,l) -> Hom c (B,C*) Y'(B') Dans ces conditions, on note D*-Paralg objets (resp. les flèches) sont ces momorphismes entre les la catégorie dont les D*-para-algèbres (resp. les ho- D*-para-algèbres). Alors, on dispose des deux foncteurs: CodonLA : D*-Paralg - -> C *- -> C (C,q,G) -> c ((c,y): (C,q,G)—> ( C S q S G * ) ) et op -3> Ens^- Do:IÏL* : DA-Paralg (C,q: Y - * H(C),G) » > ((c,y): (C,q,G)-*> (C',q',G'))l Y > (y: Y Y') , ainsi que de la transformation naturelle: V l Do telle que, pour toute - op v -> H. Codons A : D - P a r a l g DA-para-algèbre Ens^ (C,q,G) , on a: V D A(C f q,G) = q . De même, on dispose du foncteur injectif: D A -para: DA-Métalg (C,p: X - > C,G) • -> DA-Paralg > (C, H(p): H(X)~> H(C),G) ((c,x): (C,p,G)-> (C' f p f ,G')) H-> (c,H(x)) , de sorte que le diagramme de foncteurs et transformations naturelles suivant est commutatif: 55 -> DA-Paralg DA-Métalg D -para Domet- Nous poserons, enfin: -> DA-Paralg. -S> DA-Métalg DA-paramét: DA-Alg D -para D -met B. - Clairement, nous avons: Proposition 32. Si £ est une catégorie localement petite et si DA est une syntaxe d'algèbres sur £ , alors le foncteur Codons*: DA-Paralg > £ admet un adjoint à gauche. Preuve. En effet, il est facile de vérifier que, si C est un objet de £ , alors (C,qc ^:Y. > H(C), G c ^ ) est bien une DA-paraalgèbre, librement engendrée par C (relativement à Codon^* ), lors- que: - op Y 0 " qC,0îY0 résulte, - > Ens •• i est le foncteur constant sur 0 , -> H(C) est l'unique transformation naturelle qui en -> Ens c» • §£ G est le foncteur tel que: + pour toute flèche d de D , on a G c ^ (d) = 0 + pour toute flèche b: B G C 0 (J^)'1) s * G C 0 (J(b)'2) s * Fin de la preuve» > B' de B , on as Hom c (B,C) et > Homc(B',C) . 56 On en déduit, évidemment, que le foncteur CodometD^ : DA-Métalg > £ admet un (D*-para)-adjoint à gauche. Cependant, en général, Codomet * n'admet pas d'adjoint à gauche (à moins, bien sûr, que le foncteur Y^ ne soit de la forme H(C^) , pour un certain objet Cfl de £ ). C. - Montrons, maintenant, que: Proposition 33. Si^ £ est une catégorie localement petite possédant toutes les limites inductives petites et si D* est une petite syntaxe d'algèbres sur £ , alors le foncteur Dom DA : Rop £ -Paralg > Ens^- admet un adjoint à gauche Bop LDoiiij^ : Ens- > DA-Paralg . De plus, jsi £ est dense dans £ , le diagramme de foncteurs suivant est commutatif: DA-Métalg A > DA-Paralg DA-para LDomet * LDom^A Rop -> EnsS- (où LDometD* est un adjoint à gauche de Domet *: DA-Métalg dont l'existence est assurée par la proposition""31). > C , Preuve. Soit Y: B ° p > Ens un foncteur. Nous lui associons le graphe multiplicatif (de ses hypermorphismes) Hyp(Y) défini comme suit : - ses objets sont les ment de Y(B) , (B,e) , où B est objet de B et e est élé- 57 - ses flèches sont les (e,b,e'): (B,e) > (B',e') , où b: B — > B' est flèche de ,B , e est élément de Y(B) , e' est élément de Y(B') et Y(b)(e#) = e , - pour toutes flèches (e,b,e«): (B,e) > (B',ef) et (e',b',e M ): (BSe'O ainsi définies, on a > (B",e") (e',b',e").(e,b,e') = (e,b*.b,e") si, et seulement si, b'.b est défini dans B . Il en résulte un foncteur canonique: Notons alors que: hyp(Y): Hyp(Y) >B (B,e) I > B (e,b,e') i > b Hyp(Y,J) le sur-graphe multiplicatif de Hyp(Y) tel - pour toute flèche d: J(B) > J(B') de D , n'appartenant pas à J(B_) , et pour tout élément e' de Y(B') , le couple (d,e') est objet de Hyp(Y,J) . Dans ces conditions, on désigne par hyp(Y,J): Hyp(Y,J) foncteur, prolongeant hyp(Y) , tel que: - pour tout objet (d: J(B) > B_ le > J(Bf),e') de Hyp(Y,J) , qui n'est (donc) pas objet de Hyp(Y) , on a hyp(Y,J)(d,e9) = B . Il est facile de vérifier que Hyp(Y,J) est petit (puisque petite). En conséquence, le foncteur kyp(Y,J): Hyp(Y,J) *B hyp(Y,J) admet un cône limite inductive (puisque £ inductives petites): DA est >C injection possède toutes les limites (s- : k y p ( Y , J ) ( z ) - ^ Q ( Y ) ) z € H y p ( Y > J ) > 58 Alors, il est clair qu'il existe une unique (Q(Y),qy: Y D*-para-algèbre > H(Q(Y)),G y ) telle que: - pour t o u t o b j e t B de B^ , on a: q y ( B ) : Y(B) *• Homc(B,Q(Y)) S * - pour t o u t e f l è c h e à J(B) , on a: d: J(B) >• J(B*) de G y ( d , l ) : Y(B») 6 On constate aisément que librement engendrée par Enfin, si B D , n'appartenant pas > Homc(B,Q(Y)) ' ^«(d..-) (Q(Y),q Y ,G y ) est bien une Y " CB,e) (relativement au foncteur est dense dans £ et si C DA-para-algèbre Dom^*). est un objet de £ , on a (en comparant la construction précédente et celle du début de la preuve de la proposition 20, Part. II, §1, B. ) q Q(H(C)) = H(S(C)) et H(C) = H ( s ( c ) ) S DA-Paralg n°admet pas d'adjoint à gauche. D. - Enfin, nous avons: Proposition 34. Si £ est une catégorie localement petite possédant toutes les limites inductives petites et si gèbres sur £ , alors la catégorie DA DA-Paralg est une syntaxe d'alpossède aussi toutes les petites limites inductives et les foncteurs Do]HILA : D A -Paralg Bop > Ens— 59 et Codon^* : D A -Paralg P £ commutent avec ces limites. Bien entendu,' si £ possède toutes les petites limites projectives, alors les catégories DA-Métalg et DA-Paralg les possèdent également et les foncteurs Domet A , Codomet^ , D o m ^ , Codonip* , D A -para commutent avec ces petites limites projectives. 60 3. Pré-algèbres. A. - Soit £ une catégorie localement petite et taxe d'algèbres sur C . On dit que pré-algèbre (C,q: Y > H(X),p: X DA > c*G0»Gi> une syn- est une DA- si, et seulement si ,(voir aussi (S.B.D.S.)): - (X,q: Y > H(X),GQ) est - (C,p: X 5» C ^ ) une D*-para-algèbre, est une DA-méta-algèbre , - (p,q): (X,q: Y > H(X),GQ) > (C, H(p): H(X) est un homomorphisme de DA-para-algèbres, > H(C),G1) - pour toutes flèches d: J(B) > J(B') et d':J(B») > J(B") de D , composables dans D , et pour tout élément e" de Y(B"), on a (axiome "d'associativité" (+) ): G1(d,l)(G0(d',l)(e")) = G1(d'.d,l)(q(B")(e")) . De même, on dit que (c,x,y): (C,q,p,G Q ,G 1 )—> ( C S q S p ' . G ^ G » ) est un homomorphisme de la DA-pré-algèbre (C,q,p,G ,Gj) vers la DA-pré-algèbre (C\<ï»,p\G£ f Gp si, et seulement si: - (x,y): (X,q,GQ) algèbres, > (X'jqSG^) est un homomorphisme de DA-para- - (c,x): (CJPJGJ^) algèbres. > (C',p',G') est un homomorphisme de DA-méta- Dans ces conditions, on note DA-Préalg la catégorie dont les objets (resp. les flèches) sont ces DA-pré-algèbres (resp. les homomorphismes entre D*-pré-algèbres). Alors, on dispose des deux foncteurs: DA-prédo : DA-Préalg > DA-Paralg (C,q,P,GQ,G1) » > (X,q,GQ) (c,x,y) | *• (x,y) ( ) On peut avoir à considérer des "DA-algèbres partielles" plus générales que les DA-pré-algèbres, introduites ici: dans ce cas, il convient d'énoncer tout un sytème d'axiomes d'associativité. Ceci sera exposé dans un prochain travail du premier des deux auteurs, après avoir été, brièvement explicité au Séminaire de Théorie des Catégories de l'Université Paris 7 (voir aussi C.A.P.E.)). 61 et D A -préco: DA-Préalg -> DA-Métalg (C,q,p,G Q ,G 1 ) |- -> (C,p,G1) (c,x,y) i — -> (c,x) ainsi que de la transformation naturelle: H D * * £ A -prédo ^ DA-para.DA-préco : DA-Préalg DA-pré-algèbre telle que, pour toute - (C,q,p,G ,0^ ^ A ( C ' q ' p ' G 0 , G l ) = ( p ^ ) : V ^ DA-Paralg , on a: * (C,H(p),G1) . De même, on dispose du foncteur injectif: D A -pré: D A -Alg (C,F) > DA-Préalg > ^ c ' Id H(c)' Ic! c ,5,Ff5lF) l de sorte que le diagramme de foncteurs et transformations naturelles suivant est commutatif: DA-Alg DA-mét D -prédo DA-Métalg B. - -* DA-Paralg Clairement, on a: Proposition 35, Si £ est une catégorie localement petite et si est une syntaxe d'algèbres sur DA £ , alors le foncteur D A -préco: DA-Préalg > DA-Métalg admet un adjoint à gauche. Preuve. En effet, si (C,p: X il est facile de vérifier que une A > C,G) (0,¾^ est une DA-meta-algèbre, : Y 0 — * > HCX^G^ ^,G) est bien D -pré-algèbre (où l'on a repris les notations du début de la preu- 62 ve de la proposition 32, §2, B. ), librement engendrée par (C,p,G) DA-préco). Fin de la preuve. (relativement au foncteur C. - De mâme, montrons que: Proposition 36. £i £ est une catégorie localement petite possédant DA toutes les limites inductives petites et si est une petite syn- taxe d*algèbres sur £ , alors le foncteur DA-prédo: DA-Préalg > DA-Paralg admet un adjoint à gauche. Preuve. Soit (X,q: Y * H(X),GQ) une DA-para-algèbre. On sait (dfaprès la proposition 31, §1, C. ) que l^bjet engendre (relativement au foncteur une DA-méta-algèbre libre Domet *: D -Métalg (S(X), s(X): x" f On désigne alors par X A de £ > £ ) > S(X),GX). f s (X,q,G0): S(X) > S (X,q,G0) la flèche (inductivement) universelle de £ , rendant commutatif, pour toutes flèches d: J(B) sables dans de C > J(B') et df<: J(Bf) D , et pour tout élément e" > J(BM) de de D , compo- Y(B") , le diagramme suivant : G(X,q,G0)(d".d,l)(e") Gx(d,l)(G()(dM)(e")) B % S(X) Gx(d'.d,l)(q(B")(e")) (une telle flèche existe, puisque DA > Sf(X,q,G0) s'(X,q,GQ) est petite et £ possède toutes les limites inductives petites). Il est alors facile de vérifier que (S'(X,q,G0),q,s«(X,q,G0).s(X),G0,G(x^q^G } ) est bien une DA-pré-algèbre, librement engendrée par vement au foncteur A D -prédo ). Fin de la preuve. (X,q,GQ) (relati- 63 On en déduit, en particulier, que: Proposition 37, Si, £ est une catégorie localement petite, possédant toutes les limites inductives petites, et si algèbres sur est une syntaxe d* £ , alors le foncteur DA-prédo: DA-Préalg admet un DA (DA-para: DA-Métalg > DA-Paralg > DA-Paralg)-adjoint à gauche. 64 4. Para-algèbres, méta-algèbres, pré-algèbres et algèbres libres. A. - Soit £ une catégorie localement petite, possédant toutes les petites limites inductives, et D A une petite syntaxe d'algèbres sur £. En vertu de la proposition 36, §3, C. , on sait que le foncteur DA-prédo: DA-Préalg > DA-Paralg admet un adjoint à gauche: DA-Lprédo: DA-Paralg > DA-Préalg . On dispose donc de l'endo-foncteur: £ D * : DA-Paralg > DA-Préalg > DA-Métalg > DA-Paralg — DA-Lprédo DA-préco DA-para et de la transformation naturelle: : V > S Id A D -Paralg > DA s ^"Paral6 £A"Paralg. Par construction, cet endo-foncteur et cette transformation naturelle admettent des restrictions: E ' D A : DA-Métalg > DA-Métalg et *V ! IdDA-Métalg >S V ! £ A - M é t ^6 > DA-Métalg. B. - Soit £ une catégorie localement petite, possédant toutes les limites inductives petites, et D A une petite syntaxe d'algèbres sur £• On pose: " E IT = E £ * ' E £ * = Z £ A # I ; D A Si p et a DA = V ^ 1 Z DA est un ordinal (quelconque) et si 2^* : DA-Paralg est un foncteur défini, on pose: > DA-Paralg > E DA * 65 - 4A1 = V , - ^ et <^,p+1 = v 4 A • 4 A — ^ 1 • Si p est un ordinal limite, et si, pour tous ordinaux P"J < P1 et p" < p f < p , on dispose: - d'un endo-foncteur rfL : DA-Paralg - d'une transformation naturelle al*9 > DA-Paralg , : E?* > El* - d'un diagramme commutatif: alors, on pose: - IÇA = lim ( c£" ,P : 2*J" > S D A ) P " < p' < p (car Cette Umi~ DA—Paral& & te, calculée point par point dans D -Paralg— , existe en vertu de la proposition 34, §2, D. ) , 6 *B B1'1 B et, pour tout ordinal p* < p , on note 0jU * ££* * £D* la co-projection qui en résulte. Clairement, pour tous ordinaux non limites P' < p, la transformation naturelle: c^l'P : E^l 3> E ^ : DA-Paralg > DA-Paralg A admet une restriction: tf'^!'P : 2 f JI ^S°DAS £A"Métal6 >D A -Métalg . C. - Soit £ une catégorie localement petite, possédant toutes les limites inductives petites, et D A une petite syntaxe d'algèbres sur £ . En vertu de la proposition 31, §1, C. , on sait que le foncteur 66 Domet A : DA-Métalg > £ admet un adjoint à gauche: > DA-Métalg . LDometDA : £ Alors, on pose: > " nD* : £ DA-Métalg > DA-Paralg , A — LDomet * D -para - pour tout ordinal (quelconque) 0 < p > DA-Paralg , fÇ* = EJA . nDA : £ °»l ~P JO - WJJ. = CT^A n^A : f^A 1 > O^ :£ > DA-Paralg , - pour tous ordinaux 0 < p ' < p : w|JI'e = o | > 3 O^A : ÇÇ — > 0 ^ A : £ > DA-Paralg , . wjjl1 :fig.— > flg. , Ç * DA-Paralg . - pour tout ordinal J / = w ^ 0 < p : Clairement, pour tous ordinaux non limites formation naturelle: WJA , P : njl p* < P , la trans- >Q^ : £ > DA-Paralg >Clg > DA-Métalg . admet une restriction: w^''P : ng* s ç D. - Clairement, en vertu de la preuve de la proposition 20, Part. II, §1, E. , nous pouvons énoncer Proposition 38. Si a (voir aussi (C.A.P.E.)): est un ordinal régulier, si £ est une caté- gorie localement petite possédant toutes les limites inductives petites et s i £A foncteur: est une syntaxe d'algèbres de rang a sur C , alors le 67 U D * : DA-Alg > C admet un adjoint à gauche; V !£ -> D A -Alg tel que, naturellement en tout objet C de C , on a: V(C) « Urn^ (wP>P(c):^:(c)-» ^ <«V < 0 < a dans la catégorie des DA-para-algèbres (et en identifiant la aleèbre DA-para-algèbre sous-jacente ) . V D *(C) à sa En conséquence, si C et, C» sont deux objets de A existe un homomorphisme de la Sebre V DA^C'^ D -algèbre DA- C , pour qu'il V*(C) vers la £ A -al- » il faut et il suffit que la~condition suivante soit vérifiéeT " u existe deux ordinaux morphisme de la Op* (C») p £ , où A est une catégorie localement petite, est sous-algébrique d'ordre > 1/2 sur £ (modulo (D A ,D' A ) ) si, et seulement si, (voir aussi (S.B.D.S.)): - il existe une syntaxe d'algèbres D A sur £ , une syntaxe d'algèbres D' A sur DA-Alg et un foncteur inversible I: A > D'A-Alg rendant commutatif le diagramme de foncteurs suivant: > D'A-Alg A Nous dirons, plus précisément encore, qu'un foncteur U: A — > £ est sous-algébrique d'ordre > 1/2 sur £ (modulo (D A ,D' A ) ) si, et seulement si: - U est sous-algébrique d'ordre - U est algébrique sur > 1/2 sur £ modulo (I)A,D'A) , C (modulo une syntaxe a priori indépendante de D A ) , Au contraire, nous dirons qu'il est sous-algébrique d'ordre (exactement) 1/2 sur £ (modulo (DA,D,A)) si, et seulement si: - il est sous-algébrique d'ordre > 1/2 sur £ , modulo (D A ,D' A ) , - il n'est pas algébrique sur £ • On laisse au lecteur le soin de définir les foncteurs sous-algébriques d'ordre > 1/n (resp. d'ordre > 1/n ; d'ordre 1/n ) sur £ , pour tout entier n > 3 ! 70 B. - Soit lement petite. a un ordinal régulier et On dit qu'un foncteur d,Qrdre > 1/2 sur £ U: A (modulo > £ A syntaxe d'algèbres D' versible I: A > D' -Alg foncteurs suivant: est q-sous-algébrique A D* de rang a A une catégorie loca- (D ,D' ) ) si, et seulement si: - il existe une syntaxe d'algèbres A £ de rang a sur A D -Alg sur C , une et un foncteur in- rendant commutatif le diagramme de Plus précisément encore, nous dirons qu'un foncteur est a-sous-algébrique d'ordre > 1/2 sur £ (modulo U: A — > C (DA,D'A) ) si, et seulement si: - est a-sous-algébrique d'ordre > 1/2 U est a-algébrique sur £ (modulo une syntaxe a priori indépendante de D A ), Au contraire, nous dirons qu'il est sur £ (modulo sur £ (modulo (DA,D'A)), U q-sous-algébrique d'ordre (exac- (DA,D'A) ) si, et seulement si: tement) 1/2 - il est a-sous-algébrique d'ordre >.l/2 sur £ (modulo (DA,D'A)), - il n'est pas a-algébrique sur C Nous laissons au lecteur le soin de définir les foncteurs a-sousalgébriques d'ordre £ > 1/n , pour tout entier (resp. d'ordre > 1/n ; d'ordre n > 3 . 1/n ) sur 71 C. - En vertu des propositions 25 (Part. II, §2, D. ) et 27 (Part. II, §2, E. ) nous pouvons affirmer que: Proposition 39. tégorie Si^ a est un ordinal régulier, si q-présentable et si U: A > £ £ est une ca- est un foncteur, où A est une catégorie localement petite, alors les deux conditions suivantes sont équivalentes: " U est q-sous-algébrique d'ordre sous-algébrique d'ordre sur U est C • > 1/2) sur q-sous-algébrique d'ordre > 1/2 et algébrique (i.e. £ , > 1/2 (i. e. a-algébrique) 72 2. Conditions suffisantes d'-algébricité des foncteurs sous-algébriques. A. - Soit £ une catégorie localement petite. Supposons que: - D A est une syntaxe d'algèbres sur £ U * : D A -Alg - D' A > £ telle que le foncteur admet un adjoint à gauche > DA-Alg, V-*: £ est une syntaxe d'algèbres sur D A -Alg. Alors, on dispose: - de la £-isologie - de la G A: D A (DA-Alg)-isologie S A (voir G D # A : D' A Part. I, §1, D. ) , > D' A (voir Part. I, §1, D. ), - de la monade à gauche IT = (U *.V *,u,m) , associée à l'adjonction de V « de U « , donc d'un £-isomorphisme construction, d'un foncteur canonique D— D~ « D — e t , par > DA-Alg ( v o i r Part. I , §2, B . ) . On en déduit un foncteur: G D,D* : ° £«£ir -> D A -Alg canonique ->• D' canonique rendant commutatif l e diagramme de foncteurs suivant: > D' 73 D A conoyaute Dans ces conditions, nous dirons que D,A si, et seulement si: - pour tout objet D' = J,((B',FB,)) (où (B',FB,) est donc une DA-algèbre) de £• , il existe deux objets de D , il existe une flèche i Ç Cl,2} il existe de D = J(B ) et (c,ïï): V ^ B ^ D = J(B ) > (B',FB,) de DA-Alg, 7 (c.,c): (B',F«,)—> ) — Vn*(B.) . et il existe une flèche D -Alg, - naturellement en tout objet D' = J'ÇB'jF ) de D , A , il existe un B — diagramme G (D«) < ^ S.D'^l» ?'(c,c-) ^,0-^2^ de D' (où d! = ï'(ci,ci) ), présentant G ,(D') comme conoyau contrac- tile de "" (d1,d2) dans D •. Nous laissons au lecteur le soin de définir, plus généralement, dans ces mêmes conditions, les syntaxes d'algèbres colimitent des syntaxes d'algèbres B. - modulo sur C qui A sur D -Alg. Prouvons que: Proposition 40. S_i £ U: A D' A DA > £ A est une catégorie localement petite, si est un foncteur sous-algébrique d'ordre A (D ,D' ) , et si D A conoyaute est un foncteur sous-algébrique d'ordre D' A > 1/2 , alors U: A > 1/2 sur C sur C , > C (autrement dit: il est algébrique sur £ ). De plus, si a est un ordinal régulier, si foncteur q-sous-algébrique d'ordre et si DA conoyaute D'A , alors sous-algébrique d'ordre gébrique sur £ ). > 1/2 > 1/2 U: A sur £ U: A > C sur £ , modulo > £ est un (D A ,D' A ), est un foncteur a- (autrement dit: il est a-al- 74 Preuve. Notons D * D' la catégorie image pleine du foncteur •>v -> B' Y| B dont nous notons J *J' la restriction qui en résulte. Clairement, on dispose donc des foncteurs canoniques: G (restriction de G-. _.,) U -> D1 D * D' S °- * £* et: -> D * D' D * D' De plus, £ # D' sur £ . = (£fB^J * J') est bien une syntaxe d'algèbres Dans ces conditions, si (C,F) est une DA-algèbre et si ((C,F),F') est une D'A-algèbre, il lui correspond isomorphiquement une D' A algèbre ((C,F),F') (voir Part. I, §1, D.). Il est alors facile de vérifier que (C,F") est une D * D' A-algèbre, où l'on a: F": (D * D')° P •*>D'° P (G D * D f )op -> Ens . - Réciproquement, si (C,F") est une D * D' A-algèbre, il lui correspond déjà la DA-algèbre (C,F) , où l'on a: P F: D- ° (¾ *D'> op ->(D*D')° P De plus, si d': D' = J ' ^ S F f , ) > D' = J'CB'.F.,) est une flèche de o D* et si D >« (C,F) est une flèche de DA-Alg, (eSë'): (B',F D| ) — Ens mmm D on dispose (puisque A D conoyaute D' A ) du "diagramme" suivant: * V(Bi) (B',F~f) ( c ,C. ) 1* 1 df i (C,F) <(e',e') V (B £> ( B ' , F _ . ) <• T - T T - V ^ l ^ (c,c) - x. 75 (où l'on a posé x-, = Id y ^ } , si i = 1, et X i = d ^ si i = 2 ) . Alors, on pose (moyennant quelque abus de notation): (e',7') . d' = ((((e',ïï').(c ,ïï )). x.) . d.').(~.,F.) 1 X F' p" F" X Les conditions de naturalité et les équations exprimant la contractilité des conoyaux de paires utilisées permettent d'affirmer qu'on définit bien, ainsi, une D'A-algèbre ((C,F),F'). On conclut facilement. Fin de la preuve. Bien entendu, on peut énoncer (et prouver!) une proposition analogue en y remplaçant partout " D A conoyaute D , A " par " D A colimite D'A " : nous laissons ce soin au lecteur. C. - Soit £ une catégorie localement petite. Si D A U D* : A1 lT~ S est une syntaxe d'algèbres sur £ telle que le foncteur > £ admet un adjoint à gauche V * : £ on dit qu'une syntaxe d'algèbres de D A si, et seulement si: - D,A D'A > DA-Alg, sur DA-Alg est une sur-syntaxe est une syntaxe d'algèbres de sorte V D * 0 O sur C . Clairement, si D'A est une sur-syntaxe d'algèbres de la syntaxe d'algèbres D A , alors D A conoyaute D'A . Ainsi, nous pouvons énoncer (voir aussi (D.I.L.A.)): Proposition 41. Si £ est une catégorie localement petite, si Us > A £ est un foncteur sous-algébrique d'ordre > 1/2 sur £ , modulo (D A ,D' A ) , et si D'A est, une sur-syntaxe de D A , alors U: > A £ est un foncteur sous-algébrique d'ordre (autrement dit: il est algébrique sur £ ) . De > 1/2 sur C P l u s * £i a est un ordinal régulier, si U: A > £ est un foncteur a-sous-algébrique d'ordre > 1/2 sur £ , modulo (D A ,D' A ) , et S2L R'* est une sur-syntaxe de D A , alors U: A $> C est un foncteur a-sous-algébrique d'ordre > 1/2 sur £ (autrement dit: il est a-algébrique sur £ ). PARTIE V APPLICATIONS ET EXEMPLES 77 1. Exemples de foncteurs algébriques sur Cat A. - de foncteurs Soit F et F ' "deux ensembles F: X — > Y entre petites catégories. On dit que (£, (K,k),(K' ,k' )) de ( TE, 3F')-extensions de - Z^ est une catégorie petite, - pour tout foncteur teur G: X est une (petite) catégorie à choix Kan si, et seulement si: F: X > Y , appartenant à F , et tout fonc- > Z, , le diagramme suivant est une extension de Kan Pro- ject ive (de G le long de F ) : -> Y - pour tout foncteur foncteur G': X' Kan inductive (de F': X' > Y' , appartenant à F ' , et tout > £ , le diagramme suivant est une extension de G' le long de F ' ) : X' > Y' K'(G') On note alors Cat. îrM-Ka ces catégories à choix de la cat ^ 8 o r i e dont les objets sont ( F , F')-extensions de Kan et dont les flè- ches sont les foncteurs qui commutent avec ces choix. Ainsi, on dispose d'un foncteur d'oubli canonique ("catégorie sous-jacente"): 78 U (F,F')-Kan : C a t ( F, F ' )-Kan ~ Cat (Z,(K,k),(K',k')) Z B. - Montrons que (voir (E.S.T.R.), (E.D.S.A.) et (C.S.T.R.)): Proposition 42. Si a est un ordinal régulier, sjL F et_ F' sont deux ensembles de foncteurs entre (petites) catégories a-présentables (en tant qu'objets de la catégorie XQ-esquissable Cat ), alors le foncteur d'oubli canonique U (F,F')-Kan S C a t ( F, F' )-Kan " -> Cat est: - q-algébrique sur - q - s u r - e s q u i s s a b l e sur - q-monadique sur Preuve. Comme ple Cat Cat , Cat, Cat. e s t une c a t é g o r i e (E.T.S.A.) ) , e l l e e s t localement X - e s q u i s s a b l e ( v o i r , par exem- q - e s q u i s s a b l e . En conséquence e l l e e s t q-présentable e t , en vertu de l a proposition 30, Part. I I , §3, E . , pour prouver l e s t r o i s a f f i r m a t i o n s , i l s u f f i t de prouver l a première. Pour tout (resp. F: X > Y (resp. F ' : X ' > Y') appartenant à F ' ) , nous construisons tout d'abord l e s 2 - l i m i t e s inductives représentées par l e s diagrammes suivants Y/X Y//X > Y F Y/// X 79 X* //Y' X»/// Y' *• Y' — = - > Y' .) Pour toutes applications injectives croissantes f : ([!}, < ) > ({1,2}, < ) g: ({1,2}, < ) > ({1,2,3}, < ) et on en déduit deux f o n c t e u r s : (resp. V ï/x > Y//X i £ : X'/Y/ -> X* //Y' jg: !//£ " -> Y / / / X j ' : X///Y* -*> X » / / / Y' ) et (resp. rendant commutatifs l e s diagrammes s u i v a n t s : I/X Y//X __ Y//X Y/Il X ) 80 (resp. X'/Y' X'//Y X' > Y» > Y' i< \j'^/ 'f(l), X/ //Y* X ' / / / Y' De même, on dispose d'un foncteur: (resp. = k: Y//X •> Y/X k': X' //Y' -> X'/Y' ), rendant commutatif l e diagramme suivant: Y//X > Y (resp. X'//Y' X'/Y' ). 81 Alors, nous désignons par B^ F F , ) _ K a n le plus petit sous-graphe multiplicatif de Cat tel que, pour tout élément F: X (resp. F': X' > Y' ) appartenant à F (resp. F ' - X (resp. X/ ) , Y/X (resp. X'/Y» ) , Y//X Y II/ X (resp. X'/// Y') sont des objets de B. - r: X > Y/X (resp. r': X* > Y ), on a: (resp. X/ //Y» ) et , W , ) K > X'/Y» ) et k: Y//X > Y/X (resp. k'iI'//Y' - > X'/Y' ) sont des flèches de B, ^ „ . N l — •=-( F , F')-Kan pour toute application injective croissante: f: ({1}, < ) alors i f : Y/X > Y //X che de B, _ _.N „ , -( F , F')-Kan ' - > ({1,2}, < ) , (resp. i£: X'/Y' > X ' //Y' ) est flè- pour toute application injective croissante: g: ({1,2}, < ) > ({1,2,3}, < ) , alors j g : Y//X -> Y/// X (resp. est flèche de B, ^, m . s „ . -< F, F')-Kan Nous notons, enfin, £ ( F ï F . ) _ K a n 2 Y (resp. (resp. F ' ) : P ° s s e d e l e s flèches supplémentaires X < Y/X < K (resp. le sur-graphe multiplicatif de » P0"17 t o u t é l é m e n t 5> Y' ) appartenant à > X' /// Y' ) j': X' //Y' C F F x'/Y' < X' < «F' Y/// X I//X < "F X' //Y* < C F' X' /// Y' ), "F. 82 - les équations suivantes ont un sens (i. e. les composés de flèches qui y figurent sont définis) et sont vérifiées: V * VCF = 1¾ = (resp. K £ , . r ' = Ic^, V k K F"CF' = KF'^' c F-\ = ldY_ix s-1; =iV/r Cp.i^r.Kp CF,.i^ =r'.K^, V J C = I d Y//X «F-Jc = V ^ V ^ «F.-Jd = W ' vje =v s ^.-J; IÛ K'UY< = K'H* } où l ' o n a posé: a . {1} 1 > £1#2} • c: { 1 , 2 } b. f > f l } > 1 1 i > {1,2,3} , d: { 1 , 2 } {1>2} > 2 > {1,2,3} 1 I > 1 i < > 2 2 * > 2 2 > 3 > et e: { 1 , 2 } > {1,2,3} 1 y ^. ! 2 < > 3 Clairement, ^F,F')-Kan ~ (Cat '2< F, F')-Kan'£( F, F')-Kan ^~*£( F, F')-Kan ) est une syntaxe d'algèbres de rang a vérifier que U( ]pt)_ Kan est ^ F , F ' ) - K a n * F i n d e l a Preuve. sur Cat et il est facile de a-algébrique sur Cat , modulo 83 C. Si Soit F catégories U (resp * a un ordinal régulier. (resp, F ' ) est un ensemble de foncteurs entre (petites) a-présentables, on pose: F-Kan " U(F,0)-Kan s(Cat ff-Kan~ Cat Cat ( F , 0)-Kan) ) "F'-Kan/ U ( 0 . F')-Kan ;(Cat F ' - K a n f ^ g . D - K a n ^ - » C a t >• En vertu de la proposition 42 précédente, qui s'applique immédiatement, on voit que ces foncteurs sont: - a -algébriques sur Cat, - ot-sur-esquissables sur Cat, - a-monadiques sur Cat, Autrement dit, la catégorie des petites catégories munies de choix d' extensions de Kan projectives (resp. inductives),le long d'un ensemble de foncteurs entre catégories ot-présentables (voir la prop. 42),est: - isomorphe à une catégorie d'algèbres d'une syntaxe de rang a sur Cat, - isomorphe à une catégorie de réalisations d'une esquisse a-projec- tive, - isomorphe à la catégorie des algèbres d'une monade de rang a sur Cat, D. - Posons: ïï> = { 1 —>TO 0 > 0 } (où M = ( W f + ) ) Alors, la catégorie & Cat _ __ = Cat„ est la catégorie des pe& IP-Kan Peano •*—• tites catégories de Peano (voir (C.A.P.E.)) et le foncteur "catégorie sous-jacente": U., : Cat,, > Cat Peano Peano est, notamment,, en vertu du C. précédent, % -monadique sur Cat. 84 E. - Soit a un ordinal régulier. Si XX (resp. XC') est un ensemble de (petites) catégories a présentables, on pose: >l - F(XC) = £ X (resp. I X f F'(XC ) = { X' est élément de >1 / X' XC } est élément de XC' } ). ~ Cat(XC,XC')-lim = Cat(F(K),F'(JK'))-Kan " U(5«,XC')-lim = U(F(XC),F'(»t')>Karî C a t ( XC, XC')-lim * Cat ' Alors, la proposition 42 précédente s'applique immédiatement et indique que le foncteur U, . est: ( XC, XO-lim - a-algébrique sur Cat, - OC-sur-esquissable sur Cat, - a-monadique sur Cat. Autrement dit, la catégorie des petites catégories munies de choix de XC-limites projectives et_ de choix de XC'-limites inductives est: - isomorphe à une catégorie d'algèbres d'une syntaxe de rang a Cat, sur - isomorphe à une catégorie de réalisations d'une esquisse a-projective, - isomorphe à la catégorie des algèbres d'une monade de rang a Cat. sur En particulier, c'est aussi le cas pour la catégorie Ca * «-lim = Cat(XC,0)-lim XC'-lim^ (0,XC')-lim J des petites catégories munies d'un choix de limites projectives (resp. inductives) indexées par une ensemble tégories a-présentables. XC (resp. XC') de petites ca- 85 F. - Dis Notons: l'ensemble des catégories discrètes finies (i. e. un ensem- ble de représentants des classes dfisomorphismes entre catégories discrètes finies), - IPaire l'ensemble dont le seul élément est la catégorie Paire re- présentée par le diagramme suivant: (0,1,1) — » i (0,1,2) - Fin l'ensemble des catégories finies (i. e. un ensemble de repré- sentants des classes d*isomorphismes entre catégories finies), - IPfib l'ensemble dont le seul élément est la catégorie Pfib re- présentée par le diagramme suivant: - Sfib l'ensemble dont le seul élément est la catégorie Sfib re- présentée par le diagramme suivant: Alors: - la catégorie Cat . jDis-lim = Cat^ ... Prodfm (resp. ^ Cat-.. .. = Cat e Dis-lim -. Somfm e s t l a c a t é g o r i e des p e t i t e s c a t é g o r i e s munies d'un choix de produits ( r e s p . sommes)- f i n i s ( r e s p . f i n i e s ) , - l a c a t é g o r i e Cat TO . .. = Cat,. ^Paire-Jim Ker ( r e s p . Cat _ . -. = Cat. . ) r JPaire-lim^ Coker e s t l a c a t é g o r i e des p e t i t e s c a t é g o r i e s munies d'un choix de noyaux ( r e s p . de co-noyaux), ) 86 - la catégorie to Cat_,. .. tFin-lim (resp. Cat__. * -. ) est la catégorie F in-limv des petites catégories munies d'un choix de limites projectives (resp. inductives) finies, - la catégorie Cat _,-.. _. = Cat_ .-.. to ^ f îb-lim Prodfib (resp. Cat--.. -. = Cat- ,...) ^ Sfib-lim^ Somfib est la catégorie des petites catégories munies d'un choix de produits (resp. sommes) fibres (resp. fibrées). En vertu du E. précédent, ces catégories sont toutes, notamment, isomorphes à des catégories d'algèbres de monades (canoniques) de rang X0 sur Cat. De même que toutes les catégories obtenues par produit fibre (au-dessus de Cat) de deux ou plusieurs de ces catégories! 87 2. Exemples de sous-algébricité d'ordre A. - Soit iZ une catégorie petite > 1/2 sur Cat, et ker (resp. coker) un choix de noyaux (resp. co-noyaux) sur Z^ . Nous dirons que ce choix est isotrope (resp. co-isotrope) si, et seulement si: - pour t o u t e f l è c h e z: Z > Z' de Z^ , on a: ker(z,z) = Id„: Z (resp. c o k e r ( z , z ) = Id f : B. - On désigne par Cat Z' >Z >Z' ). (resp. Cat Keris . ) la catégorie uoKeris des petites catégories munies d'un choix isotrope (resp. co-isotrope) de noyaux (resp. co-noyaux). Ainsi, on dispose de deux foncteurs d'oubli canoniques: U. : Cat v îs Keris (resp. U . : Cat„ . . cois Cokeris et (resp. K > Cat v Ker > Cat. . Coker U v . : Cat v . Keris Keris > Cat U . . . : Cat. . . Cokeris Cokeris > Cat ) ) rendant commutatif le diagramme de foncteurs suivant: Cat > Cat Keris U / UKer Keris \ Cat Ker Cresp - U Cat * C a t Coker Cokeris / U Coker Cokeris \ Cat ). 88 Dans ces conditions, nous avons: Proposition 43. Le foncteur > Cat U cois : Cat Cokeris (resp. Cat. , ) . Coker De_plus, le foncteur U U ^ : Cat K e r i g Coker } ^ 1 > Cat K e r ^-algébrique sur C a t ^ U Keri£ ,: Cat K e r i s Cokeris : Cat Cokeris (resp. > Cat (resp. * C a t ^ Î2L ^-sous-algébrique d'or- dre > 1/2 sur Cat (autrement dit: il est Xp-algébrique sur Cat). Preuve. Puisque > Cat est U ^ i Cat K e r ^-algébrique sur la catégorie localement X0-présentable, il admet (en vertu de la proposition 30, Part. II, §3, E.) un adjoint à gauche V„ : Cat —5> Cat Ker Ker On dispose donc de la catégorie à choix de noyaux V (2). Ker — Par ailleurs, la catégorie 2_ est canoniquement dotée d'une unique structure, notée 2_ , de catégorie munie d'un choix isotrope de noyaux. Le foncteur Id 2 : 2 > 2 = \er(T) définit donc une unique flèche de Cat Ker ' q u e n o u s n o t o n s s :V On note, dans ces conditions, B' Cat Ker a y ant s (2) > J . le sous-graphe multiplicatif de comme seule flèche non triviale et l'on désigne par D' le sur-graphe multiplicatif de B' représenté par le diagramme et l'équation qui suivent: V ~~> 2 (2) s.s' = Idy Clairement, le foncteur U ^ s Cat K e r i g -> Cat K e r brique sur Cat R e r , modulo la syntaxe d'algèbres est D' A = (Cat,. ,B',B'c-»D') •™ qui est effectivement de rang Xn 0 sur Cat Ker .^-algéKer — — — 89 par s': 2_ s: Vv (2) > 2 , scindé Ker — — > VKgr(2_) , dans la catégorie S' , on en conclut que D conoyaute D' De plus, comme 2 est but de l'épi (voir Part. IV,§2, A. et Part. I, §1, D. ) . Les propositions 3 (Part. I, §1, E . ) , 40 (Part. IV, §2, B.) et 39 (Part. IV, §1, C.) permettent d'affirmer que que d'ordre > 1/2 sur Soit On dit que - h: X h (1) X . est bien UCoig et UCokerig . Fin de la preuve. une petite catégorie. (X,h) > Paire est une catégorie homogène si, et seulement si: est un foncteur surjectif et tel que sont deux sous-catégories connexes de Lorsque le foncteur h tant de re-préciser h Evidemment h" 1 (0) et X . est "canonique", "naturel", ou défini une fois pour toutes, on dira, plus simplement, que D. - X n -sous-algébri- Cat. On procède "dualement" pour C. - U X est homogène (en omet- à chaque fois). (Paire, Idp a i r e : Paire > Paire) est une catégorie homogène. Soit n la catégorie associée à l'ordre naturel sur l'ensemble d'entiers {0,1,...,n-l} , où Alors, si §n §1, A . ) , (§n,hn: §n n > 1 est un entier naturel fixé. désigne la catégorie subdivision de » Paire) n (voir Part. III, est une catégorie homogène, où h^ est l'unique foncteur tel que: - h n (0,l) = 0 , h n ((0,1),1) = (0,1,1) , hn((0,1),2) = (0,1,2) , - pour tout objet X de §n , différent de "" On voit facilement que §1 (0,1) , on a est isomorphe à h (X) = 1 . n Paire, et par consé- quent, elle est également (munie d'une structure de catégorie) homogène. E. - Si (X,h) est une catégorie homogène et si tégorie (petite) munie d'un choix lim x (resp. lim ir* Z est une ca- ) de X-limites 90 projectives (resp. inductives), il lui est associé un choix Ker (X,h) (resp. Coker ) de noyaux (resp. conoyaux) défini comme suit Tmoyen(X,h) nant quelque abus de notation): - pour toute paire z,z': Z > Z' ker (z,z') = Jim (x,h) de ,Z , on a: (X x > Paire h > Z ) CQfU1) (0,1,2) i(resp. Coker (z,z') = lim ( F. - Soit ^'h) a (X h ^ un ordinal régulier un ensemble de (petites) catégorie tégorie homogène Si £ > Paire > Z_ ) . (0,1,1) i (0,1,2) i > z > z' et (XC, (X,h)) (resp. (»•,(XSh 1 ))) a-présentables et pointé par une ca- (X,h) (resp. (X',h')). est une petite catégorie munie d'un choix de XC-limites (resp. XC'-limites) projectives (resp. inductives), on dit que ce choix est (X,h)-isotrope (resp. (X',h')-co-isotrope) si, et seulement si: le choix ker (resp. (X,h) coker ) de noyaux (resp. conoyaux) associé (X',h') est isotrope (resp. co-isotrope), au sens du A. précédent. Dans ces conditions, on note (resp. c ^t()K»>(Xtfhç)),limcois^ C a t / W /v , NN _. . (2K,(X,h))-limis Cat ((3K,(X,h)),(»C',(X',h'))-limis } la catégorie dont les objets sont ces petites catégories munies d'un choix de XX-limites projectives XC'-limites inductives lectives (X,h)-isotrope (resp. d'un choix de (X',h')-isotrope, de choix de (X,h)-isotrope et de XC'-limites inductives XC-limites pro(X',h')-co-iso- trope). On obtient alors des foncteurs d'oubli canoniques et un diagramme commutatif de foncteurs tel que: 91 U Cat .-is Cat (XC,(X,h))-limis XC-lim Cat (resp. U Cat U -> Cat w f . . XC'-lini ..-limcoi Cat Cat •.-cois (XC',(X',h'))-limcois U >-is -> Cat (XC,XC')-lim ((XC,(X,h)),(XC',(X',h'))-limis' U •«-limis •.-lim Cat Une démonstration en t o u t point analogue à c e l l e de l a p r o p o s i t i o n 43 précédente permet a l o r s d ' a f f i r m e r P r o p o s i t i o n 44 c Si_ a que: e s t un o r d i n a l r é g u l i e r , s_i 1 ( XC ,(X* , h ' ) ) ) e s t un ensemble de c a t é g o r i e s (XC,(X,h)) ( r e s p . q-présentables, pointé par une c a t é g o r i e homogène, a l o r s l e f o n c t e u r : U (resp. U est U (XC,(X,h))-isS Cat (XC,(X,h))-j.imis > Ca ^ XC-lim (XC',(X',h'))-coissCat(XC',(X',h' ^-limcoilT* ((XC,(X,h)),(3«',(X',h')))- i s a-algébrique sur "• C a t ^ ^ } Cat XC'-lim ' * ' (resp. C t , , . ^ ^ , Cat ( ^ xt)_lim>. De p l u s , l e f o n c t e u r : U (resp. est (XC,(X,h))-limis: — Cat (XC,(X,h))-limis ^ ^ > Cat 4» IL ( « ' . ( X ' . h ' ^ - l i m c o i s . , ' U((3K,(X,h)),(»C',(X',h')))-limis q-sous-algébriaue d'ordre > 1/2 sur } Cat: autrement d i t , i l e s t 92 a-algébrique sur gauche et est G. - Cat et donc, en particulier, il admet un adjoint à q-monadique. On pourrait multiplier les exemples de raffinement de la proposition 42: ainsi, la catégorie des petites catégories munies de choix associatifs de limites, ou celle des petites catégories munies de choix de limites projectives (resp. inductives) construites par noyaux (resp. conoyaux) et produits (resp. sommes) choisies des catégories d'algèbres de syntaxes sur ... sont Cat, donc des catégories d'algèbres de monades sur Cat. Nous laissons ce soin au lecteur, qui pourra consulter (C.A.P.E.). 93 3. Exemples de sous-algébricité d'ordre A. - On note Graph sur Graph la catégorie des graphes orientés, i. e. P la catégorie > 1/2 n Ens- , où T est le graphe multiplicatif représen- té par le diagramme et les équations suivants: «•i où c i = d.i = Id „ 1 1 Ceci suffit à établir (voir, par exemple, la proposition 28, Part. II, §3, B.) que On note Graph est une catégorie localement U: Cat > Graph le foncteur "graphe orienté sous-ja- cent": il admet évidemment un adjoint à gauche l'on sait qu'il est Si IF V: Gratfi > Cat et X0-monadique. En conséquence, d'après la propo- sition 27 (Part. II, §2, E.), B. - Soit Xn-présentable. U est XQ-algébrique sur Graph. CL un ordinal régulier. (resp. F') est un ensemble de foncteurs entre catégories a-présentables, la proposition 42 précédente permet d'affirmer immédiatement que le foncteur U est certainement ' U (]F,F')-Kan ! Cat (.F, V )-Kan a-sous-algébrique d'ordre > 1/2 > Graph sur Graph. En particulier et plus précisément nous avons: Proposition 45. Si a est un ordinal régulier, si F (resp. F' ) est un ensemble de foncteurs entre catégories discrètes et a-présentables (i. e. a-fietites). alors U.U( ï f r . ) H K a n i C a t ( r, F')-Kan ~ * est q-sous-algébrique d'ordre > 1/2 Gra Ph sur Graph: autrement dit, il est 94 a-algébrique sur Graph et donc il admet un adjoint à gauche et est q-monadique» U: Cat — > Graph Preuve. Le foncteur étant 7^0-monadique, il est q-monadique: il est donc q-algébrique, modulo une syntaxe d'algèbres D" = (Graph, £, J: B_ > D ) , de rang q sur Graph, où B est une sous-catégorie pleine petite et dense de Graph, dont les objets sont q-présentables dans Graph et telle que B_ > (Graph) est une équivalence (voir la preuve de la proposition 30, Part. II, §3, E.), La preuve de la proposition 42 précédente indique que U, ^ est q-algébrique sur Cat , modulo une syntaxe D/ -rr. -^,N v * (resp. et F: X > Y — — J F': X' catégories d'algèbres dont les objets sont, pour tout •^(FjF^-Kan > Y 1 ) , appartenant à F X (resp. X' ) , Y/X F')-Kan (resp. F ' ) , les (resp. X'/Y'), Y//X (resp. X'//Y' ) Y/// X (resp. X' /// Y' ) . Mais, il est facile de voir que ces diverses catégories sont toutes librement engendrées par des graphes orientés q-présentables, dès que X (resp. X') et Y (resp. Y') sont discrètes. Autrement dit, D , _ -^,N * est une sur-syntaxe de D A , au sens — Q F , F f ) - Kv a n — de la Part. IV, §2, C. . La proposition 41 (Part. II, §2, C.) s'applique donc: d f où la conclusion. Fin de la preuve. En particulier, il résulte de cette proposition 45 foncteurs "graphes orientés sous-jacents": Cat,, ,-. Prodfm > Graph Cat > et Somf in admettent des adjoints à gauche et sont Graph % -monadiques. C. - Montrons que: Proposition 46. Le foncteur "graphe orienté sous-jacent" "•"Keris5 C a t Keris > Graph que les 95 (resp. U est XQ-sous-algébrique d'ordre est 7C-algébrique sur et est % n -monadique. Preuve. Le Joncteur est -> Graph " U Cokeris : Cat Cokeris > 1/2 sur Graph: autrement dit, il Graph , donc il admet un adjoint à gauche U: Cat > Graph étant >C -monadique, il X 0 -algébrique, modulo une syntaxe d'algèbres % de rang sur tie et dense de Graph Graph, où ^ est une sous-catégorie pleine, pe- Graph , dont les objets sont et telle que B^ DQA = (Graph,^,^) > (Graph) -^ XQ-présentables dans est une équivalence. Par ailleurs, la preuve de la proposition 43 précédente indique nue 4 U . : CatTr . Keris Keris > Cat est une syntaxe d'algèbres D' A de rang sont 2_ , 1/Paire , 1 //Paire On a donc et X -algébrique sur 0 XQ sur Cat 1/f/ Paire . Cat, modulo dont les objets 2_ = V(2_) (moyennant quelque abus de notation ! ) . De plus, 1/Paire est la catégorie représentée par le diagramme com- mutatif ci-dessous: I (1,1) (1,0) Désignons par Tri le graphe gramme ci-dessous: (1,0) orienté représenté par le dia- 96 Alors, V(Tri) est la catégorie représentée par le diagramme et les équations qui suivent: i ^ ^ fia,i) (1,0) (0,1,1).(1,0) = (1,1,1) (0,1,2).(1,0) = (1,1,2) . Notons, alors, V(Tri) la catégorie représentée par le diagramme et les équat ions : k0.(T,ô) = (i,o). kj. = (ï,ô) (i.i.D.kj = (T,i) (1,1,2).^ = (T,D (1,0) (0,l,l).k0 = (0,1) (0,l,2).kQ = (0,1) (0,1,1).(1,0) = (1,1,1) (0,1,2).(1,0) = (1,1,2) D'où l'homomorphisme injection canonique Tri > 1/Paire induit donc un foncteur K : V(Tri) > 1/Paire. Notons K': 1/Paire > V(Tri)_ l'unique foncteur tel que: - K'(0,1,1) = (1,1,1) , K'(0,l,2) = (1,1,2) et K'(I,0) = kj . Clairement, en reprenant les notations de la proposition 38 (Part. III, — 2 2 §4, D . ) , K induit un homomorphisme K_ : Cl ,«(V(Tri)) > O D ,*(1/Paire) — 2 2 et K' induit également un homomorphisme K': C^,»(l/Paire) — » Q ,«(V(Tri)). 97 La proposition 38 indique donc qu'ils induisent deux homomorphismes: * ! W i s ' 7 ^ > VKeris(i/Z£ire) et * '•V Keris ( I/£ii^> — * V Keris' V( Ï2i> et l'on établit sans difficulté que K.K' = Id • Un raisonnement en tout point analogue, portant sur les catégories 1 //Paire et 1/// Paire permet donc de conclure que IL* conoyaute D'* , au sens de la Part. IV, §2, 1. La proposition 40 (Part. IV, §2, B.) permet donc de conclure en ce qui concerne U.U keris Le raisonnement "dual" fournit le résultat cherché pour U.U Cokeris Fin de la preuve. De la même manière, nous avons, plus généralement: Proposition 47. Si q est un ordinal régulier, s£ (XC,(X,h)) (resp. ( XC',(X',h')) ) est un ensemble de catégories q-présentables, pointé par une catégorie homogène, alors le foncteur "graphe orienté sous-jacent •i Cat Cat (resp. (XC,(X,h))-limis > GraPh (xc. >( x. >h '))-limcois > GraPh * — Cat > ((»C,(X,h)),(»C',(X',h'))-limis > Graph ) est q-sous-algébrique d'ordre > 1/2 sur Graph: autrement dit, il est q-algébrique sur Graph , donc il admet un adjoint à gauche et est q-monadique. 98 *• Exemple d'algébricité d'ordre (exactement) 1/2 sur Graph. A. - Soit G un graphe orienté fini et non vide. On dit qu'une flèche seulement si: - il existe un entier g: G > G' de G n > 1 et un diagramme de G' = Gn > G. 6 > G. ... 6 1 > G 6 2 Ainsi, par exemple, pour tout objet G de la forme = G n G , la flèche — est cyclée. Plus généralement, toute flèche fermée g: G G_ est cyclée! Dans ces conditions, on note G , ayant mêmes objets que ches cyclées de G est cyclée si, et de Id^: G — > G G > G de C(G) le sous-graphe orienté de G , dont les seules flèches sont les flè- G • On désigne alors par Ind(G) l'indice de G , i. e. le nombre entier fini, non nul, de composantes connexes (non vides) du graphe orienté C(G). On peut donc affecter à tout composante connexe 1 < i < Ind(G) une et une seule C ^ G ) , que l'on appelle La i e m e composante connexe de C(G). si ! < i < Ind(G) et 1 < j < Ind(G) , on pose i « j (ou encore C^G) « C (G) ) si, et seulement si: - il existe un objet flèche g: G G > G' de Clairement, la relation de G <£ C ^ G ) , un objet G' de C.(G) et une . , ainsi définie sur une relation d'ordre: on en désigne par (l,2,...,Ind(G)} , est Ind(G) le graphe orienté. . . . .TT. Si - 1 < i < Ind(G) , 1 < j < Ind(G) et 0(i,j) = [g:G = a(g) i « j , on pose: > G' = b(g)/ g Ç F1G , G € ObC^G) , G' € ObC.(G)} (que l'on identifie, dans toute la suite, à un graphe orienté discret). Alors, on considère le fonofc«ar canoniquement associé à <>r: §(§(Ind(G))) . > Graph G : 99 ((i,j),l) ((i,j),2) 0(i,j) 0(i,j) (en respectant l'ordre de lecture). B. U: Cat On rappelle que le foncteur "graphe orienté sous-jacent" > Graph De même, si de admet un adjoint à gauche Cat V: Graph > Cat. est la catégorie des petites catégories Peano (voir le §1, D . ) , le foncteur "catégorie sous-jacente" U^ : Cat.. > Cat Peano Peano V: Cat > Cat,, Peano admet un adjoint à gauche J . On pose alors & T_ Peano Peano Enfin, il est très facile de voir que U = U_ ^ -V^^ . Peano (et donc commute(ent) aux sommes. C. - Clairement, on a: Lemme 1. SjL £ dans est un graphe orienté fini, non vide, alors : Graph. En conséquence, on a aussi: V(G) = dans Cat , de même que: V,, .V(G) = Peano — dans lim 3 (V.()G ) lim > Cat._ Peano Etablissons, maintenant, que: (V^ .V.(L ) Peano ^G Peano T pGanQ) 100 Lemme 2. Si E est un ensemble (identifié à une petite catégorie discrète), alors on a: T_ (E) = E x T., (1) Peano Peano — dans Cat. = ii i Preuve. On a x de E = -Li 1_ dans Cat , où 1 =1^ pour tout élément x€E X ~* E . En conséquence, on a: V-, (E) = I 1 V(1 ) et donc, Peano -„ Peano —x x€E puisque T p commute aux sommes: T PoaflA (E) = -LL Peano T(1 ) = E x T_ (1) dans Peano V x Peano — Cat. Fin de la preuve. De même, montrons que: Lemme 3. !Si E est un ensemble (identifié à une petite catégorie discrète), alors on a: T. (E x 2) = E x L (2) = E x 2 x L (1) Peano — Peano — — Peano — dans Cat. Preuve. On a E x 2^ = élément 1 | 2^ dans Cat , où x x£E E • En conséquence, on a: x de T 2 = 2 pour tout x Peano(E x V = - L L ^ e a n o ^ = E x TPeano^) x€E et il est, de plus, facile de vérifier directement que T(2) = 2 x T_ (1) . Peano — — Peano — Fin de la preuve. Nous sommes alors en mesure de prouver que: Lemme 4. £i G est un graphe orienté fini, non vide, alors on a: T_ .V(G) = T B .V(lini Y G'} n'a qu'un seul élément. Mais, dans ces conditions, la catégorie X est définie comme suit: - elle contient la sous-catégorie pleine (C^G)) = CTTGT ) x Ci} (T Peano dès que i € {1,2} (et l'on note aussi T (a) = a : T et T Peano ( b ) = F 5 T Peano ( ±>-^ W > ^ ^ ^ - ses seules autres flèches sont les classes d'équivalence (k,H,k') : (K,l) des t r i p l e t s (k,H,k') + > (K',2) t e l s que: H est un objet de T 0L)->C-(G) (1) , 102 + k: K + k': b(H) > â(H) est flèche de C ^ G ) , > Kf est flèche de C 2 (G) , et ce, modulo la relation d'équivalence telle que (k,H,k') ~ ( k ^ H ^ k p si, et seulement si: + il existe un zigzag H < Z: + > Z de T P e a n o ^ d e l a f o r m e < ^ H! il existe un diagramme commutatif de C-(G) de la forme a(Z):a(H> + il existe un diagramme commutatif de C^(£) de la forme b(Z):b(H> b(H x ) 103 Une vérification longue mais facile (car les cycles de groupés*) permet alors de conclure. Fin de la preuve. D. - Considérons, maintenant, la catégorie £ G ont été "re- définie comme suit: - elle contient (T ne, dès que i Ç {1,2} et U IN : — de V-Peano > — ( ]N ) = JN ) x {i} comme sous-catégorie plei(on note - cf. p. 83 - T,, (e) = ê:T„ (1) - > 1 N reano Peano — — e ncteur * f° canonique, associé à l'adjonction à &gauche de U„ Peano ), ' - ses seules autres flèches sont les classes d'équivalence des triplets (c,A,cf) tels que: + A + est objet de T Peano . (1) J — ,' c: C > "ê(A) est flèche de + c': ë(A) > C est flèche de IN , ]N , et ce, modulo la relation d'équivalence engendrée par la réunion des deux relations R- et R- telles que: + (c,A,c') R (c ,A.,c') si, et seulement si, il existe trois diagrammes commutatifs: •> A l danS dans ^eano^ IN e(Z) ë(Z) dans IN 104 + (C.UJJO)),^) R2 ( c ^ u ^ O ^ e p s i , et seulement s i , i l e x i s t e t r o i s diagrammes commutatifs Z0: •0 . . . 0 0 dans IN dans IN u m< z o ): U MCVS dans ]N I l est f a c i l e de v é r i f i e r que le diagramme commutatif de présente P comme limite inductive d*un foncteur 9 : I Cat suivant > Cat: 105 E. - Compte tenu du lemme 1, il est clair que: Lemme 5. Naturellement en tout graphe orienté fini (non vide) G , on a: Hom Cat (V(G), P)= lim> 9 (-)) = U m > (HomCat(V(G),9(-))) dans Ens • Enfin, prouvons que: Lemme 6. Il n'existe aucune structure de catégorie de Peano sur P = lim 9 qui fasse des co-projections r^: IN > P et r0: 2 x T„ (1) 2 — — — 3 — Peano — catégories de Peano. Preuve. Soit E un ensemble et v: E r.: ]N > P — > £ , des homomorphismes de - > E une application tels que: (a) pour tout entier n > 0 , on a v (évidemment, un tel couple On note ^ Id£ , (E,v) existe ! ). (resp. <3Œ» ) la plus petite sous-catégorie de Ens telle que: - E est objet de - (resp. v: E > E est flèche de «*Œ» ) , (resp. > Ens (resp. «CE» > Ens) commute avec ces sommes. Alors - est la sous-catégorie de ses objets sont les Ens telle que: 3N x E , pour tout entier p , - ses flèches sont les applications g x Id„ : Ttr x E pour toute application g: IN > IT* • Evidemment, est une sous-catégorie de > INq x E , < Œ » , ayant mêmes objets 106 et (resp. < Œ » ) est canoniquement munie d'une structure de catégorie de Peano (de sorte que l'injection canonique > «E» est un homomorphisme de catégories de Peano): à tout foncteur _1 > < E > (resp. I > v la plus petite sous-catégorie de « E » , contenant v et : alors, la condition (a) permet d'établir facilement que: (b) il n'existe aucun diagramme commutatif de « E » , de la forme ]N x E Z: IN x E où Z est un zigzag de . 107 Dans ces conditions, on dispose tout d'abord d'un unique diagramme commutatif d'homomorphismes entre catégories de Peano: T_ (IN) = m P e a n o — — -»> ^eano^ tel que: u. -> •* T Peano (1) D — -> E 0 h et IN IN — _ > ]N -> - « E » -> (1: 0—> 0) (v: E-5> E) . Ensuite, si l'on représente par: U 1N(0) •*• Q l ' e x t e n s i o n de Kan du foncteur: 1 0 - ^ IN i- on dispose d'une unique f l è c h e -*U1N(0) k: Q > u-XO) ' de " k ' h = W u„(0) • - k . s = u _ T ( l : 0 —> 0 ) . k . IN Enfin, si l'on pose (en reprenant les notations du D.): " *= (Id uM(0)'ullW^IduI|(0); ' IN t e l l e que: 108 - y = (Id Q ,Q,Id Q ) , on dispose de deux flèches: x.(k,l): (Q,l)—5> ( UlN (0),2) et (k,2).y: ( Q , l ) — ^ ( UjN (0),2) de .P , solutions du système des deux équations (en z ): r z.(h,l) = x (z.(s,l) = u ^ d : 0 — > 0).z . x.(k,l) 4 (k,2).b . Mais, la propriété (b) permet d'affirmer que D'où la conclusion. Fin de la preuve. F. - Nous pouvons, maintenant, établir que: Proposition 48. Le foncteur - U.U„ : Cat_ Peano Peano sous-algébrique d'ordre exactement 1/2 sur > Graph est X 0 Graph: en particulier, il admet un adjoint à gauche mais il n'est pas monadique. Preuve. Notons IT la monade associée à l'adjonction de V_ .V J Peano à gauche de U.U : elle est, trivialement, de rang ?L. Si U.U^ était X^-monadique, il serait, en vertu de la propoM Peano 0 sition 30 (Part. II, §3, E.) , algébrique modulo la syntaxe d'algèbres D', * sur -/\ 0 ' R 5 Graph (voir la Part. II, §2, C ) . Or, les lemmes 1, A et précédents assurent que le graphe orienté sous-jacent à noniquement muni d'une structure de D' A est ca- -algèbre telle que: - sa catégorie sous-jacente est £ , - les co-projections > .P , r« : ]N r : JN £ > P^ et r 0 : 2 x T„ (1) > P définissent des homomorphisme s de D' *3 — Peano— — — 7(L, IT algèbres. Mais, le lemme 6 précédent signifie, en particulier, que cette structure de D' ^-algèbre n'est certainement pas une -K 0 ,ir structure de catégorie de Peano. D'où la conclusion. Fin de la preuve. 109 BIBLIOGRAPHIE. (A.L.G.R.) A. Burroni, Algèbres graphiques, Cah. de Top. et Géom. Diff., Vol. XXII,3 , Amiens, 1981. (A.O.F.S.) F. E. J. Linton, An outline of functorial semantics, Lee. Notes in Math. 80, Springer, 1969. (C.A.P.E.) L. Coppey, Catégories de Peano,catégories algorithmiques, récursivité, Diagrammes 12, Paris, 1984. (C.A.S.T.) C. Ehresmann, Catégories et structures, Dunod, Paris, 1965. (C.F.W.M.) S. MacLane, Catégories for the working mathematician, Grad. Text. in Math. 5, Springer, 1971. (C.S.C.S.) F. Mouen, Sur la caractérisâtion sémantique des catégories de structures, Diagrammes U , Paris, 1984. (C.S.T.R.) C. Lair, Condition syntaxique de triplabilité d'un foncteur algébrique esquissé, Diagrammes 1, Paris, 1979. (D.I.L.A.) J. Beck, Distributive laws, Lect. Notes in Math. 80, Springer, 1969. (E.D.S.A.) C. Lair, Esquissabilité des structures algébriques, Thèse de Doctorat es-Sciences, multigraphiée, Amiens, 1977. (E.S.T.R.) C. Lair, Esquissabilité et triplabilité, Cah. de Top. et Géom. Diff., Vol. XVI,3,'Amiens, 1975. (E.T.S.A.) C. Ehresmann, Esquisses et types des structures algébriques, Bul. instit. Polit. (F.D.C.A.) Iaçi, XIV, 1968. Y. Diers, Foncteur pleinement fidèle dense classant les algèbres, Pub. de l'U. E. R. de Math. Pures et Appli. de l'Univ. Lille I, 1975. (F.O.S.A.) C. Lair, Foncteur d'omission des structures algébriques, Cah. de Top. et Géom. Diff., Vol. XII,2, Paris, 1971. 110 (L.P.L.G.) F. Ulmer, Locally 1/2 sur Cat. 87 3. Exemples de sous-algébricité d'ordre > 1/2 sur Graph. 93 112 4. Exemples d'algébricité d'ordre (exactement) 1/2 sur Graph. 98 BIBLIOGRAPHIE. 109