Semi-grup

În matematică , un semigrup este un set cu o operație binară asociativă . Cu alte cuvinte, prin semigrup înțelegem o structură algebrică exprimată printr-o pereche (A, *) cu A împreună și funcția * definită pe toate A × A cu valori în A pentru care avem

\forall a,b,c\in A\quad :\quad a*(b*c)=(a*b)*c\quad

{\ displaystyle \ forall a, b, c \ în A \ quad: \ quad a * (b * c) = (a * b) * c \ quad}

{\ displaystyle \ forall a, b, c \ în A \ quad: \ quad a * (b * c) = (a * b) * c \ quad}

.

În mod echivalent, orice magmă asociativă poate fi definită ca semigrup.

Primele exemple

Există multe exemple de semigrupuri finite și infinite. Să luăm în considerare unele dintre ele care sunt ușor de definit.

(0) Setul gol.

(1) Ansamblul numerelor întregi pozitive cu adunare (o operație notoriu asociativă).

(2) Ansamblul numerelor întregi naturale cu multiplicare (această operație este, de asemenea, notoriu asociativă).

(3) Întregul $\,\{1,2,3,4\}$ ${\ displaystyle \, \ {1,2,3,4 \}}$ ${\ displaystyle \, \ {1,2,3,4 \}}$ echipat cu operațiunea „alegerea maximului între două numere” pe care o putem scrie $\,\max(m,n)$ ${\ displaystyle \, \ max (m, n)}$ ${\ displaystyle \, \ max (m, n)}$ : pentru asociativitate este suficient să observăm că, evident,

\max(\max(m,n),p)\,=\,\max(m,n,p)\,=\,\max(m,\max(n,p))

{\ displaystyle \ max (\ max (m, n), p) \, = \, \ max (m, n, p) \, = \, \ max (m, \ max (n, p))}

{\ displaystyle \ max (\ max (m, n), p) \, = \, \ max (m, n, p) \, = \, \ max (m, \ max (n, p))}

(4) Setul tuturor funcțiilor finale definite în cadrul unui set S , de ex. în $\,\{1,2,3,4\}$ ${\ displaystyle \, \ {1,2,3,4 \}}$ ${\ displaystyle \, \ {1,2,3,4 \}}$ , echipat cu compoziția funcțiilor. Compoziția funcțiilor este de fapt asociativă.

(5) Setul, numărabil, al tuturor șirurilor de deasupra unui alfabet dat echipat cu juxtapunerea șirurilor. Juxtapunerea șirurilor este un fel de arhetip al operațiilor binare asociative. Acest semigrup se numește semigrup liber pe alfabetul prefixat.

Semigrupul (3) este un semigrup finit, are 4 elemente. Tabelul său de înmulțire constă din matrice

{\begin{bmatrix}1&2&3&4\\2&2&3&4\\3&3&3&4\\4&4&4&4\end{bmatrix}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & 3 & 4 \\ 2 & 2 & 3 & 4 \\ 3 & 3 & 3 & 4 \\ 4 & 4 & 4 & 4 \ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} 1 & 2 & 3 & 4 \\ 2 & 2 & 3 & 4 \\ 3 & 3 & 3 & 4 \\ 4 & 4 & 4 & 4 \ end {bmatrix}}}

Prin urmare, este evident o operațiune comutativă. Într-un caz ca acesta vorbim despre un semigrup comutativ sau un semigrup abelian . Semigrupurile (1) și (2) sunt, de asemenea, comutative.

Pe de altă parte, semigrupul liber (5) nu este comutativ dacă este construit pe un alfabet de două sau mai multe caractere: de exemplu

{\mbox{piano}}\cdot {\mbox{forte}}\neq {\mbox{forte}}\cdot {\mbox{piano}}

{\ displaystyle {\ mbox {piano}} \ cdot {\ mbox {forte}} \ neq {\ mbox {forte}} \ cdot {\ mbox {piano}}}

{\ displaystyle {\ mbox {piano}} \ cdot {\ mbox {forte}} \ neq {\ mbox {forte}} \ cdot {\ mbox {piano}}}

.

Nici semigrupul endofuncțiilor unui set de mediu S nu este format din 2 sau mai multe elemente comutative. Pentru aceasta este suficient să luăm în considerare contraexemplul a două funcții finale care nu fac naveta: dacă a și b sunt două elemente diferite ale mediului S , introducem cele două funcții cu valoare constantă $\,a^{cstnt}$ ${\ displaystyle \, a ^ {cstnt}}$ ${\ displaystyle \, a ^ {cstnt}}$ Și $\,b^{cstnt}$ ${\ displaystyle \, b ^ {cstnt}}$ ${\ displaystyle \, b ^ {cstnt}}$ , care ar trebui considerate ca transformări postfix, pentru a fi scrise în dreapta argumentului și apoi definite prin intermediul

\forall x=1,2,3,4:x\,a^{cstnt}\,:=\,a\quad (\;{\mbox{equivalente a}}\quad a^{cstnt}(x)\,:=\,a\;)

{\ displaystyle \ forall x = 1,2,3,4: x \, a ^ {cstnt} \ ,: = \, a \ quad (\; {\ mbox {echivalent cu}} \ quad a ^ {cstnt} (x) \ ,: = \, a \;)}

{\ displaystyle \ forall x = 1,2,3,4: x \, a ^ {cstnt} \ ,: = \, a \ quad (\; {\ mbox {echivalent cu}} \ quad a ^ {cstnt} (x) \ ,: = \, a \;)}

.

Cu această notație este clar că pentru cele două compoziții ale acestor două funcții avem

a^{cstnt}\circ b^{cstnt}=b^{cstnt}\neq b^{cstnt}\circ a^{cstnt}=a^{cstnt}

{\ displaystyle a ^ {cstnt} \ circ b ^ {cstnt} = b ^ {cstnt} \ neq b ^ {cstnt} \ circ a ^ {cstnt} = a ^ {cstnt}}

{\ displaystyle a ^ {cstnt} \ circ b ^ {cstnt} = b ^ {cstnt} \ neq b ^ {cstnt} \ circ a ^ {cstnt} = a ^ {cstnt}}

.

Semigrupuri și monoizi

Un semigrup cu un element neutru , adică un semigrup unital sau unitar este numit de obicei monoid . Fiecare semigrup S poate fi transformat într-un monoid prin simpla adăugare a unui element e care nu aparține lui S și definirea ee : = e și es : = s =: dacă pentru fiecare s în S. O astfel de expansiune poate fi realizată de mai multe ori (elementele neutre „vechi” nu mai sunt astfel, ci absorb compoziția cu cele „noi”).

Viceversa, având în vedere un monoid, acesta este redus la un semigrup, eliminând pur și simplu elementul de unitate și rândul și coloana corespunzătoare din tabelul de înmulțire; acest semigrup poate conține sau nu un nou element neutru. Prin urmare, studiul monoizilor adaugă foarte puțin la studiul semigrupurilor: cele două specii de structuri sunt substanțial echivalente.

Un monoid cu o bază este definit ca un monoid liber : este un semi-grup cu un element neutru cu o bază pentru elementele sale. Limbajul unui automat cu stare finită reprezentat de setul de șiruri de pe un anumit alfabet Σ este un exemplu important de monoid liber.

Alte exemple de semigrupuri

Fiecare grup poate fi considerat un monoid.
Orice ideal al oricărui inel , echipat cu operația de multiplicare de către inel.
Orice subset al unui semigrup care este închis pentru operația de semigrup.
Un semigrup a cărui operație este comutativă și idempotentă este o semireticulă . Semi-rețelele de acest fel sunt date de colecția de subseturi ale unui mediu dat echipat cu intersecție (sau uniune).
Ansamblul tuturor relațiilor dintr-un set prevăzut cu componența relațiilor.
Setul tuturor limbilor dintr-un alfabet dat echipat cu juxtapunerea dintre limbi.

Izomorfisme, subsemigrupuri și idealuri

Introducem acum relațiile și construcțiile care constituie armamentarul normal pentru studiul caracteristicilor structurilor algebrice ale speciilor de semigrup. Din motive de concizie, operația generică de semigrup este prezentată cu juxtapunere simplă, adică xy denotă rezultatul aplicării operației de semigrup la perechea ordonată ( x , y ). Dacă A și B sunt subseturi ale unui semigrup, atunci AB reprezintă mulțimea { ab | a în A și b în B }.

Se spune că două semigrupuri S și T sunt izomorfe dacă există o bijecție f : S → T cu proprietatea că, pentru fiecare pereche de elemente a , b în S , f ( ab ) = f ( a ) f ( b ). În acest caz f se numește izomorfism al lui S peste T. Dacă ne limităm la luarea în considerare a caracteristicilor elementelor semigrupurilor conectate la operațiile acestor structuri, două semigrupuri izomorfe sunt complet echivalente: se pot distinge în schimb de alte proprietăți care derivă din modalitățile în funcție de care au fost construite.

Un subgrup nevida A semigrup S se numește subsemigroup de S în cazul în care este închis pentru operațiunea semigrup, adică, în cazul în care AA este un subset al A. A se numește idealul drept dacă AS este un subset al lui A și simetric numit ideal stâng dacă SA este un subset al lui A. Dacă A este simultan idealul stâng și idealul drept, atunci se numește ideal bilateral sau pur și simplu idealul lui S. Vedem rapid că intersecția a două idealuri este, de asemenea, un ideal: se poate deduce că un semigrup poate avea cel mult un ideal minim . Idealul generic al semigrupului de numere întregi pozitive cu adunare este mulțimea multiplilor oricărui număr întreg pozitiv. Prin urmare, se poate observa că semigrupul aditiv de pozitivi nu posedă un ideal minim. Idealul minim al unui semigrup comutativ, atunci când există, este un grup.

Generarea de subgrupuri

Dacă S este un semigrup, atunci intersecția oricărei colecții a subgrupurilor sale este, de asemenea, un subgrup și S. Astfel, subgrupurile lui S formează o rețea completă . Pentru fiecare subset A de S dintre subgrupurile de S care conțin un astfel de A există unul și un singur minim pentru includere ; dacă notăm T, se spune că A generează T. Fiecare element x al lui S generează subgrupul { x ⁿ |: n întreg pozitiv} care este notat < x >. Dacă acest subset al lui S este finit, se spune că x este de ordin finit sau că are un ordin finit; mai exact, cardinalitatea subsemigrupului generat se numește ordinea lui x în S. Dacă, pe de altă parte, < x > este infinit (evident infinit numărabil), se spune că x are ordinea infinită sau are.

Un semigrup periodic este orice semigrup format numai din elemente de ordine finită. În mod clar, fiecare semigrup finit este periodic.

Un semigrup monogen este orice semigrup care poate fi considerat generat de un singur element (uneori se mai numește și un semigrup ciclic , dar această expresie poate induce confuzie). Fiecare semigrup monogen infinit este izomorf pentru semigrupul aditiv de numere întregi pozitive.

Semigrupurile monogene finite pot fi, de asemenea, identificate în mod cuprinzător. Notând x generatorul său și n cardinalitatea sa, elementele sale pot fi listate ca puteri succesive ale lui x : x , x ² , ..., x ⁿ ; următoarea putere x ^{n + 1} trebuie să coincidă cu o putere mai mică, să o scriem x ^k . Numerele întregi n și k caracterizează complet semigrupul. Să luăm în considerare mulțimea p: = n-k + 1 elemente G: = {m = k, k + 1, ..., n: | x ^m }. În mod clar constituie un subgrup al lui S ; mai exact este un grup, deoarece elementele sale sunt permutate atunci când sunt înmulțite cu unul dintre ele. Dacă k = 1 semigrupul este grupul ciclic de n elemente. Unitatea subgrupului este un idempotent al semigrupului; orice alt element al semigrupului înmulțit de la sine duce la un alt element. Prin urmare, fiecare semigrup periodic finit conține cel puțin un element idempotent și fiecare semigrup monogen finit conține exact un idempotent. De asemenea, se observă că subgrupul (grupul ciclic) al unui semigrup monogen finit este un ideal al semigrupului.

Semigrupuri și grupuri

Un subgrup al unui semigrup S care este, de asemenea, un grup se numește subgrup al lui S. Există o relație strânsă între subgrupurile unui semigrup și idempotenții săi. Fiecare subgrup conține exact un idempotent, adică elementul neutru al semigrupului. Pentru fiecare e idempotent al semigrupului există un singur subgrup maxim care conține și . Fiecare subgrup maxim este identificat în acest fel și, în consecință, există o corespondență unu-la-unu între subgrupuri idempotente și maxime. (Trebuie remarcat faptul că termenul de subgrup maxim este utilizat aici diferit de modul în care este utilizat în teoria grupurilor. În această teorie, un subgrup maxim este implicat a fi un subgrup propriu. Când este considerat un semigrup, un grup are doar un subgrup. maxim, adică el însuși.)

Semigrupuri de endofuncții

Fiecare semigrup poate fi considerat un semigrup de endofuncții: de fapt este posibil să se asocieze fiecărui element y al unui semigrup S endofuncția lui S corespunzătoare înmulțirii din dreapta cu y a diferitelor sale elemente. În schimb, semigrupul < E > generat de elementele lui E (și de toate produsele lor) este asociat cu fiecare set E de endofuncții ale unui set de mediu A. Dacă A este infinit, semigrupul < E > poate fi finit sau infinit; dacă A este finit < E > evident trebuie să fie finit.

Semigrupurile generate de seturi de relații într-un set de mediu pot fi, de asemenea, luate în considerare. Se constată că aceste semigrupuri pot fi reduse la semigrupuri de endofuncții: este vorba de trecerea de la relațiile dintr-un set A la endofuncțiile din setul de părți ale lui A. Semigrupurile de endofuncții din seturi finite pot fi tratate în mod convenabil ca semiautomate deterministe (stări finite), în timp ce semiautomatele de relații din cadrul seturilor finite pot fi tratate ca semiautomate nedeterministe . În acest sens, a se vedea teoria automatelor de stare finită .

Rezultatele acestor semigrupuri și automate pot fi, de asemenea, formulate ca fapte referitoare la relațiile de congruență în cadrul monoizilor liberi pe alfabete finite care furnizează coeficienți finiti. În acest sens, a se vedea teoria limbajelor raționale (sau limbaje regulate).

Se pot spune mult mai multe despre semigrupurile finite văzute în modurile anterioare. Rezultate remarcabile privind clasificarea structurilor unor astfel de semigrupuri finite sunt obținute din teoria Krohn-Rhodes .

Bibliografie

( EN ) John M. Howie (1995): Fundamentals of Semigroup Theory , Oxford University Press, ISBN 0198511949
( EN ) Aldo Belleni Morante , Semigrupuri aplicate și ecuații de evoluție , Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1979. XV + 387 pp. ISBN 0-19-853529-5
( EN ) Aldo Belleni Morante, A Concise Guide to Semigroups and Evolution Equations , Series on Advances in Mathematics for Applied Sciences, World Scientific Publishing Co. Inc., River Edge, NJ, 1994. XIV + 164 pp. ISBN 981-02-1294-1

Elemente conexe

Alte proiecte

Wikționarul conține dicționarul lema « semigrup »

linkuri externe

( EN ) Semigroup , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică