Półgrupa bicykliczna - Bicyclic semigroup

W matematyce The bicykliczny półgrupa jest algebraiczna obiektu ważne dla konstrukcji teorii półgrup . Chociaż w rzeczywistości jest to monoid , zwykle określa się go jako po prostu półgrupę. Prawdopodobnie jest to najłatwiejsze do zrozumienia jako monoid syntaktyczny opisujący język Dycka o zrównoważonych parach nawiasów. W ten sposób znajduje powszechne zastosowania w kombinatoryce , takich jak opisywanie drzew binarnych i algebr asocjacyjnych .

Historia

Pierwszy opublikowany opis tego obiektu został podany przez Evgenii Lyapin w 1953 roku. Alfred H. Clifford i Gordon Preston twierdzą, że jeden z nich, współpracując z Davidem Reesem , odkrył go niezależnie (bez publikacji) w pewnym momencie przed 1943 rokiem.

Budowa

Istnieją co najmniej trzy standardowe sposoby konstruowania półgrupy bicyklicznej i różne notacje odnoszące się do niej. Lyapin nazwał to P ; Clifford i Preston używali ; Najnowsze dokumenty i mają tendencję do korzystania B . W tym artykule cały czas będzie używany nowoczesny styl.

Z wolnej półgrupy

Półgrupa bicykliczna jest wolnym monoidem na dwóch generatorach p i q , w relacji p q = 1. To znaczy, że każdy element półgrupy jest ciągiem tych dwóch liter, z zastrzeżeniem, że podciąg „ p q ” nie występuje. Operacja półgrupowa to konkatenacja łańcuchów, która jest wyraźnie asocjacyjna . Można zatem wykazać, że wszystkie elementy B w rzeczywistości mają postać q a p b , dla niektórych liczb naturalnych a i b . Operacja kompozycji upraszcza się do

( q a p b ) ( q c p d ) = q a + c - min { b , c } p d + b - min { b , c } .

Z uporządkowanych par

Sposób, w jaki te wykładnikami są ograniczone sugeruje, że „ p i q struktura” można usunąć, pozostawiając tylko operacje na „ i b ” części. Więc B jest półgrupą par liczb naturalnych (w tym zera), z operacją

( a , b ) ( c , d ) = ( a + c - min { b , c }, d + b - min { b , c }).

To wystarczy, aby zdefiniować B tak, aby był to ten sam obiekt, co w oryginalnej konstrukcji. Tak jak pierwotnie p i q wygenerowały B , z pustym ciągiem jako tożsamością monoidu, ta nowa konstrukcja B ma generatory (1, 0) i (0,1), z tożsamością (0, 0).

Z funkcji

Można wykazać, że każda półgrupa S wygenerowana przez elementy e , a i b spełniająca poniższe stwierdzenia jest izomorficzna z półgrupą bicykliczną.

  • a e = e a = a
  • b e = e b = b
  • a b = e
  • b a ≠ e

Nie jest całkowicie oczywiste, że tak powinno być - być może najtrudniejszym zadaniem jest zrozumienie, że S musi być nieskończone. Aby to zobaczyć, załóżmy, że a (powiedzmy) nie ma nieskończonego porządku, więc a k + h = a h dla niektórych h i k . Wtedy a k = e i

b = e b = a k b = a k - 1 e = a k - 1 ,

więc

b a = a k = e ,

co nie jest dozwolone, więc istnieje nieskończenie wiele odrębne uprawnienia . Pełny dowód znajduje się w książce Clifforda i Prestona.

Należy zauważyć, że obie podane powyżej definicje spełniają te właściwości. Trzeci sposób wyprowadzenia B wykorzystuje dwie odpowiednio dobrane funkcje, aby uzyskać półgrupę bicykliczną jako monoid przekształceń liczb naturalnych. Niech α, β i ι będą elementami półgrupy transformacji na liczbach naturalnych, gdzie

  • ι ( n ) = n
  • α ( n ) = n + 1
  • β ( n ) = 0, jeżeli n = 0, a n - 1 inaczej.

Te trzy funkcje posiadają wymagane właściwości, więc półgrupa generują jest B .

Nieruchomości

Bicykliczne półgrupa ma tę właściwość, że obraz każdej Homomorfizm cp z B do drugiego półgrupa S jest albo cykliczny , lub też jest izomorficzny kopia B . Elementy φ ( a ), φ ( b ) i φ ( e ) S zawsze będą spełniać powyższe warunki (ponieważ φ jest homomorfizmem) z możliwym wyjątkiem, że φ ( b ) φ ( a ) może okazać się φ ( e ). Jeśli to nie jest prawda, to φ ( B ) jest izomorficzne z B ; w przeciwnym razie jest to półgrupa cykliczna generowana przez φ ( a ). W praktyce oznacza to, że półgrupa bicykliczna może występować w wielu różnych kontekstach.

W idempotents z B są pary ( x , x ), gdzie x jest liczbą naturalną (stosując uporządkowaną charakterystykę parę B ). Ponieważ te dojazdy do pracy, a B jest regularne (dla każdego x istnieje y takie, że x y x = x ), półgrupa bicykliczna jest półgrupą odwrotną . (Oznacza to, że każdy element x z B ma unikalną odwrotność y , w sensie „słabej” półgrupy, że x y x = x i y x y = y .)

Każdy ideał od B jest główny: po lewej i prawej główne ideały ( m , n ) są

  • ( m , n ) B = {( s , t ): s ≥ m } i
  • B ( m , n ) = {( s , t ): t ≥ n }.

Każdy z nich zawiera nieskończenie wiele innych, więc B nie ma minimalnych ideałów lewej lub prawej.

Jeśli chodzi o relacje Greena , B ma tylko jedną klasę D (jest bisimple ), a zatem ma tylko jedną klasę J (jest to proste ). Gdy L i R stosunki są podane

Oznacza to, że dwa elementy są powiązane z H wtedy i tylko wtedy, gdy są identyczne. W konsekwencji jedyne podgrupy B to nieskończenie wiele kopii trywialnej grupy, z których każda odpowiada jednemu z idempotentów.

Diagram jajko-box dla B jest nieskończenie duża; zaczyna się lewy górny róg:

(0, 0) (1, 0) (2, 0) ...
(0, 1) (1, 1) (2, 1) ...
(0, 2) (1, 2) (2, 2) ...
... ... ... ...

Każda pozycja reprezentuje pojedynczą klasę H ; rzędy są R wyraĹĽenie -lekcje i kolumny L wyraĹĽenie -lekcje. Idempotenty klasy B pojawiają się po przekątnej, zgodnie z faktem, że w regularnej półgrupie z idempotentami dojeżdżającymi do pracy każda klasa L i każda klasa R musi zawierać dokładnie jeden idempotent.

Półgrupa bicykliczna jest „najprostszym” przykładem półgrupy bisprostej odwrotnej z tożsamością; jest wiele innych. Tam, gdzie w definicji B z par uporządkowanych wykorzystano klasę liczb naturalnych (która jest nie tylko półgrupą addytywną, ale także kratą przemienną w operacjach min i max), zamiast tego mógłby pojawić się inny zbiór o odpowiednich właściwościach, a „+”, Operacje „-” i „max” zostały odpowiednio zmodyfikowane.

Zobacz też

Uwagi

  1. ^ Hollings (2007), s. 332
  2. ^ Lothaire, M. (2011). Algebraiczna kombinatoryka słów . Encyklopedia matematyki i jej zastosowań. 90 . Z przedmową Jean Berstel i Dominique Perrin (przedruk wydania w twardej oprawie z 2002 r.). Cambridge University Press. p. 459. ISBN   978-0-521-18071-9 . Zbl   1221.68183 .
  3. ^ Howie s. 60

Bibliografia

  • Algebraiczna teoria półgrup , AH Clifford i GB Preston. American Mathematical Society, 1961 (tom 1), 1967 (tom 2).
  • Półgrupy: wprowadzenie do teorii struktur , Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
  • Kanoniczna postać elementów systemu asocjacyjnego nadana przez określenie relacji , Evgenii Sergeevich Lyapin, Leningrad Gos. Ped. Inst. Uch. Zastrzelić. 89 (1953), strony 45–54 [rosyjski].
  • Hollings, CD (2007). „Pierwsze kuszące kroki w teorii półgrup”. Magazyn Matematyka . Mathematical Association of America. 80 : 331–344. JSTOR   27643058 .