Composición de relaciones

Operación matemática

En las matemáticas de las relaciones binarias , la composición de relaciones es la formación de una nueva relación binaria R  ; S a partir de dos relaciones binarias dadas R y S. En el cálculo de relaciones , la composición de relaciones se denomina multiplicación relativa , ^[1] y su resultado se denomina producto relativo . ^{[2] : 40} La composición de funciones es el caso especial de composición de relaciones donde todas las relaciones involucradas son funciones .

La palabra tío indica una relación compuesta: para que una persona sea tío, debe ser hermano de un progenitor. En lógica algebraica se dice que la relación de tío ( ) es la composición de las relaciones "es hermano de" ( ) y "es progenitor de" ( ). ${\displaystyle xUz}$ ${\displaystyle xBy}$ ${\displaystyle yPz}$ $${\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xUz{\text{ if and only if }}\exists y\ xByPz.}$$

A partir de Augustus De Morgan , ^[3] la forma tradicional de razonamiento mediante silogismo ha sido subsumida por las expresiones lógicas relacionales y su composición. ^[4]

Definición

Si y son dos relaciones binarias, entonces su composición es la relación ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle S\subseteq Y\times Z}$ ${\displaystyle R\mathbin {;} S}$ $${\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.}$$

En otras palabras, se define por la regla que dice si y sólo si existe un elemento tal que (es decir, y ). ^{[5] : 13} ${\displaystyle R\mathbin {;} S\subseteq X\times Z}$ ${\displaystyle (x,z)\in R\mathbin {;} S}$ ${\displaystyle y\in Y}$ ${\displaystyle x\,R\,y\,S\,z}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle (y,z)\in S}$

Variaciones de notación

El punto y coma como notación infija para la composición de relaciones se remonta al libro de texto de Ernst Schröder de 1895. ^[6] Gunther Schmidt ha renovado el uso del punto y coma, particularmente en Relational Mathematics (2011). ^{[2] : 40  [7]} El uso del punto y coma coincide con la notación para la composición de funciones utilizada (principalmente por científicos informáticos) en la teoría de categorías , ^[8] así como la notación para la conjunción dinámica dentro de la semántica dinámica lingüística . ^[9]

John M. Howie ha utilizado un círculo pequeño para la notación infija de composición de relaciones en sus libros que consideran semigrupos de relaciones. ^[10] Sin embargo, el círculo pequeño se usa ampliamente para representar la composición de funciones , que invierte la secuencia de texto de la secuencia de operaciones. El círculo pequeño se utilizó en las páginas introductorias de Graphs and Relations ^{[5] : 18} hasta que se abandonó a favor de la yuxtaposición (sin notación infija). La yuxtaposición se usa comúnmente en álgebra para significar multiplicación, por lo que también puede significar multiplicación relativa. ${\displaystyle (R\circ S)}$ ${\displaystyle g(f(x))=(g\circ f)(x)}$ ${\displaystyle (RS)}$

Además de la notación circular, se pueden utilizar subíndices. Algunos autores ^[11] prefieren escribir y explícitamente cuando es necesario, dependiendo de si la relación izquierda o derecha es la primera que se aplica. Otra variación que se encuentra en la informática es la notación Z : se utiliza para indicar la composición tradicional (derecha), mientras que la composición izquierda se indica con un punto y coma grueso. Los símbolos Unicode son ⨾ y ⨟. ^{[12] [13]} ${\displaystyle \circ _{l}}$ ${\displaystyle \circ _{r}}$ ${\displaystyle \circ }$

Generalizaciones matemáticas

Las relaciones binarias son morfismos en la categoría . En Rel los objetos son conjuntos , los morfismos son relaciones binarias y la composición de morfismos es exactamente la composición de relaciones como se definió anteriormente. La categoría Conjunto de conjuntos y funciones es una subcategoría de donde los mapas son funciones . ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle R:X\to Y}$ ${\displaystyle {\mathsf {Rel}}}$ ${\displaystyle {\mathsf {Rel}}}$ ${\displaystyle X\to Y}$ ${\displaystyle f:X\to Y}$

Dada una categoría regular , su categoría de relaciones internas tiene los mismos objetos que , pero ahora los morfismos están dados por subobjetos en . ^{[14] Formalmente, estos son} intervalos monónicos conjuntos entre y . Las categorías de relaciones internas son alegorías . En particular . Dado un cuerpo (o más generalmente un dominio ideal principal ), la categoría de relaciones internas a matrices sobre , tiene morfismos los subespacios lineales . La categoría de relaciones lineales sobre el cuerpo finito es isomorfa al cálculo ZX de qubits libres de fase módulo escalares. ${\displaystyle \mathbb {X} }$ ${\displaystyle {\mathsf {Rel}}(\mathbb {X} )}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X\to Y}$ ${\displaystyle R\subseteq X\times Y}$ ${\displaystyle \mathbb {X} }$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k)),}$ ${\displaystyle n\to m}$ ${\displaystyle R\subseteq k^{n}\oplus k^{m}}$ ${\displaystyle \mathbb {F} _{2}}$

Propiedades

• La composición de relaciones es asociativa : ${\displaystyle R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}$
• La relación inversa de es Esta propiedad hace que el conjunto de todas las relaciones binarias de un conjunto sea un semigrupo con involución . ${\displaystyle R\mathbin {;} S}$ ${\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}$
• La composición de funciones (parciales) (es decir, relaciones funcionales) es nuevamente una función (parcial).
• Si y son inyectivas , entonces es inyectiva, lo que a la inversa implica sólo la inyectividad de ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle R.}$
• Si y son sobreyectivas , entonces es sobreyectiva, lo que a la inversa implica sólo la sobreyectividad de ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\mathbin {;} S}$ ${\displaystyle S.}$
• El conjunto de relaciones binarias en un conjunto (es decir, relaciones de a ) junto con la composición de relaciones (izquierda o derecha) forma un monoide con cero, donde el mapa identidad en es el elemento neutro y el conjunto vacío es el elemento cero . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$

Composición en términos de matrices

Las relaciones binarias finitas se representan mediante matrices lógicas . Las entradas de estas matrices son cero o uno, dependiendo de si la relación representada es falsa o verdadera para la fila y la columna correspondientes a los objetos comparados. Trabajar con tales matrices implica la aritmética booleana con y Una entrada en el producto matricial de dos matrices lógicas será 1, entonces, solo si la fila y la columna multiplicadas tienen un 1 correspondiente. Por lo tanto, la matriz lógica de una composición de relaciones se puede encontrar calculando el producto matricial de las matrices que representan los factores de la composición. "Las matrices constituyen un método para calcular las conclusiones tradicionalmente extraídas por medio de silogismos hipotéticos y sorites ". ^[15] ${\displaystyle 1+1=1}$ ${\displaystyle 1\times 1=1.}$

Relaciones heterogéneas

Consideremos una relación heterogénea , es decir, donde y son conjuntos distintos. Entonces, utilizando la composición de la relación con su recíproco, existen relaciones homogéneas (en ) y (en ). ${\displaystyle R\subseteq A\times B;}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$ ${\displaystyle R^{\textsf {T}},}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle A}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle B}$

Si para todo existe algo tal que (es decir, es una relación (izquierda-)total ), entonces para todo tal que es una relación reflexiva o donde I es la relación identidad De manera similar, si es una relación sobreyectiva entonces En este caso La inclusión opuesta ocurre para una relación difuncional . ${\displaystyle x\in A}$ ${\displaystyle y\in B,}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x,xRR^{\textsf {T}}x}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle \mathrm {I} \subseteq RR^{\textsf {T}}}$ ${\displaystyle \{(x,x):x\in A\}.}$ ${\displaystyle R}$ $${\displaystyle R^{\textsf {T}}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}$$ ${\displaystyle R\subseteq RR^{\textsf {T}}R.}$

La composición sirve para distinguir relaciones del tipo de Ferrer, que satisfacen ${\displaystyle {\bar {R}}^{\textsf {T}}R}$ ${\displaystyle R{\bar {R}}^{\textsf {T}}R=R.}$

Ejemplo

Sean { Francia, Alemania, Italia, Suiza } y { Francés, Alemán, Italiano } con la relación dada por cuando es un idioma nacional de Dado que tanto como es finito, se puede representar mediante una matriz lógica , asumiendo que las filas (de arriba a abajo) y las columnas (de izquierda a derecha) están ordenadas alfabéticamente: ${\displaystyle A=}$ ${\displaystyle B=}$ ${\displaystyle R}$ ${\displaystyle aRb}$ ${\displaystyle b}$ ${\displaystyle a.}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle R}$ $${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}$$

La relación inversa corresponde a la matriz transpuesta y la composición de la relación corresponde al producto de matrices cuando la suma se implementa mediante disyunción lógica . Resulta que la matriz contiene un 1 en cada posición, mientras que el producto de matrices invertido se calcula como: Esta matriz es simétrica y representa una relación homogénea en ${\displaystyle R^{\textsf {T}}}$ ${\displaystyle R^{\textsf {T}};R}$ ${\displaystyle R^{\textsf {T}}R}$ ${\displaystyle 3\times 3}$ ${\displaystyle R^{\textsf {T}}R}$ $${\displaystyle RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.}$$ ${\displaystyle A.}$

En consecuencia, la relación universal es que , por lo tanto, dos lenguas cualesquiera comparten una nación donde ambas se hablan (de hecho, Suiza). A la inversa, la pregunta de si dos naciones dadas comparten una lengua se puede responder utilizando ${\displaystyle R^{\textsf {T}}\,;R}$ ${\displaystyle B,}$ ${\displaystyle R\,;R^{\textsf {T}}.}$

Las reglas de Schröder

Para un conjunto dado, la colección de todas las relaciones binarias en forma una red booleana ordenada por inclusión . Recordemos que la complementación invierte la inclusión: En el cálculo de relaciones ^[16] es común representar el complemento de un conjunto mediante una barra superior: ${\displaystyle V,}$ ${\displaystyle V}$ ${\displaystyle (\subseteq ).}$ ${\displaystyle A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.}$ ${\displaystyle {\bar {A}}=A^{\complement }.}$

Si es una relación binaria, sea la relación inversa , también llamada transpuesta . Entonces las reglas de Schröder son Verbalmente, una equivalencia se puede obtener de otra: seleccione el primer o segundo factor y transpóngalo; luego complemente las otras dos relaciones y permútelas. ^{[5] : 15–19} ${\displaystyle S}$ ${\displaystyle S^{\textsf {T}}}$ $${\displaystyle QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.}$$

Aunque esta transformación de una inclusión de una composición de relaciones fue detallada por Ernst Schröder , de hecho Augustus De Morgan articuló por primera vez la transformación como Teorema K en 1860. ^[4] Escribió ^[17] $${\displaystyle LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.}$$

Con las reglas de Schröder y la complementación se puede resolver una relación desconocida en inclusiones de relaciones tales como Por ejemplo, por la regla de Schröder y la complementación se obtiene que se llama residuo izquierdo de por . ${\displaystyle X}$ $${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$$ ${\displaystyle RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},}$ ${\displaystyle X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},}$ ${\displaystyle S}$ ${\displaystyle R}$

Cocientes

Así como la composición de relaciones es un tipo de multiplicación que da como resultado un producto, algunas operaciones se comparan con la división y producen cocientes. Aquí se muestran tres cocientes: residuo izquierdo, residuo derecho y cociente simétrico. El residuo izquierdo de dos relaciones se define suponiendo que tienen el mismo dominio (fuente), y el residuo derecho supone el mismo codominio (rango, destino). El cociente simétrico supone que dos relaciones comparten un dominio y un codominio.

Definiciones:

• Residual izquierdo: ${\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}}$
• Residual derecho: ${\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}}$
• Cociente simétrico: ${\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}}$

Usando las reglas de Schröder, es equivalente a Por lo tanto, el residuo izquierdo es la relación más grande que satisface De manera similar, la inclusión es equivalente a y el residuo derecho es la relación más grande que satisface ^{[2] : 43–6} ${\displaystyle AX\subseteq B}$ ${\displaystyle X\subseteq A\backslash B.}$ ${\displaystyle AX\subseteq B.}$ ${\displaystyle YC\subseteq D}$ ${\displaystyle Y\subseteq D/C,}$ ${\displaystyle YC\subseteq D.}$

Se puede practicar la lógica de los residuos con Sudoku . ^{[ se necesita más explicación ]}

Unirse: otra forma de composición

Se ha introducido un operador de bifurcación para fusionar dos relaciones y en La construcción depende de proyecciones y se entiende como relaciones, lo que significa que hay relaciones inversas y Entonces ${\displaystyle (<)}$ ${\displaystyle c:H\to A}$ ${\displaystyle d:H\to B}$ ${\displaystyle c\,(<)\,d:H\to A\times B.}$ ${\displaystyle a:A\times B\to A}$ ${\displaystyle b:A\times B\to B,}$ ${\displaystyle a^{\textsf {T}}}$ ${\displaystyle b^{\textsf {T}}.}$La bifurcación deyestá dada por^[18] ${\displaystyle c}$ ${\displaystyle d}$ $${\displaystyle c\,(<)\,d~\mathrel {:=} ~c\mathbin {;} a^{\textsf {T}}\cap \ d\mathbin {;} b^{\textsf {T}}.}$$

Otra forma de composición de relaciones, que se aplica a las relaciones de lugar general, es la operación de unión del álgebra relacional . La composición habitual de dos relaciones binarias, como se define aquí, se puede obtener tomando su unión, lo que conduce a una relación ternaria, seguida de una proyección que elimina el componente intermedio. Por ejemplo, en el lenguaje de consulta SQL existe la operación join (SQL) . ${\displaystyle n}$ ${\displaystyle n\geq 2,}$

Véase también

• Composición demoníaca
• Amigo de un amigo  – Contacto humano que existe gracias a un amigo en común.

Notas

1. Bjarni Jónsson (1984) "Álgebras máximas de relaciones binarias", en Contribuciones a la teoría de grupos , KI Appel editor American Mathematical Society ISBN  978-0-8218-5035-0
2. Gunther Schmidt (2011) Matemáticas relacionales , Enciclopedia de matemáticas y sus aplicaciones, vol. 132, Cambridge University Press ISBN 978-0-521-76268-7 
3. A. De Morgan (1860) "Sobre el silogismo: IV y sobre la lógica de las relaciones"
4. Daniel D. Merrill (1990) Augustus De Morgan y la lógica de las relaciones , página 121, Kluwer Academic ISBN 9789400920477 
5. Gunther Schmidt y Thomas Ströhlein (1993) Relaciones y gráficos , libros de Springer
6. Ernst Schroder (1895) Álgebra und Logik der Relative
7. Paul Taylor (1999). Fundamentos prácticos de las matemáticas. Cambridge University Press. pág. 24. ISBN 978-0-521-63107-5.Una versión HTML gratuita del libro está disponible en http://www.cs.man.ac.uk/~pt/Practical_Foundations/
8. Michael Barr y Charles Wells (1998) Teoría de categorías para científicos informáticos Archivado el 4 de marzo de 2016 en Wayback Machine , página 6, de la Universidad McGill
9. Rick Nouwen y otros (2016) Semántica dinámica §2.2, de la Enciclopedia de filosofía de Stanford
10. John M. Howie (1995) Fundamentos de la teoría de semigrupos , página 16, LMS Monograph #12, Clarendon Press ISBN 0-19-851194-9 
11. Kilp, Knauer y Mikhalev, pag. 7
12. ISO/IEC 13568:2002(E), pág. 23
13. Ver U+2A3E y U+2A1F en FileFormat.info
14. "relaciones internas". nlab . Consultado el 26 de septiembre de 2023 .
15. Irving Copilowish (diciembre de 1948) "Desarrollo matricial del cálculo de relaciones", Journal of Symbolic Logic 13(4): 193–203 Enlace a Jstor, cita de la página 203
16. Vaughn Pratt Los orígenes del cálculo de relaciones, de la Universidad de Stanford
17. De Morgan indicó los contrarios con minúsculas, la conversión como M ⁻¹ y la inclusión con )), por lo que su notación fue ${\displaystyle nM^{-1}))\ l.}$
18. Gunther Schmidt y Michael Winter (2018): Topología relacional , página 26, Lecture Notes in Mathematics vol. 2208, Springer books , ISBN 978-3-319-74451-3 

Referencias

• M. Kilp, U. Knauer, AV Mikhalev (2000) Monoides, actos y categorías con aplicaciones a productos y gráficos de coronas , De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter , ISBN 3-11-015248-7 .