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 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 .
Las palabras tío y tía indican una relación compuesta: para que una persona sea tío, debe ser hermano de un padre (o hermana de una tía). En lógica algebraica se dice que la relación del tío ( xUz ) es la composición de relaciones "es un hermano de" ( xBy ) y "es un padre de" ( yPz ).
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
En otras palabras, está definido por la regla que dice si y solo si hay un elemento tal que (es decir y ). [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 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 del punto y coma coincide con la notación para la composición de funciones utilizada (principalmente por los 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 John M. Howie lo ha utilizado para la notación infija de la composición de relaciones en sus libros sobre 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 operación. El círculo pequeño se utilizó en las páginas introductorias de Graphs and Relations [5] : 18 hasta que se eliminó a favor de la yuxtaposición (sin notación infija). Yuxtaposición se usa comúnmente en álgebra para significar multiplicación, por lo que también puede significar multiplicación relativa.
Además, con la notación circular, se pueden utilizar subíndices. Algunos autores [11] prefieren escribir y 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 :se usa para denotar la composición tradicional (derecha), pero ⨾ (un punto y coma abierto grueso con punto de código Unicode U + 2A3E) denota la composición izquierda. [12] [13]
Las relaciones binarias a veces se consideran morfismos en una categoría Rel que tiene los conjuntos como objetos. En Rel , la composición de morfismos es exactamente la composición de relaciones como se definió anteriormente. La categoría Conjunto de conjuntos es una subcategoría de Rel que tiene los mismos objetos pero menos morfismos.
Propiedades
- La composición de las relaciones es asociativa :
- La relación inversa de R ; S es ( R ; S ) T = S T ; R T . Esta propiedad hace que el conjunto de todas las relaciones binarias de un conjunto sea un semigrupo con involución .
- La composición de funciones (parciales) (es decir, relaciones funcionales) es nuevamente una función (parcial).
- Si R y S son inyectivos , entonces R ; S es inyectiva, lo que implica por el contrario solamente la inyectividad de R .
- Si R y S son sobreyectivos , entonces R ; S es sobreyectiva, lo que implica por el contrario sólo el sobreyectividad de S .
- El conjunto de relaciones binarias en un conjunto X (es decir, relaciones de X a X ) junto con la composición de la relación (izquierda o derecha) forma un monoide con cero, donde el mapa de identidad en X es el elemento neutral y el conjunto vacío es el cero. elemento .
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 tales matrices implica la aritmética booleana con 1 + 1 = 1 y 1 × 1 = 1. 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. 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 mediante hipotéticos silogismos y sorites". [14]
Relaciones heterogéneas
Considere una relación heterogénea R ⊆ A × B , es decir, donde A y B son conjuntos distintos. Luego, usando la composición de la relación R con su inversa R T , existen relaciones homogéneas RR T (en A ) y R T R (en B ).
Si ∀ x ∈ A ∃ y ∈ B xRy (es decir, R es una relación total (izquierda) ), entonces ∀ x xRR T x de modo que RR T es una relación reflexiva o I ⊆ RR T donde I es la relación de identidad { x I x : x ∈ A }. De manera similar, si R es una relación sobreyectiva, entonces
- R T R ⊇ Yo = { x Yo x : x ∈ B }. En este caso R ⊆ RR T R . La inclusión opuesta ocurre para una relación difuncional .
La composición se utiliza para distinguir relaciones del tipo de Ferrer, que satisfacen
Ejemplo
Sea A = {Francia, Alemania, Italia, Suiza} y B = {francés, alemán, italiano} con la relación R dada por aRb cuando b es un idioma nacional de a . La matriz lógica para R está dada por
- Usando la relación inversa R T , se pueden responder dos preguntas: "¿Hay un traductor?" tiene respuesta la relación universal en B . La pregunta internacional, "¿Habla mi idioma?" es respondido por Esta matriz simétrica, que representa una relación homogénea en A , está asociada con el gráfico de estrella S 3 aumentado por un bucle en cada nodo.
Reglas de Schröder
Para un conjunto V dado , la colección de todas las relaciones binarias en V forma un retículo booleano ordenado por inclusión (⊆). Recuerde que la complementación revierte la inclusión:En el cálculo de relaciones [15] es común representar el complemento de un conjunto por una barra superior:
Si S es una relación binaria, searepresentan la relación inversa , también llamada transpuesta . Entonces las reglas de Schröder son
Verbalmente, se puede obtener una equivalencia de otra: seleccionar el primer o segundo factor y transponerlo; luego complementa las otras dos relaciones y permutalas. [5] : 15-19
Aunque Ernst Schröder detalló esta transformación de una 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ó
- [dieciséis]
Con las reglas de Schröder y la complementación se puede resolver una relación desconocida X en inclusiones de relación como
Por ejemplo, según la regla de Schröder y la complementación da que se llama el residual izquierda de S por R .
Cocientes
Así como la composición de relaciones es un tipo de multiplicación que da como resultado un producto, algunas composiciones se comparan con la división y producen cocientes. Aquí se muestran tres cocientes: residual izquierdo, residual derecho y cociente simétrico. El residuo izquierdo de dos relaciones se define asumiendo que tienen el mismo dominio (fuente) y el residuo derecho supone el mismo codominio (rango, objetivo). El cociente simétrico supone que dos relaciones comparten un dominio y un codominio.
Definiciones:
- Residuo izquierdo:
- Residuo derecho:
- Cociente simétrico:
Usando las reglas de Schröder, AX ⊆ B es equivalente a X ⊆ AB . Así, el residual izquierda es la mayor relación satisfacer AX ⊆ B . Del mismo modo, la inclusión YC ⊆ D es equivalente a Y ⊆ D / C , y la residual derecha es la mayor relación satisfacer YC ⊆ D . [2] : 43–6
Join: otra forma de composición
Un operador de tenedor (<) se ha introducido para el fusible dos relaciones c : H → A y D : H → B en c (<) d : H → A × B . La construcción depende de las proyecciones una : A × B → A y B : A × B → B , entendidas como las relaciones, lo que significa que hay relaciones converse una T y B T . A continuación, el tenedor de c y d está dada por
- [17]
Otra forma de composición de relaciones, que se aplica a las relaciones generales de n lugares para n ≥ 2, 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 combinació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 Unir (SQL) .
Ver también
- Composición demoníaca
- Amigo de un amigo
Notas
- ^ 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
- ^ a b c Gunther Schmidt (2011) Matemáticas relacionales , Enciclopedia de las matemáticas y sus aplicaciones, vol. 132, Cambridge University PressISBN 978-0-521-76268-7
- ^ A. De Morgan (1860) "Sobre el silogismo: IV y sobre la lógica de las relaciones"
- ↑ a b Daniel D. Merrill (1990) Augustus De Morgan y la lógica de las relaciones , página 121, Kluwer AcademicISBN 9789400920477
- ^ a b c Gunther Schmidt y Thomas Ströhlein (1993) Relaciones y gráficos , libros de Springer
- ^ Ernst Schroder (1895) Álgebra und Logik der Relative
- ^ 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/
- ^ 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
- ^ Rick Nouwen y otros (2016) Semántica dinámica §2.2, de la Enciclopedia de Filosofía de Stanford
- ^ John M. Howie (1995) Fundamentos de la teoría del semigrupo , página 16, Monografía de LMS # 12, Clarendon PressISBN 0-19-851194-9
- ^ Kilp, Knauer y Mikhalev, p. 7
- ^ ISO / IEC 13568: 2002 (E), p. 23
- ^ Carácter Unicode: composición relacional de notación Z de FileFormat.info
- ^ Irving Copilowish (diciembre de 1948) "Desarrollo matricial del cálculo de relaciones", Journal of Symbolic Logic 13 (4): 193-203 Enlace de Jstor , cita de la página 203
- ^ Vaughn Pratt Los orígenes del cálculo de relaciones , de la Universidad de Stanford
- ↑ De Morgan indicó los contrarios con minúsculas, conversión como M −1 e inclusión con)), por lo que su notación fue
- ^ 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 de coronas y gráficos , Exposiciones de De Gruyter en matemáticas vol. 29, Walter de Gruyter , ISBN 3-11-015248-7 .