Álgebra de relaciones

En matemáticas y álgebra abstracta, un álgebra de relaciones es un álgebra booleana residual expandida con una involución llamada conversa, una operación unaria. El ejemplo motivador de un álgebra de relaciones es el álgebra 2^X 2 de todas las relaciones binarias en un conjunto X, es decir, subconjuntos del cuadrado cartesiano X², con R•S interpretada como la composición usual de las relaciones binarias R y S, y con la inversa de R como la relación inversa.

El álgebra relacional surgió en el siglo XIX con los trabajos de Augustus De Morgan y Charles Peirce, que culminaron en la lógica algebraica de Ernst Schröder. La forma ecuacional del álgebra relacional que se trata aquí fue desarrollada por Alfred Tarski y sus estudiantes a partir de la década de 1940. Tarski y Givant (1987) aplicaron el álgebra relacional a un tratamiento sin variables de la teoría de conjuntos axiomática, con la implicación de que las matemáticas fundadas en la teoría de conjuntos podían realizarse sin variables.

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 modo que estas operaciones y constantes satisfacen ciertas ecuaciones que constituyen una Axiomatización de un cálculo de relaciones. En términos generales, un álgebra de relaciones es a un sistema de relaciones binarias en un conjunto que contiene las relaciones vacías (0), universales (1) e identidad (I) y cerrado bajo estas cinco operaciones, como un grupo es a un sistema de permutaciones de un conjunto que contiene la permutación identidad y cerrado bajo composición e inversa. 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 ambas eran iguales a x˘. Por lo tanto, un álgebra relacional puede definirse igualmente como una estructura algebraica (L, ∧, ∨, ⁻, 0, 1, •, I, ◁ , ▷). La ventaja de esta firma sobre la habitual es que un álgebra relacional puede definirse entonces en su totalidad simplemente como un álgebra booleana residual 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 la aritmética ordinaria recíproca, y algunos autores usan recíproco como sinónimo de recíproco.

Dado que las álgebras booleanas residuales se axiomatizan con un número finito de identidades, también lo hacen las álgebras de relación. Por lo tanto, estas últimas forman una variedad, la variedad RA de las álgebras de relación. Al expandir la definición anterior como ecuaciones, se obtiene la siguiente axiomatización finita.

Los axiomas B1-B10 que aparecen a continuación son una adaptación de Givant (2006: 283) y fueron enunciados por primera vez por Tarski en 1948.

L es un álgebra de Boole bajo disyunción binaria, ∨, y complementación unaria ()⁻:

B1: A Alternativa B = B Alternativa A

B2: A AlternativaB Alternativa C) =A Alternativa B) C

B3: ()A⁻ Alternativa B)⁻ AlternativaA⁻ Alternativa B⁻)⁻ = A

Esta axiomatización del álgebra de Boole se debe a Huntington (1933). Nótese que el encuentro del álgebra de Boole implícita no es el operador • (aunque se distribuye sobre ∨ como lo hace un encuentro), ni el 1 del álgebra de Boole es la constante I.

L es un monoide bajo composición binaria (•) e identidad nularia I:

B4: A •B • C) =A • B) C

B5: A • I = A

La conversa unaria ()˘ 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 el B7 expresa la propiedad antidistributiva de la conversión con respecto a la composición.

La composición y la recíproca se distribuyen sobre la disyunción:

B8: ()A Alternativa B) A∨ B.

B9: ()A Alternativa B) C =A • C) ∨B • C)

B10 es la forma ecual de Tarski del hecho, descubierto por Augustus De Morgan, que A • B ≤ C⁻ ${\displaystyle \leftrightarrow }$ A* C ≤ B⁻ ${\displaystyle \leftrightarrow }$ C • B¢ A⁻.

B10: ()A*A • B)⁻) B⁻ = B⁻

Estos axiomas son teoremas de ZFC; para los puramente booleanos 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.

La siguiente tabla muestra cuántas de las propiedades habituales de las relaciones binarias se pueden expresar como igualdades o desigualdades RA sucintas. A continuación, una desigualdad de la forma A ≤ B es una abreviatura de la ecuación booleana 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 diferente a 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 asemeja más a la de esta entrada. Ni Carnap ni Suppes formularon sus resultados utilizando la RA de esta entrada, o de manera ecuacional.

Las metamatemáticas de la RA se analizan en profundidad en Tarski y Givant (1987), y más brevemente en Givant (2006).

RA consiste enteramente en ecuaciones manipuladas utilizando nada más que el reemplazo uniforme y la sustitución de iguales por iguales. Ambas reglas son totalmente familiares en las matemáticas escolares y en el á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 fórmula de lógica de primer orden (FOL) (y, hasta la equivalencia lógica, exactamente la fórmula) que no contenga más de tres variables. (Una variable dada puede cuantificarse varias veces y, por lo tanto, los cuantificadores pueden anidarse de manera arbitraria y profunda mediante la "reutilización" de 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 que se hayan propuesto. Por lo tanto, RA es, en efecto, una forma de algebrar casi todas las matemáticas, al tiempo que se prescinde 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, incompletable e indecidible. (N.B. El fragmento de álgebra de Boole de RA es completo y decidible.)

Las álgebras de relación representables, que forman la clase RRA, son aquellas álgebras de relación isomorfas a alguna álgebra de relación que consiste en relaciones binarias sobre algún conjunto, y cerradas bajo la interpretación pretendida de las operaciones RA. Se demuestra fácilmente, por ejemplo utilizando el método de clases pseudoelementales, que RRA es una cuasivariedad, es decir, axiomatizable por una teoría universal de Horn. En 1950, Roger Lyndon demostró la existencia de ecuaciones que se cumplen en RRA y que no se cumplen en RA. Por lo 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.

Una RA es un álgebra de Q-relaciones (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

Q2: A* B = 1

En esencia, estos axiomas implican que el universo tiene una relación de emparejamiento (no sobreyectiva) cuyas proyecciones son A y B. Es un teorema que cada QRA es un RRA (Demostración de Maddux, véase Tarski & Givant 1987: 8.4(iii)).

Toda álgebra de relaciones es representable (Tarski y Givant 1987). El hecho de que no todas las álgebras de relaciones sean representables es una forma fundamental en la que la álgebra de relaciones difiere de la álgebra de relaciones y de las álgebras de Boole, que, según el teorema de representación de Stone para las álgebras de Boole, siempre son representables como conjuntos de subconjuntos de algún conjunto, cerrados bajo unión, intersección y complemento.

1. Cualquier álgebra booleana se puede convertir en un RA interpretando la conjunción como composición (la multiplicación monoide •), es decir. x • Sí. se define como x∧Sí.. Esta interpretación requiere que se interprete la identidad conversa. =Sí.), y que ambos residuales Sí.\x y x/Sí. interpretar el condicional Sí. → x (es decir,Sí.Alternativax).
2. El ejemplo motivador de una relación álgebra depende de la definición de una relación binaria R en un set X como subconjunto R ⊆ X², donde X² es la plaza cartesiana de X. El sistema de potencia 2^X2 que consiste en todas las relaciones binarias sobre X es un álgebra booleana. Mientras que 2^X2 se puede hacer una relación álgebra tomando R • S = R ∧ S, como por ejemplo (1) arriba, la interpretación estándar de • es en cambio x()R•S)z =Sí.:xRy.ySz. Es decir, el par ordenado ()x, z) pertenece a la relación R • S justo cuando existe Sí. dentro X tales que ()x, Sí.) R y ()Sí., z) S. Esta interpretación determina singularmente R\S como consiste de todos los pares ()Sí., z) tal que para todos x ▪ X, si x Ry entonces xSz. Dualmente, S/R consta de todos los pares ()x, Sí.) tal que para todos z dentro X, si YRz entonces xSz. La traducción . = ¬Sí.\I) entonces establece el converso R¢ de R como consiste de todos los pares ()Sí., x) tales que ()x, Sí.) R.
3. Una importante generalización del ejemplo anterior es el conjunto de potencia 2^E Donde E ⊆ X² es cualquier relación de equivalencia en el conjunto X. Esto es una generalización porque X² es en sí misma una relación de equivalencia, a saber, la relación completa que consiste de todos los pares. Mientras que 2^E no es un subalgebra de 2^X2 cuando E ل X² (ya que en ese caso no contiene la relación X², el elemento superior 1 siendo E en lugar de X²), se convierte sin embargo en un álgebra de relación utilizando las mismas definiciones de las operaciones. Su importancia reside en la definición de un relación representable álgebra como cualquier relación álgebra isomorfo a un subalgebra de la relación álgebra 2^E para alguna relación de equivalencia E en un set. La sección anterior dice más sobre las metamatemáticas relevantes.
4. Vamos. G Sé un grupo. Entonces el sistema de poder ${\displaystyle 2^{G}$ es una relación álgebra con las operaciones obvias de álgebra booleana, composición dada por el producto de subconjuntos de grupo, el converso por el subconjunto inverso (${\displaystyle A^{-1}=\{a^{-1}\]a\in A\}$), y la identidad por el subconjunto de singleton ${\displaystyle \{e\}}$. Hay una relación algebra homomorfismo embedding ${\displaystyle 2^{G}$ dentro ${\displaystyle 2^{G\times G}$ que envía cada subconjunto ${\displaystyle A\subset G}$ a la relación ${\displaystyle R_{(g,h)\in G\times G:h\in Ag}$. La imagen de este homomorfismo es el conjunto de todas las relaciones invariantes en G.
5. Si la suma de grupo o producto interpreta la composición, las interpretaciones inversas de grupo conversan, la identidad de grupo interpreta IY si R es una correspondencia de uno a uno, así que R* R = R • R¢ IEntonces L es un grupo así como un monoide. B4-B7 convertirse en teoremas conocidos de la teoría del grupo, de modo que RA se convierte en una extensión adecuada de la teoría del grupo, así como del álgebra boo.

De Morgan fundó la RA en 1860, pero C. S. Peirce la llevó mucho más allá y quedó fascinado con su poder filosófico. El trabajo de DeMorgan y Peirce llegó a ser conocido principalmente en la forma extendida y definitiva que Ernst Schröder le dio en el vol. 3 de su Vorlesungen (1890-1905). Los Principia Mathematica se basaron fuertemente en la RA de Schröder, pero lo reconocieron sólo como el inventor de la notación. En 1912, Alwin Korselt demostró que una fórmula particular en la que los cuantificadores estaban anidados en profundidad de cuatro no tenía equivalente en la RA. Este hecho llevó a una pérdida de interés en la RA hasta que Tarski (1941) comenzó a escribir sobre ella. Sus estudiantes han continuado desarrollando la RA hasta el día de hoy. Tarski volvió a la RA en la década de 1970 con la ayuda de Steven Givant; esta colaboración dio como resultado la monografía de Tarski y Givant (1987), la referencia definitiva sobre este tema. Para más información sobre la historia de la RA, véase Maddux (1991, 2006).

• RelMICS / Métodos de Relación en Ciencias de la Computación mantenidos por Wolfram Kahl
• Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras
• Stef Joosten, Relation Algebra como lenguaje de programación usando el compilador Ampersand, Journal of Logical and Algebraic Methods in Programming, Volumen 100, abril 2018, Páginas 113–129. (véase también https://ampersandtarski.github.io/)

• Carnap, Rudolf (1958). Introducción a la lógica simbólica y sus aplicaciones. Dover Publications.
• Givant, Steven (2006). "El cálculo de las relaciones como fundamento para las matemáticas". Journal of Automated Reasoning. 37 (4): 277–322. doi:10.1007/s10817-006-9062-x. S2CID 26324546.
• Halmos, P. R. (1960). Juego inactivo Teoría. Van Nostrand.
• Henkin, Leon; Tarski, Alfred; Monk, J. D. (1971). Álgebras cilíndricas, Parte 1. North Holland.
• Henkin, Leon; Tarski, Alfred; Monk, J. D. (1985). Álgebras cilíndricas, Parte 2. North Holland.
• Hirsch, R.; Hodkinson, I. (2002). Álgebra de Relación por Juegos. Estudios en Lógica y Fundacións de Matemáticas. Vol. 147. Elsevier Science.
• Jónsson, Bjarni; Tsinakis, Constantine (1993). "Relación álgebras como álgebras booleanas residuales". Álgebra Universalis. 30 (4): 469–78. doi:10.1007/BF01195378. S2CID 120642402.
• Maddux, Roger (1991). "El origen de los álgebras de la Relación en el desarrollo y la axiomatización del cálculo de las 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 Relación. Estudios en Lógica y Fundacións de Matemáticas. Vol. 150. Elsevier Science. ISBN 9780444520135.
• Schein, Boris M. (1970) "Algebras de relación y semigrupos de función", Foro Semigroup 1: 1–62
• Schmidt, Gunther (2010). Matemáticas relacionales. Cambridge University Press.
• Suppes, Patrick (1972) [1960]. "Capítulo 3". Conjunto axiomático Teoría (Dover reprint ed.). Van Nostrand.
• Tarski, Alfred (1941). "En el cálculo de las relaciones". Journal of Symbolic Logic. 6 (3): 73–89. doi:10.2307/2268577. JSTOR 2268577. S2CID 11899579.
• Tarski, Alfred; Givant, Steven (1987). Una Formalización de Teoría de Conjunto sin Variables. Providence RI: American Mathematical Society. ISBN 9780821810415.

• Yohji AKAMA, Yasuo Kawahara, y Hitoshi Furusawa, "Construyendo Alegoría de la Relación Álgebra y Teoremas de Representación."
• Richard Bird, Oege de Moor, Paul Hoogendijk, "Generic Programming with Relations and Functors".
• R.P. de Freitas y Viana, "A Completeness Result for Relation Algebra with Binders."
• Peter Jipsen:
  • Álgebras de Relación
  • "Fundaciones de Relaciones y Álgebra Kleene."
  • "Computer Aided Investigations of Relation Algebras."
  • "Un sistema gentzen y la decisión de retecciones residuales".
• Vaughan Pratt:
  • "Originos del Cálculo de Relaciones binarias." Un tratamiento histórico.
  • "El segundo cálculo de las relaciones binarias".
• Priss, Uta:
  • "Una interpretación de FCA de Álgebra de Relación."
  • "Algebra de Relación y FCA" Enlaces a publicaciones y software
• Kahl, Wolfram y Gunther Schmidt: Explorar (Finita) Álgebras de Relación usando Herramientas Escrito en Haskell. y Herramientas de álgebra de Relación con Haskell de la Universidad McMaster.