Álgebra de relaciones - Relation algebra
En matemáticas y álgebra abstracta , un álgebra de relaciones es un álgebra booleana residuada expandida con una involución llamada recíproca , una operación unaria. El ejemplo motivador de un álgebra de relaciones es el álgebra 2 X ² de todas las relaciones binarias en un conjunto X , es decir, subconjuntos del cuadrado cartesiano X 2 , con R • S interpretado como la composición habitual de las relaciones binarias R y S , y con el inverso de R como la relación inversa .
El álgebra de relaciones surgió en la obra del siglo XIX de Augustus De Morgan y Charles Peirce , que culminó en la lógica algebraica de Ernst Schröder . Alfred Tarski y sus alumnos desarrollaron la forma de ecuaciones del álgebra de relaciones que se trata aquí a partir de la década de 1940. Tarski y Givant (1987) aplicaron el álgebra de relaciones a un tratamiento libre de variables de la teoría axiomática de conjuntos , con la implicación de que las matemáticas fundadas en la teoría de conjuntos podrían en sí mismas realizarse sin variables.
Definición
Un álgebra de relaciones ( L , ∧, ∨, - , 0, 1, •, I , ˘) es una estructura algebraica equipada con las operaciones booleanas de conjunción x ∧ y , disyunción x ∨ y y negación x - , las constantes booleanas 0 y 1, las operaciones relacionales de composición x • y y recíproca x ˘, y la constante relacional I , de manera que estas operaciones y constantes satisfacen determinadas ecuaciones que constituyen una axiomatización de un cálculo de relaciones . Aproximadamente, un álgebra de relaciones es a un sistema de relaciones binarias en un conjunto que contiene las relaciones vacías (0), completas (1) e identidad ( I ) y cerrado bajo estas cinco operaciones como grupo es a un sistema de permutaciones de un conjunto que contiene la permutación de identidad y cerrado bajo composición e inverso. Sin embargo, la teoría de primer orden de las álgebras de relaciones no está completa para tales sistemas de relaciones binarias.
Siguiendo a Jónsson y Tsinakis (1993) es conveniente definir operaciones adicionales x ◁ y = x • y ˘, y, dualmente, x ▷ y = x ˘ • y . Jónsson y Tsinakis demostraron que I ◁ x = x ▷ I , y que ambos eran iguales ax ˘. Por tanto, un álgebra de relaciones puede definirse igualmente bien como una estructura algebraica ( L , ∧, ∨, - , 0, 1, •, I , ◁, ▷) . La ventaja de esta firma sobre la habitual es que un álgebra de relaciones se puede definir en su totalidad simplemente como un álgebra booleana residuada para la cual I ◁ x es una involución, es decir, I ◁ ( I ◁ x ) = x . La última condición puede considerarse como la contraparte relacional de la ecuación 1 / (1 / x ) = x para recíproco aritmético ordinario , y algunos autores usan recíproco como sinónimo de recíproco.
Dado que las álgebras de Boole residuales están axiomatizadas con un número finito de identidades, también lo son las álgebras de relaciones. Por lo tanto, estos últimos forman una variedad , la variedad RA de álgebras de relaciones. Expandir la definición anterior como ecuaciones produce la siguiente axiomatización finita.
Axiomas
Los axiomas B1-B10 a continuación están adaptados de Givant (2006: 283) y fueron establecidos por primera vez por Tarski en 1948.
L es un álgebra de Boole bajo disyunción binaria , ∨ y complementación unaria () - :
- B1 : A ∨ B = B ∨ A
- B2 : UNA ∨ ( B ∨ C ) = ( A ∨ B ) ∨ C
- B3 : ( A - ∨ B ) - ∨ ( A - ∨ B - ) - = A
Esta axiomatización del álgebra de Boole se debe a Huntington (1933). Tenga en cuenta que el encuentro del álgebra booleana implícita no es el operador • (aunque se distribuye sobre ∨ como lo hace un encuentro), ni el 1 del álgebra booleana es la constante I.
L es un monoide bajo composición binaria (•) e identidad nular I :
- B4 : A • ( B • C ) = ( A • B ) • C
- B5 : A • I = A
Unario recíproco () ˘ es una involución con respecto a la composición :
- B6 : A ˘˘ = A
- B7 : ( A • B ) ˘ = B ˘ • A ˘
El axioma B6 define la conversión como una involución , mientras que B7 expresa la propiedad antidistributiva de la conversión en relación con la composición.
El inverso y la composición se distribuyen sobre la disyunción:
- B8 : ( UNA ∨ B ) ˘ = UNA ˘∨ B ˘
- B9 : ( A ∨ B ) • C = ( A • C ) ∨ ( B • C )
B10 es la forma ecuacional de Tarski del hecho, descubierto por Augustus De Morgan , que A • B ≤ C - A ˘ • C ≤ B - C • B ˘ ≤ A - .
- B10 : ( A ˘ • ( A • B ) - ) ∨ B - = B -
Estos axiomas son teoremas de ZFC ; para el puramente booleano B1-B3 , este hecho es trivial. Después de cada uno de los siguientes axiomas se muestra el número del teorema correspondiente en el Capítulo 3 de Suppes (1960), una exposición de ZFC: B4 27, B5 45, B6 14, B7 26, B8 16, B9 23.
Expresando propiedades de relaciones binarias en RA
La siguiente tabla muestra cuántas de las propiedades habituales de las relaciones binarias se pueden expresar como igualdad o desigualdad de RA sucinta . A continuación, una desigualdad de la forma A ≤ B es la abreviatura de la Boolean ecuación A ∨ B = B .
El conjunto más completo de resultados de esta naturaleza es el capítulo C de Carnap (1958), donde la notación es bastante distante de la de esta entrada. El capítulo 3.2 de Suppes (1960) contiene menos resultados, presentados como teoremas de ZFC y utilizando una notación que se parece más a la de esta entrada. Ni Carnap ni Suppes formularon sus resultados utilizando el RA de esta entrada, o de manera ecuacional.
R es | Si y solo si : |
---|---|
Funcional | R ˘ • R ≤ I |
Total izquierda | I ≤ R • R ˘ ( R ˘ es sobreyectiva) |
Función | funcional y total izquierda. |
Inyectable |
R • R ˘ ≤ I ( R ˘ es funcional) |
Sobreyectiva | I ≤ R ˘ • R ( R ˘ es el total de la izquierda) |
Biyección | R ˘ • R = R • R ˘ = I (Función inyectiva sobreyectiva) |
Transitivo | R • R ≤ R |
Reflexivo | Yo ≤ R |
Coreflexivo | R ≤ I |
Irreflexivo | R ∧ I = 0 |
Simétrico | R ˘ = R |
Antisimétrico | R ∧ R ˘ ≤ yo |
Asimétrico | R ∧ R ˘ = 0 |
Fuertemente conectado | R ∨ R ˘ = 1 |
Conectado | Yo ∨ R ∨ R ˘ = 1 |
Idempotente | R • R = R |
Hacer un pedido | R es transitivo y reflexivo. |
Equivalencia | R es un preorden simétrico. |
Orden parcial | R es un preorden antisimétrico. |
Orden total | R está fuertemente conectado y es un orden parcial. |
Orden parcial estricto | R es transitivo e irreflexivo. |
Orden total estricto | R está conectado y es un orden parcial estricto. |
Denso | R ∧ I - ≤ ( R ∧ I - ) • ( R ∧ I - ) . |
Poder expresivo
Las metamatemáticas de la AR se discuten extensamente en Tarski y Givant (1987), y más brevemente en Givant (2006).
RA consiste enteramente en ecuaciones manipuladas usando nada más que un reemplazo uniforme y la sustitución de iguales por iguales. Ambas reglas son totalmente familiares de las matemáticas escolares y del álgebra abstracta en general. Por lo tanto, las demostraciones de RA se llevan a cabo de una manera familiar para todos los matemáticos, a diferencia del caso de la lógica matemática en general.
RA puede expresar cualquier (y hasta la equivalencia lógica , exactamente ) fórmulas lógicas de primer orden (FOL) que no contengan más de tres variables. (Una variable dada se puede cuantificar varias veces y, por lo tanto, los cuantificadores se pueden anidar de forma arbitraria y profunda "reutilizando" las variables). Sorprendentemente, este fragmento de FOL es suficiente para expresar la aritmética de Peano y casi todas las teorías de conjuntos axiomáticos jamás propuestas. Por lo tanto, RA es, en efecto, una forma de algebraizar casi todas las matemáticas, prescindiendo de FOL y sus conectivos , cuantificadores , torniquetes y modus ponens . Debido a que RA puede expresar la aritmética de Peano y la teoría de conjuntos, los teoremas de incompletitud de Gödel se aplican a ella; RA es incompleta , incompleta e indecidible . (NB El fragmento de álgebra de Boole de RA es completo y decidible).
Las álgebras de relaciones representables , que forman la clase RRA , son aquellas álgebras de relaciones isomorfas a alguna álgebra de relaciones que consta de relaciones binarias en algún conjunto, y cerradas bajo la interpretación pretendida de las operaciones de RA . Se muestra fácilmente, por ejemplo, usando el método de clases pseudoelementales , que RRA es una cuasivariedad , es decir, axiomatizable por una teoría de Horn universal . En 1950, Roger Lyndon demostró la existencia de ecuaciones válidas en RRA que no se cumplieron en RA . Por tanto, la variedad generada por RRA es una subvariedad propia de la variedad RA . En 1955, Alfred Tarski demostró que RRA es en sí misma una variedad. En 1964, Donald Monk demostró que RRA no tiene axiomatización finita, a diferencia de RA , que está axiomatizada finitamente por definición.
Álgebras de relación Q
Un RA es un álgebra de relación Q ( QRA ) si, además de B1-B10 , existen algunos A y B tales que (Tarski y Givant 1987: §8.4):
- Q0 : A ˘ • A ≤ I
- Q1 : B ˘ • B ≤ I
- P2 : A ˘ • B = 1
Esencialmente estos axiomas implicar que el universo tiene una (no sobreyectiva) relación de emparejamiento cuyas proyecciones son A y B . Es un teorema que cada QRA es un RRA (Prueba de Maddux, ver Tarski y Givant 1987: 8.4 (iii)).
Cada QRA es representable (Tarski y Givant 1987). El hecho de que no todas las álgebras de relaciones sean representables es una forma fundamental en que RA difiere de QRA y las álgebras booleanas , que, según el teorema de representación de Stone para las álgebras booleanas , siempre se pueden representar como conjuntos de subconjuntos de algún conjunto, cerrados bajo unión, intersección y complemento.
Ejemplos de
- Cualquier álgebra booleana se puede convertir en un RA interpretando la conjunción como composición (la multiplicación de monoide •), es decir, x • y se define como x ∧ y . Esta interpretación requiere que la identidad converse interpretar ( ў = Y ), y que ambos residuos Y \ x y x / y interpretar el condicional y → x (es decir, ¬ y ∨ x ).
- El ejemplo motivador de un álgebra de relación depende de la definición de una relación binaria R en un conjunto X como cualquier subconjunto R ⊆ X ² , donde X ² es el cuadrado cartesiano de X . El conjunto de potencia 2 X ² que consta de todas las relaciones binarias en X es un álgebra booleana. Mientras que 2 X ² puede convertirse en un álgebra de relaciones tomando R • S = R ∧ S , como en el ejemplo (1) anterior, la interpretación estándar de • es x ( R • S ) z = ∃ y : xRy.ySz . Es decir, el par ordenado ( x , z ) pertenece a la relación R • S justo cuando existe y ∈ X tal que ( x , Y ) ∈ R y ( y , z ) ∈ S . Esta interpretación determina de manera única que R \ S consta de todos los pares ( y , z ) de manera que para todo x ∈ X , si xRy entonces xSz . Dually, S / R se compone de todos los pares ( x , y ) tales que para todo z ∈ X , si yRz entonces XSZ . La traducción ў = ¬ (y \ ¬ I ) a continuación, establece la inversa R ˘ de R como un conjunto de todos los pares ( Y , x ) tal que ( x , y ) ∈ R .
- Una generalización importante del ejemplo anterior es el poder establecer 2 E donde E ⊆ X ² es cualquier relación de equivalencia en el conjunto X . Ésta es una generalización porque X ² es en sí misma una relación de equivalencia, es decir, la relación completa que consta de todos los pares. Si bien 2 E no es una subálgebra de 2 X ² cuando E ≠ X ² (ya que en ese caso no contiene la relación X ² , el elemento superior 1 es E en lugar de X ² ), sin embargo se convierte en un álgebra de relaciones utilizando las mismas definiciones de las operaciones. Su importancia reside en la definición de un álgebra de relaciones representable como cualquier álgebra de relaciones isomorfa a una subálgebra del álgebra de relaciones 2 E para alguna relación de equivalencia E en algún conjunto. La sección anterior dice más sobre las metamatemáticas relevantes.
- Sea G el grupo. Entonces, el conjunto de potencias es un álgebra de relaciones con las operaciones obvias del álgebra booleana, la composición está dada por el producto de subconjuntos de grupos , la inversa por el subconjunto inverso ( ) y la identidad por el subconjunto singleton . Hay un homomorfismo de álgebra de relaciones incrustado en el que envía cada subconjunto a la relación . La imagen de este homomorfismo es el conjunto de todas las relaciones de derecho invariantes en G .
- Si la suma del grupo o el producto interpreta la composición, el inverso del grupo interpreta lo inverso, la identidad del grupo interpreta I , y si R es una correspondencia uno a uno , de modo que R ˘ • R = R • R ˘ = I , entonces L es un grupo como así como un monoide . B4 - B7 se convierten en teoremas bien conocidos de la teoría de grupos , de modo que RA se convierte en una extensión adecuada de la teoría de grupos , así como del álgebra de Boole.
Observaciones históricas
De Morgan fundó RA en 1860, pero CS Peirce lo llevó mucho más lejos y quedó fascinado con su poder filosófico. La obra de DeMorgan y Peirce llegó a ser conocida principalmente en la forma ampliada y definitiva que Ernst Schröder le dio en el vol. 3 de su Vorlesungen (1890-1905). Principia Mathematica se basó fuertemente en el RA de Schröder , pero lo reconoció solo como el inventor de la notación. En 1912, Alwin Korselt demostró que una fórmula particular en la que los cuantificadores estaban anidados a cuatro profundidades no tenía equivalente de RA . Este hecho provocó una pérdida de interés por la RA hasta que Tarski (1941) empezó a escribir sobre ella. Sus estudiantes han seguido desarrollando RA hasta el día de hoy. Tarski regresó a RA en la década de 1970 con la ayuda de Steven Givant; esta colaboración dio lugar a la monografía de Tarski y Givant (1987), la referencia definitiva para este tema. Para obtener más información sobre la historia de la AR , consulte Maddux (1991, 2006).
Software
- RelMICS / métodos relacionales en ciencias de la computación mantenido por Wolfram Kahl
- Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras
- Stef Joosten , Relation Álgebra como lenguaje de programación usando el compilador Ampersand, Journal of Logical and Algebraic Methods in Programming , Volumen 100, abril de 2018, páginas 113-129. (ver también https://ampersandtarski.gitbook.io/documentation )
Ver también
|
Notas al pie
- ^ Alfred Tarski (1948) "Resumen: Problemas de representación para álgebras de relaciones", Boletín de la AMS 54: 80.
- ^ Chris Brink; Wolfram Kahl; Gunther Schmidt (1997). Métodos relacionales en informática . Saltador. págs. 4 y 8. ISBN 978-3-211-82971-4.
- ^ Tarski, A. (1941), p. 87.
- ^ Korselt no publicó su hallazgo. Se publicó por primera vez en Leopold Loewenheim (1915) "Über Möglichkeiten im Relativkalkül", Mathematische Annalen 76: 447–470. Traducido como "Sobre las posibilidades en el cálculo de parientes" en Jean van Heijenoort , 1967. A Source Book in Mathematical Logic, 1879-1931 . Universidad de Harvard. Presione: 228–251.
Referencias
- Carnap, Rudolf (1958). Introducción a la lógica simbólica y sus aplicaciones . Publicaciones de Dover.
- Givant, Steven (2006). "El cálculo de relaciones como fundamento de las matemáticas". Revista de razonamiento automatizado . 37 (4): 277–322. doi : 10.1007 / s10817-006-9062-x . S2CID 26324546 .
- Halmos, PR (1960). Teoría de conjuntos ingenua . Van Nostrand.
- Henkin, Leon ; Tarski, Alfred ; Monk, JD (1971). Álgebras cilíndricas, Parte 1 . Holanda Septentrional.
- Henkin, León ; Tarski, Alfred ; Monk, JD (1985). Álgebras cilíndricas, Parte 2 . Holanda Septentrional.
- Hirsch, R .; Hodkinson, I. (2002). Álgebra de relaciones por juegos . Estudios de Lógica y Fundamentos de las Matemáticas. 147 . Ciencia de Elsevier.
- Jónsson, Bjarni ; Tsinakis, Constantine (1993). "Álgebras de relación como álgebras de Boole residuales". Álgebra Universalis . 30 (4): 469–78. doi : 10.1007 / BF01195378 . S2CID 120642402 .
- Maddux, Roger (1991). "El origen de las álgebras de relaciones en el desarrollo y axiomatización del cálculo de relaciones" (PDF) . Studia Logica . 50 (3–4): 421–455. CiteSeerX 10.1.1.146.5668 . doi : 10.1007 / BF00370681 . S2CID 12165812 .
- Maddux, Roger (2006). Álgebras de relaciones . Estudios de Lógica y Fundamentos de las Matemáticas. 150 . Ciencia de Elsevier. ISBN 9780444520135.
- Schein, Boris M. (1970) "Álgebras de relaciones y semigrupos de funciones", Semigroup Forum 1: 1-62
- Schmidt, Gunther (2010). Matemáticas relacionales . Prensa de la Universidad de Cambridge.
- Suppes, Patrick (1972) [1960]. "Capítulo 3". Teoría de conjuntos axiomáticos (reimpresión de Dover ed.). Van Nostrand.
- Tarski, Alfred (1941). "Sobre el cálculo de relaciones". Revista de lógica simbólica . 6 (3): 73–89. doi : 10.2307 / 2268577 . JSTOR 2268577 .
- Tarski, Alfred; Givant, Steven (1987). Una formalización de la teoría de conjuntos sin variables . Providence RI: Sociedad Matemática Estadounidense. ISBN 9780821810415.
enlaces externos
- Yohji AKAMA, Yasuo Kawahara y Hitoshi Furusawa, " Construyendo alegorías a partir del álgebra de relaciones y teoremas de representación " .
- Richard Bird, Oege de Moor, Paul Hoogendijk, " Programación genérica con relaciones y functores " .
- RP de Freitas y Viana, " Un resultado completo para el álgebra de relaciones con carpetas " .
- Peter Jipsen :
-
Vaughan Pratt :
- " Orígenes del cálculo de relaciones binarias " . Un tratamiento histórico.
- " El segundo cálculo de relaciones binarias " .
- Priss, Uta:
- " Una interpretación de FCA del álgebra de relaciones " .
- " Relation Algebra and FCA " Enlaces a publicaciones y software
- Kahl, Wolfram y Gunther Schmidt : Exploración de álgebras de relaciones (finitas) utilizando herramientas escritas en Haskell. y herramientas de álgebra de relaciones con Haskell de la Universidad McMaster .