Grupoid

Az algebrában grupoid – más néven magma – alatt egy olyan egyműveletes algebrai struktúrát értünk, amelyben az egyetlen definiált művelet egy kétváltozós művelet.

A grupoid a lehető legáltalánosabb és legegyszerűbb algebraistruktúra-típus, amely még nem teljesen üres, jelentősége ebben nagyjából ki is merül.

Definíció 
Formálisan a grupoid egy  pár, ahol  tetszőleges halmaz,  pedig egy kétváltozós művelet.

Általában az  elemet infix jelölésmóddal,  módon jelöljük.

A  műveletet sokszor  vagy  szimbólummal jelöljük, az első jelölésmódot különösen akkor alkalmazzuk, ha a művelet kommutatív (tetszőleges  elemekre ), a másodikat pedig, ha asszociatív (tetszőleges  elemekre ).
 Az első esetben a grupoid összeadó vagy additív írásmódjáról beszélünk, és a műveletet összeadásnak nevezzük,
 a második esetben a grupoid szorzó vagy multiplikatív írásmódjáról, és a művelet neve szorzás.

Az (U, *) grupoid U tartóhalmazának vagy univerzumának számosságát (elemeinek számát) a grupoid rendjének nevezzük. Kiszámolható, hogy véges, n-edrendű grupoid (az izomorf példányokat egynek számítva) pontosan  darab van.

Speciális grupoidok

Fontosabb típusok 

A grupoid fogalmának önmagában nem sok értelme van (külön róluk szóló jelentős cikkek, kutatási irányok stb. nem igazán lelhetőek fel). Különféle, kevésbé általános alesetei azonban nagyon fontosak:

Speciális, kitüntetett elemekkel bíró grupoidféleségek:

 neutrális elemes vagy unitér grupoidban van egy neutrális elem, azaz olyan U-beli n elem, melyre tetszőleges U-beli x esetén x*n = n*x = x. Belátható, hogy legfeljebb egy neutrális elem létezik egy grupoidban, ezt összeadó írásmód esetén nullelemnek, szorzó írásmód esetén egységelemnek nevezzük;
 zéruselemes grupoidban van egy zéruselem, azaz olyan U-beli z elem, melyre tetszőleges U-beli x esetén x*z = z*x = z. Belátható, hogy legfeljebb egy zéruselem létezik egy grupoidban.

Azonosságokkal definiált grupoidosztályok:

 idempotens, ha tetszőleges U-beli x elemre x*x = x;
 kommutatív egy grupoid, ha * kommutatív művelet, azaz tetszőleges U-beli x, y elemekre x*y = y*x;
 asszociatív egy grupoid, ha * asszociatív művelet, azaz tetszőleges U-beli x, y, z elemekre (x*y)*z = x*(y*z); az asszociatív grupoidokat félcsoportnak szokás nevezni.
 monoidnak a neutrális elemes asszociatív grupoidokat, azaz a neutrális elemes félcsoportokat nevezzük.
 reguláris grupoid vagy egyszerűsíthető grupoid: tetszőleges U-beli x, y, z elemekre x*y = x*z esetén x zéruselem vagy y = z (balregularitás); és x*y = z*y esetén y zéruselem vagy x = z (jobbregularitás).
 invertálható a grupoid – más néven kvázicsoport – ha tetszőleges U\{0}-beli x, y elemekre (0 a zéruselem, ha van) az ?*x = y és az x*? = y egyenleteknek (? az „ismeretlen”) is van egy és csak egy megoldásuk, azaz egyértelműen vannak olyan a, b U-beli elemek, hogy a*x = y és x*b = y teljesüljön. Megjegyzés: fel szoktuk tenni még azt is, hogy U nem üres.
 hurok: a neutrális elemes kvázicsoportokat nevezzük így – azaz olyan grupoidokat, melyek egyszerre monoidok és kvázicsoportok. Ha egy kvázicsoport asszociatív (azaz félcsoport is, tehát csoport is), akkor automatikusan neutrális elemes.
 Csoporton olyan grupoidot értünk, mely egyszerre monoid, félcsoport és kvázicsoport; azaz a * műveletre nézve van neutrális elem, továbbá a művelet asszociatív és invertálható. Be lehet látni (ld. a példákat), hogy elegendő csak azt megkövetelni, hogy fél- és kvázicsoport legyen (azaz * asszociativitását és invertálhatóságát), mert az invertálhatóságból és az asszociativitásból együtt a neutrális elem léte következik.
 Megjegyzések:
 Egy kommutatív grupoid nem szükségszerűen asszociatív, például a nemnegatív számok  halmaza a számtani közép képzésének műveletére () kommutatív (), de nem asszociatív ().
 Fordítva, egy asszociatív grupoid sem mindig kommutatív, például az összes  valós-valós függvény a kompozíció műveletével egy asszociatív grupoid (a függvénykompozíció mindig asszociatív, bármilyen halmaz felett), de az  és  függvények (a kétszerezés és a négyzetre emelés) nem cserélhetőek fel (fg[x] = g(f(x)) = (2x)(2x) = 4x2, de gf[x] = f(g(x)) = 2(xx) = 2x2, azaz ).
 Egy invertálható grupoid, azaz egy kvázicsoport mindig reguláris. Biztosan balreguláris: ha ab=ac=d, akkor d=ab és d=ac. Az invertálhatóság miatt ekkor a d=a*? egyenlet két b,c megoldása egyenlő (hiszen egyértelműen kell hogy létezzenek a megoldások), azaz b=c. Hasonlóan belátható, hogy * jobbreguláris; összességében tehát reguláris.
 Fordítva azonban nem igaz:  reguláris grupoid ugyan (a+z = b+z esetén a = b); de nem invertálható (az a+x = b egyenletnek ugyanis nem mindig van megoldása, csak ha a ≤ b – pontosan ez a ≤ reláció definíciója).

Továbbiak 

 balról neutrális elemes grupoid: van olyan b ∈ U, hogy b*x = x (bármely x ∈ U-ra);
 jobbról neutrális elemes grupoid: van olyan j ∈ U, hogy x*j = x (bármely x ∈ U-ra)

Egy grupoid akkor és csak akkor neutrális elemes, ha balról is és jobbról is az (nyilvánvaló, hogy ha van neutrális elem, akkor az bal- és jobbneutrális egyszerre, fordítva pedig ha van bal- és jobbneutrális elem, könnyű belátni, hogy egyenlőek, így neutrálisak is – ld. még itt).

 balról reguláris (vagy balról egyszerűsíthető) egy grupoid, ha * balról reguláris (-egyszerűsíthető) művelet, azaz tetszőleges U-beli x,y,z elemekre x*y = x*z esetén x zéruselem vagy y = z;
 jobbról reguláris (vagy jobbról egyszerűsíthető) egy grupoid, ha * jobbról reguláris ( -egyszerűsíthető) művelet, azaz tetszőleges U-beli x,y,z elemekre x*y = z*y esetén y zéruselem vagy x = z (jobbregularitás).

Természetesen a grupoid akkor és csak akkor reguláris, ha balról és jobbról is reguláris.

 unipotens grupoid: érvényes x*x = y*y tetszőleges x,'y ∈ U -ra;
 zérópotens grupoid: érvényes (x*x)*y = x*(y*y) = x*x;
 mediális grupoid: érvényes (x*y)*(u*z) = (x*u)*(y*z) tetszőleges x,'y,'u,'z U-beli elemekre;
 balról szemimediális grupoid: érvényes az (x*x) * (y*z) = (x*y) * (x*z) azonosság;
 jobbról szemimediális grupoid: érvényes az (y*z) * (x*x) = (y*x) * (z*x) azonosság,
 szemimediális grupoid: balról és jobbról is szemimediális;
 balról öndisztributív: érvényes az (x)*(y*z) = (x*y) * (x*z) azonosság,
 jobbról öndisztributív: érvényes az (y*z)*x = (y*x)*(z*x),
 auto- (ön-) disztributív grupoid: balról és jobbról is disztributív.
 alternatív grupoid: érvényesek az (x*x) * y = x * (x*y) és az x * (y*y) = (x*y) * y azonosságok,
 Steiner-kvázicsoport: Idempotens, kommutatív grupoid az x(xy)=y azonossággal.

Példák 

Mivel gyakorlatilag bármilyen algebrai struktúra egyben grupoid is, példákat hozunk az egyes speciális grupoidokra:

Idempotens grupoidok 
 Az egész számok  halmaza vagy a nemnulla egész számok halmaza a legnagyobb közös osztó, vagy akár a legkisebb közös többszörös műveletével (ez tehát négy grupoid);
 egy U halmaz hatványhalmaza az unió, ill. a metszet műveletével;
 … ellenpélda, ha mondjuk a szimmetrikus differencia  műveletét vesszük (amely nem idempotens); mellesleg ez a grupoid unipotens, ha , akkor ;

Neutrális elemes és zéruselemes grupoidok 
 Az egész számok a legnagyobb közös osztó műveletével, neutrális elem a 0, zéruselem az 1.
 Az egész számok a legkisebb közös többszörös műveletével, neutrális elem az 1, zéruselem a 0.
 egy U halmaz hatványhalmaza az unió műveletével, a neutrális elem az  üres halmaz; a zéruselem maga az U;
 egy U halmaz hatványhalmaza a metszet műveletével, a neutrális elem maga az U; a zéruselem az üres halmaz;
 Egy U halmaz hatványhalmaza a szimmetrikus differencia műveletével, neutrális elem az  üres halmaz; zéruselem viszont általában nincs;
 neutrális elemes grupoid továbbá a valós számok  halmaza az összeadás műveletével, a neutrális elem a nulla, zéruselem nincs; ez már nem idempotens;
 … továbbá szintén  a szorzás műveletével, a neutrális elem ekkor az 1; zéruselem a 0; ez sem idempotens.

Lásd még a neutrális elem és zéruselem cikkeket.

Kommutatív grupoidok 
 egy U halmaz hatványhalmaza akár az unió, akár a metszet, akár a szimmetrikus differencia műveletével;
 Az egész számok  halmaza a legnagyobb közös osztó, vagy akár a legkisebb közös többszörös műveletével;
  az összeadás vagy a szorzás műveletével,
 A legfontosabb ellenpéldák: Egy adott A halmazt önmagára leképező függvények halmaza a függvénykompozíció (összetettfüggvény-képzés) műveletével; amely nem kommutatív (de asszociatív), vagy egy halmaz hatványhalmaza a különbségképzés műveletével, vagy a valós számok halmaza a kivonás műveletével; valamely test feletti n×n-es mátrixok halmaza a mátrixszorzás műveletével.

Asszociatív grupoidok (félcsoportok) és monoidok 
 egy U halmaz hatványhalmaza akár az unió, akár a metszet, akár a szimmetrikus differencia műveletével; mindegyik kommutatív, idempotens és neutrális elemes; azaz mind monoid is;
 Az egész számok  halmaza a legnagyobb közös osztó, vagy akár a legkisebb közös többszörös műveletével;
  az összeadás vagy a szorzás műveletével,
 Egy adott A halmazt önmagára leképező függvények halmaza a függvénykompozíció (összetettfüggvény-képzés) műveletével; ez asszociatív és neutrális elemes, de nem kommutatív grupoid;
 valamely test feletti n×n-es mátrixok halmaza a mátrixszorzás műveletével, amely zéruselemes és neutrális elemes félcsoport (zéruselemes monoid);
 A neutrális elem szócikk 10. példája olyan (G, *b) és (G, *j) grupoidokra ad példát, melyek könnyen beláthatóan asszociatívak, de nem neutrális elemesek. Például a ×=*b műveletre nézve minden elem valódi bal oldali neutrális elem (bal oldali neutrális, de nem kétoldali neutrális), ezért neutrális elem nincs, tehát × nem monoid-művelet, de asszociatív, ugyanis (x×y)×z = y×z = z, és x×(y×z) = x×z=z, tehát az asszociativitás érvényes.
 Sokkal fontosabb ellenpélda nem-neutrális elemes félcsoportra: legyen a tartóhalmaz a pozitív valós számok  halmaza, a művelet pedig a következő: x ∨ y = max{x, y}. Ez asszociatív művelet, de sem bal oldali, sem jobb oldali neutrális eleme nincs (ugyanis ez azt jelentené, hogy lenne egy pozitív szám, amely az összes többinél kisebb, illetve egy, amelyik nagyobb).
 További példákat a félcsoportokról szóló cikkben lehet találni; a legfontosabb ellenpéldák pedig: az egész számok halmaza a kivonással, ez nem idempotens (ámde unipotens), jobb oldali neutrális elemes, de nem neutrális elemes, nem zéruselemes, nem kommutatív és nem asszociatív kvázicsoport.

Reguláris és invertálható grupoidok, hurkok és csoportok 
 az  neutrális elemes kommutatív asszociatív grupoid (kommutatív félcsoport) reguláris, de nem invertálható.
 Egy A halmazt önmagára képező szürjektív függvények (a halmaz minden eleme előáll bármelyik függvény valamely helyen felvett értékeként, azaz bármelyik f függvényre R(f)=A ) neutrális elemes, általában nem kommutatív (de asszociatív) félcsoportot alkotnak. Ez a grupoid beláthatóan reguláris, noha általában nem invertálható.
 Egy halmazt önmagára képező kölcsönösen egyértelmű, bijektív függvények (permutációk) halmaza a függvénykompozícióval invertálható (tehát reguláris) grupoid az identitás függvénnyel mint neutrális elemmel – tehát hurok. Mivel a kompozíció művelete asszociatív is, ezért csoport is. Ez egy nem-kommutatív csoport.
  kommutatív csoport (Abel-csoport);
  a valós számok szorzásával kommutatív csoport;
 További példák a kvázicsoport, a hurok és a csoport cikkben találhatóak: ellenpéldák egy halmaz hatványhalmaza az unió, a metszet halmazműveletekkel;

Kapcsolódó fogalmak

Részgrupoid 

Legyen adott két (A,*) és (B,×) grupoid. Ha , és a * művelet a × művelet leszűkítése A-ra (* = ×|A), akkor az első grupoidot a második részgrupoidjának nevezzük. Azt is mondhatjuk, a részgrupoidot a grupouid egy olyan részhalmazán lehet értelmezni, mely szintén grupoid a nagyobb grupoidon értelmezett művelettel ellátva.

Homomorfia 

Két (A,*) és (B,×) grupoid homomorf, ha létezik köztük egy művelettartó leképezés, azaz olyan f:A→B függvény, melyre érvényes tetszőleges a,b ∈ A -ra f(a*b) = f(a)×f(b). Ez esetben a grupoidokat homomorfnak, magát a függvényt homomorfizmusnak nevezzük. A homomorfia egy előrendezési reláció grupoidok egy tetszőleges halmaza felett. Ugyanakkor általában nem szimmetrikus (így nem ekvivalenciareláció) és nem is antiszimmetrikus (így nem rendezési reláció).

Néhány példa homomorf grupoidpárokra:

 -nak -ba, önmagába való homomorfizmusa bármely  esetén az  függvény (azaz amely egy számhoz az m számmal való osztási maradékát rendeli), hiszen f(a+b)= (a+b) mod m = (a mod m + b mod m) = f(a)+f(b) érvényes, két szám adott m-mel való osztási maradéka a számok maradékainak összege.
  és , sőt köztük végtelen sok homomorfizmus található, minden  -re ugyanis a  logaritmusfüggvény homomorfizmus.
  és  is homomorfak; például a komplex szám abszolút értékének képzése egy homomorfizmus, hisz 
 Legyen mindkét grupoid univerzuma egy A halmaz P(A) hatványhalmaza, és az egyikben a művelet a metszet, a másikban az egyesítés. Ez a két grupoid is homomorf. A homomorfizmus a komplementerképzés művelete (a DeMorgan-törvény biztosítja, hogy ez valóban homomorfizmus).

Izomorfia 

Két homomorf grupoid izomorf, ha van bijektív homomorfizmusuk, azaz izomorfizmusuk. A grupoidok izomorfiája szemléletesen azt jelenti, hogy tulajdonképpen (bár nem szó szerint) „ugyanarról” a grupoidról van szó, csak másféleképp jelöltük az elemeket. Az izomorfia ekvivalenciareláció grupoidok tetszőleges halmaza felett.

Hivatkozások

Megjegyzések

Jegyzetek 

Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged (1994)

Kapcsolódó szócikkek 
 Szabad grupoid
 Abel-csoport

Források
grupoid  a PlanetMath-on.

Algebrai struktúrák