Polugrupa

U matematici, polugrupa je algebarska struktura koja se sastoji od skupa S zatvorenog u odnosu na asocijativnu binarnu operaciju.

Operacija polugrupe se najčešće označava multiplikativno, to jest, $x\cdot y$ ili jednostavnije xy označava rezultat primenjivanja operacije polugrupe na uređeni par $(x,y)$.

Formalno proučavanje polugrupa je počelo u ranom 20. veku. Od ranih 1950ih, teorija konačnih polugrupa je od velike važnosti za teorijsko računarstvo zbog prirodne veze između konačnih polugrupa i konačnih automata.

Formalna definicija

Polugrupa se formalno sastoji od para $(S,\cdot _{S})$ gde je ${\textstyle S}$ skup, a binarna funkcija $\cdot _{S}:S\times S\rightarrow S$ koja se naziva operacijom polugrupe. Primena funkcije $\cdot _{S}$ na par $(x,y)$ se jednostavnije zapisuje $x\cdot _{S}y$ ili $x\cdot y$. Neophodno je da je ova operacija asocijativna, to jest, da zadovoljava uslov $(x\cdot y)\cdot z=x\cdot (y\cdot z)$ za svako $x,y,z\in S$. Uobičajena praksa u apstraktnoj algebri je da se par $(S,\cdot _{S})$ označava kao S kada je iz konteksta jasno koja se operacija koristi.

Neki autori zahtevaju da polugrupa bude neprazna. Drugi koriste izraz polugrupa kao sinonim sa izrazom monoid, to jest, pretpostavljaju da polugrupa ima neutral. U ostatku članka, izraz polugrupa će biti korišćen u najširem smislu, to jest, polugrupa može biti prazna, a čak iako nije prazna, ne mora da ima neutral.

Kao što je gore napomenuto, monoid je polugrupa sa neutralom. Svaka polugrupa ${\textstyle S}$ se može dopuniti do monoide (što se obično označava kao $S^{1}$) jednostavnim dodavanjem elementa e koji ne pripada ${\textstyle S}$ i definisanjem ${\textstyle es=s=se}$ za svako ${\textstyle s\in S\cup \{e\}}$.

Komutativna polugrupa ${\textstyle S}$ se može dopuniti do grupe ako i samo ako ima svojstvo poništavanja, u kom slučaju se može videti kao podpolugrupa grupe razlomaka ${\textstyle SS^{-1}}$ (na sličan način na koji se integralni domen ulaže u svoje polje razlomaka). U opštem slučaju, da bi se polugrupa mogla uložiti u grupu, ona mora imati svojstvo poništavanja, ali je sveobuhvatan spisak neophodnih i dovoljnih uslova za uloživost, kako je dokazao Maljcev 1939, prebrojivo beskonačan i nijedan njegov konačan podskup nije dovoljan. Postoji veliki broj teorema koje garantuju uloživost polugrupe u grupu u posebnim slučajevima, poput npr. Oreovog svojstva da svaka dva desna koseta imaju neprazan presek; za više informacija o ovom pitanju videti pregled Džona Mikina.

Primeri polugrupa

• Svaki monoid i stoga svaka grupa.
• Pozitivni celi brojevi u odnosu na sabiranje.
• Svaki podskup polugrupe zatvoren u odnosu na operaciju polugrupe. Takav podskup je poznat kao podpolugrupa.
• Polugrupa čija operacija je idempotentna i komutativna je polumreža.
• Skup svih konačnih niski nad nekom fiksiranom azbukom $\Sigma$, u odnosu na konkatenaciju stringova kao operaciju. Ako je uključena prazna niska, onda se radi o monoidu; ako je prazna niska isključena, onda se radi o polugrupi nad $\Sigma$.
• Biciklična polugrupa.
• Regularne polugrupe.
• Inverzne polugrupe.

Literatura

• Ayres, Frank, Schaum's Outline of Modern Abstract Algebra, McGraw-Hill; 1st edition (June 1). 1965. ISBN 978-0-07-002655-1..