Composición de las relaciones

Operacion matematica

En las matemáticas de las relaciones binarias , la composición de las 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 las relaciones se llama multiplicación relativa , ^[1] y su resultado se llama 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 uno de sus padres. En lógica algebraica se dice que la relación del tío ( ) es la composición de las relaciones "es hermano de" ( ) y "es padre de" ( ). ${\displaystyle xUz}$ ${\displaystyle xBy}$ ${\displaystyle yPz}$

$${\displaystyle U=BP\quad {\text{ is equivalent to: }}\quad xByPz{\text{ if and only if }}xUz.}$$

A partir de Augustus De Morgan , ^[3] la forma tradicional de razonamiento por silogismo ha sido subsumida por 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;S}$

$${\displaystyle R;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;S\subseteq X\times Z}$ ${\displaystyle (x,z)\in R;S}$ ${\displaystyle y\in Y}$ ${\displaystyle x\,R\,y\,S\,z}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle (y,z)\in S}$

Variaciones notacionales

El punto y coma como notación infija para la composición de relaciones se remonta al libro de texto de Ernst Schroder de 1895. ^[6] Gunther Schmidt ha renovado el uso del punto y coma, particularmente en Matemáticas Relacionales (2011). ^{[2] : 40  [7]} El uso de 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 del 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ó en favor de la yuxtaposición (sin notación infija). La yuxtaposición se usa comúnmente en álgebra para indicar 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 se aplica primero la relación izquierda o derecha. Una variación adicional que se encuentra en informática es la notación Z : se usa para denotar la composición tradicional (derecha), pero ⨾ ( U+ 2A3E ⨾ Z NOTACIÓN COMPOSICIÓN RELACIONAL ) denota composición izquierda. ^{[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 los morfismos es exactamente la composición de las 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 tramos mónicos conjuntos entre y . Las categorías de relaciones internas son alegorías . En particular . Dado un campo (o más generalmente un dominio ideal principal ), la categoría de relaciones internas a matrices sobre tiene morfismos de subespacios lineales . La categoría de relaciones lineales sobre el campo finito es isomorfa a los escalares de módulo de cálculo ZX del qubit libre de fase . ${\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 las relaciones es asociativa : ${\displaystyle R;(S;T)=(R;S);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\,;S}$ ${\displaystyle (R\,;S)^{\textsf {T}}=S^{\textsf {T}}\,;R^{\textsf {T}}.}$
• La composición de funciones (parciales) (es decir, relaciones funcionales) es nuevamente una función (parcial).
• Si y son inyectivos , entonces es inyectivo, lo que a la inversa implica sólo la inyectividad de ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\,;S}$ ${\displaystyle R.}$
• Si y son sobreyectivos , entonces es sobreyectivo, lo que a la inversa implica sólo la sobreyectividad de ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R\,;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 de 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 están representadas por 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 columna correspondientes a los objetos comparados. Trabajar con tales matrices implica la aritmética booleana con y Una entrada en la matriz producto de dos matrices lógicas será 1, entonces, sólo si la fila y la columna multiplicadas tienen un correspondiente 1. Por lo tanto, se puede encontrar la matriz lógica de una composición de relaciones. 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 extraídas tradicionalmente mediante silogismos y soritos hipotéticos ". ^[15] ${\displaystyle 1+1=1}$ ${\displaystyle 1\times 1=1.}$

Relaciones heterogéneas

Considere una relación heterogénea , es decir, donde y son conjuntos distintos. Luego, usando la composición de la relación con su recíproco, hay 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 todos existe algo tal que (es decir, es una relación total (izquierda) ), entonces para todos así eso es una relación reflexiva o donde I es la relación de identidad De manera similar, si es una relación sobreyectiva entonces ${\displaystyle x\in A}$ ${\displaystyle y\in B,}$ ${\displaystyle xRy}$ ${\displaystyle R}$ ${\displaystyle x,xRR^{\textsf {T}}x}$ ${\displaystyle RR^{\textsf {T}}}$ ${\displaystyle I\subseteq RR^{\textsf {T}}}$ ${\displaystyle \{(x,x):x\in A\}.}$ ${\displaystyle R}$

$${\displaystyle R^{\textsf {T}}R\supseteq I=\{(x,x):x\in B\}.}$$

difuncional ${\displaystyle R\subseteq RR^{\textsf {T}}R.}$

La composición se utiliza 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 ambos y son finitos, se pueden representar mediante una matriz lógica , asumiendo 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 la matriz 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 la matriz invertida se calcula como: ${\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 dos lenguas cualesquiera comparten una nación donde se hablan ambas (de hecho: Suiza). Viceversa, la pregunta de si dos naciones determinadas comparten un idioma se puede responder usando ${\displaystyle R^{\textsf {T}}\,;R}$ ${\displaystyle B,}$ ${\displaystyle R\,;R^{\textsf {T}}.}$

reglas de schröder

Para un conjunto dado, la colección de todas las relaciones binarias forma una red booleana ordenada por inclusión . Recuerde 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, representemos la relación inversa , también llamada transpuesta . Entonces las reglas de Schröder son ${\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}}.}$$

^{[5] : 15-19}

Aunque Ernst Schröder detalló esta transformación de la inclusión de una composición de relaciones , 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 como ${\displaystyle X}$

$${\displaystyle RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.}$$

residual izquierdo de by ${\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 exhiben tres cocientes: residual izquierdo, residual derecho y cociente simétrico. El residual izquierdo de dos relaciones se define suponiendo que tienen el mismo dominio (fuente), y el residual derecho supone el mismo codominio (rango, objetivo). 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 residual izquierdo es la relación más satisfactoria De manera similar, la inclusión es equivalente a y el residual derecho es la relación más satisfactoria ^{[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 el 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 Luego el ${\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}}.}$bifurcación deyestá dada por^[18] ${\displaystyle c}$ ${\displaystyle d}$

$${\displaystyle c\,(<)\,d~\mathrel {:=} ~c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.}$$

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

Ver también

• Composición demoniaca
• Amigo de un amigo  : contacto humano que existe gracias a un amigo en común.

Notas

1. Bjarni Jónssen (1984) "Álgebras máximas de relaciones binarias", en Contribuciones a la teoría de grupos , editor de KI Appel American Mathematical Society ISBN  978-0-8218-5035-0
2. Gunther Schmidt (2011) Matemáticas relacionales , Enciclopedia de las matemáticas y sus aplicaciones, vol. 132, Prensa de la Universidad de Cambridge 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. Prensa de la Universidad de Cambridge. pag. 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 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, monografía n.º 12 de LMS, Clarendon Press ISBN 0-19-851194-9 
11. Kilp, Knauer y Mikhalev, pag. 7
12. ISO/IEC 13568:2002(E), pág. 23
13. Carácter Unicode: composición relacional de notación Z de FileFormat.info
14. "relaciones internas". laboratorio . 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 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 en minúsculas, conversión como M ⁻¹ e 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, libros de Springer , 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 .