D IAGRAMMES F. C URY Complétion et complétude selon H. Andreka et I. Nemeti Diagrammes, tome 28 (1992), p. 1-80 © Université Paris 7, UER math., 1992, 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 C O M P L E T I O N E T 26 , 1992 C O M P L E T U D E S E L O N H. A N D R E K A E T I . N E M E T I <3fc> petir F. Guiry <**> (*) in "Generalization of the Concept of Variety and Quasi-Variety to Partial Algebras, through Category Theory", Diss. Math. CCIV, Varszawa, 1983, (**) rapport de stage du D.E.A. d'Informatique Fondamentale, préparé sous la direction de P.-L. Curien, Paris, Septembre 1986. .M.6. eUB. CLA8S. : 0 3 Q 3 0 , 0 8 C 9 9 , 19 A 2 0 INTRODUCTION En théorie classique des modèles, les toutes premières considérations sont, nécessairement, les suivantes: - une classe B de formules (d'un certain type, donné) étant fixée, on décrit la classe Modèles de E de tous ses modèles (d'un certain genre, donné), - une classe A de modèles (d'un certain genre, donné) étant fixée, on décrit la classe Formules de A de toutes les formules (d'un certain type, donné) valides dans tout modèle appartenant à A. On peut donc effectuer les deux "aller-retour" suivants: - A étant donnée, on prend A = Modèles de (Formules de A) (et on a toujours A Ç. A\ ), - B étant donnée, on prend _ ¥ = Formules de (Modèles de B) (et on a toujours B C E ! ) . Ainsi, on obtient deux opérateurs: - l'un (que la pratique incite à appeler de complétion), sur la classe des classes de modèles (du genre donné), - l'autre (qu'on peut appeler par complétude), sur la classe des classes de formules (du type donné). Alors, deux problèmes (au moins!) se posent: (i) quel type de formules et quel genre de modèles faut-il choisir pour que A -» A et/ou E -> E soient des fermeture^ (ii) par quelles constructions, internes à la classe de tous les modèles (du genre donné), obtient-on J à partir de A et/ou par quelles constructions, internes à la classe de toutes les formules (du type donné), obtient-on 1" à partir de E ? Dans le cadre "restreint" des algèbres (d'une signature donnée), le théorème de Birkhoff (ou ce que nous convenons d'appeler comme tel) fournit une solution aux problèmes (concernant les modèles) posés en (i) et (li). Ainsi, si l'on choisit: - pour (genre de) modèles, les algèbres d'une signature donnée, - pour (type de) formules, les "équations quantifiées universellement" (ou •identités"), alors, A-* est bien une fermeture et 1 s* obtient en saturant A par: - produits, - sous-algèbres, - images homomorphes. Dans le même cadre, les mêmes choix fournissent une solution (que nous convenons d'appeler théorème de complétude algébrique) aux problèmes (concernant les formules) posés en (i) et (ii). Ainsi, dans ces conditions, E-Œ est aussi une fermeture et Ê s'obtient à partir de E en effectuant toutes les ré-écritures possibles des formules (i. e. des équations) appartenant à B, au moyen de règles d'inférence particulières (i. e. par "déductions équationnelles"). Dans le cadre (initial) plus large de la théorie classique des modèles, i. e. si 1'on choisit: - pour modèles, les interprétations d'un langage, - pour formules, les énoncés de la logique du 1er ordre (i. e. les formules closes, écrites à l'aide de variables, du langage, des connecteurs et quantificateurs usuels et, éventuellement, de deux valeurs de vérité 0 et 1), les choses ne se passent pas complètement aussi bien. On dispose en effet du théorème de consistance qu'on peut énoncer sous la forme suivante: on ne peut pas déduire, par complétude, d'un ensemble d'énoncés E deux énoncés contradictoires ssi E admet au moins un modèle, ou encore: (0 <==* D ^ E ssi Modèles de E f 0 . Ce théorème de consistance une fois établi, on en déduit alors le théorème de complétude logique (c'est pourquoi on les confond, volontairement, souvent), i, e. une solution aux problèmes (concernant les énoncés) posés en (1) et (ii): - l'opérateur B-*B est bien une fermeture et E s'obtient à partir de B en effectuant toutes les ré-écritures possibles des énoncés appartenant à E, au moyen de règles d'inférence un peu plus nombreuses que précédemment ("les déductions logiques"). Par contre, s'il est trivial de vérifier que A -> X est bien une fermeture, on ne sait pas caractériser toutes les constructions qui permettent d'obtenir J à partir de A. Andréka-Hémeti obtiennent, dans un cadre intermédiaire entre le "restreint" et le "large", évoqués plus haut, tant un théorème de Birkhoff généralisé qu'un théorème de complétude, "essentiellement algébriques", et ce, en choisissant: - pour modèles, soit les algèbres, soit les algèbres partielles d'une signature, soit encore les modèles - i. e. les interprétations - d'un langage, pour formules, essentiellement des implications entre formules atomiques "quantifiées universellement". Ils obtiennent ce théorème de Birkhoff généralisé comme application d'une version catégorique de la situation usuelle: c'est que saturer A par produits, sousalgèbres, images homomorphes, est un cas particulier de saturation, dans une "bonne catégorie" (notamment munie d'un système de factorisation et d'une classe particulère d'épimorphismes H ), d'une classe d'objets par ... produits ("catégoriques"), sources des flèches de S , buts des flèches de H . Cependant, leur version ne va pas jusqu'à donner un statut "catégorique" aux formules même infinitaires, et encore moins aux formules finitaires. ITous montrons en détail que ceci est possible en poussant (un peu) plus loin les idées de Andréka-Héméti. Et nous détaillons avec soin leur procédé de traduction de ce cadre en le cadre usuel. Le théorème de complétude essentiellement algébrique qu'ils obtiennent n'est pas, lui, catégorique: il n'est établi que dans le cadre "intermédiaire" évoqué précédemment. Tout en re-situant le problème, nous n'avons pas cru devoir ré-écrire en détail ce qui n'avait pas besoin de l'être parce que se trouvant déjà dans Andréka-Bémeti. Par contre nous suggérons un cadre catégorique qui pourrait convenir. PRELIMINAIRES 0.0. 0.0.1. COISIDBRATIOIS DE -TAILLES". Classes et ensembles. Pour la précision de la chose, disons que nous raisonnons dans un modèle Ï.B.G de la théorie des "ensembles" , i. e. avec des classes et des ensembles. Alors, un ensemble est une petite classe. Et l'on peut parler de la classe de tous les ensembles, ou de tous les petits groupes . .. Nous userons abondamment des notations ensembllstes usuelles ... y compris pour les classes (par exemple pour écrire que tel élément x est dans la classe ï , nous noterons xeX . . . ) . 0.0.2. Petites catégories. On dira qu'une catégorie est petite si, et seulement si, la classe de ses morphismes (et donc aussi de ses objets) est petite, i. e. est un ensemble. De même, une limite projective ou inductive sera dite petite si, et seulement si, elle est indexée par une catégorie petite, i. e. si, et seulement si, c'est "la" limite d'un foncteur F: I-*C , où I est petite. Lorsque ce n'est pas explicitement précisé, on ne fait pas d'hypothèse sur la taille des catégories considérées (i. e. on ne suppose pas qu'elles sont petites). 0.1. IOTATIOIS GElBfiALES POUR LBS CATEGORIES. Dans tout ce 0.1. , on suppose que 0.1.1. C est une catégorie. Objets, morphismes et composition. Pour tout morphisme f;C-*C , on appelle C son domaine codomaine. Alors, on note C = dom(f) et C* = codom(f). et C son 12 Pour tout objet identité associé à C . C de C , nous notons Idc:C-*C le morphisme Enfin, nous écrivons la composition dans l'ordre habituel (i. e. comme pour la composition des applications). Ainsi, le diagramme suivant est-il commutatlf: 0.1.2. Classes d'objets et de morphismes. Bous notons Ob(C) , ou Ob C , ou même Ob (s'il n'y a pas risque d'ambiguïté) la classe de tous les objets de C . Hous notons Mor(C) , ou Mor C , ou même Mor (s'il n'y a pas risque d'ambiguïté) la classe de tous les morphisme s de C. De même, nous notons Epi(C) (resp. Mono(C) , Iso(C) ) , ou encore Epi (resp. Mono , Iso ) , s'il n'y a pas risque d'ambiguïté, la classe de tous les épi morphisme s (resp. monomorphismes , isomorphismes ) de C . Les classes de morphismes que nous aurons à considérer ("génériquement") seront supposées saturées par isomorphismes. 0.2. 0.2.1. SYSTEMES DE FACTORISATIOI. Définition des systèmes de factorisation. Soient H et S deux classes de morphismes d'une catégorie On dit que est un système de factorisation C. de C si, et peut se décomposer en un élément h de seulement si: (i) tout morphisme suivi d'un élément f s de C de Si H 13 (ii) E O S = Iso , (iii) (propriété du "diagonal fill-in") pour tout carré commutatif (y,h,s,x) de C , où heH et seS , il existe un unique morphisme k vérifiant s.k = y et k.h = x , i. e. rendant commutatif le diagramme: hc£T > X \|/ * X •> seS 0.2.2. Propriétés générales des sytèmes de factorisation. Soit un système de factorisation de la catégorie C. Il est aisé d'établir les propriétés qui suivent. Proposition 0. Les classes H et S contiennent la classe {Idc/C€0b>, (Propriété bien évidente, vu la condition (ii), mais souvent utilisée.) H suivi Proposition 1. La décomposition d'un morphisme quelconque d'un élément de S est unique à isomorphisme près. en un élément de (Vérification classique utilisant l'unicité imposée par la propriété de "diagonal fill-in".) Proposition 2. La classe H est entièrement déterminée par la classe S (et vice versa) par: - H est la classe de tous les morphismes h pour lesquels tout carré commutatif (y,h,s,x> tel que s e S possède une unique "diagonale" k rendant commutatif le diagramme: h se S 14 Proposition 3. On a H.E = H et S.S = S . (Ceci se déduit des propositions 0 et 2. ) 0.2.3. Exemple. Dans la catégorie Ens des ensembles, n'est pas, en général, un système de factorisation). 0.3.3. Epimorphismes relatifs et monomorphismes relatifs. On dit que f est un épimorphisme relatif si, et seulement si: - f est un épimorphisme, - pour tout morphisme g vérifiant codom(g) = codom(f) , il existe des morphismes f* et g1 tels que f soit un épimorphisme et f.g' = g.î* : f'eEpi ]/ S On note Hr la classe des épimorphismes relatifs. On dit que m est un monomorphisme relatif si, et seulement si: - m est un monomorphisme, - pour tout épimorphisme relatif f et pour tout carré commutatif (x,f,m,y) , il existe un unique morphisme k vérifiant m. k = x et k. f = y : feHr 16 On note Sr la classe des monomorphismes relatifs. Ainsi, Sr est définie en imposant que le couple de classes (Hr,Sr) vérifie la propriété du "diagonal fill-in" (mais, pour autant, n'est pas, en général, un système de factorisation). 0.3.4. Les aonomorphismes forts. On dit que m est un monomorphisme fort si, et seulement si: - m est un monomorphisme, - pour tout épimorphisme f et pour tout carré commutatif (x,f,m,y) , il existe un unique morphisme k vérifiant m.k = x et k.f = y : feEpi > On note S» (avec • comme "strong") la classe des monomorphismes forts. Comme précédemment, on remarque qu'elle est définie en imposant que le couple de classes (Epi,S.) vérifie la propriété du "diagonal fill-in" (mais, pour autant, n'est pas, en général, un système de factorisation). 0.3.5. Quelques propriétés de ces classes remarquables. Si C est une catégorie telle que les couples , et sont des systèmes de factorisation (ils vérifient de toute manière la propriété de "diagonal fill-in"), alors on prouve que: (i) si H est une classe d* épimorphismes, tout H e (Iso,Hc , H.,Hr,Epi) vérifie la condition (DIAG) suivante: + pour tout morphisme heiT et pour tout morphisme f , si f.heH , alors feH (ce qu'on peut écrire schématiquement par: (DIAG) ( i i ) on a Iso C Hc C H. C Hr C Epi f€H et Mono D S r 3 S O Iso ) 17 lotons que les hypothèses précédentes peuvent être redondantes (ainsi, par exemple, l'inclusion Hr C Epi est valable dans toute catégorie C ; de même, la condition (DIAG) est vérifiée dans toute catégorie C , dès que H = Epi , la classe H de morphlsmes pouvant être alors quelconque). 0.4. GEIERATIOI. Dans tout ce 0.4. , on désigne par 0.4.1. C une catégorie quelconque. Catégorie de décomposition. Soit X une classe de morphlsmes de C et e:E-*E' un morphisme de C . On note Decx(e) (ou plus simplement Dec(e) , s'il n'y a pas risque d'ambiguïté sur la classe X ) la catégorie de (ou des) décompositlonis) de e , i. e. la catégorie telle que: - ses objets sont, d'une part dom(e) et d'autre part les couples (y:C-*E' ,x: E-*C) de flèches de C telles que y.x = e , - ses flèches sont les ((y,x) ,x) :dom(e)-*(y,x) . Alors, on dispose d'un foncteur canonique: decx(e): Decx(e) -> C (y,x) -* C = dom(y) = codom(x) ((y,x),x) -» x (foncteur que l'on notera plus simplement d'ambiguïté sur X ). 0.4.2. dec(e) , s'il n'y a pas risque Sous-classe doit-engendrant une classe d'épimorphismes. Soit X' une classe d'épimorphismes de C et X une sous-classe de X' . On dit que X dom-engendre X' si, et seulement si: - pour tout morphisme e;E-*E' appartenant à X' , l'objet E' est limite inductive (c'est-à-dire somme fibrée) du foncteur canonique decx(e): Decx(e)-*C avec (v = y) 1 (un tel g , s'il épimorphisme). On note alors: 1.1.2. existe, évidemment unique, puisque e est un C 1= e. Modèles. Soit E une classe d'épimorphismes de On dit qu'un objet C si, et seulement si: - C valide tout e e E. On note alors Mod(ls) 1.1.3. est de C valide C E ou est un modèle la classe de tous les modèles de de E. Exemples (où l'on volt apparaître des formules...). On prend pour C la catégorie Ab des (petits) groupes abéliens: les épimorphismes y sont exactement les homomorphismes surjectlfs. Un groupe abélien G valide l'homomorphisme "passage au quotient": e, : Z. -* (£/2£) si, et seulement si, il valide (au sens usuel) l'équation 2x = 0 (i. e. si, et seulement si, tous ses éléments non nuls sont d'ordre 2 ). De même, un groupe abélien G valide 1'homomorphisme canonique (induit par l'inclusion de 42. dans 2£) : e2: Z/4Z. -* (£/2£) * C (£/4£)/ (2 (£/4£)3 si, et seulement si, il valide l'implication 4x = 0 => 2x = 0 (i. e. si, et seulement si, aucun de ses éléments n'est d'ordre 4 ). 22 Plus généralement encore, G valide 1'homomorphisme canonique (induit par l'inclusion de < 4xi-6Xi-2 / ieK > dans < 2x±-3xi-2 / ici > ): () A e3: Z. / ' * (4Xi=6xi^) ici (où, si E ) E () A A (2L / '* (4Xi=6Xx«))/ '\ (2Xi=3xi^2) ici ici est un ensemble, Z.) A/ x -* Z. / (2xt=3Xi«> ici G valide l'implication ^M4x±=6x^2) =* A (2Xi=3xi^-2). ici iel Exemple (où l'on continue à voir apparaître des formules). On prend pour C la catégorie des (petites) catégories non (nécessairement) associatives (i. e. où l'on ne requiert pas l'axiome d'associativité). Les homomorphismes (i. e. les foncteurs) surjectifs en sont des épimorphismes (mais la réciproque est fausse). Soit E la catégorie non associative: b ou: di=b.a et soit E1 catégorie! ) : d2=c.b ti=c.di=c.(b.a) t2=d2.a=(c.b).a la catégorie non associative (mais il se trouve que c'est une "vraie" 23 ou: d'i = b'.a' d'2 = c'.b' t' = c'.d'i = c'.(b'.a') t' = d'2.a' = (c'.b').a'. Un foncteur de E vers une catégorie non associative A s* identifie à la donnée d'un quelconque triplet (f,g,h) de morphlsmes consécutifs de A et un foncteur de Ef vers A s'identifie à la donnée d'un tel triplet, mais vérifiant (h.g).f=h.(g.f). Dans ces conditions, une catégorie non (nécessairement) associative A valide le foncteur "passage au quotient": e: E->E-=E/((z.y).x = z. (y.x)) si, et seulement si, c'est une "vraie" catégorie. 1.1.5. Exemple (où l'on voit apparaître des formules un peu particulières). On prend pour C la catégorie des (petits) graphes multiplicatifs. Rappelons que la structure de graphe multiplicatif est un peu plus faible que celle de catégorie: on n'y requiert ni l'associativité de la composition, ni que deux flèches consécutives soient nécessairement composables. Les homomorphismes (i. e. les foncteurs) surjectifs y sont des épimorphismes (mais la réciproque est fausse). Soit et soit où Bf E le graphe multiplicatif: le graphe multiplicatif (mais il se trouve que c'est une catégorie!): c=b.a . Un graphe multiplicatif (où A validera 1'épimorphisme "passage au quotient* e: B-)B,=B/(dom(y)=codom(x) =* 3ly.x) al y.x signifie "le composé y.x est défini") 24 si, et seulement si, A est, en fait, une catégorie non (nécessairement) associative (voir 1.1.5.). 1.2. PROPRIETES DE LA CLASSE Dans tout ce 1.2., E Mod(£>. désigne une classe d'épimorphismes de 1.2.1. Propriété 1. Si E est une classe alors la classe Mod(ii) est stable par (petits) d'épimorphismes produits. C. de la catégorie C , Preuve. Soit (Ci)icz une famille d'objets de C , indexée par un ensemble I et telle que tous les C± valident E et admettent un produit C ayant pour famille de projections (pi:C-»Ci)i«x. Soit ecE et prouvons qu'alors C valide e. Soit f: E->C . Pour tout ici , comme Ci valide e , il existe g± tel que gi.e=px.f .Le morphisme g , défini par: Yiel px.g=gi vérifie alors: g.e=f car: Viel pi.g.e=gx.e=px.f . f E ^, C Ainsi C valide e . Fin de la preuve. On résume la propriété 1 précédente en écrivant symboliquement: P Mod(JB) C Mod(J5). 1.2.2. Propriété 2. Si si est un système E est une classe d9épimorphismes de la catégorie de factorisation de C et si E CB , alors la C , classe 25 Mod(E) est stable sous l'action de et C'elLodiE) , on a CeULodiE). S , i . e., Preuve. S o i t un t e l se S , s o i t Soit C dès que eeE s:C->C appartient e t prouvons q u ' a l o r s C à S valide e . Puisque morphisme f:E-*C . Comme valide e , il existe h tel que: s.f = h.e . du "diagonal fill-in" assure l'existence ECE, la propriété g vérifiant: g.e=f ( et d'un s.g=h ). eeE Ainsi, C valide e . Fin de la preuve. On résume la propriété 2 précédente en écrivant: SHodiE) 1.2.3. C Mod(£>. Objets H-projectifs. La propriété 3 qui suit (en 1.2.4.) fait intervenir la notion d'objet H-projectif qu'il convient donc de rappeler. Désignons par H une classe d'épimorphismes de C . On dit qu'alors un objet E de C est E-projectif si: - pour tout morphisme il existe un morphisme le diagramme: h si, et seulement appartenant à H et pour tout morphisme f :E-*codom(h) , f':E-*dom(h) vérifiant h.f'=f , i. e. rendant commutatif *r • > ^\ heH • Un tel morphisme f n'est pas, en général, unique, ce dont on peut se convaincre facilement grâce à l'exemple suivant: dans la catégorie Ens des ensembles, choisissons pour classe H la classe de tous les épimorphismes (i. e. de toutes les surjections), alors tout objet de Ens est H-projectif ... en vertu de l'axiome du choix ... qui permet donc de choisir f parmi plusieurs (en général). 26 On note H-proj la classe des objets H-projectifs de la catégorie C 1.2.4. Propriété 3. Si B et H sont des classes d'épimorphismes de la catégorie C , si Dom(2D C H-proj Ci. e. si le domaine de tout eeE est un objet E-projectif de C )f alors la classe Mod(2D est stable sous l'action de H , i. e., dès que h:C->C appartient à H et CeMod(-fi) , on a C'cMod(B). valide Preuve. Soit un e . Soit f:E->C. E tel h € H , soit e e E étant et prouvons H-projectif, f se relève en un h.f'=f . Comme C valide e , il existe un morphisme g' vérifiant: g'.e=f«. Le morphisme g=h.g' vérifie alors: g.e=h.g«.e=h.f'=f . f qu'alors C tel que: EeH-proj heH Ainsi, C valide e . Fin de la preuve. On résume la propriété 3 précédente en écrivant: H Mod(JÏ) C Mod(JB). 1.2.5. Propriété fondamentale de Mod(£>, En regroupant les hypothèses et les conclusions des trois propriétés précédentes et en remarquant que: - Mod(E> C P Mod(B), - Mod(JS) C SMod(E> (car S 3 I s o Z) s i e s t un système de f a c t o r i s a t i o n ), - Mod(£> CE Mod(JB) , s i H D Iso , nous obtenons l a p r o p o s i t i o n qui s u i t . Proposition. Sï est un système de factorisation de la catégorie C , si E est une classe d' épimorphismes de C , incluse dans E, et si H est une classe d'épimorphismes de C t e l J e que Dom(E> C H-proj , alors la classe Mod(2D est stable sous l'action de H S? , i. e. on a: ES? Kod(E) C Mod(£> 27 et donc: ES? 1.3. BOUES CATEGORIES ET EXTEISIOIS LIBRES. On désigne toujours par 1.3.1. C une catégorie. Catégories à peu d'objets quotients. Si de Mod(J5) = Mod(£>, B-objets H est une classe de morphlsmes de quotients C , on dit que C est à peu si, et seulement si: - pour tout objet C de C , la classe des morphlsmes appartenant à ïï et de domaine C , considérés à isomorphisme près, est un ensemble. Cette condition sera, dans la pratique (i. e. dans les exemples que nous avons en vue), vérifiée pour toute catégorie algébrique C dès que l'on aura choisi BC Epi. Ce qui "justifie" la terminologie d' "objets quotients" adoptée ici. Cependant, dans d'autres cas, il serait préférable de la remplacer par "codomaines". 1.3.2. Catégories ayant suffisamment d'objets projectifs. Si suffisamment H d'objets est une classe d'épimorphismes de E-projectifs C , on dit que C a si, et seulement si: - pour tout objet C de C , il existe un objet H-projectif ( voir 1.2.3. ) X de C et un morphisme h:X-»C appartenant à H . Intuitivement, dans une catégorie algébrique, cette condition signifie que tout objet peut être présenté comme un certain quotient d'une structure libre. 1.3.3. Bonnes catégories. On dit que (C, H,) est une bonne catégorie (ou, s'il n'y a pas risque d'ambiguïté, que c'est simplement C qui est une bonne catégorie) si, et seulement si: - H 2) Iso est une classe d'épimorphismes de C , 28 E CEpi, C, e s t un système de f a c t o r i s a t i o n de C est à (petits) produits, C est à peu de £F-objets quotients, C a suffisamment d'objets H-projectifs, la condition (DIAG) suivante est vérifiée: appartenant à E et pour tout + pour tout morphisme h alors f€H (ce qu'on peut écrire morphisme f , si f.heH schématiquement par: feH (DIAG) 1.3.4. C et de C (i) Extensions libres. Soient E une classe de morphlsmes de C un objet de C. On dit qu'un morphisme f de relative à A si, et seulement si: feB , dom(f)=C morphisme y C , A C une classe d'objets de est H-extension libre et, pour tout morphisme x:C->Àe4 de C , il existe un tel que y.f=x , i. e. rendant commutatif le diagramme: feB keA (notons que (ii) y B C Epi ), est unique si pour tout morphisme un unique morphisme diagramme: f z de C tel que vérifiant la propriété (i), il existe f=z.f, 1. e. rendant commutatif le f ^ Alors, on note f=fr c " A et codom(f)=Frc" A (bien entendu, la propriété universelle précédente assure que f est unique à isomorphisme près, dès qu'elle existe). 29 1.3.5. Proposition (existence d'extensions libres dans une bonne catégorie). Si C est une bonne catégorie et si A est une classe d'objets de C , alors tout objet C de C engendre une E-extenslon libre f=fr c " A dont le codomaine Frc** est élément de S?A. Preuve. Pour tout x:C->Ax€/ , on choisit "la" décomposition x=Sx.h>. , où s>€lso tel que hx=o.hu« . La catégorie C étant à peu de IF-objets quotients, la classe X' est un ensemble et on considère "le" produit P= TTx.x* Bx et la famille (px)x«x« de projections associée. s^eS k*eA On désigne par g l'unique morphisme tel que: YxeX' px.g=hx . On décompose g en g=s.f , avec se S et feE . Prouvons, maintenant, que f=fr c M A . Pour ce faire, soit d'abord x:C-»Ax un morphisme tel que h>Ax (où l'on a posé codom(f)=B ) vérifiant y.f=x (pour simplifier, on suppose que x est le représentant de sa classe, choisi pour construire le produit P ); comme xeX' , le morphisme y=Sx.px.s convient bien puisque: Sx. p*. s. f=Sx. p><. g=Sx. hx=x . Ainsi, f vérifie la condition (i) de 1.3.4. . Supposons, maintenant, qu'un morphisme f' :c -* B* , élément de B , vérifie aussi cette condition (i) et prouvons qu'il existe alors un z:B'-*B tel que z.f'=f (f étant un épimorphisme, z sera nécessairement unique). Or, tout x de X se factorise par f : il existe donc un y*. vérifiant yx.f'=x . Comme yx.f'=Sx.hx , la propriété du "diagonal fill-in" assure l'existence d'un morphisme kx tel que Sx.kx=yx et kx.f'=hx . Considérons, maintenant, l'unique morphisme k vérifiant: VxcJ' px.k=kx. L'égalité k.f'=s.f , due au fait que: 30 IxeX' px.k.f'=kx.f,=:hx=px.g=px.s.f , permet d'utiliser la propriété du "diagonal fill-in": il existe un unique morphisme z:B'->B vérifiant s.z=k et z.f'=f . Ce z convient donc. Fin de la preuve. Remarquons que l'idée de base de cette preuve est tout à fait analogue à celle de la preuve du théorème d'existence de structures libres de C. Ehresmann ou de P. Freyd, 1.4. BOMBES CLASSES D'EPIMORPHISMES DAMS UIE BOIME CATEGORIE. La classe d* épimorphismes intervenant dans le théorème de catégorique doit vérifier de "bonnes" propriétés que nous introduisons ici. Maintenant, (C, H, ) 1.4.1. C Birkhoff désigne une bonne catégorie. La bonne classe canonique d'épimorphismes. On appelle bonne classe la classe: canonique *V.s={e:E->E' / eeB d'épimorphismes et de la bonne catégorie EeH-proj). Rappelons que E est déterminé de manière unique en fonction réciproquement: ainsi, la notation utilisée ne prête pas à confusion. La proposition de 1.2.5. assure alors que toute partie S de E de et II'HS vérifie: ES? 1.4.2. Mod(B)=Mod(,B). Bonnes classes primitives d'épimorphismes. On dit que BHS est une bonne classe bonne catégorie C si, et seulement si: - EHS C I'HS , - EUs dom-engendre ( v o i r 0 . 4 . 2 . ) E'HS . primitive d'épimorphismes de la 31 Motons que, s'il n'y a qu'une bonne classe canonique d'épimorphismes (c'est bien pourquoi nous l'avons qualifiée de canonique!), il peut y avoir plusieurs bonnes classes primitives d'épimorphismes (et E'n& en est toujours une ! ) . 1.4.3. Exemple. Reprenons l'exemple de 1,1.3. . Dans la catégorie C = Ab des (petits) groupes abéliens, on considère 1 ' homomorphisme e3 . Alors, la famille d'homomorphismes surjectifs (donc d'épimorphismes) "passages aux quotients": ( hx : dom(e 3 ) -> (dom(e3)) / (2x1=3x1+2 )I«&L dom-engendre es. En d'autres termes, un groupe abélien G valide valide tous les h x . Ce que l'on peut encore écrire: e3 si, et seulement si, il G != ( A (4Xi=6xi-2)) =* ( A (2xi=3Xi«)) ieE. ici si, et seulement si: G 1= ( A (4x1=6x1-2)) => (2xi=3xi.+2) pour tout ieï. 1.4.4. Proposition. Si KHS est une bonne classe primitive d'épimorphismes la bonne catégorie C , alors, pour tout e'eE'ns et pour tout objet de C , on a: - A 1= e* si, et seulement si, pour tout (ui,ei)eOb Dec(e') , A 1= e± . de A Preuve. Cette propriété est une banale transcription de la définition d'une somme fibrée. Supposons d'abord que A valide e' et prouvons qu'il valide ei , lorsque (ui,ei)eOb Dec(e') , Soit f:E-»À . Il existe alors g:E'-»A vérifiant g.e'=f . Définissant g± par gi=g.ui , nous avons: gi.ei=g.ui.ei=g.e'=f . Ainsi, A valide e± . i^v^^^-^ f e' \ ^ A 32 Réciproquement, supposons que A valide ei pour tout (ui,ei)eOb Dec(e') et prouvons que A valide e' .Soit f:E-»A. Pour tout i , il existe gi:codom(ei)-»A vérifiant gi.ei=f . Les composés gi.ei étant indépendants du 1 choisi, la famille (gi)i... détermine un unique g:E->A tel que: VI g.ui=gi . On a alors: g.e'=g.ui.ei=gi.ei=f . Ainsi, A valide e' . Fin de la preuve. 1.5. 1.5.1. classe on a: LE THEOREME DE BIRKHOFF DAMS UME BOMME CATEGORIE. Enoncé du théorème de Birkhoff catégorique. Si (C, H, <#,£>) est une bonne catégorie, si E-*s primitive d'épimorphismes et si A est une classe d'objets Hod (E^s(A)) (où l'on désigne par épimorphismes validés 1.5.2. = H S? est une bonne de C , alors A Ris(A) la sous-classe de EHS par tout élément de A , i. e. : JBhs(i) = < ee&s / YkeA Al=e > ) . constituée de ceux de ses Preuve du théorème de Birkhoff catégorique. a). La classe EH si A) étant une partie de classe canonique d'épimorphismes F H S , on a: ES PMod(&8(il) )=Mod(&e(i) ), comme c e c i a é t é vu en 1 . 4 . 1 . . D'autre part, par d é f i n i t i o n , on a A CHodiEnsiA)) , ce qui assure: E S? A CE S? Mod(£B vérifiant h*.f=h , puisque la condition (DIAG) assurera alors que ITeH . Or, pour ce faire, il suffit que B valide f . Le morphisme f étant, en fait, élément de E'HS , en notant Dec(f)= <(Ui,ei) / ici ) , nous savons que B validera f dès que B validera tous les ei. Il nous reste par conséquent à vérifier que B valide ei , si ±el ; ce que nous allons faire (puisque B est un modèle de EHS(A) ) en vérifiant que ei€&s(4). Par définition de Dec(f) , e±eEns . Soit, maintenant, keA et prouvons que A valide et . Pour ce faire, considérons fi:X-*A et exhibons un morphisme gi vérifiant gi.ei=fi. Comme keA t f± se factorise par f = f r x w A : i l e x i s t e donc un morphisme y* tel que y4.f=fi . Alors, le morphisme gi , défini par: gi=yi.ui , vérifie: gi.ex=yi.ui.ei=yi.f=fi. Ainsi, A valide e t , ce qui assure que e±eEts(A) h X ^ B keA Fin de la preuve. 2 . INTERPRETATIOJST DU BIRKHOFF CATEGORIQUE DANS LA C A T E G O R I E D E S A L G E B R E S T O T A L E S , LA C A T E G O R I E D E S A L G E B R E S FARTIELLES, LA CATEGORIE D E S MODELES. THEOREME DE 2.1. 2.1.1. DEFIMITIOM DBS CATEGORIES La catégorie T T , P , des algèbres totales. Z désignant une signature donnée, la catégorie Tz , ou plus simplement T , est la catégorie des (petites) Z-algèbres totales, c'est-à-dire que: - les objets de T sont les E-algèbres (totales), ayant pour classe sous-jacente un ensemble, - les morphlsmes de T sont les homomorphisme s entre ces £-algèbres . 2.1.2. n(i) La catégorie P des algèbres partielles. Soit Z = { Ui / iel > une signature. Alors, pour tout l'arité du symbole fonctionnel Ui . iel , on note Rappelons qu'une (petite) Z-algèbre partielle A=(A, (Ax) m , (ax)id ) est la donnée: - d'un ensemble, dit sous-jacent% A , - pour tout ici , d'une partie Ai du produit cartésien A"*1* , partie appelée ensemble des n(i)-up2ets d'éléments de A composa blés pour (resp. par) ui (resp. ai ), - pour tout ici , d'une application oci:Ai-*A , dite interprétation de u± , Dans ces conditions, on identifiera, le plus souvent, le symbole Ui avec son interprétation ai . Ainsi, par exemple, si (ai,. .. ,a,-,< i >) est composable pour Ui et donc par ou , on posera ax (ai, . . . ,an< i >)=Ui (ai, . . . ,an< i •> ) . Dans le même ordre d'idée, on peut facilement généraliser la notion de n(i)-uplet (ai,. . • ,an< ±>> , composable pour un symbole fonctionnel ux , en celle de n-uplet (ai,.•.,an) composable pour un terme tcTr(xi,...,Xn) (il suffit de procéder par récurrence sur les sous-termes de t ) : son composé sera alors noté t(ai,...,an) . Rappelons, également, qu'un homomorphisme de Z-algèbres partielles f:A-+B est la donnée d'une application (encore notée) f:A-»B qui, pour tout symbole fonctionnel ui , transforme les uplets composables pour ui en des uplets composables pour ui et les composés par ai en des composés par £i . La catégorie Pz , ou plus simplement P , des (petites) Z-algèbres partielles a alors: - pour objets les (petites) Z-algèbres partielles, - pour morphlsmes les homomorphisme s entre ces Z-algèbres partielles. Ainsi, la catégorie T apparaît comme une sous-catégorie pleine de P (puisque tout homomorphisme de Z-algèbres partielles entre deux Z-algèbres totales est en fait un homomorphisme de Z-algèbres totales). 38 2.1.3. La catégorie M des modèles. Soit L=< Ui / ici > un langage (i. e. , ici, un ensemble de symboles relationnels). Pour tout ici , on note m(i) l'arité du symbole relationnel ui (ainsi, a-t-on m(i)> 0). Rappelons qu'un (petit) modèle A=(A, (Ai)i«:i) de - d'un ensemble, dit sous-jacent, A , - pour tout iel , d'une partie Ai du produit cartésien ensemble des m(i)-up2ets en relation pour L est la donnée: kUlC ± > , partie appelée u± . Rappelons aussi qu'un homomorphisme de modèles (de L ) f:A->B est la donnée d'une application (encore notée) f:A-*B qui, pour tout ici , transforme les uplets en relation pour Ui en des uplets en relation pour Ui . La catégorie IL , ou plus simplement M , des petits modèles a alors: - pour objets les (petits) modèles de L , - pour morphlsmes les homomorphismes entre ces modèles. Ainsi, P s'identifie à une sous-catégorie de M , puisque: - à la signature Z on peut associer le langage L=Z , de sorte que, pour tout ici , on ait m(i)=n(i)+l , - toute Z-algèbre partielle A s'identifie au modèle A*=(A,(A*±>±«x> , où, pour tout ici , on a: A*i = { (ai,...,a«-n ) / (ai,...,an)cAi et ûn(i> + i=Ui(ai,.,,,an(i>) ) . Bien entendu, cette sous-catégorie est pleine, puisqu'un homomorpHisme de modèles entre deux algèbres partielles est nécessairement un homomorphisme d'algèbres partielles. Enfin, ce qui vient d'être dit pour la catégorie des algèbres partielles est, a fortiori, valable pour la catégorie des algèbres totales. 2.2. 2.2.1. CASACTBSISATIOM DAMS DEF1MIES BM 0.3. . T ,P ,M , DBS CLASSBS REMARQUABLES Caractérisât ion intrinsèque. Les tableaux qui suivent indiquent à quelles conditions nécessaires et suffisantes un homomorphisme f:A-»B , dans la catégorie T , P ou M , est élément des classes remarquables: Iso C Hc C H. C B. C Epi et: Mono D Sr D S» D Iso, (nous avons rangé, arbitrairement, la classe Iso dans le premier tableau). 39 0 O •TH r-H r-l 01 -P O ^ œ «s ^ P: ~ 4* 03 -«a fn o - p bO o o u o Pî O -rH ^ 0) a as 0) -P O bo o «S rH u «s o PÎ as ai > ai rH rH (U Pi O iH rH f-i (1) - P O — . «0 * (D H 0 ~ -»H -P 0 -P (d O 01 M •*-> Il •H t-i a) -rH 0) «< UJ ^ O O -p ai as t as . ai c C ai -P « -p (L) (0 O fi> o a» « c as fi- T «O W < -P H *M as fr- - 0 as •tf -p rH 3 r* as O as rH as Oi PI 3 bO bû-rH O 03 rH (0 oi oi ai P Pi û as rH 03 rH Pi 3 -p «S (Si 03 oi ^ a, r-* -p «w II s. il P, 1 Pî ai ui >> 01 U Pî 3 01 -p • H II a te 01 r. Cu>- u u as T* 3 eu il i P H M H TS u r< B* O 0) P H B ^ 3 0 rH as as o w ai * c >-. •• O (0 0) PQ P! -tH iH m o T a> o o ai o -r-> B r^ o o ai - p bo (Si 01 as P! rH bO as P H pî Pî o -p ai P I f* « -p _ 0) PQ ai O) ^ o - S* PQ -P ai as 0) ai t> (D > Oi as - P rH (0 ai ai - 3 ai (Si c r *H o P 0) as c rQ > o 01 « rH T < î -P x» -as H P: /-v * -H Pî tH 3 rH P as -P U) •* ^ rH rH as ^ t. -P -û «rH rH U 3 (0 S fr : -p o o a> ai «i -P "r-> PQ - su rH S rH 01 01 r H o o 3 CT 1 -rH r-i ai (Si o c -P O 01 ^ -rH oi as aï m a rQ > T .. ai 01 «iH P H B i PQ 3 0 -p O as * as 01 ^ rH ^, 40 CO co « O p O Co co « co II II co p -J II J. W < (D P- H> CD- « O PL H) »-• CD- -* m > CD* 03 > GO fi) ,-Q W 0) P O <-*• P - 03 P CD O <-* 0 (D O M> C r r /~v*Cl H - rP C r» (D O rr O ff p o <-* P C r h (0 r* pi n> o M> • < C c* 1-- < CD (D P r3 * rr P c 3 r* H- AN M H- c+ M- (D s - M- ~ < K - ^ P • OQ (D (0 P »£} CD * 3 C c+ • C - (D CD 0) * »* p c - rr C S 0 v ^ fH> H•> p 3 C r-»T3 I—• H- P W H- P r-* 3 M. ^ r Q HC v (D ^ ~ p 3 r* • fl> " • .. 0) fl) cirH> M - CD & H 0Q CD (D »Q •-• C - (D (D (S) * rr C CD rr C rQ o < (D H- C (D CD <-r CD rr r- 1 (D fl> 03 CD 03 c+ O O P 3 W (D •P *^ ^ O O B p 3 •8 O O o *d 03 O CD* 03 O 03 CD 0) • r r (D M, n 1 M> CD (D " P p j, <+ <+ W r* 4, M* O O P P M M> H- ^ p CO ^ n>1 P r . g . p II • r-i » - CO 3 >n * I . ^ . P M- M> • • r* H- C P (H 3 * » P 3 »*• fT> HW /N H- H- 3 - * P P-<— CD* CD H-0) O et *Q H(D C < * CD CD 03 rh O CD P *-i—* C CD r-^HÛ CD C r r CD P P OQ CD C ~> •*> CD r-* 03 CD <+ e-r CD CD P 03 c+ CD P CD O rh 41 2.2.2. Bxemple. Reprenons les exemples de 1.1., notamment celui de 1.1.4 et celui de 1.1.5. (celui de 1.1.3., qui fait intervenir une catégorie d'algèbres totales, étant beaucoup moins intéressant ici). La catégorie des (petites) catégories non (nécessairement) associatives est une sous-catégorie d'une catégorie d1algèbres partielles P (pour laquelle on a Z=B appartenant à H. , Hr ou Epi , dans T , P ou X peut s'interpréter (i. e. se présenter) comme un "passage à un quotient" d'un type précis (i. e. par des "relations" de nature déterminée). C A S D E LA CATEGORIE T On y a H»=Hr=Epi={homomorphismes surjectifs). On obtient donc B à partir de A en identifiant certains de ses éléments; f est alors de la forme: A -> A / A (ai=a'i) iel (l'ensemble I pouvant être, bien entendu, vide). 42 CAS D E LA CATEGORIE Rappelons qu'a priori la structure d'algèbre partielle induite par B sur f(A) est plus riche, 1. e. contient davantage de uplets composables, que celle de l'algèbre partielle image f(A) . - Cas de B=Em. La caractérisation de H« assure que, contrairement au cas général rappelé ci-dessus, les deux structures d'algèbres partielles sur l'ensemble B=f(A) sont exactement les mêmes et qu'ainsi on obtient B à partir de A en identifiant certains de ses éléments; f est donc de la forme: A -> A / A (ai=a' i) iel (l'ensemble I pouvant être vide). - Cas de J£=Hr. Dans ce cas, en revanche, si l'on a encore B=f(A) , pour obtenir B à partir de A , il faut non seulement identifier certains de ses éléments mais aussi imposer à certains uplets de devenir composables (leurs composés étant alors, nécessairement, des éléments déjà existants); ainsi, f est de la forme: A -» A / ( A (ai=a'i)) A ( A aitjtej, iel jeJ a^j,) (où I et J peuvent être vides, les t0 sont des TI(XJI Xjp) signifie "le (aji,...,a3P A / ( A (ai=a'i)) A ( A si tj (aji, . . . ,adPc j >>) iel jeJ 43 (avec les conventions précédentes, étant entendu que certains des composés dont on impose l'existence peuvent être rajoutés formellement). ïotons que le symbole de "passage au quotient" / est à manier, ici, avec beaucoup de précautions, puisqu'il ne signifie pas que f est nécessairement surjective. CAS D E LA CATEGORIE M Il peut se traiter rapidement, maintenant. En effet, le (sous-)cas £f=H. est analogue à celui décrit dans la catégorie on obtient ainsi pour forme générale de f: A -> A / A (ai=a'i) iel De même, le (sous-)cas J¥=Hr=Epi est analogue.au (sous-)cas P ; on obtient, ainsi, pour forme générale de f: A -» A / ( A (ai=a'i)) A ( A (Uj (aj, iel jeJ (où I langage 2.3.1. et J L ). peuvent être vides et les uj 2.3. CARACTERISATIQI DAIS T f P , M H = Iso , Hc t H» , Hr . ff=Hr P ; décrit dans a J p < J >)) sont des symboles relationnels du DBS OBJETS H-PROJBCTIFS POUR Tableau de caractérisâtion. Le premier tableau de 2.2.1. permet, comme précédemment, de caractériser les objets H-projectif s de T , P , I pour H = Iso , Hc » H» , Hr . Ces caractérisations sont regroupées dans le tableau de la page suivante. 44 m Il i I o •S w P3 I ^ I n *i O u *i n n I *-•• T * II I t-. I 0) O I "S O n o O n n •o C (D O o c* H C' CD CD »i 0) " P g O O l 81? CD M CD* II (D CD < CD O H o < P ^ H- HfD> 3 P H - (D I «f «40) H- H* (D H> Il v K P H-ff I H - H -^ C (DOQ P *d r#- O P P o C* H-" (D - C D p • rr p •• • C 8 O* «1 CD 0) II • P • * P *T3 Pr» P K-» 3 • C rr %• • g) C CDM CD • 0 CD rr P P 3 C • CD H Û P »1 C •O 3 M 4 C CD >^ i CD P (D P c+ (D P p. C C ^N > ri P H* - C e+ - ¢+ CD t » P) e 0) P ï"Aî H, . C C P cy c /N CD * ^ In • - (D H- 0) 0»û O C H - H • CD <+ • (D (D h CD P O »-0Q P 1 CD g (D çp 0) CD 0 & 0 r f C 0) H- O 0) r r CD C O H - û) H . C H- I p CD CD P M(D M r r M OQ HCD O CD* P 0) O C C CD P P O rr CD P. CD* O *1 C CD I© • (D ffl CO P <+ P* HH- O I S S rr rr p 0) M o O C rïC r^OQ M- C • CD CD f > H- • 1 r » H- CD • CD i - < -SI* v^c> P • M GO CD (D «73 H» B CD '-A> r^ M t * H. M/ A •*/ 0) -rx C (D r- O CD P 0) HJ p B rr H.^ a m, ^ O *1 H- r* CD ÇO CD P rr >> HO rr P M p CD C < rr «D* *0 *1 ^ HH- p C H» © M-- P P • • *: P «* Il p • C (D P H- p c " g P S * H- »û H-» n> C O f i A QQ M- c * CD ^ P *T3 C S OCD C c + ^ *i O P C rr M C (D O H e CD »U PC r f C p |* CD * P C ^ œ P T3 O m (D rS. r C2 D * O M- fj) C CD p. «? g'S c r r CD *1 CD 0 r r •1 r r h* H CD H B0) P H- < CD ^ <<-* H* 0) * CD HO - CD BC M • P O CD 0 CD O 0 >£ H C H CD ^ W O p, CD ? XN * g 45 2.3.2. Présentation des objets H-projectif s de H. , Hr ) corne quotients. T f P f M (pour H = Iso , Hc , Dans une catégorie algébrique donnée, donc dans T , P , M , tout objet est déterminé par: - la donnée d'un ensemble Gén de générateurs (d'une structure libre, relativement à un foncteur qui, dans les trois cas qui nous intéressent, sera le foncteur "ensemble sous-jacent" ), - la donnée d'un ensemble Rel de "relations" entre ces générateurs. Autrement dit, tout objet se présente (de manière non nécessairement unique ou canonique) comme le "quotient" d'une structure libre par un ensemble de "relations", i. e. sous la forme: Libre(Gén) / Rel. (pour Hous présentons, ici, un objet H-projectif quelconque H = Iso , Hc , H. , Hr ) sous cette forme. CAS D E LA CATEGORIE A de T ,P , X T . Les structures libres relativement au foncteur "ensemble sous-jacent" sont ici (à isomorphisme près, bien entendu) les algèbres de termes Ti(V) , où V est un ensemble (de "variables") quelconque. Plus précisément, TE(V) = Libre(V) est "la" structure libre sur l'ensemble V. - Cas H = Iso . Dans ce cas, A forme: est une algèbre totale quelconque et peut donc s'écrire sous la Libre(V) / * (tj(xj, XjP)) jeJ où l'ensemble J peut être vide (et où l'on peut choisir pour ensemble V = Gén de générateurs l'ensemble A , sous-jacent à A , et pour ensemble Rel de relations l'ensemble de toutes les égalités, valides dans A , entre composés, par des termes, d'éléments de A ). - Cas H = Hc = H. = Hr . Dans ce cas, A est de la forme TE(V) , i. e. s'écrit: Libre(V) (c'est dire que, cette fois-ci, on choisit explicitement pour ensemble de générateurs et Rel = 0 , i. e. J=J5). Gén = V , et non Af 46 CAS DE LA CATEGORIE R . Les structures libres, relativement au foncteur "ensemble sous-jacent", sont les algèbres discrètes (voir tableau de 2.3.1.) Disc(V) , où V est un ensemble (de "variables") quelconque. Plus précisément, Disc(V) = Libre(V) est "la" structure libre sur l'ensemble V . - C a s H = Iso . Dans ce cas, A est u n e algèbre partielle quelconque et peut donc s'écrire sous la forme: Libre(V) / A ( t j (Xjl,. . . , xJp>< j ,)=t' j (x* j T , . . . , x'Jp.. < à >) ) J€J où l'ensemble J peut être vide et où, par convention, une écriture telle que: t(Xl , . . . Xp)=t* (x1 ! , . . . , x' p.- ) signifie: (al t(xi,...,x P ) ) (al f (x'i, . . . , x ' p O ) ( t(xi x P ) = f (x' i, ... ,x' p . ) ) (et l'on peut donc choisir l'ensemble A comme ensemble V = Gén de générateurs et l'ensemble de toutes les "composabilités" et égalités entre composés, valides dans A , comme ensemble Rel de "relations"). - Cas H = Hc . Dans ce cas, A est (à isomorphisme près) un segment initial quelconque d'une algèbre totale quelconque TE(V) . Si nous notons (tJ(XjlM..,XjP) peut être vide (remarquons que, cette fois-ci, on n'a pas choisi pour Gén de générateurs l'ensemble A , ce qui permet de "simplifier" Rel de "relations" par lesquelles on "quotiente"). - Cas H = H . . Dans ce cas, A est nécessairement H c -projectif et donc de la forme précédente; d'autre part, vu la caractérisât ion de H.-proj , la famille de tous les composés existant d a n s A est du type: (Uj (Xji, . . . ,Xj P (j))jcj où Ujel , pour tout J E J , et Xji f x*i-. dès que (i,j) f (h,k) . Ainsi, A s'écrit sous la forme: 47 Libre(V) / A al uj(XJI,...,xiP) JeJ où J peut être vide , Ujeï , pour tout (i,j) / (h,k) . jeJ , et où Xji / XKI-, , dès que - Cas H = Hr. Alors, A est de la forme: Libre(V). C A S D E t-A CATEGORIE M . Les structures libres relativement au foncteur "ensemble sous-jacent" sont les modèles discrets (voir tableau de 2.3.1.) Disc(V) , où V est un ensemble quelconque (de "variables"). Plus précisément, Disc(V) = Libre(V) est "la" structure libre sur l'ensemble V . Eotons qu'un modèle quelconque A peut toujours s'écrire sous la forme: Libre(A) / A uj(xjT,..., xJp) jeJ où (Uj(Xji,...,UjP))jfj désigne la famille de tous les uplets d'éléments de A , en relation par les symboles relationnels du langage L . - Cas H = Iso ou Hc (puisque Iso-proj = Hc-proj , bien que soient pas, généralement, les mêmes). Tout objet A est H-projectif, i. e. de la forme: Libre(V) / A m (x3i,...,xJpCi>) jeJ (puisque V = A convient). - Cas H = H. . Alors, A est de la forme: Libre(V) / Auj(XJI,...,x Jp ) . JeJ , où XjifXkr. dès que (i,j)f(h,k) (l'ensemble J pouvant être vide). - Cas H = Hr . Alors A est de la forme: Libre(V). Iso et Hc ne 48 2.4. 2.4.1. STRUCTURES DE BOUES CATEGORIES SUR D'EPIMORPHISMES ASSOCIEES. Choix de structures de bonnes catégories sur T , P , M ET BOUES CLASSES T , P , M . Les propriétés des catégories algébriques, en particulier de T , P , M (que l'on peut établir directement, par exemple en utilisant les caractérisations précédentes), assurent que les hypothèses du théorème de Birkhoff catégorique sont vérifiées lorsqu'on choisit (de manière indépendante l'une de l'autre): - le système de factorisation dans l'ensemble { , , ) , - la classe d'épimorphismes H dans l'ensemble { Iso , Hc , H. , Hr > . Ainsi, obtient-on douze choix possibles (non nécessairement distincts) et donc douze versions possibles du théorème de Birkhoff concernant les algèbres totales, les algèbres partielles, les modèles ... et certains types de formules. Remarquons, pour être tout à fait complet, que la classe Hc n'est pas, en général, sous-jacente à un système de factorisation (sauf, par exemple, dans T , où l'on a Hc = H. = Hr = Epi ). De même, le système de factorisation est exclu puisque, d'une part, la bonne catégorie considérée ne doit être qu'à peu de fP-objets quotients et, d'autre part, B doit être une classe d'épimorphismes. Constatons aussi que le système de factorisation est inintéressant, puisqu'il nous ferait apprendre, par le théorème de Birkhoff catégorique, que ... les isomorphismes sont validés par n'importe quel objet. Enfin, on exclut la classe d'épimorphismes H = Epi car la catégorie P n'a généralement pas d'objets Epi-projectifs (et parce que, dans les catégories T et M , on a Epi = Hr ). 2.4.2. Caractérisât ion, dans T , P , M , des bonnes classes canoniques d'épimorphismes et choix de bonnes classes primitives d* épimorphismes. Pour chacun des douze choix possibles du couple Œ,) , dans chacune des catégories T , P , M , nous avons décrit précédemment les objets H-projectifs et les éléments de E . Il est donc facile, mais fastidieux, d'en déduire, dans chaque cas, la caractérisât ion des éléments de la bonne classe canonique d'épimorphismes E'HS ; nous ne le ferons pas, mais nous remarquerons seulement que les éléments de E'HS ont une présentation (en termes de "passage aux quotients") de la forme: e': (Libre (V)/ ^ F j ) jeJ -* ( (Libre (V)/ A Fj ) / A *t jeJ ici ) 49 où les Fj (resp. les y±) sont des "relations" , i. e. des formules au sens usuel, d'un certain type disons T H S (resp. T'HS ), dépendant des choix de H et S (ou B) et où les ensembles V , J et I sont arbitraires. On prouve alors que, dans chaque cas, la sous-classe EH& de E'HS , constituée des: e: (Libre(V)/ A F j ) _, ((Libre(V)/ A Fj ) / * ) j€j jeJ où yf est une formule arbitraire de type T ' H S et où V ,J et les Fj sont comme précédemment est une bonne classe primitive d'épimorphismes. [En effet, notant: S = (Libre(V) / Apj) jeJ on vérifie aisément que le diagramme: S/y, S/ A y ± iel (où i décrit I et où tous les morphlsmes sont des passages au quotient ou s'en déduisent canoniquement) est une somme fibrée: c'est d'ailleurs l'idée sous-jacente à. la notion de bonne classe primitive d'épimorphismes ... et aux exemples de 1.1.3. repris en 1.4.3. D'autre part, on vérifie facilement aussi, mais de manière intrinsèque (i. e. purement catégorique) que, dès qu'il existe une sous-classe C de Dec(e') (voir 0.4.1 et 0.4.2) telle que codom(e') = Sommef ib<^,->«c e , alors on a aussi codom(ef ) = SommefibcD*cc*'> e . Ainsi, dans certains cas, il est encore possible de réduire la bonne classe primitive d'épimorphismes: nous ne le ferons que dans le cadre équivalent des formules associées (voir 2.5.3.), pour éviter trop de redites.3 50 2.5. 2.5.1. TRADUCT10I El TERMES DE FORMULES. Considérations préliminaires. Hous avons donné (en 1.4.) la définition intrinsèque des bonnes classes EHS d'épimorphismes. Dans le cas des catégories T , P , M , pour les douze choix possibles du couple (H,), et moyennant la description de ces classes (donnée en 2.2. et 2.3.) nous allons leur associer des classes de formules, notées E ' H S et EHS . Plus généralement encore, à toute sous-classe E de E'HS , nous allons associer une sous-classe E de E ' H S • de sorte que, pour tout objet B de C = T , P ou M , on ait: E'HS et B B valide (au sens de 1.1.1) E CEHS si, et seulement si valide (au sens usuel) E CE'HS (resp. E CE'HS) (resp. E C E H S ) Il convient de noter que ce processus de traduction d'une sous-classe E d'épimorphismes (en particulier: d'un épimorphisme) en une sous-classe E de formules (en particulier: en une formule) n'est pas intrinsèque (ou canonique). En effet, il dépend de la présentation (qui n'est pas unique) choisie pour décrire sous la forme: Libre (Gén)/Rel les objets de la catégorie considérée. EHS Reprenant les notations de 2.4.2. et considérant un élément quelconque de (resp. E'HS) , nous l'écrivons sous la forme: e: S=(Libre(V)/ A Fj > ^ S /y i€j (resp. e': S=(Libre(V)/ A Fj ) -> (S / A y ± ) ) jeJ iel Un objet quelconque B de T , P ou M valide alors e (resp. e' ) si, et seulement si, tout morphisme f:S-*B se factorise par e (resp. e* ). Or, en raison des propriétés universelles définissant un passage au quotient et une structure libre, la donnée d'un tel morphisme quelconque f est équivalente à la donnée d'une évaluation quelconque - i. e. d'une application - de l'ensemble V dans l'ensemble B , sous-jacent à B, telle que les évaluations des générateurs valident les formules Fj (dont les "variables" sont bien des éléments de V ). La condition de validation de e (resp e' ) par B va donc se traduire exactement par la validation (au sens usuel de la logique) par B de l'implication form(e) (resp. form(e') ) suivante: (resp. A F J => y jeJ A Fj =* A yA ) jeJ iel 51 où les variables (figurant dans les Fj , y4 et y ) sont "quantifiées universellement" . Dans ce qui suit, nous omettrons donc le plus souvent de faire figurer les variables et nous ne ferons pas figurer les quantificateurs universels (puisqu'il ne peut donc y avoir ambiguïté). Dans ces conditions, nous allons décrire les implications telles que form(e) , la description des implications telles que form(e') s'en déduisant facilement. Par analogie avec les classes d'épimorphismes, nous dirons que EHS est une (bonne) classe 2.5.2. primitive de formules. Classes primitives de formules pour les algèbres totales (i. e. pour T ). Les douze choix possibles dont il est question en 2.4.1. se réduisent ici à seulement deux choix distincts, à savoir H = Iso ou H = Hc = H« = Hr et = = = . Des présentations étudiées en 2.2.3. et 2.3.2. ressort alors immédiatement que: - Ei.0/Mono = < / Mtj=t' J ) =* t=t' / J ensemble et les tj,t'j,t,t' termes) jeJ - pour H=Hc=H.=Hr , EH,Mono = < t=t' / t et t' termes). En conséquence, on remarque que, dans ce dernier cas, le théorème de Birkhoff catégorique a pour traduction le ... théorème de Birkhoff usuel. 2.5.3. Classes primitives de formules pour les algèbres partielles (i. e. pour P). Des présentations étudiées en 2.2.3. et 2.3.2. ressort immédiatement que (en utilisant les mêmes conventions): - Eiso>Mono = < A J€J [on contrera utilement ce cas avec le précédent: ici, on rajoute (éventuellement) composabilités et composés, alors que, précédemment, seules les composabilités étaient rajoutées, les composés étant des éléments déjà existants], - E H C M O H O = < ( Agitj) jeJ 311 - EHc,sr =<( Aslti) 31ST 3lt 3lt' =* t=t' / J ensemble, les t,t',tj termes), ... 3lsp 3 t=u(s!, .. . ,Sp)/J ensemble, ueZ optionnel) jeJ les t,tj,Sk termes (N. B.: analogue au cas Ex«0,&r], - EHC,S» = { ( Asltj) =* t=t* / J ensemble, les t,t',tj termes) jeJ [comparaison avec EHC.SP analogue à la comparaison précédente de Ei.0,sr avec Elso,&» ] , Les descriptions des objets Hc-projectifs et Hr-projectifs étant fort similaires ici, celles des classes EHC,S et EH»,s (pour Se ) le sont aussi. Ainsi a-t-on: - EH«,Mono = i ( A alUj(xji,,.MxJPcj))) => r=r' / J ensemble,les ujeZ,les r,r' des > jeJ variables ou des uj(xji,..., Xjp) les Xj i variables xji^Xkh ssi (i,j)?(h,k) - EH.,sr = { ( A 3luj<(xji,...,xJp)) 3 r=u(ri,...,rP) /J ensemble.les u,UjeZ, ) jeJ u optionnel, les r,rk des variables ou des UJ(XJI,...,xjp), les xji des variables, Xji/Xkh ssi (i,j)^(h,k) - EH*,s* = { (À 3luj (Xji, . .. ,xjp< j >)) => t=t' / J ensemble, les UjeZ,t et t' termes jeJ les xji des variables, x.i^XKh ssi (i,j)*(h,k) La classe EHP.S (pour Se {Mono, Sr, S.) ) est la sous-classe de Ez»o,s ou de BHr,s déterminée par la condition J=0 (l'ensemble J intervenant dans la classe EHC,S ne jouant pas le même rôle que dans les autres classes). Ainsi, on obtient: - EHr,Mono = < x=x' / x et x' des variables ) - BHr,sr = i x=u(x'i,. . . ,x'p) / les x,x'k des variables,ueZ optionnel) - Enr,s. = < t=f / t et t' termes > ) 53 [N. B. : EHr.sm contient donc aussi les formules de la forme un terme), équivalentes aux formules de la forme 3lt .] 2.5.4. t=t (où Classes primitives de formules pour les modèles (1. e. pour M ). t est Les douze choix dont il est question en 2.4.1. se réduisent ici à six choix distincts, car , d'une part, Hr = Epi (i. e. S,- = S» ) et, d'autre part, Iso-proj = Hc-proj . Des présentations fournies en 2.2.3. et 2.3.2., on obtient: - EHr,Mono = < x=x* / x et x' des variables ) (car A Uj(...) =* x=x' est éauivalente à je0 x=x' !) - EHr,sr = EH>-,S« = {x=x'/x,x' des variables) U ) =* x=x'/J ensemble,les x,x',Xji des ) variables,les UjeL - Ei«o f sr=Ei» W/ sm=EHc # s»={ ' * Uj (xj i,, . . , Xj P ( j J jeJ 3 x=xV J ensemble, ueL les x,x',Xji des variables \) i '*Uj(Xji,.. . ,Xjp)3u(xi,...,xp)/J ensemble,les u,ujeL) jeJ les Xk.Xji variables - EH».Mono est la sous-classe de "xjifxkh - EHs,&r = E H « , S « Ex» 0 ,Mono ' où l'on impose: ssi (i,j)±(h,k)\ est la sous-classe de "xjxfXko ssi Ei« 0 / sr où l'on impose: (i,j)f(h,k)M. ) 3. LE THEOREME DE BIRKHOFF CATEGORIQUE FIHITAIRE. 3.1. 3.1.1. FIIITUDE. Position du problème. Comme nous l'avons dit dans l'introduction, Andréka et Néméti n'ont abordé le "problème de la finitude" (des formules) que dans le cadre spécifique des algèbres totales, des algèbres partielles ou des modèles. Ils l'ont exposé, dans ce cadre particulier, de la manière suivante: - les formules de la classe primitive EH,s ayant été décrites sous la forme A (formule atomique)j =* (formule atomique) J€J (ces formules atomiques étant, bien entendu, de telles ou telles formes, selon les valeurs particulières de H et 5 ) , comment transformer l'énoncé du théorème de Birkhoff, si l'on se limite aux seules formules finitaires, i. e. à celles pour lesquelles J est fini ? La réponse est obtenue en "gonflant" la classe H S ? A. Hous montrons ici qu'il est tout à fait possible de ne pas se limiter aux seules catégories particulières T , P , M et de donner, ainsi, une version catégorique (qui complète la précédente) de ce théorème de Birkhoff finitaire. Pour ce faire, il suffit d'utiliser une formalisation convenable de ce que peut être un objet "finitaire" dans une catégorie: c'est justement la notion d'objet finiment présentable de Gabriel-Ulmer (in "Locally a-presentable and locally a-generated catégories", Lecture Notes in Math. 195, Springer, 1971) qui la fournit. 3.1.2. Objets finiment présentables. Rappelons d'abord qu'une catégorie I est dite (finiment) filtrante si, et seulement si, tout sous-diagramme fini de cette catégorie possède un "majorant", i. e. si et seulement si: - pour toute catégorie finie J, pour tout foncteur y: J-»I , il existe (au moins) un objet I de I et (au moins) une famille (f j : y (J)-»I) j t 0 b j de flèches de I tels que: + pour toute flèche j:J->J* de J , on a fj*.y(j)=fj, i. e. le diagramme ci-dessous commute: y(j) 58 Rappelons aussi qu'une limite inductive (d'un foncteur F: I-»C) est dite filtrante si, et seulement si: - la catégorie d'indexation I est filtrante. Rappelons, enfin, qu'une catégorie C est dite localement petite si, et seulement si: - pour tous objets C et C de C , la classe Hom(C,C) = {feMor C/f:C-*C> est un ensemble (i. e. est petite). Dans ces conditions, à tout objet C de C, on associe le foncteur: Hom(C,-):C-»Ens tel que: - pour tout objet C de C , on a Hom(C,-) (C )=Hom(C,C ), - pour tout morphisme g:C'-*C" de C , on a Hom(C, -) (g)=Hom(C, g) : Hom(C, C )->Hom(C, C" ) f -» g.f Alors, si C est une catégorie localement petite, on dit qu'un objet C de C est finiment présentable (ou finitaire) si, et seulement si: - le foncteur Hom(C,-> :C->Ens commute aux limites inductives filtrantes (i. e. si, et seulement si, pour toute catégorie filtrante I , pour tout foncteur F: I->C admettant une limite inductive - qui est donc filtrante - notée limfil(F) - on a: Hom(C,limfil(F))=limfil(Hom(C,F(-))) , où l'on pose Hom(C,F(-) )=Hom(C,-) .F: I-*Ens ). Dans ces conditions, sans entrer dans les détails, notons qu'alors, en désignant par (wi)icobi la famille des coprojections d'une telle limite inductive filtrante, tout objet finiment présentable C sera tel que: - pour tout morphisme x:C-»limf il (F) de C , il existe (au moins) un objet I de I et (au moins) un morphisme xx:C-»F(I) de C vérifiant wx.xi=x , i. e. rendant commutatif le diagramme suivant: limfil(F) \ xx ^ ^ \ wx N F(I) 3.1.3. Exemples. On a rappelé en 2.3.2. que, dans toute catégorie algébrique (en particulier dans T , P , M ) tout objet peut se présenter comme le quotient d'une structure libre sur un ensemble Gén de générateurs par un ensemble Rel de "relations". Il est facile d'établir qu'un objet d'une telle catégorie y est finiment présentable si, et seulement si, les ensembles Gén et Rel peuvent être choisis finis. 59 3.2. 3.2.1. LE CADRE CATEGORIQUE DU THEOREME DE BIRKHOFF FITITAIRE. Bonnes classes d'épimorphismes finitaires. Soit (C, H, ) une bonne catégorie. Fous dirons qu'un épimorphisme seulement si: - dom(e) est un objet finiment présentable Alors, on note Epif la sous-classe de finitaires. C est finltalre e de si, et de Epi C. constituée de ces épimorphismes En désignant toujours par E'HS la bonne classe canonique d'épimorphismes de la bonne catégorie C (voir 1,4.1,), on pose: tf**H. = Jr'HsOEpif et on l'appelle bonne classe canonique d'épimorphismes finitaires de la bonne catégorie C . Maintenant, si R*s est une bonne classe primitive d'épimorphismes de la bonne catégorie C (voir 1.4.2.), on pose: F H S =finsn Epif, et on dit que c'est une bonne classe primitive (associée) d'épimorphismes finitaires de la bonne catégorie C. Clairement, elle dom-engendre encore la bonne classe canonique d*épimorphismes finitaires. 3.2.2. Propriété fondamentale de catégorie classe Proposition. Si localement petite HLod(E) est stable Mod(JB) si (C,E>) et si E sous l'action EC E'"HS. est une bonne catégorie, si C est est une sous-classe de E'^HS , alors de H , S , P et limfil. une la Preuve. Comme il est clair que limfil Mod(2D Z> Mod(2D , il ne reste à vérifier que la stabilité de Kod(E) par limfil . Soit F: I-»C un foncteur à valeurs dans Hod(E) , où I est une catégorie filtrante, et supposons que L en est une limite inductive (donc filtrante), avec (wi)i«ot> i pour famille de coprojections. Soit e:E-*E' un élément quelconque de E et prouvons qu'alors L valide e. Soit f:E->L . Comme E est finiment présentable (par hypothèse), on en déduit (voir 3.1.2.) que f se factorise par l'une (au moins) des coprojections: il existe donc un objet I de I et un morphisme fi:E-»F(I) de C vérifiant f=wx.fi . Or, F(I) est (par hypothèse) un modèle de E et il existe donc un morphisme gi de C tel que fi=gi.e . Posant g=Wi.gi , g vérifie: 60 g.e=wi.gi.e=wi.fi=f . Donc L valide e . L = lim F eeE F(I)eMod(£> Fin de la preuve. 3.3. VERSIOI FIIITAIRE DU THEOREME DE BIRKHOFF CATEGORIQUE. 3.3.1. Enoncé du théorème de Birkhoff catégorique f i n i t a i r e . Si (C, H, <#,£>) est une bonne catégorie, si C est une catégorie localement petite, si C est à (petites) limites inductives filtrantes, si tout objet E-projectif de C e s t l i m i t e inductive f i l t r a n t e (petite) d'objets E-projectifs et finiment présentables de C, si E est stable par limites inductives filtrantes (petites), si EHS est une bonne classe primitive d'épimorphismes de C et si A est une classe d'objets de C , alors: Xod(E>Hs(A)) (où l'on désigne par d1 épimorphismes finitaires keA ) . 3.3.2. B*HS(A) constituée = H l i m f i l S? A la sous-classe de la de ceux de ses épimorphismes Preuve du théorème de Birkhoff catégorique finitaire. On se reportera au diagramme qui suit. classe validés primitive par tout 61 îeE A' = lim G fx-ejï Comme dans la preuve du théorème de Birkhoff catégorique (non finitaire) de la section 1, mais en utilisant cette fois-ci la proposition de 3.2.2., il nous faut prouver seulement que, B étant un modèle de Eins(A) , alors B est élément de H limfil S? A . Comme C a suffisamment d'objets H-projectifs, il existe un tel objet X et un morphisme h:X->B , appartenant à H . X étant H-projectif, désignons par F: I-»C un foncteur, où I est une catégorie (petite) filtrante, tel que: - pour tout objet I de I , F(I) est un objet H-projectif finiment présentable de C (alors, on note F(I)=Xi), - X , muni de la famille de coprojections (wi)icot> i , est limite inductive (donc filtrante) de F . Comme C est une bonne catégorie, tout Xi engendre une ^-extension libre: fi=frXx" A :Xi->A'ieSP A . On définit alors un foncteur G: I-*C dont la valeur sur les objets de I est donnée par: G(I)=A'x (en effet, il est facile de vérifier que îrcH A=îrc" S ? A , pour tout objet C de C et on détermine alors, pour tout i:I-*I' le morphisme G(i) par: G(i).fx=fx..F(i) ). Comme C est à (petites) limites inductives filtrantes, G en possède une, notée A' , dont on désigne par (vi)ieot, i la famille des coprojections. Soit alors f "le passage à la limite" de la famille (fi:F(I)->G(I))ieob i , i. e, l'unique morphisme tel que: - pour tout objet I de I , f.wx=vi.fi. Par hypothèse, f est encore élément de E. 62 Remarquons maintenant que, pour tout objet I de I , fi est élément ,w de la classe JET Hs ; on prouve alors que, fx étant une extension libre relative à A , les épimorphismes de sa classe de décomposition Déc(fx) sont éléments de B*HS(A) , puis on en déduit que B valide fi (car on a rencontré une situation similaire dans la preuve du théorème de Birkhoff catégorique non finitaire de la section 1 ). Soit alors, pour tout objet I de I , gi:A'i-*B vérifiant: gi.fi=h.wi. La famille (gi)i«ob z vérifie: -pour tout morphisme i:I-*I' de I , gi • .G(i) = gi, (puisque gx. .G(i).fi=gx..fx.. F(i)=h,wx.. F(i)=h.Wx=gi. fi et fx , élément de E, est un épimorphisme). Cette famille définit donc un unique morphisme: g:A'=lim G=limf il (A* x) ii-*B vérifiant: - pour tout objet I de Pour tout objet I , g.vi=gi. de I , on a donc: g.f. wi=g.Vi.fi=gi.fi=h. Wx. On en déduit que g.f=h . Or, fe£T et heH : la condition geH et ainsi BeH limfil S ? A . I (DIAG) assure alors que Fin de la preuve. 3.3.3. Commentaire. La version finitaire que nous avons donnée ici est, comme nous l'avons déjà signalé, une version catégorique du théorème (spécifique à T , P , M ) d'Andréka et ïéméti: il répond donc complètement à leur motivation initiale. En outre, il est plus précis que leur version spécifique puisqu'il assure que "la plus petite classe stable sous l'action de H , S , P et limfil et contenant A " (cf. Andréka-Héméti, corollaire 1, p. 40 ) est exactement: H limfil S? A . [Signalons, de plus, que seules les limites inductives filtrantes doivent intervenir et donc que leur référence à la notion de colimite (i. e. de limite inductive) chez MacLane est erronée.] 4L . TRADUCT I ON DU THEOREME DE B I R K H O F F G A T E G O R I Q U E F I N I T A I R E DA3STS LA CATEGORIE DES A L G E B R E S TOTALES, LA CATEGORIE DES ALGEBRES PARTIELLES, LA C A T E G O R I E D E S M O D E L E S . 4.1. 4.1.1. CLASSES PRIMITIVES DE FORMULES F U I TA IRES. Le théorème de Birkhoff catégorique fini taire s" applique à Tf P ,M. Nous avons donné en 2.4.1. différentes structures de bonnes catégories sur T , P , M . Il est connu, ou facile (mais fastidieux) de vérifier, que toutes ces structures de bonnes catégories satisfont les hypothèses du théorème de Birkhoff catégorique finitaire. Ainsi, notamment, un objet H-projectif quelconque de ces catégories, qui s'écrit (voir 2.3.2.): X= Libre(Gén)/ A FK keK est finiment présentable si, et seulement si, on peut choisir Alors, c'est l'égalité: Libre(Gén)/ A Fj jeJ = Gén et K finis. limfil (Libre(G)/ A F k ) GePf(Gén) keK KePf(KG) (où: - Pf(Gén) désigne l'ensemble des parties finies de Gén , - pour toute telle partie finie G de Gén , KG désigne l'ensemble des tels que toutes les variables de Fj appartiennent à G, - Pf(KG) désigne l'ensemble des parties finies d'un tel KG ), jeJ qui assure que tout objet H-projectif est bien limite inductive filtrante d'objets H-projectifs finiment présentables, 4.1.2. Description des classes primitives de formules finitaires. Nous considérons une quelconque des structures de bonnes catégories sur T , P ou M ainsi que les classes primitives d'épimorphismes R*s et de formules EHS introduites et décrites dans la section 2 dont nous reprenons les notations et les résultats. Nous constatons ainsi que la sous-classe B*HS primitive d'épimorphismes finitaires (associée) s'obtient exactement en imposant que l'ensemble J (de 2.5.1.) est fini. De même la sous-classe BuHs de formules, dites finitaires, qui sont les traductions de cette sous-classe d'épimorphismes finitaires, se décrit comme suit: B W H S = < ( A p j 3 y) e E H S / J ensemble fini ) JeJ 66 On se reportera donc à 2.5. pour avoir la description détaillée, dans chaque cas, de ces formules finitaires. Ainsi, la formalisation donnée dans la section 3 répond bien au problème en 3.1.1. . 4.2. COROLLAIRES DE L'APPLICATION DU THEOREME DE BIRKHOFF CATEGORIQUE FIIITAIRB A Tf P ,M. 4.2.1. Corollaire 1. Pour toute structure de bonne catégorie sur T ,P ou M , donnée dans la section 2 et pour toute sous-classe d'objets A , si la classe B = H S ? A est stable par (petites) limites inductives filtrantes, alors on a: £=Mod#>HsU)=Modèles de Preuve. Le résultat est évident puisque petite classe stable sous l'action de H , S , P Fin de la preuve. E»HS(A) H S ? A et limfil sera alors la plus et contenant A. Remarquons que, plus généralement, le résultat est encore vrai pour toute structure de bonne catégorie (sur une catégorie quelconque!) satisfaisant les hypothèses du théorème de Birkhoff catégorique finitaireî 4.2.2. Corollaire 2. Pour toute structure de bonne catégorie sur T ,P ou M donnée dans la section 2 et pour toute sous-classe d'objets A , si la classe B = H S ? A est axiomatisable (i. e. est la classe des modèles d'une théorie finitaire quelconque du 1er ordre), alors: B=Mod^HS(^)=Modèles de ^HS(A) Preuve. Le résultat se déduit du corollaire 1, puisqu'une telle classe axiomatisable est nécessairement stable par limites inductives filtrantes. Fin de la preuve. 67 4.3. 4.3.1. COMPLEMENTS SPECIFIQUES A T , P ,M Préliminaires. Nous faisons figurer dans ce 4.3 une propriété supplémentaire spécifique à T ,P ou M : en ce sens qu'elle n'est pas établie, par Andréka et Néméti, dans un cadre catégorique "général" . Cela nous entraînerait trop loin de détailler un cadre convenant à une généralisation de ce résultat spécifique, mais signalons simplement qu'il existe! En tout état de cause, nous dirons dans la suite qu'une signature (resp. un langage) Z (resp. L ) est dégénérée (resp. dégénéré) si, et seulement si: - E (resp. L ) est fini et ne contient que des symboles fonctionnels (resp. relationnels) d'arité 0 (resp. 1 ). 4.3.2. Propriété complémentaire. On considère l'une quelconque des structures de bonne catégorie de la section 2 sur T , P ou M. Proposition. (1) Dans les -si "H = Hr , -si H = H. fini), - si la signature alors et si I la signature (resp. trois l le langage cas suivants: (resp. L ) le langage L ) est dégénérée (resp. est finie (resp. dégénéré), on a: H S? pour toute sous classe A (2) Dans tout autre cas, il A = Mod(J?-Hs(i4)) d'objets. existe une sous-classe H S? A d'objets vérifiant: A Ç Kod(B*Hs(A): La preuve de cette proposition, qui repose sur des raisonnements "non catégoriques" se trouve dans Andréka-Néméti. Nous nous contentons d'en donner le principe. Le (1) s'établit en prouvant, dans chaque cas, que: 1Lod(B->Hs(A)) = Mod(J&s(4)) 68 ou plus exactement que: Modèles de &>HS(A) = Modèles de E H S U ) c'est-à-dire que pour toute formule du type: A (formule atomique)j =* (formule atomique) jeJ on peut se ramener, dans le membre de gauche, à une "conjonction finie". Ceci se fait "à la main" (le premier cas, par exemple, est trivial ... puisque l'on sait que les conjonctions sont indexées par p ). Le (2) s'établit, lui aussi, "à la main" en exhibant une classe A et une famille d'objets de E S? A dont la (petite) limite inductive filtrante n'est pas dans H SP A . COMPLETUDE. 5.1. 5.1.1. LA COMPLETUDE EN TERMES DE FORMULES, POUR LES ALGEBRES TOTALES, LES ALGEBRES PARTIELLES ET LES MODELES. Position du problème. On se donne l'une des structures de bonnes catégories (définies dans la section 2) sur T ,P ou M , ainsi qu'une partie E de la classe primitive de formules (qui 6ont toutes des implications particulères) correspondante EHS (choisie dans la section 2 ). Cette classe E engendre la sur-classe: RH*(Modèles de E) ( C BHS ) de toutes les formules appartenant A EHS et validées par tout modèle de E . Ainsi, définit-on une déduction sémantique par: E 1= (L * p) si, et seulement si, (A => p) e EH*(Modèles de E). complétude, Le problème, tout à fait classique, qui se pose alors est celui de la 1. e. le suivant: - peut-on construire A partir de la classe de formules règles d'inférences (i. e. syntaxiques), toute (A 3 p) E , et si oui par quelles telle que ï 1= (û ^ p) ? Autrement dit, peut-on, et si oui comment, construire A partir de EHs(Modèles de E) qu'elle engendre ? 5.1.2. E la classe Résolution du problème. La classe BH*(Modèles de E ) est engendrée à partir de E par règles d'inférences standard (ou "relativement" standard dans certains cas, tout cornue les formules de EHS). Quant aux démonstrations, "non catégoriques" (et spécifiques A T , P , M ) qui le prouvent, elles sont tout à fait classiques. Il nous semble donc inutile de reproduire purement et simplement, ici, ce qui se trouve dans Andréka-Németi (S4, pp. 40 A 46). 72 5.2. 5.2.1. LA COMPLETUDE EM TERMES CATEGORIQUES. Position du problème. Ayant fourni un cadre totalement catégorique au théorème de Birkhoff, nous pouvons poser, en termes catégoriques, le problème de la complétude. Nous nous donnons une structure de bonne catégorie (C, H, ) (sur une catégorie quelconque C ) ainsi qu'une partie E d'une bonne classe primitive BU* d'épimorphismes de C. Cette classe B engendre la sur-classe &s(Mod(£)) ( CE** > (constituée, rappelons-le, de tous les épimorphismes de EHS modèle de B ). Le problème qui se pose alors est celui de la complétude le suivant: validés par tout catégorique, - peut-on, et si oui comment, construire "catégoriquement" A partir de classe &s(Mod(E>) qu'elle engendre ? i. e. E la (Il est, bien entendu, possible de calquer complètement la version "logique" du problème donnée en 5.1.1 en introduisant une déduction sémantique relative À C par: E l=c (e:E->E'> si, et seulement si, (e:E->E'> e &s(Mod(f)) .] 5.2.2. Remarques et suggestions pour la résolution du problème. la catégorie des carrés commvtatlfs de C , i. Notons Sq(C) la catégorie telle que: - ses objets sont les flèches x:Ci-»C2 de C, - ses flèches sont les (y,y1 ): (x:Ci-*C2>-*(x' :C i-»C2) tels que le carré suivant est commutatif dans C: Ci Ci y x' x V C* y 73 Pour tout objet C de C , notons aussi C/C la catégorie des triangles de sommet C , i. e. la catégorie telle que: - ses objets sont les flèches x:C->Ci de C, - ses flèches sont les y: (x:C-*Ci )-»(x' :C-»C i ) tels que le diagramme suivant est commutatif dans C: Alors, les règles d'inférence fournies par Andréka-Németi suggèrent que, pour obtenir 2ks(Mod(lD) A partir de 2f , 11 suffit de: - saturer E , vue comme classe d'objets de - pour tout objet E de C , saturer classe d'objets de E/C , dans E/C , Sq(C), dans Sq(C), E/J? = < eeE / dom(e)=E ) , vue comme par des opérateurs, sur ces deux types de catégories, "sommes" , "images" (associé à H) et "sous-objets" (associé A S), Ainsi, le problème de la "complétude catégorique" fait apparaître un processus de complétlon exactement dual de celui qui apparaît dans le théorème de Birkhoff catégorique (qu'il suffirait donc d'appliquer purement et simplement aux catégories duales des catégories Sq(C) et E/C ) . TABLE DES MATIERES. INTRODUCTION 0. PRELIMINAIRES 0.0. CONSIDERATIONS DE "TAILLES". 0.0.1. Classes et ensembles. 0.0.2. Petites catégories. p. 11 p. 11 p. 11 0.1. NOTATIONS GENERALES POUR LES CATEGORIES. 0.1.1. Objets, morphlsmes et composition. 0.1.2. Classes d'objets et de morphlsmes. p. 11 p. 12 0.2. SYSTEMES DE FACTORISATION. 0.2.1. Définition des systèmes de factorisation. 0.2.2. Propriétés générales des systèmes de factorisation. 0.2.3. Exemple. 0.2.4. Remarque. 0.3. CLASSES REMARQUABLES D'EPIMORPHISMES ET DE MONOMORPHISMES. ... 0.3.1. Les épimorphismes clos. 0.3.2. Les épimorphismes forts. 0.3.3. Epimorphismes relatifs et monomorphismes relatifs. 0.3.4. Les monomorphlsmes forts. 0.3.5. Quelques propriétés de ces classes remarquables. p. 12 p. 13 p. p. 14 p. 14 p. 14 p. 15 p. 15 p. 16 p. 16 0.4. GENERATION. 0.4.1. Catégorie de décomposition. 0.4.2. Sous-classe dom-engendrant une classe d'épimorphismes. p. 17 p. 17 1. LE THEOREME DE BIRKHOFF CATEGORIQUE p. 19 1.1. VALIDATION. p. 21 1.1.1. Validation d'un épimorphisme. 1.1.2. Modèles. p. 21 p. 21 78 1.1.3. Exemples (où l'on voit apparaître des formules). p. 21 1.1.4. Exemple (où l'on continue à voir apparaître des formules). .... p. 22 1.1.5. Exemple (où l'on volt apparaître des formules un peu particulières)... p. 23 1.2. PROPRIETES DE LA CLASSE Mod(J>. 1.2.1. Propriété 1 . 1.2.2. Propriété 2 . 1.2.3. Objets H-projectif s. 1.2.4. Propriété 3 . 1.2.5. Propriété fondamentale de p. 24 p. 24 p. 24 p. 25 p. 26 p. 26 Mod(JSf). 1.3. BONNES CATEGORIES ET EXTENSIONS LIBRES. 1.3.1. Catégories A peu d'objets quotients. 1.3.2. Catégories ayant suffisamment d'objets projectifs. 1.3.3. Bonnes catégories. 1.3.4. Extensions libres. 1.3.5. Proposition (existence d'extensions libres dans une bonne catégorie). 1.4. BONNES CLASSES D'EPIMORPHISMES DANS UNE BONNE CATEGORIE 1.4.1. La bonne classe canonique d'épimorphismes. 1.4.2. Bonnes classes primitives d'épimorphismes. 1.4.3. Exemple. 1.4.4. Proposition. 1.5. LE THEOREME DE BIRKHOFF DANS UNE BONNE CATEGORIE. p. 27 p. 27 p. 27 p. 27 p. 28 p. 29 p. 30 p, 30 p. 30 p. 31 p. 31 p. 32 1.5.1. Enoncé du théorème de Birkhoff catégorique. 1.5.2. Preuve du théorème de Birkhoff catégorique. p. 32 p. 32 2. INTERPRETATION DU THEOREME DE BIRKHOFF CATEGORIQUE DANS LA CATEGORIE DES ALGEBRES TOTALES, LA CATEGORIE DES ALGEBRES PARTIELLES, LA CATEGORIE DES M3DELBS. p. 35 2.1. DEFINITION DES CATEGORIES 2.1.1. La catégorie 2.1.2. La catégorie 2.1.3. La catégorie T P M T , P , M . des algèbres totales. des algèbres partielles. des modèles. p. 37 p. 37 p. 37 p. 38 79 2.2. CARACTERISATION DANS T, P, M DES CLASSES REMARQUABLES DEFINIES EN 0.3. p. 38 2.2.1. Caractérisâtion intrinsèque. 2.2.2. Exemple. 2.2.3. Présentation en termes de "passages aux quotients" des éléments de H., Hr, Epi. p. 38 p. 41 2.3. CARACTERISATION DANS T, P, 1 DES OBJETS H-PROJECTIFS, POUR Hc, H», Hr. H = Iso, p. 43 2.3.1. Tableau de caractérlsation. 2.3.2. Présentation des objets H-projectifs de T, P, M (pour H = Iso, Hc, H., Hr) comme quotients. p. 41 p. 43 .... 2.4. STRUCTURES DE BONNES CATEGORIES SUR T, P, M ET BONNES CLASSES D'EPIMORPHISMES ASSOCIEES p. 45 p. 48 2.4.1. Choix de structures de bonnes catégories sur T, P, M. p. 46 2.4.2. Caractérlsation dans T, P, M des bonnes classes canoniques d'épimorphismes et choix de bonnes classes primitives d'épimorphismes. p. 48 2.5. TRADUCTION EN TERMES DE FORMULES. p. 50 2.5.1. Considérations préliminaires. p. 50 2.5.2. Classes primitives de formules pour les algèbres totales (i. e. T). • . p. 51 2.5.3. Classes primitives de formules pour les algèbres partielles (i. e. P). p. 51 2.5.4. Classes primitives de formules pour les modèles (1. e. M) p. 53 3. LE THEOREME DE BIRKHOFF CATEGORIQUE FIMITAIRE. p. 55 3.1. FINITUDE. p. 57 3.1.1. Position du problème. 3.1.2. Objets finiment présentables. 3.1.3. Exemples. p. 57 p. 57 p. 58 3.2. LE CADRE CATEGORIQUE DU THEOREME DE BIRKHOFF FINITAIRE, .. 3.2.1. Bonnes classes d'épimorphismes finitaires. 3.2.2. Propriété fondamentale de p. 59 Mod(E), si ECB9WHS 3.3. VERSION FINITAIRE DU THEOREME DE BIRKHOFF CATEGORIQUE. 3.3.1. Enoncé du théorème de Birkhoff catégorique finitaire. p. 59 p. 59 ... p. 60 p. 60 80 3.3.2. Preuve du théorème de Birkhoff catégorique finitaire. 3.3.3. Commentaire. p. 60 p. 62 4. TRADUCTION DU THEOREME DE BIRKHOFF CATEGORIQUE FINITAIRE DAMS LA CATEGORIE DES ALGEBRES TOTALES, LA CATEGORIE DBS ALGEBRES PARTIELLES, LA CATEGORIE DES 10DELES. p. 63 4.1. CLASSES PRIMITIVES DE FORMULES FINITAIRES. 4.1.1. Le théorème de Birkhoff catégorique finitaire s'applique A T, P, M 4.1.2. Description des classes primitives de formules finitaires. .... p. 65 p. 65 p. 65 4.2. COROLLAIRES DE L'APPLICATION DU THEOREME DE BIRKHOFF CATEGORIQUE FINITAIRE A T, P, M. p. 66 4.2.1. Corollaire 1 . p. 66 4.2.2. Corollaire 2 . p. 66 4.3. COMPLEMENTS SPECIFIQUES A T, P, M . p. 67 4.3.1. Préliminaires. 4.3.2. Propriété complémentaire. p. 67 p. 67 5. COMPLETUDE. p. 69 5.1. LA COMPLETUDE EN TERMES DE FORMULES, POUR LES ALGEBRES TOTALES, LES ALGEBRES PARTIELLES ET LES MODELES. p. 71 5.1.1. Position du problème. p, 71 5.1.2. Résolution du problème. p. 71 5.2. LA COMPLETUDE EN TERMES CATEGORIQUES. p. 72 5.2.1. Position du problème. 5.2.2. Remarques et suggestions pour la résolution du problème. p. 72 p. 72