En álgebra abstracta , una red residual es una estructura algebraica que es simultáneamente una red x ≤ y y un monoide x • y que admite operaciones x \ z y z / y , vagamente análogas a la división o implicación, cuando x • y se considera como multiplicación o conjunción, respectivamente. Llamadas respectivamente residuos derechos e izquierdos, estas operaciones coinciden cuando el monoide es conmutativo. El concepto general fue introducido por Morgan Ward y Robert P. Dilworth en 1939. Los ejemplos, algunos de los cuales existían antes del concepto general, incluyen álgebras de Boole , álgebras de Heyting , álgebras de Boole residuales , álgebras de relación y MV-álgebras . Las semirredes residuales omiten la operación de encuentro ∧, por ejemplo, álgebras de Kleene y álgebras de acción .
En matemáticas , una red residual es una estructura algebraica L = ( L , ≤, •, I ) tal que
En (iii), la "mayor y ", al ser una función de z y x , se denota x \ z y se llama residuo derecho de z por x . Piense en ello como lo que queda de z a la derecha después de "dividir" z a la izquierda por x . Dualmente, la "mayor x " se denota z / y y se llama residuo izquierdo de z por y . Una declaración equivalente, 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 una x dada en L , las operaciones unarias x • y x \ son respectivamente los adjuntos inferior y superior de una conexión de Galois en L , y dualmente para las dos funciones • y y / y . Por el mismo razonamiento que se aplica a cualquier conexión de Galois, tenemos otra definición de los residuos, a saber,
junto con el requisito de que x • y sea monótona en x e y . (Cuando se axiomatiza usando (iii) o (iii) la monotonía se convierte en un teorema y por lo tanto no se requiere en la axiomatización). Estos dan un sentido en el que las funciones x • y x \ son pseudoinversas o adjuntas entre sí, y lo mismo 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 equivalentemente como una ecuación, ya sea x ∧ y = x o x ∨ y = y . Esto junto con las ecuaciones que axiomatizan retículos y monoides produce una definición puramente ecuacional de retículos residuales, siempre que las operaciones requeridas se adjunten a la signatura ( L , ≤, •, I ) expandiéndola así a ( L , ∧, ∨, •, I , /, \) . Cuando se organizan de esta manera, los retículos residuales forman una clase o variedad ecuacional , cuyos homomorfismos respetan los residuos así como las operaciones de retículo y monoide. Nótese 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 ser parte de la definición. Esta distributividad necesaria de • sobre ∨ no implica en general la distributividad de ∧ sobre ∨ , es decir, una red residual no necesita ser una red distributiva. Sin embargo, la distributividad de ∧ sobre ∨ se implica cuando • y ∧ son la misma operación, un caso especial de redes residuales 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 e y ← x para y / x , sugeridas por la similitud entre la residuo y la implicación en lógica, con la multiplicación del monoide entendida como una forma de conjunción que no necesita ser conmutativa. Cuando el monoide es conmutativo los dos residuos coinciden. Cuando no es conmutativo, el significado intuitivo del monoide como conjunción y los residuos como implicaciones puede entenderse como teniendo una cualidad temporal: x • y significa x y luego y , x → y significa tenía x (en el pasado) luego y (ahora), e y ← x significa si alguna vez x (en el futuro) entonces y (en ese momento), como lo ilustra el ejemplo de lenguaje natural al final de los ejemplos.
Una de las motivaciones originales para el estudio de las redes residuales fue la red de ideales (bilaterales) de un anillo . Dado un anillo R , los ideales de R , denotados Id( R ) , forman una red completa con la intersección de conjuntos actuando como la operación de encuentro y la "adición ideal" actuando como la operación de unión. La operación monoide • está dada por la "multiplicación 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 están dados por
Vale la pena señalar que {0}/ B y B \{0} son respectivamente los aniquiladores izquierdo y derecho de B . Esta residuación está relacionada con el conductor (o transportador ) en álgebra conmutativa escrita 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 de Boole y las álgebras de Heyting son retículos residuales conmutativos en los que x • y = x ∧ y (de donde la unidad I es el elemento superior 1 del álgebra) y ambos residuos x \ y e y / x son la misma operación, es decir, implicación x → y . El segundo ejemplo es bastante general ya que las álgebras de Heyting incluyen todos los retículos distributivos finitos , así como todas las cadenas u órdenes totales , por ejemplo el intervalo unitario [0,1] en la línea real, o los números enteros y .
La estructura ( Z , min , max , +, 0, −, −) (los enteros con resta para ambos residuos) es una red conmutativa de residuos tal que la unidad del monoide no es el elemento más grande (de hecho, no hay ningún entero más pequeño o más grande), y la multiplicación del monoide no es la operación de encuentro de la red. En este ejemplo, las desigualdades son igualdades porque − (resta) no es simplemente el adjunto o pseudoinverso de + sino el verdadero inverso. Cualquier grupo totalmente ordenado bajo adición, como los racionales o los reales, puede sustituirse por los enteros en este ejemplo. La parte no negativa de cualquiera de estos ejemplos es un ejemplo siempre que min y max se intercambien y − se reemplace por monus , definido (en este caso) de modo que x - y = 0 cuando x ≤ y y, de lo contrario, es una resta ordinaria.
Una clase más general de ejemplos la da el álgebra booleana de todas las relaciones binarias en un conjunto X , a saber, el conjunto potencia de X 2 , hecho un retículo residual tomando la multiplicación monoide • como composición de relaciones y la unidad monoide como la relación identidad I en X que consiste en todos los pares ( x , x ) para x en X . Dadas 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 justo cuando para todo z en X , zRx implica zSy (nótese la conexión con la implicación). El residuo izquierdo es la imagen especular de esto: y ( S / R ) x se cumple justo cuando para todo 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 solo cuando x = 1, mientras que x (</>) y se cumple solo cuando y = 0, lo que demuestra que la residuación de < por > es diferente según residuemos 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 los mismos porque ≤•≥ = ≥•≤, los cuales siempre se cumplen entre todos los x e y (ya que x ≤1≥ y y x ≥0≤ y ).
El álgebra de Boole 2 Σ* de todos los lenguajes formales sobre un alfabeto (conjunto) Σ forma una red de residuos cuya multiplicación de monoides es la concatenación de lenguajes LM y cuya unidad de monoides I es el lenguaje {ε} que consiste únicamente 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 .
La red residual de todas las relaciones binarias en X es finita solo cuando X es finito, y conmutativa solo cuando X tiene como máximo un elemento. Cuando X está vacío, el álgebra es el álgebra de Boole degenerada en la que 0 = 1 = I. La red residual de todos los idiomas en Σ es conmutativa solo cuando Σ tiene como máximo una letra. Es finita solo cuando Σ está vacío, y consiste en los dos idiomas 0 (el idioma vacío {}) y la unidad monoide I = {ε} = 1 .
Los ejemplos que forman un álgebra de Boole tienen propiedades especiales que se tratan en el artículo sobre álgebras de Boole residuales .
En lenguaje natural, las redes residuales formalizan la lógica de "y" cuando se usan con su significado no conmutativo de "y luego". Si x = bet , y = win , z = rich , podemos leer x • y ≤ z como "bet y luego win implica rich". Por los axiomas, esto es equivalente a y ≤ x → z, que significa "win implica had bet entonces rich", y también a x ≤ z ← y, que significa "bet implica if-ever win then rich". Los humanos detectan fácilmente nonsequiturs como "bet implica had win then rich" y "win implica if-ever bet then rich" como equivalentes a la ilusión "win y luego bet implica rich". [ cita requerida ] Los 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 humanos muestran mayor competencia con el razonamiento no clásico que con el clásico (por ejemplo, en lógica de relevancia , la ley de Peirce no es una tautología). [ ¿ relevante? ]
Una semirretícula residual se define de forma casi idéntica a las retículas residuales, omitiendo únicamente la operación de encuentro ∧. Por lo tanto, es una estructura algebraica L = (L, ∨, •, 1, /, \) que satisface todas las ecuaciones de retícula residual especificadas anteriormente, excepto aquellas que contienen una ocurrencia del símbolo ∧. La opción de definir x ≤ y como x ∧ y = x no está disponible, quedando únicamente la otra opción x ∨ y = y (o cualquier equivalente de la misma).
Cualquier red residual puede convertirse en una semirretícula residual simplemente omitiendo ∧. Las semirretículas residuales surgen en conexión con las álgebras de acción , que son semirretículas residuales que también son álgebras de Kleene , para las cuales ∧ normalmente no se requiere.
