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

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.

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ę 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 st 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 ( ) ( ) = ( st ) θ , dla wszystkich s , t w S . Definicję morfizmu półgrup odwrotnych można rozszerzyć o warunek ( ) −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 es , 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 BA , 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 , AB wtedy i tylko wtedy, gdy gAgB ;
  • 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ą:

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  : XY ma uogólnione odwrotny g  : YX 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

Dalsza lektura