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.

Formálisan a grupoid egy ${\displaystyle G=\left(U,*\right)}$ pár, ahol ${\displaystyle U}$ tetszőleges halmaz, ${\displaystyle *:U\times U\mapsto U}$ pedig egy kétváltozós művelet.

Általában az ${\displaystyle *(a,b)\in U}$ elemet infix jelölésmóddal, ${\displaystyle a*b}$ módon jelöljük.

A ${\displaystyle *}$ műveletet sokszor ${\displaystyle +}$ vagy ${\displaystyle \times }$ 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 ${\displaystyle x,y\in U}$ elemekre ${\displaystyle x*y=y*x}$), a másodikat pedig, ha asszociatív (tetszőleges ${\displaystyle x,y,z\in U}$ elemekre ${\displaystyle (x*y)*z=x*(y*z)}$).

• 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 ${\displaystyle n^{n^{2}}}$ darab van.

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 ${\displaystyle \mathbb {R} _{0}^{+}}$ halmaza a számtani közép képzésének műveletére (${\displaystyle a*b:={\frac {a+b}{2}}}$) kommutatív (${\displaystyle {\frac {a+b}{2}}={\frac {b+a}{2}}}$), de nem asszociatív (${\displaystyle (1*2)*3={\frac {{\frac {1+2}{2}}+3}{2}}={\frac {9}{4}}\neq {\frac {7}{4}}={\frac {1+{\frac {2+3}{2}}}{2}}=1*(2*3)}$).
  • Fordítva, egy asszociatív grupoid sem mindig kommutatív, például az összes ${\displaystyle f:\mathbb {R} \mapsto \mathbb {R} }$ 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 ${\displaystyle f:x\mapsto 2x}$ és ${\displaystyle g:x\mapsto x^{2}}$ 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) = 4x², de gf[x] = f(g(x)) = 2(xx) = 2x², azaz ${\displaystyle fg[x]\neq gf[x]}$).
  • 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: ${\displaystyle \left(\mathbb {N} ,+\right)}$ 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).

• 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]

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

• Az egész számok ${\displaystyle \mathbb {Z} }$ 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 ${\displaystyle A\Delta B:=(A-B)\cup (B-A)}$ műveletét vesszük (amely nem idempotens); mellesleg ez a grupoid unipotens, ha ${\displaystyle X,Y\subseteq U}$, akkor ${\displaystyle X\Delta X=Y\Delta Y(=\emptyset )}$;

• 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 ${\displaystyle \emptyset }$ ü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 ${\displaystyle \emptyset }$ üres halmaz; zéruselem viszont általában nincs;
• neutrális elemes grupoid továbbá a valós számok ${\displaystyle \mathbb {R} }$ 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 ${\displaystyle \mathbb {R} }$ 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.

• 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 ${\displaystyle \mathbb {Z} }$ halmaza a legnagyobb közös osztó, vagy akár a legkisebb közös többszörös műveletével;
• ${\displaystyle \mathbb {R} }$ 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.

• 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 ${\displaystyle \mathbb {Z} }$ halmaza a legnagyobb közös osztó, vagy akár a legkisebb közös többszörös műveletével;
• ${\displaystyle \mathbb {R} }$ 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 ${\displaystyle R^{+}}$ 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.

• az ${\displaystyle \left(\mathbb {N} ,+\right)}$ 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.
• ${\displaystyle \left(\mathbb {R} ,+\right)}$ kommutatív csoport (Abel-csoport);
• ${\displaystyle \left(\mathbb {R} -{0},\cdot \right)}$ 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;

Legyen adott két (A,*) és (B,×) grupoid. Ha ${\displaystyle A\subseteq B}$, é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.

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:

• ${\displaystyle \left(\mathbb {Z} ,+\right)}$-nak ${\displaystyle \left(\mathbb {Z} ,+\right)}$-ba, önmagába való homomorfizmusa bármely ${\displaystyle m\in \mathbb {N} ^{+}}$ esetén az ${\displaystyle f:\mathbb {Z} \mapsto \mathbb {N} ;f(n)=a\ mod\ m}$ 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.
• ${\displaystyle \left(\mathbb {R} ,+\right)}$ és ${\displaystyle \left(\mathbb {R} _{0}^{+},\cdot \right)}$, sőt köztük végtelen sok homomorfizmus található, minden ${\displaystyle a\in \mathbb {R} ^{+}-{1}}$ -re ugyanis a ${\displaystyle x\mapsto log_{a}(x)}$ logaritmusfüggvény homomorfizmus.
• ${\displaystyle \left(\mathbb {C} ,\cdot \right)}$ és ${\displaystyle \left(\mathbb {R} _{0}^{+},\cdot \right)}$ is homomorfak; például a komplex szám abszolút értékének képzése egy homomorfizmus, hisz ${\displaystyle \left|z_{1}\cdot z_{2}\right|=\left|z_{1}\right|\cdot \left|z_{2}\right|}$
• 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).

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.

• 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.

• Szabad grupoid
• Abel-csoport