Halv ring

En semiring er en generel algebraisk struktur, der ligner en ring , men uden kravet om eksistensen af et element modsat derudover.

Definitioner

Et sæt med binære operationer og defineret på det kaldes en semiring, hvis følgende betingelser er opfyldt for nogle elementer: [1] [2] [3] $S$ $+$ $\cdot$ $a,b,c$

$\langle S,+\rangle$ er en kommutativ monoid . Det vil sige, at der er egenskaber:
- Kommutativitet : $a+b=b+a$
- Associativitet : $(a+b)+c=a+(b+c)$
- Eksistensen af et neutralt element (nul): $a+0=0+a=a$
$\langle S,\cdot \rangle$ er en semigruppe . Det vil sige, at der desuden er en ejendom:
- Associativitet : $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
Multiplikation er distributiv med hensyn til addition:
- Venstre fordeling: $a\cdot (b+c)=a\cdot b+a\cdot c$
- Rigtig fordeling: $(a+b)\cdot c=a\cdot c+b\cdot c$
Multiplikativ egenskab af nul:
- $a\cdot 0=0\cdot a=0$

For en ring er det sidste forhold ikke nødvendigt, da det følger af de andre; for en semiring er det nødvendigt. Forskellen mellem en semiring og en ring er kun, at en semiring ved addition ikke danner en kommutativ gruppe , men kun en kommutativ monoid .

En semiring kaldes kommutativ , hvis multiplikationsoperationen i den er kommutativ : . $a\cdot b=b\cdot a\;\foralt a,b\in S$

En semiring kaldes en semiring med en enhed, hvis den indeholder et neutralt element ved multiplikation (kaldet en enhed ): . $a\cdot 1=1\cdot a=a\;\forall a\in S$

En semiring siges at være multiplikativ (eller additivt ) reducerbar , hvis det følger af lighed (eller henholdsvis ) at . $\;\foralt a,b,c\i S$ $a\cdot c=b\cdot c$ $a+c=b+c$ $a=b$

En semiring kaldes idempotent hvis for nogen ligheden $a\i S$ $a+a=a.$

Eksempler på semiringer

Halvdeling af naturlige tal med nul . $\langle {\mathbb {N}}_{0},+,\cdot \rangle$
Triviel semiring: $\langle \lbrace 0\rbrace ,+,\cdot \rangle$
To-element semiringer: , , hvor angiver disjunktionen , og er den logiske operation " eksklusiv eller " på sættet $\langle \mathbb {Z} _{2},+,\cdot \rangle$ $\langle {\mathbb B},\oplus ,\vee \rangle$ $\vee$ $\plus$ ${\mathbb B}=\lbrace 0,1\rbrace$
Kvadratmatricer med elementer fra semiring af naturlige tal med nul- og matrixadditions- og multiplikationsoperationer. En semiring er også dannet af kvadratiske matricer med elementer fra enhver semiring. $n\ gange n$ $\mathbb{N}_0$
Hvis er en kommutativ monoid, danner sættet af endomorfismer en semiring, hvor addition defineres punktvis, og multiplikation defineres som en sammensætning af funktioner . $EN$ $\operatorname {End} (A)$ $EN$
$\mathbb {N} [x]$ - polynomier med naturlige koefficienter - danner en kommutativ semiring; er en gratis kommutativ semiring med en unik generator . $\{x\}$
Probabilistisk semiring - ikke-negative reelle tal med de sædvanlige operationer som addition og multiplikation [2] .
$(\max ,+)$ og er semiringer af reelle tal, hvor addition er defineret som at tage maksimum (henholdsvis minimum), og multiplikation som den sædvanlige addition af reelle tal. For det første tilfælde skal delmængden være klart afgrænset nedefra, for det andet - fra oven. $(\min ,+)$

Ansøgninger

Idempotente ringe, især og , bruges ofte i personalevurderingsmetoder . De reelle tal her angiver "ankomsttid" eller "omkostninger", operationen angiver behovet for at vente på alle forudsætninger for at udføre en handling (henholdsvis betegner evnen til at vælge den billigste løsning) og + angiver tilføjelsen af tid ( omkostninger), når du passerer den samme vej. $(\max ,+)$ $(\min ,+)$ $\max$ $\min$

Floyd-Warshall-algoritmen til at finde korteste veje kan omformuleres til beregning over en -algebra. Viterbi - algoritmen til at finde den mest sandsynlige sekvens af tilstande i en skjult Markov-model kan også omformuleres til beregninger over en -algebra af sandsynligheder. Disse dynamiske programmeringsalgoritmer udnytter fordelingen af de tilsvarende semiringer til at beregne egenskaber ved at bruge et stort (muligvis eksponentielt stort) antal variabler mere effektivt end ved at angive hver enkelt. $(\min ,+)$ $(\max ,\times )$

Semiring af sæt

En semiring af sæt [4] er et system af sæt, for hvilke følgende betingelser er opfyldt: $S$

$\varnothing \i S$ ;
$\foralt A,B\in S\quad A\cap B\in S$ ;
$\forall A\in S,A_{1}\in S\quad A_{1}\subset A\Rightarrow \exists A_{2},\dots ,A_{n}\subset A:A_{1}\sqcup \ prikker \sqcup A_{n}=A$ .

Således indeholder semiring af mængder det tomme sæt , er lukket under skæring , og enhver forskel mellem mængder fra semiring af mængder kan repræsenteres som en endelig forening af disjunkte (parvis disjunkte) mængder, der hører til denne semiring af sæt. Sådanne semiringer bruges ofte i målteori.

En semiring af sæt med en enhed er en semiring af sæt med et element, således at dets skæring med ethvert element isemiring af sæt er lig med. Ved at anvende metoden til matematisk induktion kan vi udvide det sidste punkt i definitionen: hvis mængderer elementer i en semiring af mængder og delmængder af elementet, så kan de suppleres med usammenhængende elementerop til. Enhver sætring er et sæt semiring. Det direkte produkt af halveringer af sæt er også en semiring af sæt. $E$ $EN$ $EN$ $A_{1},\dots ,A_{n}$ $EN$ $A_{{n+1}},\dots ,A_{m}$ $EN$

Noter

↑ Berstel & Perrin (1985)
↑ 1 2 Lothaire (2005) s.211
↑ Sakarovitch (2009) s.27-28
↑ Noel Vaillant, Caratheodory's Extension Arkiveret 14. april 2016 på Wayback Machine , på probability.net.

Litteratur

François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (online version) , Wiley, 1992, ISBN 0-471-93609-X
Golan, Jonathan S., Semirings og deres applikationer . Opdateret og udvidet version af The theory of semirings, med anvendelser til matematik og teoretisk datalogi (Longman Sci. Tech., Harlow, 1992, MR : 1163371 . Kluwer Academic Publishers, Dordrecht, 1999. xii+381 0-7923 pp. ISBN -5786-8 MR : 1746739
Berstel, Jean; Perrine, Dominique. Kodeteori (neopr.) . - Academic Press , 1985. - T. 117. - (Ren og anvendt matematik). - ISBN 978-0-12-093420-1 .
Lothaire, M.Anvendt kombinatorik på ord (neopr.) . - Cambridge: Cambridge University Press , 2005. - V. 105. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-84802-4 .