Hispanopedia Wiki
Articulo de referencia

Composición de relaciones

Composición R ; S {\displaystyle R\mathbin {;} S} ( flechas magenta ) de ejemplo de relaciones binarias R {\displaystyle R} ( rojo ) y S {\displaystyle S} ( azul ) En las matemá...

Hispanopedia WikiContenido en espanolLectura gratuita
ComposiciónR;S{\displaystyle R\mathbin {;} S}( flechas magenta ) de ejemplo de relaciones binariasR{\displaystyle R}( rojo ) yS{\displaystyle S}( azul )

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{\displaystyle R\mathbin {;} S}a partir de dos relaciones binarias dadasR{\displaystyle R}yS{\displaystyle S}En el cálculo de relaciones , la composición de 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 un padre. En lógica algebraica se dice que la relación "es tío de" (incógnitaUz{\displaystyle xUz}) es la composición de relaciones "es hermano de" (incógnitaBy{\displaystyle xBy}) y "es padre de" (yPAGz{\displaystyle yPz}). U=B;PAG es equivalente a: incógnitaUz si y solo si ∃y. incógnitaBy y yPAGz.{\displaystyle U=B\mathbin {;} P\quad {\text{ es equivalente a: }}\quad xUz{\text{ si y solo si }}\exists y.\ xBy{\text{ y }}yPz.}

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

Definición

SiR⊆incógnita×Y{\displaystyle R\subsetequ X\times Y}yS⊆Y×Z{\displaystyle S\subseteq Y\times Z}son dos relaciones binarias, entonces su composiciónR;S{\displaystyle R\mathbin {;} S}es la relación R;S={(incógnita,z)∈incógnita×Z: existe y∈Y de tal manera que (incógnita,y)∈R y (y,z)∈S}.{\displaystyle R\mathbin {;} S=\{(x,z)\in X\times Z:{\text{ existe }}y\in Y{\text{ tal que }}(x,y)\in R{\text{ y }}(y,z)\in S\}.}

En otras palabras,R;S⊆incógnita×Z{\displaystyle R\mathbin {;} S\subseteq X\times Z}se define por la regla que dice(incógnita,z)∈R;S{\displaystyle (x,z)\in R\mathbin {;} S}si y solo si existe un elementoy∈Y{\displaystyle y\in Y}de tal manera queincógnitaRySz{\displaystyle x\,R\,y\,S\,z}(eso es, (incógnita,y)∈R{\displaystyle (x,y)\in R}y(y,z)∈S{\displaystyle (y,z)\in S}). [ 5 ] : 13

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 Matemáticas relacionales (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 ]

Un pequeño círculo(R∘S){\displaystyle (R\circ S)}John M. Howie ha utilizado la notación infija de composición de relaciones en sus libros sobre semigrupos de relaciones. [ 10 ] Sin embargo, el círculo pequeño se utiliza ampliamente para representar la composición de funciones.gramo(F(incógnita))=(gramo∘F)(incógnita){\displaystyle g(f(x))=(g\circ f)(x)}, que invierte la secuencia de texto de la secuencia de operaciones. El círculo pequeño se usó en las páginas introductorias de Graphs and Relations [ 5 ] : 18 hasta que se eliminó en favor de la yuxtaposición (sin notación infija). Yuxtaposición(RS){\displaystyle (RS)}En álgebra, se usa comúnmente para indicar multiplicación, por lo que también puede indicar multiplicación relativa.

Además, con la notación circular, se pueden usar subíndices. Algunos autores [ 11 ] prefieren escribir∘l{\displaystyle \circ _{l}}y∘r{\displaystyle \circ _{r}}explícitamente cuando sea 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 :∘{\displaystyle \circ }Se utiliza para denotar la composición tradicional (derecha), mientras que la composición izquierda se denota con un punto y coma grueso. Los símbolos Unicode son ⨾ y ⨟. [ 12 ] [ 13 ]

Generalizaciones matemáticas

Relaciones binariasR⊆incógnita×Y{\displaystyle R\subsetequ X\times Y}son morfismosR:incógnita→Y{\displaystyle R:X\to Y}en la categoría de relacionesRmil{\displaystyle {\mathsf {Rel}}}Sus objetos son conjuntos , sus morfismos son relaciones binarias y la composición de morfismos es exactamente la composición de relaciones tal como se definió anteriormente. La categoría de conjuntosSmit{\displaystyle {\mathsf {Conjunto}}}de conjuntos y funciones es una subcategoría deRmil{\displaystyle {\mathsf {Rel}}}donde los mapas incógnita→Y{\displaystyle X\to Y}son funcionesF:incógnita→Y{\displaystyle f:X\to Y}.

Dada una categoría regularincógnita{\displaystyle \mathbb {X} }, su categoría de relaciones internasRmil(incógnita){\displaystyle {\mathsf {Rel}}(\mathbb {X} )}tiene los mismos objetos que incógnita{\displaystyle \mathbb {X} }, pero ahora los morfismos incógnita→Y{\displaystyle X\to Y}son dados por subobjetosR⊆incógnita×Y{\displaystyle R\subsetequ X\times Y}enincógnita{\displaystyle \mathbb {X} }. [ 14 ] Formalmente, estos son tramos mónicos conjuntos entreincógnita{\displaystyle X}yY{\displaystyle Y}Las categorías de relaciones internas son alegorías . En particularRmil(Smit)≅Rmil{\displaystyle {\mathsf {Rel}}({\mathsf {Set}})\cong {\mathsf {Rel}}}Dado un campok{\displaystyle k}(o, más generalmente, un dominio ideal principal ), la categoría de relaciones internas a las matrices sobrek{\displaystyle k},Rmil(METROat(k)),{\displaystyle {\mathsf {Rel}}({\mathsf {Mat}}(k)),}tiene morfismosnorte→metro{\displaystyle n\to m}los subespacios linealesR⊆knorte⊕kmetro{\displaystyle R\subseteq k^{n}\oplus k^{m}}. La categoría de relaciones lineales sobre el cuerpo finitoF2{\displaystyle \mathbb {F} _{2}}es isomorfo al cálculo ZX de cúbits sin fase módulo escalares.

Propiedades

  • La composición de las relaciones es asociativa :R;(S;T)=(R;S);T.{\displaystyle R\mathbin {;} (S\mathbin {;} T)=(R\mathbin {;} S)\mathbin {;} T.}
  • La relación inversa deR;S{\displaystyle R\mathbin {;} S}es(R;S)T=ST;RT.{\displaystyle (R\mathbin {;} S)^{\textsf {T}}=S^{\textsf {T}}\mathbin {;} R^{\textsf {T}}.}Esta propiedad convierte el conjunto de todas las relaciones binarias en un conjunto en un semigrupo con involución .
  • La composición de funciones (parciales) (es decir, relaciones funcionales) es nuevamente una función (parcial).
  • SiR{\displaystyle R}yS{\displaystyle S}son inyectivos , entoncesR;S{\displaystyle R\mathbin {;} S}es inyectivo, lo cual, a la inversa, junto con el requisito de queS{\displaystyle S}también queda total enrango(R){\displaystyle {\text{rango}}(R)}[ 15 ] implica la inyectividad de soloR.{\displaystyle R.}
  • SiR{\displaystyle R}yS{\displaystyle S}son sobreyectivas , entoncesR;S{\displaystyle R\mathbin {;} S}es sobreyectiva, lo que a la inversa implica la sobreyectividad de soloS.{\displaystyle S.}
  • El conjunto de relaciones binarias en un conjuntoincógnita{\displaystyle X}(es decir, relaciones deincógnita{\displaystyle X}aincógnita{\displaystyle X}) junto con la composición de relaciones (izquierda o derecha) forma un monoide con cero, donde el mapa identidad enincógnita{\displaystyle X}es el elemento neutro , y el conjunto vacío es el elemento cero .

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 columna correspondientes a los objetos comparados. Trabajar con dichas matrices implica la aritmética booleana con1+1=1{\displaystyle 1+1=1}y1×1=1.{\displaystyle 1\times 1=1.}Una entrada en el producto matricial de dos matrices lógicas será1{\displaystyle 1}, entonces, solo si la fila y la columna multiplicadas tienen una correspondiente1{\displaystyle 1}Así, la matriz lógica de una composición de relaciones se puede hallar 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 mediante silogismos hipotéticos y sorites ». [ 16 ]

Relaciones heterogéneas

Consideremos una relación heterogénea.R⊆A×B{\displaystyle R\subseteq A\times B}, es decir, dondeA{\displaystyle A}yB{\displaystyle B}pueden ser conjuntos distintos. Luego, utilizando la composición de relacionesR{\displaystyle R}con su recíprocoRT,{\displaystyle R^{\textsf {T}},}existen relaciones homogéneasR;RT{\displaystyle R\mathbin {;} R^{\textsf {T}}}(enA{\displaystyle A}) yRT;R{\displaystyle R^{\textsf {T}}\mathbin {;} R}(enB{\displaystyle B}).

Si para todosincógnita∈A{\displaystyle x\in A}existe algoy∈B,{\displaystyle y\in B,}de tal manera queincógnitaRy{\displaystyle xRy}(eso es,R{\displaystyle R}es una relación (izquierda) total ), entonces para todoincógnita{\displaystyle x},incógnitaR;RTincógnita{\displaystyle xR\mathbin {;} R^{\textsf {T}}x}de modo queR;RT{\displaystyle R\mathbin {;} R^{\textsf {T}}}es una relación reflexiva oI⊆R;RT{\displaystyle \mathrm {I} \subseteq R\mathbin {;} R^{\textsf {T}}}donde I es la relación de identidad{(incógnita,incógnita):incógnita∈A}.{\displaystyle \{(x,x):x\in A\}.}De manera similar, siR{\displaystyle R}entonces es una relación sobreyectivaRT;R⊇I={(incógnita,incógnita):incógnita∈B}.{\displaystyle R^{\textsf {T}}\mathbin {;} R\supseteq \mathrm {I} =\{(x,x):x\in B\}.} En este casoR⊆R;RT;R.{\displaystyle R\subseteq R\mathbin {;} R^{\textsf {T}}\mathbin {;} R.}La inclusión opuesta se produce en el caso de una relación difuncional .

La composiciónR¯T;R{\displaystyle {\bar {R}}^{\textsf {T}}\mathbin {;} R}se utiliza para distinguir relaciones del tipo de Ferrer, que satisfacenR;R¯T;R=R.{\displaystyle R\mathbin {;} {\bar {R}}^{\textsf {T}}\mathbin {;} R=R.}

Ejemplo

DejarA={\displaystyle A=}{ Francia, Alemania, Italia, Suiza } yB={\displaystyle B=}{ francés, alemán, italiano } con la relaciónR{\displaystyle R}dado poraRb{\displaystyle aRb}cuandob{\displaystyle b}es un idioma nacional dea.{\displaystyle a.} Dado que ambosA{\displaystyle A}yB{\displaystyle B}es finito,R{\displaystyle R}puede representarse mediante una matriz lógica , suponiendo que las filas (de arriba a abajo) y las columnas (de izquierda a derecha) están ordenadas alfabéticamente: (100010001111).{\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.}

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

En consecuencia,RT;R{\displaystyle R^{\textsf {T}}\,;R}es la relación universal enB,{\displaystyle B,}Por lo tanto, dos idiomas cualesquiera comparten una nación donde ambos se hablan (de hecho: Suiza). A la inversa, la pregunta de si dos naciones dadas comparten un idioma se puede responder utilizandoR;RT.{\displaystyle R\,;R^{\textsf {T}}.}

Reglas de Schröder

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

SiS{\displaystyle S}es una relación binaria, seaST{\displaystyle S^{\textsf {T}}}representan la relación inversa , también llamada transpuesta . Entonces las reglas de Schröder son Q;R⊆S es equivalente a QT;S¯⊆R¯ es equivalente a S¯;RT⊆Q¯.{\displaystyle Q\mathbin {;} R\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}\mathbin {;} {\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}\mathbin {;} R^{\textsf {T}}\subseteq {\bar {Q}}.} Verbalmente, una equivalencia puede obtenerse a partir de otra: seleccione el primer o segundo factor y transpóngalo; luego complemente las otras dos relaciones y permutérelas. [ 5 ] : 15–19

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 ] Él escribió [ 18 ]L;METRO⊆norte implica norte¯;METROT⊆L¯.{\displaystyle L\mathbin {;} M\subseteq N{\text{ implies }}{\bar {N}}\mathbin {;} M^{\textsf {T}}\subseteq {\bar {L}}.}

Mediante las reglas de Schröder y la complementación se puede resolver una relación desconocida.incógnita{\displaystyle X}en relación con inclusiones tales como R;incógnita⊆Syincógnita;R⊆S.{\displaystyle R\mathbin {;} X\subseteq S\quad {\text{and}}\quad X\mathbin {;} R\subseteq S.} Por ejemplo, según la regla de SchröderR;incógnita⊆S implica RT;S¯⊆incógnita¯,{\displaystyle R\mathbin {;} X\subseteq S{\text{ implies }}R^{\textsf {T}}\mathbin {;} {\bar {S}}\subseteq {\bar {X}},}y la complementación daincógnita⊆RT;S¯¯,{\displaystyle X\subseteq {\overline {R^{\textsf {T}}\mathbin {;} {\bar {S}}}},}que se llama el residuo izquierdo deS{\displaystyle S}porR{\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 (origen), y el residuo derecho presupone el mismo codominio (rango, destino). El cociente simétrico presupone que dos relaciones comparten un dominio y un codominio.

Definiciones:

  • Resto izquierdo:A∖B:=AT;B¯¯{\displaystyle A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}\mathbin {;} {\bar {B}}}}}[ 19 ]
  • Residual derecho:D/do:=D¯;doT¯{\displaystyle D/C\mathrel {:=} {\overline {{\bar {D}}\mathbin {;} C^{\textsf {T}}}}}
  • Cociente simétrico:syq⁡(mi,F):=miT;F¯¯∩mi¯T;F¯{\displaystyle \operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}\mathbin {;} {\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}\mathbin {;} F}}}

Utilizando las reglas de Schröder,A;incógnita⊆B{\displaystyle A\mathbin {;} X\subseteq B}es equivalente aincógnita⊆A∖B.{\displaystyle X\subseteq A\backslash B.}Por lo tanto, el residuo izquierdo es la mayor relación que satisfaceA;incógnita⊆B.{\displaystyle A\mathbin {;} X\subseteq B.}De manera similar, la inclusiónY;do⊆D{\displaystyle Y\mathbin {;} C\subseteq D}es equivalente aY⊆D/do,{\displaystyle Y\subseteq D/C,}y el residuo derecho es la mayor relación que satisfaceY;do⊆D.{\displaystyle Y\mathbin {;} C\subseteq D.}[ 2 ] : 43–6

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

Unirse: otra forma de composición

Un operador de horquilla(<){\displaystyle (<)}Se ha introducido para fusionar dos relacionesdo:H→A{\displaystyle c:H\to A}yd:H→B{\displaystyle d:H\to B}endo(<)d:H→A×B.{\displaystyle c\,(<)\,d:H\to A\times B.}La construcción depende de proyeccionesa:A×B→A{\displaystyle a:A\times B\to A}yb:A×B→B,{\displaystyle b:A\times B\to B,}entendido como relaciones, lo que significa que existen relaciones recíprocas.aT{\displaystyle a^{\textsf {T}}}ybT.{\displaystyle b^{\textsf {T}}.}Entonces elbifurcación dedo{\displaystyle c}yd{\displaystyle d}está dado por [ 20 ]do(<)d := do;aT∩ d;bT.{\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 lo generalnorte{\displaystyle n}-relaciones de lugar paranorte≥2,{\displaystyle n\geq 2,}es la operación de unión del álgebra relacional . La composición usual de dos relaciones binarias, tal como se define aquí, se puede obtener tomando su unión, lo que da como resultado 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) .

Véase tambié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. 1 2 3 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. 1 2 Daniel D. Merrill (1990) Augustus De Morgan y la lógica de las relaciones , página 121, Kluwer Academic ISBN 9789400920477
  5. 1 2 3 Gunther Schmidt y Thomas Ströhlein (1993) Relaciones y grafos , Springer books
  6. ↑ Ernst Schröder (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, Monografía LMS n.° 12, Clarendon Press ISBN 0-19-851194-9
  11. ^ Kilp, Knauer y Mikhalev, pág. 7
  12. ^ ISO/IEC 13568:2002(E), pág. 23
  13. ↑ Consulte U+2A3E y U+2A1F en FileFormat.info
  14. ↑ "relaciones internas" . nlab . Consultado el 26 de septiembre de 2023 .
  15. ↑ Vea la imagen para ver un ejemplo dondeR;S{\displaystyle R\mathbin {;} S}es inyectivo, peroR{\displaystyle R}no lo es
  16. ↑ 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
  17. ↑ Vaughan Pratt, Los orígenes del cálculo de relaciones , de la Universidad de Stanford.
  18. ↑ De Morgan indicó los contrarios con minúsculas, conversión como M −1 y la inclusión con )), por lo que su notación fuenorteMETRO−1)) l.{\displaystyle nM^{-1}))\ l.}
  19. ↑ no confundir con diferencia de conjuntos
  20. ↑ 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.