Discussion:Monoïde

Un monoïde et un magma ne sont pas la même chose, un monoïde est une sorte de magma, mais l'inverse est faux.

Guillaumito 18 mar 2004 à 12:10 (CET)

La phrase d'origine est en effet ambigue : "Un monoïde est un magma, i.e. un ensemble muni d'une loi de composition interne associative avec élément neutre.". Je propose de la remplacer par "Un monoide est un magma (i.e. un ensemble muni d'une loi de composition interne) associatif avec un element neutre."

Mononoke Hime 18 mar 2004 à 12:36 (CET)

Ouais, mais ça risque de devenir chargé au bout d'un moment : un monoide est un magma avec telles propriétés c'est aussi un semigroupe avec telle propriété, etc. Encore pour une structure comme le monoïde, ça peut aller mais pour des structures plus complexes... Je propose de définir à partir de la structure "la plus proche", ie : monoide est plus proche de semigroupe que de magma.

Monoïde libre

Bonjour,

Ne trouvant pas spontanément d'exemple de monoïde non libre, je souhaiterais bénéficier de quelques suggestions. Ces dernières pourraient également figurer dans l'article. Merci par avance.

Cordialement --nha de Lyon. 6 juillet 2006 à 01:44 (CEST)

En complément à ma question précédente, et par rapport aux exemples mentionnés actuellement dans l'article, je rechercherais un exemple de monoïde libre dont la structure diffère d'un alphabet fini muni de l'opérateur de concaténation. Un tel exemple existe-t-il en l'occurrence ? Merci pour les idées.

--nha de Lyon. 6 juillet 2006 à 01:53 (CEST)

En fait, si je ne m'abuse, l'appellation de monoïde libre est réservée à un certain type de monoïdes d'alphabet A et

munis d'une opération de concaténation, qui met bout à bout des éléments de l'ensemble A. Ainsi libre revient à dire

monoïde "bête" ou "simple", dans le sens ou l'opération de concaténation donne un sens unique au mot.

Donc, si on a:

$a_{1}.\,...\,.a_{n}=b_{1}.\,...\,b_{i}\,$ pour tout entier $i,\,1\leq i\leq n\,$

alors $n=i\,$ et $a_{n}=b_{i}\,$

A vérifier

Feeder Fan 6 juillet 2006 à 14:39 (CEST)

Bonjour,

Feeder Fan, merci pour votre réponse. Il est clair qu'en informatique - et plus précisément en théorie des langages (quoique cette matière soit commune avec la linguistique formelle par exemple) - on associe de manière quasi automatique un monoïde à tout support de langage concret. En tant que tel, un monoïde libre ne définit pas de langage formel (cardinalité "trop grande") mais peut en engendrer plusieurs.

Néanmoins, j'adhère à votre réponse : un monoïde "classique" (ou bête ou simple) est libre. De fait, vous me permettez de considérer que, par définition, un monoïde libre est effectivement assimilable à toute structure établie sur un alphabet fini et munie d'un opérateur de concaténation (lapalissade de ma part !). Il resterait à exhiber un exemple (au moins) de monoïde non libre pour répondre à la 1ère question. Si vous avez une idée... ;-)

Une petite remarque par rapport au "sens unique" que vous indiquez pour un mot formé par concaténation : quoique sur le plan syntaxique votre propos est rigoureux, sur le plan sémantique (la facette cachée mais concrète des langages ;-) ) on observe de nombreux exemples de mots (concaténation de lettres) au sens proche ou identique (ou commun).

Cordialement, --nha de Lyon. 22 juillet 2006 à 00:34 (CEST)

Re,

nha si je comprends bien, vous voudriez un exemple de monoïde non libre. N'étant pas mathématicien, je n'ai pas la réponse, mais cependant, nous pouvons y réfléchir.

Prenons un monoïde d'éléments a, b et c muni d'une opération de concatenation (qui aurait la posibilité dans certains cas de reformuler un motif en un autre) et du mot vide comme élément neutre.

Alors, si cette règle remplace toute suite xx (où x est un élément de l'alphabet) en x (suppression des répétitions).

Alors on aurait: bbbbbaaacc = bbacccc = baaac = bac

La réponse n'est pas vraiment un exemple à proprement parler. Je pose donc la question, si on remplace l'operateur d'un monoïde par une fonction surjective, a-t-on un monoïde non lilbre ? Feeder Fan 28 juillet 2006 à 21:28 (CEST)

Pour nha de Lyon., vous voulez des exemples de monoïdes non libres ? C'est trés simple : considérez n'importe quel groupe ! Par ailleurs je trouve que la section sur les monoïde libre n'est que partiellement juste : l'alphabet peut tout à fait être infini. Cet erreur est sans doute due au fait que les monoïdes libre sont trop facilement considérés comme des ensembles de mots au sens où on l'entend naïvement (suite de lettre munis d'une concaténation), ce qui n'est qu'une vision particulière de la notion. Je pense réécrire qqch. --Burakumin (d) 18 février 2009 à 14:43 (CET)

Bonjour, Un monoide qui n'est pas libre ? Et bien par exemple le produit de deux monoides libre n'est pas libre.

(...)

Bon je vois que la notion de monoïde libre a déjà suscité des interrogations. Et que la discussion semble dire que que monoïde libre est confondu avec mot d'un dictionnaire, avec un alphabet et l'opératon de concaténation. Je viens ajouter une demande de source car la définition actuelle me semble excessivement restrictive puisque l'existence de deux éléments commutant empêcherait le monoïde d'être libre puisqu'on aurait a*b = b*a sans avoir a=b

J'ai également supprimé la modification d'aujourd'hui qui ne résolvait pas pour autant le problème de source mais aussi explicitait de manière très imparfaite l'unicité

• la relation entre les (a_i) et x n'était pas explicitée
• ni la relation entre n et m

HB (discuter) 19 août 2024 à 17:59 (CEST)

La page anglaise en:Free monoid appelle monoïde libre un objet libre dans la catégorie des monoïdes, et dit que c'est la même chose qu'un isomorphe à A* pour un certain ensemble A. L'article présente aussi une autre caractérisation, le fait qu'un monoïde est libre ssi il est gradué et équidivisible, et il paraît relativement bien sourcé (je n'ai pas vérifié que les sources disaient effectivement ce qu'il y a marqué sur la page). La définition avec une base qui est une partie génératrice et libre qu'on a dans monoïde n'a pas l'air fausse pour autant, j'ai l'impression qu'on peut montrer que E est isomorphe à P*, mais elle n'est pas sourcée. Je n'ai pas actuellement accès en ligne aux livres de M. Lothaire qui sont cités sur la page anglaise pour vérifier ce que dit chaque page, sinon j'aurai corrigé moi-même.

Ta remarque sur les deux éléments qui commutent n'est pas tout à fait correcte : si a et b ne sont pas le mot vide, il existe un mot c et deux entiers n et m tels que a = c^n et b = c^m. En particulier les monoïdes libres sur 0 et 1 élément sont commutatifs. JeanCASPAR (discuter) 20 août 2024 à 17:43 (CEST)

Oui, mon argument est trop général mais la définition d'une base dans cet article empêcherait l'ensemble des nombres premiers d'être une base de $(\mathbb {N} ^{*},\times ,1)$. Gênant...d'autant plus que cet exemple figure dans cet article comme archétype de monoïde libre. De même cela empêcherait$\{(0,1),(1,0)\}$ d'être une base du monoïde $\{\mathbb {N} ^{2},+,(0,0)\}$. mais peut-être ne s'agit-il pas de base (au sens d'objet libre)?

Il me parait donc nécessaire de s'appuyer sur des sources pour éviter les contradictions : il me semble, mais je peux me tromper, que selon la définition d'un objet libre, $(\mathbb {N} ^{*},\times ,1)$ ne serait pas libre sur l'ensemble des nombres premiers. De ce que je comprends de cet article on ne parlerait dans ces cas là que d'une "factorisation complète" (moins fort que la notion de base) => sources nécessaire ne se limitant pas à X* ensemble de mots formés sur l'alphabet X muni de la concaténation pour bien préciser les notions. HB (discuter) 21 août 2024 à 08:45 (CEST)

Ça ne me choque pas que $\mathbb {N} ^{*}$ et $\mathbb {N} ^{2}$ ne soient pas libres : un groupe libre n'est pas non plus commutatif en général. Par contre, il y a la notion de groupe abélien libre, et de même, la notion de monoide commutatif libre (voir https://vikraman.org/files/cmon22.pdf pour une présentation dans HoTT). Un monoïde commutatif libre est l'objet libre dans la catégorie des monoïdes commutatifs, et peut être défini comme un monoïde de la forme "l'ensemble des multiensembles finis sur un X". Avec cette définitions, $\mathbb {N} ^{*}$ est le monoïde commutatif libre sur les nombres premiers, et $\mathbb {N} ^{2}$ le monoïde commutatif libre sur $\{(1,0),(0,1)\}$. Je pense que l'erreur dans l'article vient de la confusion entre "monoïde libre" et "monoïde commutatif libre".

J'ai trouvé une définition de monoïde libre. Dans Combinatorics on words de M. Lothaire, le monoïde A* est défini comme l'ensemble des mots sur l'alphabet A. Puis il est dit que A* vérifie la propriété que pour toute fonction $f$ de A vers un monoïde M, il y a un unique morphisme de monoïdes $\varphi :A^{*}\to M$ tel que $f=\varphi \circ i$ avec $i:A\to A^{*}$ l'inclusion, c'est-à-dire la propriété universelle d'un objet libre. Ensuite, les auteurs disent qu'à cause de cette propriété, $A^{*}$ est parfois appelé "le monoïde libre sur l'alphabet A", et définissent formellement un monoïde libre comme un monoïde isomorphe à $A^{*}$ pour un certain $A$. En revanche dans ce livre, la notion de base, aussi appelée code, n'est définie que pour les sous-monoïdes libres de $A^{*}$, et c'est alors l'ensemble générateur minimal de $P$. On a la propriété que si $X$ est l'ensemble générateur minimal de $P$, $P$ est libre ssi $x_{1}\dots x_{n}=y_{1}\dots y_{m}\implies n=m\land \forall i\leq n,x_{i}=y_{i}$ pour tous $x_{i}$ et $y_{j}$ dans $X$.

Je pense qu'on peut enlever toute la partie sur les bases, j'ai fait une modification, dis-moi ce que tu en penses. JeanCASPAR (discuter) 21 août 2024 à 14:01 (CEST)

Merci. Je manque de temps de cerveau actuellement pour lire tes modifs attentivement. Je te fais confiance et reviendrai lire plus attentivement plus tard, d'autant plus qu'il me faudra entrer dans un vocabulaire non familier comme «multiensemble». A bientôt. HB (discuter) 21 août 2024 à 21:41 (CEST)

Bon, je reviens en mode rapide. J'ai lu tes modifs qui me paraissent revenir à plus de prudence et à un exposé cohérent. Merci.

Reste que, si les notions de monoïde libre et monoïde commutatif libre sont intrinsèquement différentes (le fait qu'un monoïde commutatif libre ne soit pas un monoïde libre est contre-intuitif), il serait utile de faire un avertissement. La source que tu donnes permettrait de justifier la notion de monoïde commutatif libre. HB (discuter) 27 août 2024 à 22:14 (CEST)

Notation 1/x

On lit dans l'article : " Le symétrique de $x$ est généralement noté $x^{-1}$. On le note parfois ${\frac {1}{x}}$ lorsque la loi est commutative, c'est notamment le cas avec la multiplication des nombres réels. On le note $-x$ lorsque la loi du monoïde est noté $+$."

N'est-ce pas plutôt la notation $-x$ qui est d'habitude réservée au cas commutatif (de même que la notation $+$) ?

Marvoir (d) 3 novembre 2008 à 06:38 (CET)

En effet. Ramzan (discuter) 12 septembre 2016 à 07:43 (CEST)

Clifford et Preston vol. 1 et 2

Cette réf ajoutée le 27/2/8 n'est à première vue pas pertinente pour cet article-ci. Elle est déjà dans l'article Demi-groupe. Anne (discuter) 20/1/14, 14h57