Félgyűrűt

A félgyűrű egy általános algebrai struktúra, amely hasonló a gyűrűhöz , de anélkül, hogy szükség lenne egy ellentétes elem létezésére.

Definíciók

A bináris műveleteket tartalmazó és azon definiált halmazt félgyűrűnek nevezzük, ha bármely elemre teljesülnek a következő feltételek: [1] [2] [3] $S$ $+$ $\cdot$ $ABC$

$\langle S,+\rangle$ egy kommutatív monoid . Vagyis vannak tulajdonságok:
- Kommutativitás : $a+b=b+a$
- Aszociativitás : $(a+b)+c=a+(b+c)$
- Semleges elem (nulla) létezése : $a+0=0+a=a$
$\langle S,\cdot \rangle$ egy félcsoport . Vagyis van még egy tulajdonság:
- Aszociativitás : $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
A szorzás distributív az összeadás tekintetében:
- Baloldali eloszlás: $a\cdot (b+c)=a\cdot b+a\cdot c$
- Helyes eloszlás: $(a+b)\cdot c=a\cdot c+b\cdot c$
A nulla szorzó tulajdonsága:
- $a\cdot 0=0\cdot a=0$

Gyűrűnél az utolsó reláció nem szükséges, mert a többiből következik, félgyűrűhöz viszont szükséges. A félgyűrű és a gyűrű között csak annyi a különbség, hogy összeadva a félgyűrű nem kommutatív csoportot , hanem csak kommutatív monoidot alkot .

Egy félgyűrűt kommutatívnak nevezünk, ha a szorzás művelete benne kommutatív : . $a\cdot b=b\cdot a\;\forall a,b\in S$

A félgyűrűt egységnyi félgyűrűnek nevezzük, ha szorzás útján semleges elemet tartalmaz (úgynevezett egység ): . $a\cdot 1=1\cdot a=a\;\forall a\in S$

Egy félgyűrűt többszörösen (vagy additívan ) redukálhatónak mondunk, ha az egyenlőségből (illetve ) következik, hogy . $\;\all a,b,c\in S$ $a\cdot c=b\cdot c$ $a+c=b+c$ $a=b$

A félgyűrűt idempotensnek nevezzük , ha az egyenlőségre vonatkozik $a\in S$ $a+a=a.$

Példák félgyűrűkre

Természetes számok felezése nullával . $\langle {\mathbb {N}}_{0},+,\cdot \rangle$
Triviális szemiring: $\langle \lbrace 0\rbrace ,+,\cdot \rangle$
Kételemes félgyűrűk: , , ahol a diszjunkciót jelöli , és a " kizáró vagy " logikai művelet a halmazon $\langle \mathbb {Z} _{2},+,\cdot \rangle$ $\langle {\mathbb B},\oplus ,\vee \rangle$ $\vee$ $\oplus$ ${\mathbb B}=\lkapcsos zárójel 0,1\rkapcsos zárójel$
Négyzetes mátrixok természetes számok félig osztásából származó elemekkel nulla és mátrix összeadási és szorzási műveletekkel. A félgyűrűt olyan négyzetmátrixok is alkotják, amelyek bármely félgyűrűből származó elemeket tartalmaznak. $n\szer n$ $\mathbb{N}_0$
Ha egy kommutatív monoid, akkor az endomorfizmusok halmaza egy félgyűrűt alkot, ahol az összeadást pontonként, a szorzást pedig függvények összetételeként definiáljuk . $A$ $\operatorname {End} (A)$ $A$
$\mathbb {N} [x]$ - természetes együtthatós polinomok - kommutatív félgyűrűt alkotnak; egy ingyenes kommutatív félgyűrű egyedi generátorral . $\{x\}$
Valószínűségi félig számolás - nem negatív valós számok a szokásos összeadás és szorzás műveletekkel [2] .
$(\max ,+)$ és valós számok félgyűrűi, amelyekben az összeadás a maximum (illetve a minimum) felvétele, a szorzás pedig a valós számok szokásos összeadása. Az első esetben az alhalmazt egyértelműen alulról, a másodiknál felülről kell határolni. $(\min ,+)$

Alkalmazások

Idempotens gyűrűket, különösen és gyakran használják a személyzet értékelési módszereiben . A valós számok itt "érkezési időt" vagy "költségeket" jelölnek, a művelet azt jelzi, hogy ki kell várni a művelet végrehajtásához szükséges összes előfeltételt (illetve a legolcsóbb opció kiválasztásának lehetőségét jelöli), a + pedig az idő hozzáadását ( költségek) ugyanazon az úton haladva. $(\max ,+)$ $(\min ,+)$ $\max$ $\min$

A legrövidebb utak megtalálására szolgáló Floyd-Warshall algoritmus újrafogalmazható -algebrán keresztüli számításokhoz. Ezenkívül a rejtett Markov-modellben a legvalószínűbb állapotsorozat megtalálására szolgáló Viterbi-algoritmus újrafogalmazható a valószínűségek -algebrán keresztüli számításokhoz . Ezek a dinamikus programozási algoritmusok a megfelelő félgyűrűk eloszlását használják ki a tulajdonságok kiszámítására nagy (esetleg exponenciálisan nagy) számú változó felhasználásával hatékonyabban, mint mindegyik felsorolásával. $(\min ,+)$ $(\max ,\times )$

Halmazok félig bontása

A halmazok félgyűrűje [4] olyan halmazrendszer , amelyre a következő feltételek teljesülnek: $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 \ pontok \sqcup A_{n}=A$ .

Így a halmazok félgyűrűje az üres halmazt tartalmazza , metszéspont alatt zárva van , és a halmazok félegyezésétől való tetszőleges halmazkülönbsége ábrázolható az ehhez a halmazfélhez tartozó diszjunkt (páronként diszjunkt) halmazok véges uniójaként. Az ilyen félgyűrűket gyakran használják a mértékelméletben.

Az egységgel rendelkező halmazok félgyűrűje olyan elemmel rendelkező halmazok félgyűrűje, amelynek metszéspontja a halmazok félgyűrűjének bármely elemévelegyenlő. A matematikai indukció módszerét alkalmazvakibővíthetjük a definíció utolsó pontját: ha a halmazokaz elem halmazai és részhalmazai félgyűrűjének elemei, akkor kiegészíthetők diszjunkt elemekkel-ig. Minden beállított gyűrű egy beállított félgyűrű. A halmazok félgyűrűinek közvetlen szorzata egyben halmazok félgyűrűje is. $E$ $A$ $A$ $A_{1},\pontok,A_{n}$ $A$ $A_{{n+1}},\pontok ,A_{m}$ $A$

Jegyzetek

↑ Berstel & Perrin (1985)
↑ 1 2 Lothaire (2005) 211. o
↑ Sakarovitch (2009) 27-28
↑ Noel Vaillant, Caratheodory's Extension archiválva 2016. április 14-én a Wayback Machine -nél , a probability.net oldalon.

Irodalom

François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Szinkronizálás és linearitás (online változat) , Wiley, 1992, ISBN 0-471-93609-X
Golan, Jonathan S., Semirings és alkalmazásaik . A félgyűrűk elmélete frissített és bővített változata , matematikai és elméleti számítástechnikai alkalmazásokkal (Longman Sci. Tech., Harlow, 1992, MR : 1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+ 381N30-799N30-7 pp. -5786-8 MR : 1746739
Berstel, Jean; Perrine, Dominique. Kódelmélet (neopr.) . - Academic Press , 1985. - T. 117. - (Tiszta és alkalmazott matematika). - ISBN 978-0-12-093420-1 .
Lothaire, M.Alkalmazott kombinatorika szavakra (neopr.) . - Cambridge: Cambridge University Press , 2005. - V. 105. - (Matematika és alkalmazásai enciklopédiája). - ISBN 0-521-84802-4 .