Semianillo

Anillo algebraico que no necesita tener elementos negativos aditivos

En álgebra abstracta , un semianillo es una estructura algebraica . Los semianillos son una generalización de los anillos , que eliminan el requisito de que cada elemento debe tener un inverso aditivo . Al mismo tiempo, 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 de Boole de dos elementos , por ejemplo, con la disyunción lógica como adición. Un ejemplo motivador que no es ni un anillo ni una red es el conjunto de números naturales (incluido el cero) bajo la adición 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 . ${\displaystyle \lor }$ ${\displaystyle \mathbb {N} }$

Terminología

Algunos autores definen los semirings sin el requisito de que haya un o . Esto hace que la analogía entre anillo y semiring por un lado y grupo y semigrupo por otro funcione más fluidamente. Estos autores a menudo usan 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 significar ar i ng sin una identidad multiplicativa . ) ${\displaystyle 0}$ ${\displaystyle 1}$

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

Definición

Un semianillo es un conjunto dotado de dos operaciones binarias llamadas adición y multiplicación, tales que: ^{[5] [6] [7]} ${\displaystyle R}$ ${\displaystyle +}$ ${\displaystyle \cdot ,}$

• ${\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 se vinculan a ambas operaciones:

• Mediante la multiplicación, cualquier elemento queda aniquilado por izquierda y derecha mediante la identidad aditiva:
  • ${\displaystyle 0\cdot a=0}$
  • ${\displaystyle a\cdot 0=0}$
• La multiplicación por izquierda y 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)}$

Notación

El símbolo generalmente se omite de la notación; es decir, simplemente se escribe ${\displaystyle \cdot }$ ${\displaystyle a\cdot b}$ ${\displaystyle ab.}$

De manera similar, un orden de operaciones es convencional, en el que se aplica antes de . Es decir, denota . ${\displaystyle \cdot }$ ${\displaystyle +}$ ${\displaystyle a+b\cdot c}$ ${\displaystyle a+(b\cdot c)}$

Con el propósito de desambiguación, se puede escribir o enfatizar a qué estructura pertenecen las unidades en cuestión. ${\displaystyle 0_{R}}$ ${\displaystyle 1_{R}}$

Si es un elemento de un semianillo y , entonces la multiplicación repetida -veces de por sí mismo se denota , y de manera similar se escribe para la adición repetida -veces. ${\displaystyle x\in R}$ ${\displaystyle n\in {\mathbb {N} }}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$ ${\displaystyle x\,n:=x+x+\cdots +x}$ ${\displaystyle n}$

Construcción de nuevos semirings

El anillo cero con el conjunto subyacente es un semianillo llamado semianillo trivial. Esta trivialidad se puede caracterizar mediante y, por lo tanto, cuando se habla de semianillos no triviales, a menudo se asume silenciosamente como si fuera un axioma adicional. Ahora bien, dado cualquier semianillo, existen varias formas de definir nuevos. ${\displaystyle \{0\}}$ ${\displaystyle 0=1}$ ${\displaystyle 0\neq 1}$

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

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

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

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

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

Los ideales de un semianillo , con sus operaciones estándar sobre el subconjunto, forman un semianillo ordenado en red, simple y sin suma cero. Los ideales de están en biyección con los ideales de . La colección de ideales izquierdos de (y también los ideales derechos) también tienen mucho de esa estructura algebraica, excepto que entonces no funciona como una identidad multiplicativa bilateral. ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$

Si es un semianillo y es un conjunto habitado , denota el monoide libre y los polinomios formales 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 tal que , se escribe . Los subsemianillos libres de suma cero de se pueden utilizar para determinar los subsemianillos de . ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle A^{*}}$ ${\displaystyle R[A^{*}]}$ ${\displaystyle A=\{X\}}$ ${\displaystyle A^{*}=\{\varepsilon ,X,X^{2},X^{3},\dots \}}$ ${\displaystyle R[X]}$ ${\displaystyle R}$ ${\displaystyle R[A^{*}]}$

Dado un conjunto , no necesariamente un singleton, contiguo a un elemento predeterminado del conjunto subyacente a un semianillo, se puede definir el semianillo de funciones parciales de a . ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle R}$

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

Lo anterior no es de ninguna manera una lista exhaustiva de construcciones sistemáticas.

Derivaciones

Las derivaciones de un semianillo son los mapas con y . ${\displaystyle R}$ ${\displaystyle {\mathrm {d} }\colon R\to R}$ ${\displaystyle {\mathrm {d} }(x+y)={\mathrm {d} }(x)+{\mathrm {d} }(y)}$ ${\displaystyle {\mathrm {d} }(x\cdot y)={\mathrm {d} }(x)\cdot y+x\cdot {\mathrm {d} }(y)}$

Por ejemplo, si es la matriz unidad y , entonces el subconjunto de dado por las matrices con es un semianillo con derivación . ${\displaystyle E}$ ${\displaystyle 2\times 2}$ ${\displaystyle U={\bigl (}{\begin{smallmatrix}0&1\\0&0\end{smallmatrix}}{\bigr )}}$ ${\displaystyle {\mathcal {M}}_{2}(R)}$ ${\displaystyle a\,E+b\,U}$ ${\displaystyle a,b\in R}$ ${\displaystyle a\,E+b\,U\mapsto b\,U}$

Propiedades

Una propiedad básica de los semianillos es que no es divisor de cero izquierdo o derecho , y que sino también cuadra a sí mismo, es decir, estos tienen . ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle u^{2}=u}$

Algunas propiedades notables se heredan de las estructuras monoides: los axiomas monoides exigen la existencia de unidades, y por lo tanto el conjunto subyacente a un semianillo no puede estar vacío. Además, el predicado 2-ario definido como , aquí definido para la operación de adición, siempre constituye la relación de preorden canónico correcto. La reflexividad está atestiguada por la identidad. Además, siempre es válido, y por lo tanto cero es el elemento menor con respecto a este preorden. Considerándolo para la adición conmutativa en particular, la distinción de "correcto" puede ignorarse. En los números enteros no negativos , por ejemplo, esta relación es antisimétrica y fuertemente conexa , y por lo tanto, de hecho, un orden total (no estricto) . ${\displaystyle x\leq _{\text{pre}}y}$ ${\displaystyle \exists d.x+d=y}$ ${\displaystyle y\leq _{\text{pre}}y}$ ${\displaystyle 0\leq _{\text{pre}}y}$ ${\displaystyle \mathbb {N} }$

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

Semicampos

Todo cuerpo es también un semicuerpo , que a su vez es un semianillo en el que también existen inversos multiplicativos.

Anillos

Cualquier cuerpo es también un anillo , que a su vez es un semianillo en el que también existen inversos aditivos. Nótese que un semianillo omite tal requisito, es decir, requiere solo un monoide conmutativo , no un grupo conmutativo . El requisito adicional para un anillo en sí mismo ya implica la existencia de un cero multiplicativo. Este contraste es también la razón por la que para la teoría de semianillos, el cero multiplicativo debe especificarse explícitamente.

Aquí , el inverso aditivo de , se eleva al cuadrado a . Como siempre existen diferencias aditivas en un anillo, es una relación binaria trivial en un anillo. ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle d=y-x}$ ${\displaystyle x\leq _{\text{pre}}y}$

Semianillos conmutativos

Un semianillo se llama semianillo conmutativo si también la multiplicación es conmutativa. ^[8] Sus axiomas se pueden enunciar de manera concisa: Consiste en dos monoides conmutativos y en un conjunto tal que y . ${\displaystyle \langle +,0\rangle }$ ${\displaystyle \langle \cdot ,1\rangle }$ ${\displaystyle a\cdot 0=0}$ ${\displaystyle a\cdot (b+c)=a\cdot b+a\cdot c}$

El centro de un semianillo es un subsemianillo y ser conmutativo equivale a ser su propio centro.

El semianillo conmutativo de números naturales es el objeto inicial entre su tipo, lo que significa que existe una estructura única que preserva el mapa en cualquier semianillo conmutativo. ${\displaystyle {\mathbb {N} }}$

Las redes distributivas acotadas son semianillos conmutativos parcialmente ordenados que cumplen ciertas ecuaciones algebraicas relacionadas con la distributividad y la idempotencia. Por lo tanto, también lo son sus duales .

Semianillos ordenados

Las nociones de orden se pueden definir mediante formulaciones estrictas, no estrictas o de segundo orden . Propiedades adicionales como la conmutatividad simplifican los axiomas.

Dado un orden total estricto (también llamado a veces orden lineal, o pseudoorden en una formulación constructiva), entonces, por definición, los elementos positivos y negativos cumplen resp. . Por irreflexividad de un orden estricto, si es un divisor de cero por la izquierda, entonces es falso. Los elementos no negativos se caracterizan por , que entonces se escribe . ${\displaystyle 0<x}$ ${\displaystyle x<0}$ ${\displaystyle s}$ ${\displaystyle s\cdot x<s\cdot y}$ ${\displaystyle \neg (x<0)}$ ${\displaystyle 0\leq x}$

En general, el orden total estricto se puede negar para definir un orden parcial asociado. La asimetría del primero se manifiesta como . De hecho, en matemáticas clásicas, el segundo es un orden total (no estricto) y tal que implica . Del mismo modo, dado cualquier orden total (no estricto), su negación es irreflexiva y transitiva , y esas dos propiedades que se encuentran juntas a veces se denominan cuasiorden estricto. Clásicamente, esto define un orden total estricto; de hecho, el orden total estricto y el orden total se pueden definir en términos uno del otro. ${\displaystyle x<y\to x\leq y}$ ${\displaystyle 0\leq x}$ ${\displaystyle x=0\lor 0<x}$

Recordemos que " " definido anteriormente es trivial en cualquier anillo. La existencia de anillos que admiten un orden no trivial y no estricto muestra que estos no necesariamente tienen que coincidir con " ". ${\displaystyle \leq _{\text{pre}}}$ ${\displaystyle \leq _{\text{pre}}}$

Semianillos idempotentes aditivamente

Un semianillo en el que cada elemento es idempotente aditivo , es decir, para todos los elementos , se denomina semianillo idempotente (aditivamente) . ^[9] Establecer es suficiente. Tenga en cuenta que a veces esto simplemente se llama semianillo idempotente, independientemente de las reglas de multiplicación. ${\displaystyle x+x=x}$ ${\displaystyle x}$ ${\displaystyle 1+1=1}$

En un semianillo de este tipo, es equivalente a y siempre constituye un orden parcial, aquí ahora denotado . En particular, aquí . Por lo tanto, los semianillos idempotentes aditivos son suma cero libres y, de hecho, el único semianillo idempotente aditivo que tiene todos los inversos aditivos es el anillo trivial y, por lo tanto, esta propiedad es específica de la teoría de semianillos. La adición y la multiplicación respetan el orden en el sentido de que implica , y además implica así como , para todos y . ${\displaystyle x\leq _{\text{pre}}y}$ ${\displaystyle x+y=y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\leq 0\leftrightarrow x=0}$ ${\displaystyle x\leq y}$ ${\displaystyle x+t\leq y+t}$ ${\displaystyle s\cdot x\leq s\cdot y}$ ${\displaystyle x\cdot s\leq y\cdot s}$ ${\displaystyle x,y,t}$ ${\displaystyle s}$

Si es aditivamente idempotente, entonces también lo son los polinomios en . ${\displaystyle R}$ ${\displaystyle R[X^{*}]}$

Un semianillo tal que existe una estructura reticular en su conjunto subyacente está ordenado reticularmente si la suma coincide con el encuentro, y el producto se encuentra debajo de la unión . El semianillo ordenado reticularmente de ideales en un semianillo no es necesariamente distributivo con respecto a la estructura reticular. ${\displaystyle x+y=x\lor y}$ ${\displaystyle x\cdot y\leq x\land y}$

Más estrictamente que la idempotencia aditiva, un semianillo se llama simple si y solo si para todos . Entonces también y para todos . Aquí entonces funciona de manera similar a un elemento infinito aditivo. Si es un semianillo idempotente aditivo, entonces con las operaciones heredadas es su subsemianillo simple. Un ejemplo de un semianillo idempotente aditivo que no es simple es el semianillo tropical en con la función máxima 2-aria, con respecto al orden estándar, como adición. Su subsemianillo simple es trivial. ${\displaystyle x+1=1}$ ${\displaystyle x}$ ${\displaystyle 1+1=1}$ ${\displaystyle x\leq 1}$ ${\displaystyle x}$ ${\displaystyle 1}$ ${\displaystyle R}$ ${\displaystyle \{x\in R\mid x+1=1\}}$ ${\displaystyle {\mathbb {R} }\cup \{-\infty \}}$

Un c-semianillo es un semianillo idempotente y con adición definida sobre conjuntos arbitrarios.

Un semianillo idempotente aditivo con multiplicación idempotente, , se denomina semianillo idempotente aditivo y multiplicativo , pero a veces también simplemente semianillo idempotente. Los semianillos conmutativos simples con esa propiedad son exactamente los retículos distributivos acotados con un único elemento mínimo y máximo (que entonces son las unidades). Las álgebras de Heyting son tales semianillos y las álgebras de Boole son un caso especial. ${\displaystyle x^{2}=x}$

Además, dadas dos redes distributivas acotadas, hay construcciones que dan como resultado semianillos conmutativos aditivamente idempotentes, que son más complicados que la simple suma directa de estructuras.

Líneas numéricas

En un modelo del anillo , se puede definir un predicado de positividad no trivial y un predicado como que constituye un orden total estricto, que cumple propiedades como , o clásicamente la ley de tricotomía . Con su adición y multiplicación estándar, esta estructura forma el cuerpo estrictamente ordenado que es Dedekind-completo . Por definición , todas las propiedades de primer orden probadas en la teoría de los reales también son demostrables en la teoría decidible del cuerpo cerrado real . Por ejemplo, aquí es mutuamente excluyente con . ${\displaystyle {\mathbb {R} }}$ ${\displaystyle 0<x}$ ${\displaystyle x<y}$ ${\displaystyle 0<(y-x)}$ ${\displaystyle \neg (x<0\lor 0<x)\to x=0}$ ${\displaystyle x<y}$ ${\displaystyle \exists d.y+d^{2}=x}$

Pero más allá de los cuerpos ordenados, las cuatro propiedades que se enumeran a continuación también siguen siendo válidas en muchos subsemianillos de , incluidos los racionales, los enteros, así como las partes no negativas de cada una de estas estructuras. En particular, los números reales no negativos, los racionales no negativos y los enteros no negativos son tales semianillos. Las dos primeras propiedades son análogas a la propiedad válida en los semianillos idempotentes: La traslación y el escalamiento respetan estos anillos ordenados , en el sentido de que la adición y la multiplicación en este anillo validan ${\displaystyle {\mathbb {R} }}$

• ${\displaystyle (x<y)\,\to \,x+t<y+t}$
• ${\displaystyle (x<y\land 0<s)\,\to \,s\cdot x<s\cdot y}$

En particular, la cuadratura de los elementos preserva la positividad. ${\displaystyle (0<y\land 0<s)\to 0<s\cdot y}$

Tenga en cuenta dos propiedades más que siempre son válidas en un anillo. En primer lugar, trivialmente para cualquier . En particular, la existencia de diferencia aditiva positiva se puede expresar como ${\displaystyle P\,\to \,x\leq _{\text{pre}}y}$ ${\displaystyle P}$

• ${\displaystyle (x<y)\,\to \,x\leq _{\text{pre}}y}$

En segundo lugar, en presencia de un orden tricotómico, los elementos no nulos del grupo aditivo se dividen en elementos positivos y negativos, y la operación de inversión se desplaza entre ellos. Con , se demuestra que todos los cuadrados son no negativos. En consecuencia, los anillos no triviales tienen una unidad multiplicativa positiva, ${\displaystyle (-1)^{2}=1}$

• ${\displaystyle 0<1}$

Habiendo discutido un orden estricto, se deduce que y , etc. ${\displaystyle 0\neq 1}$ ${\displaystyle 1\neq 1+1}$

Semianillos ordenados discretamente

Existen algunas nociones conflictivas de discreción en la teoría del orden. Dado un orden estricto en un semianillo, una de esas nociones se da al ser positivo y cubrir , es decir, no haber ningún elemento entre las unidades, . Ahora bien, en el presente contexto, un orden se llamará discreto si esto se cumple y, además, todos los elementos del semianillo son no negativos, de modo que el semianillo comienza con las unidades. ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle x}$ ${\displaystyle \neg (0<x\land x<1)}$

Denotamos por la teoría de un semianillo conmutativo, discretamente ordenado, que también valida las cuatro propiedades anteriores que relacionan un orden estricto con la estructura algebraica. Todos sus modelos tienen el modelo como su segmento inicial y la incompletitud de Gödel y la indefinibilidad de Tarski ya se aplican a . Los elementos no negativos de un anillo conmutativo, discretamente ordenado , siempre validan los axiomas de . Por lo tanto, un modelo ligeramente más exótico de la teoría está dado por los elementos positivos en el anillo polinomial , con predicado de positividad para definido en términos del último coeficiente distinto de cero, , y como se indicó anteriormente. Mientras que prueba todas las -oraciones que son verdaderas sobre , más allá de esta complejidad se pueden encontrar afirmaciones simples que son independientes de . Por ejemplo, mientras que las -oraciones verdaderas sobre siguen siendo verdaderas para el otro modelo que se acaba de definir, la inspección del polinomio demuestra la -independencia de la -afirmación de que todos los números son de la forma o (" par o impar "). Demostrar que también se puede ordenar de forma discreta demuestra que la afirmación - para un número distinto de cero ("ningún cuadrado racional es igual a ") es independiente. Asimismo, el análisis para demuestra la independencia de algunas afirmaciones sobre la factorización que son verdaderas en . Hay caracterizaciones de primalidad que no son válidas para el número . ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle {\mathbb {Z} }[X]}$ ${\displaystyle p={\textstyle \sum }_{k=0}^{n}a_{k}X^{k}}$ ${\displaystyle 0<p:=(0<a_{n})}$ ${\displaystyle p<q:=(0<q-p)}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle X}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Pi _{2}}$ ${\displaystyle 2q}$ ${\displaystyle 2q+1}$ ${\displaystyle {\mathbb {Z} }[X,Y]/(X^{2}-2Y^{2})}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle x^{2}\neq 2y^{2}}$ ${\displaystyle x}$ ${\displaystyle 2}$ ${\displaystyle {\mathbb {Z} }[X,Y,Z]/(XZ-Y^{2})}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle 2}$

En la otra dirección, a partir de cualquier modelo de se puede construir un anillo ordenado, que entonces tiene elementos que son negativos con respecto al orden, que sigue siendo discreto en el sentido que cubre . Para ello se define una clase de equivalencia de pares a partir del semianillo original. A grandes rasgos, el anillo corresponde a las diferencias de elementos en la antigua estructura, generalizando la forma en que se puede definir el anillo inicial a partir de . Esto, en efecto, suma todos los inversos y entonces el preorden es nuevamente trivial en cuanto a que . ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \forall x.x\leq _{\text{pre}}0}$

Más allá del tamaño del álgebra de dos elementos, ningún semianillo simple comienza con las unidades. El hecho de estar ordenado discretamente también contrasta, por ejemplo, con el ordenamiento estándar en el semianillo de racionales no negativos , que es denso entre las unidades. Por ejemplo, puede estar ordenado, pero no de manera discreta. ${\displaystyle {\mathbb {Q} }_{\geq 0}}$ ${\displaystyle {\mathbb {Z} }[X]/(2X^{2}-1)}$

Números naturales

${\displaystyle {\mathsf {PA}}^{-}}$Además, la inducción matemática da una teoría equivalente a la aritmética de Peano de primer orden . La teoría también es famosa por no ser categórica , pero es, por supuesto, el modelo pretendido. Demuestra que no hay divisores de cero y que es una suma cero libre, por lo que ningún modelo de ella es un anillo. ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}}$

La axiomatización estándar de es más concisa y la teoría de su orden se trata comúnmente en términos del " " no estricto. Sin embargo, simplemente eliminar el potente principio de inducción de esa axiomatización no deja una teoría algebraica viable. De hecho, incluso la aritmética de Robinson , que elimina la inducción pero agrega nuevamente el postulado de existencia del predecesor, no prueba el axioma monoide . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \leq _{\text{pre}}}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle \forall y.(0+y=y)}$

Semianillos completos

Un semianillo completo es un semianillo para el cual el monoide aditivo es un monoide completo , lo que significa que tiene una operación de suma infinitaria para cualquier conjunto de índices y que deben cumplirse las siguientes leyes distributivas (infinitarias): ^{[10] [11] [12]} ${\displaystyle \Sigma _{I}}$ ${\displaystyle I}$

${\displaystyle {\textstyle \sum }_{i\in I}{\left(a\cdot a_{i}\right)}=a\cdot \left({\textstyle \sum }_{i\in I}{a_{i}}\right),\qquad {\textstyle \sum }_{i\in I}{\left(a_{i}\cdot a\right)}=\left({\textstyle \sum }_{i\in I}{a_{i}}\right)\cdot a.}$

Ejemplos de un semianillo completo son el conjunto potencia de un monoide bajo unión y el semianillo matricial sobre un semianillo completo. ^[13] Para semianillos conmutativos, idempotentes aditivamente y simples, esta propiedad está relacionada con redes residuales .

Semianillos continuos

Un semianillo continuo se define de manera similar como aquel cuyo monoide de adición es un monoide continuo . Es decir, parcialmente ordenado con la propiedad de límite superior mínimo y para el cual la adición y la multiplicación respetan el orden y la supremacía. El semianillo con adición, multiplicación y orden habituales extendidos es un semianillo continuo. ^[14] ${\displaystyle \mathbb {N} \cup \{\infty \}}$

Cualquier semianillo continuo es completo: ^[10] esto puede tomarse como parte de la definición. ^[13]

Semianillos de estrella

Un semianillo estelar (a veces escrito starsemiring ) es un semianillo con un operador unario adicional , ^{[9] [11] [15] [16]} que satisface ${\displaystyle {}^{*}}$

${\displaystyle a^{*}=1+aa^{*}=1+a^{*}a.}$

Un álgebra de Kleene es un semianillo en estrella con adición idempotente y algunos axiomas adicionales. Son importantes en la teoría de lenguajes formales y expresiones regulares . ^[11]

Semianillos de estrella completos

En un semianillo estelar completo , el operador estrella se comporta más como la estrella Kleene habitual : para un semianillo completo utilizamos el operador de suma infinitaria para dar la definición habitual de la estrella Kleene: ^[11]

${\displaystyle a^{*}={\textstyle \sum }_{j\geq 0}{a^{j}},}$

dónde

${\displaystyle a^{j}={\begin{cases}1,&j=0,\\a\cdot a^{j-1}=a^{j-1}\cdot a,&j>0.\end{cases}}}$

Téngase en cuenta que los semianillos estelares no están relacionados con el *-álgebra , donde la operación estelar debería considerarse como una conjugación compleja .

Semianillo Conway

Un semianillo de Conway es un semianillo en estrella que satisface las ecuaciones de suma-estrella y producto-estrella: ^{[9] [17]}

${\displaystyle {\begin{aligned}(a+b)^{*}&=\left(a^{*}b\right)^{*}a^{*},\\(ab)^{*}&=1+a(ba)^{*}b.\end{aligned}}}$

Todo semianillo estelar completo es también un semianillo de Conway, ^[18] pero la relación inversa no se cumple. Un ejemplo de semianillo de Conway que no es completo es el conjunto de números racionales no negativos extendidos con la adición y multiplicación habituales (esta es una modificación del ejemplo con números reales no negativos extendidos dado en esta sección mediante la eliminación de números irracionales). ^[11] Un semianillo de iteración es un semianillo de Conway que satisface los axiomas de grupo de Conway, ^[9] asociados por John Conway a los grupos en semianillos estelares. ^[19] ${\displaystyle \mathbb {Q} _{\geq 0}\cup \{\infty \}}$

Ejemplos

• Por definición, cualquier anillo y cualquier semicampo es también un semianillo.
• Los elementos no negativos de un anillo conmutativo, discretamente ordenado, forman un semianillo conmutativo, discretamente ordenado (en el sentido definido anteriormente). Esto incluye los números enteros no negativos . ${\displaystyle \mathbb {N} }$
• También los números racionales no negativos así como los números reales no negativos forman semianillos ordenados conmutativos. ^{[20] [21] [22]} Este último se llamasemiring de probabilidad .^[6]Ninguno de ellos es un anillo o un retículo distributivo. Estos ejemplos también tienen inversos multiplicativos.
• Se pueden construir nuevos semianillos de forma condicional a partir de los existentes, como se ha descrito. Los números naturales extendidos con adición y multiplicación se extendieron de modo que . ^[21] ${\displaystyle \mathbb {N} \cup \{\infty \}}$ ${\displaystyle 0\cdot \infty =0}$
• El conjunto de polinomios con coeficientes naturales, denotados como forma un semianillo conmutativo. De hecho, este es el semianillo conmutativo libre en un solo generador. También se pueden definir polinomios con coeficientes en otros semianillos, como se ha comentado. ${\displaystyle \mathbb {N} [x],}$ ${\displaystyle \{x\}.}$
• Las fracciones terminales no negativas , en un sistema de numeración posicional con una base dada , forman un subsemianillo de los racionales. Se tiene ‍ si divide a . Para , el conjunto es el anillo de todas las fracciones terminales con base y es denso en . ${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}:=\left\{mb^{-n}\mid m,n\in \mathbb {N} \right\}}$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\subseteq {\tfrac {\mathbb {N} }{c^{\mathbb {N} }}}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle |b|>1}$ ${\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)}$ ${\displaystyle b,}$ ${\displaystyle \mathbb {Q} }$
• El semianillo logarítmico con adición dada por con multiplicación del elemento cero y el elemento unidad ^[6] ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$ ${\displaystyle +,}$ ${\displaystyle +\infty ,}$ ${\displaystyle 0.}$

De manera similar, en presencia de un orden apropiado con elemento inferior,

• Los semianillos tropicales se definen de diversas formas. El semianillo máximo-plus es un semianillo conmutativo con que sirve como adición de semianillos (identidad ) y la adición ordinaria (identidad 0) que sirve como multiplicación de semianillos. En una formulación alternativa, el semianillo tropical es y min reemplaza a max como operación de adición. ^[23] Una versión relacionada tiene como conjunto subyacente. ^{[6] [10]} Son un área activa de investigación, que vincula variedades algebraicas con estructuras lineales por partes . ^[24] ${\displaystyle \mathbb {R} \cup \{-\infty \}}$ ${\displaystyle \max(a,b)}$ ${\displaystyle -\infty }$ ${\displaystyle \mathbb {R} \cup \{\infty \},}$ ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$
• El semianillo de Łukasiewicz : el intervalo cerrado con adición de y dada por tomando el máximo de los argumentos ( ) y multiplicación de y dada por aparece en la lógica multivaluada . ^[11] ${\displaystyle [0,1]}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \max(a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \max(0,a+b-1)}$
• El semianillo de Viterbi también se define sobre el conjunto base y tiene como suma el máximo, pero su multiplicación es la multiplicación habitual de números reales. Aparece en el análisis probabilístico . ^[11] ${\displaystyle [0,1]}$

Tenga en cuenta que . Más sobre los semianillos idempotentes aditivos, ${\displaystyle \max(x,x)=x}$

• El conjunto de todos los ideales de un semianillo dado forman un semianillo bajo la suma y multiplicación de ideales.
• Cualquier red distributiva acotada es un semianillo conmutativo bajo uniones y encuentros. Un álgebra de Boole es un caso especial de estos. Un anillo de Boole es también un semianillo (de hecho, un anillo) pero no es idempotente bajo la adición . Un semianillo de Boole es un semianillo isomorfo a un subsemianillo de un álgebra de Boole. ^[20]
• El semianillo conmutativo formado por el álgebra de Boole de dos elementos y definido por . También se le llama ${\displaystyle 1+1=1}$Semianillo booleano .^{[6][21][22][9]}Ahora, dados dos conjuntosyrelaciones binariasentreycorresponden a matrices indexadas porycon entradas en el semianillo booleano,la adición de matricescorresponde a la unión de relaciones, yla multiplicación de matricescorresponde ala composición de relaciones.^[25] ${\displaystyle X}$ ${\displaystyle Y,}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$
• Cualquier cuanto unitario es un semianillo bajo unión y multiplicación.
• Una red oblicua normal en un anillo es un semianillo para las operaciones de multiplicación y nabla, donde la última operación se define por ${\displaystyle R}$ ${\displaystyle a\nabla b=a+b+ba-aba-bab}$

Más uso de monoides,

• Se ha descrito la construcción de semianillos a partir de un monoide conmutativo . Como se ha indicado, dado un semianillo , las matrices forman otro semianillo. Por ejemplo, las matrices con entradas no negativas forman un semianillo matricial. ^[20] ${\displaystyle \operatorname {End} (M)}$ ${\displaystyle M}$ ${\displaystyle R}$ ${\displaystyle n\times n}$ ${\displaystyle {\mathcal {M}}_{n}(\mathbb {N} ),}$
• Dado un alfabeto (conjunto finito) Σ, el conjunto de lenguajes formales sobre (subconjuntos de ) es un semianillo con producto inducido por concatenación de cadenas y adición como la unión de lenguajes (es decir, 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] ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}}$
• Generalizando el ejemplo anterior (al verlo como el monoide libre sobre ), tome como cualquier monoide; el conjunto potencia de todos los subconjuntos de forma un semianillo bajo la unión de la teoría de conjuntos como adición y multiplicación de conjuntos: ^[22] ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle M}$ ${\displaystyle \wp (M)}$ ${\displaystyle M}$ ${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}.}$
• De manera similar, si es un monoide, entonces el conjunto de multiconjuntos finitos en forma un semianillo. Es decir, un elemento es una función ; dado un elemento de la función, se indica cuántas veces aparece ese elemento en el multiconjunto que representa. La unidad aditiva es la función de cero constante. La unidad multiplicativa es la función que se aplica a y todos los demás elementos de a La suma está dada por y el producto está dado por ${\displaystyle (M,e,\cdot )}$ ${\displaystyle M}$ ${\displaystyle f\mid M\to \mathbb {N} }$ ${\displaystyle M,}$ ${\displaystyle e}$ ${\displaystyle 1,}$ ${\displaystyle M}$ ${\displaystyle 0.}$ ${\displaystyle (f+g)(x)=f(x)+g(x)}$ ${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

Respecto a conjuntos y abstracciones similares,

• Dado un conjunto, el conjunto de relaciones binarias sobre es un semianillo con adición, la unión (de relaciones como conjuntos) y multiplicación, 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 con entradas en el semianillo booleano, y luego la adición 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 . ${\displaystyle U,}$ ${\displaystyle U}$ ${\displaystyle U}$
• 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 (del modelo interno).
• La familia de (clases de equivalencia de isomorfismo de) clases combinatorias (conjuntos de un número contable de objetos con tamaños enteros no negativos tales que hay un número finito de objetos de cada tamaño) con la clase vacía como el objeto cero, la clase que consiste solo en el conjunto vacío como la unidad, la unión disjunta de clases como adición 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 aparejo de Burnside. ^[27] Un aparejo de Burnside es un anillo si y solo si la categoría es trivial .

Semianillos de estrella

Varias de las estructuras mencionadas anteriormente pueden equiparse con una operación estrella.

• El semianillo de relaciones binarias antes mencionado sobre algún conjunto base en el que para todos Esta operación estrella es en realidad el cierre reflexivo y transitivo de (es decir, la relación binaria reflexiva y transitiva más pequeña sobre que contiene ). ^[11] ${\displaystyle U}$ ${\displaystyle R^{*}=\bigcup _{n\geq 0}R^{n}}$ ${\displaystyle R\subseteq U\times U.}$ ${\displaystyle R}$ ${\displaystyle U}$ ${\displaystyle R.}$
• El semianillo de los lenguajes formales es también un semianillo estrella completo, coincidiendo la operación estrella con la estrella de Kleene (para conjuntos/lenguajes). ^[11]
• El conjunto de números reales extendidos no negativos junto con la adición y multiplicación usual de números reales es un semianillo estrella completo con la operación estrella dada por para (es decir, la serie geométrica ) y para ^[11] ${\displaystyle [0,\infty ]}$ ${\displaystyle a^{*}={\tfrac {1}{1-a}}}$ ${\displaystyle 0\leq a<1}$ ${\displaystyle a^{*}=\infty }$ ${\displaystyle a\geq 1.}$
• El semianillo booleano con ^{[b] [11]} ${\displaystyle 0^{*}=1^{*}=1.}$
• El semicírculo con adición y multiplicación extendidas, y para ^{[b] [11]} ${\displaystyle \mathbb {N} \cup \{\infty \},}$ ${\displaystyle 0^{*}=1,a^{*}=\infty }$ ${\displaystyle a\geq 1.}$

Aplicaciones

Los semirings tropicales y trópicos de los números reales se utilizan a menudo en la evaluación del rendimiento de los sistemas de eventos discretos. Los números reales son entonces los "costos" o el "tiempo de llegada"; la operación "máxima" corresponde a tener que esperar todos los requisitos previos de un evento (tomando así el tiempo máximo), mientras que la operación "mínima" corresponde a poder elegir la mejor opción, la menos costosa; y + corresponde a la acumulación a lo largo del mismo camino. ${\displaystyle (\max ,+)}$ ${\displaystyle (\min ,+)}$

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

Generalizaciones

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. Tales estructuras se denominan hemiringlos [ ^30] o pre-semiringlos ^[31] Otra generalización son los pre-semiringlos izquierdos ^[32] , que además no requieren distributividad derecha (o pre-semiringlos derechos , que no requieren distributividad izquierda).

Otra generalización son los semianillos cercanos : además de no requerir un elemento neutro para el producto, o distributividad derecha (o distributividad izquierda), no requieren que la adición sea conmutativa. Así como los números cardinales forman un semianillo (de clase), los números ordinales forman un semianillo cercano , cuando se tienen en cuenta la adición y la multiplicación ordinales estándar . Sin embargo, la clase de ordinales se puede convertir en un semianillo considerando en su lugar las llamadas operaciones naturales (o de Hessenberg) .

En teoría de categorías , un 2-rig es una categoría con operaciones funcionales análogas a las de un rig. El hecho de que los números cardinales formen un rig se puede categorizar para decir que la categoría de conjuntos (o, de manera más general, cualquier topos ) es un 2-rig.

Véase también

• Anillo de conjuntos  – Familia cerrada bajo uniones y complementos relativos
• Álgebra de valoración  : álgebra que describe el procesamiento de la informaciónPages displaying short descriptions of redirect targets

Notas

1. Para ver un ejemplo, consulte la definición de plataforma en Proofwiki.org
2. Se trata de un semianillo de estrella completo y, por tanto, también de un semianillo de Conway. ^[11]

Citas

1. Głazek (2002), pág. 7
2. Kuntzmann, J. (1972). Théorie des réseaux (gráficos) (en francés). París: Dunod. Zbl  0239.05101.
3. Semianillos para el desayuno, diapositiva 17
4. Baccelli, François Louis; Olsder, Geert Jan; Quadrat, Jean-Pierre; Cohen, Guy (1992). Sincronización y linealidad. Un álgebra para sistemas de eventos discretos . Serie Wiley sobre probabilidad y estadística matemática. Chichester: Wiley. Zbl  0824.93003.
5. Berstel y Perrin (1985), pág. 26
6. Lothaire (2005), pág. 211
7. Sakarovitch (2009), págs. 27-28
8. Lothaire (2005), pág. 212
9. Ésik, Zoltán (2008). "Semirings de iteración". En Ito, Masami (ed.). Desarrollos en teoría del lenguaje. 12.ª conferencia internacional, DLT 2008, Kioto, Japón, 16-19 de septiembre de 2008. Actas . Lecture Notes in Computer Science. Vol. 5257. Berlín: Springer-Verlag . pp. 1-20. doi :10.1007/978-3-540-85780-8_1. ISBN . 978-3-540-85779-2. Código Postal  1161.68598.
10. Kuich, Werner (2011). "Sistemas algebraicos y autómatas pushdown". En Kuich, Werner (ed.). Fundamentos algebraicos en informática. Ensayos dedicados a Symeon Bozapalidis con motivo de su jubilación . Apuntes de clase en informática. Vol. 7020. Berlín: Springer-Verlag . pp. 228–256. ISBN 978-3-642-24896-2.Zbl1251.68135  .​
11. Droste y Kuich (2009), págs. 7-10
12. Kuich, Werner (1990). "Semirings ω-continuous, algebraic systems and pushdown automata". En Paterson, Michael S. (ed.). Automata, Languages ​​and Programming: 17th International Colloquium, Warwick University, Inglaterra, 16-20 de julio de 1990, Proceedings . Apuntes de clase en informática. Vol. 443. Springer-Verlag . págs. 103-110. ISBN 3-540-52826-1.
13. Sakarovitch (2009), pág. 471
14. Ésik, Zoltán; Leiß, Hans (2002). "Forma normal de Greibach en semirings algebraically complete". En Bradfield, Julian (ed.). Lógica informática. 16.º taller internacional, CSL 2002, 11.ª conferencia anual de la EACSL, Edimburgo, Escocia, 22-25 de septiembre de 2002. Actas . Lecture Notes in Computer Science. Vol. 2471. Berlín: Springer-Verlag . pp. 135-150. Zbl  1020.68056.
15. Lehmann, Daniel J. (1977), "Estructuras algebraicas para el cierre transitivo" (PDF) , Theoretical Computer Science , 4 (1): 59–76, doi :10.1016/0304-3975(77)90056-1
16. Berstel y Reutenauer (2011), pág. 27
17. Ésik, Zoltán; Kuich, Werner (2004). "Axiomas ecuacionales para una teoría de autómatas". En Martín-Vide, Carlos (ed.). Lenguajes formales y aplicaciones . Estudios en Fuzziness y Soft Computing. Vol. 148. Berlín: Springer-Verlag . pp. 183–196. ISBN. 3-540-20907-7.Zbl 1088.68117  .
18. Droste y Kuich (2009), pág. 15, Teorema 3.4
19. Conway, JH (1971). Álgebra regular y máquinas finitas . Londres: Chapman and Hall. ISBN 0-412-10620-5.Zbl 0231.94041  .
20. Guterman, Alexander E. (2008). "Funciones de rango y determinante para matrices sobre semianillos". En Young, Nicholas; Choi, Yemon (eds.). Encuestas en matemáticas contemporáneas . Serie de notas de conferencias de la London Mathematical Society. Vol. 347. Cambridge University Press . págs. 1–33. ISBN 978-0-521-70564-6. ISSN  0076-0552. Zbl  1181.16042.
21. Sakarovitch (2009), pág. 28.
22. Berstel y Reutenauer (2011), pág. 4
23. Espira, David; Sturmfels, Bernd (2009) [2004]. "Matemáticas Tropicales". Matemáticas. Mag . 82 (3): 163-173. arXiv : matemáticas/0408099 . doi :10.4169/193009809x468760. S2CID  119142649. Zbl  1227.14051.
24. Espira, David; Sturmfels, Bernd (2009). "Matemáticas Tropicales". Revista Matemáticas . 82 (3): 163-173. doi :10.1080/0025570X.2009.11953615. ISSN  0025-570X. S2CID  15278805.
25. John C. Baez (6 de noviembre de 2001). "Mecánica cuántica sobre un sistema conmutativo". Grupo de noticias : sci.physics.research. Usenet:  [email protected] . Consultado el 25 de noviembre de 2018 .
26. Bard, Gregory V. (2009), Criptoanálisis algebraico, Springer, Sección 4.2.1, "Clases combinatorias", ff., págs. 30-34, ISBN 9780387887579
27. Schanuel SH (1991) Los conjuntos negativos tienen característica y dimensión de Euler. En: Carboni A., Pedicchio MC, Rosolini G. (eds) Category Theory. Lecture Notes in Mathematics, vol 1488. Springer, Berlín, Heidelberg
28. Par (1967), pág. 271.
29. Derniame y Par (1971)
30. Golan (1999), pág. 1, cap. 1
31. Gondran y Minoux (2008), pág. 22, capítulo 1, §4.2.
32. Gondran y Minoux (2008), pág. 20, capítulo 1, §4.1.

Bibliografía

• Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Problemas de trayectoria en gráficos) , París: Dunod
• Baccelli, François ; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre (1992), Sincronización y linealidad (versión en línea), Wiley, ISBN 0-471-93609-X
• Golan, Jonathan S. (1999) Semirings and their applications . Versión actualizada y ampliada de The theory of semirings, with applications to mathematics and theory computer science (La teoría de los semirings, con aplicaciones a las matemáticas y a la informática teórica) (Longman Sci. Tech., Harlow, 1992, MR 1163371). Kluwer Academic Publishers, Dordrecht. xii+381 pp. ISBN 0-7923-5786-8 MR 1746739 
• Berstel, Jean; Perrin, Dominique (1985). Teoría de códigos . Matemáticas puras y aplicadas. Vol. 117. Academic Press. ISBN 978-0-12-093420-1.Zbl 0587.68066  .
• Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0.Zbl 1250.68007  .
• Droste, Manfred; Kuich, Werner (2009), "Capítulo 1: Semirings and Formal Power Series", Manual de autómatas ponderados , págs. 3–28, doi :10.1007/978-3-642-01492-5_1
• Durrett, Richard (2019). Probabilidad: teoría y ejemplos (PDF) . Cambridge Series in Statistical and Probabilistic Mathematics. Vol. 49 (5.ª ed.). Cambridge Nueva York, NY: Cambridge University Press . ISBN 978-1-108-47368-2. OCLC  1100115281 . Consultado el 5 de noviembre de 2020 .
• Folland, Gerald B. (1999), Análisis real: técnicas modernas y sus aplicaciones (2.ª ed.), John Wiley & Sons, ISBN 9780471317166
• Golan, Jonathan S. (1999), Semirings y sus aplicaciones , Dordrecht: Kluwer Academic Publishers, doi :10.1007/978-94-015-9333-5, ISBN 0-7923-5786-8, Sr.  1746739
• Lothaire, M. (2005). Combinatoria aplicada a las palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 105. Un trabajo colectivo de Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche y Valérie Berthé . Cambridge: Cambridge University Press . ISBN. 0-521-84802-4.Zbl 1133.68067  .
• Głazek, Kazimierz (2002). Una guía de la literatura sobre semianillos y sus aplicaciones en matemáticas y ciencias de la información. Con bibliografía completa . Dordrecht: Kluwer Academic. ISBN 1-4020-0717-5.Zbl 1072.16040  .
• Gondran, Michel; Minoux, Michel (2008). Grafos, dioides y semianillos: nuevos modelos y algoritmos . Serie de interfaces de investigación de operaciones/ciencia informática. Vol. 41. Dordrecht: Springer Science & Business Media. ISBN 978-0-387-75450-5.Zbl 1201.16038  .
• Pair, Claude (1967), "Sur des algoritmos pour des problèmes de cheminement dans les graphes finis (Sobre algoritmos para problemas de caminos en gráficos finitos)", en Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) – Theory of Graphs (simposio internacional) , Roma (Italia), julio de 1966: Dunod (París) et Gordon and Breach (Nueva York){{citation}}: CS1 maint: location (link)
• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3.Zbl 1188.68177  .

Lectura adicional

• Golan, Jonathan S. (2003). Semirings and Affine Equations over Them [Anillos semicirculares y ecuaciones afines sobre ellos] . Springer Science & Business Media. ISBN 978-1-4020-1358-4.Zbl 1042.16038  .
• Grillet, Mireille P. (1970). "Relaciones de Green en un semianillo". Port. Math . 29 : 181–195. Zbl  0227.16029.
• Gunawardena, Jeremy (1998). "Una introducción a la idempotencia". En Gunawardena, Jeremy (ed.). Idempotencia. Basado en un taller, Bristol, Reino Unido, 3-7 de octubre de 1994 (PDF) . Cambridge: Cambridge University Press . págs. 1-49. Zbl  0898.16032.
• Jipsen, P. (2004). "De semianillos a redes de Kleene residuales". Studia Logica . 76 (2): 291–303. doi :10.1023/B:STUD.0000032089.54776.63. S2CID  9946523. Zbl  1045.03049.
• Dolan, Steven (2013), "Diversión con semirings" (PDF) , Actas de la 18.ª conferencia internacional ACM SIGPLAN sobre programación funcional , págs. 101-110, doi : 10.1145/2500365.2500613, ISBN 9781450323260, Número de identificación del sujeto  2436826