Szabad félcsoport

Egy $\left(\left[X\right];\cdot \right)$ tartóhalmaz, művelet párt szabad félcsoportnak nevezünk pontosan akkor, ha minden $\left(\left[A\right];*\right)$ félcsoportra teljesül, hogy akármilyen $\varphi :X\to A$ függvény homomorf módon kiterjeszthető $\left[X\right]$ és $\left[A\right]$ között menő függvénnyé.

Ahol $\left[X\right]$ az X halmaz $\cdot$ műveletre vonatkozó generátuma, és $\left[A\right]$ a $*$ művelettel az A halmazé .

Motiváció

Félcsoportok általános vizsgálatakor felmerül a kérdés, hogy melyek azok az azonosságok, amelyek minden félcsoportban teljesülnek. Nyilván az asszociativitás teljesül, hiszen ez része a félcsoport definíciójának. A kérdés, hogy például kommutatív-e minden félcsoport. Erre a válasz nem, hiszen egyszerűen adható ellenpélda a csoportelméletből már megismert geometriai forgatások és tükrözések példájából kiindulva. (Például az a félcsoport, ami a tükrözést, és a 90 fokos forgatást tartalmazza, s ezek összes létező összetételét (a kompozícióval, mint művelettel), nyilván nem kommutatív, hiszen a forgatás és tükrözés nem felcserélhető elemek.)

Mit tehetünk akkor, ha a félcsoportoknak csak azokat az azonosságait szeretnénk vizsgálni, ami minden félcsoportban teljesül? Tekinthetünk például egy tetszőleges X halmazt, s ennek a generátumát szeretnénk vizsgálni valamely művelettel (amellyel félcsoportot alkot). Azt szeretnénk, hogy ebben a félcsoportban csak olyan azonosság legyen igaz, ami azonosság az összes félcsoportban, és az összes ilyet bevegyük. Ez pont akkor történik meg, ha tetszőleges félcsoportot tekintve, és tetszőleges függvényt X-ből a másik félcsoport tartóhalmazába, ennek a függvények egyértelmű kiterjesztése van mint a generátumok közötti homomorfizmus, ahol az X-beli elemek képe ugyanaz marad, mint az eredeti függvénynél. Ezzel leírtuk azt az X tartóhalmazából álló félcsoportot, amelyben minden más azonosság teljesül, ami egyéb félcsoportokban is, hiszen a homomorfizmus mindig tartja az azonosságokat. Ekkor fogjuk az X és a megadott művelet által generált félcsoportot szabad félcsoportnak hívni.

Egy ekvivalens definíció

A szabad félcsoportoknak van egy fontos tulajdonsága, nevezetesen, hogy a legszűkebb generátorhalmazából egyértelműen állnak elő elemei mint szorzatok (zárójelezéstől eltekintve). Az olyan generátorrendszert, amelyből az adott félcsoport elmei egyértelműen állnak elő, szabad generátoroknak nevezzük. Egy S szabad félcsoportra pedig igaz, hogy van szabad generátora. E tétel bizonyítás konstruktív módon történhet, azaz megadjuk konkrétan a szabad félcsoportot a szabad generátorával. A szabad félcsoportunk pongyolán megfogalmazva nem lesz más, mint a stringek, azaz betűsorozatok az egymás után írás műveletével, ahol a betűk a generátor elemei. Szemléletesen világosan látszik, hogy egy-egy betűsorozat (szó) egyértelműen áll elő mint a betűk egymásutánja, hiszen például azt a szót, hogy alma, csak egyféleképp tudom leírni (magyar nyelven). Ez pontosan definiálható, és a tétel indukcióval bizonyítható; tulajdonképpen egy n hosszú stringet egy n tagból álló direkt szorzatként értelmezünk elölről hátulra zárójelezve, azaz $(\ldots (a_{1},a_{2}),a_{3}),\ldots ),a_{n})$ formában.

Sokszor ezt a tulajdonságot szokták a szabad félcsoportok definíciójaként ismertetni, a fenti definíciót pedig tételként vezetik le. Lényegi megszorítást egyik sem jelent, gyakorlati alkalmazásokhoz utóbbi, elméleti vizsgálódásokhoz előbbi definíció kényelmesebb.

Felhasználása

Elméleti területen a félcsoportok vizsgálata, gyakorlati felhasználása a kódoláselméletben a betűnkénti kódolásoknál.