En álgebra abstracta , un enrejado residuated es una estructura algebraica que es simultáneamente un enrejado x ≤ y y una monoid x • y que admite operaciones x \ z y z / y , vagamente análoga a la división o implicación, cuando x • y es visto como multiplicación o conjunción, respectivamente. Llamadas respectivamente residuales derecho e izquierdo, estas operaciones coinciden cuando el monoide es conmutativo. El concepto general fue introducido por Morgan Ward yRobert P. Dilworth en 1939. Ejemplos, algunos de los cuales existían antes de la concepto general, incluyen las álgebra de Boole , las álgebra de Heyting , álgebra boleanas residuated , las álgebra de relación , y MV-álgebra . Las semirretículas residuales omiten la operación de encuentro ∧, por ejemplo, álgebras de Kleene y álgebras de acción .
Definición
En matemáticas , una red residuada es una estructura algebraica L = ( L , ≤, •, I ) tal que
- (i) ( L , ≤) es una red .
- (ii) ( L , •, I ) es un monoide .
- (iii) Para todo z existe para todo x un y mayor , y para todo y un x mayor , tal que x • y ≤ z (las propiedades de residuación).
En (iii), la " y mayor ", siendo una función de z y x , se denota x \ z y se llama el 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, el "mayor x " se denota z / y y se llama el residuo izquierdo de z por y . Un enunciado equivalente y más formal de (iii) que utiliza estas operaciones para nombrar estos valores máximos es
(iii) 'para todo 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 doblemente 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,
- x • ( x \ y ) ≤ y ≤ x \ ( x • y ), y
- ( y / x ) • x ≤ y ≤ ( y • x ) / x ,
junto con el requisito de que x • y ser monótona en x e y . (Cuando se axiomatiza usando (iii) o (iii) 'la monotonicidad 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í, e igualmente para • x y / x .
Esta última definición es puramente en términos de desigualdades, señalando que la monotonicidad se puede axiomatizar como x • y ≤ ( x ∨ z ) • y de manera similar para las otras operaciones y sus argumentos. Además, cualquier desigualdad x ≤ y se puede expresar de manera equivalente como una ecuación, ya sea x ∧ y = x o x ∨ y = y . Esto, junto con las ecuaciones que axiomatizan retículas y monoides, produce una definición puramente ecuacional de retículas residuales, siempre que las operaciones requeridas se unan a la firma ( L , ≤, •, I ) expandiéndola a ( L , ∧, ∨, •, Yo , /, \). Cuando se organizan así, las celosías residuales forman una clase o variedad ecuacional , cuyos homomorfismos respetan tanto los residuos como las operaciones de celosía y monoide. Tenga en cuenta 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 formar parte de la definición. Esta distributividad necesaria de • sobre ∨ no implica en general una distributividad de ∧ sobre ∨, es decir, una red residuada no necesita ser una red distributiva. Sin embargo, la distributividad de ∧ sobre ∨ está implicada cuando • y ∧ son la misma operación, un caso especial de retículas 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 ey 1 '. Las notaciones alternativas para los residuos son x → y para x \ y y y ← x para y / x , sugeridas por la similitud entre la residuación y la implicación en la 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 residuales como implicaciones puede entenderse como que tiene una cualidad temporal: x • y significa x y luego y , x → y significa que 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.
Ejemplos de
Una de las motivaciones originales para el estudio de las celosías residuales fue la celosía de los ideales (de dos caras) de un anillo . Dado un anillo R , los ideales de R , denominados 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 • viene dada por "multiplicación ideal", y el elemento R de Id ( R ) actúa como 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 de izquierda y derecha aniquiladores de B . Este residuation 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 solo un subconjunto.
Las álgebras booleanas y las álgebras de Heyting son retículas conmutativas residuales en las 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, la implicación x → y . El segundo ejemplo es bastante general ya que las álgebras de Heyting incluyen todas las celosías distributivas finitas , así como todas las cadenas u órdenes totales que forman una celosía completa , por ejemplo, el intervalo unitario [0,1] en la línea real, o los enteros y ±.
La estructura ( Z , min , max , +, 0, -, -) (los números enteros con sustracción para ambos residuos) es una celosía residuada conmutativa tal que la unidad del monoide no es el elemento más grande (de hecho, no hay mínimo o mayor entero), y la multiplicación del monoide no es la operación de encuentro de la red. En este ejemplo, las desigualdades son iguales porque - (resta) no es simplemente el adjunto o pseudoinverso de + sino el verdadero inverso. En este ejemplo, cualquier grupo totalmente ordenado bajo la suma, como los racionales o los reales, puede sustituir a los números enteros. La parte no negativa de cualquiera de estos ejemplos es un ejemplo siempre que min y max se intercambien y - se sustituya 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 viene dada por el álgebra booleana de todas las relaciones binarias en un conjunto X , a saber, el conjunto de potencias de X 2 , hecho una red residuada tomando la multiplicación de monoide • como composición de relaciones y la unidad de monoide como la relación de 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 (observe 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
El álgebra booleana 2 Σ * de todos los lenguajes formales sobre un alfabeto (conjunto) Σ forma un entramado residuo cuya multiplicación de monoide es la concatenación de lenguajes LM y cuya unidad monoide I es el lenguaje {ε} que consiste solo en la cadena vacía ε. El derecho residual M \ L consta de todas las palabras w sobre Σ tal que Mw ⊆ L . El L / M residual izquierdo es el mismo con wM en lugar de Mw .
La retícula residual de todas las relaciones binarias en X es finita solo cuando X es finita, y conmutativa solo cuando X tiene como máximo un elemento. Cuando X es vaciar el álgebra es el álgebra de Boole degenerada en la que 0 = 1 = I . La celosía residual de todos los idiomas en Σ es conmutativa solo cuando Σ tiene como máximo una letra. Es finito solo cuando Σ está vacío, y consta de los dos idiomas 0 (el idioma vacío {}) y la unidad monoide I = {ε} = 1.
Los ejemplos que forman un álgebra booleana tienen propiedades especiales tratadas en el artículo sobre álgebras booleanas residuales .
En el lenguaje natural, las celosías residuales formalizan la lógica de "y" cuando se usan con su significado no conmutativo de "y luego". Estableciendo x = apuesta , y = ganar , z = rico , podemos leer x • y ≤ z como "apostar y luego ganar implica rico". Según los axiomas, esto es equivalente a y ≤ x → z, que significa "ganar implica que se haya apostado entonces rico", y también ax ≤ z ← y que significa "apuesta implica que si-alguna vez se gana, entonces rico". Los seres humanos detectan fácilmente tales no-sequiturs como "la apuesta implica ganar y luego rico" y "ganar implica si-alguna vez apostar entonces rico", ya que ambos son equivalentes a la ilusión "ganar y luego apostar implica rico". [ 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 exhiben más competencia con el razonamiento no clásico que el clásico (por ejemplo, en relevancia lógica , la ley de Peirce no es una tautología). [ relevante? ]
Semicarejilla residual
Una semirrejilla residual se define de manera casi idéntica para las celosías residuales, omitiendo solo la operación de encuentro ∧. Por lo tanto, es una estructura algebraica L = (L, ∨, •, 1, /, \) que satisface todas las ecuaciones reticulares residuales como se especificó anteriormente, excepto aquellas que contienen una ocurrencia del símbolo ∧. La opción de definir x ≤ y como x ∧ y = x entonces no está disponible, dejando solo la otra opción x ∨ y = y (o cualquier equivalente de la misma).
Cualquier enrejado residual puede convertirse en un semirretículo residuo simplemente omitiendo ∧. Las semirretículas residuales surgen en relación con las álgebras de acción , que son semirreticulaciones residuales que también son álgebras de Kleene , para las cuales ∧ normalmente no se requiere.
Ver también
Referencias
- Ward, Morgan y Robert P. Dilworth (1939) "Rejillas residuales", Trans. Amer. Matemáticas. Soc. 45 : 335–54. Reimpreso en Bogart, K, Freese, R. y Kung, J., eds. (1990) Los teoremas de Dilworth: artículos seleccionados de RP Dilworth Basel: Birkhäuser.
- Nikolaos Galatos, Peter Jipsen, Tomasz Kowalski e Hiroakira Ono (2007), Rejillas residuales. Un vistazo algebraico a la lógica subestructural , Elsevier, ISBN 978-0-444-52141-5 .