Monoide

In matematica , un monoide è una delle strutture algebriche utilizzate in algebra generale . È un insieme dotato di una legge di composizione interna associativa e di un elemento neutro . In altre parole, è un associativo e unificato magma , vale a dire un unico mezzo gruppo .

Preambolo

A volte capita che una struttura composta da un insieme e da una singola operazione sia relativamente povera di elementi invertibili, ad esempio un anello dove si considera solo la moltiplicazione. Una tale struttura è chiamata monoide . L'apparente povertà dell'operazione dà origine a una teoria specifica, come le relazioni di Green per monoidi o ideali in anelli anche non commutativi. Un'altra tecnica, quando ci si trova in presenza di un'operazione semplificabile, consiste nell ' "arricchire" il monoide per farne un gruppo .

A volte, al contrario, la struttura monoide è perfettamente adeguata. Questo è il caso dell'algebra dei polinomi in diversi indeterminati  : è costruita come l' algebra di un particolare monoide , generata da un insieme di indici.

Definizione

Un monoide è un magma unificato associativo.

Formalmente, ( E , ✻, e ) è un monoide quando, per ogni elemento x , y e z di E  :

• X∗y∈E{\ displaystyle x * y \ in E} (diritto interno);
• X∗(y∗z)=(X∗y)∗z{\ displaystyle x * (y * z) = (x * y) * z} (associatività);
• X∗e=e∗X=X{\ displaystyle x * e = e * x = x}( e è neutro).

Si dice che un E monoide sia semplificato a sinistra , o anche regolare a sinistra , (rispettivamente a destra ) se

∀(a,b,vs)∈E3,a∗b=a∗vs{\ displaystyle \ forall (a, b, c) \ in E ^ {3}, a * b = a * c \,}(rispettivamente )b∗a=vs∗a{\ displaystyle b * a = c * a \,}⇒b=vs.{\ displaystyle \ Rightarrow b = c.}

Un monoide si dice commutativo se i suoi elementi sono permutabili , cioè se:

∀(X,y)∈E2X∗y=y∗X.{\ displaystyle \ forall (x, y) \ in E ^ {2} \ quad x * y = y * x.}

Composto da una sequenza (finita) di elementi

Sia E un monoide. Notiamo la sua legge di composizione in forma moltiplicativa, vale a dire che scriveremo per designare il composto notato sopra. L'elemento neutro viene quindi indicato con 1. Xy{\ displaystyle xy}X∗y{\ displaystyle x * y}

Possiamo definire per induzione su n il prodotto di una n- tripla di elementi di E da: X1⋯Xnon{\ displaystyle x_ {1} \ cdots x_ {n}}

• il prodotto della tupla 0 è uguale a  ;1(0){\ displaystyle 1 \ quad (0)}
• X1⋯Xnon+1=(X1⋯Xnon)Xnon+1(1){\ displaystyle x_ {1} \ cdots x_ {n + 1} = (x_ {1} \ cdots x_ {n}) x_ {n + 1} \ quad (1)}.

Estendendo questa definizione al composto (“prodotto” nella nostra notazione) di una sequenza di elementi di E - vale a dire di una famiglia indicizzata da un insieme finito totalmente ordinato -, dimostriamo: ∏io∈ioXio{\ displaystyle \ prod _ {i \ in I} x_ {i}} (Xio)io∈io{\ displaystyle (x_ {i}) _ {i \ in I}}

• un teorema di associatività secondo il quale, in un monoide, un prodotto , valutato con questa definizione o ponendo le parentesi in altro modo , darà lo stesso risultato (ad esempio :) .X1⋯Xnon{\ displaystyle x_ {1} \ cdots x_ {n}}((ab)vs)d=(a(bvs))d=(ab)(vsd)=a((bvs)d)=a(b(vsd)){\ displaystyle ((ab) c) d = (a (bc)) d = (ab) (cd) = a ((bc) d) = a (b (cd))}
• un teorema di commutatività secondo il quale, in un monoide commutativo (o più in generale, per una famiglia i cui elementi commutano a due a due) il composto di una famiglia finita non dipende dall'ordine scelto sull'indice di questa famiglia.

Un corollario è che per ogni ( n + 1) -tupla di elementi di E , (X1,...,Xnon+1){\ displaystyle (x_ {1}, \ ldots, x_ {n + 1})}

X1⋯Xnon+1=X1(X2⋯Xnon+1)(2){\ displaystyle x_ {1} \ cdots x_ {n + 1} = x_ {1} (x_ {2} \ cdots x_ {n + 1}) \ quad (2)}.

Questa formula (2), unita alla condizione (0) di cui sopra, è l'altra definizione comune di per induzione su n . Il corollario permette di provare l'equivalenza di queste due definizioni, per induzione sul numero di fattori. X1⋯Xnon{\ displaystyle x_ {1} \ cdots x_ {n}}

Sub-monoide

Un sub-monoide di un monoide ( E , ✻, e ) è un sottoinsieme F di E che soddisfa:

• ∀X,y∈FX∗y∈F{\ displaystyle \ forall x, y \ in F \ quad x * y \ in F} (stabile);
• e∈F.{\ displaystyle e \ in F.}

Qualsiasi intersezione di sub-monoidi è un sub-monoide.

Un sotto- semigruppo di un monoide M può essere un monoide senza essere un sub-monoide di M. Ad esempio, se M è il monoide formato dall'insieme ℤ / 6ℤ con la sua moltiplicazione, le classi residue delle coppie di numeri formano un sotto-semigruppo D di M ed è facile verificare che la classe residua di 4 è un elemento neutro di questo sotto-semigruppo. Tuttavia, D non è un sottomonoide di M, perché l'elemento neutro di M (la classe residua di 1) non appartiene a D.

Generazione della famiglia di un sottomonoide

Sia P una parte di un monoide ( E , ✻, e ). Chiamato submonoid generato da P (indicato P *) all'intersezione della sotto-monoidi E contenente P . Questo è il più piccolo di submonoid E contenente P . Può essere descritto da:

P∗={X∈E∣∃non∈NON,∃(a1,⋯,anon)∈Pnon,X=a1∗⋯∗anon}{\ displaystyle P ^ {*} = \ {x \ in E \ mid \ esiste n \ in \ mathbb {N}, \ esiste (a_ {1}, \ cdots, a_ {n}) \ in P ^ {n }, x = a_ {1} * \ cdots * a_ {n} \}}

(l'elemento e fa effettivamente parte di questo insieme: è il prodotto vuoto , corrispondente a n = 0).

P è chiamata famiglia generatrice di P *.

Possiamo sempre trovare una famiglia di generatori per qualsiasi monoide, essendo il più banale stesso.

Basi libere e monoidi

Una parte P di un monoide ( E , ✻, e ) è detta base di E se è una famiglia generatrice di E in cui ogni elemento si decompone in modo univoco, cioè se

∀X∈E∃!non∈NON∃!(a1,...,anon)∈Pnon,X=a1∗⋯∗anon.{\ displaystyle \ forall x \ in E \ quad \ esiste! n \ in \ mathbb {N} \ quad \ esiste! (a_ {1}, \ ldots, a_ {n}) \ in P ^ {n}, x = a_ {1} * \ cdots * a_ {n}.}

Si dice che un monoide sia libero se ammette una base. In questo caso, la base è unica.

• e non appartiene alla base, altrimenti gli elementi avrebbero un'infinità di possibili decomposizioni.
• Se A è un insieme (talvolta chiamato alfabeto ), l'insieme di sequenze finite di elementi di A (chiamati parole ) con l'operazione di concatenazione è un monoide libero notato A * e chiamato monoid gratuito  (in) su A . La sua base è l'insieme di parole di lunghezza uno, e quindi naturalmente assimilabili all'alfabeto.
• Due monoidi liberi su alfabeti finiti sono isomorfi se e solo se le loro basi hanno la stessa cardinalità.
• In un monoide libero, l'elemento neutro è l'unico elemento che può essere simmetrizzato .

Esempi

• L'insieme dei numeri naturali fornito con l'aggiunta è un monoide libero, di cui 0 è l'elemento neutro e 1 l'unico elemento della base.NON{\ displaystyle \ mathbb {N}}
• NON{\ displaystyle \ mathbb {N}}fornito con la moltiplicazione è un monoide dell'elemento neutro 1. L'elemento 0 non è semplificabile .(∀(non,m)0.non=0.m){\ displaystyle (\ forall (n, m) \, 0.n = 0.m \,)}
• NON{\ displaystyle \ mathbb {N}}provvisto della legge max che associa a due interi il maggiore dei due è un monoide con neutro 0.
• L' insieme delle parti di un insieme E , dotato dell'unione dell'insieme, è un monoide, di cui l'insieme vuoto è l'elemento neutro. Lo stesso insieme dotato dell'intersezione dell'insieme è anche un monoide di cui E è l'elemento neutro.
• L'insieme delle applicazioni di un insieme in sé, fornito con la composizione , è un monoide il cui neutro è l' applicazione identitaria , gli elementi che possono essere semplificati a sinistra sono le iniezioni e quelli che possono essere semplificati a destra sono le suriezioni .
• La seconda legge di un anello unitario ha una struttura monoide (non commutativa se l' anello è non commutativo ).

Morfismo monoide

Siano ( E , ✻, e ) e ( F , ✮, f ) due monoidi. Chiamiamo morfismo da ( E , ✻, e ) a ( F , ✮, f ) qualsiasi mappa φ da E a F tale che

• ∀X,y∈Eφ(X∗y)=φ(X)⋆φ(y){\ Displaystyle \ forall x, y \ in E \ quad \ varphi (x * y) = \ varphi (x) \ star \ varphi (y)}
• φ(e)=f.{\ displaystyle \ varphi (e) = f.}

La prima proprietà è quella del morfismo dei magmi .

• Il composto di due morfismi di monoidi è un morfismo di monoidi.
• Il reciproco di un morfismo biettivo di monoidi è un morfismo di monoidi. Di conseguenza, un morfismo biettivo è chiamato isomorfismo.
• Qualsiasi morfismo di magmi da un monoide a un monoide semplificabile è un morfismo di monoidi.
• Se dotiamo l'insieme degli interi naturali con la legge del massimo , la mappa n ↦ n + 1 è un morfismo dei magmi ma non è un morfismo dei monoidi.
• Qualsiasi morfismo magmatico suriettivo tra due monoidi è un morfismo monoide.
• Chiamiamo il nucleo di un morfismo di monoidi l'insieme degli antecedenti dell'elemento neutro. Se il morfismo è iniettivo allora il suo nucleo è ridotto all'elemento neutro, ma il contrario è generalmente falso (a differenza del caso di un morfismo di gruppo ): per esempio il morfismo che associa la sua lunghezza a qualsiasi parola, da un monoide libero su almeno) due elementi verso (ℕ, +) , non è iniettiva.

• L' immagine reciproca di un sottomonoide da un morfismo di monoidi è un sottomonoide . In particolare, il nucleo di un morfismo monoide è un sottomonoide.
• L' immagine di un sottomonoide da un morfismo di monoidi è un sottomonoide. In particolare, l' immagine di un morfismo di monoidi è un sottomonoide.

Prodotto diretto di monoidi

• Siano ( E , ✻, e ) e ( F , ✮, f ) due monoidi. Possiamo fornire al prodotto cartesiano una struttura monoide introducendo una nuova legge come segue:E×F{\ displaystyle E \ times F \,}∧{\ displaystyle \ wedge}

∀(X,y),(X′,y′)∈(E×F)2, (X,y)∧(X′,y′)=(X∗X′,y⋆y′){\ Displaystyle \ forall (x, y), (x ', y') \ in (E \ times F) ^ {2}, \ (x, y) \ wedge (x ', y') = (x * x ', y \ star y')}.
È un monoide neutro .(e,f){\ displaystyle \ displaystyle (e, f)}

• Le due proiezioni di in e di in sono morfismi monoide. E la terzina controlla la proprietà universale del prodotto diretto .p:(X,y)↦X{\ displaystyle p: (x, y) \ mapsto x}E×F{\ displaystyle E \ times F}E{\ displaystyle \ displaystyle E}q:(X,y)↦y{\ displaystyle q: (x, y) \ mapsto y}E×F{\ displaystyle E \ times F}F{\ displaystyle \ displaystyle F}((E×F,∧,(e,f)),p,q){\ displaystyle ((E \ times F, \ wedge, (e, f)), p, q)}
• Più in generale, cioè un insieme e una famiglia di monoidi. Costruiamo la struttura del prodotto diretto sul prodotto cartesiano dalla formulaio{\ displaystyle I}((Eio,∗io,eio))io∈io{\ displaystyle ((E_ {i}, * _ {i}, e_ {i})) _ {i \ in I}}∏io∈io(Eio){\ displaystyle \ prod _ {i \ in I} (E_ {i})}

(Xio)io∈io∗(yio)io∈io=(Xio∗ioyio)io∈io.{\ displaystyle (x_ {i}) _ {i \ in I} * (y_ {i}) _ {i \ in I} = (x_ {i} * _ {i} y_ {i}) _ {i \ in I}.}.

Simmetrica di un elemento

• Sia ( E , ✻, e ) un monoide e x un elemento E . Diciamo che:
  • x è simmetrizzabile a destra se esiste un elemento y in E tale che x ✻ y = e . Diciamo quindi che y è un simmetrico retto di x  ;
  • x è simmetrizzabile a sinistra se esiste un elemento z in E tale che z ✻ x = e . Diciamo quindi che z è simmetrico a sinistra di x  ;
  • x è simmetrizzabile se è simmetrizzabile a destra ea sinistra.
• Quando x è simmetrizzabile, ammette un unico simmetrico destro e un unico simmetrico sinistro e questi sono uguali.Infatti, con le notazioni precedenti, y = e ✻ y = ( z ✻ x ) ✻ y = z ✻ ( x ✻ y ) = z ✻ e = z .Questo singolo elemento è chiamato simmetrico di x e generalmente indicato con x −1 .
• L'insieme I ( E ) degli elementi simmetrizzabili del monoide forma un gruppo, perché è stabile:
  • andando simmetrico: per ogni x ∈ I ( E ), x −1 ∈ I ( E ) e ( x −1 ) −1 = x  ;
  • per prodotto: per ogni x , y ∈ I ( E ), x ✻ y ∈ I ( E ) e ( x ✻ y ) −1 = y −1 ✻ x −1 .Infatti, ( y −1 ✻ x −1 ) ✻ ( x ✻ y ) = y −1 ✻ ( x −1 ✻ x ) ✻ y = y −1 ✻ e ✻ y = y −1 ✻ y = e quindi anche ( impostando un y = -1 e b = x -1 ) ( x ✻ y ) ✻ ( y -1 ✻ x -1 ) = ( b -1 ✻ un -1 ) ✻ ( un ✻ b ) = e .
• Per restrizione, qualsiasi morfismo φ: ( E , ✻, e ) → ( F , ✮, f ) tra due monoidi induce un morfismo di gruppo da I ( E ) a I ( F ).
  Nella teoria delle categorie , dicendo che nell'interpretare il fatto che I è un funtore dalla categoria dei monoidi nel gruppo (cioè l' aggiunto destro del funtore dimenticando M  : Grp → My ).

Simmetrizzazione

Generalizziamo la costruzione di interi relativi da interi naturali , associando canonicamente a qualsiasi monoide commutativo M = ( S , +, 0) un gruppo abeliano G ( M ), chiamato il suo gruppo Grothendieck , dotato di un morfismo di monoidi da M a G ( M ).

Il processo di costruzione è chiamato simmetrizzazione monoide. Per questo, consideriamo la relazione di equivalenza ∼ su S × S definita da:

(m,non)∼(p,q)⇔∃K∈Sm+q+K=p+non+K.{\ displaystyle (m, n) \ sim (p, q) \ Leftrightarrow \ esiste k \ in S \ quad m + q + k = p + n + k.}

Il gruppo G ( M ) ha come elementi le classi di equivalenza di ∼ e il morfismo naturale di M in G ( M ) associa ad ogni elemento x di S la classe di ( x , 0). Questo morfismo è iniettivo se e solo se M è semplificabile; in questo caso, la relazione ∼ può essere descritta più semplicemente:

(m,non)∼(p,q)⇔m+q=p+non.{\ displaystyle (m, n) \ sim (p, q) \ Leftrightarrow m + q = p + n.}

Applicazioni

Il monoide è un buon framework per definire le iterazioni di un elemento.

In informatica teorica , monoidi e più in particolare il monoide libero sono tra le strutture più utilizzate, in particolare nella teoria dei codici e nella teoria dei linguaggi .

Il termine "monoide" ha fatto il suo ingresso nell'arte contemporanea negli anni '70 con il pittore Jean-Claude Bédard, che lo giustifica nel suo libro Pour un art schématique: study d'un monoïdeographique , Éditions de Beaune et Goutal-Darley, 1978.

Note e riferimenti

1. Questa sezione è molto più dettagliata nel capitolo "Composto da una sequenza" della lezione sui monoidi su Wikiversità .
2. N. Bourbaki , Algebra, capitoli da 1 a 3 , Springer ,2007, cap. I, § 1, n .  3, p.  4 e § 2, n o  1, p.  13 .
3. Bourbaki 2007 , cap. I, § 1, teor. 2, p. 8.
4. Bourbaki 2007 , cap. I, § 2, n o  1, p. 13.
5. (in) Arjeh Cohen, Hans Cuypers e Hans Sterk, Algebra Interactive!: Imparare l'algebra in modo emozionante Springer1999( leggi in linea ) , p.  71.
6. (in) Henri Bourlès e Bogdan Marinescu Linear Time-Varying Systems: Algebraic-Analytic Approach , Springer,2011( leggi in linea ) , p.  30.
7. Per una dimostrazione, vedi ad esempio la chiave di risposta per il corrispondente esercizio su Wikiversità .

Articoli Correlati

• Mezzo gruppo
• Monoide digitale

Bibliografia

(en) Alfred H. Clifford e Gordon B. Preston , The Algebraic Theory of Semigroups , vol.  1 ( 2 ° ed. 1964) e vol. 2 (ristampa 1988), AMS

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">