Grupoid
![]() | Ez a szócikk az algebrai struktúráról szól. Hasonló címmel lásd még: Grupoid (univerzális algebra). |
Az algebrában grupoid[1][m 1] – más néven magma[m 2] – 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.[2]
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.
Megjegyzések
- ↑ A grupoidokat egyes szerzők néha monoidoknak is nevezték, újabban azonban ezt a megnevezést inkább csak az úgynevezett egységelemes asszociatív grupoidra alkalmazzák.
- ↑ A bourbakisták a „magma” terminust vezették be eredetileg a grupoidokra. A „grupoid” név talán az angol „group-oid”, azaz „csoport-szerű” kifejezésből ered, és valószínűleg arra utal, hogy a grupoidok „olyanok, mint a csoportok (csak jóval kevesebbet tudnak)”. A csoport nevű matematikai struktúra valóban a grupoid egy specializációja. Egyébként a grupoid nem csak a csoportok, hanem az összes egyműveletes struktúra primitív „prototípusát” is jelenti, de az egyműveletes struktúrák közül a csoport a legfontosabb és – úgy látszik – „legmagasabbrendűnek” tartott (és ezt fedezték fel elsőként az ilyen struktúrák között): a többi fontos egyműveletes struktúra (félcsoport, kvázicsoport) is a csoportról lett elkeresztelve.
Hivatkozások
Források
- Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged (1994)
- grupoid Archiválva 2008. július 9-i dátummal a Wayback Machine-ben a PlanetMath-on.
Kapcsolódó szócikkek
- Szabad grupoid
- Abel-csoport
Matematikaportál • összefoglaló, színes tartalomajánló lap