Полугрупа

У математици, полугрупа је алгебарска структура која се састоји од скупа S затвореног у односу на асоцијативну бинарну операцију.

Операција полугрупе се најчешће означава мултипликативно, то јест, $x\cdot y$ или једноставније xy означава резултат примењивања операције полугрупе на уређени пар $(x,y)$.

Формално проучавање полугрупа је почело у раном 20. веку. Од раних 1950их, теорија коначних полугрупа је од велике важности за теоријско рачунарство због природне везе између коначних полугрупа и коначних аутомата.

Формална дефиниција

Полугрупа се формално састоји од пара $(S,\cdot _{S})$ где је ${\textstyle S}$ скуп, а бинарна функција $\cdot _{S}:S\times S\rightarrow S$ која се назива операцијом полугрупе. Примена функције $\cdot _{S}$ на пар $(x,y)$ се једноставније записује $x\cdot _{S}y$ или $x\cdot y$. Неопходно је да је ова операција асоцијативна, то јест, да задовољава услов $(x\cdot y)\cdot z=x\cdot (y\cdot z)$ за свако $x,y,z\in S$. Уобичајена пракса у апстрактној алгебри је да се пар $(S,\cdot _{S})$ означава као S када је из контекста јасно која се операција користи.

Неки аутори захтевају да полугрупа буде непразна. Други користе израз полугрупа као синоним са изразом моноид, то јест, претпостављају да полугрупа има неутрал. У остатку чланка, израз полугрупа ће бити коришћен у најширем смислу, то јест, полугрупа може бити празна, а чак иако није празна, не мора да има неутрал.

Као што је горе напоменуто, моноид је полугрупа са неутралом. Свака полугрупа ${\textstyle S}$ се може допунити до моноиде (што се обично означава као $S^{1}$) једноставним додавањем елемента e који не припада ${\textstyle S}$ и дефинисањем ${\textstyle es=s=se}$ за свако ${\textstyle s\in S\cup \{e\}}$.

Комутативна полугрупа ${\textstyle S}$ се може допунити до групе ако и само ако има својство поништавања, у ком случају се може видети као подполугрупа групе разломака ${\textstyle SS^{-1}}$ (на сличан начин на који се интегрални домен улаже у своје поље разломака). У општем случају, да би се полугрупа могла уложити у групу, она мора имати својство поништавања, али је свеобухватан списак неопходних и довољних услова за уложивост, како је доказао Маљцев 1939., пребројиво бесконачан и ниједан његов коначан подскуп није довољан. Постоји велики број теорема које гарантују уложивост полугрупе у групу у посебним случајевима, попут нпр. Ореовог својства да свака два десна косета имају непразан пресек; за више информација о овом питању видети преглед Џона Микина.

Примери полугрупа

• Сваки моноид и стога свака група.
• Позитивни цели бројеви у односу на сабирање.
• Сваки подскуп полугрупе затворен у односу на операцију полугрупе. Такав подскуп је познат као подполугрупа.
• Полугрупа чија операција је идемпотентна и комутативна је полумрежа.
• Скуп свих коначних ниски над неком фиксираном азбуком $\Sigma$, у односу на конкатенацију стрингова као операцију. Ако је укључена празна ниска, онда се ради о моноиду; ако је празна ниска искључена, онда се ради о полугрупи над $\Sigma$.
• Бициклична полугрупа.
• Регуларне полугрупе.
• Инверзне полугрупе.

Литература

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