Estructuras Discretas

Relaciones

´ relacion ´ Definicion: ´ binaria de A en B es un Sean A y B dos conjuntos. Una relacion subconjunto de A × B.

Relaciones ´ n-aria R ⊆ A1 × A2 × · · · × An es una relacion Claudio Lobos, Jocelyn Simmonds

clobos,[email protected] ´ Universidad Tecnica Federico Santa Mar´ıa Estructuras Discretas – INF 152

´ Notacion:

aRb denota que (a, b) ∈ R a Rb denota que (a, b) 6∈ R Ejemplo: Si A = {0, 1, 2} y B = {a, b}, entonces un ejemplo de una ´ de A en B es el conjunto {(0, a), (0, b), (1, a), (2, b)}. En este relacion caso, 0Ra, pero 1 Rb. ´ es una relacion, ´ pero no toda relacion ´ es funcion. ´ Ojo: Toda funcion

Relaciones en un Conjunto

Propiedades de Relaciones en A Reflexividad

´ en un conjunto A es una relacion ´ de A en A, o sea, un Una relacion subconjunto de A × A Ejemplo: si A = {1, 2, 3, 4}, donde

R ⊆ A × A, R = {(a, b) | a divide b} entonces,

En algunas relaciones, un elemento siempre esta´ relacionado consigo mismo. Se dice que estas relaciones son reflexivas: ´ reflexividad Definicion: ´ R ⊆ A × A es reflexiva si ∀a ∈ A, (a, a) ∈ R Una relacion

R ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} A puede ser infinito. Ejemplo: S ⊆ Z+ × Z+ , donde S = {(a, b) | a = b} En este caso, no podemos enumerar los pares ordenados que pertenecen a S, solo podemos indicar si un par ordenado ´ pertenece o no a la relacion. Por ejemplo, (10, 10) ∈ S, mientras que (2, 6) 6∈ S

´ Ejemplos: sea A = {1, 2, 3, 4}. ¿Cuales de las siguientes relaciones son reflexivas?

R1 = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 1), (4, 4)} . . . no es reflexiva, porque (2, 2) 6∈ R1 R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} . . . si es reflexiva

Reflexividad

Propiedades de Relaciones en A

Ejemplos

Simetr´ıa y antisimetr´ıa

´ Sean R1 , R2 , R3 ⊆ Z+ × Z+ . ¿Cuales de las siguientes relaciones son reflexivas? 1

2

R1 = {(a, b) | a ≤ b} ´ Sea x ∈ Z+ . Como x ≤ x (prop. basica de los numeros), tenemos ´ que (x, x) ∈ R1 . Generalizando, tenemos que ∀a ∈ Z+ , (a, a) ∈ R, as´ı que R1 es reflexiva. R2 = {(a, b) | a divide b} ´ anterior, porque sabemos que Muy similar a la demostracion dado un x cualquiera ∈ Z+ , x divide a si mismo . . . as´ı que R2 es reflexiva.

3

R3 = {(a, b) | a + b ≤ 3} ´ ver que (2, 2) 6∈ R3 , porque ¿(1, 1) ∈ R3 ? Si. ¿y (2, 2)? Es facil 2 + 2 = 4, as´ı que (2, 2) 6∈ R3 , por lo que R3 no es reflexiva.

En algunas relaciones, un elemento esta relacionado con un segundo elemento si, y solo si, el segundo elemento esta relacionado con el ´ primero. Se dice que estas relaciones son simetricas: ´ simetr´ıa Definicion: ´ R ⊆ A × A es simetrica ´ Una relacion si

∀a, b ∈ A, [(a, b) ∈ R ⇒ (b, a) ∈ R] Un concepto relacionado (¡pero no opuesto!): ´ antisimetr´ıa Definicion: ´ R ⊆ A × A es antisimetrica ´ Una relacion si

∀a, b ∈ A, [(a, b) ∈ R ∧ (b, a) ∈ R ⇒ a = b]. O de forma equivalente, ∀a, b ∈ A, [(a, b) ∈ R ∧ a 6= b ⇒ (b, a) 6∈ R]

Simetr´ıa

antisimetr´ıa

∀a, b ∈ A, [(a, b) ∈ R ⇒ (b, a) ∈ R]

∀a, b ∈ A, [(a, b) ∈ R ∧ (b, a) ∈ R ⇒ a = b]

´ Sean R1 , R2 , R3 ⊆ Z+ × Z+ . ¿Cuales de las siguientes relaciones son ´ simetricas?

R1 = {(a, b) | a ≤ b} ´ ver que (1, 2) ∈ R1 , pero que (2, 1) 6∈ R1 , as´ı que Es facil ´ no es simetrica. ´ claramente esta relacion

R2 = {(a, b) | a = b} Sean x, y ∈ Z+ . Si (x, y) ∈ R2 , tenemos que x = y, pero esto es lo mismo que decir y = x (conmut. de =), as´ı que (y, x) ∈ R2 . Generalizando, tenemos que

∀a, b ∈ Z+ , [(a, b) ∈ R2 ⇒ (b, a) ∈ R2 ], as´ı que R2 es ´ simetrica.

R3 = {(a, b) | a + b ≤ 3} Similar a la demo. anterior. Sabemos que x + y = y + x, as´ı que si ´ es verdad que y + x ≤ 3, o (x, y) ∈ R3 , o sea, x + y ≤ 3, tambien ´ sea, (y, x) ∈ R3 . Por lo tanto, R3 es simetrica.

´ Sean R1 , R2 , R3 ⊆ Z+ × Z+ . ¿Cuales de las siguientes relaciones son ´ antisimetricas?

R1 = {(a, b) | a ≤ b} Sean x, y ∈ Z+ . Si (x, y) ∈ R1 ∧ (y, x) ∈ R1 , tenemos que x ≤ y ∧ y ≤ x. Esto solo es verdadero si x = y. Generalizando, tenemos que ∀a, b ∈ Z+ , [(a, b) ∈ R1 ∧ (b, a) ∈ R1 ⇒ a = b], o ´ sea, R1 es antisimetrica. R2 = {(a, b) | a = b} ´ demostrar que R2 es antisimetrica. ´ De forma similar, es facil

R3 = {(a, b) | a + b ≤ 3} ´ no es antisimetrica ´ Una relacion si ´ del ∀∀). Es ∃a, b ∈ A, [(a, b) ∈ R ∧ (b, a) ∈ R ∧ (a 6= b)] (negacion ´ facil ver que (2, 1) ∈ R3 ∧ (1, 2) ∈ R3 ∧ 1 6= 2, as´ı que esta ´ no es antisimetrica. ´ relacion

Propiedades de Relaciones en A

Transitividad

Transitividad

∀a, b, c ∈ A, ([(a, b) ∈ R ∧ (b, c) ∈ R] ⇒ (a, c) ∈ R)

´ Sean R1 , R2 , R3 ⊆ Z+ × Z+ . ¿Cuales de las siguientes relaciones son transitivas? En algunas relaciones, sabemos como se relacionan dos elementos a ´ de un tercer elemento. Se dice que estas relaciones son traves transitivas:

R1 = {(a, b) | a ≤ b} Sean x, y, z ∈ Z+ . Si (x, y) ∈ R1 ∧ (y, z) ∈ R1 , tenemos que x ≤ y ∧ y ≤ z. Dado que ≤ es transitivo, esto significa que x ≤ z, o sea, (x, z) ∈ R1 . Generalizando, tenemos entonces que R1 es

´ simetr´ıa Definicion:

transitiva.

´ R ⊆ A × A es transitiva si Una relacion

R2 = {(a, b) | a = b}

∀a, b, c ∈ A, ([(a, b) ∈ R ∧ (b, c) ∈ R] ⇒ (a, c) ∈ R)

´ demostrar que R2 De forma similar (transitividad de =), es facil es transitiva.

R3 = {(a, b) | a + b ≤ 3} Sabemos que (1, 2) ∈ R3 y que (2, 1) ∈ R3 . ¿Se cumple que (1, 1) ∈ R3 ? Si. Ahora, dado que (2, 1) ∈ R3 y (1, 2) ∈ R3 . . . ¿se cumple que (2, 2) ∈ R3 ? No. As´ı que R3 no es transitiva.

´ de Relaciones Combinacion

´ de Relaciones Combinacion Ejemplos

Como las relaciones de A en B son subconjuntos de A × B, dos relaciones se pueden combinar de cualquier forma en que se combinan dos conjuntos: Sean A = {1, 2, 3} y B = {a, b, c, d}, donde R1 = {(1, a), (2, b), (3, c)} y R2 = {(1, a), (1, b), (1, c), (1, d)}:

R1 ∪ R2 = ? {(1, a), (1, b), (1, c), (1, d), (2, b), (3, c)} R1 ∩ R2 = ? {(1, a)}

Sean R1 , R2 ⊆ Z+ × Z+ , donde R1 = {(x, y) | x < y} y R2 = {(x, y) | x > y}:

R1 ∪ R2 = ? {(x, y) | x < y ∨ y < x} = {(x, y) | x 6= y} R1 ∩ R2 = ? {(x, y) | x < y ∧ y < x} = {(x, y) | F} = ∅ Algunas definiciones adicionales ´ relacion ´ inversa Definicion: ´ inversa Sea R ⊆ A × B, podemos definir la relacion

R−1 = {(b, a) | (a, b) ∈ R}

R1 − R2 = ? {(2, b), (3, c)} R2 − R1 = ? {(1, b), (1, c), (1, d)}

´ relacion ´ complementaria Definicion: ´ complemento Sea R ⊆ A × B, podemos definir la relacion

R = {(a, b) | (a, b) 6∈ R}

´ de Relaciones Composicion

Ejemplo

´ composicion ´ Definicion: ´ de A en B y S una relacion ´ de B en C. La Sean R una relacion ´ de R y S, denotada S ◦ R, es la relacion ´ que consiste en composicion los pares ordenados (a, c) (con a ∈ A y c ∈ C) para los que existe un elemento b ∈ B tal que (a, b) ∈ R y (b, c) ∈ S.

´ en el conjunto de las personas, tal que (x, y) ∈ R si Sea R una relacion ´ representa R ◦ R? x es padre o madre de y. Entonces, ¿que´ relacion

Ejemplo: sean R ⊆ {1, 2, 3} × {1, 2, 3, 4} y S ⊆ {1, 2, 3, 4} × {0, 1, 2}

(a, c) ∈ R ◦ R si, y solo si existe una persona b tal que (a, b) ∈ R y (b, c) ∈ R

R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} y

O sea, a es padre/madre de b, y b es padre/madre de c

S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} S◦R = ?

Entonces, si (a, c) ∈ R ◦ R, significa que a es abuelo/abuela de c

(1, 1) ∈ R y (1, 0) ∈ S, as´ı que (1, 0) ∈ S ◦ R (3, 1) ∈ R y (1, 0) ∈ S, as´ı que (3, 0) ∈ S ◦ R (2, 3) ∈ R y (3, 1) ∈ S, as´ı que (2, 1) ∈ S ◦ R (2, 3) ∈ R y (3, 2) ∈ S, as´ı que (2, 2) ∈ S ◦ R . . . S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}

Potencias de R

´ de Relaciones Representacion

´ potencias de R Definicion:

´ ´ en el plano cartesiano, Podemos dibujar el grafico de una funcion porque para cada a, existe un unico valor f (a) = b ´

´ en un conjunto A. Las potencias Rn (n = 1, 2, 3 . . . ) Sea R una relacion se definen recursivamente como R1 = R y Rn+1 = Rn ◦ R

´ puede haber uno o mas ´ valores En cambio, en una relacion, ´ asignados a a, as´ı que no podemos graficar una relacion

Ejemplo: R2 = R ◦ R, R3 = (R ◦ R) ◦ R, etc. Teorema 1

´ Existen dos metodos para representar relaciones:

´ R en un conjunto A es transitiva si, y solo si, R ⊆ Rn , para La relacion

1

Grafos dirigidos

n = 1, 2, 3 . . .

2

Matrices booleanas

Grafos Dirigidos

Grafos Dirigidos Ejemplo

Sea A = {1, 2, 3, 4}, R ⊆ A × A, donde

R = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)} ´ grafo dirigido Definicion: ´ Un grafo dirigido consiste de un conjunto V de vertices (o nodos) y un conjunto E de pares ordenados de elementos de V , llamados arcos (o aristas). ´ Si (a, b) ∈ E, entonces a es el vertice inicial de la arista (a, b), y b es ´ el vertice final de la arista.

´ R: Podemos dibujar el grafo correspondiente a la relacion

2 1

Una arista de la forma (a, a) se representa usando una arista que conecta al elemento a consigo mismo (se llama un bucle).

3

4

Propiedades de Relaciones

Propiedades de Relaciones

´ Reflexividad: cada vertice debe tener un bucle

´ Reflexividad: cada vertice debe tener un bucle

1

2

1

2

3

4

3

4

Simetr´ıa: si hay un arco entre ´ vertices a y b, debe haber un arco ´ entre vertices bya

Propiedades de Relaciones

Propiedades de Relaciones

´ Reflexividad: cada vertice debe tener un bucle

1

% 3

%

´ Reflexividad: cada vertice debe tener un bucle

2

Simetr´ıa: si hay un arco entre ´ vertices a y b, debe haber un arco ´ entre vertices bya

1

2

Simetr´ıa: si hay un arco entre ´ vertices a y b, debe haber un arco ´ entre vertices bya

4

antisimetr´ıa: si hay un arco entre ´ vertices a y b, donde a 6= b, no puede haber un arco entre b y a

3

4

antisimetr´ıa: si hay un arco entre ´ vertices a y b, donde a 6= b, no puede haber un arco entre b y a

Conclusion: esta relacion ´ no es reflexiva, simetrica, ´ antisimetrica ni transitiva

Matrices Booleanas

Transitividad: si hay un arco entre ´ ´ vertices a y b, y vertices b y c, entonces debe haber un arco entre ayc

Matrices Booleanas Ejemplos

1

´ R ⊆ A × B, donde A = {a1 , a2 , . . . , am } y Suponiendo una relacion ´ se puede representar por medio de B = {b1 , b2 , . . . , bn }, la relacion una matriz MR = [mij ], donde

Sean A = {1, 2, 3} y B = {1, 2}, donde R ⊆ A × B, R = {(a, b) | a > b}. MR =?

1 1 0 MR = 2  1 3 1  1 Si MR = 0 1 

( 1 si (ai , bj ) ∈ R mij = 0 si (ai , bj ) 6∈ R MR tiene m filas y n columnas 2

Nota: para hacer esto, uno debe escoger un orden para A, B. Si A = B, lo usual es usar el mismo orden para las filas y las columnas.

2  0 0 1

 0 1 0 1 0 1, donde A = {1, 2, 3} y B = {a, b, c, d} 0 1 0 (con orden obvio), entonces R =? R = {(1, a), (1, c), (2, b), (2, d), (3, a), (3, c)}

Propiedades de Relaciones

Propiedades de Relaciones

Reflexividad

Simetr´ıa

R ⊆ A × A es reflexiva sii ∀a ∈ A, (a, a) ∈ R

´ R ⊆ A × A es simetrica sii ∀a, b ∈ A, (a, b) ∈ R ⇒ (b, a) ∈ R

Entonces, si A = {a1 , a2 , . . . an }, R es reflexiva sii (ai , ai ) ∈ R, para i = 1, 2, . . . n

´ Entonces, si A = {a1 , a2 , . . . an }, R es simetrica sii (aj , ai ) ∈ R siempre que (ai , aj ) ∈ R

En consecuencia, R es reflexiva sii mii = 1, para i = 1, 2, . . . n

´ En consecuencia, R es simetrica sii

En otras palabras, R es reflexiva si todos los elementos de la diagonal principal son iguales a 1

´ Entonces, R es simetrica sii mij = mji , i 6= j, para i, j = 1, 2, . . . n

(mij = 1 ⇒ mji = 1) ∧ (mij = 0 ⇒ mji = 0) ´ O sea, R es simetrica sii MR = (MR )t (traspuesta)

  1 ?  1    MR =   ..   . ? 1



? 0 MR =  1 0

0 ? 1 1

1 1 ? 0

Propiedades de Relaciones

Propiedades de Relaciones

antisimetr´ıa

Transitividad

 0 1  0 ?

´ R ⊆ A × A es antisimetrica sii ∀a, b ∈ A, [(a, b) ∈ R ∧ a 6= b] ⇒ (b, a) 6∈ R ´ Entonces, si A = {a1 , a2 , . . . an }, R es antisimetrica sii (ai , aj ) ∈ R ∧ i 6= j implica que (aj , ai ) 6∈ R ´ En consecuencia, R es antisimetrica sii mij = 1 ∧ i 6= j implica que mji = 0 ´ Entonces, R es antisimetrica sii mij = 0 ⊕ mji = 0 siempre que

i 6= j 

? 1 MR =  0 1

0 ? 0 0

1 1 ? 1

 0 1  0 ?

´ No se puede hacer un analisis visual simple de una matriz ´ es transitiva booleana para determinar si una relacion

´ de Relaciones Combinacion

´ de Relaciones Composicion

Sean R1 , R2 ⊆ A, representadas por matrices MR1 y MR2 Sean R ⊆ A × B y S ⊆ B × C:

´ ¿Como calculamos MR1 ∪R2 y MR1 ∩R2 ?

El par (ai , cj ) ∈ S ◦ R sii ∃bk tal que (ai , bk ) ∈ R y (bk , cj ) ∈ S

Sabemos que (a, b) ∈ R1 ∪ R2 si (a, b) ∈ R1 ∨ (a, b) ∈ R2 R

Si MS◦R = [tij ], MR = [rij ] y MS = [sij ], entonces tij = 1 si, y solo si, rik = skj = 1, para algun ´ k

R

O sea, mij 1 = 1 ∨ mij 2 = 1 R

R

Entonces, MR1 ∪R2 = [mij ], donde mij = mij 1 ∨ mij 2 R

R

De la misma forma, MR1 ∩R2 = [mij ], donde mij = mij 1 ∧ mij 2

    1 0 1 1 1 1 Ejemplo: si MR1 = 0 1 0 y MR2 = 0 1 0, entonces 1 1 1 0 0 0     1 1 1 1 0 1 MR1 ∪R2 = 0 1 0 y MR1 ∩R2 = 0 1 0 1 1 1 0 0 0

Relaciones de Equivalencia

´ relacion ´ de equivalencia Definicion: ´ R en un conjunto A es una relacion ´ de equivalencia si es Una relacion ´ reflexiva, simetrica y transitiva ´ de Se dice que dos elementos relacionados por una relacion ´ ´ equivalencia son equivalentes (con respecto a la relacion). ¿Por que? Reflexividad: cualquier elemento es equivalente a si mismo ´ relacionados dos Simetr´ıa: no importa en que orden esten ´ relacionados, son equivalentes para la elementos . . . si estan ´ relacion ´ by Transitividad: si elementos a y b son equivalentes, y ademas c son equivalentes, entonces a y c son equivalentes para la ´ relacion

O sea, MS◦R = MR MS , donde es el producto booleano ´ producto booleano Definicion: ˜ m×k y Sean A = [aij ] y B = [bij ] matrices booleanas de tamanos k × n, respectivamente. El producto booleano de A y B, denotado ˜ m × n cuyo elemento (i, j) es cij , donde A B, es la matriz de tamano

cij = (ai1 ∧ b1j ) ∨ (ai2 ∧ b2j ) ∨ · · · ∨ (aik ∧ bkj )

Ejemplo

Sea R ⊆ Z × Z, donde R = {(a, b) | a y b tienen la misma paridad} (o ´ de sea, ambos numeros son pares, o ambos son impares). La relacion ´ ´ de equivalencia: paridad es una relacion Reflexividad: como a tiene la misma paridad que si mismo, para cualquier a en Z, se sigue que R es reflexiva Simetr´ıa: si (a, b) ∈ R, significa que a y b tienen la misma paridad ´ (ambos pares, o ambos impares). Por lo tanto, (b, a) tambien ´ pertenece a R, lo que significa que R es simetrica Transitividad: supongamos que (a, b) ∈ R y (b, c) ∈ R. Como a y c tienen la misma paridad que b, significa que a y c tienen la misma paridad. Por lo tanto, (a, c) ∈ R, as´ı que R es transitiva ´ los numeros Para esta relacion, pares son “equivalentes” entre si, y ´ ´ estos dos los numeros impares son “equivalentes” entre si. Ademas, ´ ´ nos da el conjunto inicial. subconjuntos son disjuntos, y su union

Clases de Equivalencia

Algunas Definiciones

´ clase de equivalencia Definicion:

Antes de seguir con otro ejemplo, necesitamos algunas definiciones:

´ de equivalencia en A. El conjunto de todos los Sea R una relacion ´ relacionados con un elemento a ∈ A se llama la elementos que estan clase de equivalencia de a, y se denota [a]R , donde

´ Teorema de la division

[a]R = {b ∈ A | (a, b) ∈ R} Si b ∈ [a]R , de dice que b es un representante de la clase de ´ de paridad, tenemos las equivalencia [a]R . Ejemplo: para la relacion siguientes clases de equivalencia:

[0]R = {. . . , −4, −2, 0, 2, 4, . . . } = [2]R = [16]R = . . . [1]R = {. . . , −3, −1, 1, 3, . . . } = [−3]R = [9]R = . . . Lema 1 Las clases de equivalencia son siempre no vac´ıas (dado que las relaciones de equivalencia son reflexivas)

Algunas Definiciones

Teorema

Sean a ∈ Z y d ∈ Z+ . Existen dos unicos enteros q y r (cociente y ´ resto, respectivamente) tales que a = dq + r, donde 0 ≤ r < d ´ q = a div d (parte entera de la division) ´ r = a mod d (resto de la division) ´ congruencia modulo ´ Definicion: m ´ Si a, b ∈ Z y m ∈ Z+ , entonces a es congruente con b modulo m si m ´ a ≡m b) divide a − b, y se denota a ≡ b (mod m) (o tambien ´ En otras palabras, dos numeros son congruentes modulo m si tienen ´ ´ el mismo resto con respecto a m. Si a y b no son congruentes modulo m, escribimos a 6≡ b (mod m)

Ejemplo

Sea R ⊆ Z × Z, donde R = {(a, b) | a ≡ b (mod m)}. ¿Es R una ´ de equivalencia? relacion

Sean a, b ∈ Z y m ∈ Z+ . Entonces a ≡ b (mod m) si, y solo si, a mod m = b mod m

Reflexividad: sea x ∈ Z. Como x − x = 0, y 0 es divisible por m, se cumple que x ≡ x (mod m). Generalizando, tenemos que ∀a ∈ Z, a ≡ a (mod m), o sea R es reflexiva

Ejemplos:

Simetr´ıa: sean x, y ∈ Z Si (x, y) ∈ R, entonces x ≡ y (mod m)

10 ≡ 25 (mod 3), dado que 10 mod 3 = 25 mod 3 = 1 7 6≡ 10 (mod 4), dado que 7 mod 4 = 3 y 10 mod 4 = 2 Pregunta: sea R ⊆ Z × Z, donde R = {(a, b) | a ≡ b (mod m)}. ¿Es R ´ de equivalencia? una relacion

Por la def. de congruencia, tenemos que m divide x − y, o sea, ∃k ∈ Z tal que x − y = km Multiplicando ambos lados por -1, obtenemos que y − x = (−k)m ´ es entero, significa que m tambien ´ divide y − x, Como −k tambien as´ı que se cumple que y ≡ x (mod m), o sea, (y, x) ∈ R ´ Generalizando, podemos concluir que R es simetrica

Ejemplo

Ejemplo

Sea R ⊆ Z × Z, donde R = {(a, b) | a ≡ b (mod m)}. ¿Es R una ´ de equivalencia? relacion Transitividad: sean x, y, z ∈ Z Si (x, y) ∈ R y (y, z) ∈ R, tenemos que x ≡ y (mod m) y y ≡ z (mod m) O sea, x − y y y − z son divisibles por m:

´ ´ ¿Cuales son las clases de equivalencia de congruencia modulo 4? ´ por 4 es 0} [0]≡4 = {x ∈ Z tales que el resto de la division = {· · · − 8, −4, 0, 4, 8, . . . } ´ por 4 es 1} [1]≡4 = {x ∈ Z tales que el resto de la division = {· · · − 7, −3, 1, 5, 9, . . . } Como quedan elementos de Z sin clase de equivalencia, nos quedan algunas clases de equivalencia por descubrir

∃k ∈ Z tal que x − y = km ∃` ∈ Z tal que y − z = `m Sumando estas dos ecuaciones, obtenemos que x − z = (k + `)m, donde (k + `) es claramente un entero, por lo que x − z es divisible por m Entonces, x ≡ z (mod m), por lo que (x, z) ∈ R Generalizando, podemos concluir que R es transitiva

´ ´ de ∴ Como R es reflexiva, simetrica y transitiva, es relacion equivalencia

Particiones

´ por 4 es 2} [2]≡4 = {x ∈ Z tales que el resto de la division = {· · · − 6, −2, 2, 6, 10, . . . } . . . y por ultimo . . . ´ por 4 es 3} [3]≡4 = {x ∈ Z tales que el resto de la division = {· · · − 5, −1, 3, 7, 11, . . . } ´ ver que Z = [0]≡4 ∪ [1]≡4 ∪ [2]≡4 ∪ [3]≡4 , y que Es facil [0]≡4 ∩ [1]≡4 = ∅, [0]≡4 ∩ [2]≡4 = ∅ . . .

Particiones

Teorema

´ particion ´ Definicion:

´ de equivalencia en A. Entonces, para cualquier Sea R unas relacion dos clases de equivalencia [a]R y [b]R se cumple que:

´ se subconjuntos {Ai }, donde i ∈ I (un conjunto de La coleccion ´ de A sii ´ındices) forma una particion T 1) Ai 6= ∅ para todo i ∈ I 3) Ai = A i∈I 2) Ai ∩ Aj = ∅ si i 6= j

1

[a]R = [b]R si (a, b) ∈ R

2

[a]R ∩ [b]R = ∅ si (a, b) 6∈ R

Teorema Demo. (propuesto): 1

[a]R = [b]R si (a, b) ∈ R: deben demostrar que [a]R ⊆ [b]R y que [b]R ⊆ [a]R . Recordar que A ⊆ B si x ∈ A ⇒ x ∈ B

2

´ al absurdo, [a]R ∩ [b]R = ∅ si (a, b) 6∈ R: demostrar por reduccion asumir que (a, b) 6∈ R y [a]R ∩ [b]R 6= ∅ y derivar una ´ contradiccion

´ de equivalencia en A. Entonces, las clases de Sea R una relacion ´ de A. Rec´ıprocamente, dada equivalencia de R forman una particion ´ ´ de una particion {Ai | i ∈ I} del conjunto A, hay una relacion equivalencia cuyas clases de equivalencia son los conjuntos Ai , i ∈ I Demo. (propuesto): se puede demostrar en forma directa usando las propiedades de clases de equivalencia

Ejercicios Propuestos

Cierre de Relaciones

´ en A: Sea R una relacion 1

Demostrar que si R, S son relaciones transitivas en A, entonces ´ transitiva R ∩ S es relacion

2

Demostrar que las siguientes relaciones son relaciones de equivalencia: 1 R en Z, donde R = {(a, b) | a + 2b es divisible por 3} a c 2 R en Q, donde R = {(p, q) | p = b , q = d , (p, q) ∈ R sii ad = bc} 3 R en R, donde R = {(x, y) | |x| + |y| = |x + y|}

3

´ y R = {(a, b) | f (a) = f (b)}. ¿Es R Sea f : A → A una funcion, ´ de equivalencia? Si lo es, ¿como ´ una relacion particiona el conjunto A?

Cierre de Relaciones

R puede o no cumplir una cierta propiedad, como por ejemplo, reflexividad Si R no cumple una propiedad, entonces la pregunta es: ¿que´ elementos de A × A hay que agregar a R para que R cumpla la propiedad? Obviamente queremos agregar lo justo y necesario para que la ´ m´ınima de la propiedad se cumpla – queremos la extension ´ R relacion ´ es el cierre de R con respecto a la propiedad Esta nueva relacion dada

Reflexividad Ejemplo: sea A = {1, 2, 3} y R = {(1, 1), (1, 2), (2, 1), (3, 2)}

Formalmente:

´ no es reflexiva Claramente, esta relacion

´ cierre de R con respecto a P Definicion:

Para cerrarla con respecto a reflexividad, debemos agregar al menos dos pares ordenados: (2, 2) y (3, 3)

´ en A que no cumple una propiedad P. Sea S una Sea R una relacion ´ tal que: relacion 1

R ⊆ S,

Podemos agregar mas pares ordenados a R, pero basta con ´ sea reflexiva estos dos para que la relacion

2

S cumple la propiedad P, y

Entonces, si S es el cierre reflexivo de R,

3

´ que cumple la propiedad P y R ⊆ T , si T es otra relacion entonces S ⊆ T S es el cierre de R con respecto a P

A nosotros nos interesa el cierre con respecto a la reflexividad, simetr´ıa y transitividad

S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 2), (3, 3)} ˜ Entonces, dada R en A, el cierre reflexivo de R se forma anadiendo todos los pares de la forma (a, a), con a ∈ A, que no pertenezcan a R ´ cierre reflexivo Definicion: ´ en A, y S su cierre reflexivo. Entonces, S = R ∪ ∆, Sea R una relacion donde ∆ = {(a, a) | a ∈ A}

Reflexividad

Simetr´ıa

Ejemplo

Ejemplo: sea A = {1, 2, 3} y R = {(1, 2), (1, 3), (2, 3), (3, 2)} ´ es el cierre reflexivo de las siguientes relaciones? ¿Cual 1

2

Sea R en Z, donde R = {(a, b) | a > b} ∆ = {(a, a) | a ∈ Z} = {(a, b) | a = b} Entonces, S = R ∪ ∆ = {(a, b) | a > b} ∪ {(a, b) | a = b} ´ S = {(a, b) | a > b ∨ a = b} = {(a, b) | a ≥ b} Por def. de union, Sea R en Z, donde R = {(a, b) | a = b ∨ a = −b} ´ ya es Como a = a ∨ a = −a es siempre verdadero, esta relacion reflexiva As´ı que el cierre reflexivo de R es R

´ no es simetrica ´ Claramente, esta relacion Para cerrarla con respecto a simetr´ıa, debemos agregar al menos dos pares ordenados: (2, 1) y (3, 1) Ambos pares ordenados pertenecen a R−1 , donde R−1 es la ´ inversa de R (R−1 = {(b, a) | (a, b) ∈ R}) relacion ´ Entonces, si S es el cierre simetrico de R,

S = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)}

Lema

´ cierre simetrico ´ Definicion:

´ reflexiva, entonces el cierre reflexivo de R es R Si R es una relacion

´ en A, y S su cierre simetrico. ´ Sea R una relacion Entonces, −1 −1 ´ inversa de R S = R ∪ R , donde R es la relacion

Simetr´ıa

Transitividad

Ejemplo

´ es el cierre simetrico ´ ¿Cual de las siguientes relaciones? 1

Sea R en Z, donde R = {(a, b) | a > b} R−1 = {(b, a) | (a, b) ∈ R} = {(b, a) | a > b} Haciendo un cambio de variables, tenemos que

R−1 = {(b, a) | a > b} = {(c, a) | a > c} = {(c, b) | b > c} = {(a, b) | b > a} As´ı que S = R ∪ R−1 = {(a, b) | a > b} ∪ {(a, b) | b > a} = {(a, b) | a > b ∨ b > a} = {(a, b) | a 6= b} 2

Sea R en Z, donde R = {(a, b) | a + b ≤ 3} Como a + b = b + a, tenemos entonces que si a + b ≤ 3 es V, ´ lo es, por lo que esta relacion ´ es entonces b + a ≤ 3 tambien ´ simetrica As´ı que el cierre simetrico de R es R

Lema ´ simetrica, ´ ´ Si R es una relacion entonces el cierre simetrico de R es R

1

2

4

3

Ejemplo: sea A = {1, 2, 3, 4} y

R = {(1, 3), (1, 4), (2, 1), (3, 2)}

´ no es transitiva: (1, 3), (3, 2) ∈ R, pero (1, 2) 6∈ R Esta relacion ´ de transitividad, habr´ıa que agregar al menos los Por la definicion siguientes pares a R: T = {(1, 2), (2, 3), (2, 4), (3, 1)} Definamos R0 = R ∪ T . . . ¿es R0 transitiva? No, porque (1, 2), (2, 1) ∈ R0 , pero (1, 1) 6∈ R0 ´ como construir el Construir el cierre transitivo de R no es tan facil ´ cierre reflexivo o simetrico Analicemos un ejemplo mas simple

Transitividad

Transitividad

Sea A = {1, 2, 3, 4} y R = {(1, 2), (2, 3), (3, 4)}. R no es transitiva. En este ejemplo, el “camino” mas largo sin ciclos entre nodos es de largo 3, dado que |A| = 4. Entonces, no hace falta considerar R4 , R5 . . . para construir el cierre transitivo de R.

1

2

3

4

Faltan los arcos (1, 3) y (2, 4) (def. de transitividad)

1

2

3

4

Estos son los arcos entre los nodos alcanzables en dos pasos, o sea, son elementos de R2 . ¿Faltan mas arcos? Si: como ahora (1, 2), (2, 4) ∈ R, falta agregar (1, 4)

(1, 4) ∈

R3 ,

o sea, agregamos arcos entre los nodos alcanzables en tres pasos

´ Regla para generar el cierre transitivo de una relacion: Si existe algun ´ camino entre nodos a y b en R, entonces debemos agregar el arco (a, b) al cierre transitivo de R

Ahora R es transitiva

Caminos

´ camino Definicion: ´ de Un camino de nodo a a b en un grafo dirigido G es una sucesion aristas (x0 , x1 ), (x1 , x2 ), . . . (xn−1 , xn ) donde n ≥ 1, x0 = a y xn = b. Este camino se denota como x0 , x1 , . . . xn−1 , xn , y es de largo n (numero de arcos incluidos en el camino) ´ entre la existencia de un camino y la Hay una clara relacion ´ composicion de relaciones:

Cierre Transitivo ´ relacion ´ de conexion ´ Definicion: ´ en un conjunto A. La relacion ´ de conexion ´ R∗ Sea R una relacion consta de los pares (a, b) tales que hay un camino en R de largo al menos 1 de a a b. Como Rn esta formado por los pares (a, b) tales que hay un camino de largo n de a a b . . . ∞ S . . . se sigue que R∗ = Rn n=1

Teorema ´ en un conjunto A. Hay un camino de largo n, Sea R una relacion donde n ≥ 1 de a a b si, y solo si (a, b) ∈ Rn .

Teorema

´ Ahora podemos definir el cierre transitivo de una relacion: necesitamos agregar un arco entre cada par de nodos conectados por algun ´ camino.

Lema

´ R es la relacion ´ de conexion ´ R∗ El cierre transitivo de una relacion

´ en A, entonces el cierre transitivo de R Si |A| = n y R es una relacion ∗ 2 en A es R = R ∪ R ∪ · · · ∪ Rn

Cierre Transitivo Ejemplo

Sea R en el conjunto de personas tal que R = {(a, b) | a conoce a b} ´ es la relacion ´ Rn , para n > 1? ¿Cual

Rn consta de los pares (a, b) tales que hay personas x1 , x2 . . . xn−1 tal que a conoce a x1 , x1 conoce a x2 , . . . y xn−1 conoce a b ´ es la relacion ´ R∗ ? ¿Cual ´ de R∗ consta de los pares (a, b) tales que existe alguna sucesion personas tal que: ´ 1 a conoce a la primera persona de la sucesion ´ conoce a la siguiente de la sucesion, ´ cada persona de la sucesion ´ 3 y la ultima persona de la sucesion conoce a b 2