Semiring - Semiring
Struktura algebraiczna → Teoria pierścieni Teoria pierścieni |
---|
W abstrakcyjnej Algebra , A semiring jest algebraiczna strukturę podobną do pierścienia , ale bez wymogu, aby każdy element musi mieć addytywne odwrócony .
Określenie Rig jest również od czasu do czasu, to pochodzi jako kawał, co sugeruje, że wiertnicze są ri n ń bez n elementów egative, podobnie jak w przypadku RNG oznacza AR I ng bez multiplikatywnej ı dentity.
Półpierścienie tropikalne są aktywnym obszarem badań, łączącym rozmaitości algebraiczne ze strukturami odcinkowo liniowymi .
Struktury algebraiczne |
---|
Definicja
Semiring jest zestaw wyposażony w dwóch operacjach binarnych i nazywa dodawania i mnożenia, tak że:
-
jest przemiennym monoidem z elementem tożsamości :
-
jest monoidem z elementem tożsamości :
- Mnożenie z lewej i prawej strony rozkłada się na dodawanie:
- Mnożenie przez anihilacje :
Symbol jest zwykle pomijany w notacji; to znaczy, jest właśnie napisane Podobnie, przyjmuje się Kolejność operacji , zgodnie z którą stosuje się przed ; to znaczy jest
W porównaniu z pierścieniem , półpierścień pomija wymaganie odwrotności przy dodawaniu; oznacza to, że wymaga tylko przemiennego monoidu , a nie przemiennej grupy . W pierścieniu wymóg odwrotności dodatku implikuje istnienie zera multiplikatywnego, więc tutaj musi być wyraźnie określony. Jeśli mnożenie półpierścienia jest przemienne , nazywa się je przemiennym półpierścieniem .
Niektórzy autorzy wolą pominąć wymóg, aby semiring miał 0 lub 1. To sprawia, że analogia między ringiem i semiringiem z jednej strony, a grupą i semigroupą z drugiej strony przebiega sprawniej. Autorzy ci często używają platformy dla zdefiniowanego tutaj pojęcia.
Teoria
Teorię algebr (asocjacyjnych) nad pierścieniami przemiennymi można uogólnić bezpośrednio do teorii algebr nad półpierścieniami przemiennymi.
Półpierścień, w którym każdy element jest addytywnym idempotentnym (czyli dla wszystkich elementów ) nazywa się an idempotentny semiring . Idempotentne semiringi są specyficzne dla teorii semiringów, ponieważ każdy idempotentny semiring, który jest jednocześnie pierścieniem, jest w rzeczywistościtrywialny. Można zdefiniowaćporządek częściowy na idempotentnym semiringu, ustawiająckiedykolwiek(lub równoważnie, jeśli istniejetaki, że). Najmniej elementemw odniesieniu do tego celu jestco oznacza, żedla wszystkichdodawania i mnożenia respektować kolejność w tym sensie, żezakładaii
Aplikacje
Te i tropikalne semirings dotyczące liczb rzeczywistych, są często stosowane w ocenie wyników na dyskretnych układów zdarzeń. Liczby rzeczywiste to wtedy „koszty” lub „czas przybycia”; operacja „max” odpowiada konieczności oczekiwania na wszystkie warunki wstępne zdarzenia (a tym samym maksymalny czas), podczas gdy operacja „min” odpowiada możliwości wybrania najlepszego, mniej kosztownego wyboru; a + odpowiada akumulacji wzdłuż tej samej ścieżki.
Algorytm Floyda-Warshalla dla najkrótszych ścieżek mogą być tak sformułowane jako obliczenia nad Algebra. Podobnie algorytm Viterbiego do znajdowania najbardziej prawdopodobnej sekwencji stanów odpowiadającej sekwencji obserwacji w modelu ukrytego Markowa można również sformułować jako obliczenie na algebrze prawdopodobieństw. Te dynamiczne algorytmy programowania opierają się na właściwościach rozdzielczych powiązanych z nimi półpierścieni, aby obliczać ilości na dużej (prawdopodobnie wykładniczej) liczbie terminów bardziej efektywnie niż wyliczanie każdego z nich.
Przykłady
Z definicji każdy pierścień jest również półpierścieniem. Motywującym przykładem semiringu jest zbiór liczb naturalnych (w tym liczba zero ) przy zwykłym dodawaniu i mnożeniu. Podobnie nieujemne liczby wymierne i nieujemne liczby rzeczywiste tworzą półpierścienie. Wszystkie te półpierścienie są przemienne.
Ogólnie
- Zbiór wszystkich ideałów danego pierścienia tworzy idempotentny semiring pod wpływem dodawania i mnożenia ideałów.
- Dowolny kwant jednostkowy jest idempotentnym semiringiem przy łączeniu i mnożeniu.
- Każda ograniczona, dystrybucyjna krata jest przemiennym, idempotentnym półpierścieniem w połączeniu i spotkaniu.
- W szczególności algebra Boole'a jest takim półpierścieniem. Logiczny pierścień jest także semiring (w istocie, pierścień), ale nie jest idempotentnych pod dodatkowo . Boolean semiring jest semiring izomorficzna do subsemiring z algebry Boole'a.
- Normalna siatka skośna w pierścieniu jest idempotentnym półpierścieniem dla operacji mnożenia i nabla, gdzie ta ostatnia operacja jest zdefiniowana przez
- Każdy c-semiring to także semiring, w którym dodawanie jest idempotentne i definiowane na dowolnych zbiorach.
- Klasy izomorfizmu obiektów w dowolnej kategorii dystrybucyjnej , w ramach operacji koproduktu i produktu , tworzą półpierścień znany jako platforma Burnside. Zestaw Burnside to pierścień wtedy i tylko wtedy, gdy kategoria jest banalna .
Semiring zestawów
Semiring ( zestawów ) jest niepusty zbiór podzbiorów w taki sposób,
- Jeśli i wtedy
- Jeśli i wtedy istnieje skończona liczba wzajemnie rozłącznych zbiorów dla takich, że
Warunki (2) i (3) wraz z implikują, że takie półpierścienie są używane w teorii miary . Przykładem semiringu zbiorów jest zbiór na wpół otwartych, na wpół zamkniętych interwałów rzeczywistych
A semialgebra nato semiring że majako element.
Konkretne przykłady
- Odnośnej (ujemna) kończące frakcji w pozycyjnym systemie liczbowym do danej podstawy Mamy jeśli dzieli ponadto ma pierścień wszystkich frakcji końcowe do podstawy i jest gęsta w za
- Te wydłużone liczby naturalne z dodawania i mnożenia przekształcone (a ).
- Biorąc pod uwagę semiring z matrycy semiring z kwadratowych macierzy , tworzą semiring pod zwykłym dodatkiem i mnożenie macierzy i tym semiring macierzy jest generalnie nie przemienne, chociaż mogą być przemienne. Na przykład macierze z wpisami nieujemnymi tworzą półpierścień macierzy.
- Jeśli jest przemienne monoid, zestaw z endomorfizm niemal tworzy semiring, gdzie dodatkiem jest dodatek punktowo i mnożenie jest złożenie funkcji . Zera morfizmem i identyfikatory są odpowiednie elementy obojętne. To nie jest prawdziwy półpierścień, ponieważ skład nie rozkłada się po lewej stronie nad dodawaniem punktowym: Jeśli jest monoidem addytywnym liczb naturalnych otrzymujemy półpierścień liczb naturalnych jak a jeśli z semiringiem otrzymujemy (po przyporządkowaniu każdego morfizmu do macierzy ) półpierścień macierzy kwadratowych o współczynnikach in
- ten Półpierścień Boole'a to półpierścień przemiennyutworzony przezdwuelementową algebrę Boole'ai zdefiniowany przezJest idempotentny i jest najprostszym przykładem półpierścienia, który nie jest pierścieniem. Biorąc pod uwagę dwa zbioryirelacje binarnemiędzyiodpowiadają macierzom indeksowanym przeziz wpisami w semiringu boolowskim,dodawanie macierzyodpowiada połączeniu relacji, amnożenie macierzyodpowiadaskładaniu relacji.
- Dany zbiór zbioru relacji binarnych nad jest semiringiem z dodawaniem sumy (relacji jako zbiorów) i mnożeniem składu relacji . Zero semiringa to pusta relacja, a jego jednostką jest relacja tożsamościowa . Związki te odpowiadają matrycy semiring (rzeczywiście, matryca semialgebra) z matryc kwadratowych indeksowanych przez z wpisów w logiczną semiring, a następnie dodawania i mnożenia są zwykle operacji macierzy, gdy zerowy i urządzenie są zwykle macierz zerowa i tożsamość matrycy .
- Zbiór wielomianów o współczynnikach liczb naturalnych oznaczonych tworzy półpierścień przemienny. W rzeczywistości jest to swobodny półpierścień przemienny na jednym generatorze
- Półkola tropikalne są różnie definiowane. Maksymalnie plus semiring jest przemienne, idempotent semiring z służąc jako semiring dodawania (tożsamości ) i zwykły dodatek (tożsamość 0) służącego jako semiring mnożenia. W alternatywnym sformułowaniu semiring tropikalny jest i min zastępuje max jako operację dodawania. Powiązana wersja ma jako podstawowy zestaw.
- Zbiór liczb kardynalnych mniejszych niż jakakolwiek dana nieskończona liczba kardynalna tworzy półpierścień pod wpływem dodawania i mnożenia kardynalnego. Klasa wszystkich Cardinals o o wewnętrznej modelu tworzą (klasa) semiring pod wewnętrzną (modelu) dodanie główne i mnożenia.
- ten semiring prawdopodobieństwa nieujemnych liczb rzeczywistych przy zwykłym dodawaniu i mnożeniu.
- Dziennika semiring na z dodatkiem podanej przez
- Rodzina (klas równoważności izomorfizmu) klas kombinatorycznych (zbiory policzalnie wielu obiektów o nieujemnych rozmiarach całkowitych takich, że istnieje skończenie wiele obiektów o każdej wielkości) z pustą klasą jako obiektem zerowym, klasa składająca się tylko z pustego jako jednostkę, rozłączną sumę klas jako dodawanie i iloczyn kartezjański klas jako mnożenie.
- Łukasiewicz semiring: odcinkiem z dodatkiem podano przyjmując maksymalną argumentów ( ) i pomnożenie podanych przez pojawia się logiczne wielowartościowym .
- Viterbiego semiring również określona dla zestawu podstawowego i ma równej dodaniem, ale jego namnażanie jest zwykle mnożenia liczb rzeczywistych. Pojawia się w analizie probabilistycznej .
- Mając alfabet (zbiór skończony) Σ, zbiór języków formalnych nad (podzbiory ) jest semiringiem, którego iloczyn indukowany jest przez konkatenację i dodawanie łańcuchów jako unię języków (czyli zwykłą unię jako zbiory). Zero tego semiringu to pusty zbiór (pusty język), a jednostką semiringu jest język zawierający tylko pusty łańcuch .
- Uogólniając poprzedni przykład (przez oglądanie jako wolny monoid nad ), należy przyjąć dowolny monoid; zbiór potęgowy wszystkich podzbiorów tworzy półpierścień w ramach unii mnogościowej jako dodawanie i mnożenie mnogościowe:
- Podobnie, jeśli jest monoid, wówczas zestaw skończonych multisets w tworzy semiring. Oznacza to, że element jest funkcją ; dany element funkcji mówi, ile razy ten element występuje w multizestawie, który reprezentuje. Jednostka dodatku jest stałą funkcją zerową. Urządzenie jest multiplikatywną odwzorowaniem funkcji do i wszystkie inne elementy do Suma podaje się , a produkt jest przez
Wariacje
Kompletne i ciągłe semiringi
Kompletny semiring jest semiring dla których dodatek monoid Jest to kompletny monoid , co oznacza, że ma nieskończonej operację sumy dla każdego zestawu indeksu i że następujący (nieskończonej) rozdzielność musi posiadać:
Przykładami kompletnego semiringu są układ potęgowy monoidu pod sumą i macierzowy semiring nad kompletnym semiringiem.
Ciągły semiring jest zdefiniowana jako ten, dla którego monoid dodatkiem jest ciągły monoid . Oznacza to, że częściowo uporządkowane z najmniejszą górną granicą właściwości i dla których dodawanie i mnożenie uwzględniają porządek i supremę. Półpierścień ze zwykłym dodawaniem, mnożeniem i rozszerzaniem kolejności jest półokrągłym ciągłym.
Każdy ciągły semiring jest kompletny: może to być traktowane jako część definicji.
Półpierścienie gwiazd
Gwiazdy semiring (czasami pisane starsemiring ) jest semiring z dodatkowym operatorem, * spełniających
Kleene algebra jest gwiazdą semiring z dodatkiem idempotent. Są ważne w teorii języków formalnych i wyrażeń regularnych .
Kompletne półpierścienie gwiazd
W kompletnym półpierścieniu gwiazdy operator star zachowuje się bardziej jak zwykła gwiazda Kleene : dla pełnego półpierścienia używamy operatora sumy nieskończonej, aby podać zwykłą definicję gwiazdy Kleene:
Conway semiring
Conway semiring jest gwiazdą semiring zaspokojenie suma-gwiazdkowe i product-gwiazdkowe równania:
Każdy kompletny półpierścień gwiazd jest również półpierścieniem Conwaya, ale odwrotność nie obowiązuje. Przykładem niekompletnego półpierścienia Conwaya jest zbiór rozszerzonych nieujemnych liczb wymiernych ze zwykłym dodawaniem i mnożeniem (jest to modyfikacja przykładu z rozszerzonymi nieujemnymi liczbami rzeczywistymi podanymi w tej sekcji poprzez wyeliminowanie liczb niewymiernych).
Iteracja semiring jest Conway semiring spełniających grupy aksjomatów Conway, związane przez Johna Conwaya do grup gwiezdnych semirings.
Przykłady
Przykłady półksiężyców gwiazdowych obejmują:
- The ( ww ) semiring od relacji binarnych ponad pewnego zestawu podstawowego , w którym dla wszystkich operacji Ta gwiazda jest w rzeczywistości zwrotna i przechodnia zamknięcie od (czyli najmniejsza zwrotna i przechodnia relacja binarna ponad zawierający ).
- semiring języków formalnych jest także pełna gwiazda semiring z operacji gwiazdy pokrywającym się z gwiazdą Kleene (dla sets / językach).
- Zbiór nieujemnych rozszerzonych liczb rzeczywistych wraz ze zwykłym dodawaniem i mnożeniem liczb rzeczywistych jest kompletnym półpierścieniem gwiazdy z operacją na gwiazdę daną przez for (czyli szereg geometryczny ) i for
- Półpierścień logiczny z
- Półpierścień dalej z rozszerzonym dodawaniem i mnożeniem oraz dla
Dioida
Termin dioid (od „podwójnego monoidu”) był używany do oznaczania różnych typów półpierścieni:
- Został użyty przez Kuntzmana w 1972 roku do oznaczenia tego, co obecnie nazywa się semiringiem.
- Użycie oznaczenia podgrupy idempotentnej zostało wprowadzone przez Baccelli et al. w 1992 roku.
- Nazwa „dioid” jest również czasami używana na oznaczenie naturalnie uporządkowanych półpierścieni .
Uogólnienia
Uogólnienie semiringów nie wymaga istnienia multiplikatywnej tożsamości, tak że multiplikacja jest raczej semigrupą niż monoidem. Takie struktury nazywane są hemirings lub pre-semirings . Dalszym uogólnieniem są lewostronne pre-semiringi , które dodatkowo nie wymagają prawostronności (lub prawostronne pre-semiringi , które nie wymagają lewostronności).
Jednak dalszym uogólnieniem są prawie semiringi : oprócz tego, że nie wymagają neutralnego elementu dla produktu lub prawostronnej dystrybucji (lub lewostronnej dystrybucji), nie wymagają dodawania, aby były przemienne. Tak jak liczebniki główne tworzą półpierścień (klasowy), tak liczebniki porządkowe tworzą bliski pierścień , gdy uwzględni się standardowe dodawanie i mnożenie porządkowe . Jednak klasę porządków porządkowych można przekształcić w semiring, rozważając zamiast tego tak zwane operacje naturalne (lub Hessenberg) .
W teorii kategorii , o 2-rig jest kategorią z functorial działań analogicznych do tych z platformy. To, że liczby kardynalne tworzą zestaw, można sklasyfikować, mówiąc, że kategoria zbiorów (lub ogólniej, dowolne toposy ) to zestaw 2-rig.
Zobacz też
- Pierścień zestawów – Rodzina zamknięta pod związkami i dopełnieniami względnymi
- Algebra wyceny
Uwagi
Cytaty
Bibliografia
- Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Problemy ścieżki na wykresach) , Dunod (Paryż)
- François Baccelli , Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronizacja i liniowość (wersja online) , Wiley, 1992, ISBN 0-471-93609-X
- Golan, Jonathan S., Semiringi i ich zastosowania . Zaktualizowana i rozszerzona wersja Teoria półpierścieni, z zastosowaniami w matematyce i informatyce teoretycznej (Longman Sci. Tech., Harlow, 1992, MR 1163371 . Kluwer Academic Publishers, Dordrecht, 1999. XII+381 s. ISBN 0-7923- 5786-8 MR 1746739
- Berstel, Jean; Perrin, Dominik (1985). Teoria kodów . Matematyka czysta i stosowana. 117 . Prasa akademicka. Numer ISBN 978-0-12-093420-1. Zbl 0587.68066 .
- Durrett, Richard (2019). Prawdopodobieństwo: teoria i przykłady (PDF) . Seria Cambridge w matematyce statystycznej i probabilistycznej. 49 (wyd. 5). Cambridge Nowy Jork, NY: Cambridge University Press . Numer ISBN 978-1-108-47368-2. OCLC 110115281 . Źródło 5 listopada 2020 .
- Lothaire, M. (2005). Kombinatoryka stosowana na słowach . Encyklopedia matematyki i jej zastosowań. 105 . Praca zbiorowa Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadii Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman , Gregory Koucherov, Jean-Paul Allouche i Valérie Berthé . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 0-521-84802-4. Zbl 1133.68067 .
- Głazek, Kazimierz (2002). Przewodnik po literaturze dotyczącej semiringów i ich zastosowań w matematyce i informatyce. Z pełną bibliografią . Dordrecht: Akademicki Kluwer. Numer ISBN 1-4020-0717-5. Zbl 1072.16040 .
- Sakarowicz, Jacques (2009). Elementy teorii automatów . Przetłumaczone z francuskiego przez Reubena Thomasa. Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-84425-3. Zbl 1188,68177 .
- Berstel, Jean; Reutenauer, Christophe (2011). Nieprzemienne szeregi wymierne z zastosowaniami . Encyklopedia matematyki i jej zastosowań. 137 . Cambridge: Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-19022-0. Zbl 1250.68007 .
Dalsza lektura
- Golan, Jonathan S. (2003). Semiringi i równania afiniczne nad nimi . Springer Nauka i Media Biznesowe. Numer ISBN 978-1-4020-1358-4. Zbl 1042.16038 .
- Gondran, Michel; Minoux, Michel (2008). Wykresy, dioidy i semiringi: nowe modele i algorytmy . Seria interfejsów do badań operacyjnych/informatyki. 41 . Dordrecht: Springer Science & Business Media. Numer ISBN 978-0-387-75450-5. Zbl 1201.16038 .
- Grillet, Mireille P. (1970). „Stosunki Greena w półpierścieniu” . Port. Matematyka . 29 : 181-195. Zbl 0227.16029 .
- Gunawardena, Jeremy (1998). „Wprowadzenie do idempotencji”. W Gunawardena Jeremy (red.). Idempotencja. Na podstawie warsztatów, Bristol, Wielka Brytania, 3–7 października 1994 (PDF) . Cambridge: Wydawnictwo Uniwersytetu Cambridge . s. 1-49. Zbl 0898.16032 .
- Jipsena, P. (2004). „Od półpierścieni do resztkowych krat Kleene”. Studia Logiki . 76 (2): 291–303. doi : 10.1023/B: STUD.0000032089.54776.63 . S2CID 9946523 . Zbl 1045.03049 .
- Steven Dolan (2013) Zabawa z Semiringami , doi : 10.1145/2500365.2500613