Chapitre 3 Aspects catégoriques

3.1 Généralités

Une catégorie est une classe (on n'entre pas dans les subtilités classe vs. ensemble) d'objets et de morphismes. Chaque morphisme va d'un objet (sa source) à un objet (son but). Les morphismes de source X et de but Y donnés dans une catégorie forment un ensemble Hom_C(X,Y). On peut omettre le C si cela ne crée pas d'ambiguïté. On peut composer deux morphismes dès lors que le but du premier est la source du second, et alors le composé est un morphisme qui va de la source du premier au but du deuxième. En outre chaque objet X a un morphisme identité 1_X qui l'a pour source et but. Les égalités suivantes sont exigées (ab)c=a(bc) dès qu'on peut composer les morphismes a,b,c et a1_X=a, 1_Xb=b dès que l'on peut composer l'identité 1_X d'un objet avec les morphismes a et b.

Un isomorphisme entre deux objets X et Y est un morphisme j:X® Y tel qu'il existe un morphisme k:Y® X avec kj=1_X et jk=1_Y, où 1_X et 1_Y sont les identités de X et Y.

Un foncteur F est une application d'une catégorie C vers une catégorie D, telle que pour tous objets c₁, c₂ de C, et tout morphisme a de c₁ vers c₂ le résultat F(a) est un morphisme de F(c₁) vers F(c₂); on exige de plus que l'identité i₁ de l'objet c a pour image F(i) l'identité de F(c), et que F(ab)=F(a)F(b) pour tous morphismes composables a,b de C.

Un foncteur F:C® D a un foncteur adjoint à droite G:D® C si on a un morphisme naturel j_X:X® GF(X) telle que l'application Hom_D(F(X),Y)®Hom_C(X,G(Y)) définie par f|® G(f)j_X est une bijection pour tous X et Y. On alors aussi un morphisme naturel i_Y:FG(Y)® Y telle que Hom_C(X,G(Y))®Hom_D(F(X),Y) définie par g|® i_Y F(g) soit la bijection inverse de la précédente. De sorte que F est adjoint à gauche de G.

Pour plus de détails voir [25].

3.1.1 Exemples

Une catégorie bien usuelle est Ens, celle dont les objets sont les ensembles, et les morphismes sont les applications.

Une autre est Grp, celle des groupes, avec comme morphismes les homomorphismes de groupe. On a alors un foncteur d'oubli U: au groupe G on associe U(G), l'ensemble sous-jacent à G et au morphisme a:G® H on associe l'application U(a):U(G)® U(H) qui n'est autre que a, en oubliant ses propriétés supplémentaires.

Une troisième est celle des monoïdes, Mon. Les monoïdes sont comme les groupes, sauf qu'on n'exige pas que chaque élément admette un inverse. Par exemple, les éléments d'un anneau, avec la multiplication de cet anneau, forment un monoïde. Voici la table de la multiplication pour l'anneau

	1	2	3
0	0	0	0
1	1	2	3
2	2	0	2
3	3	2	1

On voit que 1 est neutre, que 3 est son propre inverse, mais que ni 2 ni 0 n'ont d'inverse.

On peut observer un premier foncteur d'oubli Grp®Mon, et un deuxième Mon®Ens dont la composition donne U.

On a un foncteur en sens inverse, des ensembles vers les monoïdes qui a un ensemble E associe le monoïde libre sur E, c'est l'ensemble des suites finies d'éléments de E, avec la concaténation ([a₁... a_k],[b₁... b_l])|®[a₁... a_kb₁... b_l], dont la suite vide [] est le neutre. On notera que ce foncteur est l'adjoint à gauche du foncteur d'oubli de Mon dans Ens.

On a aussi un foncteur de Ens vers Grp, qui à un ensemble E associe le groupe libre sur E, et qui est l'adjoint à gauche du foncteur d'oubli U de Grp dans Ens.

On s'accroche pour la description de cette chose! C'est un groupe. On considère l'ensemble des chaînes d'éléments de la forme [a₁,a₂,... a_k], avec chaque a_i qui est soit un élément de E soit l'inverse (formel) d'un élément de E, avec l'opération de concaténation des chaînes, quotienté par la relation d'équivalence engendrée par [aa^-1]=[]=[a^-1a]. Ce qui veut dire que dans une chaîne on peut sans changer la classe d'équivalence insérer ou supprimer deux éléments successifs inverses l'un de l'autre, et que deux chaînes seront considérées comme équivalentes si on peut passer de l'une à l'autre par une succession de telles modifications.

Si on a une application f:E® F, le foncteur Ens®Mon introduit plus haut donne un morphisme de monoïdes [a₁,...,a_k]|®[f(a₁),...,f(a_k)]. De même pour la formation de groupes libres.

En particulier, si E=Ø, (l'ensemble vide), le monoïde libre sur E et le groupe libre sur E sont réduits à un élément, ce qui ne laisse guère de choix pour l'opération, Pour |E|=1, le monoïde libre est isomorphe à

avec son addition et le groupe libre à

avec son addition.

3.2 Catégories de graphes

On doit décider des objets: les graphes, bien sûr, et des morphismes. Le plus naturel est de décider qu'un morphisme de graphes G® H est une application de l'ensemble des sommets de G sur ceux de H qui envoie toute arête de G sur une arête de H. Cette option 1 est la plus appropriéee dans les problèmes de colorations de graphes: voir par exemple [111].

Une autre décision (option 2) raisonnable est que chaque arête est envoyée sur un arête ou un sommet. Ce qui revient à admettre tacitement que chaque sommet a une boucle. Dans cette seconde option, il y a beaucoup plus de morphismes entre deux graphes donnés. Par exemple, les projections de la somme cartésienne vers ses composantes sont alors des morphismes de graphes, ce qui n'est pas le cas --- sauf exceptions triviales --- pour la première option.

Le line graphe est un foncteur de la catégorie des graphes (options 1 ou 2) vers la catégorie des graphes (option 2).

Pour les graphes orientés, on prendra pour objets les garphes orientés, pour morphismes de G vers H les applications qui envoient arc sur arc (option 1). Là aussi, il y a l'option de replier les arcs.

3.3 Produits, noyaux, objet final

Dans une catégorie, on appelle produit de deux objets X,Y, un objet P muni de deux morphismes p_X:P® X et p_Y:P® Y tel que chaque fois qu'on a un objet T avec deux morphismes q_X:T® X et T® Y on a un unique morphisme q_Z:T® Z avec q_X=p_Xq_Z et q_Y=p_Yq_Z. Cela n'existe pas toujours ! Mais si cela existe, c'est unique à isomorphisme près.

Pour les ensembles, le produit convient. Pour les groupes, le produit direct convient. Pour les graphes (option 1), le produit cartésien convient; pour les graphes (option 2) le produit fort convient.

On peut aussi former (éventuellement) le produit d'une famille d'objets: X_i, iÎ I; c'est l'objet P s'il existe muni d'une famille p_i:P® X_i de morphismes tel que pout tout objet Q muni d'une famille q_i:Q® X_i il existe un unique morphisme q:Q® P tel que q_i=p_iq pour tout iÎ I. Cela n'existe pas toujours ! Mais si cela existe, c'est unique à isomorphisme près.

Le noyau d'une paire de morphismes k₁,k₂:X® Y est l'objet K muni d'un morphisme i:K® X tel que k₁i=k₂i tel que pout tout objet L muni d'un morphisme j:L® X il existe un unique morphisme n:L® K tel que j=in. On peut bien sûr définir de même le noyau d'une famille de morphismes k_i:X® Y. Cela n'existe pas toujours ! Mais si cela existe, c'est unique à isomorphisme près.

L'objet final T d'une catégorie C est tel que Hom(X,T) a exactement un élément pour tout objet X de C.

Refrain: Cela n'existe pas toujours...

3.3.1 Exemples

.

La catégorie des ensembles a un élément final: n'importe quel ensemble à un élément convient. Celle des groupes aussi: le groupe à un élément. Celle des graphes (option 2) aussi: le graphe à un sommet. En revanche celle des graphes (option 1) n'en a pas.

3.4 Sommes, conoyaux, objet initial

On définit de même la somme de X et Y: c'est ---s'il en existe--- un objet S muni de deux morphismes i_X:X® S, i_Y:Y® S tel que tout objet Z muni de deux morphismes f_X:X® Z, f_Y:Y® Z donne lieu à un unique morphisme m:S® Z tel que f_X=mi_X et f_Y=mi_Y.

L'objet initial I, s'il en existe, est caractérisé par |Hom(I,X)|=1 pour tout objet X.

Le conoyau de deux morphismes k₁,k₂:X® Y est l'objet K s'il existe muni d'un morphisme p:Y® K tel que pk₁=pk₂ et que tout morphisme j:Y® L tel que jk₁=jk₂ se factorise de façon unique en j=lp

3.4.1 Exemples

La catégorie des ensembles a pour élément initial l'ensemble vide, celle des groupes le groupe à 1 élément, celle des graphes le graphe sans sommet (et sans arête).

3.5 Objet nul

Si la catégorie C a un objet N initial et final, cet objet est dit nul. Dans ce cas chaque paire d'objets X,Y admet un morphisme 0:X® Y appelé le morphisme nul qui est le composé de l'unique morphisme X® N (vu que N est final) et de l'unique morphisme N® Y (vu que N est initial.

Dans ce cas il y a un morphisme naturel de la somme de deux éléments X,Y vers leur produit: on choisit les morphismes I_X:X® X et 0:X® Y, ce qui donne un morphisme a_X:X® X×_C Y et de même les deux morphismes I_Y:Y® Y et 0:Y® X donnent un morphismes a_Y:Y® X×_C Y, et cette paire a_X,a_Y donne un morphisme: X+_C Y® X×_C Y.

3.5.1 Exemple

La catégorie Ens n'a pas d'objet nul: il n'y a pas de morphisme du tout de son objet final (à 1 élément) vers son objet initial (vide) et a fortiori pas d'isomorphisme.

Le groupe à 1 élément est nul dans la catégorie Grp et aussi dans la catégorie GrAb. Dans cette dernière, le morphisme somme à produit est un isomorphisme.

Présentation de groupe Il s'agit de construire un groupe. On se donne un ensemble générateur G, et un ensemble de relations R, c'est-à-dire d'éléments du groupe libre á Gñ sur G. On forme le sous-groupe normal H de á Gñ minimal parmi ceux qui contiennent R, et le groupe-quotient K=á Gñ/H.

Alors K peut être vu comme l'objet initial dans la catégorie dont les objets sont les groupes L munis d'un morphisme d'ensembles G® U(L) dans lesquels les images des éléments de R sont le neutre.

3.6 Groupes et groupes abéliens

On a une catégorie GrAb des groupes abéliens (on dit aussi commutatifs). Ses objets sont les groupes abéliens (ce qui veut dire ab=ba pour tous éléments a,b du groupe) et les morphismes tout simplement les morphismes de groupes. Il y a donc un foncteur d'oubli très simple de GrAb dans Grp.

Mais les deux catégories sont bien différentes. La somme dans GrAb de deux groupes X,Y dans GrAb est isomorphe au produit direct, avec X® P défini par x|® (x,e_Y) et Y® P par y|® (e_X,y). La somme dans Grp de X et Y est l'ensemble dont les éléments sont les chaînes [x₁y₁x₂y₂... x_ky_k], avec l'opération de concaténation, quotienté par la relation d'équivalence engendrée par [x_ie_Yx_j]=[x_ix_j] et [y_ie_Xy_j]=[y_iy_j].

Ainsi la somme de deux exemplaires de

dans GrAb est un groupe à 4 éléments, alors que la somme de deux exemplaires de

dans Grp est isomorphe au produit semi-direct

{-1,1} défini par (a,s)(b,t)=(a+st,st). L'isomorphisme est donné (par exemple) par x|®(0,(-1)^x) si x est dans le premier exemplaire, et 0|®(0,1) et 1|®(1,-1) pour les éléments du second exemplaire.

Adjoint à gauche Ce foncteur d'oubli c de GrAb dans Grp a un adjoint à gauche qui est défini à l'aide du morphisme (dans Grp) G® c(G/G') où G' est le sous groupe (normal) de G engendré par les ghg^-1h^-1, où g et h parcourent G, ou si on préfère, à l'aide du morphisme c(G)/(c(G))'® G qui est en fait un isomorphisme pour tout groupe G de GrAb, car le groupe c(G) est isomorphe à G et tous les ghg^-1h^-1, avec g et h parcourent c(G), sont égaux au neutre.

Pas d'adjoint à droite En revanche, c n'a pas d'adjoint à droite w. En effet, on devrait avoir des ensembles de morphismes égaux (à isomorphisme naturel près)

Hom_Grp(cX+_GrpcY,Z) =Hom_Grp(cX,Z)×Hom_Grp(cY,Z) =Hom_GrAb(X,wZ)×Hom_GrAb(Y,wZ) =Hom_GrAb(X+_GrAbY,wZ) =Hom_Grp(c(X+_GrAbY),Z)

On devrait donc avoir cX+_GrpcY et c(X+_GrAbY) isomorphes; ce n'est pas vrai en général (on l'a vu pour X=Y=

).

Et voilà. C'était une preuve typique de la théorie des catégories !

3.7 Ensembles avec structure

On a déja vu des exemples (groupes, graphes, etc.) en voici d'autres qui vont revenir par la suite.

3.7.1 Ensembles pointés

Les objets sont les ensembles non vides avec un élément spécial. Soit (E,e) et (D,d) de tels objets. Un morphisme f dans cette catégorie de (D,d) vers (E,e) est une application de D dans E qui de plus envoie d sur e.

Cette catégorie a un objet nul: un ensemble a un seul élément, qui est son élément spécial convient. Elle a des produits : E× D avec le point (e,d) est le produit de (E,e) et (D,d), des noyaux : si f,g:(D,d)®(E,e) sont des morphismes, le sous-ensemble de D formé des x tels que f(x)=g(x), avec l'élément d est noyau de la paire f,g, des sommes: l'union disjointe de E et F quotientée par e=d avec l'élément spécial formé de e et d, des conoyaux: si f,g:(D,d)®(E,e) sont des morphismes, on quotiente E par la relation d'équivalence engendrée par les f(x)=g(x),xÎ D.

3.7.2 Ensembles munis d'une partition

Les objets sont les ensembles mnui d'une partition. Les morphismes de (E,P) vers (F,Q) sont les applications E® F telles que des éléments de la même classe dans E aient pour images des éléments de la même classe dans F.

Il y a un objet initial (Ø,Ø) et un objet final, l'ensemble à 1 élément avec sa seule partition. Le produit de (E,P) et (F,Q) est E× F muni des parties A× B, avec A,B parcourant P,Q. Le noyau de f,g:(E,P)®(F,Q) est le sous-ensemble H de E formé des xÎ E tels que f(x)=g(x), avec les parties de la forme HÇ A, AÎ P qui ne sont pas vides.

Il y a des sommes: (prendre l'union disjointe de E et F, avec les parties copiées de celles qu'on a dans P et Q), et des conoyaux: pour fornmer un conoyau de f,g:(E,P)®(F,Q) prendre le conoyau j:F® K d'ensembles et la partition R de K la plus fine telle que les j(A),AÎ Q sont contenus dans des parties appartenant à R.

Par exemple, si E={a} avec la partition {{a}}, si F={c,d,e} avec la partition {{c,d},{e}}, si f(a)=c et g(a)=e alors dans le conoyau (K,R) l'ensemble K a deux éléments, j(c)=j(e) et j(d), comme c et d sont dans la même classe, il faut mettre j(c) et j(d) dans la même classe, donc R={K}.

On notera que le foncteur d'oubli de la catégorie des ensembles avec partition dans Ens (on oublie la partition) a un adjoint à droite et un adjoint à gauche. Pour l'adjoint à droite, on munit chaque ensemble Y de sa partition (grossière) en au plus une partie. Pour l'adjoint à gauche on munit chaque ensemble de sa partition en parties à un élément.

3.8 Produit tensoriel

Il peut arriver que l'ensemble Hom_C(X,Y) soit naturellement lui aussi un objet de la catégorie C, ce qui veut dire que si f:Y® Z est un morphisme, alors Hom_C(X,Y)®Hom_C(X,Z) défini par g|® fg est un morphisme de C, que Hom_C(Z,T)®Hom_C(Y,T) défini par g|® gf est un morphisme de C, etc. Dans ce cas on peut envisager l'existence d'un objet de C, noté XÄ Y tel que Hom_C(XÄ Y,Z)~ Hom_C(X,Hom_C(Y,Z)).

Plus généralement, si les morphismes de C ont une structure dans D, on peut tenter de représenter Hom_D(X,Hom_C(Y,·) par un objet dans C, c'est-à-dire de former un objet XÄ Y de C tel que Hom_D(X,Hom_C(Y,Z)~ Hom_C((XÄ Y),Z).

Dans la catégorie Ens, c'est le produit cartésien. Pour la catégorie des groupes abéliens, en donnant à Hom_GrAb la structure de groupe abélien par (f+g)(x)=f(x)+g(x), c'est le produit tensoriel habituel.

Un autre exemple fort utilisé en algèbre : soit R un anneau, Mod_g la catégorie des modules à gauche sur R et Mod_d celle des modules à droite sur R. On a une structure naturelle de R-module à droite sur Hom(M,G) (les applications préservant l'addition --- économisons l'écriture d'un foncteur d'oubli) si M est un module à gauche et G un groupe commutatif, en définissant fl par (fl)(m)=f(l m) pour tout mÎ M. On a alors un groupe abélien NÄ M tel que Hom_GrAb((NÄ M),G)~ Hom_Mod_{_d}(N,Hom_Mod_{_g}(M,G)) de façon naturelle.

Si C a un objet initial I, on a |Hom_C(I,Y)|=1 pour tout Y, donc si on a un foncteur d'oubli de C dans Ens qui est fidèle, c'est-à-dire transforme des morphismes distincts de C en morphismes distincts d'ensembles, on a aussi |Hom_C(X,Hom_C(I,Y))=1|, ce qui se traduit par: XÄ I existe, et est isomorphe à I.

Pour la catégorie des graphes, on met une arête entre deux morphismes de graphes f,g:G® H si pour tout sommet x de G les sommets f(x) et g(x) sont adjacents dans H (ce qui autorise f(x)=g(x) pour l'option 2).

Examinons par exemple, le n-cycle C_n pour n³ 3 et l'arête K₂.

Dans l'option 1, on a deux morphismes C_n® K₂ liés par une arête si n est pair et aucun si n est impair. Pour l'option 2, on a un graphe complet à 2ⁿ sommets dans les deux cas.

Dans l'option 1, il n'y a aucun morphisme C₃® C₄, dans l'option 2 il y en a 28, qui sont les 4 constants et les 24 qui envoient un sommet du triangle (3 choix) sur un sommet du carré (4 choix) et les deux autres sur un sommet voisin (2 choix). Le graphe de ces morphismes n'est pas complet.

Dans les graphes pointés, avec l'option 2, le morphisme somme à produit est facile à voir (figure 3.1):

Figure 3.1 : Somme et produit de deux chemins pointés

Dans la catégorie des graphes orientés, on a aussi la possibilité de structurer en graphe orienté Hom(G,H), en mettant un arc de f vers g si on a pour tout xÎ G un arc de f(x) vers g(x) dans H.

On note que le line-graphe dans les graphes orientés est un foncteur, presque isomorphe naturellement à Hom(U₁,·) (abréviation de H|® Hom(U₁,H)) pour l'option 1, où U₁ est le graphe orienté à 2 sommets et un arc qui les joint. En effet, le graphe orienté G de la figure 3.2 montre que ces foncteurs ne sont pas isomorphes. Cependant on peut considérer la catégorie des graphes orientés qui n'ont pas ce graphe G comme sous-graphe induit, avec l'option 1 pour le choix des morphismes.

Figure 3.2 : Un graphe orienté G avec Hom(U₁,G) non isomorphe au line-graphe

Dans cette catégorie, comme dans les graphes orientés en général (option 1), on a donc pour U_n est le chemin orienté à n+1 sommets.

Hom(U_n,U_m)~

ì
í
î

U_m-n	si m³ n
Ø	sinon

On constate alors que le line-graphe itéré n fois n'est autre (à isomorphisme naturel près) que Hom(U_n,·), où U_n est le chemin orienté à n+1 sommets et on a donc U_nÄ U_m~ U_n+m dans la catégorie des graphes orientés dépourvus du graphe induit particulier G (option 1).