Objet libre
En mathématiques, la notion d'objet libre est l'un des concepts de base de l'algèbre générale. Elle appartient à l'algèbre universelle, car elle s'applique à tous les types de structures algébriques (avec des opérations finitaires). Elle se formule plus généralement dans le langage de la théorie des catégories :
Des exemples d'objets libres sont les groupes libres, les groupes abéliens libres, les algèbres tensorielles… Informellement, un objet libre sur un ensemble X est une structure algébrique « générique » sur X : les seules équations qui relient les éléments de l'objet libre sont celles imposées par les axiomes qui définissent la structure algébrique.
Définition
modifierLa notion d'objet libre sur un ensemble est une généralisation directe de celle d'espace vectoriel de base prescrite. Pour toute base X d'un espace vectoriel V, toute application de X dans un espace vectoriel Y s'étend de façon unique en une application linéaire de V dans Y. La définition suivante généralise cette situation à n'importe quelle catégorie.
Soit (C, G) une catégorie concrète (c'est-à-dire que G, de C dans la catégorie Set des ensembles, est un foncteur fidèle, appelé « foncteur d'oubli » : pour tout objet Y de C, G(Y) est l'ensemble sous-jacent à Y, lorsqu'on « oublie » sa structure algébrique). Un objet de C libre sur un ensemble X (appelé « base » de l'objet libre) est un objet F(X) ∈ C, muni d'une application
(appelée « injection canonique »), vérifiant la propriété universelle suivante : pour tout objet Y de C et toute application g de X dans l'ensemble G(Y), il existe un unique morphisme f : F(X) → Y tel que g = G(f) ∘ ηX, autrement dit, l'application:
est bijective.
Construction
modifierPour construire un objet libre sur un ensemble, on procède généralement en deux étapes.
Cas d'une loi associative
modifierPour les structures comportant une seule loi et si cette loi est associative, la première étape consiste à considérer tous les mots (finis) sur un certain alphabet. La seconde étape consiste à quotienter cet ensemble de mots par la relation d'équivalence engendrée par toutes les relations imposées par les axiomes de la structure algébrique considérée. L'objet libre est l'ensemble des classes d'équivalence.
Par exemple, pour construire le groupe libre sur une paire, on peut partir d'un alphabet de cinq lettres S = { e, a, b, a', b' }. Sur l'ensemble W*(S) des mots non vides sur cet alphabet, la relation d'équivalence ~ doit seulement imposer les relations vérifiées dans tout groupe de neutre e et contenant deux éléments a et b de symétriques respectifs a' et b' : pour toutes chaînes de caractères u et v, uaa'v ~ ua'av ~ ubb'v ~ ub'bv ~ uev et si u ou v est non vide, uev ~ uv. Le groupe libre F2 est l'ensemble quotient W*(S)/~. Pour une variante de construction autorisant le mot vide, ce qui dispense de la lettre e dans l'alphabet pour représenter le neutre, voir le § « Construction » de l'article sur les groupes libres.
Un exemple plus simple est celui des monoïdes libres, pour lesquels la seconde étape est inutile : le monoïde libre sur un ensemble X est simplement la fermeture de Kleene de l'alphabet X (elle inclut le mot vide, qui produit le neutre).
Cas général
modifierPour une structure algébrique quelconque, où la loi n'est pas nécessairement associative (ni unique), il faut dans la première étape ajouter des parenthèses dans les chaînes de caractères formant les mots et un symbole pour chaque loi — et si elles ne sont pas binaires, tenir compte de leurs arités respectives —, ce qui conduit à une algèbre de termes : c'est l'objet libre parmi les structures algébriques de signature fixée.
Son quotient par la relation d'équivalence est parfois difficile à calculer. Par exemple, on sait très peu de choses sur les algèbres de Heyting libres à plus d'un générateur[1]. Le problème de déterminer si deux chaînes de caractères appartiennent à la même classe d'équivalence est le problème du mot.
Comme le suggèrent les exemples, les objets libres peuvent être construits par la syntaxe ; réciproquement, dans une certaine mesure, les principaux objets produits par la syntaxe peuvent être expliqués et caractérisés comme des objets libres, d'une manière qui rend plus compréhensible (et plus facile à mémoriser) leur aspect apparemment lourd.
Foncteur « objet libre »
modifierPar définition, pour toute catégorie concrète C, le foncteur « objet libre » F est — s'il existe — adjoint à gauche du foncteur d'oubli G.
La transformation naturelle η : idSet → G ∘ F est appelée l'unité ; avec la co-unité ε : F ∘ G → idC, on peut construire une monade. Réciproquement, F existe dès que C est monadique sur Set. C'est le cas si C est une variété.
D'autres types de foncteurs d'oubli, à valeurs dans d'autres catégories que celle des ensembles, possèdent un adjoint à gauche, qu'on peut encore appeler foncteur « objet libre ». Par exemple, l'algèbre tensorielle d'un espace vectoriel V est l'algèbre (associative et unifère) libre sur V. De même, l'algèbre symétrique de V est l'algèbre commutative libre sur V.
Exemples
modifierNotes et références
modifier- (en) Peter Johnstone, Stone Spaces, CUP, , 370 p. (ISBN 978-0-521-23893-9) (l'algèbre de Heyting libre à un générateur est traitée au chapitre 1, section 4.11).
