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 R.x=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 {End} (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 normal sesgada 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}$ matrices form another semiring. For example, the matrices with non-negative entries, ${\displaystyle {\mathcal {M}}_{n}(\mathbb {N} ),}$ form a matrix semiring.^[20]
• Given an alphabet (finite set) Σ, the set of formal languages over ${\displaystyle \Sigma }$ (subsets of ${\displaystyle \Sigma ^{*}}$) is a semiring with product induced by string concatenation${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}}$ and addition as the union of languages (that is, ordinary union as sets). The zero of this semiring is the empty set (empty language) and the semiring's unit is the language containing only the empty string.^[11]
• Generalizing the previous example (by viewing ${\displaystyle \Sigma ^{*}}$ as the free monoid over ${\displaystyle \Sigma }$), take ${\displaystyle M}$ to be any monoid; the power set ${\displaystyle \wp (M)}$ of all subsets of ${\displaystyle M}$ forms a semiring under set-theoretic union as addition and set-wise multiplication: ${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}.}$^[22]
• Similarly, if ${\displaystyle (M,e,\cdot )}$ is a monoid, then the set of finite multisets in ${\displaystyle M}$ forms a semiring. That is, an element is a function ${\displaystyle f\mid M\to \mathbb {N} }$; given an element of ${\displaystyle M,}$ the function tells you how many times that element occurs in the multiset it represents. The additive unit is the constant zero function. The multiplicative unit is the function mapping ${\displaystyle e}$ to ${\displaystyle 1,}$ and all other elements of ${\displaystyle M}$ to ${\displaystyle 0.}$ The sum is given by ${\displaystyle (f+g)(x)=f(x)+g(x)}$ and the product is given by ${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

Regarding sets and similar abstractions,

• Given a set ${\displaystyle U,}$ the set of binary relations over ${\displaystyle U}$ is a semiring with addition the union (of relations as sets) and multiplication the composition of relations. The semiring's zero is the empty relation and its unit is the identity relation.^[11] These relations correspond to the matrix semiring (indeed, matrix semialgebra) of square matrices indexed by ${\displaystyle U}$ with entries in the Boolean semiring, and then addition and multiplication are the usual matrix operations, while zero and the unit are the usual zero matrix and identity matrix.
• The set of cardinal numbers smaller than any given infinite cardinal form a semiring under cardinal addition and multiplication. The class of all cardinals of an inner model form a (class) semiring under (inner model) cardinal addition and multiplication.
• 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 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 )}$ algebra on probabilities. These dynamic programming algorithms rely on the distributive property of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.^[28][29]

A generalization of semirings does not require the existence of a multiplicative identity, so that multiplication is a semigroup rather than a monoid. Such structures are called hemirings^[30] or pre-semirings.^[31] A further generalization are left-pre-semirings,^[32] which additionally do not require right-distributivity (or right-pre-semirings, which do not require left-distributivity).

Yet a further generalization are near-semirings: in addition to not requiring a neutral element for product, or right-distributivity (or left-distributivity), they do not require addition to be commutative. Just as cardinal numbers form a (class) semiring, so do ordinal numbers form a near-semiring, when the standard ordinal addition and multiplication are taken into account. However, the class of ordinals can be turned into a semiring by considering the so-called natural (or Hessenberg) operations instead.

In category theory, a 2-rig is a category with functorial operations analogous to those of a rig. That the cardinal numbers form a rig can be categorified to say that the category of sets (or more generally, any topos) is a 2-rig.

• Ring of sets – Family closed under unions and relative complements
• Valuation algebra – Algebra describing information processingPages displaying short descriptions of redirect targets