Semi-grup

În matematică , semigrup este un set cu o asociativă operație binară . Cu alte cuvinte, prin semigrup ne referim la 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}

.

Echivalent, orice asociativă Magma poate fi definit ca un semigrup.

Primele exemple

Există mai multe exemple de semigrupuri finite și infinite. Să considerăm unele dintre ele, care sunt ușor de definit.

(0) vidă.

(1) Setul de numere naturale, cu adaos (operațiune notoriu asociative).

(2) Setul de numere întregi naturale cu multiplicare (această operațiune este de asemenea notorietate asociativ).

(3) Întreaga $\,\{1,2,3,4\}$ ${\ Displaystyle \, \ {1,2,3,4 \}}$ ${\ Displaystyle \, \ {1,2,3,4 \}}$ echipat cu operațiunea „alegerea maximă între două numere“ pe care le putem scrie $\,\max(m,n)$ ${\ Displaystyle \, \ max (m, n)}$ ${\ Displaystyle \, \ max (m, n)}$ : Pentru asociativitatea este suficient să se observe că, în mod 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) Ansamblul tuturor endofunctions definite în cadrul unui set S, de exemplu , în $\,\{1,2,3,4\}$ ${\ Displaystyle \, \ {1,2,3,4 \}}$ ${\ Displaystyle \, \ {1,2,3,4 \}}$ , Echipat cu compoziția de funcții. Compoziția funcțiilor este de fapt asociativ.

(5) set, numărabile, dintre toate șirurile de mai sus un anumit alfabet echipat cu juxtapunerea de coarde. Juxtapunerea siruri de caractere este un fel de arhetip de operații binare asociative. Acest semigrup este numit un semigrup liber pe alfabetul prestabilit.

Semigrupul (3) este un semigrup finit, are 4 elemente. Tabela de multiplicare este format din matricea

{\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ție comutativă. Într - un caz ca acesta vorbim de un semigrup comutativă sau un semigrup abeliană. The semigrupuri (1) și (2) sunt de asemenea comutativ.

Pe de altă parte, semigrupul liber (5) nu este comutativă în cazul în care 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 {pian}} \ cdot {\ mbox {}} FORTE \ neq {\ mbox {}} FORTE \ cdot {\ mbox {pian}}}

{\ Displaystyle {\ mbox {pian}} \ cdot {\ mbox {}} FORTE \ neq {\ mbox {}} FORTE \ cdot {\ mbox {pian}}}

.

De asemenea, nu este semigrupul din endofunctions oricărui set de mediu S format din 2 sau mai multe elemente comutativ. Pentru aceasta este suficient să se ia în considerare contraexemplul a două endofunctions care nu fac naveta: în cazul în care a și b sunt două elemente diferite ale mediului S, vom introduce 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 să fie considerate ca transformări postfix, care urmează să fie scris în dreapta argumentului și apoi definit 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} \ = ,: \, un \ quad (\; {\ mbox {echivalent}} \ quad a ^ {cstnt} (x) \ = ,: \ o \;)}

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

.

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} \ b ^ {Circ cstnt} = b ^ {cstnt} \ neq b ^ {cstnt} \ a ^ {Circ cstnt} = a ^ {cstnt}}

{\ Displaystyle a ^ {cstnt} \ b ^ {Circ cstnt} = b ^ {cstnt} \ neq b ^ {cstnt} \ a ^ {Circ cstnt} = a ^ {cstnt}}

.

SEMIGRUPURI și monoids

Un semigrup cu un element de neutru , adică un semigrup unital sau unitar se numește de obicei un monoid . Fiecare semigrup S poate fi făcută pentru a deveni un monoid pur și simplu prin adăugarea unui element e care nu aparțin S și definirea ee: = e și es: = s =: dacă pentru fiecare s în S. O astfel de extindere poate fi efectuată de mai multe ori (elementele neutre „vechi“ nu mai sunt astfel, dar absorb compoziția cu „noi“).

Viceversa, având în vedere o monoid, este redus la un semigrup prin simpla eliminare a elementului de unitate și rândul corespunzător și coloană din tabelul înmulțirii; acest semigrup poate sau nu poate să conțină un nou element neutru. Prin urmare, studiul monoids adaugă foarte puțin la studiul semigrupuri: 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 finit reprezentat de setul de siruri de caractere pe un anumit alfabet Σ este un exemplu important al unui monoid liber.

Alte exemple de semigrupuri

Fiecare grup poate fi considerat un monoid.
Orice ideală a oricărui inel , echipat cu operația de înmulțire cu inelul.
Orice subgrup al unui semigrup care este închis pentru operația semigrup.
Un semigrup a cărui funcționare este comutativă și idempotente este un semireticle . Semi-Grile de acest tip sunt date de colectarea subseturi de un mediu dat echipat cu intersecția (sau uniune).
Setul tuturor relațiilor din cadrul unui set prevăzut cu compoziția de relații.
Setul tuturor limbilor pe un anumit alfabet echipat cu juxtapunerea între limbi.

Izomorfismele, subsemigroups și idealuri

Acum introducem relațiile și construcțiile care constituie armamentarium normale pentru studiul caracteristicilor structurilor algebrice ale speciei semigrupul. Pentru concizie, operațiunea semigrup generic este prezentat cu simpla juxtapunere, adică xy denotă rezultatul aplicării operației semigrup perechii ordonate (x, y). Dacă A și B sunt subseturi ale unui semigrup, atunci AB denotă mulțimea {ab | o în A și b în B}.

Două semigrupuri S și T se spune că sunt izomorfe dacă există o bijectie 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 S peste T. Dacă ne limităm la examinarea caracteristicilor elementelor caracteristice ale semigrupuri conectate la operațiile acestor structuri, două semigrupuri izomorfe sunt complet echivalente: ele pot fi în schimb distinse de alte proprietăți care decurg din modalitățile conform cărora 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 A, și simetric numit un ideal stânga dacă SA este un subset al lui A. Dacă A este simultan idealul stâng și idealul dreapta, atunci aceasta se numește idealul bilateral sau pur și simplu idealul de S. Ne repede vedem că intersecția a două idealuri este , de asemenea , un ideal: se poate deduce că un semigrup poate avea cel mult un minim ideal. Idealul generic al semigrupul de numere naturale, cu adaos este setul de multipli de orice număr întreg pozitiv. Prin urmare, se poate observa că semigrupul aditiv pozitive nu posedă un ideal minim. Idealul minimă a unui semigrup comutativ, atunci când există, este un grup.

Generarea de subsemigroups

În cazul în care S este semigrup, atunci intersecția orice colecție de subsemigroups sale este , de asemenea , un subsemigroup si S. Astfel, subsemigroups de S formează o latice completă . Pentru fiecare subgrup A S între subsemigroups de S care conțin astfel de A este unul și numai unul minim pentru includere ; dacă vom nota T, se spune că A generează T. Fiecare element x al S generează subsemigroup {x ⁿ |: n întreg pozitiv} care este notată <x>. Dacă acest subset de S este finit, x este declarat a fi de ordin finit, sau că are ordin finit; mai precis, cardinalitatea al subsemigroup generat este numit ordinul x în S. Dacă, pe de altă parte, <x> este infinit (infinit evident numărabilă), x este declarat a fi, sau nu are, ordine infinit.

Un semigrup periodic este orice semigrup constând numai din elemente de ordin finit. În mod clar fiecare semigrup finit este periodică.

Un semigrup monogenic este orice semigrup care poate fi considerat generat de un singur element (uneori este numită semigrup ciclică, dar această expresie poate induce confuzie). Fiecare semigrup monogenic infinit este izomorf semigrupul aditiv de numere întregi pozitive.

semigrupuri monogenice finite pot fi, de asemenea, identificate în mod cuprinzător. Prin denotând x generatorul său și n cardinalitatea sale, elementele sale pot fi enumerate puteri succesive x: x, x ^2, ..., x ^n; următoarea putere x ^{n + 1} trebuie să coincidă cu o putere mai mică, să - l scrie x ^k. Numerele întregi n și k caracterizează complet semigrupul. Să considerăm setul de p: = n-k + 1 elemente G: = {m = k, k + 1, ..., n: | x ^m}. În mod evident, constituie o subsemigroup de S; mai precis este un grup, deoarece elementele sale sunt permutate atunci când acestea sunt multiplicate cu una dintre ele. Dacă k = 1 semigrupul este gruparea ciclică de n elemente. Unitatea subgrupului este o idempotente a semigrupul; orice alt element al semigrupul înmulțit cu sine conduce la un alt element. Prin urmare, fiecare semigrup periodică finită conține cel puțin un element de idempotente și fiecare finită monogenica semigrup conține exact un idempotente. De asemenea, se observă că subgrupul (grupă ciclică) a unei finite monogenica semigrup este un ideal al semigrupul.

SEMIGRUPURI și grupuri

Un subsemigroup unui semigrup S , care este , de asemenea , un grup este numit un subgrup de S. Există o relație strânsă între subgrupurile de semigrup și idempotents sale. Fiecare subgrupă conține exact un idempotente, adică elementul neutru al semigrupul. Pentru fiecare idempotente e de semigrupul există un singur subgrup maximal care conține și. Fiecare subgrup maximal este identificat în acest fel, și în consecință există o corespondență unu-la-unu între idempotente și subgrupe maximale. (Trebuie remarcat faptul că subgrupa termenul maxim este utilizat aici în mod diferit de modul în care este utilizat în teoria de grup. În această teorie, un subgrup maxim este implicat să fie un subgrup al propriei sale. Atunci când a considerat ca un semigrup, un grup are doar un subgrup. maximală, adică în sine.)

SEMIGRUPURI de endofunctions

Fiecare semigrup poate fi considerat un semigrup de endofunctions: de fapt, este posibil să se asocieze la fiecare element y al unui semigrup S endofunction de S care corespunde multiplicarea pe dreapta de către y a diferitelor elemente sale. In schimb, semigrupul <E> generată de elementele de E (și prin toate produsele lor) este asociată cu fiecare set E de endofunctions unui set de mediu A. Dacă A este infinit semigrupul <E> poate fi finit sau infinit; în cazul în care A este finită <E> , evident , trebuie să fie finită.

SEMIGRUPURI generate de seturi de relații într-un set de mediu poate fi, de asemenea, luate în considerare. Se constată că aceste semigrupuri pot fi reduse la semigrupuri de endofunctions: este o chestiune de trecere de la relațiile în cadrul unui set A la endofunctions în cadrul setului de părți A. De semigrupuri de endofunctions din cadrul seturilor finite pot fi în mod convenabil tratate ca semiautomata deterministă (stări finite), în timp ce semigrupuri relațiilor din cadrul seturilor finite pot fi tratate ca semiautomata non-deterministic . În acest sens, a se vedea Teoria automatelor de stare finită .

Rezultatele cu privire la aceste semigrupuri și aceste automate pot fi de asemenea formulate ca fapte în ceea ce privește relațiile congruență în cadrul monoids libere pe alfabetele finite care furnizează coeficienti finite. În acest sens, a se vedea Teoria limbilor raționale (sau limbi regulate).

Mult mai mult se poate spune despre SEMIGRUPURI finite observate în modurile anterioare. Rezultate remarcabile privind clasificarea structurilor de astfel semigrupuri finite sunt obținute din teoria Krohn-Rhodes .

Bibliografie

(RO) John M. Howie (1995): Fundamentele Teorie semigrup, Oxford University Press, ISBN 0198511949
(RO) Aldo Belleni Morante , semigrupuri aplicate și ecuațiile de evoluție, Oxford matematice Monografii. Clarendon Press, Oxford University Press, New York, 1979. XV + 387 pp. ISBN 0-19-853529-5
(RO) Aldo Belleni Morante, un ghid concis SEMIGRUPURI și Evolution Ecuații, Seria Advances in Matematica pentru Stiinte Aplicate, World Scientific Publishing Co., Inc. River Edge, NJ, 1994. XIV + 164 pp. ISBN 981-02-1294-1

Elemente conexe

Alte proiecte

Wikționar conține dicționarul Lema « semigrup »

linkuri externe

(RO) semigrup , în Enciclopedia Britannica , Encyclopaedia Britannica, Inc.

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