Álgebra de relaciones

En matemáticas y álgebra abstracta , un álgebra relacional es un álgebra booleana residual expandida con una involución llamada recíproca , una operación unaria . El ejemplo motivador de un álgebra relacional es el álgebra 2 ^X^² de todas las relaciones binarias sobre 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 recíproca de R como la relación recíproca .

El álgebra de relaciones surgió en el siglo XIX con el trabajo de Augustus De Morgan y Charles Peirce , que culminó en la lógica algebraica de Ernst Schröder . La forma ecuacional del álgebra de relaciones 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 de relaciones 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 podrían realizarse sin variables.

Definición

Un álgebra de relaciones $(L, \land, \lor, -, 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$ , tales 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ía (0), universal (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 relación 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 de relaciones puede definirse igualmente bien como una estructura algebraica $(L, \land, \lor, -, 0, 1, •, I, ◁ , ▷)$ . La ventaja de esta firma sobre la habitual es que un álgebra de relaciones puede entonces definirse en su totalidad simplemente como un álgebra booleana residual para la que $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 inverso.

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.

Axiomas

Los axiomas B1-B10 que aparecen a continuación están adaptados de Givant (2006: 283) y fueron enunciados por primera vez por Tarski en 1948. ^[1]

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

B1 :

A \lor B = B \lor A

B2 :

A \lor (B \lor C) = (A \lor B) \lor C

B3 :

(A - \lor B) - \lor (A - \lor 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 nular $I$ :

B4 :

A •(B • C) = (A • B)• C

B5 :

A • Yo = A

La inversa 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 B7 expresa la propiedad antidistributiva de la conversión relativa a la composición. ^[2]

La conversa y la composición se distribuyen sobre la disyunción:

B8 :

(A \lor B)˘ = A ˘ \lor B ˘

B9 :

(A \lor B) • C = (A • C) \lor (B • C)

B10 es la forma ecuacional de Tarski del hecho, descubierto por Augustus De Morgan , de que A • B ≤ C ⁻ A ˘ • C ≤ B ⁻C • B ˘ ≤ A ⁻ . $\flecha izquierda-derecha$ $\flecha izquierda-derecha$

B10 :

(A ˘ • (A • B) -) \lor B - = B -

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

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 igualdades o desigualdades RA sucintas. A continuación, una desigualdad de la forma $A \leq B$ es una forma abreviada de la ecuación booleana $A \lor 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.

Poder expresivo

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

La RA consiste enteramente en ecuaciones manipuladas utilizando únicamente el reemplazo uniforme y la sustitución de iguales por iguales. Ambas reglas son totalmente conocidas 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 las) 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 manera arbitraria y profunda "reutilizando" las variables). ^[^{cita requerida}^] 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, al tiempo que 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 . ^[^{cita requerida}^] (NB 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 en algún conjunto, y cerradas bajo la interpretación pretendida de las operaciones RA . Se muestra 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 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.

Álgebras de relación Q

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 \leq I

Q1 :

B ˘ • B \leq 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 (prueba de Maddux, ver Tarski y 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 .

Ejemplos

Cualquier álgebra de Boole se puede convertir en una RA interpretando la conjunción como composición (la multiplicación monoide •), es decir, x • y se define como x ∧ y . Esta interpretación requiere que la inversa interprete la identidad ( ў = y ), y que ambos residuos y \ x y x / y interpreten el condicional y → x (es decir, ¬ y ∨ x ).
El ejemplo motivador de un álgebra relacional depende de la definición de una relación binaria R en un conjunto X como cualquier subconjunto $R \subseteq X 2$ , donde $X 2$ es el cuadrado cartesiano de X . El conjunto potencia 2 ^X^² que consiste en todas las relaciones binarias en X es un álgebra de Boole. Mientras que 2 ^X^² puede convertirse en un álgebra relacional tomando $R$ $•$ $S$ $=$ $R$ $\land$ $S$ , como en el ejemplo (1) anterior, la interpretación estándar de • es en cambio $x$ $($ $R$ $•$ $S$ $)$ $z$ $= \exists$ $y$ $:$ $xRy.ySz$ . Es decir, el par ordenado $($ $x$ $,$ $z$ $)$ pertenece a la relación R • S solo cuando existe $y$ en $X$ tal que $($ $x$ $,$ $y$ $) \in$ $R$ y $($ $y$ $,$ $z$ $) \in$ $S$ . Esta interpretación determina de manera única que R \ S consiste en todos los pares $($ $y$ $,$ $z$ $)$ tales que para todo $x$ $\in$ $X$ , si xRy entonces xSz . Dualmente, S / R consiste en todos los pares $($ $x$ $,$ $y$ $)$ tales que para todo z en X , si yRz entonces xSz . La traducción $ў$ $= \neg($ $y$ $\¬$ $I$ $)$ establece entonces el inverso R ˘ de R como consistente en todos los pares $($ $y$ $,$ $x$ $)$ tales que $($ $x$ $,$ $y$ $) \in$ $R$ .
Una generalización importante del ejemplo anterior es el conjunto potencia 2 ^E donde $E \subseteq X 2$ es cualquier relación de equivalencia en el conjunto X . Esto es una generalización porque $X 2$ es en sí mismo una relación de equivalencia, es decir, la relación completa que consiste en todos los pares. Si bien 2 ^E no es una subálgebra de 2 ^X^² cuando $E$ $\neq$ $X$ $2$ (ya que en ese caso no contiene la relación $X$ $2$ , siendo el elemento superior 1 E en lugar de $X$ $2$ ), 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 álgebra de relación representable como cualquier álgebra de relación isomorfa a una subálgebra del álgebra de relación 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$ un grupo . Entonces el conjunto potencia es un álgebra relacional con las obvias operaciones del álgebra de Boole, composición dada por el producto de los subconjuntos del grupo , el recíproco por el subconjunto inverso ( ), y la identidad por el subconjunto singleton . Hay un homomorfismo de álgebra relacional incrustado en el cual envía cada subconjunto a la relación . La imagen de este homomorfismo es el conjunto de todas las relaciones invariantes por la derecha en $G$ . ${\estilo de visualización 2^{G}}$ $A^{-1}=\{a^{-1}\!:a\en A\}$ ${\estilo de visualización \{e\}}$ ${\estilo de visualización 2^{G}}$ $2^{G\veces G}$ $A\subconjunto G$ $R_{A}=\{(g,h)\en G\times G:h\en Ag\}$
Si la suma o el producto de un grupo interpretan la composición, la inversa de un grupo interpreta la inversa, la identidad de un grupo interpreta $I$ , y si R es una correspondencia biunívoca , de modo que $R ˘ • R = R • R ˘ = I$ , ^[3] entonces L es un grupo 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ó la RA en 1860, pero CS 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). Principia Mathematica se basó en gran medida en la 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 en profundidad de cuatro no tenía equivalente en RA . ^[4] 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 regresó 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 para este tema. Para más información sobre la historia de AR , véase Maddux (1991, 2006).

Software

RelMICS / Métodos relacionales en informática mantenido por Wolfram Kahl
Carsten Sinz: ARA / Un demostrador automático de teoremas para álgebras de relación
Stef Joosten, Álgebra relacional como lenguaje de programación utilizando el compilador Ampersand, Journal of Logical and Algebraic Methods in Programming, volumen 100, abril de 2018, páginas 113-129. (véase también https://ampersandtarski.github.io/)

Véase también

Notas al pie

^ Alfred Tarski (1948) "Resumen: Problemas de representación para álgebras de relación", Boletín de la AMS 54: 80.
^ Chris Brink; Wolfram Kahl; Günther Schmidt (1997). Métodos relacionales en informática . Saltador. págs.4 y 8. ISBN 978-3-211-82971-4.
^ Tarski, A. (1941), pág. 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. Un libro de consulta en lógica matemática, 1879-1931 . Universidad de Harvard. Prensa: 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". Journal of Automated Reasoning . 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, Leon ; 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. Vol. 147. Elsevier Science.
Jónsson, Bjarni ; Tsinakis, Constantino (1993). "Álgebras de relaciones como álgebras booleanas residuales". Álgebra universal . 30 (4): 469–78. doi :10.1007/BF01195378. S2CID 120642402.
Maddux, Roger (1991). "El origen de las álgebras de relación 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 relación . Estudios de lógica y fundamentos de las matemáticas. Vol. 150. Elsevier Science. ISBN 9780444520135.
Schein, Boris M. (1970) "Álgebras de relación y semigrupos de funciones", Semigroup Forum 1: 1–62
Schmidt, Gunther (2010). Matemáticas relacionales . Cambridge University Press.
Suppes, Patrick (1972) [1960]. "Capítulo 3". Teoría de conjuntos axiomática (edición reimpresa de Dover). Van Nostrand.
Tarski, Alfred (1941). "Sobre el cálculo de 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 la teoría de conjuntos sin variables. Providence RI: American Mathematical Society. ISBN 9780821810415.

Enlaces externos

Yohji AKAMA, Yasuo Kawahara y Hitoshi Furusawa, "Construcción de 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 funtores".
RP de Freitas y Viana, "Un resultado de completitud para el álgebra de relaciones con ligantes".
Peter Jipsen:
- Álgebras de relación
- "Fundamentos de relaciones y álgebra de Kleene".
- "Investigaciones asistidas por computadora de álgebras de relación".
- "Un sistema Gentzen y decidibilidad para redes residuales".
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 FCA del álgebra de relaciones".
- "Álgebra de relaciones y FCA" Enlaces a publicaciones y software
Kahl, Wolfram y Gunther Schmidt : Exploración de álgebras de relación (finitas) utilizando herramientas escritas en Haskell. y herramientas de álgebra de relación con Haskell de la Universidad McMaster .