Inverzne polugrupe

Podsjetimo se: polugrupa \((S,\,\cdot\,)\) je neprazni skup \(S\) s binarnom relacijom \(\cdot:S\times S\to S\),  koja je asocijativna: \(a(bc)=(ab)c\), za sve \(a,b,c\in S\).

 

Inverzna polugrupa \((S,\,\cdot\,)\) je polugrupa u kojoj za svaki \(a\in S\) postoji jedincati \(b\in S\) takav da je 

$$aba=a,\quad bab=b.$$

Primijetite da ne zahtijevamo postojanje jediničnog elementa \(e\). Svrha inverznih polugrupa je opis lokalnih simetrija, dok grupe opisuju globalne simetrije.

Element \(b\) zovemo inverznim elementom od \(a\) , uz oznaku \(a^{-1}:=b\).

Ako je \(S\) inverzni monoid (tj. inverzna polugrupa s jedinicom \(e\)), onda niti \(aa^{-1}\) niti \(a^{-1}a\) ne moraju biti jednaki jedinici.

Za element \(x\) u inverznoj polugrupi kažemo da je idempotentan ako je \(x^2=x\), gdje je \(x^2:=xx\)).

Lema. Ako je \(x\) idempotentan, onda je \(x^{-1}=x\).

Lema. Ako su \(x\) i \(y\) idempotentni, onda je \(xy\) idempotentan. Svaka dva idempotenta elementa komutiraju.

Propozicija. U inverznoj polugrupi su elementi \(aa^{-1}\) i \(a^{-1}a\) idempotentni.

Lema. U inverznoj polugrupi \(S\) (kao i u grupi) za svaka dva elementa \(x,y\in S\) vrijedi 

$$(xy)^{-1}=y^{-1}x^{-1},\quad (x^{-1})^{-1}=x.$$

 

Pogledajmo osnovni primjer u kontekstu funkcija na zadanom nepraznom skupu \(X\). Parcijalna transformacija skupa \(X\) je bilo koja bijektivna funkcija \(f:A\to B\), gdje su \(A\) i \(B\) neprazni podskupovi od \(X\). Radi bijektivnosti je onda jasno da skupovi \(A\) i \(B\) moraju imati isti broj elemenata, tj. \(|A|=|B|\). Djelovanje funkcije dogovorno gledamo s lijeva na desno, tj. kao \(x\mapsto xf\).

Ako su \(f\) i \(g\) dvije parcijalne transformacije od \(X\), onda možemo definirati kompoziciju \(fg\) (dogovorno s lijeva na desno, tj. najprije djelujemo s \(f\), a onda s \(g\): \(x\mapsto xfg\)), na najvećoj domeni  na kojoj kompozicija ima smisla:

$$\operatorname{dom}(fg)=(\operatorname{im}(f)\cap\operatorname{dom}(g))f^{-1}$$

Skup \(\operatorname{dom}(fg)\) može biti prazan (u slučaju kad je \(\operatorname{im}(f)\cap\operatorname{dom}(g)=\emptyset\)), pa radi toga uvodimo praznu transformaciju \(\emptyset_1\). Dodavanjem prazne transformacije (skupu svih parcijalnih transformacija), kompozicija bilo kojih dviju parcijalnih transformacija postaje dobro definirana.

Skup svih parcijalnih transformacija na \(X\) (zajedno s praznom transformacijom) time postaje asocijativna struktura (tj. polugrupa) s obzirom na kompoziciju kao binarnu operaciju. Pritom definiramo \(\emptyset_1f=\emptyset_1 f=\emptyset_1\) za sve parcijalne transformacije \(f\) na \(X\).

Skup \(\mathcal I_X\) svih injektivnih parcijalnih transformacij na \(X\) (zajedno s praznom transformacijom) je inverzna polugrupa s obzirom na kompoziciju. Pritom je \(\emptyset_1^{-1}=\emptyset_1\). Zapravo, to je i inverzni monoid, jer sadrži \(id_X\) kao svoj jedinični element.

Na sličan način kao kod grupa, uvodi se pojam homomorfizma i izomorfizma inverznih polugrupa.

Injektivni homomorfizam (tj. monomorfizam) inverznih polugrupa \(\alpha:S_1\to S_2\) možemo interpretirati kao ulaganje prve inverzne polugrupe u drugu. U tom slučaju pišemo da je \(S_1\le S_2\) (tj. \(S_1\) je podpolugrupa od \(S_1\)).

Teorem (analogon Cayleyeva teorema za grupe) Svaka inverzna polugrupa se može na prirodan način uložiti u neku inverznu polugrupu \(\mathcal I_X\).

Na taj način se proučavanje svih inverznih polugrupa svodi na proučavanje inverznih polugrupa parcijalnih transformacija.

Ako polugrupa \(S\) nema jedinicu (tj. \(S\) nije monoid), uvijek joj moguće dodati formalnu jedinicu \(e\notin S\), definirajući \(se=es=s\) za sve \(s\in S\cup\{e\}\). Onda je \(S\cup\{e\}\) monoid.

Ako polugrupa \(S\) ima jedinicu (tj. monoid je), stavljamo \(S^1=S\). Ako polugrupa \(S\) ne sadrži jedinicu (tj. nije monoid), definiramo \(S^1=S\cup\{e\}\) kao gore, pa je \(S^1\) opet monoid.

 

Primjer: parcijalne transformacije dvočlanog skupa

Neka je \(X=\{1,2\}\). Na tom dvočlanom skupu imamo sljedeće parcijalne transformacije:

  • \(\emptyset_1\) (prazna transformacija)
  • parcijalne transformacije među jednočlanim podskupovima od \(X\): $$a:\{1\}\to\{1\},\quad b:\{1\}\to\{2\},\quad c:\{2\}\to\{1\},\quad d:\{2\}\to\{2\},\quad$$
  • parcijalne transformacije na cijelom skupu \(X\): $$e=id_X=(1)(2),\quad f=(1,2),$$

pri čemu \((1,2)\) znači da \(1\mapsto 2\) i \(2\mapsto 1\).

Kao što vidimo, skup \(\mathcal I_X\) ima sedam elemenata, tj. postoji sedam parcijalnih transformacija dvočlanog skupa: $$\mathcal I_X=\{a,b,c,d,e,f\}.$$

Pogledajmo sada odgovarajuću \(7\times 7\) tablicu množenja (tj. komponiranja) u \(\mathcal I_X\):

 

\begin{array} {c|ccccccc} \circ & \emptyset_1 & a & b & c & d & e &  f\\ \hline \emptyset_1 & \emptyset_1 & \emptyset_1 & \emptyset_1 & \emptyset_1 & \emptyset_1 & \emptyset_1 &  \emptyset_1 \\ a & \emptyset_1 & a & b & \emptyset_1 & \emptyset_1 & a & \emptyset_1 \\ b & \emptyset_1 & \emptyset_1 & \emptyset_1 & a & b & b &  a \\ c & \emptyset_1 & c & d & \emptyset_1 & \emptyset_1 & c &  d \\ d & \emptyset_1 & \emptyset_1 & \emptyset_1 & c & d & d &  c \\ e & \emptyset_1 & a & b & c & d & e &  f \\ f & \emptyset_1 & c & d & a & b & f &  e  \end{array}

 

Jedinični elementi su \(a\), \(d\) i \(e\) (to su parcijalne identitete na odgovarajućim podskupovima). To su ujedno i jedini idempotentni elementi, kao što je vidljivo iz tablice: $$a^2=a,\quad d^2=d,\quad e^2=e.$$

Također, svaki od sedam elementa iz \(\mathcal I_X\) ima jednoznačno određen inverzni element:

\begin{gathered}\emptyset_1^{-1}=\emptyset_1\\ a^{-1}=a,\quad  b^{-1}=c,\quad  c^{-1}=b,\quad  d^{-1}=d\\ e^{-1}=e,\quad  e^{-1}=f.  \end{gathered}

Na primjer, $$bb^{-1}b=bcb=ab=b,\quad b^{-1}bb^{-1}=cbc=dc=c=b^{-1}$$

pa je doista \(b^{-1}=c\). Prema tome, \(\mathcal I_X\) je inverzna polugrupa transformacija. Zapravo, \(\mathcal I_X\) je inverzni monoid, jer sadrži jedinični element \(e\).

Primijetimo da je ova inverzna polugrupa nekomutativna. Na primjer, \(bc\neq cb\).

 

Broj elemenata inverzne polugrupe svih parcijalnih transformacija zadanog konačnog skupa \(X\)

 

Teorem. Pretpostavimo da skup \(X\) ima \(n\) elemenata, \(n\ge1\). Onda je $$|\mathcal I_X|=\sum_{k=0}^n\binom nk^2k!\,\,.$$

Dokaz. Neka su \(A\) i \(B\) \(k\)-člani podskupovi skupa \(X\), gdje je \(k\ge1\). Svih bijekcija \(f:A\to B\) ima ukupno \(k!\). Par \(k\)-članih podskupova \((A,B)\) možemo birati na \(\binom nk^2\) načina, jer skup \(A\) možemo birati na \(\binom nk\) načina, kao i skup \(B\) (ovdje koristimo Produktno pravilo iz kombinatorike). Slučaju \(k=0\) odgovara samo jedna prazna transformacija \(\emptyset_1\), a ona je ubrojena u \(\binom n0^20!=1\). Time je formula u teoremu dokazana. QED

 

Označimo li \(J_n:=J_{\{1,2,\dots,n\}}\), onda je jasno da je \(J_n\le J_{n+1}\) za svaki prirodan broj \(n\). Točnije, polugrupa \(J_n\) je na prirodan način uložena u \(J_{n+1}\), zahvaljujući inkluziji \(\{1,2,\dots,n\}\subset\{1,2,\dots,n+1\}\). Drugim riječima, parcijalne bijekcije na skupu \(\{1,2,\dots,n\}\) poistovjećujemo s odgovarajućim parcijalnim bijekcijama na skupu \(\{1,2,\dots,n+1\}\). Imamo $$J_1\le J_2\le J_3\le\dots \le J_n\le J_{n+1}\le\dots$$

Budući da je inverzna polugrupa \(J_2\) nekomutativna, onda su sve polugrupe \(J_n\), \(n\ge2\), nekomutativne.

Pogledajmo broj elemenata u \(J_n\) za nekoliko prvih \(n\)-ova, koji se dobivaju iz gornjeg Teorema, kao i odgovarajuću broj \(J_n\) svih umnožaka (kompozicija) u pripadajućoj Cayleyevoj tablici:

 

\begin{array} {c|ccc} n & |J_n| & |J_n|^2\\ \hline 1 & 2 & 4 \\ 2 & 7 & 49 \\ 3 & 34 & 1\,156 \\ 4 & 209 & 43\,681  \\ 5 &  1\,548 &  2\,396\,304 \\ 6 &  13\,327 & 177\,608\,929   \end{array}

 

 

Ideali u polugrupi (dakle i u inverznoj polugrupi)

Lijevi ideal \(I\) sadržan u polugrupi \(S\) je podskup \(I\subseteq S\) takav da je \(SI\subseteq I\). Slično, ako je \(IS\subseteq I\), onda kažemo da je \(I\) desni ideal. Naravno, svaki ideal je podpolugrupa od \(S\), jer imamo

  • grupoidnost: \(II\subseteq I\) (naime, čak je \(SI\subseteq I\) za lijevi ideal \(I\), odnosno \(IS\subseteq I\) za desni ideal)
  • asocijativnost množenja je naslijeđena iz \(S\).

Kažemo da je \(I\) ideal u polugrupi \(S\) ako je istodobno lijevi i desni ideal, tj. \(SI\subseteq I\) i \(IS\subseteq I\).

Trivijalan ideal u \(S\) je \(I=S\). Za ideal \(I\) kažemo da je pravi ideal u polugrupi \(S\), ako je \(I\ne S\), tj. \(I\) je pravi podskup polugrupe \(S\).

Presjek ideala polugrupe \(S\), ako je neprazan, je opet ideal u \(S\).

Za svaki element \(s\in S\) možemo definirati glavni lijevi ideal generiran s \(s\), kao presjek \(L(s)\) svih lijevih ideala koji sadrže \(s\). Lako je vidjeti da je \(L(s)=S^1s\).

Za svaki element \(s\in S\) možemo definirati glavni desni ideal generiran s \(s\), kao presjek \(R(s)\) svih desnih ideala koji sadrže \(s\). Lako je vidjeti da je \(R(s)=sS^1\).

Za svaki element \(s\in S\) možemo definirati glavni ideal generiran s \(s\), kao presjek \(J(s)\) svih ideala koji sadrže \(s\). Lako je vidjeti da je \(L(s)=S^1sS^1\).

 

Terminologija. Engleski termini: inverse semigroup (nešto općenitiji pojam je regular semigroup, u kojem se ne zahtijeva jednoznačnost inverza, nego samo njegovo postojanje). Francuski termin za inverznu polugrupu: demi-groupe inversif.

Početci teorije inverznih polugrupa. Pojam inverzne polugrupe uveo je Viktor V. Wagner 1952. g. u bivšem Sovjetskom Savezu. Nakon njega je 1952. taj je pojam ponovno otkrio Gordon Preston iz Velike Britanije.

 

Problem. Definirati polugrupe jorbova. Jesu li one inverzne polugrupe?

Problem (istraživački). Može li se svaka konačna inverzna polugrupa do na izomorfizam poistovjetiti s nekom inverznom polugrupom jorbova? Drugim riječima, pokriva li teorija jorbova teoriju konačnih inverznih polugrupa?

Može li se teorija konačnih inverznih polugrupa poistovjetiti s teorijom  polugrupa jorbova?

 

Izvori