Monoid - Monoid

Struktury algebraiczne
Grupa -like Grupa Półgrupa  / Monoid Stojak i kwantowa Quasigrupa i pętla Grupa abelowa Magma Grupa kłamstw Teoria grup
pierścień -like Dzwonić Rng Semiring Blisko pierścienia Pierścień przemienny Domena integralna Pole Pierścień dywizji Teoria pierścieni
Krata -like Krata Semisiatka Uzupełniona krata Całkowite zamówienie Algebra Heyting Algebra Boole'a Mapa krat Teoria sieci
Moduł podobny Moduł Grupuj z operatorami Przestrzeń wektorowa Algebra liniowa
Algebra -like Algebra Asocjacyjny Nieskojarzone Algebra kompozycji Algebra kłamstwa Ocenione Bialgebra
v T mi

W algebrze abstrakcyjnej , gałęzi matematyki , monoid jest zbiorem wyposażonym w operację binarną asocjacyjną i element tożsamości .

Monoidy to półgrupy o identyczności. Takie struktury algebraiczne występują w kilku gałęziach matematyki.

Na przykład funkcje ze zbioru w siebie tworzą monoid w odniesieniu do kompozycji funkcji. Mówiąc bardziej ogólnie, w teorii kategorii morfizmy obiektu do siebie tworzą monoid i odwrotnie, monoid może być postrzegany jako kategoria z pojedynczym obiektem.

W informatyce i programowaniu komputerowym zbiór ciągów znaków zbudowany z danego zestawu znaków jest monoidem swobodnym . Monoidy przejścia i monoidy syntaktyczne są używane do opisu maszyn skończonych . Monoidy śledzenia i monoidy historii stanowią podstawę obliczeń procesów i obliczeń współbieżnych .

W informatyce teoretycznej badanie monoidów ma fundamentalne znaczenie dla teorii automatów ( teoria Krohna-Rhodesa ) i formalnej teorii języka ( problem wysokości gwiazdy ).

Zobacz półgrupę, aby zapoznać się z historią przedmiotu i kilkoma innymi ogólnymi właściwościami monoidów.

Definicja

Zestaw S wyposażony w operacji binarnego S x S → S , co oznaczamy •, jest monoid , jeżeli spełnia ona następujące dwa axioms:

Łączność

Dla wszystkich a , b i c w S , równanie ( a • b ) • c = a • ( b • c ) jest prawdziwe .

Element tożsamości

Istnieje element e w S tak, że na każdy element a w S równania e • o = i • e = w ładowni.

Innymi słowy, monoid to półgrupa z elementem tożsamościowym . Można go również traktować jako magmę z asocjatywnością i tożsamością. Element tożsamości monoidu jest wyjątkowy. Z tego powodu tożsamość jest traktowana jako stała , czyli operacja 0-argumentowa (lub nullary). Monoid zatem charakteryzuje się specyfikacją trójki ( S , • , e ).

W zależności od kontekstu symbol operacji binarnej można pominąć, aby operacja była oznaczona zestawieniem; na przykład aksjomaty monoidów można zapisać ( ab ) c = a ( bc ) i ea = ae = a . Ten zapis nie oznacza, że ​​jest to mnożenie liczb.

Monoid, w którym każdy element ma odwrotność, jest grupą .

Struktury monoidalne

Podmonoidy

Submonoid z monoid ( M , •) jest podzbiór N o M , który jest zamknięty w ramach operacji monoid i zawiera Tożsamość elementu e o M . Symbolicznie N jest submonoid z M jeśli N ⊆ M , x • y ∈ N gdy x , y ∈ N i e ∈ N . W tym przypadku N jest monoidem w ramach operacji binarnej odziedziczonej z M .

Z drugiej strony, jeśli N jest podzbiorem monoidu, który jest zamknięty w operacji monoidu i jest monoidem dla tej dziedziczonej operacji, to N nie zawsze jest podmonoidem, ponieważ elementy tożsamości mogą się różnić. Na przykład zbiór pojedynczych {0} jest zamknięty w wyniku mnożenia i nie jest podmonoidem (multiplikatywnego) monoidu nieujemnych liczb całkowitych .

Generatory

Mówi się, że podzbiór S z M generuje M, jeśli najmniejszym podmonoidem M zawierającym S jest M . Jeśli istnieje skończony zbiór generujący M , to mówi się , że M jest skończenie generowanym monoidem .

Monoid przemienny

Monoid, którego działanie jest przemienne, nazywany jest monoidem przemiennym (lub rzadziej monoidem abelowym ). Monoidy przemienne są często pisane addytywnie. Każdy przemienny monoid ma swoje wstępne uporządkowanie algebraiczne ≤ , zdefiniowane przez x ≤ y , jeśli istnieje z takie , że x + z = y . Jednostka porządkowa monoidu przemiennego M jest elementem u z M takim, że dla dowolnego elementu x z M istnieje v w zbiorze wygenerowanym przez u taki, że x ≤ v . Jest to często stosowane w przypadku M jest dodatnią stożek z częściowo uporządkowanej Abelowych grupy G , w tym przypadku stwierdzić, że u jest rozkaz, jednostka G .

Częściowo przemienny monoid

Monoid, dla którego operacja jest przemienna dla niektórych, ale nie wszystkich elementów, jest monoidem śladowym ; monoidy śladowe powszechnie występują w teorii obliczeń współbieżnych .

Przykłady

• Spośród 16 możliwych binarnych operatorów logicznych , każdy z czterech, które mają dwustronną tożsamość, jest również przemienny i asocjacyjny, a zatem czyni zbiór {False, True} monoidem przemiennym. Zgodnie ze standardowymi definicjami AND i XNOR mają tożsamość True, podczas gdy XOR i OR mają tożsamość False. Monoidy z AND i OR są również idempotentne, podczas gdy te z XOR i XNOR nie.
• Zbiór liczb naturalnych jest monoidem przemiennym pod wpływem dodawania (element tożsamości 0 ) lub mnożenia (element tożsamości 1 ). Podmonoid z dodatkiem N nazywany jest monoidem numerycznym .${\ Displaystyle \ mathbb {N} = \ {0,1,2, \ ldots \}}$
• Zbiór liczb całkowitych dodatnich jest monoidem przemiennym pod wpływem mnożenia (element tożsamości 1).${\ Displaystyle \ mathbb {N} \ setminus \ {0 \}}$
• Biorąc pod uwagę zbiór A , zbiór podzbiorów A jest przemiennym monoidem pod przecięciem (elementem tożsamości jest sam A ).
• Biorąc pod uwagę zbiór A , zbiór podzbiorów A jest monoidem przemiennym w ramach unii (elementem tożsamości jest zbiór pusty ).
• Uogólniając poprzedni przykład, każda ograniczona półsieć jest idempotentnym monoidem przemiennym.
  • W szczególności, każdy ograniczonym, krata może być wyposażony zarówno spełniają - i dołączyć - monoid strukturę. Elementami tożsamości są odpowiednio góra i dół kraty. Będąc kratami, algebry Heytinga i algebry Boole'a są wyposażone w te struktury monoidalne.
• Każdy zbiór singletonów { x } zamknięty pod operacją binarną • tworzy trywialny (jednoelementowy) monoid, będący jednocześnie grupą trywialną .
• Każda grupa jest monoidem, a każda grupa abelowa monoidem przemiennym.
• Dowolną półgrupę S można przekształcić w monoid po prostu przez przyłączenie elementu e spoza S i zdefiniowanie e • s = s = s • e dla wszystkich s ∈ S . Ta konwersja dowolnej półgrupy do monoidu jest dokonywana przez funktor swobodny między kategorią półgrup a kategorią monoidów.
  • Tak więc idempotentny monoid (czasami znany jako znajdź-pierwszy ) może być utworzony przez przyłączenie elementu tożsamości e do lewej półgrupy zerowej nad zbiorem S . Przeciwny monoid (czasami nazywany find-last ) jest utworzony z prawej półgrupy zerowej nad S .
    • Dołącz tożsamość e do półgrupy po lewej stronie zerowej za pomocą dwóch elementów {lt, gt} . Następnie otrzymany idempotentny monoid {lt, e , gt} modeluje porządek leksykograficzny sekwencji o podanych rzędach jego elementów, gdzie e reprezentuje równość.
• Podstawowy zbiór dowolnego pierścienia , z dodawaniem lub mnożeniem jako operacją. (Z definicji pierścień ma tożsamość multiplikatywną 1.)
  • Te liczby całkowite , liczby wymierne , liczbami rzeczywistymi lub liczbami zespolonymi , z dodatkiem lub mnożenia jako operacji.
  • Zbiór wszystkich macierzy n na n nad danym pierścieniem, z operacją dodawania lub mnożenia macierzy .
• Zbiór wszystkich skończonych łańcuchów nad pewnym ustalonym alfabetem Σ tworzy monoid z konkatenacją łańcuchów jako operacją. Pusty łańcuch służy jako element neutralny. Ten monoid jest oznaczony Σ ^∗ i jest nazywany wolnym monoidem nad Σ . Nie jest przemienny.
• Mając dowolny monoid M , przeciwny monoid M ^op ma ten sam zbiór nośników i element tożsamości co M , a jego działanie jest zdefiniowane przez x • ^op y = y • x . Każdy monoid przemienny jest przeciwieństwem samego siebie.
• Biorąc pod uwagę dwa zbiory M i N obdarzone strukturą monoidu (lub ogólnie dowolną skończoną liczbę monoidów, M ₁ , …, M _k ) , ich iloczyn kartezjański M × N jest również monoidem (odpowiednio M ₁ × ⋯ × M _k ). Operacja asocjacyjna i element tożsamości są definiowane parami.
• Napraw monoid M . Zbiór wszystkich funkcji od danego zestawu do M jest również monoidem. Element tożsamości jest stałą funkcją odwzorowującą dowolną wartość na tożsamość M ; operacja asocjacyjna jest zdefiniowana punktowo .
• Ustalić monoid M z działaniem • i element neutralny e , i za jego ustawienia mocy P ( M ) składa się z wszystkich podgrup o M . Binarna działanie takich podzbiory mogą być określone przez S • T = { y • t  : y ∈ S , T ∈ T } . To zamienia P ( M ) w monoid z elementem tożsamościowym { e } . W ten sam sposób zbiór potęgowy grupy G jest monoidem pod iloczynem podzbiorów grupowych .
• Niech S będzie zbiorem. Zbiór wszystkich funkcji S → S tworzy monoid pod złożeniem funkcji . Tożsamość jest tylko funkcją tożsamości . Nazywana jest również pełna transformacja monoid od S . Jeśli S jest skończony z n elementami, monoid funkcji na S jest skończony z n ⁿ elementami.
• Uogólniając poprzedni przykład, niech C będzie kategorią, a X obiektem C . Zbiór wszystkich endomorfizm z X , oznaczonej koniec _C ( X ) tworzy monoid pod kompozycji morfizmów . Więcej informacji na temat związku między teorią kategorii a monoidami znajdziesz poniżej.
• Zestaw homeomorfizm klas o zwartej powierzchni z podłączonego sumy . Jej jednostkowym elementem jest klasa zwykłej 2-kuli. Ponadto, jeśli a oznacza klasę torusa , a b oznacza klasę płaszczyzny rzutowej, to każdy element c monoidu ma jednoznaczne wyrażenie w postaci c = na + mb gdzie n jest dodatnią liczbą całkowitą, a m = 0, 1 lub 2 . Mamy 3 b = a + b .
• Niech będzie monoidem cyklicznym rzędu n , czyli . Potem dla niektórych . W rzeczywistości każdy taki k daje odrębny monoid rzędu n , a każdy cykliczny monoid jest izomorficzny z jednym z nich. Ponadto f można traktować jako funkcję w punktach podanych przez${\ Displaystyle \ langle f \ rangle }$${\ Displaystyle \ langle f \ rangle = \ lewo \ {f ^ {0}, f ^ {1}, \ kropki, f ^ {n-1} \ prawo \}}$${\ Displaystyle f ^ {n} = f ^ {k}}$${\displaystyle 0\leq k<n}$
  ${\displaystyle \{0,1,2,\kropki, n-1\}}$

${\ Displaystyle {\ zacząć {bmatrix} 0 i 1 i 2 i \ cdots & n-2 i n-1 \ \ 1 i 2 i 3 i \ cdots & n-1 i k \ koniec {bmatrix}}}$

lub równoważnie

${\ Displaystyle f (i): = {\ zacząć {przypadki} i + 1, & {\ tekst {jeśli}} 0 \ leq i < n-1 \ \ k, & {\ tekst {jeśli}} i = n -1.\end{przypadki}}}$

Mnożenie elementów w jest wtedy podane przez złożenie funkcji.${\ Displaystyle \ langle f \ rangle }$

Kiedy wtedy funkcja f jest permutacją i daje unikalną grupę cykliczną rzędu n .${\ Displaystyle k = 0}$${\displaystyle \{0,1,2,\kropki,n-1\},}$

Nieruchomości

Aksjomaty monoidu implikują, że element tożsamości e jest unikalny: Jeśli e i f są elementami tożsamości monoidu, to e = ef = f .

Produkty i uprawnienia

Dla każdego nieujemną liczbę całkowitą N , można określić produkt dowolnej sekwencji z n elementów monoid rekurencyjnie niech p ₀ = e i niech t _m = p _{m -1} • _m do 1 ≤ m ≤ n . ${\ Displaystyle p_ {n} = \ textstyle \ prod _ {i = 1} ^ {n} a_ {i}}$${\ Displaystyle (a_ {1}, \ ldots, a_ {n})}$

W szczególnym przypadku można zdefiniować nieujemne potęgi całkowite elementu x monoidu: x ⁰ = 1 oraz x ⁿ = x ^{n −1} • x dla n ≥ 1 . Wtedy x ^{m + n} = x ^m • x ⁿ dla wszystkich m , n ≥ 0 .

Elementy odwracalne

Element x jest nazywany odwracalnym, jeśli istnieje element y taki, że x • y = e i y • x = e . Element y nazywamy odwrotnością x . Odwrotności, jeśli istnieją, są unikalne: Jeśli y i z są odwrotnościami x , to przez asocjatywność y = ey = ( zx ) y = z ( xy ) = ze = z .

Jeśli x jest odwracalne, powiedzmy z odwrotnością y , wtedy można zdefiniować ujemne potęgi x przez ustawienie x ^{− n} = y ⁿ dla każdego n ≥ 1 ; to sprawia, że ​​równanie x ^{m + n} = x ^m • x ^{n obowiązuje} dla wszystkich m , n ∈ Z .

Zbiór wszystkich elementów odwracalnych w monoidzie wraz z operacją • tworzy grupę .

Grupa Grothendiecka

Nie każdy monoid znajduje się w grupie. Na przykład, jest całkiem możliwe, aby mieć monoid w którym dwa elementy A i B istnieje takie, że • b = posiada chociaż b nie jest element neutralny. Taki monoid nie może być osadzony w grupie, ponieważ w grupie pomnożenie obu stron przez odwrotność a dałoby b = e , co nie jest prawdą.

Monoid ( M , •) ma właściwość anulowania (lub jest anulowania), jeśli dla wszystkich a , b i c w M , równość a • b = a • c implikuje b = c , a równość b • a = c • a implikuje b = c .

Monoid przemienny z właściwością anulowania można zawsze osadzić w grupie za pomocą konstrukcji grupy Grothendiecka . W ten sposób addytywna grupa liczb całkowitych (grupa z operacją +) jest konstruowana z addytywnego monoidu liczb naturalnych (monoid przemienny z operacją + i właściwością anulowania). Jednak nieprzemienny monoid skojarzeniowy nie musi być osadzony w grupie.

Jeśli monoid ma właściwość anulowania i jest skończony , to w rzeczywistości jest grupą.

Każdy z prawych i lewych skreśleń monoidu tworzy kolejno podmonoid (tj. są zamknięte pod operacją i oczywiście zawierają tożsamość). Oznacza to, że elementy kasujące dowolnego monoidu przemiennego można rozszerzyć na grupę.

Własność kasacyjna w monoidzie nie jest konieczna do wykonania konstrukcji Grothendiecka – wystarcza przemienność. Jeśli jednak przemienny monoid nie ma właściwości anulowania, homomorfizm monoidu do jego grupy Grothendiecka nie jest iniektywny. Dokładniej, jeśli a • b = a • c , to b i c mają ten sam obraz w grupie Grothendiecka, nawet jeśli b ≠ c . W szczególności, jeśli monoid ma element absorbujący , to jego grupa Grothendiecka jest grupą trywialną .

Rodzaje monoidów

Odwrotny monoid jest monoid gdzie dla każdego a w M istnieje unikalny A ^-1 w M , tak że = • ^-1 • i ^-1 = ^-1 • • ^-1 . Jeśli odwrotny monoid jest anulacyjny, to jest to grupa.

W przeciwnym kierunku monoid bez sumy zerowej jest addytywnie zapisywanym monoidem, w którym a + b = 0 oznacza, że a = 0 i b = 0 : równoważnie, że żaden element inny niż zero nie ma odwrotności addytywnej.

Akty i monoidy operatora

Niech M będzie monoidem, z operacją binarną przez • i elementem tożsamości przez e . Wtedy (lewy) M -akt (lub lewy akt nad M ) jest zbiorem X wraz z operacją ⋅ : M × X → X, która jest zgodna ze strukturą monoidu w następujący sposób:

• dla wszystkich x w X : e ⋅ x = x ;
• dla wszystkich a , b w M i x w X : a ( b ⋅ x ) = ( a • b ) ⋅ x .

Jest to odpowiednik w teorii monoidów (lewego) działania grupowego . W podobny sposób definiuje się prawe akty M. Monoid z aktem jest również znany jako monoid operatora . Ważne przykłady obejmują układy przejściowe o semiautomata . Półgrupa przekształcenie może być przekształcony w monoid operatora przez przylegający do transformacji tożsamości.

Homomorfizmy monoidów

Homomorfizm dwóch monoids ( M *) i ( N , •) jest funkcją f  : M → N w taki sposób,

• f ( x ∗ y ) = f ( x ) • f ( y ) dla wszystkich x , y w M
• f ( e _M ) = e _N ,

gdzie e _M i e _N są tożsamości na M i N , odpowiednio. Homomorfizmy monoidalne są czasami nazywane po prostu morfizmami monoidalnymi .

Nie każdy homomorfizm półgrupy między monoidami jest homomorfizmem monoidu, ponieważ może nie mapować tożsamości na tożsamość docelowego monoidu, nawet jeśli tożsamość jest tożsamością obrazu homomorfizmu. Rozważmy na przykład zbiór klas pozostałości modulo wyposażony w mnożenie. W szczególności klasą jest tożsamość. Funkcja podana przez jest homomorfizmem półgrupowym, jak w . Jednak , więc homomorfizm monoidu jest homomorfizmem półgrupowym między monoidami, który odwzorowuje tożsamość pierwszego monoidu na tożsamość drugiego monoidu, a tego ostatniego warunku nie można pominąć. ${\ Displaystyle M_ {n}}$${\ Displaystyle n}$${\ Displaystyle 1}$${\ Displaystyle f \ dwukropek M_ {3}\ do M_ {6}}$${\displaystyle f(k)=3k}$${\ Displaystyle 3k \ cdot 3l = 9kl = 3kl}$${\ Displaystyle M_ {6}}$${\ Displaystyle f (1) = 3 \ neq 1}$

W przeciwieństwie do tego, homomorfizm półgrupy między grupami jest zawsze homomorfizmem grupy , ponieważ z konieczności zachowuje tożsamość (ponieważ w grupie tożsamość jest jedynym elementem takim, że x ⋅ x = x ).

Bijective monoid homomorfizm jest nazywany monoid izomorfizmem . Mówi się, że dwa monoidy są izomorficzne, jeśli między nimi występuje izomorfizm monoidu.

Prezentacja równań

Monoidom można przedstawić prezentację , podobnie jak grupy można określić za pomocą prezentacji grupowej . Robi się to przez określenie zbioru generatorów Σ i zbioru relacji na swobodnym monoidzie Σ ^∗ . Robi się to rozszerzając (skończone) relacje binarne na Σ ^∗ na kongruencje monoidalne, a następnie konstruując monoid ilorazowy, jak wyżej.

Biorąc pod uwagę binarną relację R ⊂ Σ ^∗ × Σ ^∗ , definiujemy jej symetryczne zamknięcie jako R ∪ R ⁻¹ . Można to rozszerzyć do symetrycznej relacji E ⊂ Σ ^∗ × Σ ^∗ definiując x ~ _E y wtedy i tylko wtedy, gdy x = sut i y = svt dla niektórych łańcuchów u , v , s , t ∈ Σ ^∗ z ( u , v ) R ∪ R ^-1 . Na koniec bierzemy domknięcie zwrotne i przechodnie E , które jest wtedy kongruencją monoidalną.

W typowej sytuacji relacja R jest po prostu podana jako zbiór równań, tak że . Tak więc na przykład ${\ Displaystyle R = \ {u_ {1} = v_ {1} \ cdots, u_ {n} = v_ {n} \}}$

${\ Displaystyle \ langle p, q \, \ vert \; pq = 1 \ rangle }$

jest równaniem prezentacji dla bicyklicznego monoidu , a

${\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle}$

jest monoidem plastycznym stopnia 2 (ma nieskończony porządek). Elementy tego płaskiego monoidu można zapisać jak dla liczb całkowitych i , j , k , ponieważ z relacji wynika, że ba łączy się zarówno z a, jak i b . ${\ Displaystyle a ^ {i} b ^ {j} (ba) ^ {k}}$

Związek z teorią kategorii

Struktury grupowe
	Całość	Łączność	Tożsamość	Odwracalność	Przemienność
Semigroupoid	Niepotrzebne	Wymagany	Niepotrzebne	Niepotrzebne	Niepotrzebne
Mała kategoria	Niepotrzebne	Wymagany	Wymagany	Niepotrzebne	Niepotrzebne
Groupoid	Niepotrzebne	Wymagany	Wymagany	Wymagany	Niepotrzebne
Magma	Wymagany	Niepotrzebne	Niepotrzebne	Niepotrzebne	Niepotrzebne
Quasigrupa	Wymagany	Niepotrzebne	Niepotrzebne	Wymagany	Niepotrzebne
Jednolita Magma	Wymagany	Niepotrzebne	Wymagany	Niepotrzebne	Niepotrzebne
Pętla	Wymagany	Niepotrzebne	Wymagany	Wymagany	Niepotrzebne
Półgrupa	Wymagany	Wymagany	Niepotrzebne	Niepotrzebne	Niepotrzebne
Monoid	Wymagany	Wymagany	Wymagany	Niepotrzebne	Niepotrzebne
Monoid przemienny	Wymagany	Wymagany	Wymagany	Niepotrzebne	Wymagany
Grupa	Wymagany	Wymagany	Wymagany	Wymagany	Niepotrzebne
Grupa abelowa	Wymagany	Wymagany	Wymagany	Wymagany	Wymagany
^α Zamknięcie, które jest używane w wielu źródłach, jest równoważnym aksjomatem dla całości, choć różnie definiowanym.

Monoidy można postrzegać jako specjalną klasę kategorii . Rzeczywiście, aksjomaty wymagane od operacji monoidu są dokładnie tymi wymaganymi przy składaniu morfizmów, gdy są ograniczone do zbioru wszystkich morfizmów, których źródłem i celem jest dany obiekt. To jest,

Monoid jest zasadniczo tym samym, co kategoria z pojedynczym przedmiotem.

Dokładniej, mając monoid ( M , • ) , można skonstruować małą kategorię z tylko jednym obiektem i której morfizmy są elementami M . Skład morfizmów jest określony operacją monoidu •.

Podobnie homomorfizmy monoidalne są tylko funktorami między kategoriami pojedynczych obiektów. Tak więc konstrukcja ta daje równoważność między kategorią (małych) monoidów Mon i pełną podkategorią kategorii (małych) kategorii Cat . Podobnie kategoria grup odpowiada innej pełnej podkategorii Cat .

W tym sensie teorię kategorii można traktować jako rozszerzenie pojęcia monoidu. Wiele definicji i twierdzeń o monoidach można uogólnić do małych kategorii z więcej niż jednym obiektem. Na przykład iloraz kategorii z jednym obiektem jest tylko monoidem ilorazu.

Monoidy, podobnie jak inne struktury algebraiczne, również tworzą własną kategorię, Mon , której obiekty są monoidami, a morfizmy są homomorfizmami monoidów.

Istnieje również pojęcie obiektu monoidalnego, które jest abstrakcyjną definicją tego, czym jest monoid w kategorii. Obiekt monoid w Set jest po prostu monoidem.

Monoidy w informatyce

W informatyce strukturę monoidową można nadać wielu abstrakcyjnym typom danych . W powszechnym wzorze sekwencja elementów monoidu jest „ składana ” lub „akumulowana”, aby uzyskać końcową wartość. Na przykład, wiele algorytmów iteracyjnych wymaga aktualizacji pewnego rodzaju „suma bieżącej” w każdej iteracji; ten wzór może być elegancko wyrażony przez operację monoidu. Alternatywnie asocjatywność operacji monoidowych zapewnia, że ​​operacja może być zrównoleglona przez zastosowanie sumy prefiksów lub podobnego algorytmu, w celu wydajnego wykorzystania wielu rdzeni lub procesorów.

Biorąc pod uwagę sekwencji wartości typu M z elementu osobistego oraz asocjacyjne pracy The krotnie operacji są zdefiniowane w następujący sposób: ${\displaystyle \varepsilon}$${\ Displaystyle \ pocisk}$

${\ Displaystyle \ operatorname {fold}: M ^ {*} \ rightarrow M = \ ell \ mapsto {\ zacząć {przypadki} \ varepsilon i {\ mbox {jeśli}} \ ell = \ operatorname {nil} \ \ m \ bullet \mathrm {fold} \,\ell '&{\mbox{if }}\ell =\mathrm {przeciw} \,m\,\ell '\end{cases}}}$

Ponadto każdą strukturę danych można „zwinąć” w podobny sposób, dzięki serializacji jej elementów. Na przykład wynik „zwinięcia” drzewa binarnego może się różnić w zależności od przechodzenia przez drzewo w przedsprzedaży i po złożeniu zamówienia .

MapaReduce

Zastosowaniem monoidów w informatyce jest tak zwany model programowania MapReduce (patrz Kodowanie Map-Reduce jako monoid z zawinięciem w lewo ). MapReduce w obliczeniach składa się z dwóch lub trzech operacji. Biorąc pod uwagę zestaw danych, „Mapa” polega na mapowaniu dowolnych danych na elementy określonego monoidu. "Reduce" polega na złożeniu tych elementów, dzięki czemu w końcu wyprodukujemy tylko jeden element.

Na przykład, jeśli mamy multiset , w programie jest on reprezentowany jako mapa od elementów do ich numerów. W tym przypadku elementy nazywane są kluczami. Liczba różnych kluczy może być zbyt duży, a w tym przypadku multiset jest sharded. Aby prawidłowo zakończyć redukcję, etap „Tasowanie” ponownie grupuje dane między węzłami. Jeśli nie potrzebujemy tego kroku, cała Map/Reduce składa się z mapowania i redukcji; obie operacje można zrównoleglać, pierwsza ze względu na elementarną naturę, druga ze względu na asocjatywność monoidu.

Kompletne monoidy

Kompletny monoid jest przemienne monoid wyposażony w nieskończonej operacji sumy dla każdego indeksu ustawić I takie, że: ${\ Displaystyle \ Sigma _ {I}}$

${\ Displaystyle \ suma _ {i \ w \ pusty zestaw} {m_ {i}} = 0; \ quad \ suma _ {i \ w \ {j \}} {m_ {i}} = m_ {j}; \ quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ dla }}j\neq k}$

oraz

${\ Displaystyle \ suma _ {j \ w J} {\ suma _ {i \ w I_ {j}} {m_ {i}}} = \ suma _ {i \ w I} (m_ {i}) \ quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ i }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'}$

Ciągły monoid jest uporządkowana przemienne monoid w którym każdy zbiór skierowany ma przynajmniej górna granica zgodna z operacją monoid:

${\ Displaystyle a + \ sup S = \ sup (a + S) \ .}$

Te dwa pojęcia są ściśle powiązane: ciągły monoid to kompletny monoid, w którym nieskończoną sumę można zdefiniować jako

${\ Displaystyle \ suma _ {I} a_ {i} = \ sup \ suma _ {E} a_ {i}}$

gdzie supremum po prawej stronie biegnie przez wszystkie skończone podzbiory E od I, a każda suma po prawej jest skończoną sumą w monoidzie.

Zobacz też

• Relacje Greena
• Monada (programowanie funkcjonalne)
• Semiring i Kleene algebra
• Problem z wysokością gwiazdy
• Plac wedyjski

Uwagi

Bibliografia

• Howie, John M. (1995), Podstawy teorii półgrup , Monografie London Mathematical Society. Nowa seria, 12 , Oxford: Clarendon Press, ISBN 0-19-851194-9, Zbl  0835.20077
• Jacobson, Nathan (1951), Wykłady z algebry abstrakcyjnej , I , D. Van Nostrand Company, ISBN 0-387-90122-1
• Jacobson, Nathan (2009), Podstawowa algebra , 1 (2nd ed.), Dover, ISBN 978-0-486-47189-1
• Kilpa, Mati; Knauera, Ulryka; Mikhalev, Alexander V. (2000), Monoidy, akty i kategorie. Z aplikacjami do wianków i wykresów. Podręcznik dla studentów i badaczy , de Gruyter Expositions in Mathematics, 29 , Berlin: Walter de Gruyter, ISBN 3-11-015248-7, Zbl  0945.20036
• Lothaire, M. (1997), Combinatorics on words , Encyclopedia of Mathematics and Its Applications, 17 , Perrin, D.; Reutenauer, C.; Berstel, J.; Szpilka, JE; Pirillo, G.; Foata, D.; Sakarowicz, J.; Szymona I.; poseł Schützenberger; Choffrut, C.; Cori, R.; Lyndona, Rogera; Rota, Gian-Carlo. Przedmowa Rogera Lyndona (2nd ed.), Cambridge University Press , doi : 10.1017/CBO9780511566097 , ISBN 0-521-59924-5, MR  1475463 , Zbl  0874.20040

Zewnętrzne linki

• "Monoid" , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Monoid” . MatematykaŚwiat .
• Monoid w PlanetMath .