====== Relaciones ====== ===== Motivación ===== Con frecuencia queremos expresar que dos objetos mantienen entre sí una determinada relación. Por ejemplo: * un número es menor que otro; * un número divide a otro; * dos números tienen el mismo resto al dividirlos por 3; * una persona es progenitora de otra; * dos conjuntos tienen los mismos elementos. Podemos representar todas estas situaciones mediante relaciones. Las relaciones permiten estudiar de manera general propiedades como la simetría, la transitividad o la reflexividad. También sirven para construir otras estructuras importantes. En particular, las funciones pueden entenderse, desde un enfoque conjuntista, como relaciones que satisfacen determinadas condiciones adicionales. ===== Definición ===== Sean A y B dos conjuntos. Una relación R de A en B es un subconjunto del producto cartesiano A x B. Por tanto, R sub A x B. Si (a,b) en R, decimos que a está relacionado con b mediante R. Podemos escribir esta afirmación de forma más breve como a R b. Por tanto, a R b <-> (a,b) en R. ===== Ejemplo ===== Sean A = {1,2,3} y B = {a,b}. Podemos definir la relación R = {(1,a),(1,b),(3,b)}. Como (1,a) en R, podemos escribir 1 R a. También tenemos 1 R b y 3 R b. En cambio, 2 R a es falso, porque (2,a) noen R. Una relación no tiene por qué relacionar todos los elementos de A con algún elemento de B, ni tiene por qué relacionar cada elemento con un único elemento. En este ejemplo, 2 no está relacionado con ningún elemento de B, mientras que 1 está relacionado con dos elementos distintos. Estas posibilidades serán importantes cuando comparemos posteriormente las relaciones con las funciones. ===== Dominio de una relación ===== El dominio de una relación R sub A x B es el conjunto de los elementos de A que están relacionados con algún elemento de B. Podemos definirlo como dom(R) = {a en A : exi b en B: a R b}. En el ejemplo anterior, R = {(1,a),(1,b),(3,b)}, por lo que dom(R) = {1,3}. El elemento 2 pertenece a A, pero no pertenece al dominio efectivo de R porque no está relacionado con ningún elemento de B. ===== Imagen o rango de una relación ===== La imagen de una relación R es el conjunto de los elementos de B que están relacionados con algún elemento de A. Podemos escribir im(R) = {b en B : exi a en A: a R b}. En nuestro ejemplo, im(R) = {a,b}. Algunas fuentes utilizan también el término //rango// para este conjunto. Conviene distinguir el conjunto B con el que hemos definido la relación de su imagen efectiva: pueden existir elementos de B que no estén relacionados con ningún elemento de A. ===== Relación inversa ===== Dada una relación R sub A x B, podemos invertir el orden de cada par y obtener una relación R^-1 sub B x A. La definimos mediante b R^-1 a <-> a R b. Equivalentemente, R^-1 = {(b,a) en B x A : (a,b) en R}. Por ejemplo, si R = {(1,a),(1,b),(3,b)}, entonces R^-1 = {(a,1),(b,1),(b,3)}. Invertir dos veces una relación devuelve la relación original: (R^-1)^-1 = R. ===== Composición de relaciones ===== Supongamos que tenemos R sub A x B y S sub B x C. Podemos construir una nueva relación entre A y C. Decimos que a está relacionado con c mediante la composición cuando existe algún elemento b de B que conecta ambos pasos: a R b y b S c. Escribiremos la composición como S comp R. Por definición, a (S comp R) c <-> exi b en B: a R b y b S c. Obsérvese el orden: primero se aplica R, de A a B, y después S, de B a C. Por ejemplo, supongamos R = {(1,a),(2,b)} y S = {(a,x),(b,y)}. Entonces S comp R = {(1,x),(2,y)}. La composición de relaciones es asociativa: T comp (S comp R) = (T comp S) comp R siempre que los conjuntos implicados permitan realizar las composiciones. En general, no es conmutativa: S comp R != R comp S. De hecho, una de las dos composiciones puede estar definida en un contexto en el que la otra ni siquiera tenga los conjuntos intermedios adecuados. ===== Relaciones sobre un conjunto ===== Un caso especialmente importante aparece cuando relacionamos elementos de un conjunto A con otros elementos del mismo conjunto. Una relación sobre A es una relación R sub A x A. Por ejemplo, la relación < es una relación sobre los números reales. También lo son <= = y muchas otras relaciones habituales. Las relaciones sobre un mismo conjunto pueden satisfacer diferentes propiedades estructurales. ===== Reflexividad ===== Una relación R sobre A es reflexiva cuando todo elemento está relacionado consigo mismo: pt a en A: a R a. Por ejemplo, la relación <= sobre los números reales es reflexiva porque a <= a para todo número real a. La igualdad también es reflexiva: a = a. En cambio, la relación < no es reflexiva, porque nunca se cumple a < a. ===== Irreflexividad ===== Una relación R sobre A es irreflexiva cuando ningún elemento está relacionado consigo mismo: pt a en A: no(a R a). Por ejemplo, < es irreflexiva sobre los números reales. No debe confundirse "no ser reflexiva" con "ser irreflexiva". Una relación no reflexiva sólo necesita que exista algún elemento a para el que no se cumpla a R a. Una relación irreflexiva exige que no se cumpla a R a para ningún elemento. ===== Simetría ===== Una relación R sobre A es simétrica cuando pt a,b en A: a R b -> b R a. Por ejemplo, la relación a R b <-> %%|a-b| <= 1%% sobre los números reales es simétrica. Si a está a una distancia menor o igual que 1 de b, entonces b está a la misma distancia de a. La igualdad también es simétrica: a=b -> b=a. En cambio, < no es simétrica. De 2 < 3 no sigue 3 < 2. ===== Antisimetría ===== Una relación R sobre A es antisimétrica cuando pt a,b en A: a R b y b R a -> a=b. Esto no significa que la relación sea "lo contrario de simétrica". Una relación puede ser simultáneamente simétrica y antisimétrica. La igualdad es un ejemplo. La relación <= también es antisimétrica, porque a <= b y b <= a implican a=b. ===== Asimetría ===== Una relación R sobre A es asimétrica cuando pt a,b en A: a R b -> no(b R a). Por ejemplo, < es asimétrica. Si a < b, entonces no puede cumplirse b < a. Toda relación asimétrica es irreflexiva. Si a R a, la asimetría exigiría no(a R a), lo que resulta imposible. Toda relación asimétrica es también antisimétrica. La antisimetría exige a R b y b R a -> a=b. Pero, por asimetría, nunca pueden cumplirse simultáneamente a R b y b R a. Por tanto, el antecedente de la implicación es siempre falso y la implicación es verdadera por vacuidad. En consecuencia, asimétrica -> irreflexiva y asimétrica -> antisimétrica. Los recíprocos no son ciertos en general. ===== Transitividad ===== Una relación R sobre A es transitiva cuando pt a,b,c en A: a R b y b R c -> a R c. Por ejemplo, < es transitiva sobre los números reales. Si a < b y b < c, entonces a < c. La relación <= también es transitiva. No todas las relaciones lo son. Por ejemplo, consideremos sobre los números reales la relación a R b <-> %%|a-b| <= 1%%. Tenemos 0 R 1 y 1 R 2, pero 0 R 2 es falso, porque %%|0-2| = 2 > 1%%. Por tanto, esta relación no es transitiva. ===== Resumen de propiedades ===== Para una relación R sobre A: * Reflexiva: pt a en A: a R a. * Irreflexiva: pt a en A: no(a R a). * Simétrica: pt a,b en A: a R b -> b R a. * Antisimétrica: pt a,b en A: a R b y b R a -> a=b. * Asimétrica: pt a,b en A: a R b -> no(b R a). * Transitiva: pt a,b,c en A: a R b y b R c -> a R c. Estas propiedades son independientes en muchos casos. No conviene intentar deducirlas simplemente por el significado cotidiano de sus nombres. ===== Relaciones de equivalencia ===== Una relación de equivalencia sobre A es una relación que satisface simultáneamente: * reflexividad; * simetría; * transitividad. La igualdad es el ejemplo más inmediato. Sin embargo, las relaciones de equivalencia permiten expresar formas más generales de considerar dos objetos como equivalentes respecto de alguna propiedad. Por ejemplo, sobre los números enteros podemos definir a R b cuando a y b dejan el mismo resto al dividirlos por 3. Así, 1 R 4 4 R 7 y 1 R 7. Los números relacionados de esta manera pueden agruparse en clases de equivalencia. Las relaciones de equivalencia y los conjuntos cociente se estudiarán con más detalle en [[conceptos:relaciones_de_equivalencia|Relaciones de equivalencia]]. ===== Relaciones de orden ===== Determinadas combinaciones de las propiedades anteriores permiten definir relaciones de orden. Una relación es un orden parcial cuando es: * reflexiva; * antisimétrica; * transitiva. Por ejemplo, consideremos la relación de divisibilidad sobre los números naturales positivos. En este ejemplo, a, b y c representarán siempre números naturales mayores que cero. Escribimos a divide b cuando existe un número natural positivo k tal que b=a*k. Veamos las propiedades de esta relación. Reflexividad: pt a en N: a divide a. Todo número natural se divide a si mismo. Por lo tanto la relación es reflexiva. Antisimetría: pt a,b en N: a divide b y b divide a -> a=b. Si a divide b, b=a*k_1 donde k_1 es natural. Si b divide a, a=b*k_2 donde k_2 es natural. Por tanto si a divide b y b divide a, a=b*k_2=(a*k_1)*k_2=a*(k_1*k_2) Si a*(k_1*k_2)=a, k_1*k_2=1, y para k_1 y k_2 naturales, k_1=k_2=1. Por tanto, a=1*b y b=1*a, así que a=b. En consecuencia, se cumple la antisimetría. Transitividad: pt a,b,c en N: a divide b y b divide c -> a divide c. Si a divide b podemos escribir b=a*k_1 donde k_1 es un número natural. Igualmente, si b divide a c, c=b*k_2 donde k_2 es natural. De lo que deducimos: c=b*k_2=(a*k_1)*k_2=a*(k_1*k_2) y ya que k_1 y k_2 son naturales, k_1*k_2 también lo es, y por tanto, a divide c. Por tnato, se verifica la transitividad. Sin embargo, esta relación no ordena todos los números naturales. Tomemos como ejemplo 2 y 3. 2 no divide a 3, ni 3 divide a 2. Los números 2 y 3 son, por tanto, incomparables respecto de esta relación. Otro ejemplo, sub es un orden parcial sobre P(A). Dados dos subconjuntos B y C de A, puede ocurrir que B sub C, que C sub B, o que ninguno sea subconjunto del otro. Por eso hablamos de un orden //parcial//. Un orden total añade la condición de que cualesquiera dos elementos puedan compararse. Para cualesquiera a y b, a R b o b R a. La relación <= sobre los números reales es un orden total. Las relaciones de orden merecen un tratamiento más detallado en [[conceptos:relaciones_de_orden|Relaciones de orden]]. ===== Una función como relación ===== Una relación R sub A x B puede relacionar un elemento de A con ninguno, uno o varios elementos de B. Para obtener una función necesitamos imponer dos condiciones adicionales. Para cada a en A debe existir algún b en B relacionado con a: pt a en A: exi b en B: a R b. Además, ese b debe ser único. Si a R b y a R c, entonces b=c. Una relación que satisface ambas condiciones puede representar una función f:A -> B. Por tanto, desde un enfoque conjuntista, una función es una relación que asigna a cada elemento de su dominio exactamente un elemento del codominio. Esta idea se desarrollará en [[conceptos:funciones|Funciones]]. ===== Demostrar propiedades de una relación ===== Para demostrar que una relación posee una propiedad debemos utilizar directamente su definición. Por ejemplo, supongamos que sobre los números enteros definimos a R b <-> a-b es par. Queremos demostrar que R es simétrica. Supongamos a R b. Por definición, a-b es par. Por tanto, existe un entero k tal que a-b = 2k. Multiplicando por -1, b-a = -2k = 2(-k). Como -k también es un entero, b-a es par. Por definición de R, b R a. Por tanto, R es simétrica. Este procedimiento es general: * Escribir la propiedad que queremos demostrar. * Sustituir a R b por la definición concreta de R. * Demostrar la condición resultante. * Volver a interpretar el resultado mediante la definición de R. ===== Refutar una propiedad de una relación ===== Para demostrar que una relación no satisface una propiedad universal basta encontrar un contraejemplo. Por ejemplo, para demostrar que a R b <-> %%|a-b| <= 1%% no es transitiva, basta encontrar a, b y c tales que a R b y b R c, pero no(a R c). Podemos escoger a=0, b=1, c=2. Entonces %%|0-1| = 1%% y %%|1-2| = 1%%, por lo que 0 R 1 y 1 R 2. Sin embargo, %%|0-2| = 2%%, por lo que no(0 R 2). Hemos encontrado un contraejemplo y, por tanto, la relación no es transitiva. ===== Ejercicios ===== ==== Ejercicio 1 ==== Sean A = {1,2,3} y B = {a,b}. Considera R = {(1,a),(2,a),(2,b)}. Determina: * dom(R). * im(R). * R^-1. ==== Ejercicio 2 ==== Sobre los números enteros definimos a R b <-> a-b es par. Determina si R es: * reflexiva; * simétrica; * antisimétrica; * transitiva. Justifica cada respuesta. ==== Ejercicio 3 ==== Sobre los números reales definimos a R b <-> a <= b. Determina cuáles de las propiedades estudiadas satisface R. ==== Ejercicio 4 ==== Sobre los números reales definimos a R b <-> %%|a-b| < 1%%. Demuestra que R es reflexiva y simétrica. Encuentra un contraejemplo que demuestre que no es transitiva. ==== Ejercicio 5 ==== Sea A un conjunto. Considera la relación sub sobre P(A). Demuestra que es reflexiva, antisimétrica y transitiva. ==== Ejercicio 6 ==== Sean R = {(1,a),(2,b),(3,a)} y S = {(a,x),(b,y)}. Calcula S comp R. ==== Ejercicio 7 ==== Explica por qué la relación R = {(1,a),(1,b),(2,a)} no puede representar una función de {1,2} en {a,b}. ==== Ejercicio 8 ==== Construye una relación sobre A = {1,2,3} que sea simétrica pero no reflexiva. Después construye otra que sea reflexiva pero no simétrica. ===== Soluciones ===== ==== Solución del ejercicio 1 ==== Los elementos de A que aparecen como primera componente de algún par de R son 1 y 2. Por tanto, dom(R) = {1,2}. Los elementos de B que aparecen como segunda componente son a y b. Por tanto, im(R) = {a,b}. Invirtiendo los pares, R^-1 = {(a,1),(a,2),(b,2)}. ==== Solución del ejercicio 2 ==== La relación es reflexiva. Para cualquier entero a, a-a=0, y 0 es par. Por tanto, a R a. Es simétrica. Si a R b, entonces a-b es par. El número b-a = -(a-b) también es par. Por tanto, b R a. No es antisimétrica. Por ejemplo, 1 R 3 y 3 R 1, pero 1 != 3. Es transitiva. Si a R b y b R c, entonces existen enteros k y m tales que a-b=2k y b-c=2m. Sumando, a-c = (a-b)+(b-c) = 2k+2m = 2(k+m). Como k+m es entero, a-c es par. Por tanto, a R c. Así, R es reflexiva, simétrica y transitiva: es una relación de equivalencia. ==== Solución del ejercicio 3 ==== La relación <= sobre los números reales es reflexiva porque a <= a. Es antisimétrica porque a <= b y b <= a implican a=b. Es transitiva porque a <= b y b <= c implican a <= c. No es simétrica: por ejemplo, 2 <= 3 pero no 3 <= 2. Tampoco es irreflexiva ni asimétrica, porque a <= a para todo a. Por tanto, <= es un orden parcial y, además, un orden total. ==== Solución del ejercicio 4 ==== Para cualquier número real a, %%|a-a| = |0| = 0 < 1%%. Por tanto, a R a, y R es reflexiva. Si a R b, entonces %%|a-b| < 1%%. Por la simetría de la distancia, %%|b-a| = |a-b| < 1%%. Por tanto, b R a, y R es simétrica. No es transitiva. Por ejemplo, tomemos a=0, b=3/4, c=3/2. Entonces %%|a-b| = 3/4 < 1%% y %%|b-c| = 3/4 < 1%%, pero %%|a-c| = 3/2 > 1%%. Por tanto, a R b y b R c, pero no(a R c). ==== Solución del ejercicio 5 ==== Para cualquier B en P(A), B sub B, por lo que sub es reflexiva. Si B sub C y C sub B, entonces B y C tienen exactamente los mismos elementos. Por la igualdad de conjuntos, B=C. Por tanto, sub es antisimétrica. Finalmente, supongamos B sub C y C sub D. Todo elemento de B pertenece a C, y todo elemento de C pertenece a D. Por tanto, todo elemento de B pertenece a D: B sub D. Así, sub es transitiva. Por consiguiente, sub es una relación reflexiva, antisimétrica y transitiva sobre P(A), y por tanto es un orden parcial. No es necesariamente un orden total. Por ejemplo, si A = {1,2}, los conjuntos {1} y {2} pertenecen a P(A), pero {1} no es subconjunto de {2} y {2} no es subconjunto de {1}. Por tanto, {1} y {2} son incomparables respecto de sub. ==== Solución del ejercicio 6 ==== Tenemos R = {(1,a),(2,b),(3,a)} y S = {(a,x),(b,y)}. Para obtener S comp R buscamos los elementos intermedios que relacionan cada elemento mediante R y después mediante S. Tenemos 1 R a y a S x, por lo que 1 (S comp R) x. También, 2 R b y b S y, por lo que 2 (S comp R) y. Finalmente, 3 R a y a S x, por lo que 3 (S comp R) x. Por tanto, S comp R = {(1,x),(2,y),(3,x)}. ==== Solución del ejercicio 7 ==== La relación es R = {(1,a),(1,b),(2,a)}. Para representar una función de {1,2} en {a,b}, cada elemento del dominio debe estar relacionado con exactamente un elemento del codominio. Sin embargo, 1 R a y 1 R b, con a != b. Por tanto, el elemento 1 está relacionado con dos valores distintos. La relación no satisface la condición de unicidad y no puede representar una función. ==== Solución del ejercicio 8 ==== Queremos primero una relación simétrica pero no reflexiva sobre A = {1,2,3}. Podemos tomar R = {(1,2),(2,1)}. Es simétrica porque cada vez que aparece un par (a,b), aparece también (b,a). No es reflexiva porque, por ejemplo, (1,1) noen R. Para obtener una relación reflexiva pero no simétrica podemos tomar S = {(1,1),(2,2),(3,3),(1,2)}. Es reflexiva porque contiene (1,1), (2,2) y (3,3). Sin embargo, (1,2) en S pero (2,1) noen S. Por tanto, S no es simétrica. ===== Véase también ===== * [[conceptos:conjuntos|Conjuntos]] * [[conceptos:relaciones_de_equivalencia|Relaciones de equivalencia]] * [[conceptos:relaciones_de_orden|Relaciones de orden]] * [[conceptos:funciones|Funciones]] ===== Notación ===== * R sub A x B: R es una relación de A en B. * a R b: a está relacionado con b mediante R; equivale a (a,b) en R. * dom(R): dominio de la relación R. * im(R): imagen de la relación R. * R^-1: relación inversa de R. * S comp R: composición de R seguida de S.