Jumătate de inel

Un semiring este o structură algebrică generală similară cu un inel , dar fără cerința existenței unui element opus în plus.

Definiții

O mulțime cu operații binare și definită pe ea se numește semiring dacă sunt îndeplinite următoarele condiții pentru orice element: [1] [2] [3] $S$ $+$ $\cdot$ $a,b,c$

$\langle S,+\rangle$ este un monoid comutativ . Adică există proprietăți:
- Comutativitate : $a+b=b+a$
- Asociativitate : $(a+b)+c=a+(b+c)$
- Existența unui element neutru (zero): $a+0=0+a=a$
$\langle S,\cdot \rangle$ este un semigrup . Adică, în plus, există o proprietate:
- Asociativitate : $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
Înmulțirea este distributivă în raport cu adunarea:
- Distributivitatea stângă: $a\cdot (b+c)=a\cdot b+a\cdot c$
- Distributivitatea corectă: $(a+b)\cdot c=a\cdot c+b\cdot c$
Proprietatea multiplicativă a lui zero:
- $a\cdot 0=0\cdot a=0$

Pentru un inel, ultima relație nu este necesară, deoarece decurge din celelalte; pentru un semi-inel, este necesară. Diferența dintre un semi-inel și un inel este doar că, prin adunare, un semi-inel nu formează un grup comutativ , ci doar un monoid comutativ .

Un semiring se numește comutativ dacă operația de înmulțire în el este comutativă : . $a\cdot b=b\cdot a\;\forall a,b\în S$

Un semi-inel se numește semi-inel cu o unitate dacă conține un element neutru prin înmulțire (numit unitate ): . $a\cdot 1=1\cdot a=a\;\forall a\în S$

Se spune că un semiring este reductibil multiplicativ (sau aditiv ) dacă rezultă din egalitate (sau, respectiv, ) că . $\;\forall a,b,c\in S$ $a\cdot c=b\cdot c$ $a+c=b+c$ $a=b$

Un semiring se numește idempotent dacă pentru orice egalitate $a\în S$ $a+a=a.$

Exemple de semiinele

Semirizarea numerelor naturale cu zero . $\langle {\mathbb {N}}_{0},+,\cdot \rangle$
Semiring trivial: $\langle \lbrace 0\rbrace ,+,\cdot \rangle$
Semirele cu două elemente: , , unde denotă disjuncția și este operația logică „ exclusivă sau ” pe set $\langle \mathbb {Z} _{2},+,\cdot \rangle$ $\langle {\mathbb B},\oplus ,\vee \rangle$ $\vee$ $\oplus$ ${\mathbb B}=\lbrace 0,1\rbrace$
Matrici pătrate cu elemente din semicercul numerelor naturale cu zero și operații de adunare și înmulțire matrice. Un semiinel este, de asemenea, format din matrici pătrate cu elemente din orice seminel. $n\ ori n$ $\mathbb{N}_0$
Dacă este un monoid comutativ, atunci mulțimea de endomorfisme formează un semiinel, unde adunarea este definită punctual, iar înmulțirea este definită ca o compoziție de funcții . $A$ $\operatorname {End} (A)$ $A$
$\mathbb {N} [x]$ - polinoame cu coeficienți naturali - formează un semicerc comutativ; este un semiring comutativ liber cu un generator unic . $\{X\}$
Semicerc probabilistic - numere reale nenegative cu operațiile uzuale de adunare și înmulțire [2] .
$(\max ,+)$ și sunt semiinele de numere reale, în care adunarea este definită ca luând maximul (respectiv, minimul) și înmulțirea ca adunare obișnuită a numerelor reale. Pentru primul caz, submulțimea trebuie să fie clar delimitată de jos, pentru al doilea - de sus. $(\min ,+)$

Aplicații

Inelele idempotente, în special și , sunt adesea folosite în metodele de evaluare a personalului . Numerele reale denotă aici „ora de sosire” sau „costuri”, operația denotă necesitatea de a aștepta toate condițiile prealabile pentru a efectua o acțiune (respectiv, denotă capacitatea de a alege opțiunea cea mai puțin costisitoare) și + indică adăugarea timpului ( costuri) la trecerea pe aceeași cale. $(\max ,+)$ $(\min ,+)$ $\max$ $\min$

Algoritmul Floyd-Warshall pentru găsirea celor mai scurte căi poate fi reformulat pentru calcul pe o -algebră. De asemenea, algoritmul Viterbi pentru găsirea celei mai probabile secvențe de stări într-un model Markov ascuns poate fi reformulat pentru calcule pe o -algebră a probabilităților. Acești algoritmi de programare dinamică exploatează distributivitatea semiringelor corespunzătoare pentru a calcula proprietăți prin utilizarea unui număr mare (posibil exponențial mare) de variabile mai eficient decât prin enumerarea fiecăreia. $(\min ,+)$ $(\max ,\times )$

Semiring de seturi

Un semiring de mulțimi [4] este un sistem de mulțimi pentru care sunt îndeplinite următoarele condiții: $S$

$\varnothing \in S$ ;
$\forall 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 \ puncte \sqcup A_{n}=A$ .

Astfel, seminelul de mulțimi conține mulțimea goală , este închis sub intersecție și orice diferență de mulțimi față de seminelul de mulțimi poate fi reprezentată ca o uniune finită a mulțimilor disjunse (disjunctive în perechi) aparținând acestui seminel de mulțimi. Astfel de semiinele sunt adesea folosite în teoria măsurării.

Un semi-inel de mulțimi cu o unitate este un semi-inel de mulțimi cu un element astfel încât intersecția sa cu orice element alcercului de mulțimi este egală cu. Aplicând metoda inducției matematice , putem extinde ultimul punct al definiției: dacă mulțimilesunt elemente ale unui semicerc de mulțimi și submulțimi ale elementului, atunci ele pot fi completate cu elemente disjunctivepână la. Orice inel setat este un semiring setat. Produsul direct al semiinelelor de seturi este, de asemenea, un seminel de seturi. $E$ $A$ $A$ $A_{1},\puncte ,A_{n}$ $A$ $A_{{n+1}},\puncte ,A_{m}$ $A$

Note

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

Literatură

François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (versiune online) , Wiley, 1992, ISBN 0-471-93609-X
Golan, Jonathan S., Semirings și aplicațiile lor . Versiune actualizată și extinsă a Teoriei semiringelor, cu aplicații la matematică și informatică teoretică (Longman Sci. Tech., Harlow, 1992, MR : 1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923 -5786-8 MR : 1746739
Berstel, Jean; Perrine, Dominique. Teoria codurilor (neopr.) . - Academic Press , 1985. - T. 117. - (Matematică pură și aplicată). - ISBN 978-0-12-093420-1 .
Lothaire, M.Combinatorică aplicată asupra cuvintelor (neopr.) . - Cambridge: Cambridge University Press , 2005. - V. 105. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-84802-4 .