Odwrotna półgrupa

W teorii grup odwrotna półgrupa (czasami nazywana półgrupą odwrotną ) S jest półgrupą , w której każdy element x w S ma unikalną odwrotność y w S w tym sensie, że x = xyx i y = yxy , tj. regularna półgrupa , w której każdy element ma unikalną odwrotność. Odwrotne półgrupy pojawiają się w różnych kontekstach; na przykład mogą być zatrudnieni w badaniu częściowe symetrie .

(Konwencja zastosowana w tym artykule będzie polegała na zapisywaniu funkcji po prawej stronie jej argumentu, np. xf zamiast f(x) , i składaniu funkcji od lewej do prawej - konwencja często obserwowana w teorii półgrup).

Pochodzenie

Odwrotne półgrupy zostały wprowadzone niezależnie przez Wiktora Władimirowicza Wagnera w Związku Radzieckim w 1952 r. I przez Gordona Prestona w Wielkiej Brytanii w 1954 r. Obaj autorzy doszli do odwrotnych półgrup poprzez badanie bijekcji cząstkowych zbioru : częściowa transformacja α zbioru X jest funkcją od A do B , gdzie A i B są podzbiorami X . Niech α i β będą częściowymi przekształceniami zbioru X ; α i β można złożyć (od lewej do prawej) na największej domenie , na której „ma sens” ich komponowanie:

gdzie α −1 oznacza przedobraz pod α . Transformacje częściowe były już badane w kontekście pseudogrup . Jednak dopiero Wagner jako pierwszy zauważył, że składanie przekształceń cząstkowych jest szczególnym przypadkiem składania relacji binarnych . Uznał również, że dziedziną złożenia dwóch przekształceń cząstkowych może być zbiór pusty , dlatego wprowadził przekształcenie puste wziąć to pod uwagę. Po dodaniu tej pustej transformacji składanie częściowych transformacji zbioru staje się wszędzie definiowaną asocjacyjną operacją binarną . W ramach kompozycji zbiór wszystkich częściowych przekształceń -jeden zbioru tworzy odwrotną półgrupę, zwaną symetryczną odwrotną półgrupą ( lub monoidem) na X. , z odwrotnością funkcjonalnej odwrotności zdefiniowanej od obrazu do domeny (równoważnie odwrotna relacja ). Jest to „archetypowa” odwrotna półgrupa, w taki sam sposób, w jaki grupa symetryczna jest grupą archetypową . Na przykład, tak jak każda grupa może być osadzona w grupie symetrycznej , tak każda odwrotna półgrupa może być osadzona w symetrycznej odwrotnej półgrupie (patrz § Homomorfizmy i reprezentacje odwrotnych półgrup poniżej).

Podstawy

Odwrotność elementu x odwrotnej półgrupy S jest zwykle zapisywana jako x −1 . Odwrotności w odwrotnej półgrupie mają wiele takich samych właściwości jak odwrotności w grupie , na przykład ( ab ) −1 = b −1 a −1 . W monoidzie odwrotnym xx −1 i x −1 x niekoniecznie równe tożsamości, ale oba są idempotentne . Odwrotny monoid S , w którym xx −1 = 1 = x −1 x , dla wszystkich x w S ( jednomocny monoid odwrotny), jest oczywiście grupą .

Istnieje wiele równoważnych charakterystyk odwrotnej półgrupy S :

  • Każdy element S ma unikalną odwrotność w powyższym sensie.
  • Każdy element S ma co najmniej jedną odwrotność ( S jest regularną półgrupą ) i idempotenty dojeżdżają (to znaczy idempotenty S tworzą półsieć ).
  • Każda klasa i każda klasa zawiera dokładnie jeden idempotent , gdzie i { \ to dwie relacje Greena .

Idempotent w klasie s to s -1 s , podczas gdy idempotent w klasie s to ss - } - 1 . Istnieje zatem prosta charakterystyka relacji Greena w odwrotnej półgrupie:

O ile nie zaznaczono inaczej, E(S) będzie oznaczać półkratę idempotentów odwrotnej półgrupy S .

Przykłady odwrotnych półgrup

Przykład tabliczki mnożenia. Jest asocjacyjny i każdy element ma swoją odwrotność zgodnie z aba = a, bab = b. Nie ma tożsamości i nie jest przemienna.

Odwrotna półgrupa
& A B C D mi
A A A A A A
B A B C A A
C A A A B C
D A D mi A A
mi A A A D mi

Naturalny porządek częściowy

Odwrotna półgrupa S posiada naturalną relację częściowego rzędu ≤ (czasami oznaczaną przez ω), która jest zdefiniowana następująco:

dla pewnego idempotentnego e w S . równoważnie,

dla jakiegoś (na ogół innego) idempotentnego f w S . W rzeczywistości e można przyjąć jako aa −1 , a f jako a −1 a .

Naturalny porządek częściowy jest zgodny zarówno z mnożeniem, jak i inwersją, to znaczy

I

W grupie ten częściowy porządek po prostu sprowadza się do równości, ponieważ tożsamość jest jedynym idempotentnym . W symetrycznej odwrotnej półgrupie porządek częściowy sprowadza się do ograniczenia odwzorowań, tj. α ≤ β wtedy i tylko wtedy, gdy domena α jest zawarta w dziedzinie β i x α = x β, dla wszystkich x w domenie z α.

Naturalny porządek częściowy na odwrotnej półgrupie oddziałuje z relacjami Greena w następujący sposób: jeśli s t i s t , to s = t . Podobnie, jeśli t s .

Na E(S) naturalny porządek częściowy przyjmuje postać:

tak więc, ponieważ idempotenty tworzą półsieć w operacji iloczynu, iloczyny na E (S) dają najmniejsze górne granice w odniesieniu do ≤.

Jeśli E(S) jest skończony i tworzy łańcuch (tj. E(S) jest całkowicie uporządkowany przez ≤), to S jest sumą grup . Jeśli E(S) jest nieskończonym łańcuchem , to analogiczny wynik można uzyskać przy dodatkowych hipotezach dotyczących S i E(S).

Homomorfizmy i reprezentacje odwrotnych półgrup

Homomorfizm (lub morfizm ) odwrotnych półgrup definiuje się dokładnie tak samo, jak dla każdej innej półgrupy: dla odwrotnych półgrup S i T funkcja θ od S do T jest morfizmem, jeśli ( ) ( ) = ( st ) θ , dla wszystkich s , t w S . Definicję morfizmu odwrotnych półgrup można rozszerzyć, włączając warunek ( ) −1 = s −1 θ , jednak nie ma takiej potrzeby, gdyż właściwość ta wynika z powyższej definicji poprzez następujące twierdzenie:

Twierdzenie. Homomorficzny obraz odwrotnej półgrupy jest odwrotną półgrupą; odwrotność elementu jest zawsze odwzorowywana na odwrotność obrazu tego elementu.

Jednym z najwcześniejszych wyników udowodnionych na temat odwrotnych półgrup było twierdzenie Wagnera – Prestona , które jest analogiem twierdzenia Cayleya dla grup :

Twierdzenie Wagnera-Prestona. Jeśli S jest odwrotną półgrupą, to funkcja , dana przez S do ja

dom ( a φ) = Sa −1 i x ( a φ) = xa

jest wierną reprezentacją S. _ _

Zatem dowolna odwrotna półgrupa może być osadzona w symetrycznej odwrotnej półgrupie iz obrazem zamkniętym w ramach operacji odwrotnej na bijekcjach cząstkowych. I odwrotnie, każda podgrupa symetrycznej odwrotnej półgrupy zamkniętej w ramach operacji odwrotnej jest półgrupą odwrotną. Stąd półgrupa S jest izomorficzna z podgrupą symetrycznej odwrotnej półgrupy zamkniętej pod odwrotnościami wtedy i tylko wtedy, gdy S jest odwrotną półgrupą.

Kongruencje na odwrotnych półgrupach

Kongruencje są definiowane na odwrotnych półgrupach dokładnie w taki sam sposób, jak w przypadku każdej innej półgrupy: kongruencja ρ jest relacją równoważności zgodną z mnożeniem półgrup, tj.

Szczególnie interesująca jest relacja , zdefiniowana na odwrotnej półgrupie S przez

istnieje za z

Można wykazać, że σ jest kongruencją iw rzeczywistości jest to kongruencja grupowa , co oznacza, że ​​półgrupa czynnikowa S / σ jest grupą. W zbiorze wszystkich kongruencji grupowych na półgrupie S element minimalny (dla porządku częściowego zdefiniowanego przez włączenie zbiorów) nie musi być elementem najmniejszym. W szczególnym przypadku, w którym S jest odwrotną półgrupą, σ jest najmniejszą kongruencją na S taką, że S / σ jest grupą, to znaczy, jeśli τ jest dowolną inną kongruencją na S z S / τ a grupą, wtedy σ zawiera się w τ . Kongruencja σ nazywana jest minimalną kongruencją grupową na S . Minimalna kongruencja grupowa może być wykorzystana do scharakteryzowania E -jednostkowych odwrotnych półgrup (patrz poniżej).

Kongruencja ρ na odwrotnej półgrupie S nazywana jest idempotentną czystą, jeśli

E -jednostkowe odwrotne półgrupy

, jest klasa E -jednostkowych odwrotnych półgrup: odwrotna półgrupa S (z półkratą E idempotentów ) jest E - unitarna , jeśli dla wszystkich e w E i wszystkich s w S ,

równoważnie,

Kolejna charakterystyka E -jednostkowej odwrotnej półgrupy S jest następująca: jeśli e jest w E i e s , dla niektórych s w S , to s jest w E .

Twierdzenie. Niech S będzie odwrotną półgrupą z półkratą E idempotentów i minimalną kongruencją grupy σ . Następnie następujące są równoważne:

  • S oznacza E -jednolitą;
  • σ jest idempotentnie czysty;
  • = σ ,

gdzie relacją zgodności na , zdefiniowaną przez

są idempotentne.

Twierdzenie McAlistera o pokryciu. Każda odwrotna półgrupa S ma pokrycie jednostkowe E; to znaczy istnieje idempotent oddzielający homomorfizm suriekcyjny od jakiejś E-jednolitej półgrupy T do S.

Centralnym punktem badania E -jednostkowych odwrotnych półgrup jest następująca konstrukcja. Niech będzie częściowo uporządkowanym zbiorem z uporządkowaniem ≤ i niech będzie podzbiorem z właściwościami, które

  • jest dolną półkratą , to znaczy każda para elementów w ma największą dolną granicę ZA B w (w odniesieniu do ≤);
  • jest ideałem rzędu X , czyli dla ZA , b w , jeśli A jest w B ZA to B jest w .

Niech G będzie grupą działającą na (po lewej) taką, że displaystyle

  • dla wszystkich g w G i wszystkich ZA , b w , gA = gB wtedy i tylko wtedy A = b ;
  • dla każdego g w G i każdego B istnieje A takim że gA = ;
  • dla wszystkich ZA , b w , ZA b wtedy i tylko wtedy gA gB ;
  • dla wszystkich sol , h w G i wszystkich ZA w , ( hA ) = ( gh ) ZA

potrójna ma następujące właściwości:

  • dla każdego X w istnieje g w G i A w że gA = X
  • dla g w sol , mają niepuste .

potrójna _ _ _ Trójka McAlistera służy do zdefiniowania następujących elementów:

razem z mnożeniem

.

Wtedy jest odwrotną półgrupą pod tym mnożeniem, gdzie ( ZA , g ) -1 = ( sol -1 ZA , sol -1 ). Jednym z głównych wyników badania E -jednostkowych odwrotnych półgrup jest P-Twierdzenie McAlistera :

Twierdzenie McAlistera o P. Niech będzie potrójną McAlister. Wtedy } ) } I odwrotnie, każda odwrotna półgrupa E jest izomorficzna z jedną tego typu.

F -odwrotne półgrupy

Mówimy, że odwrotna półgrupa jest F -odwrotna, jeśli każdy element ma nad sobą unikalny element maksymalny w naturalnym porządku częściowym, tj. każda klasa σ ma element maksymalny. Każda półgrupa odwrotna F jest monoidem jednostkowym E. Twierdzenie McAlistera o pokryciu zostało udoskonalone przez MV Lawsona do:

Twierdzenie. Każda odwrotna półgrupa ma F -odwrotne pokrycie.

P -twierdzenie McAlistera zostało również użyte do scharakteryzowania F -odwrotnych półgrup. Trójka McAlistera jest F -odwrotną półgrupą wtedy i tylko wtedy, gdy jest głównym ideałem i jest półkratą.

Dowolne odwrotne półgrupy

Konstrukcja podobna do wolnej grupy jest możliwa dla odwrotnych półgrup. Prezentację swobodnej odwrotnej półgrupy na zbiorze X można uzyskać, rozważając swobodną półgrupę z inwolucją , gdzie inwolucja polega na przyjęciu odwrotności, a następnie przyjęciu ilorazu przez kongruencję Vagnera

Problem tekstowy dla swobodnych odwrotnych półgrup jest znacznie bardziej skomplikowany niż dla wolnych grup. Słynny wynik w tej dziedzinie dzięki WD Munnowi, który wykazał, że elementy swobodnej odwrotnej półgrupy można naturalnie uznać za drzewa, znane jako drzewa Munna. Mnożenie w swobodnej odwrotnej półgrupie ma odpowiednika na drzewach Munna, które zasadniczo składa się z nakładających się wspólnych części drzew. (więcej szczegółów w Lawson 1998)

Każda swobodna odwrotna półgrupa jest F -odwrotna.

Związki z teorią kategorii

Powyższa kompozycja częściowych przekształceń zbioru daje początek symetrycznej odwrotnej półgrupie. Istnieje inny sposób komponowania przekształceń cząstkowych, który jest bardziej restrykcyjny niż zastosowany powyżej: dwie przekształcenia cząstkowe α i β są złożone wtedy i tylko wtedy, gdy obraz α jest równy domenie β ; w przeciwnym razie skład αβ jest nieokreślony. W ramach tej alternatywnej kompozycji zbiór wszystkich częściowych przekształceń jeden-jeden zbioru nie tworzy odwrotnej półgrupy, ale indukcyjną grupoidę w sensie teorii kategorii . Ten ścisły związek między odwrotnymi półgrupami a indukcyjnymi grupami jest zawarty w twierdzeniu Ehresmanna – Scheina – Nambooripada , które stwierdza, że ​​​​grupoidę indukcyjną można zawsze zbudować z odwrotnej półgrupy i odwrotnie. Mówiąc dokładniej, odwrotna półgrupa jest właśnie grupoidą w kategorii pozycji, która jest grupoidą etalną w odniesieniu do jej (podwójnej) topologii Aleksandrowa i której zestaw obiektów jest spotkaniem semilattyki.

Uogólnienia odwrotnych półgrup

Jak zauważono powyżej, odwrotną półgrupę S można zdefiniować za pomocą warunków (1) S jest regularną półgrupą i (2) idempotenty w S dojeżdżają; doprowadziło to do powstania dwóch odrębnych klas uogólnień odwrotnej półgrupy: półgrup, w których (1) zachodzi, ale (2) nie i odwrotnie.

Przykładami regularnych uogólnień odwrotnej półgrupy są:

Klasa uogólnionych odwrotnych półgrup jest przecięciem klasy lokalnie odwrotnych półgrup i klasy półgrup ortodoksyjnych .

Wśród nieregularnych uogólnień odwrotnej półgrupy są:

  • (Lewy, prawy, dwustronny) odpowiednie półgrupy.
  • (Lewy, prawy, dwustronny) obszerne półgrupy.
  • (Lewe, prawe, dwustronne) póładekwatne półgrupy.
  • Słabo (lewo, prawo, dwustronnie) obfite półgrupy.

Kategoria odwrotna

To pojęcie odwrotności można również łatwo uogólnić na kategorie . Kategoria odwrotna to po prostu kategoria, w której każdy morfizm f : X Y ma uogólnioną odwrotność g : Y X taką, że fgf = f i gfg = g . Kategoria odwrotna jest samodualna . Najlepszym przykładem jest kategoria zbiorów i bijekcji cząstkowych .

Kategorie odwrotne znalazły różne zastosowania w informatyce teoretycznej .

Zobacz też

Notatki

Dalsza lektura