Composición de relaciones

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, y su resultado se denomina producto relativo. 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 un tío, debe ser el hermano de un padre. En la lógica algebraica se dice que la relación del tío (${\displaystyle xUz}$) es la composición de las relaciones "es un hermano de" (${\displaystyle xBy!$) y "es un padre de" (${\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, la forma tradicional de razonamiento mediante silogismo ha sido absorbida por las expresiones lógicas relacionales y su composición.

Si ${\displaystyle R\subseteq X\times Y}$ y ${\displaystyle S\subseteq Y\times Z}$ son dos relaciones binarias, entonces su composición ${\displaystyle R\mathbin {} S}$ es la relación $${\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, ${\displaystyle R\mathbin S\subseteq X\times Z}$ se define por la regla que dice ${\displaystyle (x,z)\in R\mathbin {} S}$ si y sólo si hay un elemento ${\displaystyle y\in Y}$ tales que ${\displaystyle x\,R\,Y\,S\,z}$ (es decir, ${\displaystyle (x,y)\in R}$ y ${\displaystyle (y,z)\in S}$).

El uso del 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. Gunther Schmidt ha renovado el uso del punto y coma, en particular en Relational Mathematics (2011). 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, así como con la notación para la conjunción dinámica dentro de la semántica dinámica lingüística.

Un pequeño círculo ${\displaystyle (R\circ S)}$ ha sido utilizado para la notación infix de la composición de las relaciones por John M. Howie en sus libros considerando semigrupos de relaciones. Sin embargo, el pequeño círculo se utiliza ampliamente para representar la composición de las funciones ${\displaystyle g(f(x)=(g\circ f)(x)}$, que inversas la secuencia de texto de la secuencia de operación. El pequeño círculo se utilizó en las páginas introductorias Gráficos y Relaciones hasta que se dejó caer a favor de la yuxtaposición (sin notación de infijo). Juxtaposition ${\displaystyle (RS)}$ es comúnmente utilizado en álgebra para significar la multiplicación, así también, puede significar la multiplicación relativa.

Además de la notación del círculo, se pueden utilizar subscriptos. Algunos autores prefieren escribir ${\displaystyle \circ _{l}$ y ${\displaystyle \circ _{r}$ explícitamente cuando sea necesario, dependiendo de si la relación izquierda o derecha es la primera aplicada. Otra variación encontrada en la ciencia informática es la notación Z: ${\displaystyle \circ }$ se utiliza para denotar la composición tradicional (derecha), mientras que la composición izquierda es denotada por un semicolón de grasa. Los símbolos unicode son ⨾ y ⨟.

Relaciones binarias ${\displaystyle R\subseteq X\times Y}$ son morfismos ${\displaystyle R:X\to Sí.$ en la categoría ${\displaystyle {\Mathsf {Rel}}$. In 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 definidas anteriormente. La categoría Set de conjuntos y funciones es una subcategoría ${\displaystyle {\Mathsf {Rel}}$ donde los mapas ${\displaystyle X\to Y}$ funciones ${\displaystyle f:X\to Sí.$.

Dada una categoría regular ${\displaystyle \mathbb {X}$, su categoría de relaciones internas ${\displaystyle {\mathsf {Rel}(\mathbb {X})}$ tiene los mismos objetos ${\displaystyle \mathbb {X}$pero ahora los morfismos ${\displaystyle X\to Y}$ son dados por subobjetos ${\displaystyle R\subseteq X\times Y}$ dentro ${\displaystyle \mathbb {X}$. Formalmente, estos son lapsos monicos conjuntos entre ${\displaystyle X}$ y ${\displaystyle Sí.$. Categorías de relaciones internas son alegorías. En particular ${\displaystyle {\Mathsf {Rel}} {\Mathsf {Set})\cong {\mathsf {Rel}}}$. Dado un campo ${\displaystyle k}$ (o más generalmente un dominio ideal principal), la categoría de relaciones internas a matrices sobre ${\displaystyle k}$, ${\displaystyle {\mathsf {Rel}({\mathsf {Mat}(k)),}$ tiene morfismos ${\displaystyle n\to m}$ los subespacios lineales ${\displaystyle R\subseteq k^{n}\oplus k^{m}$. La categoría de relaciones lineales sobre el campo finito ${\displaystyle \mathbb {F} _{2}$ es isomorfo a los escalares sin fase de qubit ZX-calculus modulo.

• La composición de las relaciones es asociativa: ${\displaystyle R\mathbin (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin T.$
• La relación conversa ${\displaystyle R\mathbin {} S}$ es ${\displaystyle (R\mathbin {;} S)^{\textsf {T}=S^{\textsf Mathbin. R^{\textsf {T}$ Esta propiedad hace el conjunto de todas las relaciones binarias en un conjunto de un semigrupo con involution.
• La composición de funciones (partiales) (es decir, relaciones funcionales) es otra vez una función (partial).
• Si ${\displaystyle R.$ y ${\displaystyle S.$ son inyectables, entonces ${\displaystyle R\mathbin {} S}$ es inyectable, que implica, por el contrario, sólo la injetividad ${\displaystyle R.$
• Si ${\displaystyle R.$ y ${\displaystyle S.$ son subjetivos, entonces ${\displaystyle R\mathbin {} S}$ es subjetivo, que implica por el contrario sólo la subjetividad ${\displaystyle S.}$
• El conjunto de relaciones binarias en un conjunto ${\displaystyle X}$ (es decir, relaciones de ${\displaystyle X}$ a ${\displaystyle X}$) junto con (izquierda o derecha) la composición de relación forma un monoide con cero, donde el mapa de identidad en ${\displaystyle X}$ es el elemento neutral, y el conjunto vacío es el elemento cero.

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 correspondiente a objetos comparados. Trabajar con tales matrices implica la aritmética booleana con ${\displaystyle 1+1=1}$ y ${\displaystyle 1\times 1=1.}$ Una entrada en el producto de matriz de dos matrices lógicas será 1, entonces, sólo si la fila y la columna multiplicada tienen un correspondiente 1. Por lo tanto, la matriz lógica de una composición de relaciones se puede encontrar computando el producto matriz de las matrices que representan los factores de la composición. "Las matrices constituyen un método para computación las conclusiones tradicionalmente sacadas por medio de silogismos hipotéticos y sorites."

Considerar una relación heterogénea ${\displaystyle R\subseteq A\times B;}$ es decir, dónde ${\displaystyle A}$ y ${\displaystyle B}$ son conjuntos distintos. Luego utilizando la composición de la relación ${\displaystyle R.$ con su contra ${\displaystyle R^{\textsf},}$ hay relaciones homogéneas ${\displaystyle RR^{\textosf {T}}$ (sobre ${\displaystyle A}$) y ${\displaystyle R^{\textsf}R}$ (sobre ${\displaystyle B}$).

Si para todos ${\displaystyle x\in A}$ existe ${\displaystyle y\in B,}$ tales que ${\displaystyle xRy}$ (es decir, ${\displaystyle R.$ es una relación (izquierda-)total), entonces para todos ${\displaystyle x,xRR^{\textsf {T}x}$ así ${\displaystyle RR^{\textosf {T}}$ es una relación reflexiva o ${\displaystyle \mathrm {I} \subseteq RR^{\textsf {T}}$ donde soy la relación de identidad ${\displaystyle \{(x,x):x\in A\}$ Del mismo modo, si ${\displaystyle R.$ es una relación subjetiva entonces $${\displaystyle R^{\textsf {T}R\supseteq \mathrm {I} =\{(x,x):x\in B\}.}$$ En este caso ${\displaystyle R\subseteq RR^{\textosf R.$ La inclusión opuesta ocurre para una relación difuncional.

La composición ${\displaystyle {\bar} {\textosf}R}$ se utiliza para distinguir las relaciones del tipo Ferrer, que satisfacen ${\displaystyle R{\bar {R}\textosf R=R.$

Vamos. ${\displaystyle A=$ Francia, Alemania, Italia, Suiza y ${\displaystyle B=$ { Francés, Alemán, Italiano } con la relación ${\displaystyle R.$ dado por ${\displaystyle ARb!$ cuando ${\displaystyle b}$ es un idioma nacional ${\displaystyle a.}$Desde ambos ${\displaystyle A}$ y ${\displaystyle B}$ es finito, ${\displaystyle R.$ puede ser representado por una matriz lógica, asumiendo filas (de arriba a abajo) y columnas (izquierda a derecha) se ordenan alfabéticamente: $${\splaystyle {\begin{pmatrix}1 tendría0\0}}}}$$

La relación conversa ${\displaystyle R^{\textsf {T}}$ corresponde a la matriz transpuesta, y la composición de relación ${\displaystyle R^{\textsf}R}$ corresponde al producto matriz ${\displaystyle R^{\textsf}R}$ cuando la summación es implementada por la disyunción lógica. Resulta que el ${\displaystyle 3\times 3}$ matriz ${\displaystyle R^{\textsf}R}$ contiene un 1 en cada posición, mientras que el producto de matriz revertido calcula como: $${\displaystyle RR^{\textsf {T}={\begin{pmatrix}1 tendría0 ventaja1\0 correspond1}}}}}$$Esta matriz es simétrica y representa una relación homogénea sobre ${\displaystyle A.}$

Correspondientemente, ${\displaystyle R^{\textsf {T}\,R}$ es la relación universal ${\displaystyle B,}$ Por lo tanto, cualquier dos idiomas comparten una nación donde ambos se hablan (de hecho: Suiza). Viceversa, la pregunta de si dos naciones dadas comparten un idioma puede ser contestada usando ${\displaystyle R\,;R^{\textsf {T}}$

Para un conjunto dado ${\displaystyle V.$ la colección de todas las relaciones binarias en ${\displaystyle V}$ forma una lattiza booleana ordenada por inclusión ${\displaystyle (\subseteq).}$ Recordar que la complementación revierte la inclusión: ${\displaystyle A\subseteq B{\text{ implica }B^{\complemento Subseteq A^{\complement }$ En el cálculo de las relaciones es común representar el complemento de un conjunto por una barra superior: ${\displaystyle {\bar {\fn}=A^{\complement} }$

Si ${\displaystyle S.$ es una relación binaria, dejar ${\displaystyle S^{\textsf}}$ representa la relación conversa, también llamada transpose. Entonces las reglas de Schröder son $${\displaystyle QR\subseteq S\quad {\text{ is equivalent to }\quad Q^{\textsf Suseteq {\bar {R}\quad {\text{ is equivalent to }\quad {\bar}}}\quad {\bar}}R^{\textf Subseteq {\bar}$$Verbalmente, una equivalencia puede obtenerse de otra: seleccione el primer o segundo factor y transponerlo; luego complemente las otras dos relaciones y permutelas.

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 primero articulaba la transformación como Theorem K en 1860. Él escribió $${\displaystyle LM\subseteq N{ implica }{\bar {N}M^{\textsf Subseteq {\bar}$$

Con reglas y complementos Schröder se puede resolver para una relación desconocida ${\displaystyle X}$ in relation inclusions such as $${\displaystyle RX\subseteq S\quad {\text{and}\quad XR\subseteq S.}$$Por ejemplo, por la regla Schröder ${\displaystyle RX\subseteq S{\text{ implies }R^{\textsf Subseteq {\bar}$ y la complementación da ${\displaystyle X\subseteq {\overline {\textosf} {}}}}$ que se llama residual izquierdo ${\displaystyle S.$ por ${\displaystyle R.$.

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:

• Residuo izquierdo: ${\displaystyle A\backslash B\mathrel {:=} {\fnMicrosoft Sans} {\fnK}} {\fnMicrosoft Sans Serif}} {\fnMicrosoft Sans Serif}$
• Residuo derecho: ${\displaystyle D/C\mathrel {:=} {\fnMicrosoft Sans Serif} {T}}}$
• Cociente simétrico: ${\displaystyle \operatorname {syq}(E,F)\mathrel {:=} {\fnMicrosoft Sans Serif}\cap {\fnMicrosoft Sans Serif}\cap {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {T}F}}$

Usando las reglas de Schröder, ${\displaystyle AX\subseteq B}$ equivale a ${\displaystyle X\subseteq A\backslash B.}$ Así el residual izquierdo es la mayor relación satisfactoria ${\displaystyle AX\subseteq B.}$ Del mismo modo, la inclusión ${\displaystyle YC\subseteq D}$ equivale a ${\displaystyle Y\subseteq D/C,}$ y el residual derecho es la mayor relación satisfactoria ${\displaystyle YC\subseteq D.}$

Se puede practicar la lógica de los residuos con el Sudoku.

Un tenedor ${\displaystyle (traducido)}$ ha sido introducida para fusionar dos relaciones ${\displaystyle c:H\to A}$ y ${\displaystyle d:H\to B}$ en ${\displaystyle c\,(traducido)\,d:H\to A\times B.}$ La construcción depende de proyecciones ${\displaystyle a:A\times B\to A}$ y ${\displaystyle b:A\times B\to B,}$ entendido como relaciones, lo que significa que hay relaciones conversas ${\displaystyle a^{\textsf}}$ y ${\displaystyle b^{\textsf {}}$ Entonces el tenedor de ${\displaystyle c}$ y ${\displaystyle d}$ es dado por $${\displaystyle c\,(a)\,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 generales ${\displaystyle n}$- relaciones de lugar para ${\displaystyle n\geq 2,}$ es Únase operación de álgebra relacional. La composición habitual de dos relaciones binarias definidas aquí se puede obtener tomando su unión, dando lugar a una relación ternaria, seguida de una proyección que elimina el componente medio. Por ejemplo, en el lenguaje de consulta SQL hay la unión de operación (SQL).

• Composición demográfica
• Amigo de un amigo – Contacto humano que existe debido a un amigo mutuo

• M. Kilp, U. Knauer, A.V. Mikhalev (2000) Monoids, Actos y Categorías con Aplicaciones para los Productos y Gráficos, De Gruyter Exposiciones en Matemáticas vol. 29, Walter de Gruyter,ISBN 3-11-015248-7.