Semigrupuri și monoizi; reguli de calcul și puteri

Până acum am studiat proprietățile unei legi de compoziție una câte una: asociativitatea, comutativitatea, elementul neutru, elementele simetrizabile. Lecția de față face pasul care schimbă felul de a lucra: în loc să verificăm de fiecare dată totul de la capăt, dăm nume pachetelor de proprietăți și, odată numele pus, moștenim automat toate consecințele lor. Așa apar semigrupurile și monoizii, primele două structuri algebrice din programa de clasa a 12-a, mate-info. Semigrupul este o mulțime nevidă înzestrată cu o lege de compoziție asociativă, iar monoidul este un semigrup care are, în plus, element neutru; prin urmare orice monoid este semigrup, dar nu invers.

Ideea e simplă și profitabilă. Dacă știi doar că legea e asociativă, poți deja scrie produse lungi fără paranteze. Dacă știi în plus că există element neutru, poți defini puterile și poți demonstra că simetricul, atunci când există, este unic — exact teorema pe care am amânat-o în Elemente simetrizabile și simetricul unui element. Iar când, pe deasupra, toate elementele sunt simetrizabile, obții structura cea mai bogată din capitol, cea care va primi un nume în unitatea următoare și va ocupa singură douăzeci de lecții. La Bacalaureat M1, cerințele „arătați că $(M,\ast )$ este monoid comutativ" și „calculați $x^n$" sunt printre cele mai frecvente din Subiectul al II-lea.

Ce vei învăța

• Vei ști să definești un semigrup și un monoid și să spui precis ce proprietate le desparte.
• Vei ști să încadrezi operațiile uzuale de pe $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, pe matrice, pe funcții și pe mulțimea părților în ierarhia semigrup–monoid.
• Vei ști să demonstrezi unicitatea simetricului într-un monoid și să aplici regulile $(x^{\prime }{)}^{\prime }=x$ și $(x\ast y{)}^{\prime }=y^{\prime }\ast x^{\prime }$.
• Vei ști să folosești regula de simplificare cu un element simetrizabil, pentru a rezolva ecuații.
• Vei ști să calculezi puterile unui element, cu regulile $x^m\ast x^n=x^{m+n}$ și $(x^m{)}^n=x^{mn}$, și să explici de ce $(x\ast y{)}^n=x^n\ast y^n$ cere comutativitate.
• Vei ști să recunoști monoizi în afara matematicii: cuvintele unui alfabet cu concatenarea, transformările unui sistem cu compunerea.

Hai să descoperim împreună

1. Ce este un semigrup și ce este un monoid?

Un semigrup este o pereche $(M,\ast )$ formată dintr-o mulțime nevidă $M$ și o lege de compoziție $\ast$ pe $M$ care este asociativă, adică satisface $(x\ast y)\ast z=x\ast (y\ast z)$ pentru orice $x,y,z\in M$. Dacă, în plus, legea admite element neutru $e$, perechea $(M,\ast )$ se numește monoid. Un semigrup sau un monoid se numește comutativ dacă legea este comutativă.

Ierarhia se citește pe verticală, fiecare treaptă adăugând o cerință peste cea de dedesubt:

Reține ordinea, pentru că baremul o urmărește: orice monoid este semigrup, dar nu invers. Iar treapta a patra, monoidul în care toate elementele sunt simetrizabile, este ținta către care lucrăm — îi vom da un nume în unitatea următoare, iar de acolo încolo capitolul se schimbă complet.

Observă și ce nu apare în ierarhie: comutativitatea. Ea nu e o treaptă, ci un adjectiv care se poate adăuga oricărei trepte. Există semigrupuri comutative și necomutative, monoizi comutativi și necomutativi, iar exemplele de mai jos le arată pe toate.

2. Cum recunoști un monoid printre operațiile cunoscute?

Verifici două lucruri, în ordine: asociativitatea și existența elementului neutru. Metodele sunt cele din Asociativitatea unei legi de compoziție și din Elementul neutru al unei legi de compoziție: calculezi $(x\ast y)\ast z$ și $x\ast (y\ast z)$ și compari, apoi rezolvi ecuația $x\ast e=x$. Iată tabloul operațiilor pe care le cunoști deja, ordonat după structură:

Două rânduri merită comentate. $({\mathbb{N}}^{\ast },+)$ este un semigrup care nu este monoid: adunarea rămâne asociativă, dar elementul neutru $0$ a fost scos din mulțime, iar niciun număr natural nenul nu îl poate înlocui, pentru că $x+e=x$ obligă $e=0$. $(\mathbb{Z},-)$ nu urcă nici măcar prima treaptă: $(5-3)-2=0$, în timp ce $5-(3-2)=4$, deci scăderea nu este asociativă și nu are rost să căutăm mai departe.

Ultimul rând este cel mai interesant. La Legi de compoziție pe mulțimea părților ai văzut că diferența simetrică satisface $A△A=\varnothing$ pentru orice mulțime $A$. Cum $\varnothing$ este elementul neutru, înseamnă că fiecare element al monoidului $(\mathcal{P}(M),△)$ este simetrizabil, fiind propriul simetric. Iată deci un exemplu de structură completă, de pe treapta a patra.

3. De ce este simetricul unic într-un monoid?

Pentru că asociativitatea permite mutarea parantezelor, iar mutarea parantezelor forțează cei doi candidați să coincidă. Enunțul și demonstrația sunt cele care se cer la Bacalaureat M1.

Teoremă (unicitatea simetricului). Fie $(M,\ast )$ un monoid cu elementul neutru $e$ și fie $x\in M$ un element simetrizabil. Atunci simetricul lui $x$ este unic.

Demonstrație. Presupunem că $x$ are doi simetrici, $y$ și $z$; prin urmare $x\ast y=y\ast x=e$ și $x\ast z=z\ast x=e$. Calculăm produsul $y\ast x\ast z$ în două feluri. Grupând la dreapta,

$$y\ast (x\ast z)=y\ast e=y,$$

iar grupând la stânga,

$$(y\ast x)\ast z=e\ast z=z.$$

Cele două expresii sunt egale, pentru că legea este asociativă, deci $y=z$. $■$

Observă exact unde intervine ipoteza: la egalitatea $(y\ast x)\ast z=y\ast (x\ast z)$, adică la asociativitate. Fără ea, teorema e falsă — contraexemplul cu tabla pe trei elemente din lecția precedentă arată un element cu doi simetrici diferiți. De acum înainte, în orice monoid, avem dreptul să spunem „simetricul lui $x$", cu articol hotărât, și să-l notăm $x^{\prime }$ (respectiv $x^{-1}$ sau $-x$, după cum e scrisă legea).

4. Care sunt regulile de calcul într-un monoid?

Odată unicitatea asigurată, apar trei reguli pe care le vei folosi în aproape toate exercițiile. Fie $(M,\ast )$ monoid cu neutrul $e$.

Regula 1: $(x^{\prime }{)}^{\prime }=x$ pentru orice $x$ simetrizabil. Într-adevăr, egalitățile $x\ast x^{\prime }=x^{\prime }\ast x=e$ spun, citite invers, că $x$ este un simetric al lui $x^{\prime }$; cum simetricul este unic, el este cel simetric al lui $x^{\prime }$, adică $(x^{\prime }{)}^{\prime }=x$.

Regula 2: $(x\ast y{)}^{\prime }=y^{\prime }\ast x^{\prime }$ pentru $x,y$ simetrizabile — cu ordinea inversată. Verificăm direct, folosind asociativitatea:

$$(x\ast y)\ast (y^{\prime }\ast x^{\prime })=x\ast (y\ast y^{\prime })\ast x^{\prime }=x\ast e\ast x^{\prime }=x\ast x^{\prime }=e,$$

și analog $(y^{\prime }\ast x^{\prime })\ast (x\ast y)=e$. Prin urmare $y^{\prime }\ast x^{\prime }$ este simetricul lui $x\ast y$. Inversarea ordinii nu e un moft: la înmulțirea matricelor sau la compunerea funcțiilor, $x^{\prime }\ast y^{\prime }$ dă, în general, cu totul altceva. Regula seamănă cu ordinea în care îți scoți hainele — întâi ce ai pus ultima dată.

Regula 3 (simplificarea): dacă $x$ este simetrizabil, atunci din $x\ast y=x\ast z$ rezultă $y=z$, iar din $y\ast x=z\ast x$ rezultă tot $y=z$. Demonstrația compune la stânga cu $x^{\prime }$:

$$x\ast y=x\ast z\Rightarrow x^{\prime }\ast (x\ast y)=x^{\prime }\ast (x\ast z)\Rightarrow (x^{\prime }\ast x)\ast y=(x^{\prime }\ast x)\ast z\Rightarrow e\ast y=e\ast z\Rightarrow y=z.$$

Atenție la ipoteză: se simplifică numai cu elemente simetrizabile. În monoidul $(\mathbb{Z},\cdot )$, din $0\cdot 3=0\cdot 5$ nu rezultă $3=5$, tocmai pentru că $0$ nu este simetrizabil.

5. Ce este mulțimea $U(M)$ a elementelor simetrizabile?

Elementele simetrizabile ale unui monoid formează o mulțime care merită o notație proprie. Mulțimea $U(M)$ este mulțimea tuturor elementelor simetrizabile ale monoidului $(M,\ast )$; elementele ei se mai numesc unitățile monoidului. Ea nu e niciodată vidă, pentru că $e\in U(M)$, și este parte stabilă: dacă $x,y\in U(M)$, atunci $x\ast y\in U(M)$, cu simetricul $y^{\prime }\ast x^{\prime }$ dat de Regula 2. Când pe aceeași mulțime lucrăm cu mai multe legi, notația poartă și legea: scriem $U(\mathbb{Z},+)$ și $U(\mathbb{Z},\cdot )$, pentru că cele două mulțimi sunt complet diferite; forma scurtă $U(M)$ se folosește doar când legea e limpede din context.

Exemplele canonice, cele pe care programa cere să le compari între ele:

$$U(\mathbb{Z},\cdot )=\{-1,1\},U(\mathbb{Q},\cdot )={\mathbb{Q}}^{\ast },U(\mathbb{R},\cdot )={\mathbb{R}}^{\ast },U(\mathbb{C},\cdot )={\mathbb{C}}^{\ast }.$$

Aceeași operație, patru mulțimi, două răspunsuri complet diferite: pe $\mathbb{Z}$ rămân două elemente, pe celelalte trei rămâne tot ce nu e zero. Alte două exemple, la fel de folosite: $U({\mathcal{M}}_2(\mathbb{R}),\cdot )$ este mulțimea matricelor cu determinantul nenul, iar $U(\mathcal{F}(E),\circ )$ este mulțimea funcțiilor bijective de la $E$ la $E$. La capătul celălalt stau monoizii în care $U(M)=M$, adică cei în care toate elementele sunt simetrizabile: $(\mathbb{Z},+)$, $({\mathcal{M}}_2(\mathbb{R}),+)$, $(\mathcal{P}(M),△)$. Structura aceasta este cea care primește un nume în unitatea următoare.

6. Cum se calculează puterile unui element?

Într-un semigrup, puterile se definesc prin recurență, exact ca la numere:

$$x^1=x,x^{n+1}=x^n\ast x\text{pentru orice }n\in {\mathbb{N}}^{\ast }.$$

Într-un monoid se adaugă convenția $x^0=e$, care face ca regulile de mai jos să funcționeze și pentru exponentul zero. Cele două reguli de calcul sunt:

$$x^m\ast x^n=x^{m+n},{\left(x^m\right)}^n=x^{mn},m,n\in \mathbb{N}.$$

Prima se demonstrează prin inducție după $n$, cu metoda din Metoda inducției matematice: principiul dominoului. Pentru $n=0$ avem $x^m\ast x^0=x^m\ast e=x^m=x^{m+0}$. Presupunând $x^m\ast x^n=x^{m+n}$, obținem

$$x^m\ast x^{n+1}=x^m\ast \left(x^n\ast x\right)=\left(x^m\ast x^n\right)\ast x=x^{m+n}\ast x=x^{m+n+1},$$

unde pasul din mijloc folosește asociativitatea. A doua regulă se demonstrează la fel, prin inducție după $n$, folosind-o pe prima.

⚠️ Regula care NU se transferă: $(x\ast y{)}^n=x^n\ast y^n$ este adevărată numai dacă $x\ast y=y\ast x$. Într-adevăr, $(x\ast y{)}^2=x\ast y\ast x\ast y$, iar pentru a-l rescrie ca $x\ast x\ast y\ast y$ trebuie să schimbăm între ele pe $y$ și pe $x$ din mijloc. Contraexemplul se ia în $({\mathcal{M}}_2(\mathbb{R}),\cdot )$, folosind Înmulțirea a două matrice: pentru $A=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ și $B=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$ avem $AB=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$, deci $(AB{)}^2=\left(\begin{array}{cc}5& 3\\ 3& 2\end{array}\right)$, în timp ce $A^2{B}^2=\left(\begin{array}{cc}5& 2\\ 2& 1\end{array}\right)$.

Când legea e scrisă aditiv, puterile se numesc multipli și se notează $nx$ în loc de $x^n$: $1x=x$, $(n+1)x=nx+x$, $0x=0$, iar regulile devin $mx+nx=(m+n)x$ și $n(mx)=(nm)x$. Este aceeași teoremă, îmbrăcată în notația aditivă.

7. Asociativitatea generalizată: produse fără paranteze

Asociativitatea a fost enunțată pentru trei factori. Ea are însă o consecință care se folosește tăcut peste tot: într-un semigrup, produsul $x_1\ast x_2\ast \cdots \ast x_n$ nu depinde de felul în care punem parantezele, deci parantezele se pot omite cu totul. Afirmația se demonstrează prin inducție după $n$: cazul $n=3$ este chiar axioma, iar pasul de inducție arată că orice mod de a paranteza un produs de $n+1$ factori se poate rescrie sub forma $(x_1\ast \cdots \ast x_k)\ast (x_{k+1}\ast \cdots \ast x_{n+1})$ și apoi, folosind ipoteza, se reduce la forma standard.

Fără această consecință nu am putea scrie nici măcar $x^4$ fără să precizăm ce înmulțim cu ce. Atenție însă: independența de paranteze nu înseamnă independență de ordine. Într-un semigrup necomutativ, $x\ast y\ast z$ și $z\ast y\ast x$ sunt, în general, diferite; putem muta parantezele, nu factorii.

8. Monoizi din alte domenii: cuvinte, transformări, rotații

Structura de monoid apare masiv în afara matematicii, iar programa cere explicit câteva dintre aceste apariții.

Monoidul cuvintelor. Fie $A$ un alfabet, de pildă $A=\{a,b\}$, și fie $A^{\ast }$ mulțimea tuturor cuvintelor formate cu literele lui, inclusiv cuvântul vid, notat $\lambda$. Operația este concatenarea: lipirea a două cuvinte unul după altul, de exemplu $ab\ast ba=abba$. Concatenarea este asociativă (lipirea în orice ordine dă același șir de litere) și are elementul neutru $\lambda$, deci $(A^{\ast },\ast )$ este monoid. Nu este comutativ: $a\ast b=ab$, iar $b\ast a=ba$. Și, lucru surprinzător, singurul element simetrizabil este $\lambda$: lungimea cuvântului compus este suma lungimilor, deci din lungime $0$ rezultă că ambele cuvinte sunt vide. Așadar $U(A^{\ast })=\{\lambda \}$. Acesta este monoidul pe care se construiește toată teoria limbajelor formale din informatică — iar secvențele de nucleotide din ADN, cu alfabetul $\{A,C,G,T\}$, formează exact același tip de structură.

Monoidul transformărilor. Dacă un sistem fizic poate trece dintr-o stare în alta, iar fiecare transformare este o funcție de la mulțimea stărilor la ea însăși, atunci compunerea transformărilor este asociativă și are ca element neutru transformarea „nu se schimbă nimic". Structura este submonoidul lui $(\mathcal{F}(E),\circ )$ generat de transformările disponibile, iar întrebarea „ce transformări se pot anula?" este exact întrebarea despre $U(M)$.

Monoidul rotațiilor. Rotațiile unui pătrat în jurul centrului său, cu unghiuri multipli de $\frac{\pi }{2}$, formează mulțimea $\left\{R_0,R_{\frac{\pi }{2}},R_{\pi },R_{\frac{3\pi }{2}}\right\}$, iar compunerea a două rotații este tot o rotație din mulțime: unghiurile se adună, iar când suma ajunge la $2\pi$ rotația revine la $R_0$. Compunerea e asociativă, elementul neutru e $R_0$, deci avem un monoid comutativ; în plus, fiecare rotație are simetric, pentru că $R_{\alpha }$ compusă cu $R_{2\pi -\alpha }$ dă $R_0$. Este iarăși un monoid în care toate elementele sunt simetrizabile — structura căreia îi dăm un nume în unitatea următoare. Legătura cu algebra o cunoști din Matricea de rotație și puterile ei: fiecărei rotații îi corespunde o matrice, iar compunerii îi corespunde înmulțirea matricelor. În cristalografie, exact acest tip de monoid descrie simetriile unei rețele.

Monoizi de funcții. Funcțiile continue pe un interval $I$ formează monoid comutativ față de adunare, cu elementul neutru funcția nulă, pentru că suma a două funcții continue este continuă — proprietate cunoscută din clasa a XI-a. La fel, funcțiile derivabile pe $I$ formează monoid față de adunare. În schimb, față de compunere, funcțiile continue de la $I$ la $I$ formează un monoid necomutativ, cu elementul neutru $1_I$.

Exemple rezolvate

Exemplul 1 — O lege aditivă pe $\mathbb{Z}$

Arată că $(\mathbb{Z},\ast )$, cu $x\ast y=x+y-4$, este monoid comutativ și determină $U(\mathbb{Z},\ast )$.

Asociativitatea: $(x\ast y)\ast z=(x+y-4)+z-4=x+y+z-8$, iar $x\ast (y\ast z)=x+(y+z-4)-4=x+y+z-8$; expresiile coincid. Comutativitatea e imediată, adunarea numerelor fiind comutativă. Elementul neutru: din $x+e-4=x$ rezultă $e=4$. Deci $(\mathbb{Z},\ast )$ este monoid comutativ. Din $x+x^{\prime }-4=4$ obținem $x^{\prime }=8-x\in \mathbb{Z}$, deci $U(\mathbb{Z},\ast )=\mathbb{Z}$: toate elementele sunt simetrizabile.

Exemplul 2 — Un semigrup care nu e monoid

Arată că $({\mathbb{N}}^{\ast },+)$ este semigrup, dar nu este monoid.

Adunarea numerelor naturale nenule este asociativă, iar suma a două numere naturale nenule este tot un număr natural nenul, deci ${\mathbb{N}}^{\ast }$ este parte stabilă și $({\mathbb{N}}^{\ast },+)$ este semigrup. Dacă ar exista $e\in {\mathbb{N}}^{\ast }$ cu $x+e=x$ pentru orice $x$, am obține $e=0$, imposibil, pentru că $0\notin {\mathbb{N}}^{\ast }$. Deci nu există element neutru și structura nu urcă la treapta de monoid.

Exemplul 3 — Puterile unei matrice

În monoidul $({\mathcal{M}}_2(\mathbb{R}),\cdot )$, calculează $A^n$ pentru $A=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$, $n\in {\mathbb{N}}^{\ast }$.

Calculăm primii termeni: $A^2=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$, $A^3=\left(\begin{array}{cc}1& 3\\ 0& 1\end{array}\right)$. Presupunem $A^n=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$ și înmulțim cu $A$:

$$A^{n+1}=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& n+1\\ 0& 1\end{array}\right).$$

Prin inducție, $A^n=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$ pentru orice $n\in {\mathbb{N}}^{\ast }$; formula rămâne adevărată și pentru $n=0$, dând $I_2$. Control: $A^5=\left(\begin{array}{cc}1& 5\\ 0& 1\end{array}\right)$.

Exemplul 4 — Când $(x\ast y{)}^n\ne x^n\ast y^n$

În monoidul $(\mathcal{F}(\mathbb{R}),\circ )$, fie $f(x)=x+1$ și $g(x)=2x$. Compară $(f\circ g{)}^2$ cu $f^2\circ g^2$.

Avem $(f\circ g)(x)=f(2x)=2x+1$, deci $(f\circ g{)}^2(x)=2(2x+1)+1=4x+3$. Pe de altă parte, $f^2(x)=x+2$ și $g^2(x)=4x$, deci $\left(f^2\circ g^2\right)(x)=4x+2$. Cele două funcții sunt diferite, pentru că $4x+3\ne 4x+2$. Motivul: $f\circ g\ne g\circ f$, adică cele două elemente nu comută.

Exemplul 5 — Monoidul cuvintelor

Fie $A=\{a,b\}$ și $A^{\ast }$ monoidul cuvintelor cu concatenarea. Câte cuvinte de lungime $3$ există? Care sunt elementele simetrizabile?

Fiecare dintre cele trei poziții se completează în două feluri, deci există $2^3=8$ cuvinte de lungime $3$: $aaa$, $aab$, $aba$, $abb$, $baa$, $bab$, $bba$, $bbb$. Pentru simetrice, folosim lungimea: dacă $u\ast v=\lambda$, atunci lungimea lui $u$ plus lungimea lui $v$ este $0$, deci ambele sunt nule și $u=v=\lambda$. Prin urmare $U(A^{\ast })=\{\lambda \}$: singurul cuvânt simetrizabil este cuvântul vid.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră mulțimea $M=\left\{A(x)=\left(\begin{array}{cc}1& x\\ 0& 1\end{array}\right)|x\in \mathbb{R}\right\}$, cu înmulțirea matricelor.

a) Arată că $A(x)\cdot A(y)=A(x+y)$ pentru orice $x,y\in \mathbb{R}$.

$$A(x)A(y)=\left(\begin{array}{cc}1& x\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& y\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& x+y\\ 0& 1\end{array}\right)=A(x+y).$$

În particular, $M$ este parte stabilă a lui ${\mathcal{M}}_2(\mathbb{R})$ față de înmulțire.

b) Arată că $(M,\cdot )$ este monoid comutativ.

Asociativitatea se moștenește de la înmulțirea matricelor, care este asociativă pe ${\mathcal{M}}_2(\mathbb{R})$; nu se reverifică. Comutativitatea rezultă din punctul a): $A(x)A(y)=A(x+y)=A(y+x)=A(y)A(x)$. Elementul neutru este $A(0)=I_2$, pentru că $A(x)A(0)=A(x+0)=A(x)$. Deci $(M,\cdot )$ este monoid comutativ.

c) Determină $U(M)$ și calculează ${\left(A(x)\right)}^n$.

Din $A(x)A(x^{\prime })=A(0)$ obținem $x+x^{\prime }=0$, deci $x^{\prime }=-x$ și simetricul lui $A(x)$ este $A(-x)\in M$. Prin urmare $U(M,\cdot )=M$: toate elementele sunt simetrizabile, iar $(M,\cdot )$ este un monoid în care fiecare element are simetric — structura căreia îi dăm un nume în unitatea următoare. Din regula puterilor, ${\left(A(x)\right)}^n=A(nx)=\left(\begin{array}{cc}1& nx\\ 0& 1\end{array}\right)$ pentru orice $n\in \mathbb{N}$. Acesta este, aproape cuvânt cu cuvânt, formatul problemei din Subiectul al II-lea de la Bacalaureat M1.

Să exersăm

1. Arată că $(\mathbb{N},+)$ este monoid comutativ și precizează elementul neutru.

2. Este $({\mathbb{N}}^{\ast },+)$ monoid? Justifică răspunsul.

3. Este $(\mathbb{Z},-)$ semigrup? Verifică pe numerele $5$, $3$ și $2$.

4. Arată că $({\mathcal{M}}_2(\mathbb{R}),\cdot )$ este monoid necomutativ, dând două matrice care nu comută.

5. În monoidul $({\mathcal{M}}_2(\mathbb{R}),\cdot )$, calculează $A^5$ pentru $A=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$.

6. (Adevărat/Fals cu motivare.) „Într-un monoid, $(x\ast y{)}^{\prime }=x^{\prime }\ast y^{\prime }$ pentru orice $x,y$ simetrizabile."

7. În monoidul $(\mathcal{F}(\mathbb{R}),\circ )$, determină $f^4$ pentru $f(x)=x+3$.

8. Demonstrează prin inducție după $n$ că $x^m\ast x^n=x^{m+n}$ într-un monoid.

9. Arată că $(\mathcal{P}(M),\cup )$ este monoid comutativ și determină elementele simetrizabile.

10. Arată că în $(\mathcal{P}(M),△)$ toate elementele sunt simetrizabile și că fiecare este propriul simetric.

11. (Problemă aplicată.) În monoidul cuvintelor peste alfabetul $\{a,b\}$, scrie toate cuvintele de lungime $3$ și explică de ce singurul cuvânt simetrizabil este cuvântul vid.

12. Pe $M=(3,+\infty )$ se definește $x\ast y=xy-3x-3y+12$. Arată că $M$ este parte stabilă și că $(M,\ast )$ este monoid comutativ, precizând elementul neutru.

13. Într-un monoid, arată că dacă $x$ este simetrizabil și $x\ast y=x\ast z$, atunci $y=z$.

14. (Adevărat/Fals cu motivare.) „Orice semigrup este monoid."

15. (Exercițiu tip Bacalaureat M1.) Fie $M=\left\{A(x)=\left(\begin{array}{cc}1& x\\ 0& 1\end{array}\right)|x\in \mathbb{R}\right\}$. a) Arată că $A(x)A(y)=A(x+y)$. b) Arată că $(M,\cdot )$ este monoid comutativ. c) Determină simetricul lui $A(x)$ și calculează ${\left(A(2)\right)}^7$.

16. În $(\mathcal{F}(\mathbb{R}),\circ )$, fie $f(x)=2x$ și $g(x)=x+1$. Determină simetricul lui $f\circ g$ și verifică regula $(f\circ g{)}^{-1}=g^{-1}\circ f^{-1}$.

17. Determină mulțimea $U(\mathbb{Z},\cdot )$ a elementelor simetrizabile ale monoidului $(\mathbb{Z},\cdot )$ și arată că ea este parte stabilă față de înmulțire.

18. (Provocare.) Arată prin inducție că într-un monoid comutativ are loc $(x\ast y{)}^n=x^n\ast y^n$, apoi dă un contraexemplu care arată că, fără comutativitate, egalitatea este falsă.

Răspunsuri și explicații

1. Adunarea numerelor naturale este asociativă și comutativă, iar $x+0=0+x=x$ pentru orice $x\in \mathbb{N}$. Deci $(\mathbb{N},+)$ este monoid comutativ, cu $e=0$.

2. Nu. Adunarea rămâne asociativă, deci avem semigrup, dar condiția $x+e=x$ dă $e=0$, iar $0\notin {\mathbb{N}}^{\ast }$. Fără element neutru, structura nu este monoid.

3. Nu. $(5-3)-2=2-2=0$, în timp ce $5-(3-2)=5-1=4$. Cum $0\ne 4$, scăderea nu este asociativă, deci $(\mathbb{Z},-)$ nu este nici măcar semigrup.

4. Înmulțirea matricelor este asociativă și are elementul neutru $I_2$, deci avem monoid. Pentru $X=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ și $Y=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$ obținem $XY=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$ și $YX=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$, matrice diferite, deci monoidul nu este comutativ.

5. $A^n=\left(\begin{array}{cc}1& n\\ 0& 1\end{array}\right)$, deci $A^5=\left(\begin{array}{cc}1& 5\\ 0& 1\end{array}\right)$.

6. Fals. Regula corectă este $(x\ast y{)}^{\prime }=y^{\prime }\ast x^{\prime }$, cu ordinea inversată. Egalitatea din enunț este adevărată doar când $x$ și $y$ comută, de pildă în orice monoid comutativ.

7. Aplicând funcția de patru ori: $f^4(x)=x+3+3+3+3=x+12$.

8. Inducție după $n$. Pentru $n=0$: $x^m\ast x^0=x^m\ast e=x^m=x^{m+0}$. Pas: presupunem $x^m\ast x^n=x^{m+n}$; atunci $x^m\ast x^{n+1}=x^m\ast (x^n\ast x)=(x^m\ast x^n)\ast x=x^{m+n}\ast x=x^{m+n+1}$, unde am folosit asociativitatea și definiția puterii.

9. Reuniunea este asociativă și comutativă, iar $A\cup \varnothing =A$, deci $(\mathcal{P}(M),\cup )$ este monoid comutativ cu $e=\varnothing$. Din $A\cup B=\varnothing$ rezultă $A=B=\varnothing$, deci singurul element simetrizabil este $\varnothing$.

10. Pentru orice $A\subseteq M$ avem $A△A=\varnothing =e$, deci $A$ este simetrizabil și $A^{\prime }=A$. Prin urmare $U(\mathcal{P}(M),△)=\mathcal{P}(M)$.

11. Cuvintele de lungime $3$ sunt $aaa$, $aab$, $aba$, $abb$, $baa$, $bab$, $bba$, $bbb$ — în total $2^3=8$. Lungimea concatenării este suma lungimilor; dacă $u\ast v=\lambda$, lungimea sumă este $0$, deci ambele cuvinte au lungimea $0$ și sunt vide.

12. Forma factorizată este $x\ast y=(x-3)(y-3)+3$. Pentru $x,y>3$ avem $(x-3)(y-3)>0$, deci $x\ast y>3$ și $M$ este parte stabilă. Asociativitatea și comutativitatea se verifică prin calcul direct, iar din $(x-3)(e-3)=x-3$ rezultă $e=4\in M$. Deci $(M,\ast )$ este monoid comutativ.

13. Fie $x^{\prime }$ simetricul lui $x$. Compunem la stânga cu $x^{\prime }$: $x^{\prime }\ast (x\ast y)=x^{\prime }\ast (x\ast z)$. Prin asociativitate, $(x^{\prime }\ast x)\ast y=(x^{\prime }\ast x)\ast z$, adică $e\ast y=e\ast z$, deci $y=z$.

14. Fals. Un semigrup poate să nu aibă element neutru; exemplul standard este $({\mathbb{N}}^{\ast },+)$. Implicația funcționează doar în sens invers: orice monoid este semigrup.

15. a) $A(x)A(y)=\left(\begin{array}{cc}1& x+y\\ 0& 1\end{array}\right)=A(x+y)$. b) Asociativitatea se moștenește de la ${\mathcal{M}}_2(\mathbb{R})$, comutativitatea rezultă din $x+y=y+x$, iar elementul neutru este $A(0)=I_2$. c) Din $x+x^{\prime }=0$ obținem simetricul $A(-x)$; iar ${\left(A(2)\right)}^7=A(14)=\left(\begin{array}{cc}1& 14\\ 0& 1\end{array}\right)$.

16. $(f\circ g)(x)=2(x+1)=2x+2$, funcție bijectivă cu inversa $\frac{x-2}{2}$. Pe de altă parte, $f^{-1}(x)=\frac{x}{2}$ și $g^{-1}(x)=x-1$, deci $\left(g^{-1}\circ f^{-1}\right)(x)=\frac{x}{2}-1=\frac{x-2}{2}$. Cele două coincid, așa cum prevede Regula 2.

17. Din $xy=1$ cu $x,y\in \mathbb{Z}$ rezultă $x\in \{-1,1\}$, deci $U(\mathbb{Z},\cdot )=\{-1,1\}$. Mulțimea este parte stabilă: produsele posibile sunt $1\cdot 1=1$, $(-1)(-1)=1$ și $1\cdot (-1)=-1$, toate în $\{-1,1\}$.

18. Inducție după $n$. Pentru $n=1$ egalitatea e evidentă. Pas: $(x\ast y{)}^{n+1}=(x\ast y{)}^n\ast (x\ast y)=x^n\ast y^n\ast x\ast y$; folosind comutativitatea mutăm pe $x$ înaintea lui $y^n$ și obținem $x^n\ast x\ast y^n\ast y=x^{n+1}\ast y^{n+1}$. Contraexemplu fără comutativitate: cu $A=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ și $B=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$ avem $(AB{)}^2=\left(\begin{array}{cc}5& 3\\ 3& 2\end{array}\right)$, iar $A^2{B}^2=\left(\begin{array}{cc}5& 2\\ 2& 1\end{array}\right)$.

De reținut

• Un semigrup este o mulțime nevidă înzestrată cu o lege de compoziție asociativă, iar un monoid este un semigrup care are, în plus, element neutru.
• Într-un monoid, simetricul unui element simetrizabil este unic, iar demonstrația calculează produsul $y\ast x\ast z$ în două feluri, folosind asociativitatea.
• Regulile de calcul într-un monoid sunt $(x^{\prime }{)}^{\prime }=x$, $(x\ast y{)}^{\prime }=y^{\prime }\ast x^{\prime }$ cu ordinea inversată, și simplificarea cu un element simetrizabil.
• Mulțimea $U(M)$ a elementelor simetrizabile ale unui monoid conține întotdeauna elementul neutru și este parte stabilă față de legea monoidului.
• Puterile unui element se definesc prin $x^0=e$ și $x^{n+1}=x^n\ast x$, respectă regulile $x^m\ast x^n=x^{m+n}$ și ${\left(x^m\right)}^n=x^{mn}$, dar $(x\ast y{)}^n=x^n\ast y^n$ numai când $x$ și $y$ comută.

Greșeli frecvente

• Confuzia dintre semigrup și monoid. Semigrupul cere numai asociativitate; monoidul cere și element neutru. Orice monoid este semigrup, dar $({\mathbb{N}}^{\ast },+)$ arată că reciproca este falsă.
• Inversarea uitată în $(x\ast y{)}^{\prime }$. Simetricul unui compus este $y^{\prime }\ast x^{\prime }$, nu $x^{\prime }\ast y^{\prime }$. La matrice și la funcții greșeala duce la un rezultat pur și simplu fals; la legile comutative trece neobservată, ceea ce o face și mai periculoasă.
• Simplificarea cu un element nesimetrizabil. Din $x\ast y=x\ast z$ nu rezultă $y=z$ decât dacă $x$ este simetrizabil. În $(\mathbb{Z},\cdot )$, din $0\cdot 3=0\cdot 5$ nu urmează $3=5$.
• Aplicarea formulei $(x\ast y{)}^n=x^n\ast y^n$ fără comutativitate. Este cea mai frecventă eroare la puterile matricelor. Înainte de a o folosi, verifică $x\ast y=y\ast x$ și scrie asta explicit în rezolvare.
• Reverificarea asociativității pe o submulțime. Când legea este restricția uneia deja asociative (înmulțirea matricelor, compunerea funcțiilor), asociativitatea se moștenește și se spune în două cuvinte. Recalculul inutil consumă timp la Bacalaureat M1, iar uneori introduce erori.

Aplică acasă

1. Inventarul din bucătărie. Alege trei operații din viața de zi cu zi (amestecarea a două culori, lipirea a două bucăți de sfoară, suprapunerea a două filtre foto) și verifică pentru fiecare asociativitatea și existența unui element neutru. Care dintre ele formează monoid și care nu?

2. Monoidul cuvintelor, pe hârtie. Scrie toate cuvintele de lungime cel mult $2$ peste alfabetul $\{a,b\}$ și alcătuiește tabla concatenării pe această mulțime, cu tot cu cuvântul vid. Ce observi despre simetria tablei? Explică de ce structura nu este comutativă.

3. Puteri de matrice cu foaia de calcul. Într-o foaie de calcul, scrie matricea $\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ și calculează succesiv puterile ei până la a zecea. Compară rezultatele cu formula demonstrată în lecție, apoi repetă experimentul cu $\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right)$ și formulează singur o conjectură.

Pentru părinți și profesori

Lecția este pivotul unității: transformă lista de proprietăți verificate una câte una într-o clasificare cu nume. Ea verifică trei competențe: încadrarea corectă a unei structuri (semigrup sau monoid), redactarea unei demonstrații scurte cu axiome (unicitatea simetricului, regulile de calcul) și calculul cu puteri, inclusiv conștientizarea limitei impuse de necomutativitate.

De verificat în caiet: (1) la fiecare exemplu se spune care proprietate lipsește, nu doar „nu e monoid"; (2) asociativitatea moștenită este invocată, nu recalculată; (3) în demonstrația unicității simetricului se indică pasul în care se folosește asociativitatea; (4) formula $(x\ast y{)}^n=x^n\ast y^n$ apare numai însoțită de justificarea comutativității. Întrebări de control: „Ce lipsește ca $({\mathbb{N}}^{\ast },+)$ să fie monoid?"; „Cât face $(x\ast y{)}^{\prime }$?"; „Când ai voie să simplifici?"; „De ce $x^0=e$?".

La BAC, structura tipică a problemei este: se dă o mulțime cu o lege (deseori o familie de matrice sau un interval cu o lege polinomială), se cere stabilitatea, apoi structura de monoid comutativ, apoi simetricele sau o putere. Semn că elevul a înțeles: enumeră axiomele în ordine și justifică fiecare pas cu numele proprietății folosite, în loc să facă doar calcule.

Întrebări frecvente

Ce este un semigrup? Un semigrup este o mulțime nevidă $M$ împreună cu o lege de compoziție $\ast$ care este asociativă, adică $(x\ast y)\ast z=x\ast (y\ast z)$ pentru orice elemente $x$, $y$, $z$ din $M$. Nu se cere nimic altceva: nici element neutru, nici comutativitate, nici simetrice.

Ce este un monoid și prin ce diferă de un semigrup? Un monoid este un semigrup care are, în plus, element neutru. Diferența este exact această cerință: orice monoid este semigrup, dar nu invers. Exemplul standard de semigrup care nu e monoid este $({\mathbb{N}}^{\ast },+)$, unde adunarea rămâne asociativă, dar elementul neutru $0$ a fost scos din mulțime.

De ce este simetricul unic într-un monoid? Pentru că asociativitatea permite calcularea produsului $y\ast x\ast z$ în două moduri. Dacă $y$ și $z$ sunt amândoi simetrici ai lui $x$, gruparea la dreapta dă $y\ast (x\ast z)=y\ast e=y$, iar gruparea la stânga dă $(y\ast x)\ast z=e\ast z=z$. Cele două rezultate fiind egale, obținem $y=z$.

Care este formula simetricului unui produs? Formula este $(x\ast y{)}^{\prime }=y^{\prime }\ast x^{\prime }$, cu ordinea factorilor inversată. Se verifică direct: $(x\ast y)\ast (y^{\prime }\ast x^{\prime })=x\ast (y\ast y^{\prime })\ast x^{\prime }=x\ast x^{\prime }=e$. Inversarea contează la legile necomutative, cum sunt înmulțirea matricelor și compunerea funcțiilor.

Cum se calculează puterile unui element într-un monoid? Prin recurență: $x^0=e$, $x^1=x$ și $x^{n+1}=x^n\ast x$. Regulile de calcul sunt $x^m\ast x^n=x^{m+n}$ și ${\left(x^m\right)}^n=x^{mn}$, ambele demonstrate prin inducție. Când legea este scrisă aditiv, puterile se numesc multipli și se notează $nx$.

Când este adevărată egalitatea $(x\ast y{)}^n=x^n\ast y^n$? Numai atunci când $x$ și $y$ comută, adică $x\ast y=y\ast x$; în particular, în orice monoid comutativ. Contraexemplul clasic se ia cu matricele $\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$ și $\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$, pentru care $(AB{)}^2$ și $A^2{B}^2$ sunt matrice diferite.

Ce înseamnă notația $U(M)$? $U(M)$ este mulțimea elementelor simetrizabile ale monoidului $(M,\ast )$, numite și unitățile monoidului. Ea conține întotdeauna elementul neutru și este parte stabilă. Exemplele canonice sunt $U(\mathbb{Z},\cdot )=\{-1,1\}$, $U(\mathbb{Q},\cdot )={\mathbb{Q}}^{\ast }$ și mulțimea matricelor cu determinantul nenul.

Unde apar semigrupurile și monoizii în subiectele de Bacalaureat M1? În Subiectul al II-lea, aproape întotdeauna sub forma „arătați că $(M,\ast )$ este monoid comutativ", urmată de determinarea simetricelor sau de calculul unei puteri. Mulțimea este de regulă un interval cu o lege polinomială sau o familie de matrice depinzând de un parametru real.