Relaciones

(Relación.) Sean A y B conjuntos. Un subconjunto R del producto cartesiano A × B se llama una relación de A en B. Es decir R es una relación de A en B si R ∈ P(A × B). Ejemplos: Sean A = {a, b, c}, B = {1, 2}. Entonces R1 = {(a, 1),(b, 1),(b, 2)}, R2 = {(a, 2),(b, 2),(c, 1),(c, 2)}, R3 = ∅ y R4 = A × B son ejemplos de relaciones de A en B, y R5 = {(1, c),(2, a)} es un ejemplo de relación de B en A (notar que importa el orden).

Sean A = B = R: R6 = {(x, y) ∈ R 2: x 2 = y 2} y R7 = {(x, y) ∈ R 2 : x = y 2} son relaciones de R en R, o, como veremos luego, relaciones en R

Dados a ∈ A, b ∈ B y una relación R de A en B, se dice que a esta relacionado con b (por la relación R) si (a, b) ∈ R. En ese caso se escribe a R b. Si a no está relacionado con b, es decir (a, b) ∈ R/, se escribe a ̸Rb. En los ejemplos arriba, se tiene b R1 1 pero a ̸R1 2, a R4 b, ∀ a ∈ A, b ∈ B, y @ a ∈ A, @ b ∈ B tal que a R3 b. También, −2 R6 2 y 4 R7 − 2. Posibles representaciones graficas de las relaciones: ¿Cuantas relaciones de A = {a, b, c} en B = {1, 2} hay?

Sabemos que hay una relación por cada subconjunto de A × B, o sea por cada elemento de P(A × B). Es decir, hay tantas relaciones como elementos en P(A × B). Luego la cantidad de relaciones es igual a #( P(A × B) ) .

Como, por la Proposición 1.1.11, el conjunto P (A×B) tiene en este caso 26 elementos, hay 26 relaciones de A en B. Este mismo razonamiento vale para conjuntos finitos cualesquiera: Proposición 1.2.2. (Combinatoria: Cantidad de relaciones.) Sean Am y Van conjuntos finitos, con m y n elementos respectivamente. Entonces la cantidad de relaciones que hay de Am en Van es igual a 2 m·n . 1.2.1. Relaciones en un conjunto. En esta sección consideramos relaciones de un conjunto en sí mismo.

 Definición. Sea A un conjunto. Se dice que R es una relación en A cuando R ⊆ A × A. Ejemplos: Las relaciones R6 y R7 arriba son relaciones en el conjunto R. La igualdad de elementos siempre es una relación en cualquier conjunto A: R = {(a, a), a ∈ A}, es decir ∀ a, b ∈ A : a R b ⇔ a = b. ≤ es una relación en R, y ⊆ es una relación en P(A), cualquiera sea el conjunto A.

Sea A = {a, b, c, d}, entonces R8 = {(a, a),(a, b),(a, d),(b, b),(c, c),(c, d),(d, a),(d, d)} es una relación en A, que según lo que vimos arriba se puede representar de las siguientes maneras: Sin embargo, cuando el conjunto A es finito (como en este caso), una relación R en A se puede representar también por medio de un grafo dirigido, o sea un conjunto de puntos (llamados vértices, que son los elementos del conjunto A) y un conjunto de flechas entre los vértices, que se corresponden con los elementos relacionados: se pone una flecha (que parte de a y llega a b) para cada elemento (a, b) ∈ R, es decir cada vez que a R b. Ejemplos: La teoría de grafos juega un rol esencial en varias ramas de la matemática y la computación. Las relaciones en un conjunto dado son particularmente importantes, y algunas de las propiedades que pueden cumplir merecen un nombre. Definición 1.2.4. (Relación reflexiva, simétrica (anti simétrica) y transitiva.) Sean A un conjunto y R una relación en A. Se dice que R es reflexiva si (a, a) ∈ R, ∀ a ∈ A (dicho de otra manera, a R a, ∀ a ∈ A). En términos del grafo de la relación, R es reflexiva si en cada vértice hay una flecha que es un “bucle”, es decir que parte de ´el y llega a ´el.

Se dice que R es simétrica si cada vez que un par (a, b) ∈ R, entonces el par (b, a) ∈ R también (dicho de otra manera, ∀ a, b ∈ A, a R b ⇒ b R a). En términos del grafo de la relación, R es simétrica si por cada flecha que une dos vértices en un sentido, hay una flecha (entre los mismos vértices) en el sentido opuesto. Se dice que R es anti simétrica si cada vez que un par (a, b) ∈ R con a ̸= b, entonces el par (b, a) ∈ R/ (dicho de otra manera, ∀ a, b ∈ A, a R b y b R a ⇒ a = b). En términos del grafo de la relación, R es anti simétrica si no hay ningún par de flechas en sentidos opuestos que unen dos vértices distintos. Se dice que R es transitiva si para toda terna de elementos a, b, c ∈ A tales que (a, b) ∈ R y (b, c) ∈ R, se tiene que (a, c) ∈ R también (dicho de otra manera, ∀ a, b, c ∈ A, a R b y b R c ⇒ a R c). En términos del grafo de la relación, R es transitiva si hay un “camino directo” por cada “camino con paradas”. Ejemplos: La relación R8 de arriba es reflexiva, pero no es simétrica ni anti simétrica, y tampoco transitiva como se ve en el grafo arriba: están todos los “bucles” (es reflexiva), esta por ejemplo la flecha a → b pero no la vuelta b → a (no es simétrica), están las flechas a → d y b → a (no es anti simétrica) y están las flechas c → d y d → a pero no el camino corto c → a (no es transitiva). R6 es reflexiva, pues ∀ x ∈ R, se tiene x R6 x pues x 2 = x 2 , es simétrica pues ∀ x, y ∈ R, se tiene que si x R6 y, es decir x 2 = y 2 , entonces y 2 = x 2 , es decir y R6 x, no es anti simétrica pues no es cierto que x R6 y e y R6 x implica x = y: por ejemplo para x = 1 e y = −1 se tiene x 2 = y 2 e y 2 = x 2 , y es transitiva pues ∀ x, y, z ∈ R, x 2 = y 2 e y 2 = z 2 implica x 2 = z 2 . ¿Cómo se ve que una relación es reflexiva en la representación grafica del producto cartesiano? ¿Y simétrica? ¿Puede ser una relación simétrica y anti simétrica a la vez? Si si, ¿en qué caso? = en A, con A un conjunto, es una relación reflexiva, simétrica y transitiva. ≤ en R es una relación reflexiva pues para todo x ∈ R, se tiene x ≤ x, no es simétrica pues en general x ≤ y no implica y ≤ x: por ejemplo para x = 1 e y = 2. Pero es antisim´etrica pues si x ≤ y e y ≤ x, entonces x = y. Y es transitiva pues x ≤ y e y ≤ z implica x ≤ z. Mostrar que ⊆ en P(A) es una relación reflexiva, antisim´etrica y transitiva. R7 no es reflexiva, pues ∃ x ∈ R tal que x ̸R7 x, es decir x ̸= x 2 (por ejemplo x = 2), tampoco es simétrica porque x = y 2 no implica en general y = x 2 (por ejemplo para x = 4, y = 2). ¿Es antisim´etrica? Supongamos x, y ∈ R tales que x = y 2 e y = x 2 , por lo tanto x = x 4 , lo que implica x(x 3 − 1) = 0, es decir x = 0 o x = 1 (por estar en R, ¡ojo!), y luego en el caso x = 0 se tiene y = x 2 = 02 = 0 = x, y en el caso x = 1 se tiene y = x 2 = 12 = 1 = x también, o sea es antisim´etrica nomás. Finalmente R7 no es transitiva pues x = y 2 e y = z 2 implica x = z 4 que no es igual a z 2 en general, por ejemplo tomando x = 16, y = 4, z = 2.