Odwrotna półgrupa - Inverse semigroup
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 , czyli regularna półgrupa, w której każdy element ma unikalną odwrotność. Odwrotne półgrupy pojawiają się w różnych kontekstach; na przykład można je wykorzystać do badania symetrii częściowych .
(Konwencją przyjętą w tym artykule będzie zapis funkcji po prawej stronie jej argumentu, np. xf zamiast f(x) i łączenie funkcji od lewej do prawej — konwencja często obserwowana w teorii półgrup.)
Początki
Odwrotne półgrupy zostały wprowadzone samodzielnie przez Wiktor Władimirowicz Wagnera w ZSRR w 1952 roku, a przez Gordon Preston w Wielkiej Brytanii w roku 1954. Obaj autorzy przybyłych na odwrotnych półgrup poprzez badania częściowych bijections o zestawie : do częściowej transformacji alfa zestawu X jest funkcją od A do B , gdzie A i B są podzbiorami X . Niech α i β będą cząstkowymi transformacjami zbioru X ; α i β mogą być złożone (od lewej do prawej) na największej domenie, na której „ma sens” ich skomponowanie:
gdzie α -1 oznacza obraz wstępny pod α . Przekształcenia częściowe były już badane w kontekście pseudogrup . Jednak to Wagner jako pierwszy zauważył, że składanie przekształceń cząstkowych jest szczególnym przypadkiem składania relacji binarnych . Uznał też, że dziedziną składania dwóch przekształceń cząstkowych może być zbiór pusty , dlatego wprowadził transformację pustą, aby to uwzględnić. Po dodaniu tej pustej transformacji składanie częściowych transformacji zbioru staje się definiowaną wszędzie asocjacyjną operacją binarną . W tej kompozycji zbiór wszystkich częściowych przekształceń jeden-jeden zbioru X tworzy odwrotną półgrupę, zwaną symetryczną odwrotną półgrupą (lub monoidem) na X , z odwrotnością funkcjonalną odwrotnością określoną od obrazu do dziedziny (odpowiednik odwrotnej relacji ). Jest to „archetypowa” odwrócona półgrupa, podobnie jak grupa symetryczna jest grupą archetypową . Na przykład, tak jak każda grupa może być osadzona w grupie symetrycznej , 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 odwrotnym monoid , xx -1 i x -1 x niekoniecznie równe tożsamości, ale obie są idempotent . Odwrotny monoid S, w którym xx -1 = 1 = x -1 x , dla wszystkich x w S ( unipotentny odwrotny monoid), jest oczywiście grupą .
Istnieje szereg 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 jeden odwrotny ( S jest regularność ) i idempotents dojeżdża (to znaczy idempotents z S tworzą semilattice ).
- Każda -klasa i każda -klasa zawiera dokładnie jeden idempotent , gdzie i są dwiema relacjami Greena .
Idempotent w -class o s to s -1 s , podczas gdy idempotent w -class o 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ółsieć idempotentów odwrotnej półgrupy S .
Przykłady odwrotnych półgrup
- Bijekcje częściowe na zbiorze X tworzą odwrotną półgrupę w składzie.
- Każda grupa jest odwróconą półgrupą.
- Bicykliczny półgrupa jest odwrotne, z ( a , b ) -1 = ( b , ).
- Każda półsieć jest odwrócona.
- Brandt półgrupa jest odwrotna.
- Munn półgrupa jest odwrotna.
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 przemienny.
& | 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ę rzędu częściowego ≤ (czasami oznaczaną przez ω), która jest zdefiniowana następująco:
dla niektórych idempotentnych e w S . Równoważnie,
dla niektórych (na ogół różnych) idempotentnych f w S . W rzeczywistości, e może być uznany aa -1 i f być -1 .
Naturalny porządek częściowy jest zgodny zarówno z mnożeniem, jak i inwersją, to znaczy
oraz
W grupie ten częściowy porządek po prostu sprowadza się do równości, ponieważ tożsamość jest jedyną idempotentną . W symetrycznej półgrupie odwrotnej porządek częściowy sprowadza się do ograniczenia odwzorowań, tj. α ≤ β wtedy i tylko wtedy, gdy domena α jest zawarta w domenie β i x α = x β, dla wszystkich x w domenie α.
Naturalny porządek cząstkowy 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 s t .
Na E(S) naturalny porządek częściowy staje się:
tak, ponieważ idempotenty tworzą semisieć pod działaniem produktu, produkty na E (S) dają najmniejsze granice górne w odniesieniu do ≤.
Jeżeli E (Y) jest ograniczone i tworzy łańcuch (tj PL (S) jest uporządkowany przez ≤), a S jest związek z grup . Jeżeli E(S) jest nieskończonym łańcuchem , analogiczny wynik można uzyskać przy dodatkowych hipotezach dotyczących S i E(S).
Homomorfizmy i reprezentacje odwrotnych półgrup
Homomorfizm (lub morfizmem ) odwrotnych półgrup jest zdefiniowana w ten sam sposób, jak w przypadku innych półgrupa: inwersyjnej półgrup S i T , w funkcji θ z S na T jest morfizmem if ( sθ ) ( tθ ) = ( st ) θ , dla wszystkich s , t w S . Definicję morfizmu półgrup odwrotnych można rozszerzyć o warunek ( sθ ) −1 = s −1 θ , jednak nie ma takiej potrzeby, ponieważ własność ta wynika z powyższej definicji, poprzez następujące twierdzenie:
Twierdzenie. Homomorficzny obraz odwróconej półgrupy jest odwrotną półgrupą; odwrotność elementu jest zawsze mapowana na odwrotność obrazu tego elementu.
Jednym z najwcześniejszych wyników dowiedziono o odwrotnych półgrupach 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 φ od S do , dana przez
- dom ( a φ) = Sa -1 i x ( a φ) = xa
jest wierne przedstawienie z S .
Zatem dowolna odwrotna półgrupa może być osadzona w symetrycznej odwrotnej półgrupie iz obrazem zamkniętym w operacji odwrotnej na częściowych bijekcji. Odwrotnie, każda podpółgrupa symetrycznej odwrotnej półgrupy zamkniętej w operacji odwrotnej jest odwrotną półgrupą. Stąd półgrupa S jest izomorficzna z podpółgrupą symetrycznej półgrupy odwrotnej zamkniętej pod odwrotnościami wtedy i tylko wtedy, gdy S jest półgrupą odwrotną.
Kongruencje na odwrotnych półgrupach
Kongruencje definiuje się na odwrotnych półgrupach w dokładnie taki sam sposób, jak w przypadku każdej innej półgrupy: zgodność ρ jest relacją równoważności, która jest zgodna z mnożeniem półgrup, tj.
Szczególnie interesująca jest relacja , zdefiniowana na odwrotnej półgrupie S przez
- istnieje z
Można wykazać, że σ jest kongruencją, a w rzeczywistości jest kongruencją grupową , co oznacza, że półgrupa czynnikowa S / σ jest grupą. W zbiorze wszystkich kongruencji grupowych na półgrupie S element minimalny (dla rzędu częściowego zdefiniowanego przez uwzględnienie 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 jakąkolwiek inną kongruencją na S z S / τ grupą, to σ jest zawarte w t . Kongruencja σ nazywana jest minimalną kongruencją grupy na S . Minimalna kongruencja grupy może być użyta do scharakteryzowania E- jednostkowych odwróconych półgrup (patrz poniżej).
Kongruencję ρ na odwrotnej półgrupie S nazywamy idempotentną czystą, jeśli
E – odwrotne półgrupy jednostkowe
Jedna klasa odwrotnych półgrup które badano intensywnie w ciągu roku jest klasa E półgrup -unitary odwrotność odwrotna półgrupa S (z semilattice E z idempotents ) to e - jednolity , jeżeli dla wszystkich e w e i wszystkie 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 półgrupą odwrotną z półsietą E o idempotentach i minimalną kongruencją grupy σ . Wtedy następujące są równoważne:
- S oznacza E -jednostkowe;
- σ jest idempotentny czysty;
- = σ ,
gdzie jest relacja zgodności na S , zdefiniowana przez
- są idempotentni.
Twierdzenie McAlistera o pokrywaniu. Każda odwrócona półgrupa S ma osłonę E-jednostkową; oznacza to, że istnieje idempotentny oddzielający suriektywny homomorfizm od pewnej E-jednostkowej półgrupy T na S.
Kluczem do badania E- jednostkowych odwrotnych półgrup jest następująca konstrukcja. Niech będzie zbiorem częściowo uporządkowanym , z porządkowaniem ≤ i niech będzie podzbiorem o własnościach, które
- jest dolną półsiecią , to znaczy każda para elementów A , B in ma największe ograniczenie dolne A B in (w odniesieniu do ≤);
- to ideał rzędu , to znaczy dla A , B in , jeśli A jest w i B ≤ A , to B jest w .
Teraz niech G będzie grupą, która działa na (po lewej), taką, że
- dla wszystkich g w G i wszystkich A , B w , gA = gB wtedy i tylko wtedy, gdy A = B ;
- dla każdej g z G i każdy B w , istnieje A w taki sposób, że gA = B ;
- dla wszystkich A , B w , A ≤ B wtedy i tylko wtedy, gdy gA ≤ gB ;
- dla wszystkich g , h w G i wszystkich A w , g ( hA ) = ( gh ) A .
Zakłada się również, że trójka ma następujące właściwości:
- dla każdego X w , istnieje g w G i A w takim, że gA = X ;
- dla wszystkich g w G , g i mają niepuste przecięcie.
Taka trójka nazywana jest trójką McAlistera . Trójka McAlister służy do definiowania następujących elementów:
wraz z mnożeniem
- .
Następnie jest odwrotna półgrupa pod tym mnożeniem, gdzie ( A , g ) -1 = ( g -1 A , g -1 ). Jednym z głównych wyników w badaniu E- jednostkowych odwrotnych półgrup jest twierdzenie P McAlistera :
Twierdzenie P McAlistera. Niech będzie potrójny McAlister. Wtedy jest E- jednostkowa odwrócona półgrupa. I odwrotnie, każda E- jednostkowa odwrócona półgrupa jest izomorficzna z jedną z tego typu.
F – odwrotne półgrupy
Półgrupa odwrotna jest nazywana F -odwrotną, jeśli każdy element ma nad nim unikalny element maksymalny w naturalnym porządku cząstkowym, tj. każda klasa σ ma element maksymalny. Każda półgrupa odwrotna F jest monoidem E- jednostkowym. Twierdzenie McAlistera o zakryciu zostało udoskonalone przez MV Lawsona do:
Twierdzenie. Każda odwrócona półgrupa ma okładkę F -odwrotną.
Do scharakteryzowania półgrup odwrotnych F również użyto twierdzenia McAlistera P. Trójka McAlistera jest półgrupą odwrotną F wtedy i tylko wtedy, gdy jest ideałem głównym i jest półsiecią.
Swobodne odwrotne półgrupy
Dla półgrup odwrotnych możliwa jest konstrukcja podobna do wolnej grupy . Prezentacji wolnej odwrotnym półgrupa na zadany X można otrzymać biorąc pod uwagę wolną półgrupa z inwolucji , w którym zanik jest przeprowadzenie odwrotnej, a następnie przy iloraz przez zbieżność Vagner
Zadanie tekstowe dla wolnych odwrotnych półgrup jest znacznie bardziej skomplikowane niż dla wolnych grup. Sławny wynik w tym obszarze dzięki WD Munn, który wykazał, że elementy odwrotnej półgrupy wolnej można naturalnie uznać za drzewa, znane jako drzewa Munna. Mnożenie w półgrupie odwrotnej wolnej ma swojego odpowiednika w drzewach Munna , które zasadniczo polegają na nakładaniu się wspólnych części drzew. (więcej szczegółów w Lawson 1998)
Każda wolna półgrupa odwrotna jest F -odwrotna.
Związki z teorią kategorii
Powyższa kompozycja przekształceń cząstkowych zbioru daje początek symetrycznej półgrupie odwrotnej. Istnieje inny sposób tworzenia transformacji cząstkowych, który jest bardziej restrykcyjny niż ten zastosowany powyżej: dwie transformacje cząstkowe α i β składają się 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, lecz grupoid indukcyjny w sensie teorii kategorii . To ścisłe powiązanie między odwrotnymi półgrupami a grupoidami indukcyjnymi jest zawarte w twierdzeniu Ehresmanna-Scheina-Nambooripada , które stwierdza, że grupoid indukcyjny może być zawsze skonstruowany z odwrotnej półgrupy i odwrotnie. Dokładniej, półgrupa odwrotna jest to właśnie groupoid w kategorii Posets że jest Etale groupoid w odniesieniu do jego (dual) Przestrzeń Aleksandrowa i którego poset obiektów to meet-semilattice.
Uogólnienia odwrotnych półgrup
Jak zauważono powyżej, odwrotna półgrupa S może być zdefiniowana przez warunki (1) S jest regularną półgrupą , oraz (2) idempotenty w S komutują; doprowadziło to do dwóch odrębnych klas uogólnień odwrotnej półgrupy: półgrupy, w których (1) zachodzi, ale (2) nie i odwrotnie.
Przykładami regularnych uogólnień odwrotnej półgrupy są:
- Półgrupy regularne : półgrupa S jest regularna, jeśli każdy element ma przynajmniej jedną odwrotność; równoważnie, dla każdego a w S istnieje x w S takie, że axa = a .
- Półgrupy lokalnie odwrotne : półgrupa regularna S jest odwrotna lokalnie, jeśli eSe jest półgrupą odwrotną, dla każdego idempotentnego e .
- Ortodoksyjne półgrupy : regularna półgrupa S jest ortodoksyjna, jeśli jej podzbiór idempotentów tworzy podpółgrupę.
- Uogólnione półgrupy odwrotne : regularna półgrupa S nazywana jest uogólnioną półgrupą odwrotną, jeśli jej idempotenty tworzą normalne pasmo, tj. xyzx = xzyx , dla wszystkich idempotentów x , y , z .
Klasy uogólnionych odwrotnych półgrup jest skrzyżowanie z klasy lokalnie odwrotnych półgrup a klasa ortodoksyjnych półgrup.
Wśród nieregularnych uogólnień odwrotnej półgrupy są:
- (Lewe, prawe, dwustronne) odpowiednie półgrupy.
- (Lewo, prawo, dwustronne) obszerne półgrupy.
- (Lewe, prawe, dwustronne) póładekwatne półgrupy.
- Słabe (lewe, prawe, dwustronne) obfite półgrupy.
Kategoria odwrotna
To pojęcie odwrotności również łatwo uogólnia się na kategorie . Kategorii odwrotna jest tylko kategoria, w której każdy morfizmem f : X → Y ma uogólnione odwrotny g : Y → X tak, że FGF = F i gfg = g . Kategoria odwrotna jest samodualna . Najlepszym przykładem jest kategoria zbiorów i częściowych bijekcji .
Kategorie odwrotne znalazły różne zastosowania w informatyce teoretycznej .
Zobacz też
Uwagi
Bibliografia
- Clifford, AH; Preston, Wielka Brytania (1967). Algebraiczna teoria półgrup . Badania matematyczne Amerykańskiego Towarzystwa Matematycznego. 7 . Numer ISBN 978-0-8218-0272-4.
- Fontanna, JB (1979). „Adekwatne półgrupy” . Materiały Towarzystwa Matematycznego w Edynburgu . 22 (2): 113–125. doi : 10.1017/S0013091500016230 .
- Gołab, ul. (1939). "Über den Begriff der "Pseudogruppe von transformationen " ". Mathematische Annalen (w języku niemieckim). 116 : 768–780. doi : 10.1007/BF01597390 .
- Exel, R. (1998). „Częściowe działania grup i działania odwrotnych półgrup”. Procedury Amerykańskiego Towarzystwa Matematycznego . 126 (12): 3481–4. arXiv : funct-an/9511003 . doi : 10.1090/S0002-9939-98-04575-4 .
- Gould, V. „(Słabe) lewe półgrupy E-ample” . Zarchiwizowane z oryginału (Postscript) dnia 2005-08-26 . Pobrano 2006-08-28 .
- Howie, JM (1995). Podstawy teorii półgrup . Oxford: Clarendon Press. Numer ISBN 0198511949.
- Lawson, MV (1998). Odwrotne półgrupy: teoria symetrii częściowych . Światowy Naukowy. Numer ISBN 9810233167.
- McAlister, DB (1974a). „Grupy, półsieci i odwrotne półgrupy”. Transakcje Amerykańskiego Towarzystwa Matematycznego . 192 : 227-244. doi : 10.2307/1996831 . JSTOR 1996831 .
- McAlister, DB (1974b). „Grupy, półsieci i półgrupy odwrotne II” . Transakcje Amerykańskiego Towarzystwa Matematycznego . 196 : 351-370. doi : 10.2307/1997032 . JSTOR 1997032 .
- Petrich, M. (1984). Odwrotne półgrupy . Wileya. Numer ISBN 0471875457.
- Preston, Wielka Brytania (1954a). „Odwrócone półgrupy”. Dziennik Londyńskiego Towarzystwa Matematycznego . 29 (4): 396-403. doi : 10.1112/jlms/s1-29.4.396 .
- Preston, Wielka Brytania (1954b). „Odwrotne pół-grupy z minimalnymi prawymi ideałami”. Dziennik Londyńskiego Towarzystwa Matematycznego . 29 (4): 404–411. doi : 10.1112/jlms/s1-29.4.404 .
- Preston, Wielka Brytania (1954c). „Reprezentacje odwrotnych pół-grup”. Dziennik Londyńskiego Towarzystwa Matematycznego . 29 (4): 411–9. doi : 10.1112/jlms/s1-29.4.411 .
- Schein, BM (1981). „Nekrolog: Wiktor Władimirowicz Vagner (1908-1981)” . Forum półgrupowe . 28 : 189–200. doi : 10.1007/BF02676643 .
- Schein, BM (2002). „Recenzja książki: „Odwrotne półgrupy: teoria symetrii częściowych” autorstwa Marka V. Lawsona”. Forum półgrupowe . 65 : 149–158. doi : 10.1007/s00233010132 .
- Wagnera, VV (1952). „Grupy uogólnione”. Materiały Akademii Nauk ZSRR (w języku rosyjskim). 84 : 1119-1122. Tłumaczenie na język angielski (PDF)
- Wagnera, VV (1953). „Teoria uogólnionych hałd i uogólnionych grup”. Matematyczny Sbornik . Nowaja Serija (po rosyjsku). 32 (74): 545–632.
Dalsza lektura
- Krótkie wprowadzenie do odwrotnych półgrup można znaleźć w Clifford & Preston 1967 , rozdział 7 lub Howie 1995 , rozdział 5.
- Bardziej wyczerpujące wprowadzenia można znaleźć w Petrich 1984 i Lawson 1998 .
- Linckelmann, M. (2012). „O kategoriach odwrotnych i transferze w kohomologii” (PDF) . Materiały Towarzystwa Matematycznego w Edynburgu . 56 : 187. doi : 10.1017/S0013091512000211 . Wstępny wydruk z otwartym dostępem