Medio anillo

Un semiring es una estructura algebraica general similar a un ring , pero sin el requisito de la existencia de un elemento opuesto además.

Definiciones

Un conjunto con operaciones binarias y definido en él se llama semiring si se cumplen las siguientes condiciones para cualquier elemento: [1] [2] [3] $S$ $+$ $\cdot$ $a B C$

$\langle S,+\rangle$ es un monoide conmutativo . Es decir, hay propiedades:
- Conmutatividad : $a+b=b+a$
- Asociatividad : $(a+b)+c=a+(b+c)$
- La existencia de un elemento neutro (cero): $a+0=0+a=a$
$\langle S,\cdot \rangle$ es un semigrupo . Es decir, además, existe una propiedad:
- Asociatividad : $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
La multiplicación es distributiva con respecto a la suma:
- Distributividad izquierda: $a\cdot (b+c)=a\cdot b+a\cdot c$
- Distributividad derecha: $(a+b)\cdot c=a\cdot c+b\cdot c$
Propiedad multiplicativa del cero:
- $a\cdot 0=0\cdot a=0$

Para un anillo, no se requiere la última relación, ya que se sigue de las demás; para un semiring, es necesario. La diferencia entre un semiring y un anillo es solo que, por adición, un semiring no forma un grupo conmutativo , sino solo un monoide conmutativo .

Un semicírculo se llama conmutativo si la operación de multiplicación en él es conmutativa : . $a\cdot b=b\cdot a\;\para todo a,b\in S$

Un semiring se llama semiring con una unidad si contiene un elemento neutro por multiplicación (llamado unidad ): . $a\cdot 1=1\cdot a=a\;\forall a\in S$

Se dice que un semianillo es reducible multiplicativamente (o aditivamente ) si se sigue de la igualdad (o, respectivamente, ) que . $\;\para todo a,b,c\en S$ $a\cdot c=b\cdot c$ $a+c=b+c$ $a=b$

Un semiring se llama idempotente si para cualquiera la igualdad $a \ en S$ $a+a=a.$

Ejemplos de semirings

Semiring de números naturales con cero . $\langle {\mathbb {N}}_{0},+,\cdot \rangle$
Semiringeo trivial: $\langle \lbrace 0\rbrace ,+,\cdot \rangle$
Semianillos de dos elementos: , , donde denota la disyunción , y es la operación lógica " exclusiva o " sobre el conjunto $\langle \mathbb {Z} _{2},+,\cdot \rangle$ $\langle {\mathbb B},\oplus,\vee \rangle$ $\vee$ $\oplus$ ${\mathbb B}=\lbraza 0,1\rbraza$
Matrices cuadradas con elementos del semiring de números naturales con cero y operaciones de suma y multiplicación de matrices. Un semiring también está formado por matrices cuadradas con elementos de cualquier semiring. $n\veces n$ $\mathbb{N}_0$
Si es un monoide conmutativo, entonces el conjunto de endomorfismos forma un semicírculo, donde la suma se define puntualmente y la multiplicación se define como una composición de funciones . $A$ $\operatorname {Fin} (A)$ $A$
${\ estilo de visualización \ mathbb {N} [x]}$ - polinomios con coeficientes naturales - forman un semianillo conmutativo; es un semiring conmutativo libre con un único generador . $\{X\}$
Semiring probabilístico: números reales no negativos con las operaciones habituales de suma y multiplicación [2] .
${\ estilo de visualización (\ máximo, +)}$ y son semianillos de números reales, en los que la suma se define como tomar el máximo (respectivamente, el mínimo) y la multiplicación como la suma habitual de números reales. Para el primer caso, el subconjunto debe estar claramente delimitado desde abajo, para el segundo, desde arriba. ${\ estilo de visualización (\ min, +)}$

Aplicaciones

Los anillos idempotentes, especialmente y , se utilizan a menudo en los métodos de evaluación de personal . Los números reales aquí denotan "tiempo de llegada" o "costos", la operación denota la necesidad de esperar todos los requisitos previos para realizar una acción (respectivamente, denota la capacidad de elegir la opción menos costosa) y + denota la adición de tiempo ( costes) al pasar por el mismo camino. ${\ estilo de visualización (\ máximo, +)}$ ${\ estilo de visualización (\ min, +)}$ ${\ estilo de visualización \ máximo}$ ${\ estilo de visualización \ min}$

El algoritmo de Floyd-Warshall para encontrar los caminos más cortos se puede reformular para calcular sobre un álgebra. Además, el algoritmo de Viterbi para encontrar la secuencia de estados más probable en un modelo oculto de Markov se puede reformular para cálculos sobre un álgebra de probabilidades. Estos algoritmos de programación dinámica aprovechan la distributividad de los semianillos correspondientes para calcular propiedades utilizando una gran cantidad de variables (posiblemente exponencialmente grande) de manera más eficiente que enumerando cada una. ${\ estilo de visualización (\ min, +)}$ ${\ estilo de visualización (\ máximo, \ veces)}$

Semiring de conjuntos

Un semiring de conjuntos [4] es un sistema de conjuntos para el cual se cumplen las siguientes condiciones: $S$

$\varnada \en 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 \ puntos \sqcup A_{n}=A$ .

Por lo tanto, el semicírculo de conjuntos contiene el conjunto vacío , está cerrado bajo la intersección , y cualquier diferencia de conjuntos del semicírculo de conjuntos puede representarse como una unión finita de conjuntos disjuntos (disjuntos por pares) que pertenecen a este semicírculo de conjuntos. Tales semianillos se usan a menudo en la teoría de la medida.

Un semiring de conjuntos con una unidad es un semiring de conjuntos con un elemento tal que su intersección con cualquier elemento delsemiring de conjuntos es igual a. Aplicando el método de inducción matemática , podemos ampliar el último punto de la definición: si los conjuntosson elementos de un semiconjunto de conjuntos y subconjuntos del elemento, entonces pueden complementarse con elementos disjuntoshasta. Cualquier anillo conjunto es un semianillo conjunto. El producto directo de semirings de conjuntos es también un semiring de conjuntos. $mi$ $A$ $A$ $A_{1},\puntos,A_{n}$ $A$ $A_{{n+1}},\puntos,A_{m}$ $A$

Notas

↑ Berstel y Perrin (1985)
↑ 1 2 Lothaire (2005) p.211
↑ Sakarovitch (2009) págs.27-28
↑ Noel Vaillant, Extensión de Caratheodory Archivado el 14 de abril de 2016 en Wayback Machine , enprobable.net.

Literatura

François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Sincronización y linealidad (versión en línea) , Wiley, 1992, ISBN 0-471-93609-X
Golan, Jonathan S., Semirings y sus aplicaciones . Versión actualizada y ampliada de La teoría de los semianillos, con aplicaciones a las matemáticas y la informática teórica (Longman Sci. Tech., Harlow, 1992, MR : 1163371 . Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923 -5786-8 SEÑOR : 1746739
Berstel, Jean; Perrine, Dominique. Teoría de códigos (neopr.) . - Academic Press , 1985. - T. 117. - (Matemáticas puras y aplicadas). - ISBN 978-0-12-093420-1 .
Lotario, M.Combinatoria aplicada a las palabras (neopr.) . - Cambridge: Cambridge University Press , 2005. - V. 105. - (Enciclopedia de las Matemáticas y sus Aplicaciones). - ISBN 0-521-84802-4 .