D IAGRAMMES C HRISTIAN L AIR Éléments de théorie des patchworks (I) Diagrammes, tome 29 (1993), exp. no 1, p. CL1-CL29 © Université Paris 7, UER math., 1993, tous droits réservés. L’accès aux archives de la revue « Diagrammes » implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ DIAGRAMMES VOLUME 29,1993 ELEMENTS DE THEORIE DES PATCHWORKS (I) Christian LAIR Introduction Dans ce travail, nous présentons forniellenient la notion de patchwork (et celle, indissociable, d'honioniorphisme entre patchworks) et la notion de modèle d'un patchwork d a n s une catégorie (et celle, indissociable, de transformation entre modèles d'un patchwork donné dans u n e catégorie donnée). On pourra y voir un patchwork, au choix, comme : — une présentation diagrammatique d'un type de structures qui peuvent être axiomatisées par une théorie (logique) du 2ème ordre, — u n e spécification diagrammatique "orientée sous-diagrammes" (i. e. "orientée objets") d'un type abstrait de données, — u n e esquisse (voir (I.T.S.C.) e t / o u (E.T.S.A.) e t / o u (C.Q.C.E.), par exemple) généralisée, en ce sens qu'on peut y distinguer des sous-diagrammes plus complexes que seulement des cônes project if s ou des cônes inductifs. Dès lors, on pourra y voir aussi un modèle d'un patchwork comme : — u n modèle de la théorie logique correspondante, — une sémantique pour le type abstrait ainsi spécifié, — u n foncteur transformant les sous-diagrammes distingués en A.M.S. SUR CIASS. : 18 C 10, 18 D 35 , 18 A 10 ELEMENTS DE THEORIE DES PATCHWORKS (I) des sous-diagrammes astreints à vérifier des conditions plus générales que seulement des propriétés universelles. Ce texte se veut le premier d'une série d'autres (que nous espérons pouvoir publier assez régulièrement) où nous continuerons à développer les éléments les plus significatifs de cette (naissante!) théorie des patchworks" : — esquisses et trames (voir (S.C.S.T.)) comme patchworks particuliers, — divers et nombreux exemples, — esquissabilité projective de la structure de patchwork, propriétés de la catégorie des patchworks et constructions de patchworks, — notion de sémantique catégorique d'un système de patchworks, esquissabilité de la structure de sémantique catégorique et "complétions" de patchworks, — propriétés de catégories de modèles, Le contenu du présent travail - et au delà - a fait l'objet d'un certain nombre d'exposés : aux Journées "Esquisses et Types de Structures" (Université Paris 7, 2-4 Juillet 1992) et au Groupe de Travail "Esquisses et Calcul Formel" (Université Paris 7, Octobre 1992 et Mai 1993), notamment. Deux raisons (principales) m'incitent, cependant, à publier dès maintenant cette seule partie I (qui paraîtra, sans doute, d'autant plus brève et formaliste qu'elle est encore, nécessairement, très isolée des suivantes) : — d'aucuns, qui m'y ont poussé, voulaient pouvoir disposer d'une référence bibliographique précise, — d'autres préféreraient certainement le contraire- 1. Patchworks et homomorphismes Dans ce paragraphe, nous définissons successivement les "patchworks" (qui sont des graphes munis d'une structure supplémentaire) et les "homomorphismes" entre patchworks (d'autant plus naturellement que la structure de patchwork est projectivement esquissabie, i. e. essentiellement algébrique). Un "patchwork" est un graphe muni d'une composition partielle de ses flèches et auquel sont attachées des "figures" constituées de "triangles" et de "cônes" plus ou moins complexes, en ce sens que leurs sommets sont eux-mêmes des patchworks : ainsi, le patchwork (total) considéré a un "degré" (de complexité) qui est évidemment plus élevé que ceux des patchworks constituant ses figures. Précisément, on définit les patchworks, par induction (voir la Note 1), de la manière suivante: — on dit que P = ( S , 0 ) est un patchwork de degré 0 si S est un graphe à composition (voir la Note 2), appelé le support de P et noté S = S U P P ( P ) , — si n £ 0 est un ordinal (voir la Note 3) et si S est un graphe à composition, on dit que le quintuplet T = ( r , > l , / ? , p , i l ) est un triangle de degré < n au-dessus de S si (on pourra se reporter au Tableau 1, ci-dessous) : SUPP ( r ) \ -i Tableau 1 CL 3 %> SUPP ( A ) ELEMENTS DE THEORIE DES PATCHWORKS (I) • r est u n patchwork de degré < n (et de support SUPP ( F ) ), appelé le patchwork de gauche de T et noté r = PGAUCHE ( T ) , • A est u n patchwork de degré ^ n (de support SUPP ( A ) ), appelé le patchwork de droite de T et noté A = PDROITE ( T ) , • A: SUPP( T ) - + S est u n foncteur (voir la Note 2), appelé le fondeur de gauche de T et noté X = FGAUCHE ( T ) , • p : SUPP ( r) -* SUPP ( A ) est un foncteur, appelé le foncteur debasede T e t n o t é /3 = B A S E ( T ) , • p : SUPP ( A ) -• S est u n foncteur, appelé le foncteur de droite de T et noté p = FDROITE ( T ) , • l'égalité suivante est satisfaite : — si n >0 est p o p = X, ordinal, on dit un que le C = ( J , JE, ( /ZTI)IGOB(J), ( £ 2 I ) I € O B < / ), ( ri)ïeFL(/ )) quintuplet est un cône de degré < n si (on pourra se reporter au Tableau 2, ci-dessous) : SUPP(X SUPP(Ûi) Tableau 2 • I est un graphe à composition identitaire (voir la Note 2), appelé Yindexation de C et noté I = INDEX ( C ) , • E est un patchwork de degré ^ n (de support SUPP ( L ) ), appelé le sommet de C et noté E = SOMMET ( C ) , • pour tout objet 1 de I, £2i est un patchwork de degré < n (de support SUPP ( 121 ) ), appelé Vopposant dfindice noté Qi = OPPi ( C ) appelée la famille 1 de C et (alors la famille i2 = ( Qi ) i € 0 Q(/ ) des opposants I2 = O P P ( C ) ) , CL 4 de C et est est notée ELEMENTS DE THEORIE DES PATCHWORKS (I) • pour tout objet I de J , JL\ : SUPP ( E)-+ SUPP ( JQI) est un foncteur, qu'on appelle le foncteur projection d'indice et que Ton note n\ = PROJ i ( C ) ; t = ( 7ti: SUPP (E)-+ SUPP ( I 2 i ) ) IGOB(I) (alors 1 de C la famille est appelée famille des projections de C et est notée TU = PROJ ( C ) ), • pour toute flèche i : I -• I' du graphe à composition J, ri : SUPP (121 ) -* SUPP (121-) est un foncteur, appelé le foncteur transition d'indice i de C et noté n = TRANSIT i ( C ) (alors on appelle diagramme des transitions de C , et on note également r = TRANSIT ( C ) = ( n : SUPP ( i2i )-> SUPP ( i2i ) ) ieF L(i )) la famille de ces transitions), • pour tout objet 1 G OBID(I) =OB ( / ) du graphe composition (identitaire, par hypothèse) / , on a l'égalité : à riD(i) = I D ( S U P P ( f l i ) ) , • pour toutes flèches i : 1 -• l1 et ï : I1 -+ I" composables (voir la Note 2) dans / , on a l'égalité : Ti'-ï = de /, 7~i' O T i , • pour toute flèche i : 1 -* F de / , on a l'égalité : n om = Kv, — si n > 0 est un ordinal et si S est un graphe à composition, on dit que le triplet F = ( T , a , C ) est une figure de degré ^ n au-dessus de S si (on pourra se reporter au Tableau 3, ci- dessous) : Tableau 3 CL 5 ELEMENTS DE THEORIE DES PATCHWORKS (I) • T est u n triangle de degré £ n au-dessus de S , appelé le triangle de F et noté T = TRIANGLE ( F ) , • C est u n cône de degré ^ n , appelé le cône de F et noté C = CONE(F), • a:SUPP(PDRCHTE(T)) -* SUPP ( SOMMET ( C ) ) est u n foncteur, appelé Yarête de F et noté a = ARETE ( F ) , — si n £ 0 est un ordinal et si S est un graphe à composition, on dit que le triplet F = ( T , a , C ) est une figure de degré 0 est un ordinal, on dit que P = (S7^J) est u n patchwork de degré < n si (on pourra se reporter au Tableau 4, cidessous) : Tableau 4 *S est u n graphe à composition, appelé le support de P CL 6 et ELEMENTS DE THEORIE DES PATCHWORKS (I) noté S = S U P P ( P ) , • S J est un ensemble (voir la Note 1) de figures de degrés < n au-dessus de iS, appelées les figures attachées à P (ou S) et noté 7 = F I G A T ( P ) . En particulier, si HJ. est un univers (voir la Note 1), nous laissons au lecteur le soin de définir les patchworks 'li-petits (i. e. les patchworks où "tout11 est fy-petit). Tout naturellement, les "homomorphismes" entre deux patchworks sont les foncteurs qui transforment les figures attachées au patchwork domaine en des figures également attachées au patchwork codomaine. Formellement, si S et S' sont deux graphes à composition, si f: S -+ Sf est un foncteur et si n ^ 0 est un ordinal, on constate tout d'abord, que : — dès que T = ( J T , / l , / 3 , p , A ) est un triangle de degré < n au-dessus de S , alors (on pourra consulter le Tableau 5, cidessous) f(T)=(r,foX, p,fop,A) est un triangle de degré < n au-dessus de S', qu'on appelle le transformé de T par le foncteur f7 SUPP( Tableau 5 — dès que F = ( T , a , C ) est une figure de degré < n au-dessus de S y alors (on pourra consulter le Tableau 6, ci-dessous) / ? ( F ) = ( / ? ( T ) , a , C ) est une figure de degré < n au-dessus de S', qu'on appelle la transformée de F par le foncteur f. CL 7 ELEMENTS DE THEORIE DES PATCHWORKS (I) s s- ' v ' Tableau 6 De la sorte, si P et P' sont deux patchworks, on dit que h = (P,f, P') est un homomorpKisme de P vers P' et on note h : P - P' si : — f : SUPP ( P) -+ SUPP ( P ' ) est un foncteur, appelé le support de h et noté f= SUPP ( h) , — dès que F est une figure attachée à P , alors la figure f ( F ) est attachée à P' (et on dit encore que f(F) est la transformée de F par h et on note de même f ( F ) = h ( F ) ) . Nous laissons au lecteur le soin de définir l'homomorphisme, bien entendu noté h ' o h : P - * P " , composé de deux homomorphismes consécutifs h: P -+ P' et h' : P' -• P " entre patchworks (de sorte que le foncteur support du composé soit le composé des foncteurs supports). De même, n o u s lui laissons le soin de définir l'homomorphisme, évidemment noté ID ( P ) : P -> P, identité en un patchwork P (de sorte que son support soit le foncteur identité). En particulier, si s li est u n univers, on note Qi-Patch la catégorie (où "la composition est celle des supports") dont les objets sont les patchworks '7^-petits et dont les flèches sont les homomorphismes entre ces patchworks. 2. Modèles et transformations Dans ce paragraphe, nous définissons successivement les "modèles" d'un quelconque patchwork dans une quelconque catégorie (puisqu'il faut voir un patchwork comme une spécification diagrammatique d'un genre de structures), les "standards de transformations" puis les "transformations", conformes à un tel standard donné, entre modèles d'un patchwork donné dans une catégorie donnée (étant entendu que les transformations naturelles sont évidemment conformes à un standard ... canonique ! ). Un "modèle" d'un patchwork dans une catégorie se doit d'en concrétiser sa géométrie (i. e. son graphe sous-jacent) et son algèbre (i. e. ses équations de composition) abstraites : c'est donc, au moins, un foncteur. Mais il doit aussi respecter une certaine logique de comportement (existence de "factorisations" et de "connexions") vis-à-vis d'autres modèles: ceux des patchworks partiels constituant les figures attachées au patchwork total initialement donné. Ainsi, les modèles des patchworks dans une catégorie donnée A sont définis, par induction, comme suit : — si P = ( S , 0 ) est un patchwork de degré 0 , on dit qu'un foncteur g : S -*• A définit (ou même est) un modèle (noté formellement m = (P,g,A)) de P vers A et de support g et on note m:P-+A (ou même g : P -> A ) et g = SUPP ( m ) , — si n £ 0 est un ordinal, si C est un cône de degré £ n , si H , K sont deux objets de INDEX (C) et si m' K : OPPK (C) -> A m' H : OPPH (C) — A sont des modèles, on dit que et le quintuplet X = (p , (Iq)i l2s+i est u n e flèche de INDEX ( C ) , • pour tout entier 1 < q < 2 p + l , m" q : OPP iq ( C ) -* A est un modèle, • pour tout entier 1 < r <* p , on a l'égalité: SUPP ( m"2r i ) o TRANSIT i r ( C ) = SUPP ( m"* ), • pour tout entier 1 < s < p , on a l'égalité : S U P P ( m " 2 s + i ) o T R A N S I T je ( C ) = S U P P ( f n " 2 s ) , • les deux égalités suivantes sont satisfaites : m H = m'\ -si et m K = m V u , n > 0 est u n ordinal, si C est un cône de degré < n , CL 10 ELEMENTS DE THEORIE DES PATCHWORKS (I) si m' : SOMMET ( C ) -• A est un modèle, on dit qu'il satisfait C si (voir la Note 4) : • il existe un objet I de INDEX ( C ) et un modèle m'i: OPPi( C )->A pour lesquels on a (on pourra se reporter au Tableau 8, ci-après) : SUPP ( ro'i ) o PROJ i ( C ) = SUPP ( m' ) (alors, on dit que m'i est une C-factorisation de ro'), • deux C-factorisations de m ' sont C-connectées, — si n £ 0 est un ordinal et si P = ( S , < 7 ) est un patchwork de degré < n , on dit qu'un foncteur g : SUPP (P) -+ A même est) un modèle (noté formellement rn = (P,g, vers A et de support g: P -» A ) et g- g et on note SUPP ( m ) définit (ou A ) ) de P m: P -• A (ou même si (on pourra se reporter, de nouveau, au Tableau 8, ci-dessous) : 1 OPPr(C) Tableau 8 • dès que F = ( T , a , C ) E \ 7 est une figure de degré < n , attachée à P, alors g o FGAUCHE ( T ) : PGAUCHE ( T ) -+ A et g o FDROITE ( T ) : PDROITE ( T ) -> A sont deux modèles, CL U ELEMENTS DE THEORIE DES PATCHWORKS (I) • dès que F = ( T , a , C ) e ^ J est une figure de degré < n , attachée à P , et dès que m ' : SOMMET ( C ) -• A est un modèle pour lequel on a l'égalité SUPP ( m ' ) o a = # 0 FDRCMTE ( T ) , alors m ' satisfait C . Dans ces conditions, si P est u n patchwork et si A est une catégorie, on note ENSMOD ( P, A ) l'ensemble des modèles de P vers A . Enfin, si h: P -+ P' est u n homomorphisme entre deux patchworks, si A est une catégorie et si rn':P' -+A est un modèle, nous laissons au lecteur le soin de définir le modèle composé m,oh:P-+A (de sorte que le foncteur support du composé soit le composé des foncteurs supports). Ainsi, on dispose de l'application "composition par h " : ENSMOD ( h , A ) : ENSMOD ( P*, A ) — ENSMOD ( P , A ) . Il n'est pas toujours judicieux de considérer qu'un homomorphisme entre deux modèles (seulement vus comme deux foncteurs particuliers), d'un patchwork donné dans une catégorie donnée, n'est rien d'autre qu'une transformation naturelle. Dès lors qu'on voit plus ces deux foncteurs comme des modèles d'une spécification diagrammatique qui peut être t r è s complexe, il peut s'avérer préférable de spécifier aussi la forme des transformations - non nécessairement naturelles - souhaitées, et ce à l'aide d'un nouveau patchwork. Autrement dit, les "transformations" désirées, que nous introduisons ici, doivent être "conformes" à u n certain "standard" constitué - pour l'essentiel - par une cocatégorie dont l'objet des objets est (à quelque nuance près) le patchwork initialement donné et dont lfobjet des flèches est ce nouveau patchwork. Alors, on peut comparer (cette fois, naturellement!) de tels standards à l'aide de "protocoles" : ce sont eux qui fournissent les foncteurs "modèles sous-jacents". Ainsi, si A est une catégorie, on dit D = ( P, 6, Ecat, que le EOB , 0 , ^ , /i ) est u n A-standard CL 12 sextuplet (catégorique) ELEMENTS DE THEORIE DES PATCHWORKS (I) de transformations si (on pourra se reporter au Tableau 9, ci- dessous) : Tableau 9 — P est un patchwork, appelé le patchwork de référence de D et noté P = PATCH(D), — Ecat est l'esquisse des catégories et EOB en est "l'objet des objets" (voir la Note 5), (on peut appeler référence de D et Ecat EOB l'objet de référence de Vesquisse D de et noter Ecat = ESQREF ( D ) et EOB = OBREF ( D ) - voir la Note 6), — Qi est un univers, appelé l'univers de référence de D et noté Qi = UNIV ( D ) , pour lequel A est ^-petite, — (f>:( SUPP ( Ecat ) ) op -• Qi-Patch foncteur de co-représentation est un foncteur, appelé le relatif à D et noté = COREP ( D ) , — 6: (EOB ) -• -P (voir la Note 5) est un homomorphisme entre patchworks, appelé l'homomorphisme CL 13 de co-affaiblissement relatif ELEMENTS DE THEORIE DES PATCHWORKS (I) à D et noté 0 = COAFF(D), — p : Ecat -• Qi-Ens est un modèle de support le foncteur ENSMOD(0(-),A):SUPP(JEcat) -^Oi-Ens, de sorte que p est une catégorie (voir la Note 5), qu'on appelle la catégorie faible relative à D et qu'on note p = FBLE ( D ) . Dans ces conditions, si TOI ,TO2: P -• A dit que 1 = ( T O I , I I , T O 2 ) (A-)standard sont deux modèles, on est une transformation, conforme au D , de TOI vers m 2 et d'affaiblissement ri, et on note ! : T O I - > D T O 2 (OU t: TOI -*DTO2: P -> A ) et Q = A F F D ( £ ) , si (on pourra se reporter, de nouveau, au Tableau 9, ci-dessus) : — n: ( EFL ) - + A (voir la Note 5) est un modèle, — on a les deux égalités (voir la Note 5) : n o ( eooM ) = TOI O d et n o 4> ( ecoDOM ) =TO2o 6. Alors, on laisse au lecteur le soin de définir la transformation, conforme au standard D , notée ti *D U :TOI-*DTO3, composée de deux transformations, conformes au standard D , consécutives fi:TOi-*DTO2 et l'affaiblissement de £2:TO2-+DTO3 la composée (et ce de sorte que soit la composée des affaiblissements, dans la catégorie p ). On lui laisse également le soin de définir la transformation, conforme au standard D , notée ID D ( m ) :TO->DTO, identité en un modèle rn: P -* A (de sorte que son affaiblissement soit l'identité en l'affaiblissement ntoô de TO , dans la catégorie p). Ainsi, on dispose de la catégorie (voir la Note 6) MODD ( P, A ) dont les objets sont les modèles de P vers A et dont les flèches sont les transformations, conformes au standard D , entre ces modèles (et où "la composition est celle des affaiblissements") ; on l'appelle la catégorie, conforme au (A-)standard D , des modèles de P vers A (puisque, par construction, on a : OB ( MOD D ( P , A ) ) = ENSMOD (P,A)). Si A est une catégorie et si D et D' sont deux A-standards (catégoriques) de transformations, on dit que d = ( D , h, Y , D') CL 14 ELEMENTS DE THEORIE DES PATCHWORKS (I) est un A-protocole (fonctoriel) de comparaison, allant de D D 1 , si (on pourra se reporter au Tableau 10, ci-dessous) : vers PATCH (D') Tableau 10 — h : PATCH ( D ) ~> PATCH ( D' ) patchworks, est un homomorphisme entre — on a UNIV ( D ) E UNIV ( D' ) et UNIV ( D' ) 3 UNIV ( D ) , — v : FONCT ( D ) -> FONCT ( D' ) est une transformation naturelle (en identifiant FONCT ( D ) : ( SUPP ( Ecat ) ) o p ^ UNIV ( D à un foncteur à valeurs dans UNIV ( D' )-Patch — on a l'égalité : )-Patch ), h o COAFF ( D ) = COAFF ( D1 ) o j / ( EOB ) Par conséquent, si t' = (TO'I, n', TO'* ) : TO'I ->D' m'2 est une transformation, conforme au standard D ' , entre les deux modèles TO'I ,TO2: PATCH ( D' ) -> A , on constate immédiatement que i'-dft = (i»'i o h , n'o V ( E F L ) , TO2oh) : m\ oh -> D TO2oft est une transformation, conforme au standard D , entre les deux modèles (composés par h ) TO'I O h, m 2 o h : PATCH ( D ) -• A (on pourra se reporter, de nouveau, au Tableau 10, ci-dessus). CL 15 ELEMENTS DE THEORIE DES PATCHWORKS (I) Clairement, on définit ainsi un foncteur (voir la Note 6) : MOD d (h , A) : MOD D • (PATCH(D') , A) - MOD D (PATCH(D) , A) ; on l'appelle le foncteur modèle sous-jacent par (A-)protocole d. h , conforme au Notes N o t e 1. On raisonne d a n s un modèle de la théorie des ensembles de Zermelo-Praenkel, avec axiome du choix et axiome des univers. En particulier, si sli est u n univers, nous disons d'un ensemble qu'il est 'li-petit s'il est élément de l'univers 'Il. De même, nous disons d'une structure (par exemple, d'une catégorie) qu'elle est Qi-petite (resp. localement Qi-petité) si tous (resp. "certains") des ensembles qui la constituent sont <7*-petits. Ainsi, nous ne raisonnons pas dans un modèle de la théorie des "ensembles et classes", Autrement dit, nous à ne la Bernays-Gôdel-Von Neumann. procédons pas aux distinctions (habituelles) entre structures (par exemple, catégories) petites et structures qui ne le seraient pas (ou qui ne seraient que "localement" petites). Cependant, du point de vue que nous adoptons, on dispose d'une assez bonne interprétation de cette hiérarchie des "tailles" (du moins, pour l'usage qu'on en fait, usuellement) dès que l'on se donne deux univers 'Il et ?/ tels que 'Il G »?/ et Q/ 2 'Il : les ensembles ^ - p e t i t s y jouent le rôle de "tous" les ensembles et les ensembles ?/-petits celui de "toutes" les classes et, de même, les structures (localement) ^ - p e t i t e s y jouent le rôles de toutes les structures (localement) petites et les structures ?/-petites celui de "toutes" les structures "grosses" (i. e. sur des classes). N o t e 2. On rappelle qu'un graphe (partiellement) à composition G est constitué par : — un ensemble (re-voir la Note 1) d'objets OB ( G ) , — une partie OBID ( G ) de OB ( G ) , dite ensemble des objets identifiés, — un ensemble de flèches FL ( G ) , CL 17 ELEMENTS DE THEORIE DES PATCHWORKS (I) — une partie FLCOMP ( G ) de F L ( G ) X F L ( G ) , dite ensemble des couples composables de flèches, ou encore des couples de flèches composables, — une application sélection des domaines : DOM ( G ) : FL ( G ) -> OB ( G ) , — une application sélection des codomaines : CODOM ( G ) : F L ( G ) — O B ( G ) , — une application sélection des identités : SELID ( G ) : OBID ( G ) — FL ( G ) , — une application composition : COMP ( G ) : FLCOMP ( G ) -> FL ( G ) , et ce, de sorte que : — pour tout objet identifié G , on a : DOM ( SELID ( G ) ) = G = CODOM ( SELID ( G ) ) , — pour tout couple ( g ' , g ) de flèches composables , on a : DOM ( g' ) = CODOM ( g ) , (il est donc nécessaire que deux flèches soient consécutives être composables mais ce n'est pas, en général, suffisant), pour — pour tout couple ( g ' , g ) de flèches composables, on a : DOM ( g' • g ) = DOM ( g ) ) et CODOM ( g' • g ) = CODOM ( g' ) , (en posant, évidemment, COMP ( g 1 , g ) = g1 • g ), — pour tout objet identifié G et toute flèche g tels que DOM ( g ) = G (resp. CODOM ( g ) = G ), le couple de flèches ( g , SELID ( G ) ) (resp. ( SELID ( G ) , g ) ) est composable et on a : g • SELID ( G ) = g (resp. SELID ( G ) • g = g ) . En particulier, on dit qu'un tel graphe à composition G est identitaire si tout objet y est identifié, i. e. si OBID ( G ) = O B ( G ) . Par exemple, on voit que : — un graphe (au sens de (C.F.W.M.), notamment) s'identifie à un graphe à composition où l'ensemble des objets identifiés est minimal (i. e. vide), ainsi que celui des couples de flèches composables, — un graphe orienté (au sens, standard, de (C.A.S.T.), par CL 18 ELEMENTS DE THEORIE DES PATCHWORKS (I) exemple) s'identifie à un graphe à composition où l'ensemble des objets identifiés est maximal et, ceci acquis, où celui des couples de flèches composables est minimal, — il est, dès lors, loisible d'appeler graphe (partiellement) à identités u n graphe à composition où l'ensemble des objets identifiés est quelconque, mais où, ceci étant, l'ensemble des couples de flèches composables est minimal (de sorte que les graphes et les graphes orientés en sont des cas particuliers "extrêmes" et "opposés"), — les graphes multiplicatifs de (C.A.S.T.) (encore appelés graphes compositifs en (C.Q.C.E.)) s'identifient aux graphes à composition ayant des ensembles d'objets identifiés maximaux (et des ensembles de couples de flèches composables quelconques), i. e. aux graphes à composition identitaires, — les catégories s'identifient aux graphes à composition ayant des ensembles d'objets identifiés maximaux, des ensembles de couples de flèches composables maximaux, ainsi qu'une composition associative. En tout état de cause, il est facile de définir ce qu'est u n foncteur d'un graphe à composition vers un a u t r e : il doit évidemment commuter aux opérations sélection des domaines et sélection des codomaines, aux objets identifiés et à l'opération sélection des identités, aux couples de flèches composables et à l'opération de composition. E n particulier, on définit sans difficulté le foncteur identité en un graphe à composition, ou encore le foncteur composé de deux foncteurs consécutifs e n t r e graphes à composition. De même, il est aisé de définir ce qu'est une transformation naturelle entre deux foncteurs, d'un graphe à composition vers une catégorie, en procédant par simple analogie avec le cas - usuel où le graphe à composition domaine est une catégorie (par contre, ce serait beaucoup plus délicat si c'était la catégorie co-domaine qu'on remplaçait par un graphe à composition). CL 19 ELEMENTS DE THEORIE DES PATCHWORKS (I) N o t e 3 . Pour simplifier, on peut se contenter de définir les patchworks de degrés finis (voire les patchworks de degré fini fixé), i. e. se limiter à une récurrence ordinaire, en considérant que l'ordinal n > 0 de la définition générale est seulement u n entier. De la sorte, il apparaît que les figures attachées à u n patchwork de degré fini l'entier n > 0 sont toutes de degrés < n , donc majorés par n - Cependant, dans la pratique, même si on n e s'autorise à attacher aux patchworks utilisables que des figures de degrés finis, cette clause de majoration peut être trop contraignante. Dans ce cas, il convient de "pousser" la récurrence (au moins) jusqu'à l'ordre Ko (compris). Ainsi, les figures attachées aux patchworks de degrés 0 , à partir de ceux dont les degrés sont égaux à des ordinaux strictement plus petits. Contrairement à notre présentation (que nous avons choisie notamment pour cette raison) ceci nécessiterait deux constructions différentes, selon que l'ordinal n a un prédécesseur ou est limite (mais c'est sans doute en cela que cette autre présentation paraîtrait plus classique). Cependant, partant de notre présentation, on définit facilement (et nous laissons ce soin au lecteur) les triangles, les cônes et les CL 20 ELEMENTS DE THEORIE DES PATCHWORKS (I) patchworks de degrés strictement inférieurs à un ordinal n > 0 (au même t i t r e que les figures de degrés < n , dont nous avons explicitement besoin dans notre induction), puis les triangles, les cônes, les figures et les patchworks de degré égal à u n ordinal n>0. N o t e 4. Supposons que 'Il est un univers et que A est une catégorie ^ - p e t i t e (alors, pour tout graphe à composition '1ipetit G , on note ENSFONCT ( G , A) l'ensemble - qui est '7/-petit - des foncteurs de G vers A ) . Si P est un patchwork ^ - p e t i t et si F est une figure qui lui est attachée (pour laquelle on pose C = C O N E ( F ) , 1= INDEX ( C ) , Z = SOMMET(C) objet 1 de I, .QI = O P P I ( C ) successivment : et, pour tout et ^ I = P R O J I ( C ) ), alors on peut construire, pour tout objet 1 de Z, le produit fibre (dans 'li-Ens ) représenté par le diagramme commutatif suivant : pi y \ pi ENSMOD ( A , A ) SUPP ( ENSMOD rv. ENSFONCT (SUPP (*2i),A) SUPP( ENSFONCT (SUPP Ainsi, on dispose (£A) d'un (DA) cône p = ( p i : X i -+ ENSMOD(£, A))ieIap ) inductif et, comme d'applications 'Il Ens est à colimites d'indexations *7/-petites, il existe une unique application COFACT (p) : COLIM ( X Ï ) { G r * -> ENSMOD ( E, A ) rendant, tout objet 1 de J , le diagramme ci-dessous commutatif : CL 21 pour ELEMENTS DE THEORIE DES PATCHWORKS (I) COFACT(p) COUM (XOi s / — > ENSMOD (LA) Alors, connaissant la construction des colimites ^/-petites dans 'liEns, on voit qu'un modèle m': E -* A , i. e. un élément m' G ENSMOD ( E, A) , satisfait C si, et seulement si, il possède un unique antécédent par COFACT ( K ) . N o t e 5- On rappelle (voir (I.T.S.C.) e t / o u (E.T.S.A.) e t / o u (C.Q.C.E.)) qu'une esquisse E est constituée par : — un graphe à composition SUPP ( E ) , appelé le support de E, — un ensemble (voir la Note 1) PRDIST ( E ) de cônes projectifs de SUPP ( E ) , dits distingués, — un ensemble INDIST ( E ) de cônes inductifs de SUPP ( E ) , dits distingués, (on montre facilement que toute esquisse s'identifie à un patchwork de degré < 2 , mais ceci est sans importance ici). Dans ces conditions, si A est une catégorie, on dit que p = (E, (j>,A) est un modèle de E vers A, et on note p : E -> A , si : — : SUPP ( E ) -* A est un foncteur (dont on dit, également, qu'il définit p ), qu'on appelle le support de p et qu'on note 4>= S U P P (p), — transforme tout cône projectif distingué de E en un cône limite projective dans la catégorie A, — transforme tout cône inductif distingué de E en un cône limite inductive dans la catégorie A . En particulier, l'esquisse Ecat (dite esquisse des catégories, bien que nombre d'autres mériteraient cet intitulé) est définie comme suit : CL 22 ELEMENTS DE THEORIE DES PATCHWORKS (I) — son support est le graphe à composition engendré par le graphe à identités (re-voir la Note A) représenté ci-dessous et l e s équations qui suivent : o QCOMP ÎOOM Ec ETCOMP ] CODOM e DOM • e SELID - ID ( E OB ) - e CODOM • e SELID , e DOM • e i = e = e CODOM • e 2 e DOM • e COMP = e DOM • e 2 , e CODOM • ecoMP = e CODOM • , e i , e i • j DOM = ID ( E F L ) , e 2 • j DOM = eSELID • eDOM , e 1 • j CODOM = e SELID • e CODOM > eo • j CODOM = ID ( E R ) , e COMP • j DOM = ID ( E FL ) , e COMP • j CODOM = ID ( E R_ ) , e 2 • e' 1 = e1 = e 1 • e' 2 , e i • e'ûcoMP = ecoMP • e ' i , e 2 • e' GCOMP = e 2 • e' 2 , e 1 • e' DCOMP = e 1 • e' 1, e 2 • e 1 DCOMP = e COMP • e' 2, — les deux cônes projectifs représentés distingués : CL 23 ci-dessous sont ELEMENTS DE THEORIE DES PATCHWORKS (I) Eocoi ETDOMP — aucun cône inductif n'est distingué. Alors, si 'Il est u n univers, à t o u t modèle p : Ecat -• 'li-Ens clairement associée u n e catégorie CAT ( p ) est (évidemment '11- petite), pour laquelle on a (notamment) : — OB ( CAT ( p ) ) = p ( EOB ) , — FL(CAT(/J)) = /J(EFL), — pour t o u t (objet) C e OB ( CAT ( p ) ) , on a : I D ( C ) = /i(eSELID)(C), — pour tout(e) (flèche) c E FL ( CAT ( / i ) ) , o n a : DOM ( c ) = p ( epoM ) ( c ) et CODOM ( c ) = p ( ecoDOM ) ( c ) , — pour toutes flèches (consécutives) c : C -> C et c' : C -• C " , on a : c' • c = / j ( ecoMP ) ( < c ' , c > ) , lorsqu'on désigne par < c ' , c > l'unique élément de p ( ECCOMP ) tel que / j ( e i ) ( < c ' , c > ) = c' / j ( e 2 ) ( < c l , c > ) = c (cet et élément existe et est unique, puisque le diagramme commutatif cidessous est u n profuit fibre dans la catégorie 'li-Ens : e ^(ECCOMP) V<£ù/ C* € ji(EFU) \ fîtes) C € JI(EFO Jl(e0OM) >v y \i (ÔCODOM) C€*I(EOB) )- Usuellement, il n'y a aucun inconvénient à exciper de "la catégorie CL 2 4 ELEMENTS DE THEORIE DES PATCHWORKS (I) p " , i. e. à identifier le modèle p : Ecat -* 0.1-Ens (ou même son foncteur support) à la ("vraie") catégorie CAT ( p ) qu'il définit. N o t e 6. Dans la définition des A-standards catégoriques, on peut évidemment substituer à l'esquisse (de catégories) pointée (par son objet des objets) ( Ecat, EOB ) une (quelconque) autre esquisse pointée (par un - quelconque - de ses objets) (E, E ) . On obtient de la sorte des "A-standards de structures" (autres que celles de catégories) dont l'ensemble ENSMOD (P ,A) peut être muni (i. e. peut-être l'ensemble "des éléments de sorte E " sous-jacent). De même, on peut définir les "A-protocoles de comparaison entre structures" (autres que des foncteurs entre catégories) dont l'application : ENSMOD (h , A ) : ENSMOD ( P ' , A ) -* ENSMOD ( P, A ) peut être l'application sous-jacente ("de sorte E " , i. e. entre les ensembles d'éléments de sorte E sous-jacents). Plus généralement, on pourrait même substituer à ces esquisses des ... patchworks (sans pour a u t a n t créer de cercle vicieux ! ). Bibliographie (C^A.S/T.) (C.F.W.M.) (C.Q^C.E.) (E.T.S.A.) (I.T.S.C.) (S.C.S.T.) C. E h r e s m a n n , Catégories et Structures, Dunod (1965). S, M a c L a n e , Catégories for t h e Working Mathematician, Springer (1971). C. L a i r , Catégories Qualifiables et Catégories Esquissables, Diagrammes 17, Paris (1987). C. E h r e s m a n n , Esquisses et Types des Structures Algébriques, Bull. Instit. Polit. Iasi, XIV (1968). C. E h r e s m a n n , Introduction to t h e Theory of Structured Catégories, Techn. Report 10, Univ. of Kansas, Lawrence (1966). C. L a i r , Trames et Sémantiques Catégoriques des Systèmes de Trames, Diagrammes 18, Paris (1987). Table Introduction p. 1 1. Patchworks et homomorphismes p. 3 2. Modèles et transformations p. 9 Notes p. 17 Bibliographie p. 27 UNIVERSITE PARIS 7 U.F.R. de Mathématiques Tours 45-55-5ème étage 2, place JUSSIEU 75251 PARIS CEDEX 05 FRANCE