Semianillo

En álgebra abstracta , un semianillo es una estructura algebraica . Los semianillos son una generalización de los anillos , ya que prescinden del requisito de que cada elemento tenga un inverso aditivo . Asimismo, los semianillos son una generalización de los retículos distributivos acotados .

El semianillo más pequeño que no es un anillo es el álgebra booleana de dos elementos , por ejemplo con disyunción lógica.${\displaystyle \lor }$como suma. Un ejemplo motivador que no es ni un anillo ni una red es el conjunto de los números naturales.${\displaystyle \mathbb {N} }$(incluido el cero) bajo suma y multiplicación ordinarias. Los semianillos son abundantes porque una operación de multiplicación adecuada surge como la composición de funciones de endomorfismos sobre cualquier monoide conmutativo .

Algunos autores definen semianillos sin el requisito de que exista un${\displaystyle 0}$o${\displaystyle 1}$Esto hace que la analogía entre anillo y semianillo , por un lado, y grupo y semigrupo , por otro, funcione con mayor fluidez. Estos autores suelen usar «rig» para el concepto definido aquí. ^{[ 1 ] [ a ]} ​​Esto se originó como una broma, sugiriendo que los rigs son anillos sin elementos negativos . (Similar a usar «rng» para referirse a un anillo sin una identidad multiplicativa ) .

El término dioide (por "monoide doble") se ha utilizado para referirse a semianillos u otras estructuras. Kuntzmann lo empleó en 1972 para designar un semianillo. ^{[ 2 ]} (Alternativamente, a veces se utiliza para semianillos ordenados naturalmente ^{[ 3 ]} , pero Baccelli et al. también lo emplearon para subgrupos idempotentes en 1992. ^{[ 4 ]} )

Un semianillo es un conjunto${\displaystyle R}$equipado con dos operaciones binarias${\displaystyle +}$y${\displaystyle \cdot ,}$llamadas suma y multiplicación, de tal manera que: ^{[ 5 ] [ 6 ] [ 7 ]}

• ${\displaystyle (R,+)}$es un monoide conmutativo con un elemento identidad llamado${\displaystyle 0}$:
  • ${\displaystyle (a+b)+c=a+(b+c)}$
  • ${\displaystyle 0+a=a}$
  • ${\displaystyle a+0=a}$
  • ${\displaystyle a+b=b+a}$
• ${\displaystyle (R,\,\cdot \,)}$es un monoide con un elemento identidad llamado${\displaystyle 1}$:
  • ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$
  • ${\displaystyle 1\cdot a=a}$
  • ${\displaystyle a\cdot 1=a}$

Además, los siguientes axiomas están relacionados con ambas operaciones:

• Mediante la multiplicación, cualquier elemento es aniquilado por la izquierda y por la derecha por la identidad aditiva:
  • ${\displaystyle 0\cdot a=0}$
  • ${\displaystyle a\cdot 0=0}$
• La multiplicación por la izquierda y por la derecha se distribuye sobre la suma:
  • ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$
  • ${\displaystyle (b+c)\cdot a=(b\cdot a)+(c\cdot a)}$

El anillo cero con conjunto subyacente${\displaystyle \{0\}}$es un semianillo llamado semianillo trivial. Esta trivialidad se puede caracterizar mediante${\displaystyle 0=1}$y así cuando hablamos de semianillos no triviales,${\displaystyle 0\neq 1}$A menudo se da por sentado, como si fuera un axioma adicional. Ahora bien, dado cualquier semianillo, existen varias maneras de definir otros nuevos.

Como se ha señalado, los números naturales${\displaystyle {\mathbb {N} }}$con su estructura aritmética forman un semianillo. Tomando el cero y la imagen de la operación sucesora en un semianillo${\displaystyle R}$, es decir, el conjunto${\displaystyle \{x\in R\mid x=0_{R}\lor \exists p\in Rx=p+1_{R}\}}$junto con las operaciones heredadas, siempre es un subsemirreducción de${\displaystyle R}$.

Si${\displaystyle (M,+)}$es un monoide conmutativo, la composición de funciones proporciona la multiplicación para formar un semianillo: El conjunto${\displaystyle \operatorname {Fin} (M)}$de endomorfismos${\displaystyle M\to M}$forma un semianillo donde la suma se define a partir de la suma puntual en${\displaystyle M}$. El morfismo cero y la identidad son los respectivos elementos neutros. Si${\displaystyle M=R^{n}}$con${\displaystyle R}$un semianillo, obtenemos un semianillo que puede asociarse con el cuadrado${\displaystyle n\times n}$matrices${\displaystyle {\mathcal {M}}_{n}(R)}$con coeficientes en${\displaystyle R}$, el semianillo matricial utilizando las reglas ordinarias de suma y multiplicación de matrices. Dado${\displaystyle n\in {\mathbb {N} }}$y${\displaystyle R}$un semianillo,${\displaystyle {\mathcal {M}}_{n}(R)}$siempre es un semianillo también. Generalmente no es conmutativo incluso si${\displaystyle R}$era conmutativo.

Extensiones de Dorroh : Si${\displaystyle R}$es un semianillo, entonces${\displaystyle R\times {\mathbb {N} }}$con suma y multiplicación punto por punto dadas por${\displaystyle \langle x,n\rangle \bullet \langle y,m\rangle$ :=\langle x\cdot y+(x\,m+y\,n),n\cdot m\rangle } define otro semianillo con unidad multiplicativa${\displaystyle 1_{R\times {\mathbb {N} }}:=\langle 0_{R},1_{\mathbb {N} }\rangle }$. De manera muy similar, si${\displaystyle N}$es cualquier subsemirrelación de${\displaystyle R}$, también se puede definir un semianillo en${\displaystyle R\times N}$, simplemente reemplazando la suma repetida en la fórmula por una multiplicación. De hecho, estas construcciones incluso funcionan bajo condiciones menos estrictas, ya que la estructura${\displaystyle R}$En realidad no es necesario tener una unidad multiplicativa.

Los semianillos sin suma cero son, en cierto sentido, los que están más alejados de ser anillos. Dado un semianillo, se puede añadir un nuevo cero.${\displaystyle 0'}$al conjunto subyacente y así obtener un semianillo libre de suma cero que también carece de divisores cero . En particular, ahora${\displaystyle 0\cdot 0'=0'}$y el antiguo semianillo en realidad no es un subsemianillo. Entonces se puede continuar y adjuntar nuevos elementos "encima" uno a la vez, respetando siempre el cero. Estas dos estrategias también funcionan bajo condiciones menos estrictas. A veces las notaciones${\displaystyle -\infty }$respectivamente.${\displaystyle +\infty }$se utilizan al realizar estas construcciones.

Al añadir un nuevo cero al semianillo trivial, de esta manera, se obtiene otro semianillo que puede expresarse en términos de los conectores lógicos de disyunción y conjunción:${\displaystyle \langle \{0,1\},+,\cdot ,\langle 0,1\rangle \rangle =\langle \{\bot ,\top \},\lor ,\land ,\langle \bot ,\top \rangle \rangle }$. En consecuencia, este es el semianillo más pequeño que no es un anillo. Explícitamente, viola los axiomas de anillo como${\displaystyle \top \lor P=\top }$a pesar de${\displaystyle P}$, es decir${\displaystyle 1}$no tiene inverso aditivo. En la definición autodual , la falla está en${\displaystyle \bot \land P=\bot }$. (Esto no debe confundirse con el anillo${\displaystyle \mathbb {Z} _{2}}$, cuya suma funciona como xor${\displaystyle \veebar }$.) En el modelo de von Neumann de los naturales ,${\displaystyle 0_{\omega }:=\{\}}$,${\displaystyle 1_{\omega }:=\{0_{\omega }\}}$y${\displaystyle 2_{\omega }:=\{0_{\omega },1_{\omega }\}={\mathcal {P}}1_{\omega }}$. El semianillo de dos elementos puede representarse en términos de la unión e intersección de la teoría de conjuntos como${\displaystyle \langle {\mathcal {P}}1_{\omega },\cup ,\cap ,\langle \{\},1_{\omega }\rangle \rangle }$Ahora bien, esta estructura de hecho sigue constituyendo un semianillo cuando${\displaystyle 1_{\omega }}$es reemplazado por cualquier conjunto habitado.

Los ideales en un semicírculo${\displaystyle R}$, con sus operaciones estándar sobre subconjuntos, forman un semianillo reticulado, simple y sin suma cero. Los ideales de${\displaystyle {\mathcal {M}}_{n}(R)}$están en biyección con los ideales de${\displaystyle R}$. La colección de ideales de izquierda de${\displaystyle R}$(y asimismo los ideales correctos) también tienen gran parte de esa estructura algebraica, excepto que entonces${\displaystyle R}$no funciona como una identidad multiplicativa bilateral.

Si${\displaystyle R}$es un semianillo y${\displaystyle A}$es un conjunto habitado ,${\displaystyle A^{*}}$denota el monoide libre y los polinomios formales${\displaystyle R[A^{*}]}$sobre sus palabras forman otro semianillo. Para conjuntos pequeños, los elementos generadores se utilizan convencionalmente para denotar el semianillo polinomial. Por ejemplo, en el caso de un singleton${\displaystyle A=\{X\}}$de tal manera que${\displaystyle A^{*}=\{\varepsilon ,X,X^{2},X^{3},\dots \}}$, escribe uno${\displaystyle R[X]}$. Sub-semirregimientos sin suma cero de${\displaystyle R}$puede utilizarse para determinar subsemirrenos de${\displaystyle R[A^{*}]}$.

Dado un conjunto${\displaystyle A}$, no necesariamente solo un singleton, adjuntando un elemento predeterminado al conjunto subyacente de un semianillo${\displaystyle R}$uno puede definir el semianillo de funciones parciales a partir de${\displaystyle A}$a${\displaystyle R}$.

Dada una derivación${\displaystyle {\mathrm {d} }}$en un semianillo${\displaystyle R}$, otra la operación "${\displaystyle \bullet }$"satisfacción${\displaystyle X\bullet y=y\bullet X+{\mathrm {d} }(y)}$puede definirse como parte de una nueva multiplicación en${\displaystyle R[X]}$, lo que da como resultado otro semianillo.

La lista anterior no es, ni mucho menos, exhaustiva de construcciones sistemáticas.

Una propiedad básica de los semianillos es que${\displaystyle 1}$no es un divisor de cero por la izquierda o por la derecha , y eso${\displaystyle 1}$pero también${\displaystyle 0}$cuadrados a sí mismo, es decir, estos tienen${\displaystyle u^{2}=u}$.

Algunas propiedades notables se heredan de las estructuras monoides: Los axiomas monoides exigen la existencia de unidades, por lo que el conjunto subyacente a un semianillo no puede estar vacío. Además, el predicado 2-ario${\displaystyle x\leq _{\text{pre}}y}$definido como${\displaystyle \exists d.x+d=y}$, aquí definida para la operación de suma, siempre constituye la relación de preorden canónica correcta . Reflexividad${\displaystyle y\leq _{\text{pre}}y}$es presenciado por la identidad. Además,${\displaystyle 0\leq _{\text{pre}}y}$siempre es válido, por lo que cero es el elemento más pequeño con respecto a este preorden. Considerándolo en particular para la suma conmutativa, la distinción de "derecha" puede ser ignorada. En los enteros no negativos${\displaystyle \mathbb {N} }$, por ejemplo, esta relación es antisimétrica y fuertemente conectada , y por lo tanto, de hecho, un orden total (no estricto) .

A continuación se analizan más propiedades condicionales.

• Por definición, cualquier anillo y cualquier semicuerpo es también un semianillo.
• Los elementos no negativos de un anillo conmutativo y discretamente ordenado forman un semianillo conmutativo y discretamente ordenado (en el sentido definido anteriormente). Esto incluye los enteros no negativos.${\displaystyle \mathbb {N} }$.
• Además, los números racionales no negativos , así como los números reales no negativos , forman semianillos ordenados conmutativos. ^{[ 20 ] [ 21 ] [ 22 ]} Este último se denominasemianillo de probabilidad . ^{[ 6 ]} Tampoco son anillos ni retículos distributivos. Estos ejemplos también tienen inversos multiplicativos.
• Se pueden construir nuevos semianillos a partir de los existentes, como se describe. Los números naturales extendidos${\displaystyle \mathbb {N} \cup \{\infty \}}$con la suma y la multiplicación extendidas de modo que${\displaystyle 0\cdot \infty =0}$. ^{[ 21 ]}
• El conjunto de polinomios con coeficientes de números naturales, denotado${\displaystyle \mathbb {N} [x],}$forma un semianillo conmutativo. De hecho, este es el semianillo conmutativo libre sobre un único generador.${\displaystyle \{x\}.}$También se pueden definir polinomios con coeficientes en otros semianillos, como ya se ha comentado.
• Las fracciones terminantes no negativas${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}:=\left\{mb^{-n}\mid m,n\in \mathbb {N} \right\}}$, en un sistema de numeración posicional a una base dada${\displaystyle b\in \mathbb {N} }$, forman un subsemirreligión de los racionales. Uno tiene${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\subseteq {\tfrac {\mathbb {N} }{c^{\mathbb {N} }}}}$si${\displaystyle b}$divide${\displaystyle c}$. Para${\displaystyle |b|>1}$, el conjunto${\displaystyle {\tfrac {\mathbb {Z} _{0}}{b^{\mathbb {Z} _{0}}}}:={\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\cup \left(-{\tfrac {\mathbb {N} _{0}}{b^{\mathbb {N} }}}\right)}$es el anillo de todas las fracciones terminantes a base${\displaystyle b,}$y es denso en${\displaystyle \mathbb {Q} }$.
• El semicírculo de troncos en${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$con adición dada por${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$con multiplicación${\displaystyle +,}$elemento cero${\displaystyle +\infty ,}$y elemento unitario${\displaystyle 0.}$^{[ 6 ]}
• De manera similar, el semianillo tropical max-plus se define utilizando${\displaystyle \mathbb {R} \cup \{-\infty \}}$con${\displaystyle \max(a,b)}$sirviendo como adición de semianillo (identidad)${\displaystyle -\infty }$) y la suma ordinaria (identidad 0) que sirve como multiplicación de semianillo. Asimismo, el semianillo tropical min-plus es${\displaystyle \mathbb {R} \cup \{\infty \},}$y min reemplaza a max como operación de suma. ^{[ 23 ]} Una versión relacionada tiene${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$como el conjunto subyacente. ^{[ 6 ] [ 10 ]} Son un área activa de investigación, que vincula variedades algebraicas con estructuras lineales por partes . ^{[ 24 ]}
• El semianillo de Łukasiewicz : el intervalo cerrado${\displaystyle [0,1]}$con adición de${\displaystyle a}$y${\displaystyle b}$dado tomando el máximo de los argumentos (${\displaystyle \max(a,b)}$) y multiplicación de${\displaystyle a}$y${\displaystyle b}$dado por${\displaystyle \max(0,a+b-1)}$aparece en lógica multivaluada . ^{[ 11 ]}
• El semianillo de Viterbi también se define sobre el conjunto base.${\displaystyle [0,1]}$y tiene el máximo como su suma, pero su multiplicación es la multiplicación usual de números reales. Aparece en el análisis probabilístico . ^{[ 11 ]}

• El conjunto de todos los ideales de un semianillo dado forma un semianillo bajo la suma y la multiplicación de ideales.
• Cualquier retículo distributivo acotado es un semianillo conmutativo bajo las operaciones de unión e intersección. Un álgebra booleana es un caso especial de estos. Un anillo booleano también es un semianillo (de hecho, un anillo), pero no es idempotente bajo la suma . Un semianillo booleano es un semianillo isomorfo a un subsemianillo de un álgebra booleana. ^{[ 20 ]}
• El semianillo conmutativo formado por el álgebra booleana de dos elementos y definido por${\displaystyle 1+1=1}$También se le llama elSemianillo booleano . ^{[ 6 ] [ 21 ] [ 22 ] [ 9 ]} Ahora, dados dos conjuntos${\displaystyle X}$y${\displaystyle Y,}$relaciones binarias entre${\displaystyle X}$y${\displaystyle Y}$corresponden a matrices indexadas por${\displaystyle X}$y${\displaystyle Y}$Con entradas en el semianillo booleano, la suma de matrices corresponde a la unión de relaciones, y la multiplicación de matrices corresponde a la composición de relaciones . ^{[ 25 ]}
• Cualquier cuantal unitario es un semianillo bajo la unión y la multiplicación.
• Una red sesgada normal en un anillo${\displaystyle R}$es un semianillo para las operaciones de multiplicación y nabla, donde esta última operación se define por${\displaystyle a\mathbin {\nabla } b=a+b+ba-aba-bab}$

Más uso de monoides,

• La construcción de semianillos${\displaystyle \operatorname {End} (M)}$de un monoide conmutativo${\displaystyle M}$Se ha descrito. Como se indicó, dé un semianillo.${\displaystyle R}$, el${\displaystyle n\times n}$Las matrices forman otro semianillo. Por ejemplo, las matrices con entradas no negativas,${\displaystyle {\mathcal {M}}_{n}(\mathbb {N} ),}$forman un semianillo matricial. ^{[ 20 ]}
• Dado un alfabeto (conjunto finito) Σ, el conjunto de lenguajes formales sobre${\displaystyle \Sigma }$(subconjuntos de${\displaystyle \Sigma ^{*}}$) es un semianillo con producto inducido por concatenación de cadenas${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}}$y la suma como la unión de lenguajes (es decir, la unión ordinaria como conjuntos). El cero de este semianillo es el conjunto vacío (lenguaje vacío) y la unidad del semianillo es el lenguaje que contiene solo la cadena vacía . ^{[ 11 ]}
• Generalizando el ejemplo anterior (al ver${\displaystyle \Sigma ^{*}}$como el monoide libre sobre${\displaystyle \Sigma }$), llevar${\displaystyle M}$ser cualquier monoide; el conjunto potencia${\displaystyle \wp (M)}$de todos los subconjuntos de${\displaystyle M}$forma un semianillo bajo la unión teórica de conjuntos como suma y multiplicación por conjuntos:${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}.}$^{[ 22 ]}
• De manera similar, si${\displaystyle (M,e,\cdot )}$es un monoide, entonces el conjunto de multiconjuntos finitos en${\displaystyle M}$forma un semianillo. Es decir, un elemento es una función.${\displaystyle f\mid M\to \mathbb {N} }$; dado un elemento de${\displaystyle M,}$La función indica cuántas veces aparece ese elemento en el multiconjunto que representa. La unidad aditiva es la función constante cero. La unidad multiplicativa es la función de mapeo.${\displaystyle e}$a${\displaystyle 1,}$y todos los demás elementos de${\displaystyle M}$a${\displaystyle 0.}$La suma viene dada por${\displaystyle (f+g)(x)=f(x)+g(x)}$y el producto es dado por${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

En lo que respecta a conjuntos y abstracciones similares,

• Dado un conjunto${\displaystyle U,}$el conjunto de relaciones binarias sobre${\displaystyle U}$es un semianillo donde la suma es la unión (de relaciones como conjuntos) y la multiplicación es la composición de relaciones . El cero del semianillo es la relación vacía y su unidad es la relación identidad . ^{[ 11 ]} Estas relaciones corresponden al semianillo matricial (de hecho, semiálgebra matricial) de matrices cuadradas indexadas por${\displaystyle U}$con entradas en el semianillo booleano, y luego la suma y la multiplicación son las operaciones matriciales habituales, mientras que el cero y la unidad son la matriz cero y la matriz identidad habituales .
• El conjunto de números cardinales menores que cualquier cardinal infinito dado forma un semianillo bajo la suma y multiplicación de cardinales. La clase de todos los cardinales de un modelo interno forma un semianillo (de clase) bajo la suma y multiplicación de cardinales (de un modelo interno).
• La familia de clases combinatorias (conjuntos de una cantidad numerable de objetos con tamaños enteros no negativos tales que hay una cantidad finita de objetos de cada tamaño) con la clase vacía como objeto cero, la clase que consiste únicamente en el conjunto vacío como unidad, la unión disjunta de clases como suma y el producto cartesiano de clases como multiplicación. ^{[ 26 ]}
• Las clases de isomorfismo de objetos en cualquier categoría distributiva , bajo operaciones de coproducto y producto , forman un semianillo conocido como un anillo de Burnside. ^{[ 27 ]} Un anillo de Burnside es un anillo si y solo si la categoría es trivial .

El${\displaystyle (\max ,+)}$y${\displaystyle (\min ,+)}$Los semicírculos tropicales en los números reales se utilizan a menudo en la evaluación del rendimiento de sistemas de eventos discretos. Los números reales representan los "costos" o el "tiempo de llegada"; la operación "máx." corresponde a tener que esperar a que se cumplan todos los prerrequisitos de un evento (tomando así el tiempo máximo), mientras que la operación "mín." corresponde a poder elegir la mejor opción, la menos costosa; y el signo + corresponde a la acumulación a lo largo del mismo camino.

El algoritmo de Floyd-Warshall para caminos más cortos puede, por lo tanto, reformularse como un cálculo sobre un${\displaystyle (\min ,+)}$álgebra. De manera similar, el algoritmo de Viterbi para encontrar la secuencia de estados más probable correspondiente a una secuencia de observaciones en un modelo oculto de Markov también puede formularse como un cálculo sobre un${\displaystyle (\max ,\times )}$Álgebra sobre probabilidades. Estos algoritmos de programación dinámica se basan en la propiedad distributiva de sus semianillos asociados para calcular cantidades sobre un gran número (posiblemente exponencial) de términos de manera más eficiente que enumerando cada uno de ellos. ^{[ 28 ] [ 29 ]}

Una generalización de los semianillos no requiere la existencia de una identidad multiplicativa, de modo que la multiplicación es un semigrupo en lugar de un monoide. Estas estructuras se denominan hemirings ^{[ 30 ]} o pre-semirings ^{[ 31 ]} . Una generalización adicional son los pre-semirings izquierdos ^{[ 32 ]} , que además no requieren distributividad derecha (o pre-semirings derechos , que no requieren distributividad izquierda).

Una generalización adicional la constituyen los semianillos casi completos : además de no requerir un elemento neutro para el producto, o distributividad derecha (o izquierda), tampoco requieren que la suma sea conmutativa. Así como los números cardinales forman un semianillo (de clase), los números ordinales forman un semianillo casi completo cuando se consideran la suma y la multiplicación ordinales estándar . Sin embargo, la clase de los ordinales puede transformarse en un semianillo al considerar las llamadas operaciones naturales (o de Hessenberg) .

En teoría de categorías , un 2-rig es una categoría con operaciones funtoriales análogas a las de un rig. Que los números cardinales formen un rig se puede categorizar diciendo que la categoría de conjuntos (o, más generalmente, cualquier topos ) es un 2-rig.

• Anillo de conjuntos – Familia cerrada bajo uniones y complementos relativos 
• Álgebra de valoración : álgebra que describe el procesamiento de la información. Páginas que muestran breves descripciones de los destinos de redireccionamiento.