Szabad félcsoport

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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

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

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.

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 ${\displaystyle (\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.

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.