Lógica residuada - Enciclopedia

En la álgebra abstracta, un anillo residuado es una estructura algebraica que es simultáneamente un anillo x ≤ y y un monoido x•y que admite operaciones x\z y z/y, de manera imprecisa análogas a la división o la implicación, cuando x•y se ve como multiplicación o conjunción, respectivamente. Llamadas respectivamente residuales derechas e izquierdas, estas operaciones coinciden cuando el monoido es conmutativo. El concepto general fue introducido por Morgan Ward y Robert P. Dilworth en 1939. Ejemplos, algunos de los cuales existían antes del concepto general, incluyen álgebras booleanas, álgebras de Heyting, álgebras booleanas residuadas, álgebras de relaciones y álgebras MV. Los semialgebras residuadas omiten la operación de intersección ∨, por ejemplo, álgebras de Kleene y álgebras de acción.


Definición
En matemáticas, un anillo residuado es una estructura algebraica L = (L, ≤, •, I) tal que

(i) (L, ≤) es un anillo.
(ii) (L, •, I) es un monoido.
(iii) Para todos z hay para cada x un y mayor, y para cada y un x mayor, tales que x•y ≤ z (propiedades de residuo).
En (iii), el "y mayor", siendo una función de z y x, se denota x\z y se llama residuo derecho de z por x. Piensa en él como lo que queda de z a la derecha después de "dividir" z a la izquierda por x. Dualmente, el "x mayor" se denota z/y y se llama residuo izquierdo de z por y. Una declaración equivalente y más formal de (iii) que utiliza estas operaciones para nombrar estos valores máximos es
(iii)' para todos x, y, z en L, y ≤ x\z ⇔ x•y ≤ z ⇔ x ≤ z/y.
Como sugiere la notación, los residuos son una forma de cociente. Más precisamente, para un x dado en L, las operaciones unarias x• y x\ son respectivamente los adjuntos inferiores y superiores de una conexión Galois en L, y de manera dual para las dos funciones •y y /y. Por la misma razón que se aplica a cualquier conexión Galois, tenemos otra definición de los residuos, namely,

x•(x\y) ≤ y ≤ x\(x•y), y
(y/x)•x ≤ y ≤ (y•x)/x,
junto con la condición de que x•y sea monótono en x y y. (Cuando se axiomatiza utilizando (iii) o (iii)' la monotonía se convierte en un teorema y por lo tanto no es requerida en la axiomatización.) Estos proporcionan un sentido en el que las funciones x• y x\ son inversos pseudoinversos o adjuntos de cada otra, y de manera similar para •x y /x.
Esta última definición es puramente en términos de desigualdades, notando que la monotonía puede axiomatizarse como x • y ≤ (x∨z) • y y de manera similar para las otras operaciones y sus argumentos. Además, cualquier desigualdad x ≤ y puede expresarse equivalente como una ecuación, ya sea x∧y = x o x∨y = y. Esto junto con las ecuaciones que axiomatizan los anillos y los monoidos entonces proporciona una definición puramente equacional de los anillos residuados, siempre que se adjunten las operaciones necesarias a la firma (L, ≤, •, I) expandiéndola a (L, ∧, ∨, •, I, /, \). Cuando se organiza de esta manera, los anillos residuados forman una clase o variedad equacional, cuyos homomorfismos respetan los residuos así como las operaciones de anillo y monoido. Notar que la distributividad x • (y ∨ z) = (x • y) ∨ (x • z) y x•0 = 0 son consecuencias de estos axiomas y por lo tanto no necesitan incluirse en la definición. Esta necesaria distributividad de • sobre ∨ no implica generalmente la distributividad de ∧ sobre ∨, es decir, un anillo residuado no necesita ser un anillo distributivo. Sin embargo, la distributividad de ∧ sobre ∨ se implica cuando • y ∧ son la misma operación, un caso especial de los anillos residuados llamado álgebra de Heyting.
Las notaciones alternativas para x•y incluyen x◦y, x;y (álgebra de relaciones) y x⊗y (lógica lineal). Las alternativas para I incluyen e y 1'. Las notaciones alternativas para los residuos son x → y para x\y y y ← x para y/x, sugeridas por la semejanza entre el residuo y la implicación en la lógica, con la multiplicación del monoido entendida como una forma de conjunción que no necesita ser conmutativa. Cuando el monoido es conmutativo, los dos residuos coinciden. Cuando no es conmutativo, el significado intuitivo del monoido como conjunción y los residuos como implicaciones pueden entenderse como teniendo una cualidad temporal: x•y significa x y luego y, x → y significa si x (en el pasado) entonces y (ahora), y y ← x significa si alguna vez x (en el futuro) entonces y (en ese momento), como ilustra el ejemplo de lenguaje natural al final de los ejemplos.


Ejemplos
Una de las motivaciones originales para el estudio de los anillos residuados fue el anillo de (ideales de dos lados) de un anillo. Dado un anillo R, los ideales de R, denotados Id(R), forman un anillo completo con la intersección de conjunto actuando como la operación de intersección y "adición de ideal" actuando como la operación de unión. La operación de monoido • se da por "multiplicación de ideal", y el elemento R de Id(R) actúa como la identidad para esta operación. Dados dos ideales A y B en Id(R), los residuos se dan por



A

/

B
:=
{
r
∈
R
∣
r
B
⊆
A
}


{\displaystyle A/B:=\{r\in R\mid rB\subseteq A\}}




B
∖
A
:=
{
r
∈
R
∣
B
r
⊆
A
}


{\displaystyle B\setminus A:=\{r\in R\mid Br\subseteq A\}}


Es digno de mencionar que {0}/B y B\{0} son respectivamente el aniquilador izquierdo y derecho de B. Este residuo está relacionado con el conductor (o transportador) en álgebra conmutativa escrito como (A:B)=A/B. Una diferencia en el uso es que B no necesita ser un ideal de R: puede ser simplemente un subconjunto.
Las álgebras booleanas y las álgebras de Heyting son anillos residuados conmutativos en los que x•y = x∧y (por lo tanto, el elemento unitario I es el elemento superior 1 del álgebra) y ambas residuales x\y y y/x son la misma operación, es decir, la implicación x → y. El segundo ejemplo es bastante general ya que las álgebras de Heyting incluyen todas las álgebras distributivas finitas, así como todas las cadenas o órdenes totales, por ejemplo, el intervalo unitario [0,1] en la recta real, o los enteros y



±
∞


{\displaystyle \pm \infty }

.
La estructura (Z, min, max, +, 0, −, −) (los enteros con resta para ambas residuales) es un anillo residuado con el elemento unitario del monoido que no es el elemento mayor (de hecho, no hay ningún entero menor o mayor), y la multiplicación del monoido no es la operación de intersección del anillo. En este ejemplo, las desigualdades son igualdades porque − (resta) no es simplemente el adjunto o pseudoinverso de + sino el verdadero inverso. Cualquier grupo total ordenado bajo adición como los racionales o los reales puede sustituirse por los enteros en este ejemplo. La porción no negativa de cualquiera de estos ejemplos es un ejemplo proporcionado que se intercambien min y max y se reemplace − por monus, definido (en este caso) de manera que x-y = 0 cuando x ≤ y y de otro modo es la resta ordinaria.
Una clase más general de ejemplos se da por el álgebra booleana de todas las relaciones binarias en un conjunto X, es decir, el poder conjunto de X2, convertido en un anillo residuado tomando la multiplicación de monoido • como la composición de relaciones y el elemento unitario del monoido como la relación de identidad I en X que consiste en todos los pares (x,x) para x en X. Dados dos relaciones R y S en X, el residuo derecho R\S de S por R es la relación binaria tal que x(R\S)y se cumple cuando para todos z en X, zRx implica zSy (notar la conexión con la implicación). El residuo izquierdo es el espejo de esto: y(S/R)x se cumple cuando para todos z en X, xRz implica ySz.
Esto se puede ilustrar con las relaciones binarias < y > en {0,1} en las que 0 < 1 y 1 > 0 son las únicas relaciones que se cumplen. Entonces x(><)y se cumple cuando x = 1, mientras que x(</>)y se cumple cuando y = 0, mostrando que el residuo de < por > es diferente dependiendo de si residuamos a la derecha o a la izquierda. Esta diferencia es una consecuencia de la diferencia entre <•> y >•<, donde las únicas relaciones que se cumplen son 0(<•>)0 (ya que 0<1>0) y 1(>•<)1 (ya que 1>0<1). Si hubiéramos elegido ≤ y ≥ en lugar de < y >, ≥\≤ y ≤/≥ habrían sido las mismas porque ≤•≥ = ≥•≤, ambos de los cuales siempre se cumplen entre todos x y y (ya que x≤1≥y y x≥0≤y).
El álgebra booleana 2Σ* de todos los lenguajes formales sobre un alfabeto (conjunto) Σ forma un anillo residuado cuyo multiplicación de monoido es la concatenación de lenguajes LM y cuyo elemento unitario I es el lenguaje {ε} que consiste en la cadena vacía ε. El residuo derecho M\L consiste en todas las palabras w sobre Σ tales que Mw ⊆ L. El residuo izquierdo L/M es el mismo con wM en lugar de Mw.
El anillo residuado de todas las relaciones binarias en X es finito cuando X es finito y conmutativo cuando X tiene como máximo un elemento. Cuando X está vacío, el álgebra es el álgebra booleana degenerada en la que 0 = 1 = I. El anillo residuado de todas las lenguajes en Σ es conmutativo cuando Σ tiene como máximo una letra. Es finito cuando Σ está vacío, consistiendo de los dos lenguajes 0 (el lenguaje vacío {}) y el elemento unitario I = {ε} = 1.
Los ejemplos que forman un álgebra booleana tienen propiedades especiales tratadas en el artículo sobre álgebras booleanas residuadas.
En el lenguaje natural, los anillos residuados formalizan la lógica de "y" cuando se utiliza con su significado no conmutativo de "y luego". Estableciendo x = apuesta, y = ganar, z = rico, podemos leer x•y ≤ z como "apuesta y luego ganar implica rico". Según los axiomas, esto es equivalente a y ≤ x→z, que significa "ganar implica si alguna vez apuesta entonces rico", y también a x ≤ z←y, que significa "apuesta implica si alguna vez ganar entonces rico". Los seres humanos detectan fácilmente tales no secuencia como "apuesta implica si alguna vez ganar entonces rico" y "ganar implica si alguna vez apuesta entonces rico" como equivalentes al deseo de pensar "ganar y luego apostar implica rico". Los seres humanos no detectan tan fácilmente que la ley de Peirce ((P→Q)→P)→P es una tautología clásica, una situación interesante en la que los seres humanos muestran más destreza en el razonamiento no clásico que en el clásico (por ejemplo, en la lógica de relevancia, la ley de Peirce no es una tautología).


Semialgebra residuada
Una semialgebra residuada se define casi de la misma manera que para los anillos residuados, omitiendo solo la operación de intersección ∧. Por lo tanto, es una estructura algebraica L = (L, ∨, •, 1, /, \) satisfaciendo todas las ecuaciones del anillo residuado como se especifica anteriormente, excepto aquellas que contienen una ocurrencia del símbolo ∧. La opción de definir x ≤ y como x∧y = x no está disponible, dejando solo la otra opción x∨y = y (o cualquier equivalente). Cualquier anillo residuado puede convertirse en una semialgebra residuada simplemente omitiendo ∧. Las semialgebras residuadas surgen en conexión con las álgebras de acción, que son semialgebras residuadas que también son álgebras de Kleene, para las que ∧ no se requiere ordinariamente.


Véase también
Quantale
Mapeo residuado
Lógica subestructural
Álgebra booleana residuada


Referencias
Ward, Morgan, y Robert P. Dilworth (1939) "Anillos residuados," Trans. Amer. Math. Soc. 45: 335–54. Reimpreso en Bogart, K, Freese, R., y Kung, J., editores (1990) The Dilworth Theorems: Selected Papers of R.P. Dilworth Basel: Birkhäuser.
Nikolaos Galatos, Peter Jipsen, Tomasz Kowalski y Hiroakira Ono (2007), Anillos residuados. Una Perspectiva Algebraica de las Lógicas Subestructurales, Elsevier, ISBN 978-0-444-52141-5.