Relación entre dos conjuntos, definida por un conjunto de pares ordenados
En matemáticas , una relación en un conjunto puede ser válida o no entre dos miembros dados del conjunto. Por ejemplo, " es menor que " es una relación sobre el conjunto de los números naturales ; se cumple, por ejemplo, entre los valores 1 y 3 (indicados como 1 < 3 ), y también entre 3 y 4 (indicados como 3 < 4 ), pero no entre los valores 3 y 1 ni entre 4 y 4 , es decir , 3 <1 y 4 <4 ambos se evalúan como falso. Como otro ejemplo, " es hermana de " es una relación en el conjunto de todas las personas, por ejemplo, entre Marie Curie y Bronisława Dłuska , y viceversa. Los miembros del conjunto pueden no estar en relación "hasta cierto punto": o están en relación o no.
Formalmente, una relación R sobre un conjunto X puede verse como un conjunto de pares ordenados ( x , y ) de miembros de X. [1]
La relación R se cumple entre xey si ( x , y ) es miembro de R. Por ejemplo, la relación " es menor que " en los números naturales es un conjunto infinito R menor de pares de números naturales que contiene tanto (1,3) como (3,4) , pero ni (3,1) ni (4). ,4) . La relación " es un divisor no trivial de " en el conjunto de números naturales de un dígito es lo suficientemente pequeña como para mostrarse aquí: R dv = { (2,4), (2,6), (2,8), (3 ,6), (3,9), (4,8) } ; por ejemplo , 2 es un divisor no trivial de 8 , pero no al revés, por lo tanto (2,8) ∈ R dv , pero (8,2) ∉ R dv .
Si R es una relación que se cumple para x e y, a menudo se escribe xRy . Para las relaciones más comunes en matemáticas, se introducen símbolos especiales, como " < " para "es menor que" , y " | " para "es un divisor no trivial de" y, el más popular, " = " para "es igual a" . Por ejemplo, " 1 < 3 ", " 1 es menor que 3 " y " (1,3) ∈ R menos " significan todos lo mismo; algunos autores también escriben " (1,3) ∈ (<) ".
Se investigan varias propiedades de las relaciones. Una relación R es reflexiva si xRx se cumple para todo x , e irreflexiva si xRx se cumple para ningún x . Es simétrico si xRy siempre implica yRx , y asimétrico si xRy implica que yRx es imposible. Es transitivo si xRy y yRz siempre implican xRz . Por ejemplo, " es menor que " es irreflexivo, asimétrico y transitivo, pero ni reflexivo ni simétrico. " es hermana de " es transitiva, pero no reflexiva (por ejemplo, Pierre Curie no es hermana de él mismo), ni simétrica ni asimétrica; si bien ser irreflexivo o no puede ser una cuestión de definición (¿es cada mujer hermana de sí misma?), " es antepasado de " es transitivo, mientras que " es padre de " no lo es. Se conocen teoremas matemáticos sobre combinaciones de propiedades de relación, como "una relación transitiva es irreflexiva si, y sólo si, es asimétrica".
De particular importancia son las relaciones que satisfacen ciertas combinaciones de propiedades. Un orden parcial es una relación reflexiva, antisimétrica y transitiva, [2]
una relación de equivalencia es una relación reflexiva, simétrica y transitiva, [3]
una función es una relación única por la derecha y total por la izquierda (vea abajo). [4] [5]
El concepto anterior de relación [a] se ha generalizado para admitir relaciones entre miembros de dos conjuntos diferentes ( relación heterogénea , como " yace sobre " entre el conjunto de todos los puntos y el de todas las rectas en geometría), relaciones entre tres o más conjuntos ( relación finita , como "la persona x vive en la ciudad y en el momento z " ), y relaciones entre clases [b] (como " es un elemento de " en la clase de todos los conjuntos, consulte Relación binaria § Conjuntos versus clases ).
Definición
Dado un conjunto X , una relación R sobre X es un conjunto de pares ordenados de elementos de X , formalmente: R ⊆ { ( x , y ) | x , y ∈ X } . [1] [9]
La declaración ( x , y ) ∈ R dice " x está relacionada con R con y " y está escrita en notación infija como xRy . [6] [7] El orden de los elementos es importante; si x ≠ y entonces yRx puede ser verdadero o falso independientemente de xRy . Por ejemplo, 3 divide a 9 , pero 9 no divide a 3 .
Representación de relaciones
Una relación R en un conjunto finito X puede representarse como:
Gráfico dirigido : Cada miembro de X corresponde a un vértice; una arista dirigida de x a y existe si y solo si ( x , y ) ∈ R .
Matriz booleana : Los miembros de X están ordenados en alguna secuencia fija x 1 , ..., x n ; la matriz tiene dimensiones n × n , siendo el elemento en la línea i , columna j, si ( x i , x j ) ∈ R , y, de lo contrario.
Gráfico 2D : como generalización de una matriz booleana, una relación en el conjunto –infinito– R de números reales se puede representar como una figura geométrica bidimensional: usando coordenadas cartesianas , dibuja un punto en ( x , y ) siempre que ( x , y ) ∈ R .
Una relación transitiva [c] R en un conjunto finito X también se puede representar como
Diagrama de Hasse : Cada miembro de X corresponde a un vértice; Los bordes dirigidos se dibujan de manera que exista una ruta dirigida de x a y si y solo si ( x , y ) ∈ R . En comparación con una representación de gráfico dirigido, un diagrama de Hasse necesita menos aristas, lo que da lugar a una imagen menos enredada. Dado que la relación " existe un camino dirigido de x a y " es transitiva, en los diagramas de Hasse sólo se pueden representar relaciones transitivas. Por lo general, el diagrama se presenta de manera que todos los bordes apunten hacia arriba y se omiten las flechas.
Por ejemplo, en el conjunto de todos los divisores de 12 , defina la relación R div por
x R div y si x es divisor de y y x ≠ y .
Formalmente, X = { 1, 2, 3, 4, 6, 12 } y R div = { (1,2), (1,3), (1,4), (1,6), (1,12 ), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) } . La representación de R div como una matriz booleana se muestra en la tabla del medio; En la imagen de la izquierda se muestra la representación como diagrama de Hasse y como gráfico dirigido.
Los siguientes son equivalentes:
x R div y es cierto.
( x , y ) ∈ R div .
Existe una ruta de x a y en el diagrama de Hasse que representa R div .
Existe una arista de xay en el gráfico dirigido que representa R div .
En la matriz booleana que representa R div , el elemento en la línea x , columna y es "".
Como otro ejemplo, defina la relación R el en R por
x R el y si x 2 + xy + y 2 = 1 .
La representación de R el como un gráfico 2D obtiene una elipse, ver imagen de la derecha. Dado que R no es finito, no se puede utilizar ni un gráfico dirigido, ni una matriz booleana finita, ni un diagrama de Hasse para representar R el .
Propiedades de las relaciones
Algunas propiedades importantes que puede tener una relación R sobre un conjunto X son:
para todo x ∈ X , no xRx . Por ejemplo, > es una relación irreflexiva, pero ≥ no lo es.
Las 2 alternativas anteriores no son exhaustivas; por ejemplo, la relación roja y = x 2 dada en el siguiente diagrama no es ni irreflexiva ni reflexiva, ya que contiene el par (0,0) , pero no (2,2) , respectivamente.
para todo x , y ∈ X , si xRy entonces yRx . Por ejemplo, "es pariente consanguíneo de" es una relación simétrica, porque x es pariente consanguíneo de y si y sólo si y es pariente consanguíneo de x .
para todo x , y ∈ X , si xRy e yRx entonces x = y . Por ejemplo, ≥ es una relación antisimétrica; también lo es > , pero de forma vacía (la condición en la definición siempre es falsa). [10]
para todo x , y ∈ X , si xRy entonces no yRx . Una relación es asimétrica si y sólo si es a la vez antisimétrica e irreflexiva. [11] Por ejemplo, > es una relación asimétrica, pero ≥ no lo es.
Nuevamente, las 3 alternativas anteriores están lejos de ser exhaustivas; Como ejemplo de los números naturales, la relación xRy definida por x > 2 no es simétrica (por ejemplo, 5 R 1 , pero no 1 R 5 ) ni antisimétrica (por ejemplo, 6 R 4 , pero también 4 R 6 ), y mucho menos asimétrica.
para todo x , y , z ∈ X , si xRy e yRz entonces xRz . Una relación transitiva es irreflexiva si y sólo si es asimétrica. [12] Por ejemplo, "es antepasado de" es una relación transitiva, mientras que "es padre de" no lo es.
para todo x , y ∈ X , si x ≠ y entonces xRy o yRx . Por ejemplo, en los números naturales, < está conexo, mientras que " es divisor de " no lo es (por ejemplo, ni 5 R 7 ni 7 R 5 ).
para todo x , y ∈ X , xRy o yRx . Por ejemplo, en los números naturales, ≤ está fuertemente conexo, pero < no lo está. Una relación es fuertemente conexa si, y sólo si, es conexa y reflexiva.
Propiedades de unicidad:
Inyectiva [d] (también llamada única por izquierda [13] )
Para todo x , y , z ∈ X , si xRy y zRy entonces x = z . Por ejemplo, las relaciones verde y azul en el diagrama son inyectivas, pero la roja no lo es (ya que relaciona −1 y 1 con 1 ), ni la negra (ya que relaciona −1 y 1 con 0 ). .
Funcional [14] [15] [16] [d] (también llamado único por la derecha , [13] definido por la derecha [17] o univalente [8] )
Para todo x , y , z ∈ X , si xRy y xRz entonces y = z . Esta relación se llama función parcial . Por ejemplo, las relaciones roja y verde en el diagrama son funcionales, pero la azul no lo es (ya que relaciona 1 con −1 y 1 ), ni la negra (ya que relaciona 0 con −1 y 1). .
Propiedades de totalidad:
Serie [d] (también llamada total o total izquierdo )
Para todo x ∈ X , existe algún y ∈ X tal que xRy . Esta relación se llama función multivaluada . Por ejemplo, las relaciones rojo y verde en el diagrama son totales, pero la azul no lo es (ya que no relaciona −1 con ningún número real), ni la negra (ya que no relaciona 2 con ningún número real). ). Como otro ejemplo, > es una relación serial sobre números enteros. Pero no es una relación serial entre los números enteros positivos, porque no hay y en los números enteros positivos tales que 1 > y . [18] Sin embargo, < es una relación serial entre los números enteros positivos, los números racionales y los números reales. Toda relación reflexiva es serial: para una x dada , elija y = x .
Sobreyectiva [d] (también llamada total derecha [13] o sobre )
Para todo y ∈ Y , existe un x ∈ X tal que xRy . Por ejemplo, las relaciones verde y azul en el diagrama son sobreyectivas, pero la roja no lo es (ya que no relaciona ningún número real con −1 ), ni la negra (ya que no relaciona ningún número real con 2). ).
Combinaciones de propiedades
Las relaciones que satisfacen ciertas combinaciones de las propiedades anteriores son particularmente útiles y, por lo tanto, han recibido nombres propios.
Una relación que es reflexiva, simétrica y transitiva. También es una relación simétrica, transitiva y serial, ya que estas propiedades implican reflexividad.
Una función que es inyectiva y sobreyectiva. Por ejemplo, la relación verde en el diagrama es una biyección, pero las rojas, azules y negras no lo son.
Operaciones sobre relaciones.
unión [e]
Si R y S son relaciones sobre X entonces R ∪ S = { ( x , y ) | xRy o xSy } es la relación de unión de R y S . El elemento de identidad de esta operación es la relación vacía. Por ejemplo, ≤ es la unión de < y = , y ≥ es la unión de > y = .
Intersección [e]
Si R y S son relaciones sobre X entonces R ∩ S = { ( x , y ) | xRy y xSy } es la relación de intersección de R y S . El elemento de identidad de esta operación es la relación universal. Por ejemplo, "es una carta inferior del mismo palo que" es la intersección de "es una carta inferior que" y "pertenece al mismo palo que".
Composición [e]
Si R y S son relaciones sobre X entonces S ∘ R = { ( x , z ) | existe y ∈ X tal que xRy y ySz } (también denotado por R ; S ) es el producto relativo de R y S . El elemento de identidad es la relación de identidad. El orden de R y S en la notación S ∘ R , utilizada aquí, concuerda con el orden de notación estándar para la composición de funciones . Por ejemplo, la composición "es madre de" ∘ "es padre de" produce "es abuelo materno de", mientras que la composición "es madre de" ∘ "es madre de" produce "es abuela de". Para el primer caso, si x es el padre de y y y es la madre de z , entonces x es el abuelo materno de z .
conversar [e]
Si R es una relación entre los conjuntos X e Y, entonces R T = { ( y , x ) | xRy } es la relación inversa de R sobre Y y X . Por ejemplo, = es el recíproco de sí mismo, al igual que ≠ , y < y > son recíprocos entre sí, al igual que ≤ y ≥ .
Complemento [e]
Si R es una relación sobre X entonces R = { ( x , y ) | x , y ∈ X y no xRy } (también denotado por R o ¬ R ) es la relación complementaria de R . Por ejemplo, = y ≠ son complementos de cada uno, al igual que ⊆ y ⊈ , ⊇ y ⊉ , y ∈ y ∉ , y, para pedidos totales , también < y ≥ , y > y ≤ . El complemento de la relación inversa R T es el inverso del complemento:
Restricción [e]
Si R es una relación sobre X y S es un subconjunto de X, entonces R | S = {( x , y ) | xRy y x , y ∈ S } es elrelación de restricción de R a S . La expresión R | S = {( x , y ) | xRy y x ∈ S }es elrelación de restricción izquierda de R a S ; la expresión R | S = {( x , y ) | xRy e y ∈ S }se llamarelación de restricción por la derecha de R a S . Si una relación esreflexiva, irreflexiva,simétrica,antisimétrica,asimétrica,transitiva,total,tricotómica, deorden parcial,total,de orden débil estricto,de preorden total(orden débil), o de unarelación de equivalencia, entonces también lo son sus restricciones. Sin embargo, la clausura transitiva de una restricción es un subconjunto de la restricción de la clausura transitiva, es decir, en general no es igual. Por ejemplo, restringir la relación " x es padre de y " a mujeres produce la relación " x es madre de la mujer y "; su cierre transitivo no relaciona a una mujer con su abuela paterna. Por otro lado, la clausura transitiva de "es padre de" es "es antepasado de"; su restricción a las mujeres relaciona a una mujer con su abuela paterna.
Se dice que una relación R sobre los conjuntos X e Y escontenida en una relación S sobre X e Y , escrita R ⊆ S , si R es un subconjunto de S , es decir, para todo x ∈ X e y ∈ Y , si xRy , entonces xSy . Si R está contenido en S y S está contenido en R , entonces R y S sellamanigualesescritos R = S. Si R está contenido en S pero S no está contenido en R , entoncesse dice que R esmás pequeño que S , escrito R ⊊ S . Por ejemplo, en losnúmeros racionales, la relación>es menor que≥, e igual a la composición> ∘ >.
Teoremas sobre las relaciones
Una relación es asimétrica si, y sólo si, es antisimétrica e irreflexiva.
Una relación transitiva es irreflexiva si, y sólo si, es asimétrica.
Una relación es reflexiva si, y sólo si, su complemento es irreflexivo.
Una relación es fuertemente conexa si, y sólo si, es conexa y reflexiva.
Una relación es igual a su inversa si, y sólo si, es simétrica.
Una relación es conexa si, y sólo si, su complemento es antisimétrico.
Una relación es fuertemente conexa si, y sólo si, su complemento es asimétrico. [20]
Si la relación R está contenida en la relación S , entonces
Si R es reflexivo, conexo, fuertemente conexo, total por izquierda o total por derecha, entonces también lo es S.
Si S es irreflexivo, asimétrico, antisimétrico, único por la izquierda o único por la derecha, entonces también lo es R.
Una relación es reflexiva, irreflexiva, simétrica, asimétrica, antisimétrica, conexa, fuertemente conexa y transitiva si su recíproca lo es, respectivamente.
El concepto anterior de relación se ha generalizado para admitir relaciones entre miembros de dos conjuntos diferentes. Dados los conjuntos X e Y , una relación heterogénea R sobre X e Y es un subconjunto de { ( x , y ) | x ∈ X , y ∈ Y } . [1] [21]
Cuando X = Y , se obtiene el concepto de relación descrito anteriormente; a menudo se le llama relación homogénea (o endorelación ) [22] [23] para distinguirla de su generalización. Las propiedades y operaciones anteriores que están marcadas como " [d] " y " [e] ", respectivamente, se generalizan a relaciones heterogéneas. Un ejemplo de relación heterogénea es "el océano x limita con el continente y ". Los ejemplos más conocidos son funciones [f] con distintos dominios y rangos, como sqrt : N → R + .
^ ab CI Lewis (1918) Un estudio de la lógica simbólica, págs. 269-279, a través de Internet Archive
^ ab Schmidt 2010, capítulo. 5
^ Enderton 1977, capítulo 3. p. 40
^ Smith, Eggen y St. Andre 2006, pág. 160
^ Nievergelt 2002, pag. 158
^ Flaška y col. 2007, p.1 Lema 1.1 (iv). Esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
^ a b C Kilp, Knauer y Mikhalev 2000, p. 3. Las mismas cuatro definiciones aparecen a continuación: Pahl & Damrath 2001, p. 506, Best 1996, págs. 19–21, Riemann 1999, págs. 21–22
^ Van Gasteren 1990, pag. 45.
^ "Relación funcional - Enciclopedia de Matemáticas". encyclopediaofmath.org . Consultado el 13 de junio de 2024 .
^ "relación funcional en nLab". ncatlab.org . Consultado el 13 de junio de 2024 .
Codd, Edgar Frank (junio de 1970). "Un modelo relacional de datos para grandes bancos de datos compartidos" (PDF) . Comunicaciones de la ACM . 13 (6): 377–387. doi :10.1145/362384.362685. S2CID 207549016 . Consultado el 29 de abril de 2020 .
Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Cierres Transitivos de Relaciones Binarias I (PDF) . Praga: Escuela de Matemáticas – Universidad Carolina de Física. Archivado desde el original (PDF) el 2 de noviembre de 2013.
Kilp, Mati; Knauer, Ulrich; Mikhalev, Alejandro (2000). Monoides, actos y categorías: con aplicaciones a gráficos y productos de coronas . Berlín: De Gruyter . ISBN 978-3-11-015248-7.
Mäs, Stephan (2007), "Razonamiento sobre restricciones de integridad semántica espacial", Teoría de la información espacial: octava conferencia internacional, COSIT 2007, Melbourne, Australia, 19 al 23 de septiembre, Actas , Apuntes de conferencias en informática, vol. 4736, Springer, págs. 285–302, doi :10.1007/978-3-540-74788-8_18
Müller, ME (2012). Descubrimiento de conocimiento relacional . Prensa de la Universidad de Cambridge. ISBN 978-0-521-19021-3.
Nievergelt, Yves (2002), Fundamentos de la lógica y las matemáticas: aplicaciones a la informática y la criptografía , Springer-Verlag
Pahl, Peter J.; Damrath, Rudolf (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Medios de ciencia y negocios de Springer. ISBN 978-3-540-67995-0.
Peirce, Charles Sanders (1873). "Descripción de una notación para la lógica de relativos, resultante de una amplificación de las concepciones del cálculo lógico de Boole". Memorias de la Academia Estadounidense de Artes y Ciencias . 9 (2): 317–178. Código bibliográfico : 1873MAAAS...9..317P. doi :10.2307/25058006. hdl : 2027/hvd.32044019561034 . JSTOR 25058006 . Consultado el 5 de mayo de 2020 .
Riemann, Robert-Christoph (1999). Modelado de sistemas concurrentes: métodos estructurales y semánticos en el cálculo de la red de Petri de alto nivel . Editorial Herbert Utz. ISBN 978-3-89675-629-9.
Rosenstein, Joseph G. (1982), Ordenamientos lineales , Academic Press, ISBN 0-12-597680-1
Schmidt, Günther ; Ströhlein, Thomas (1993). Relaciones y gráficos: matemáticas discretas para informáticos. Berlín: Springer. ISBN 978-3-642-77970-1.
Smith, Douglas; Eggen, Mauricio; St. Andre, Richard (2006), Una transición a las matemáticas avanzadas (6.ª ed.), Brooks/Cole, ISBN 0-534-39900-2
Van Gasteren, Antonetta (1990). Sobre la forma de los argumentos matemáticos . Berlín: Springer. ISBN 9783540528494.
Yao, YY; Wong, SKM (1995). "Generalización de conjuntos aproximados utilizando relaciones entre valores de atributos" (PDF) . Actas de la segunda conferencia anual conjunta sobre ciencias de la información : 30–33.