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 są 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
- Bijekcje cząstkowe na zbiorze X tworzą odwrotną półgrupę w składzie.
- Każda grupa jest odwrotną półgrupą.
- Półgrupa bicykliczna jest odwrotna, gdzie ( a , b ) −1 = ( b , a ).
- Każda półkrata jest odwrotna.
- Półgrupa Brandta jest odwrotna.
- Półgrupa Munna 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 przemienna.
& | 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 ( sθ ) ( tθ ) = ( st ) θ , dla wszystkich s , t w S . Definicję morfizmu odwrotnych półgrup można rozszerzyć, włączając warunek ( sθ ) −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ą:
- Regularne półgrupy : półgrupa S jest regularna , jeśli każdy element ma co najmniej jedną odwrotność; równoważnie dla każdego a w S istnieje x w S takie, że axa = a .
- Lokalnie odwrotne półgrupy : regularna półgrupa S jest lokalnie odwrotna, jeśli eSe jest odwrotną półgrupą, dla każdego idempotentnego e .
- Półgrupy ortodoksyjne : regularna półgrupa S jest ortodoksyjna , jeśli jej podzbiór idempotentów tworzy podgrupę.
- Uogólnione odwrotne półgrupy : regularna półgrupa S jest nazywana uogólnioną odwrotną półgrupą , jeśli jej idempotenty tworzą normalne pasmo, tj. xyzx = xzyx , dla wszystkich idempotentów x , y , z .
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
- Clifford, Ah; Preston, Wielka Brytania (1967). Algebraiczna teoria półgrup . Ankiety matematyczne Amerykańskiego Towarzystwa Matematycznego. Tom. 7. ISBN 978-0-8218-0272-4 .
- Fontanna, JB (1979). „Odpowiednie półgrupy” . Proceedings of Edinburgh Mathematical Society . 22 (2): 113–125. doi : 10.1017/S0013091500016230 .
- Gołab, St. (1939). "Über den Begriff der "Pseudogruppe von Transformationen" ". Mathematische Annalen (w języku niemieckim). 116 : 768–780. doi : 10.1007/BF01597390 .
- Eksel, R. (1998). „Częściowe działania grup i działania odwrotnych półgrup”. Proceedings of the American Mathematical Society . 126 (12): 3481–4. arXiv : funkcja-an/9511003 . doi : 10.1090/S0002-9939-98-04575-4 .
- Gould, V. „(Słabo) lewy E-ample półgrupy” . Zarchiwizowane od oryginału (postscript) w dniu 2005-08-26 . Źródło 2006-08-28 .
- Howie, JM (1995). Podstawy teorii półgrup . Oksford: Clarendon Press. ISBN 0198511949 .
- Lawson, MV (1998). Odwrotne półgrupy: teoria częściowych symetrii . Świat naukowy. 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 odwrotne półgrupy II” . Transakcje Amerykańskiego Towarzystwa Matematycznego . 196 : 351–370. doi : 10.2307/1997032 . JSTOR 1997032 .
- Petrich, M. (1984). Półgrupy odwrotne . Wileya. ISBN 0471875457 .
- Preston, Wielka Brytania (1954a). „Odwrotne półgrupy”. Journal of London Mathematical Society . 29 (4): 396–403. doi : 10.1112/jlms/s1-29.4.396 .
- Preston, Wielka Brytania (1954b). „Odwrotne półgrupy z minimalnymi prawymi ideałami”. Journal of London Mathematical Society . 29 (4): 404–411. doi : 10.1112/jlms/s1-29.4.404 .
- Preston, Wielka Brytania (1954c). „Reprezentacje odwrotnych półgrup”. Journal of London Mathematical Society . 29 (4): 411–9. doi : 10.1112/jlms/s1-29.4.411 .
- Schein, BM (1981). „Nekrolog: Wiktor Władimirowicz Vagner (1908–1981)” . forum półgrupy . 28 : 189–200. doi : 10.1007/BF02676643 .
- Schein, BM (2002). „Recenzja książki:„ Odwrotne półgrupy: teoria symetrii częściowych ”Marka V. Lawsona” . forum półgrupy . 65 : 149–158. doi : 10.1007/s002330010132 .
- 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”. Matematicheskii Sbornik . Nowaja Serija (po rosyjsku). 32 (74): 545–632.
Dalsza lektura
- Krótkie wprowadzenie do półgrup odwrotnych można znaleźć w Clifford i Preston 1967 , rozdział 7 lub Howie 1995 , rozdział 5.
- Bardziej obszerne wprowadzenie można znaleźć w Petrich 1984 i Lawson 1998 .
- Linkkelmann, M. (2012). „O kategoriach odwrotnych i transferze w kohomologii” (PDF) . Proceedings of Edinburgh Mathematical Society . 56 : 187. doi : 10.1017/S0013091512000211 . Preprint w otwartym dostępie