Structures algébriques libres
Dans ce fil, Homo Topi s'intéressait aux structures libres sur un ensemble $X$, avec différentes notions de structures : monoïdes, groupes, modules, anneaux...
Sur sa demande (et mon conseil) je vais régler le problème une fois pour toutes, pour toutes les structures algébriques (je préciserai ce que j'entends par là). Je le répète car dans ledit fil il y a plusieurs moments où ce n'était pas clair : ce que je présente va être une construction explicite des structures libres dans les cas qui nous intéressent. Il y a au moins 2 autres manières de prouver l'existence des structures libres sur tout ensemble, l'une purement catégorique en utilisant le théorème du foncteur adjoint qui s'applique trivialement dans les situations considérées, et l'autre qui avait été mentionnée par christophe dans un fil dans Fondements et Logique, qui consiste à prendre un produit suffisamment gros. Je pourrais présenter celle-là plus précisément, mais elle est moins explicite et ne correspondra donc pas au voeu de Homo Topi : je ne le ferai que si c'est demandé (en fait c'est la même chose que la preuve catégorique mais on refait la preuve du théorème que je mentionnais à la main, et donc ça paraît moins abstrait). Il y a beaucoup de choses que je ne prouve pas: soit ce sera évident pour vous, soit cela veut dire que je vous laisse le prouver.
Voici donc :
Déjà le cadre. On considère un ensemble $S$ (ensemble de "symboles de fonctions") muni d'une application $a : S\to \N$ ("arité"). Les éléments de $S$ sont à interpréter comme des symboles qui représentent des fonctions (par exemple le symbole $+$, le symbole $\times$), et si $s\in S$, $a(s)$ représente l'arité de ce symbole, par exemple pour le symbole $+$ ce serait $2$, pour $1$ ce serait $0$, etc. : c'est le nombre d'arguments que prendra la fonction. Un tel couple $\tau = (S,a)$ peut s'appeler par exemple un type d'algèbres.
Etant donné $\tau = (S,a)$ un type d'algèbres, une algèbre de type $\tau$ (ou $\tau$-algèbre), $\mathfrak{A}$ est un ensemble $A$ muni de, pour tout $f\in S$, une application $f^\mathfrak{A} : A^{a(f)} \to A$. En particulier, lorsque $a(f) = 0$, il s'agit essentiellement d'un élément de $A$; et lorsque $a(f) = 2$ on retrouve la notion d'opération binaire. Je risque de faire souvent l'abus d'identifier $\mathfrak{A}$ et $A$ et d'écrire $f$ pour $f^\mathfrak{A}$. Je vais essayer d'éviter mais parfois j'oublierai.
Si $\mathfrak{A,B}$ sont deux algèbres de type $\tau$, un morphisme de $\tau$-algèbres est une application $h:A\to B$ telle que pour tout $f\in S$, tous $x_1,...,x_{a(f)} \in A$, on ait $h(f^\mathfrak{A}(x_1,...,x_{a(f)})) = f^\mathfrak{B}(h(x_1),...,h(x_{a(f)}))$: "$h$ est compatible avec les opérations".
Exemples : Si $\tau =( \{\times\}, \times \mapsto 2)$ on retrouve la notion de magma et de morphisme de magma. Si $\mathfrak{A,B}$ s'avèrent être des groupes, c'est un morphisme de groupes. Mais pour les groupes je préfère $\tau = \{\times, e, \iota\}$ où $\times$ est d'arité $2$, $e$ d'arité $0$ et $\iota$ d'arité $1$.
Exercice : Voir que les anneaux, les $A$-modules pour un anneau $A$ fixé, les groupes, les monoïdes sont des cas particuliers de $\tau$-algèbres pour certains types $\tau$.
Si $\mathfrak{A}$ est une $\tau$-algèbre, une sous-$\tau$-algèbre (sous-algèbre si le contexte est clair) de $\mathfrak{A}$ est un sous-ensemble $C\subset A$ qui est stable par toutes les opérations : pour tout $f\in S$, $f^\mathfrak{A}(C^{a(f)})\subset C$. Il est évident qu'une intersection de sous-algèbres est une sous-algèbre, donc on a une notion de sous-algèbre engendrée par un sous-ensemble $X$. Si $C\subset A$ est une sous-algèbre, il existe une unique structure d'algèbre $\mathfrak{C}$ sur $C$ telle que l'inclusion $C\to A$ soit un morphisme $\mathfrak{C\to A}$
Si $\mathfrak{A}$ est une algèbre ($\tau$ est fixé et je ne le mentionne pas quand c'est clair), une congruence sur $\mathfrak{A}$ est une relation d'équivalence $R$ sur $A$ telle que pour tout $f\in S$, $(x_1,y_1),...,(x_{a(f)},y_{a(f)}) \in R$, alors $(f^\mathfrak{A}(x_1,...,x_{a(f)}), f^\mathfrak{A}(y_1,...,y_{a(f)}) )\in R$ : si $x_i$ est relié à $y_i$ pour tout $i$, alors $f^\mathfrak{A}(x_1,...,x_{a(f)})$ est relié à $f^\mathfrak{A}(y_1,...,y_{a(f)})$ : "$R$ est compatible avec les opérations".
Une intersection de congruences est évidemment une congruence, donc on a une notion de congruence engendrée par un sous-ensemble $X\subset A^2$.
Si $R$ est une congruence, $A/R$ a une unique structure d'algèbre $\mathfrak{A}/R$ telle que la projection canonique $\pi : A\to A/R$ soit un morphisme d'algèbres.
Si $h: \mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors $\ker (h) = \{(x,y)\in A^2\mid h(x) = h(y)\}$ est une congruence sur $\mathfrak{A}$. $\ker (\pi) =R$ lorsque $\pi$ est la projection canonique $ \mathfrak{A}\to \mathfrak{A}/R$
exercice : Pourquoi ai-je appelé ça $\ker$ ?
$\pi : \mathfrak{A}\to \mathfrak{A}/R$ a la propriété universelle suivante : si $h:\mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors il se factorise par $\pi : \mathfrak{A}\to \mathfrak{A}/R$ si et seulement si $R\subset \ker (h)$. Elle est facile à prouver si on se souvient de la propriété universelle du quotient d'un ensemble par une relation d'équivalence.
En particulier, si $X\subset A^2$ et si $R$ est la congruence engendrée par $X$, alors $\mathfrak{A}/R$ a la propriété universelle suivante : si $h:\mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors il se factorise par $\pi : \mathfrak{A}\to \mathfrak{A}/R$ si et seulement si $X\subset \ker (h)$. En effet, $\ker (h)$ étant une congruence, $R\subset \ker (h) \iff X\subset \ker (h)$.
On définit maintenant les termes sur un type $\tau = (S,a)$. On fixe un ensemble (typiquement dénombrable quand on fait de la syntaxe, mais ici quelconque) $V$ disjoint de $S$, appelé ensemble de variables. Ses éléments seront typiquement notés $\mathbf{x}$.
On définit alors inductivement un terme : les éléments de $V$ sont des termes; si $t_1,...,t_n$ sont des termes et $f\in S$ vérifie $a(f) = n$, alors $(f,t_1,...,t_n)$ est un terme; on l'écrit généralement $f(t_1,...,t_n)$. Une autre présentation équivalente (que je n'utiliserai pas) sera qu'un terme est un arbre enraciné dont les noeuds et la racine sont étiquetés par des éléments de $S$, les feuilles par des éléments de $V$, et que si un noeud est étiqueté par $f\in S$, alors il a exactement $a(f)$ fils. Je note $T(V)$ l'ensemble des termes avec variables dans $V$.
Une équation est alors un couple $(p,q)$ où $p,q \in T(V)$. Il faut y penser comme l'équation "$p=q$". Souvent, le couple $(p,q)$ est noté $p\approx q$ dans ce contexte.
L'ensemble $T(V)$ est naturellement muni d'une structure de $T$-algèbre, notée $\mathfrak{T}(V)$, définie comme suit : si $f\in S, a(f) = n$, alors $(t_1,...,t_n) \mapsto (f,t_1,...,t_n)$ est bien définie, et c'est ce qu'on note $f^{\mathfrak{T}(V)}$. Le point le plus important est le suivant, il est relativement évident, donc je n'écris pas tous les détails :
Proposition : $(\mathfrak{T}(V),i)$ est la $\tau$-algèbre libre sur $V$; où $i$ est l'inclusion $V\to T(V)$.
Preuve : Soit $\mathfrak{A}$ une $\tau$-algèbre, et $h: V\to A$ une application. On définit inductivement $g:T(V)\to A$ comme suit : $g(\mathbf{x}) = h(\mathbf{x})$ pour $\mathbf{x} \in V$, et $g((f,t_1,...,t_n) ) = f^\mathfrak{A}(g(t_1),...,g(t_n))$ sinon. Il est clair que c'est bien un morphisme d'algèbres, et qu'il vaut $h$ sur $V$. Il est de plus clair que ce morphisme est unique.
Soit $p,q\in T(V)$. On dit que l'équation $(p,q)$ est valide dans $\mathfrak{A}$, aussi noté $\mathfrak{A}\models p\approx q$ si quelle que soit $h:V\to A$, le morphisme induit $g:\mathfrak{T}(V)\to \mathfrak{A}$ vérifie $g(p) = g(q)$.
Une autre manière de le voir est la suivante : si $p$ est un terme, alors il induit une application $p^\mathfrak{A} : A^V\to A$ de la manière suivante : si $h:V\to A$, elle induit $g: \mathfrak{T}(V) \to \mathfrak{A}$, et je peux alors poser $p^\mathfrak{A}(h) = g(p)$.
Alors l'équation $(p,q)$ est valide dans $\mathfrak{A}$ si et seulement si $p^\mathfrak{A} = q^\mathfrak{A}$ .
Exercice : Avec cette notation, si $h: \mathfrak{A\to B}$ est un morphisme d'algèbres, alors $p^\mathfrak{B}\circ h^V = h\circ p^\mathfrak{A}$, où $h^V : A^V\to B^V$ est $f\mapsto h\circ f$ (si $V$ est fini de taille $n$, c'est $h^V(x_1,...,x_n) = (h(x_1),...,h(x_n))$)
Soit $E$ un ensemble d'équations; on a alors une classe d'algèbres intéressantes qui est la classe des algèbres dans lesquelles $(p,q)$ est valide (dans lesquelles $p\approx q$ est valide) pour tout $(p,q)\in E$. On dit que $E$ est valide dans $\mathfrak{A}$ si c'est le cas, ou que $\mathfrak{A}$ satisfait $E$.
Exercice : Trouver un type $\tau$ et un ensemble $E$ d'équations tels que : une $\tau$-algèbre dans laquelle $E$ est valide est un groupe, et un morphisme de telles $\tau$-algèbres est un morphisme de groupes.
Faire de même en remplaçant "groupe" par "monoïde", "anneau", "$A$-module" ($A$ anneau fixé).
Soit $\mathfrak{A}$ une algèbre, $E$ un ensemble d'équations, $R$ la congruence sur $\mathfrak{A}$ engendrée par $\{(p^\mathfrak{A}(h),q^\mathfrak{A}(h)), h: V\to A, (p,q) \in E\}$. Montrer que $\mathfrak{A}/R$ satisfait $E$. Montrer que c'est le plus gros quotient de $\mathfrak{A}$ qui satisfait $E$; en particulier si $A$ satisfait $E$ montrer que la projection canonique $\mathfrak{A}\to \mathfrak{A}/R$ est un isomorphisme. Dans la suite, je noterai $E^\mathfrak{A}$ cette congruence.
Théorème : Soit $\tau=(S,a)$ un type d'algèbres, $E$ un ensemble d'équations sur $\tau$, avec ensemble de variables $V$. On appelle $(\tau,E)$-algèbre une $\tau$-algèbre qui satisfait $E$. Soit $X$ un ensemble disjoint de $S$, $\pi :\mathfrak{T}(X) \to \mathfrak{T}(X)/E^{\mathfrak{T}(X)}$ le morphisme canonique et $i :X\to T(X)$ l'inclusion. Alors $( \mathfrak{T}(X)/E^{\mathfrak{T}(X)}, i)$ est une $(\tau,E)$-algèbre libre sur $X$.
Preuve : Déjà, par ce que j'ai dit avant, c'est bien un $(\tau,E)$-algèbre.
Soit $\mathfrak{A}$ une $(\tau,E)$-algèbre, et $f:X\to A$ une application. Comme $\mathfrak{A}$ est une $\tau$-algèbre, la proposition que j'ai mentionnée plus haut s'applique et j'obtiens un unique morphisme de $\tau$-algèbres $\overline{f} : \mathfrak{T}(X)\to \mathfrak{A}$ tel que $\overline{f}\circ i = f$.
Maintenant soit $(p,q)\in E$ une équation ($p,q$ sont des termes à variables dans $V$: $p,q\in T(V)$ !!).
Soit $h\in T(X)^V$, on a $p^\mathfrak{A}(\overline{f}^V(h) ) = p^\mathfrak{A}\circ \overline{f}^V (h) = \overline{f}\circ p^{\mathfrak{T}(X)} (h)$, et de même avec $q$ (cf. plus haut), et donc, comme $\mathfrak{A}$ satisfait $E$, ces deux expressions sont égales, de sorte que $\{(p^\mathfrak{A}(h),q^\mathfrak{A}(h)), h: V\to A, (p,q) \in E\} \subset \ker (\overline{f})$; et donc par propriété universelle, $\overline{f}$ se factorise de manière unique par $\pi :\mathfrak{T}(X) \to \mathfrak{T}(X)/E^{\mathfrak{T}(X)}$, ce qui donne un morphisme $g: \mathfrak{T}(X)/E^{\mathfrak{T}(X)}\to \mathfrak{A}$ tel que $g\circ (\pi\circ i) = (g\circ \pi)\circ i = \overline{f} \circ i = f$.
On a donc l'existence. Maintenant si $k\circ (\pi\circ i) = f$, alors $(k\circ \pi)\circ i = f$, donc par unicité, $k\circ \pi = \overline{f}$, et donc par unicité $k=g$; d'où l'unicité. Donc c'est bien la $(\tau,E)$-algèbre libre sur $X$.
Finalement, si $X$ n'est pas disjoint de $S$, on trouve une bijection avec un ensemble qui est disjoint de $S$, et on trouve notre $(\tau,E)$-algèbre libre, donc en soi on peut toujours faire "comme si" $X$ était disjoint de $S$.
Grâce à l'exercice que j'ai fourni, on retrouve tous les exemples d'avant: monoïdes, groupes, anneaux, $A$-modules.
Je fais quelques remarques :
1- les constructions de ces objets libres qu'on a données dans l'autre fil ont l'air très différentes. Pourtant, comme on l'a vu, elles sont forcément isomorphes : c'est juste une présentation différente, et en fait on a juste pris avantage de la situation spécifique dans laquelle on était pour simplifier beaucoup ce à quoi ressemblait $T(X)$ modulo les équations. Par exemple dans les monoïdes on a l'équation $(ab)c = a(bc)$ (formellement, sur le type $\{\times, e\}$, elle s'écrit $(\times, (\times ,a,b) , c) \approx (\times, a, (\times, b,c))$ ) qui permet et $ea = a, ae = a$ qui permettent de voir que les termes modulo ces équations sont essentiellement les suites finies d'éléments de $X$. Il y a une grosse tripotée de termes $p\in T(V)$ qui représentent tous l'application $(x_1,...,x_n)\mapsto x_1...x_n$ par exemple, là on en a choisi un.
2- Cette construction est 100% explicite, constructive, tout ce qu'on veut. En particulier, les éléments de l'objet libre sur $X$ c'est essentiellement des "expressions algébriques" avec comme variables les expressions de $X$ modulo les équations qui définissent notre structure algébrique, et tout ce qu'on peut en déduire via les opérations. C'est pour ça que l'anneau commutatif libre sur $\{x,y\}$ par exemple donne les polynômes en $x,y$ : une expression algébrique c'est des sommes de produit de somme de produit de blabla; sauf que grâce aux axiomes d'anneaux (qui se traduisent en équations) on peut voir que toute telle expression algébrique est pareille qu'une certaine somme de $x^iy^j$ ou $-x^iy^j$. Sauf que quand $xy$ apparaît plusieurs fois on peut le voir comme $xy+...+xy = 1\times xy +...+ 1\times xy = (1+...+1)\times xy = n\times xy$ -> polynômes à coefficients entiers.
3- Vu la facilité avec laquelle les propriétés universelles nous aident, on se doute qu'il y a plein de super choses à faire, par exemple déduire le groupe libre du monoïde libre comme on l'avait fait dans l'autre fil. Je vous laisse le soin de voir : a - que se passe-t-il si on rajoute des équations dans $E$; i.e. y a-t-il un rapport (si oui lequel) entre la $(\tau,E)$-algèbre sur $X$ et la $(\tau, E')$-algèbre sur $X$ lorsque $E\subset E'$ ? [exemple : passer de l'anneau libre à l'anneau commutatif libre] b- Que se passe-t-il si on rajoute un symbole de fonction : on passe de $S$ à $S\cup \{t\}$ ? [exemple : passer du monoïde libre au groupe libre; du groupe libre au groupe abélien libre] Des symboles de fonctions ? [exemple : passer du groupe abélien libre au $A$-module libre] Ces questions et leurs réponses permettent de parler du groupe abélien libre sur un groupe, de l'anneau libre sur un groupe additif, de l'anneau libre sur un monoïde multiplicatif, etc.
4- Tout ceci s'inscrit dans le cadre plus général des foncteurs adjoints.
5- Dans des cas plus complexes (on parlait par exemple de la $A$-algèbre libre lorsque $A$ n'est pas commutatif) la structure des termes, même modulo les équations de la définition, est très compliquée, et on n'a vraiment que peu d'intérêt à passer par eux plutôt que par la propriété universelle qui, je le répète, contient toute l'information nécessaire.
6-Interprétation en logique de tout ce bazar : l'algèbre $\mathfrak{T}(X)$ est l'algèbre "absolument libre" : les seules équations valables sont les équations débiles, $p=p$, aucune autre n'y est vraie, c'est l'algèbre de l'égalité pure on pourrait dire. Quand on quotiente par la congruence $E^{\mathfrak{T}(X)}$ on assouplit un peu ceci. Ce qu'on peut prouver, c'est que deux termes $p,q \in T(X)$ seront égaux dans le quotient si et seulement si il y a une preuve qu'ils le sont dans une logique toute petite, où les seules choses qu'on a le droit de faire c'est appliquer des symboles de fonctions, utiliser la transitivité, la réflexivité et la symétrie de l'égalité; et les équations de $E$ (preuve: la relation qu'on obtient ainsi est une congruence et elle contient le truc qui génère $E^{\mathfrak{T}(X)}$, et elle est clairement contenue dans toute congruence qui contient $E$; donc c'est $E^{\mathfrak{T}(X)}$): ainsi l'algèbre libre est vraiment l'algèbre où n'est vrai que ce qui est prouvable. Mais ça on le savait déjà, via le théorème de complétude de Gödel et la propriété universelle.
S'il y a des erreurs, des coquilles, des points pas clairs, ou si vous avez besoin d'explications plus approfondies (ou si vous avez juste des commentaires), n'hésitez pas !
Sur sa demande (et mon conseil) je vais régler le problème une fois pour toutes, pour toutes les structures algébriques (je préciserai ce que j'entends par là). Je le répète car dans ledit fil il y a plusieurs moments où ce n'était pas clair : ce que je présente va être une construction explicite des structures libres dans les cas qui nous intéressent. Il y a au moins 2 autres manières de prouver l'existence des structures libres sur tout ensemble, l'une purement catégorique en utilisant le théorème du foncteur adjoint qui s'applique trivialement dans les situations considérées, et l'autre qui avait été mentionnée par christophe dans un fil dans Fondements et Logique, qui consiste à prendre un produit suffisamment gros. Je pourrais présenter celle-là plus précisément, mais elle est moins explicite et ne correspondra donc pas au voeu de Homo Topi : je ne le ferai que si c'est demandé (en fait c'est la même chose que la preuve catégorique mais on refait la preuve du théorème que je mentionnais à la main, et donc ça paraît moins abstrait). Il y a beaucoup de choses que je ne prouve pas: soit ce sera évident pour vous, soit cela veut dire que je vous laisse le prouver.
Voici donc :
Déjà le cadre. On considère un ensemble $S$ (ensemble de "symboles de fonctions") muni d'une application $a : S\to \N$ ("arité"). Les éléments de $S$ sont à interpréter comme des symboles qui représentent des fonctions (par exemple le symbole $+$, le symbole $\times$), et si $s\in S$, $a(s)$ représente l'arité de ce symbole, par exemple pour le symbole $+$ ce serait $2$, pour $1$ ce serait $0$, etc. : c'est le nombre d'arguments que prendra la fonction. Un tel couple $\tau = (S,a)$ peut s'appeler par exemple un type d'algèbres.
Etant donné $\tau = (S,a)$ un type d'algèbres, une algèbre de type $\tau$ (ou $\tau$-algèbre), $\mathfrak{A}$ est un ensemble $A$ muni de, pour tout $f\in S$, une application $f^\mathfrak{A} : A^{a(f)} \to A$. En particulier, lorsque $a(f) = 0$, il s'agit essentiellement d'un élément de $A$; et lorsque $a(f) = 2$ on retrouve la notion d'opération binaire. Je risque de faire souvent l'abus d'identifier $\mathfrak{A}$ et $A$ et d'écrire $f$ pour $f^\mathfrak{A}$. Je vais essayer d'éviter mais parfois j'oublierai.
Si $\mathfrak{A,B}$ sont deux algèbres de type $\tau$, un morphisme de $\tau$-algèbres est une application $h:A\to B$ telle que pour tout $f\in S$, tous $x_1,...,x_{a(f)} \in A$, on ait $h(f^\mathfrak{A}(x_1,...,x_{a(f)})) = f^\mathfrak{B}(h(x_1),...,h(x_{a(f)}))$: "$h$ est compatible avec les opérations".
Exemples : Si $\tau =( \{\times\}, \times \mapsto 2)$ on retrouve la notion de magma et de morphisme de magma. Si $\mathfrak{A,B}$ s'avèrent être des groupes, c'est un morphisme de groupes. Mais pour les groupes je préfère $\tau = \{\times, e, \iota\}$ où $\times$ est d'arité $2$, $e$ d'arité $0$ et $\iota$ d'arité $1$.
Exercice : Voir que les anneaux, les $A$-modules pour un anneau $A$ fixé, les groupes, les monoïdes sont des cas particuliers de $\tau$-algèbres pour certains types $\tau$.
Si $\mathfrak{A}$ est une $\tau$-algèbre, une sous-$\tau$-algèbre (sous-algèbre si le contexte est clair) de $\mathfrak{A}$ est un sous-ensemble $C\subset A$ qui est stable par toutes les opérations : pour tout $f\in S$, $f^\mathfrak{A}(C^{a(f)})\subset C$. Il est évident qu'une intersection de sous-algèbres est une sous-algèbre, donc on a une notion de sous-algèbre engendrée par un sous-ensemble $X$. Si $C\subset A$ est une sous-algèbre, il existe une unique structure d'algèbre $\mathfrak{C}$ sur $C$ telle que l'inclusion $C\to A$ soit un morphisme $\mathfrak{C\to A}$
Si $\mathfrak{A}$ est une algèbre ($\tau$ est fixé et je ne le mentionne pas quand c'est clair), une congruence sur $\mathfrak{A}$ est une relation d'équivalence $R$ sur $A$ telle que pour tout $f\in S$, $(x_1,y_1),...,(x_{a(f)},y_{a(f)}) \in R$, alors $(f^\mathfrak{A}(x_1,...,x_{a(f)}), f^\mathfrak{A}(y_1,...,y_{a(f)}) )\in R$ : si $x_i$ est relié à $y_i$ pour tout $i$, alors $f^\mathfrak{A}(x_1,...,x_{a(f)})$ est relié à $f^\mathfrak{A}(y_1,...,y_{a(f)})$ : "$R$ est compatible avec les opérations".
Une intersection de congruences est évidemment une congruence, donc on a une notion de congruence engendrée par un sous-ensemble $X\subset A^2$.
Si $R$ est une congruence, $A/R$ a une unique structure d'algèbre $\mathfrak{A}/R$ telle que la projection canonique $\pi : A\to A/R$ soit un morphisme d'algèbres.
Si $h: \mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors $\ker (h) = \{(x,y)\in A^2\mid h(x) = h(y)\}$ est une congruence sur $\mathfrak{A}$. $\ker (\pi) =R$ lorsque $\pi$ est la projection canonique $ \mathfrak{A}\to \mathfrak{A}/R$
exercice : Pourquoi ai-je appelé ça $\ker$ ?
$\pi : \mathfrak{A}\to \mathfrak{A}/R$ a la propriété universelle suivante : si $h:\mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors il se factorise par $\pi : \mathfrak{A}\to \mathfrak{A}/R$ si et seulement si $R\subset \ker (h)$. Elle est facile à prouver si on se souvient de la propriété universelle du quotient d'un ensemble par une relation d'équivalence.
En particulier, si $X\subset A^2$ et si $R$ est la congruence engendrée par $X$, alors $\mathfrak{A}/R$ a la propriété universelle suivante : si $h:\mathfrak{A}\to \mathfrak{B}$ est un morphisme d'algèbres, alors il se factorise par $\pi : \mathfrak{A}\to \mathfrak{A}/R$ si et seulement si $X\subset \ker (h)$. En effet, $\ker (h)$ étant une congruence, $R\subset \ker (h) \iff X\subset \ker (h)$.
On définit maintenant les termes sur un type $\tau = (S,a)$. On fixe un ensemble (typiquement dénombrable quand on fait de la syntaxe, mais ici quelconque) $V$ disjoint de $S$, appelé ensemble de variables. Ses éléments seront typiquement notés $\mathbf{x}$.
On définit alors inductivement un terme : les éléments de $V$ sont des termes; si $t_1,...,t_n$ sont des termes et $f\in S$ vérifie $a(f) = n$, alors $(f,t_1,...,t_n)$ est un terme; on l'écrit généralement $f(t_1,...,t_n)$. Une autre présentation équivalente (que je n'utiliserai pas) sera qu'un terme est un arbre enraciné dont les noeuds et la racine sont étiquetés par des éléments de $S$, les feuilles par des éléments de $V$, et que si un noeud est étiqueté par $f\in S$, alors il a exactement $a(f)$ fils. Je note $T(V)$ l'ensemble des termes avec variables dans $V$.
Une équation est alors un couple $(p,q)$ où $p,q \in T(V)$. Il faut y penser comme l'équation "$p=q$". Souvent, le couple $(p,q)$ est noté $p\approx q$ dans ce contexte.
L'ensemble $T(V)$ est naturellement muni d'une structure de $T$-algèbre, notée $\mathfrak{T}(V)$, définie comme suit : si $f\in S, a(f) = n$, alors $(t_1,...,t_n) \mapsto (f,t_1,...,t_n)$ est bien définie, et c'est ce qu'on note $f^{\mathfrak{T}(V)}$. Le point le plus important est le suivant, il est relativement évident, donc je n'écris pas tous les détails :
Proposition : $(\mathfrak{T}(V),i)$ est la $\tau$-algèbre libre sur $V$; où $i$ est l'inclusion $V\to T(V)$.
Preuve : Soit $\mathfrak{A}$ une $\tau$-algèbre, et $h: V\to A$ une application. On définit inductivement $g:T(V)\to A$ comme suit : $g(\mathbf{x}) = h(\mathbf{x})$ pour $\mathbf{x} \in V$, et $g((f,t_1,...,t_n) ) = f^\mathfrak{A}(g(t_1),...,g(t_n))$ sinon. Il est clair que c'est bien un morphisme d'algèbres, et qu'il vaut $h$ sur $V$. Il est de plus clair que ce morphisme est unique.
Soit $p,q\in T(V)$. On dit que l'équation $(p,q)$ est valide dans $\mathfrak{A}$, aussi noté $\mathfrak{A}\models p\approx q$ si quelle que soit $h:V\to A$, le morphisme induit $g:\mathfrak{T}(V)\to \mathfrak{A}$ vérifie $g(p) = g(q)$.
Une autre manière de le voir est la suivante : si $p$ est un terme, alors il induit une application $p^\mathfrak{A} : A^V\to A$ de la manière suivante : si $h:V\to A$, elle induit $g: \mathfrak{T}(V) \to \mathfrak{A}$, et je peux alors poser $p^\mathfrak{A}(h) = g(p)$.
Alors l'équation $(p,q)$ est valide dans $\mathfrak{A}$ si et seulement si $p^\mathfrak{A} = q^\mathfrak{A}$ .
Exercice : Avec cette notation, si $h: \mathfrak{A\to B}$ est un morphisme d'algèbres, alors $p^\mathfrak{B}\circ h^V = h\circ p^\mathfrak{A}$, où $h^V : A^V\to B^V$ est $f\mapsto h\circ f$ (si $V$ est fini de taille $n$, c'est $h^V(x_1,...,x_n) = (h(x_1),...,h(x_n))$)
Soit $E$ un ensemble d'équations; on a alors une classe d'algèbres intéressantes qui est la classe des algèbres dans lesquelles $(p,q)$ est valide (dans lesquelles $p\approx q$ est valide) pour tout $(p,q)\in E$. On dit que $E$ est valide dans $\mathfrak{A}$ si c'est le cas, ou que $\mathfrak{A}$ satisfait $E$.
Exercice : Trouver un type $\tau$ et un ensemble $E$ d'équations tels que : une $\tau$-algèbre dans laquelle $E$ est valide est un groupe, et un morphisme de telles $\tau$-algèbres est un morphisme de groupes.
Faire de même en remplaçant "groupe" par "monoïde", "anneau", "$A$-module" ($A$ anneau fixé).
Soit $\mathfrak{A}$ une algèbre, $E$ un ensemble d'équations, $R$ la congruence sur $\mathfrak{A}$ engendrée par $\{(p^\mathfrak{A}(h),q^\mathfrak{A}(h)), h: V\to A, (p,q) \in E\}$. Montrer que $\mathfrak{A}/R$ satisfait $E$. Montrer que c'est le plus gros quotient de $\mathfrak{A}$ qui satisfait $E$; en particulier si $A$ satisfait $E$ montrer que la projection canonique $\mathfrak{A}\to \mathfrak{A}/R$ est un isomorphisme. Dans la suite, je noterai $E^\mathfrak{A}$ cette congruence.
Théorème : Soit $\tau=(S,a)$ un type d'algèbres, $E$ un ensemble d'équations sur $\tau$, avec ensemble de variables $V$. On appelle $(\tau,E)$-algèbre une $\tau$-algèbre qui satisfait $E$. Soit $X$ un ensemble disjoint de $S$, $\pi :\mathfrak{T}(X) \to \mathfrak{T}(X)/E^{\mathfrak{T}(X)}$ le morphisme canonique et $i :X\to T(X)$ l'inclusion. Alors $( \mathfrak{T}(X)/E^{\mathfrak{T}(X)}, i)$ est une $(\tau,E)$-algèbre libre sur $X$.
Preuve : Déjà, par ce que j'ai dit avant, c'est bien un $(\tau,E)$-algèbre.
Soit $\mathfrak{A}$ une $(\tau,E)$-algèbre, et $f:X\to A$ une application. Comme $\mathfrak{A}$ est une $\tau$-algèbre, la proposition que j'ai mentionnée plus haut s'applique et j'obtiens un unique morphisme de $\tau$-algèbres $\overline{f} : \mathfrak{T}(X)\to \mathfrak{A}$ tel que $\overline{f}\circ i = f$.
Maintenant soit $(p,q)\in E$ une équation ($p,q$ sont des termes à variables dans $V$: $p,q\in T(V)$ !!).
Soit $h\in T(X)^V$, on a $p^\mathfrak{A}(\overline{f}^V(h) ) = p^\mathfrak{A}\circ \overline{f}^V (h) = \overline{f}\circ p^{\mathfrak{T}(X)} (h)$, et de même avec $q$ (cf. plus haut), et donc, comme $\mathfrak{A}$ satisfait $E$, ces deux expressions sont égales, de sorte que $\{(p^\mathfrak{A}(h),q^\mathfrak{A}(h)), h: V\to A, (p,q) \in E\} \subset \ker (\overline{f})$; et donc par propriété universelle, $\overline{f}$ se factorise de manière unique par $\pi :\mathfrak{T}(X) \to \mathfrak{T}(X)/E^{\mathfrak{T}(X)}$, ce qui donne un morphisme $g: \mathfrak{T}(X)/E^{\mathfrak{T}(X)}\to \mathfrak{A}$ tel que $g\circ (\pi\circ i) = (g\circ \pi)\circ i = \overline{f} \circ i = f$.
On a donc l'existence. Maintenant si $k\circ (\pi\circ i) = f$, alors $(k\circ \pi)\circ i = f$, donc par unicité, $k\circ \pi = \overline{f}$, et donc par unicité $k=g$; d'où l'unicité. Donc c'est bien la $(\tau,E)$-algèbre libre sur $X$.
Finalement, si $X$ n'est pas disjoint de $S$, on trouve une bijection avec un ensemble qui est disjoint de $S$, et on trouve notre $(\tau,E)$-algèbre libre, donc en soi on peut toujours faire "comme si" $X$ était disjoint de $S$.
Grâce à l'exercice que j'ai fourni, on retrouve tous les exemples d'avant: monoïdes, groupes, anneaux, $A$-modules.
Je fais quelques remarques :
1- les constructions de ces objets libres qu'on a données dans l'autre fil ont l'air très différentes. Pourtant, comme on l'a vu, elles sont forcément isomorphes : c'est juste une présentation différente, et en fait on a juste pris avantage de la situation spécifique dans laquelle on était pour simplifier beaucoup ce à quoi ressemblait $T(X)$ modulo les équations. Par exemple dans les monoïdes on a l'équation $(ab)c = a(bc)$ (formellement, sur le type $\{\times, e\}$, elle s'écrit $(\times, (\times ,a,b) , c) \approx (\times, a, (\times, b,c))$ ) qui permet et $ea = a, ae = a$ qui permettent de voir que les termes modulo ces équations sont essentiellement les suites finies d'éléments de $X$. Il y a une grosse tripotée de termes $p\in T(V)$ qui représentent tous l'application $(x_1,...,x_n)\mapsto x_1...x_n$ par exemple, là on en a choisi un.
2- Cette construction est 100% explicite, constructive, tout ce qu'on veut. En particulier, les éléments de l'objet libre sur $X$ c'est essentiellement des "expressions algébriques" avec comme variables les expressions de $X$ modulo les équations qui définissent notre structure algébrique, et tout ce qu'on peut en déduire via les opérations. C'est pour ça que l'anneau commutatif libre sur $\{x,y\}$ par exemple donne les polynômes en $x,y$ : une expression algébrique c'est des sommes de produit de somme de produit de blabla; sauf que grâce aux axiomes d'anneaux (qui se traduisent en équations) on peut voir que toute telle expression algébrique est pareille qu'une certaine somme de $x^iy^j$ ou $-x^iy^j$. Sauf que quand $xy$ apparaît plusieurs fois on peut le voir comme $xy+...+xy = 1\times xy +...+ 1\times xy = (1+...+1)\times xy = n\times xy$ -> polynômes à coefficients entiers.
3- Vu la facilité avec laquelle les propriétés universelles nous aident, on se doute qu'il y a plein de super choses à faire, par exemple déduire le groupe libre du monoïde libre comme on l'avait fait dans l'autre fil. Je vous laisse le soin de voir : a - que se passe-t-il si on rajoute des équations dans $E$; i.e. y a-t-il un rapport (si oui lequel) entre la $(\tau,E)$-algèbre sur $X$ et la $(\tau, E')$-algèbre sur $X$ lorsque $E\subset E'$ ? [exemple : passer de l'anneau libre à l'anneau commutatif libre] b- Que se passe-t-il si on rajoute un symbole de fonction : on passe de $S$ à $S\cup \{t\}$ ? [exemple : passer du monoïde libre au groupe libre; du groupe libre au groupe abélien libre] Des symboles de fonctions ? [exemple : passer du groupe abélien libre au $A$-module libre] Ces questions et leurs réponses permettent de parler du groupe abélien libre sur un groupe, de l'anneau libre sur un groupe additif, de l'anneau libre sur un monoïde multiplicatif, etc.
4- Tout ceci s'inscrit dans le cadre plus général des foncteurs adjoints.
5- Dans des cas plus complexes (on parlait par exemple de la $A$-algèbre libre lorsque $A$ n'est pas commutatif) la structure des termes, même modulo les équations de la définition, est très compliquée, et on n'a vraiment que peu d'intérêt à passer par eux plutôt que par la propriété universelle qui, je le répète, contient toute l'information nécessaire.
6-Interprétation en logique de tout ce bazar : l'algèbre $\mathfrak{T}(X)$ est l'algèbre "absolument libre" : les seules équations valables sont les équations débiles, $p=p$, aucune autre n'y est vraie, c'est l'algèbre de l'égalité pure on pourrait dire. Quand on quotiente par la congruence $E^{\mathfrak{T}(X)}$ on assouplit un peu ceci. Ce qu'on peut prouver, c'est que deux termes $p,q \in T(X)$ seront égaux dans le quotient si et seulement si il y a une preuve qu'ils le sont dans une logique toute petite, où les seules choses qu'on a le droit de faire c'est appliquer des symboles de fonctions, utiliser la transitivité, la réflexivité et la symétrie de l'égalité; et les équations de $E$ (preuve: la relation qu'on obtient ainsi est une congruence et elle contient le truc qui génère $E^{\mathfrak{T}(X)}$, et elle est clairement contenue dans toute congruence qui contient $E$; donc c'est $E^{\mathfrak{T}(X)}$): ainsi l'algèbre libre est vraiment l'algèbre où n'est vrai que ce qui est prouvable. Mais ça on le savait déjà, via le théorème de complétude de Gödel et la propriété universelle.
S'il y a des erreurs, des coquilles, des points pas clairs, ou si vous avez besoin d'explications plus approfondies (ou si vous avez juste des commentaires), n'hésitez pas !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Maxtimax m'avait incité à vérifier qu'un corps libre sur un ensemble donné ne peut pas exister (et la démonstration n'est pas particulièrement difficile) et il m'avait dit que les corps ne sont pas un type d'algèbre au sens défini ici. Le fait que les corps ne sont pas un type d'algèbre n'implique pas directement qu'un corps libre ne peut pas exister... du moins, pas avec seulement les résultats que Maxtimax a exposés ici, qui nous disent seulement qu'on ne peut pas compter eux pour démontrer qu'un corps libre existerait.
Je propose ma version pour voir que les corps ne sont pas un type d'algèbre. Il nous faut :
- un symbole d'addition $+$, d'arité $2$
- un symbole de neutre additif $e_+$, d'arité $0$
- un symbole d'inversion additive $-$, d'arité $1$
- un symbole de multiplication $\times$, d'arité 2
- un symbole de neutre multiplicatif $e_\times$, d'arité $0$
- un symbole d'inversion multiplicative $/$, d'arité. $1$.
(je ne note pas $0$ et $1$ les neutres pour qu'on ne s'embrouille pas entre les symboles et leur arité, enfin bref)
Jusque-là, tout va bien. J'embarque $S = \{+, e_+,-, \times, e_\times, / \}$ dans le paragraphe suivant. Soit donc $A$ un ensemble muni de la structure $S$.
Là où ça va planter, c'est qu'il faut que je puisse associer à $/$ une application $f : A^1 \longrightarrow A$ (donc définie en tout élément de $A^1=A$), qui correspond évidemment à l'application d'inversion multiplicative, et on sait ce que ça donne quand on suppose que $e_+$ est inversible pour la multiplication...
EDIT : Dans ce que je raconte, rien dans ma structure n'impose à ma loi additive d'être commutative... Je suis allé vite dans ma rédaction, mais je reste convaincu que mon argument marchera quand même.
Simplement, il n'y a pas d'ensemble d'équations $E$ tel que "être un corps" est équivalent à "être un $(\tau,E)$-algèbre", c'est ça que j'entendais quand je disais que "corps" ce n'est pas "algébrique"
Les corps sont des anneaux particuliers, donc rangeons-les dans le type d'algèbre "anneau" pour commencer.
On pourrait soit essayer de les mettre dans un type d'algèbre à part, le type "corps", mais je pense quand même que ce que j'ai dit nous empêche de faire ça, non ?
Sinon, on peut essayer de les définir comme des anneaux qui vérifient un certain ensemble d'équations, mais là je ne vois pas comment tu démontres que c'est impossible.
Justement, on peut prouver qu'il n'y a pas d'ensemble d'équations $E$ tel que "un anneau vérifie $E$ si et seulement si c'est un corps"
Si c'est intéressant, peut-être que tu pourrais au moins donner des indices sur la démonstration de ce que tu viens de dire.
Je n'ai pas défini le produit d'algèbres, mais la définition est relativement évidente : on prend comme ensemble sous-jacent le produit des ensembles sous-jacents, et comme opérations les opérations coordonnée par coordonnée.
C'est assez facile de prouver ce résultat, et encore plus facile de voir que si on prend pour $K$ la classe des corps, alors il y en a $2$ sur les $3$ qui ne fonctionnent pas (si $\tau$ est le type des anneaux, qu'est-ce qu'un sous-algèbre ? qu'est-ce que le produit ? ).
Le point intéressant du théorème de Birkhoff est la réciproque de ce que je viens d'annoncer (qui n'est pas si compliqué une fois qu'on a compris ce qui se passe précisément avec les algèbres libres)
Il y a bien, d'un certain point de vue, un "corps libre" au-dessus de n'importe quel anneau commutatif $A$. Bon, ce corps libre est en fait un espace annelé en corps : l'espace est le spectre premier de $A$, avec sa topologie constructible (une base d'ouverts est formée des combinaisons booléennes des $D_a=\{\mathfrak p\in \mathrm{Spec}(A)\mid a\not\in \mathfrak p\}$ pour $a\in A$) ; la fibre en $\mathfrak p$ est le corps de fractions $k(\mathfrak p)$ de $A/\mathfrak p$.
On voit facilement que tout morphisme $f:A\to K$ dans un corps factorise à travers $A\to k(\mathfrak p)$ pour un unique $\mathfrak p$, à savoir $ \mathfrak p=\ker(f)$. Mais la propriété universelle du "corps libre" se se formule de manière plus large, en faisant intervenir la catégorie des espaces annelés en corps.
L'anneau des sections globales du "corps libre" au-dessus de $A$ est l'anneau von Neumann-régulier commutatif libre sur $A$. Un anneau commutatif $R$ est dit von Neumann-régulier quand
$$\forall a\in R\ \exists b\in R\quad (a^2b=a \text{ et } b^2a=b)\;.$$La théorie des anneaux commutatifs von Neumann-réguliers n'est pas équationnelle dans le langage des anneaux, mais ça n'empêche pas le foncteur d'oubli de la catégorie des anneaux commutatifs von Neumann-réguliers dans la catégorie des anneaux commutatifs de bien avoir un adjoint à gauche.
Merci pour ce super message.
Une question par rapport à ce que tu as écrit: le premier exercice que tu nous proposes est de décrire les groupes (et d'autres choses) comme des $\tau$-algèbres pour un certain $\tau$.
Mais il me semble que l'associativité s'exprime comme une équation (de même la notion d'élément neutre et d'inverse) et qu'un groupe est plutôt une $(\tau,E)$-algèbre non ? avec $\tau = \{x,1,i\}$ et $E= \{a(bc)=(ab)c, 1a=a1, ai(a)=1=i(a)a\}$.
Je me souviens de propriétés comme "pour vérifier qu'une fonction est un morphisme de groupes, il suffit de vérifier que le produit est préservé". On trouve la même chose pour les algèbres de Boole : la loi envoyant un élément sur son complémentaire est automatiquement préservée (par unicité du complémentaire). Ou encore, dans les corps, l'inverse est préservé (toujours "par unicité"). Y a-t il un cadre intéressant dans lequel ça s'inscrit ? (Sait-on jamais.)
Par exemple, la chose suivante est-elle vraie ? Pour simplifier, on pense à un symbole comme muni de son arité. On suppose que notre ensemble de symboles s'écrit comme une union disjointe $A \uplus B$. Supposons que $X$ soit une $(A \uplus B, E)$-structure qui ait la propriété d'être le seul "prolongement" de la $A$-structure sous-jacente. Est-il vrai que pour toute $(A \uplus B, E)$-structure $Y$, une fonction $Y \to X$ est un $(A \uplus $-morphisme dès que c'est un $A$-morphisme ? Si non, on peut se demander si c'est vrai lorsqu'on suppose que toute $(A \uplus B, E)$-structure ait la propriété requise pour $X$. Si c'est encore non, c'est au moins vrai si pour toute $(A \uplus B, E)$-structure $X$, chaque graphe d'une fonction dans $B$ se décrit de manière algébrique grâce aux fonctions dans $A$ (comme égaliseur de deux morphismes $X^n \to X^m$, où "morphisme" veut dire construit grâce aux fonctions de $A$). Il se peut que ce graphe ne soit que le graphe d'une fonction partielle, comme le cas des corps pour l'inversion.
@Champ-Pot-Lion : très bonne question; je n'ai jamais vu de trucs à ce sujet (mais je n'ai pas tout vu donc ça existe très possiblement)
Dans les groupes et les algèbres de Boole, ce qu'il y a de remarquable je pense c'est aussi qu'on ait un "inverse" , c'est-à-dire que partant de quelqu'un au hasard on peut retomber sur le neutre (enfin l'un des neutres).
Pour ton énoncé plus précis, je ne sais pas, ça m'a l'air faux. La "preuve évidente" en tout cas ne marche pas immédiatement.
Si le morphisme est injectif, elle marche cependant (pour "toute structure a au plus une extension").
Il y a peut-être un théorème de logique qui dit que s'il y a toujours au plus une extension, alors c'est que les symboles de $B$ sont définissables. Dans ce cas, selon la complexité des formules, c'est plus ou moins clair (c'est ce qui se passe pour les groupes et les algèbres de Boole)
PS: ce que tu as appelé morphisme entre guillemets s'appelle souvent polynôme ou fonction polynômiale
Je lirai tout ce fil de discussion en détail plus tard, en ce moment je n'ai pas énormément de temps et je ne pensais pas que l'exposé de Maxtimax serait aussi long et détaillé :-D
Le formalisme que Maxtimax a imposé, c'est qu'un type d'algèbre, c'est un couple $(S,a)$ ou $a$ est notre application arité, qui s'applique aux éléments de $S$, qu'il a appelé des "symboles de fonctions". Et ensuite, une algèbre de ce type, c'est un ensemble muni d'une application associée à chacun des "symboles de fonctions", dont le nombre de variables est égal à l'arité du symbole.
Mais si je prends une structure algébrique, par exemple les groupes. On sait qu'un groupe c'est un ensemble muni d'un produit et d'une inversion, et le symbole par lequel on représente ces applications, en vrai on s'en fiche. On se donne un symbole parce que c'est plus simple d'écrire $(x \star y) \star z = x \star (y \star z)$ que $f(f(x,y),z) = f(x,f(y,z))$.
Là où je veux en venir, c'est que ça me paraîtrait plus naturel de définir le type "groupe" comme étant un ensemble, muni de deux applications, d'arité respectives $2$ et $1$, vérifiant telles équations. Ça me paraît extrêmement artificiel de définir un type par des symboles, parce que je me dis que si je définis $S = \{\star, \diamond \}$ et $S' = \{ \star ' , \diamond '\}$ avec les mêmes arités respectives, j'aurai deux types d'algèbres différents (puisque les symboles sont différents) alors qu'ils pourraient décrire la même structure.
Je pense qu'en me faisant cette réflexion, je viens de me justifier à moi-même que le point de vue "une 'bonne' structure algébrique, c'est un ensemble dont le comportement peut être décrit par des équations" est très naturel en soi. Ce qui donne au fameux théorème de Birkhoff toute son importance, pour montrer qu'un truc artificiel mais très simple peut suffire à décrire un truc qui ne se comprenait autrement que par des équations.
Mais voilà, la question reste quand même, pourquoi on utilise la définition que je trouve artificielle, avec des symboles, plutôt qu'une définition de type d'algèbre en passant par les applications elles-mêmes.
Il faut tout de même donner un nom aux symboles de fonctions, pour ne pas les mélanger. Prends par exemple les treillis distributifs. Il y a deux fonctions d'arité 2 (l'inf et le sup), et les équations ne permettent pas de distinguer entre ces deux opérations, si on ne les nomme pas ! On serait bien embêté pour définir les morphismes, si on ne sait pas qui est l'inf et qui est le sup !
Le truc c'est que tu ne peux pas dire "un groupe c'est un ensemble avec une opération d'arité $2$, une d'arité $1$ et une d'arité $0$"; parce que si tu généralises, disons aux anneau, tu te retrouves avec deux opérations d'arité $2$, et donc pour décrire les équations, et les morphismes il te faut donner des noms à ces opérations, sinon tu ne peux pas t'y retrouver. Leur donner des noms (addition, multiplication par exemple) c'est pareil que fixer un symbole qui la décria : c'est ce rôle que jouent les éléments de $S$.
Alors effectivement, si tu prends $(S,a), (S',a')$ tels qu'il y a une bijection $f:S\to S'$ qui préserve l'arité ($a=a'\circ f$) tu obtiens des trucs isomorphes, donc le choix de $S$ peut paraître arbitraire. Mais même le choix de dire "une opération d'arité $2$, une d'arité $1$ et une d'arité $0$" est arbitraire : tu peux décrire les groupes avec une seule opération binaire, et une seule équation, et tu obtiens des catégories (concrètement) isomorphes !
Le seul moyen de s'en sortir et d'obtenir un truc non biaisé (non arbitraire) c'est de regarder ce qu'on appelle le clone des algèbres, et qui est en soi contenu dans la notion de termes modulo les opérations : le clone d'une algèbre $\mathfrak{A}$ c'est l'ensemble "gradué" des fonctions polynomiales sur $A$. Là si tu as de tels $S,S'$ ou même si on a une situation plus tordue comme celle que j'ai decrite avec les groupes, tu auras le même clone en considérant $A$ comme $S$-algèbre ou $S'$-algèbre.
Ça se réduit à deux questions, selon ce que tu préfères entre syntaxe et sémantique : interdéfinissabilité des types, ou isomorphisme (concret) de catégories.
Pour résumer :oui c'est arbitraire, et on a des moyens de pallier à ça; mais il y a une raison de mettre un $S$ : pouvoir nommer les opérations et les distinguer et donc donner un sens aux équations/morphismes. (Si tu préfères, puisque $(S,a)$ c'est essentiellement un objet de $\mathbf{Set}/\N$, et que ça c'est équivalent à $\mathbf{Set}^\N$, se donner $(S,a)$ c'est pareil que se donner une famille $(C_n)_n$, où $C_n$ est l'ensemble des symboles d'arité $n$
EDIT : grillé par GBZM. D'ailleurs, pour lui répondre, on peut se passer du neutre en rajoutant les axiomes $xx^{-1}= yy^{-1}$ et en utilisant $xx^{-1}$ comme neutre
Un monoïde, c'est un ensemble muni d'une loi associative qui admet un élément neutre.
Donc si on se donne le type $\{\times, e\}$ où $\times$ est notre loi de composition interne, d'arité $2$, et $e$ est notre élément neutre, d'arité $0$, on y est presque mais on n'a pas décrit l'associativité. J'ai donc décrit le type d'algèbre "magma unitaire" pour l'instant.
Je suppose donc qu'on va prendre le type $\{\times, e\}$ et le quotienter par la congruence qui décrit l'associativité, mais je ne comprends pas en quoi, en faisant ça, on décrit un nouveau type. Avec ce que Maxtimax a dit, les monoïdes sont des sous-"magma unitaire"s mais c'est tout, je crois ?
Je peux continuer avec ça... admettons que les monoïdes et même les groupes soient descriptibles comme des types d'algèbre. Pour parler de groupes abéliens, je vais encore devoir quotienter par la congruence qui décrit la commutativité, mais dans ce cas j'aurai juste dit que les groupes abéliens sont des sous-"groupe"s, mais rien ne me dit comment les décrire comme un nouveau type.
Et j'ai besoin de pouvoir décrire les groupes abéliens comme un type à part (chose que j'avais zappée lors de me tentative d'expliquer pourquoi les corps ne sont pas un type à part) pour pouvoir montrer que les anneaux sont aussi un type d'algèbre.
En plus, même si j'arrive à montrer tout ça, quand j'essaierai avec les modules, je serai un peu perdu parce que je ne vois pas trop comment décrire la "loi externe" avec ce formalisme. Maxtimax m'avait dit en message privé de considérer que ça n'existe pas, mais alors, il faudra rajouter dans mon ensemble de symboles littéralement tous les éléments de l'anneau sur lequel on considère les modules, c'est ça ? Un truc du genre $S = \{\text{symboles de fonctions}\} \cup A$ ?
Bref, c'est compliqué tout ça, je trouve.
C'est le même genre de choses pour groupes ,anneaux etc.
Et oui tu as raison pour les modules, on peut rajouter les éléments de $A$ comme symboles (en faisant en sorte qu'ils soient distincts des symboles pour $+,\times, 0, 1, -$). Il y a un autre formalisme plus général que ce que j'ai développé ici qui permet de gérer plusieurs "sortes", et donc pour les modules on pourrait faire une "sorte" qui serait les scalaires, et un autre les vecteurs, mais bon ici je ne l'ai pas fait donc tu "dois" mettre une opération par élément de l'anneau
Les monoïdes vont être des $\{\text{produit, neutre}\}$.
Les groupes vont être des $\{\text{produit, neutre, inversion}\}$.
Les anneaux unitaires vont être des $\{\text{addition, zéro, opposé, multiplication, unité}\}$.
Les $A$-modules vont être des $\{\text{addition, zéro, opposé}\} \cup A$.
Et pour rajouter l'associativité, la commutativité, la distributivité et autres, ça sera des congruences à chaque fois, j'imagine.
On a donc un morphisme de $\tau$-algèbres $h : A \longrightarrow B$. On définit $R = \{(x,y) \in A^2 \mid h(x)=h(y)\}$ et on va admettre que c'est bien une congruence.
Si c'est bel et bien le cas, comme une congruence est en particulier une relation d'équivalence, on peut appliquer le théorème de factorisation : en notant $\pi : A \longrightarrow A/R$ la surjection canonique, il existe une unique application $\overline{h} : A/R \longrightarrow B$ telle que $h = \overline{h} \circ \pi$.
De plus, toujours d'après le même théorème, $\overline{h}$ est injective si, et seulement si : $(x,y) \in R \Longleftrightarrow h(x) = h(y)$, est c'est précisément le cas puisqu'on a défini $R$ comme ça.
Maintenant, admettons de plus que $A/R$ possède effectivement une structure de $\tau$-algèbre, plus précisément admettons qu'il existe effectivement une unique structure de $\tau$-algèbre sur $A/R$ qui fait de $\pi$ un morphisme de $\tau$-algèbres. Alors admettons que $\overline{h}$ est en fait lui aussi un morphisme $\tau$-algèbres.
Admettons que, comme tout ce qu'on a l'habitude d'appeler un morphisme de structures algébriques, un morphisme de $\tau$-algèbres est injectif, si, et seulement si, son noyau est réduit à l'élément neutre. Sauf que l'élément neutre de $A/R$, par construction, c'est la classe des éléments de $R$, ce qui veut dire : $\ker(\overline{h}) = R$. Le fait d'appeler $R$ le noyau de $h$ n'est qu'un abus de notation.
Que pourrait vouloir dire "élément neutre" pour des algèbres générales ? Et qu'est-ce que c'est que "la classe des éléments de $R$"? Et, en algèbre linéaire par exemple, les applications non injectives n'ont pas le droit à un noyau ?
Le noyau de $f$ qui est une congruence sur $G$ est $\{(x,y) \in G^2 \mid f(x) = f(y)\}$. Dans le cas des groupes, je peux réécrire $f(x) = f(y)$ sous la forme $f(xy^{-1})=e'$. Donc ma congruence s'écrit $\{(x,y) \in G^2 \mid f(xy^{-1})=e' \}$.
Maintenant, une partie $S$ de $G$ est un sous-groupe de $G$ si, et seulement si, $S$ est stable par l'application $\varphi : G^2 \longrightarrow G$, $(x,y) \longmapsto xy^{-1}$. Donc je réécris ma congruence sous la forme $\{(x,y) \in G^2 \mid f \circ \varphi(x,y)=e' \}$. Donc c'est le noyau "au sens classique" du morphisme $f \circ \varphi$ ?
Et là encore, quand ce n'est pas un groupe, tout ce que je dis ne marche pas. J'ai du mal à voir à quoi tu veux en venir, où l'on va avec tout ça.
Inversement, $\ker(f)$ devient la classe de $e$ modulo $R$ !
Le point important est : $\ker(f)$ (la congruence) est la relation de congruence modulo $\ker(f)$ (le sous-groupe); donc quand tu quotientes par le sous-groupe $\ker(f)$, en réalité tu quotientes par la relation d'équivalence $\ker(f)$, d'où le nom.
Donc on peut retrouver $\ker(f)$ à partir de $R$, et inversement. Il en est évidemment de même pour les modules et les anneaux par exemples; ça s'inscrit dans la correspondance congruence $\leftrightarrow$ sous-groupe normal (resp. sous-module, idéal bilatère)
Du coup, ça permet aussi de savoir, étant donné une structure à laquelle on n'est pas habitué (demigroupe ou je ne sais quoi), de trouver le type de sous-ensemble qui permet d'avoir une structure sur le quotient : les sous-groupes distingués pour les groupes, les idéaux pour les anneaux, etc
On a donc un morphisme de $\tau$-algèbres $h : A \longrightarrow B$.
On note $R = \{(x,y) \in A^2 \mid h(x) = h(y) \}$. C'est une relation d'équivalence, et même une congruence.
Le noyau de $h$ "au sens usuel" est $\ker(h) = \{x \in A \mid h(x) = e'\}$.
Maintenant, quand on est "au moins" dans un groupe, on peut écrire $R = \{(x,y) \in A^2 \mid h(xy^{-1}) = e' \}$, c'est-à-dire $R = \{(x,y) \in A^2 \mid xy^{-1} \in \ker(h) \}$. Donc effectivement, quand on est "au moins" dans un groupe, $R$ est la congruence modulo $\ker(h)$.
Ça peut marcher pour les structures qui sont plus riches que les groupes, comme les anneaux et les modules.
Mais dans un monoïde, on ne peut pas appliquer la même logique... dans le cas des monoïdes, il n'y a aucun rapport entre $R$ et $\ker(h)$ ?
(Enfin, on peut toujours écrire que $\{(x,e) \in A^2 \mid x \in \ker(h)\} \subset R$, $\{(e,x) \in A^2 \mid x \in \ker(h)\} \subset R$ et même $(\ker(h))^2 \subset R$, mais bon)
Prenons un exemple dans les monoïdes. Pour se simplifier la vie (question de "distingué") on va prendre des monoïdes commutatifs. Dans ce cas si $N$ est un sous-monoïde de $M$, l'analogue naturel de la congruence modulo $N$ va être $x\sim y\iff x+N=y+N$ (à moins que tu aies mieux). On verifie facilement que c'est une congruence, et donc on peut donner un sens à "quotienter par $N$".
Seulement voilà, contrairement aux groupes où toutes les congruences s'obtiennent ainsi, dans les monoïdes ce n'est pas le cas ! Par exemple sur $\N$ prenons la congruence qui a $3$ classes : $\{0\}, \{1\}$ et le reste. Vérifie que c'est bien une congruence. Supposons qu'il y ait un sous-monoïde $M$ qui l'induise. Alors $2+M = 3+M$, donc $1+M = 2+M$ car $\N$ est "cancellable" ($x+y = x+z\implies y=z$); donc $1\sim 2$ : absurde.
Je retiens aussi ce que tu viens de dire, que dès qu'on a une structure "au moins" de groupe, toutes les congruences sont associées à un sous-groupe (et similaire dans les anneaux, modules etc avec le sous-machin correspondant)
C'est très proche de ce que Maxtimax a proposé. Mais j'y vois quelques détails qui changent : ils définissent l'algèbre des termes comme le plus petit ensemble tel que [conditions]. Il faut aussi démontrer que ça existe. Je préfère ça à la définition inductive de Maxtimax, mais ça va être un petit peu plus compliqué, je pense.
La preuve de l'existence n'est pas compliquée : tu prends un ensemble assez gros pour être sûr qu'il contient tout ce qu'il faut, et tu prends ensuite l'intersection de ceux qui satisfont les conditions.
Monoïdes : on définit le type $\tau$ à partir de $S = \{\times, e\}$ comme on avait dit ($\times$ est binaire, $e$ est nullaire). Les équations qu'on va utiliser sont :
- associativité : $(x \times (y \times z);(x \times y) \times z)$
- neutre : $(x \times e;x)$ et $(e \times x;x)$
- si on veut la commutativité : $(x \times y; y \times x)$
Groupes : on "enrichit" $S$ en ajoutant $i$ qui est unaire, et on ajoute les équations :
- $(x \times i(x);e)$
- $(i(x) \times x;e)$
Bon, je vais m'arrêter là pour l'instant, je suis assez confiant que c'est juste (mais on n'est pas à l'abri d'une erreur).
En parlant d'erreurs, je m'embrouille un peu sur certains trucs, peut-être as tu fait des erreurs en rédigeant le premier message.
Avant la Proposition, je pense que tu veux dire que $T(V)$ est muni d'une structure de $\tau$-algèbre. Entre les deux exercices après la Proposition, je pense que tu veux dire $(p,q) \in T(V)^2$.
J'ai encore du travail à faire pour comprendre les histoires de termes, d'équations et d'ensembles vérifiant ces équations. Je vais être assez pris dans les prochains temps, donc je ne sais pas si je passerai beaucoup de temps dessus. Ce qui n'empêche personne d'écrire quelque chose ici, la beauté des forums internet c'est que les messages ne disparaissent pas et qu'on peut encore les lire longtemps après qu'ils ont été postés :-D
J'ai quelques questions, puisque Maxtimax et GaBuZoMeu ont tous les deux parlé de ça :
Dans l'intégralité de l'autre fil, on parlait de structures libres sur $X$, on n'avait pas de structure algébrique sur $X$. Et dans le premier message de Maxtimax ici, il ne définit rien de plus que ça : les structures libres sur un ensemble $X$ qui n'a pas lui-même de structure algébrique (ou, s'il en a une, on s'en fiche). Sauf qu'après, Maxtimax a parlé de diverses constructions possibles, comme le "groupe abélien libre sur un groupe". Je suppose que dans cet exemple précis, c'est l'ensemble qui va contenir les trucs de la forme $xy^{-1}z^2 + x^{-3}yz$ et autres termes de ce style-là... ça ressemble à des espèces de fractions rationnelles formelles à plusieurs variables : je viens d'écrire $\displaystyle \frac{XZ^2}{Y} + \frac{YZ}{X^3}$. C'est ça ?
(GBZM : tu as fait l'effort de mentionner "l'espace annelé en corps sur un anneau commutatif", mais c'est encore un peu trop compliqué pour moi. C'est de la géométrie algébrique, ça fait intervenir des histoires de faisceaux, donc de catégories, et dans les définitions que j'ai vues, espace signifie espace topologique, donc il y a de la topologie en plus... restons dans les choses simples pour l'instant)
Puisque vous avez tous les deux parlé de foncteur adjoint, j'ai cherché un petit peu : le foncteur qui nous intéresse, ici, c'est le foncteur d'oubli qui va la catégorie des $(\tau,E)$-algèbres vers celle des ensembles. On a un "foncteur objet libre", qui associe à un ensemble $X$ la $(\tau,E)$-algèbre libre libre sur $X$, qui est l'adjoint (à gauche, apparemment) du foncteur d'oubli. Donc les histoires de groupe abélien libre sur un groupe, en gros, c'est : on a un foncteur d'oubli de la catégorie des groupes abéliens vers la catégorie des groupes (donc, il a meilleure mémoire que le premier foncteur d'oubli), et il a lui aussi un adjoint à gauche qui va associer à un groupe le groupe abélien libre dessus. C'est ça ?
Je vais m'aventurer en terrain encore assez méconnu, alors soyez indulgents, mais... la recherche des objets libres, ça pourrait se résume à chercher deux catégories $C$ et $D$, telles qu'il existe un foncteur d'oubli de $C$ dans $D$ qui admet un adjoint à gauche, auquel cas l'image d'un objet $x$ de $D$ par ce foncteur adjoint est l'objet de $C$ libre sur $x$, non ? Si ça existe, ça donnerait un sens à des objets libres qui ne sont pas de nature algébrique. Du coup, ça me fait poser la question suivante : je sais qu'il y a une catégorie des espaces topologiques, et je ne vois pas pourquoi elle n'aurait pas son foncteur d'oubli vers la catégorie des ensembles. Est-ce que ce foncteur d'oubli admet un adjoint à gauche, qui donnerait sens à un espace topologique libre sur machin, ou bien le fait qu'il existe un adjoint à gauche pour un foncteur d'oubli caractérise les "catégories algébriques" ?
-Non, le groupe abélien libre sur le groupe $G$ c'est son abélianisé $G^{ab}$, en tout cas si tu définis "libre" comme "adjoint à gauche" (ce que tu fais plus bas, et qui me semble tout à fait raisonnable)
-Oui, c'est ça. Comme tu le dis (un peu maladroitement en parlant de "chercher" et d'existence) plus bas, si tu as un foncteur qu'on s'amuse considérer comme "d'oubli $U:C\to D$", on peut considérer les objets de $C$ comme des objets de $D$ "munis d'une structure", et alors trouver un adjoint à gauche de $U$ c'est trouver, pour tout objet $d$ de $D$, le $C$-objet libre dessus.
-Cela donne du sens à des objets libres dans des catégories non algébriques. L'espace topologique libre sur un ensemble $X$ en ce sens, c'est l'espace topologique $X$ muni de la topologie discrète (le "co-libre" c'est la topologie grossière). L'espace compact Hausdorff libre sur $X$, c'est l'espace des ultrafiltres sur $X$, $\beta X$. Etc, etc. ("catégorie algébrique" est très difficile à caractériser, plus difficile que "l'oubli a un adjoint à gauche")
C'est très intéressant, tout ça. Ça me donne envie de plonger plus en détail dans la théorie des catégories, en tout cas. J'ai trouvé le livre "Categories For The Working Mathematician" de Saunders Mac Lane en PDF, il attend que j'aie le temps de le lire...
Ou c’est moi ou il y a un problème de ponctuation ou des signes qui manquent
Édit: lol pardon $f^\mathfrak{A}$ c’est le nom de ton application .... je lisais ça comme application de $\mathfrak{A}$ dans f...
Continue à lire, on a répondu à la question ici-même