Apuntes de Matem´atica Discreta 8. Relaciones de Equivalencia

Francisco Jos´e Gonz´alez Guti´errez C´adiz, Octubre de 2004

Universidad de C´ adiz

Departamento de Matem´ aticas

ii

Lecci´ on 8

Relaciones de Equivalencia Contenido 8.1

Generalidades . . . . . . . 8.1.1 Definici´ on . . . . . . . 8.1.2 Digrafo asociado a una 8.2 Clases de Equivalencia . 8.2.1 Definici´ on . . . . . . . 8.2.2 Lema . . . . . . . . . 8.3 Conjunto Cociente . . . . 8.3.1 Teorema . . . . . . . . 8.3.2 Definici´ on . . . . . . . 8.3.3 Teorema . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Relaci´ on de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

199 200 201 201 201 202 203 203 204 208

La verdad no es un objeto que se encuentre al cabo de una cadena l´ ogica r´ıgida; tampoco est´ a indeterminada en todas las direcciones del discurso. En una regi´ on limitada por contornos excepcionales: descubrir estos contornos es iluminar esa regi´ on, es explorar lo posible y precisar lo probable, es aplicar a las cosas la potencia de la claridad y de orden del esp´ıritu; en una palabra es comprender Jean Ullmo

8.1

Generalidades

Este tipo de relaciones binarias juegan un papel importante en todas las ciencias porque permiten clasificar los elementos del conjunto en el que est´an definidas. Muchas veces trataremos a los elementos de un conjunto m´as por sus propiedades que como objetos individuales. En tales situaciones, podremos ignorar todas las propiedades que no sean de inter´es y tratar elementos diferentes como “equivalentes” o indistinguibles, a menos que puedan diferenciarse utilizando u ´nicamente las propiedades que nos interesen. La noci´on de “equivalencia” tiene tres caracter´ısticas importantes: (i) Todo elemento es equivalente a s´ı mismo. (Reflexividad ). (ii) Si a es equivalente a b, entonces b es equivalente a a. (Simetr´ıa). 199

Universidad de C´ adiz

Departamento de Matem´ aticas

(iii) Si a es equivalente a b y b es equivalente a c, entonces a es equivalente a c. (Transitividad ). Estas propiedades son la base para una clase importante de relaciones binarias sobre un conjunto.

8.1.1

Definici´ on

Una relaci´ on binaria R definida sobre un conjunto A se dice que es de equivalencia cuando es reflexiva, sim´etrica y transitiva. Ejemplo 8.1

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

Ver si R es de equivalencia. Soluci´on Reflexividad. En efecto, (1, 1) ∈ R, (2, 2) ∈ R, (3, 3) ∈ R y (4, 4) ∈ R luego, ∀x (x ∈ A =⇒ xRx) es decir, R es reflexiva. Simetr´ıa. En efecto,

(1, 2) ∈ R y (2, 1) ∈ R (3, 4) ∈ R y (4, 3) ∈ R

luego, ∀x, y ∈ A [(x, y) ∈ R =⇒ (y, x) ∈ R] es decir, la relaci´ on propuesta es sim´etrica. Transitividad. En efecto,

(1, 1) ∈ R y (1, 2) ∈ R

=⇒ (1, 2) ∈ R

(1, 2) ∈ R y (2, 1) ∈ R

=⇒ (1, 1) ∈ R

(1, 2) ∈ R y (2, 2) ∈ R

=⇒ (1, 2) ∈ R

(2, 1) ∈ R y (1, 1) ∈ R

=⇒ (2, 1) ∈ R

(2, 1) ∈ R y (1, 2) ∈ R

=⇒ (2, 2) ∈ R

(2, 2) ∈ R y (2, 1) ∈ R

=⇒ (2, 1) ∈ R

(3, 4) ∈ R y (4, 4) ∈ R

=⇒ (3, 4) ∈ R

(3, 3) ∈ R y (3, 4) ∈ R

=⇒ (3, 4) ∈ R

(4, 3) ∈ R y (3, 3) ∈ R

=⇒ (4, 3) ∈ R

(4, 4) ∈ R y (4, 3) ∈ R

=⇒ (4, 3) ∈ R

luego, ∀x, y, z ∈ A [(x, y) ∈ R ∧ (y, z) ∈ R =⇒ (x, z) ∈ R] y la relaci´on es, por tanto, transitiva.



Ejemplo 8.2 (a) La relaci´ on universal sobre cualquier conjunto A es una relaci´on de equivalencia. 200

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

(b) La relaci´ on vac´ıa ∅ es una relaci´ on de equivalencia sobre el conjunto vac´ıo ∅. No es, sin embargo, una relaci´ on de equivalencia sobre cualquier conjunto no vac´ıo ya que no es reflexiva. (c) La relaci´ on de igualdad sobre cualquier conjunto es una relaci´on de equivalencia.

8.1.2



Digrafo asociado a una Relaci´ on de Equivalencia

El digrafo asociado a una relaci´ on de equivalencia, R, tiene algunas caracter´ısticas que lo distinguen. − Como R es reflexiva, cada v´ertice tiene un bucle. − La simetr´ıa implica que si existe un arco desde a hasta b, tambi´en existe un arco desde b hasta a. − La transitividad implica que si existe un camino desde a hasta b, entonces existe un arco desde a hasta b. Consecuentemente, cada una de las componentes del digrafo de una relaci´ on de equivalencia es un digrafo completo.

8.2

Clases de Equivalencia

8.2.1

Definici´ on

Sea R una relaci´ on de equivalencia sobre un conjunto A. Para cada a ∈ A, llamaremos clase de equivalencia de a, al conjunto formado por todos los elementos de A que est´en relacionados con ´el. La notaremos [a], es decir, [a] = {x ∈ A : xRa} Obs´ervese que la clase de equivalencia de un elemento a nunca es vac´ıa, ya que la reflexividad de R implica que a ∈ [a]. Ejemplo 8.3

Sea A = {a, b, c, d} y R el conjunto R = {(a, a), (a, b), (b, a), (b, b), (c, c), (c, d), (d, c), (d, d)}

Representar el digrafo de R y calcular las clases de equivalencia. Soluci´on

[a] = {a, b} [b] = {a, b} • a

• c

• b

• d

Digrafo

[c] = {c, d} [d] = {c, d}

Clases

Ejemplo 8.3 Obs´ervese que [a] = [b] y [c] = [d], es decir, existen s´olo dos clases de equivalencia. 201



Universidad de C´ adiz

8.2.2

Departamento de Matem´ aticas

Lema

Sea R una relaci´ on de equivalencia sobre el conjunto A. Entonces, (i) [a] = [b] si, y s´ olo si aRb. (ii) Si [a] 6= [b], entonces [a] ∩ [b] = ∅ Demostraci´on (i) [a] = [b] si, y s´ olo si aRb. “S´olo si”. En efecto, supongamos que [a] = [b]. Como a ∈ [a] y [a] = [b], entonces a ∈ [b] de aqu´ı que aRb. “Si”. Supongamos que aRb y sea x cualquiera de A, entonces x ∈ [a] ⇐⇒

xRa

=⇒

xRb

⇐⇒

x ∈ [b]

{Hip´otesis y transitividad de R}

tenemos, pues, que ∀x ∈ A (x ∈ [a] =⇒ x ∈ [b]) es decir, [a] ⊆ [b]. Por otra parte, x ∈ [b] ⇐⇒

xRb

=⇒

xRa

⇐⇒

x ∈ [a]

{Simetr´ıa de la hip´otesis y transitividad de R}

tenemos, pues, que ∀x ∈ A (x ∈ [b] =⇒ x ∈ [a]) es decir, [b] ⊆ [a]. De la doble inclusi´ on hallada se sigue el resultado. (ii) Si [a] 6= [b], entonces [a] ∩ [b] = ∅ Probaremos la contrarrec´ıproca. Es decir, [a] ∩ [b] 6= ∅ =⇒ [a] = [b] En efecto, [a] ∩ [b] 6= ∅

=⇒

∃x ∈ A : x ∈ [a] ∧ x ∈ [b]

⇐⇒

∃x ∈ A : xRa ∧ xRb

=⇒

∃x ∈ A : aRx ∧ xRb

{Simetr´ıa}

=⇒

aRb

{Transitividad}

⇐⇒

[a] = [b]

{Apartado (ii)} 

Obs´ervese que de todo lo anterior se sigue que cualquiera de los elementos que componen una clase de equivalencia puede elegirse como representante de la misma. 202

Matem´ atica Discreta

8.3

Francisco Jos´e Gonz´ alez Guti´errez

Conjunto Cociente

8.3.1

Teorema

Si R es una relaci´ on de equivalencia en un conjunto A, entonces la familia de todas las clases de equivalencia de los elementos de A produce una partici´ on de A. Demostraci´on Dado que cada clase de equivalencia es un subconjunto de A, el conjunto de todas ellas ser´a una familia de subconjuntos de A. Veamos que, en efecto, es una partici´ on de A. 1. [a] 6= ∅, ∀a ∈ A En efecto, como ya dijimos antes, al menos a pertenece a su clase de equivalencia, luego son no vac´ıas. 2. Si [a] 6= [b], entonces [a] ∩ [b] = ∅ Directamente de (ii) en el lema anterior. 3.

[

[a] = A

a∈A

Veamos que la uni´ on de todas las clases de equivalencia es el conjunto A. En efecto, x∈

[a]⊆A

[

[a] =⇒ ∃a ∈ A : x ∈ [a] =⇒ x ∈ A

a∈A

luego, ! ∀x x ∈

[

[a] =⇒ x ∈ A

a∈A

es decir, [

[a] ⊆ A

a∈A

Por otra parte, x ∈ A =⇒ x ∈ [x] =⇒ x ∈

[

[a]

a∈A

luego, ! ∀x x ∈ A =⇒ x ∈

[

[a]

a∈A

es decir, A⊆

[

[a]

a∈A

de la doble inclusi´ on se sigue el resultado, A=

[

[a]

a∈A

 203

Universidad de C´ adiz

8.3.2

Departamento de Matem´ aticas

Definici´ on

Dada una relaci´ on de equivalencia sobre un conjunto A, llamaremos conjunto cociente al formado por todas las clases de equivalencia, lo notaremos por A/R, indicando as´ı que es el conjunto A partido por la relaci´ on de equivalencia R. A/R = {[a] : a ∈ A} Ejemplo 8.4 8.1

Determinar el conjunto cociente A/R siendo R la relaci´on de equivalencia del ejemplo

Soluci´on A = {1, 2, 3, 4} [1] = {x ∈ A : xR1} = {1, 2} [2] = {x ∈ A : xR1} = {1, 2} [3] = {x ∈ A : xR1} = {3, 4} [4] = {x ∈ A : xR1} = {3, 4} Consecuentemente, A/R = {[1] , [3]} = {{1, 2} , {3, 4}}  Ejemplo 8.5

Sea el conjunto Z+ × Z+ y consideremos en ´el la relaci´on (a, b)R(c, d) si, y s´olo si a + d = b + c

cualesquiera que sean (a, b) y (c, d) de Z+ × Z+ . (a) Probar que la relaci´ on propuesta es de equivalencia. (b) Hallar las clases de equivalencia. (c) Obtener el conjunto cociente. (d) Escribir el conjunto cociente que se obtiene en el caso de que la relaci´on se defina en el conjunto A × A siendo A = {1, 2, 3, 4, 5}. (e) Construir una gr´ afica que represente al conjunto cociente para A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Soluci´on (a) Probaremos que R cumple las condiciones exigidas para ser de equivalencia. Reflexividad. En efecto, para cada par (a, b) de Z+ × Z+ se verifica que a+b=b+a de aqu´ı que (a, b)R(a, b) y la relaci´on es, por tanto, reflexiva. Simetr´ıa. En efecto, si (a, b) y (c, d) son cualesquiera de Z+ × Z+ tales que (a, b)R(c, d) 204

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

tendremos que a+d=b+c de donde por la conmutatividad de la suma en Z+ se sigue que d+a=c+b luego (c, d)R(a, b) y R es, por tanto, sim´etrica. Transitividad. Sean (a, b), (c, d) y (e, f ) tres elementos arbitrarios de Z+ × Z+ , tales que (a, b)R(c, d) y (c, d)R(e, f ) es decir, tales que a+d=b+c y c+f =d+e si sumamos miembro a miembro ambas igualdades obtendremos a+d+c+f =b+c+d+e de donde se sigue que a+f =b+e luego (a, b)R(e, f ) y, consecuentemente, R es transitiva. Por ser reflexiva, sim´etrica y transitiva, R ser´a una relaci´on de equivalencia (b) Hallemos las clases de equivalencia. Sea (a, b) un par de enteros positivos cualesquiera. Entonces, [(a, b)]

= {(x, y) ∈ Z+ × Z+ : (x, y)R(a, b)} = {(x, y) ∈ Z+ × Z+ : x + b = y + a} = {(x, y) ∈ Z+ × Z+ : x − y = a − b} = {(x, y) ∈ Z+ × Z+ : x − y = d}

donde d es la diferencia entre a y b. Cuando el par (a, b) recorra todo el conjunto Z+ ×Z+ , su diferencia, d, recorrer´a el conjunto Z de los n´ umeros enteros ya que ser´a un entero negativo, cero o positivo dependiendo de que a sea menor, igual o mayor que b. Por lo tanto, la clase de equivalencia de cualquier elemento tendr´a la forma:  (x, y) ∈ Z+ × Z+ : x − y = d, con d ∈ Z Por ejemplo, 

(x, y) ∈ Z+ × Z+ : x − y = 0

ser´a la clase de equivalencia del par (1, 1) y del (2, 2), del (3, 3), etc..., en general de todos los pares de la forma (a, a). Tomando como representante el (1, 1),  [(1, 1)] = (x, y) ∈ Z+ × Z+ : x = y = {(1, 1), (2, 2), (3, 3), . . . . . .} y el conjunto 

(x, y) ∈ Z+ × Z+ : x − y = −8 = {(1, 9), (2, 10), (3, 11), (4, 12), . . . . . .} 205

Universidad de C´ adiz

Departamento de Matem´ aticas

ser´a, por ejemplo, [(1, 9)], clase de equivalencia del par (1, 9). (c) Obtengamos el conjunto cociente. Z+ × Z+ /R

= {

······

{(x, y) ∈ Z+ × Z+ : x − y = −2} , {(x, y) ∈ Z+ × Z+ : x − y = −1} , {(x, y) ∈ Z+ × Z+ : x − y = 0} , {(x, y) ∈ Z+ × Z+ : x − y = 1} , {(x, y) ∈ Z+ × Z+ : x − y = 2} ,

······

}

es decir, Z+ × Z+ /R

=



{(x, y) ∈ Z+ × Z+ : x − y = d}d∈Z− ,

{(x, y) ∈ Z+ × Z+ : x − y = 0} , {(x, y) ∈ Z+ × Z+ : x − y = d}d∈Z+  = {(x, y) ∈ Z+ × Z+ : x − y = −d}d∈Z+ , {(x, y) ∈ Z+ × Z+ : x − y = 0} , {(x, y) ∈ Z+ × Z+ : x − y = d}d∈Z+  = {(x, x + d) ∈ Z+ × Z+ }d∈Z+ , {(x, x) ∈ Z+ × Z+ } , {(y + d, y) ∈ Z+ × Z+ }d∈Z+ = {[(x, x + d)] , [(x, x)] , [(y + d, y)] , con d ∈ Z+ }x∈Z+ ,y∈Z+ y como x − (x + d) = −d, x − x = 0 y d + y − y = d independientemente de los valores que tomen x e y, podemos tomar x = 1 e y = 1, es decir elegir como representante de cada clase a los pares (1, 1 + d), (1, 1) y (1 + d, 1), respectivamente. Entonces,  Z+ × Z+ /R = [(1, 1 + d)] , [(1, 1)] , [(1 + d, 1)] , con d ∈ Z+ y haciendo 1 + d = p,   Z+ × Z+ /R = [(1, p)] , [(1, 1)] , [(p, 1)] , con p ∈ Z+ \ {1} = [(1, p)] , [(p, 1)] , con p ∈ Z+ (d) Escribiremos el conjunto cociente para el subconjunto de Z+ , A = {1, 2, 3, 4, 5} A × A/R

= {[(1, p)] , [(p, 1)] , con p ∈ A} = {[(1, 5)] , [(1, 4)] , [(1, 3)] , [(1, 2)] , [(1, 1)] , [(2, 1)] , [(3, 1)] , [(4, 1)] , [(5, 1)]} = {{(1, 5)} , {(1, 4)(2, 5)} , {(1, 3), (2, 4), (3, 5)} , {(1, 2), (2, 3), (3, 4), (4, 5)} , =

{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)} , {(2, 1), (3, 2), (4, 3), (5, 4)} , {(3, 1), (4, 2), (5, 3)} ,

=

{(4, 1), (5, 2)} , {(5, 1)}}

(e) Construiremos una gr´ afica representativa del conjunto cociente para el subconjunto de Z+ , A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} . 206

Matem´ atica Discreta

(2, 10)

(3, 10)

(4, 10)

(5, 10)

(6, 10)

(8, 10)

(7, 10)

(9, 10)

(10, 10)

(1, 9)

(2, 9)

(3, 9)

(4, 9)

(5, 9)

(6, 9)

(7, 9)

(8, 9)

(9, 9)

(10, 9)

(1, 8)

(2, 8)

(3, 8)

(4, 8)

(5, 8)

(6, 8)

(7, 8)

(8, 8)

(9, 8)

(10, 8)

(1, 7)

(2, 7)

(3, 7)

(4, 7)

(5, 7)

(6, 7)

(7, 7)

(8, 7)

(9, 7)

(10, 7)

(1, 6)

(2, 6)

(3, 6)

(4, 6)

(5, 6)

(6, 6)

(7, 6)

(8, 6)

(9, 6)

(10, 6)

(1, 5)

(2, 5)

(3, 5)

(4, 5)

(5, 5)

(6, 5)

(7, 5)

(8, 5)

(9, 5)

(10, 5)

(1, 4)

(2, 4)

(3, 4)

(4, 4)

(5, 4)

(6, 4)

(7, 4)

(8, 4)

(9, 4)

(10, 4)

(1, 3)

(2, 3)

(3, 3)

(4, 3)

(5, 3)

(6, 3)

(7, 3)

(8, 3)

(9, 3)

(10, 3)

(1, 2)

(2, 2)

(3, 2)

(4, 2)

(5, 2)

(6, 2)

(7, 2)

(8, 2)

(9, 2)

(10, 2)

(1, 1)

(2, 1)

(3, 1)

(4, 1)

(5, 1)

(6, 1)

(7, 1)

(8, 1)

(9, 1)

(10, 1)

Conjunto cociente Ejemplo 8.6

En el conjunto A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} se considera la relaci´on aRb si, y s´olo si a − b es m´ ultiplo de 3

Probar que es de equivalencia, hallar las clases de equivalencia y el conjunto cociente. Soluci´on Obs´ervese que a − b es m´ ultiplo de 3 ⇐⇒ a − b = 3k; k ∈ Z. luego la relaci´ on puede escribirse en la forma aRb ⇐⇒ a − b = 3k; k ∈ Z Reflexiva. Para cada a de A se verifica que a−a=0 lo cual puede escribirse en la forma a − a = 3 · 0; 0 ∈ Z 207

[(1 0, 1) ]

[(9 ,1 )]

[(8 ,1 )]

[(7 ,1 )]

)] [(6 ,1

[(5 ,1 )]

)] [(4 ,1

)] [(3 ,1

)] [(2 ,1

[(1 ,1

)]

[(1 ,2

)]

[(1 ,3

)]

[(1 ,4

)]

[(1 ,5

)]

[(1 ,6

)]

[(1 ,7

)]

[(1 ,8

)]

[(1 ,9 )]

[(1 ,1 0) ]

(1, 10)

Francisco Jos´e Gonz´ alez Guti´errez

Universidad de C´ adiz

Departamento de Matem´ aticas

luego aRa. Sim´etrica. Si a y b son cualesquiera de A tales que aRb, entonces a − b = 3k; k ∈ Z de aqu´ı que b − a = 3(−k); −k ∈ Z y por tanto, bRa. Transitiva. En efecto, si a, b y c son cualesquiera de A tales que aRb y bRc, entonces a − b = 3k1 ; k1 ∈ Z y b − c = 3k2 ; k2 ∈ Z y si sumamos miembro a miembro ambas ecuaciones, tendremos que a − c = 3(k1 + k2 ); k1 + k2 ∈ Z luego aRc. Clases de equivalencia. Si a es cualquiera de A, entonces x ∈ [a] ⇐⇒

xRa

⇐⇒

x − a = 3k; k ∈ Z

⇐⇒

x = a + 3k; k ∈ Z

luego [a] = {x : x = a + 3k; k ∈ Z} . As´ı pues, [0] = {x : x = 3k; k ∈ Z} = {0, 3, 6, 9} [1] = {x : x = 1 + 3k; k ∈ Z} = {1, 4, 7} [2] = {x : x = 2 + 3k; k ∈ Z} = {2, 5, 8} El conjunto cociente ser´ a, por tanto, A/R = {{0, 3, 6, 9} , {1, 4, 7} , {2, 5, 8}} 

8.3.3

Teorema

Dada una partici´ on de un conjunto A, puede definirse en ´el una relaci´ on de equivalencia R tal que el conjunto cociente A/R coincida con la partici´ on dada. Demostraci´on Sea {A1 , A2 , . . . , An } una partici´ on del conjunto A. Definimos la siguiente relaci´on: Dos elementos de A est´ an relacionados si, y s´ olo si pertenecen al mismo subconjunto de la partici´ on. es decir, si a y b son cualesquiera de A, entonces aRb ⇐⇒ ∃Ai ⊆ A : a y b ∈ Ai Veamos que R es de equivalencia. En efecto, 208

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

Reflexividad. Si a es cualquiera de A, como {A1 , A2 , . . . , An } es una partici´on de A, ser´a A=

n [

Ai

i=1

luego a∈

n [

Ai =⇒ ∃Ai : a ∈ Ai =⇒ a y a ∈ Ai =⇒ aRa

i=1

por lo tanto, ∀a (a ∈ A =⇒ aRa) es decir, la relaci´ on es reflexiva. Simetr´ıa. Sean a y b dos elementos cualesquiera de A, entonces aRb ⇐⇒ ∃Ai ⊆ A : a y b ∈ Ai =⇒ ∃Ai ⊆ A : b y a ∈ Ai ⇐⇒ bRa o sea, ∀a, b ∈ A (aRb =⇒ bRa) y la relaci´ on es, por tanto, sim´etrica. Transitividad. En efecto, si a, b y c son tres elementos arbitrariamente elegidos en A, entonces aRb ⇐⇒ ∃Ai ⊆ A : a y b ∈ Ai y bRc ⇐⇒ ∃Aj ⊆ A : b y c ∈ Aj de donde se sigue que b ∈ Ai ∩ Aj , consecuentemente Ai ∩ Aj 6= ∅ y por la definici´on de partici´on tendremos que Ai = Aj . Resulta, pues, que a y c pertenecen al mismo subconjunto de la partici´on y, por lo tanto, aRc. As´ı pues, ∀a, b, c ∈ A (aRb ∧ bRc =⇒ aRc) es decir, R es transitiva. Veamos el conjunto cociente. Por la forma en que hemos definido la relaci´on, se sigue directamente que las clases de equivalencia correspondientes son los subconjuntos de la partici´on, luego A/R = {A1 , A2 , . . . , An }  Ejemplo 8.7 Sea A = {1, 3, 3, 4} y {{1, 2, 3} , {4}} una partici´on de A. Determ´ınese la relaci´on de equivalencia correspondiente en A. Soluci´on Si tenemos en cuenta que las clases de equivalencia son los subconjuntos de la partici´on, tendremos [1] = {1, 2, 3} y [4] = {4} A partir de la definici´ on de clases de equivalencia y de que R ha de ser de equivalencia, tendremos: [1] = {1, 2, 3} , luego (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) ∈ R [4] = {4} , luego (4, 4) ∈ R 209

Universidad de C´ adiz

Departamento de Matem´ aticas

de aqu´ı que R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)}  Ejemplo 8.8 Determinar si la relaci´ on R cuya matriz se da es una relaci´on de equivalencia sobre el conjunto A = {a, b, c}.

(a) MR

(b) MR



1 = 0 0

0 1 1

 0 1  1



0 1 0

 1 0  1

1 = 0 0

Soluci´on Supongamos que rij es un elemento cualquiera de la matriz, donde i indica la fila a la que pertenece y j la columna. (a) Veamos si cumple las condiciones para que la relaci´on propuesta sea de equivalencia. Reflexiva. En efecto lo es ya que todos los elementos de la diagonal principal son unos, lo cual significa que ∀x (x ∈ A =⇒ xRx) Sim´etrica. Tambi´en lo es, ya que rij = rji , ∀i, j = 1, 2, 3; i 6= j lo cual significa que ∀x, y ∈ A (xRy =⇒ yRx) Transitiva. Se prueba con facilidad que si rij = 1 ∧ rjk = 1, entonces rik = 1 y si rik = 0, entonces rij = 0 ∨ rjk = 0 lo cual significa que ∀x, y, z ∈ A (xRy ∧ yRz =⇒ xRz) (b) La relaci´ on propuesta no es de equivalencia ya que r13 = 1 y r31 = 0, lo cual significa que aRc y, sin embargo cR /a es decir, la relaci´ on propuesta no es sim´etrica. Ejemplo 8.9 equivalencia.



Determinar si las relaciones cuyos grafos dirigidos se dan en la figura siguiente son de

210

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

• 2

1 •

1 •

• 2

6 •

5 • 3 • • 3

4 •

(a)

(b)

Soluci´on (a) Veamos si cumple las tres condiciones. Reflexiva. En efecto lo es, ya que en cada uno de los v´ertices hay un bucle. Sim´etrica. Tambi´en lo es, ya que entre cada dos v´ertices x e y hay dos aristas, una que va desde x hasta y y otra que va desde y hasta x. Transitiva. En efecto, para cada camino entre dos puntos x e y del digrafo, hay una arista entre los mismos. (b) Veamos si cumple las condiciones exigidas para que la relaci´on representada por el digrafo sea de equivalencia. Reflexiva. En cada uno de los v´ertices hay un bucle, luego la relaci´on es reflexiva. Sim´etrica. No lo es, ya que por ejemplo entre 1 y 2 hay una arista, pero no as´ı entre 2 y 1. Consecuentemente, la relaci´ on no es de equivalencia.



Ejemplo 8.10 Si {{a, c, e} , {b, d, f }} es una partici´on del conjunto A = {a, b, c, d, e, f }, determinar la relaci´on de equivalencia correspondiente. Soluci´on Si R es la relaci´ on de equivalencia buscada, entonces el conjunto cociente es A/R = {{a, c, e} , {b, d, f }} luego las clases de equivalencia son [a] = {a, c, e} y [b] = {b, d, f } Pues bien, [a] = {a, c, e} , luego (a, a), (a, c), (a, e), (c, a), (c, c), (c, e), (e, a), (e, c) y (e, e) est´an en R 211

Universidad de C´ adiz

Departamento de Matem´ aticas

tambi´en, [b] = {b, d, f } , luego (b, b), (b, d), (b, f ), (d, b), (d, d), (d, f ), (f, b), (f, d) y (f, f ) est´an en R Consecuentemente, la relaci´ on es R

= {(a, a), (a, c), (a, e), (c, a), (c, c), (c, e), (e, a), (e, c), (e, e), (b, b), (b, d), (b, f ), (d, b), (d, d), (d, f ), (f, b), (f, d), (f, f )} 

Ejemplo 8.11

Sobre el conjunto Z+ × Z+ se define la relaci´on, (a, b)R(c, d) ⇐⇒ ad = bc

(a) Probar que R es de equivalencia. (b) Obtener las clases de equivalencia. (c) Escribir el conjunto cociente. (d) Escribir el conjunto cociente y dibujar una gr´afica explicativa del mismo para el conjunto A × A, siendo A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Soluci´on (a) Probaremos que R es de equivalencia. Reflexiva. Sea (a, b) cualquiera de Z+ × Z+ A. Por la conmutatividad del producto de enteros, ab = ba, luego (a, b)R(b, a), es decir,   ∀(a, b) (a, b) ∈ Z+ × Z+ =⇒ (a, b)R(a, b) y la relaci´on es, en efecto, reflexiva. Sim´etrica. Sean (a, b) y (c, d) dos elementos arbitrarios de Z+ × Z+ . Entonces, (a, b)R(c, d) ⇐⇒ ad = bc ⇐⇒ bc = ad ⇐⇒ (c, d)R(a, b) luego, ∀(a, b), (c, d) ∈ Z+ × Z+ [(a, b)R(c, d) =⇒ (c, d)R(a, b)] es decir, R es sim´etrica. Transitiva. Si (a, b), (c, d) y (e, f ) son cualesquiera de Z+ × Z+ , entonces  (a, b)R(c, d) ⇐⇒ ad = bc  y =⇒ adcf = bcde =⇒ af = be ⇐⇒ (a, b)R(e, f )  (c, d)R(e, f ) ⇐⇒ cf = de (b) Obtengamos las clases de equivalencia. Sea (a, b) un par de enteros positivos cualquiera. Entonces, [(a, b)]

= {(x, y) ∈ Z+ × Z+ : (x, y)R(a, b)} = {(x, y) ∈ Z+ × Z+ : xb = ya}   a + + x = (x, y) ∈ Z × Z : = y b

Por ejemplo, [(9, 15)] =

  x 9 (x, y) ∈ Z+ × Z+ : = y 15 212

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

ahora bien, 9 = 15

9 3 15 3

=

3 , siendo 3 = m.c.d.(9, 15) 5

y 3 3k = , con k ∈ Z+ 5 5k luego,   3 + + x [(9, 15)] = (x, y) ∈ Z × Z : = = [(3, 5)] y 5 y [(3, 5)]

=

  3 x (x, y) ∈ Z+ × Z+ : = y 5

= {(x, y) ∈ Z+ × Z+ : x = 3k e y = 5k, con k ∈ Z+ } = {(3k, 5k) : k ∈ Z+ } = {k(3, 5) : k ∈ Z+ } En general podemos razonar de forma an´ aloga. a − Si m.c.d.(a, b) = 1, es decir si la fracci´on es irreducible, entonces b ka a = , con k ∈ Z+ b kb − Si m.c.d.(a, b) = d 6= 1, entonces a = b y la fracci´ on

a d b d

a d b d

es irreducible, luego a d b d

=

k ad k db

con k ∈ Z+

Por lo tanto, si llamamos d al m.c.d.(a, b), tendremos   x a/d [(a, b)] = (x, y) ∈ Z+ × Z+ : = y b/d   a b + + + = (x, y) ∈ Z × Z : x = k e y = k , con k ∈ Z d d    a b = k ,k , con k ∈ Z+ d d     a b + = k , , con k ∈ Z d d Por ejemplo, si queremos calcular la clase de equivalencia del par (3, 7), como m.c.d.(3, 7) = 1, tendremos que [(3, 7)] = {k(3, 7), con k ∈ Z+ } = {(3, 7), (6, 14), (9, 21), (12, 28), (15, 35), . . .} y si queremos calcular la clase del par (16, 20), como m.c.d.(16, 20) = 4,     16 20 [(16, 20)] = k , , con k ∈ Z+ 4 4 = {k(4, 5), con k ∈ Z+ } = {(4, 5), (8, 15), (16, 20), (20, 25), (24, 30), . . .} 213

Universidad de C´ adiz

Departamento de Matem´ aticas

(c) Escribamos el conjunto cociente Z+ × Z+ /R. Seg´ un lo que hemos visto en el punto anterior, Z+ × Z+ /R

= {{k(a, b), con k ∈ Z+ } (a, b) ∈ Z+ × Z+ y m.c.d.(a, b) = 1} = {[(a, b)] : (a, b) ∈ Z+ × Z+ y m.c.d.(a, b) = 1}

(d) Veamos cual es el conjunto cociente para A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Por el punto anterior, = {{k(a, b), con k ∈ Z+ } (a, b) ∈ A × A y m.c.d.(a, b) = 1}

A × A/R

= {[(a, b)] : (a, b) ∈ A × A y m.c.d.(a, b) = 1} luego tenemos que saber cuantos pares de n´ umeros primos entre s´ı hay en el conjunto A × A. En la siguiente tabla figuran los divisores de todos los n´ umeros y en los cruces los divisores comunes.

1 2 3 4 5 6 1 8 9 10

1 1,2 1,3 1,2,4 1,5 1,2,3,6 1,7 1,2,4,8 1,3,9 1,2,5,10

1 1 1 1 1 1 1 1 1 1 1 1

2 1,2 1 1,2 1 1,2 1 1,2 1 1,2 1 1,2

3 1,3 1 1 1,3 1 1 1,3 1 1 1,3 1

4 1,2,4 1 1,2 1 1,2,4 1 1,2 1 1,2,4 1 1,2

5 1,5 1 1 1 1 1,5 1 1 1 1 1,5

6 1,2,3,6 1 1,2 1,3 1,2 1 1,2,3,6 1 1,2 1,3 1,2

7 1,7 1 1 1 1 1 1 1,7 1 1 1

8 1,2,4,8 1 1,2 1 1,2,4 1 1,2 1 1,2,4,8 1 1,2

9 1,3,9 1 1 1,3 1 1 1,3 1 1 1,3,9 1

10 1,2,5,10 1 1,2 1 1,2 1,5 1,2 1 1,2 1 1,2,5,10

Por lo tanto, A × A/R

= {[(1, 10)] , [(1, 9)] , [(1, 8)] , [(1, 7)] , [(1, 6)] , [(1, 5)] , [(2, 9)] , [(1, 4)] , [(2, 7)] , [(3, 10)] , [(1, 3)] , [(3, 8)] , [(2, 5)] , [(3, 7)] , [(4, 9)] , [(1, 2)] , [(5, 9)] , [(4, 7)] , [(3, 5)] , [(5, 8)] , [(2, 3)] , [(7, 10)] , [(5, 7)] , [(3, 4)] , [(7, 9)] , [(4, 5)] , [(5, 6)] , [(6, 7)] , [(7, 8)] , [(8, 9)] , [(9, 10)] , [(1, 1)] , [(10, 9)] , [(9, 8)] , [(8, 7)] , [(7, 6)] , [(6, 5)] , [(5, 4)] , [(9, 7)] , [(4, 3)] , [(7, 5)] , [(10, 7)] , [(3, 2)] , [(8, 5)] , [(5, 3)] , [(7, 4)] , [(9, 5)] , [(2, 1)] , [(9, 4)] , [(7, 3)] , [(5, 2)] , [(8, 3)] , [(3, 1)] , [(10, 3)] , [(7, 2)] , [(4, 1)] , [(9, 2)] , [(5, 1)] , [(6, 1)] , [(7, 1)] , [(8, 1)] , [(9, 1)] , [(10, 1)]} = {{(1, 10)} , {(1, 9)} , {(1, 8)} , {(1, 7)} , {(1, 6)} , {(1, 5) , (2, 10)} , {(2, 9)} , {(1, 4) , (2, 8)} , {(2, 7)} , {(3, 10)} , {(1, 3) , (2, 6) , (3, 9)} , {(3, 8)} , {(2, 5) , (4, 10)} , {(3, 7)} , {(4, 9)} , {(1, 2) , (2, 4) , (3, 6) , (4, 8) , (5, 10)} , {(5, 9)} , {(4, 7)} , {(3, 5) , (6, 10)} , {(5, 8)} , {(2, 3) , (4, 6) , (6, 9)} , {(7, 10)} , {(5, 7)} , {(3, 4) , (6, 8)} , {(7, 9)} , {(4, 5) , (8, 10)} , {(5, 6)} , {(6, 7)} , {(7, 8)} , {(8, 9)} , {(9, 10)} , {(1, 1)} , {(10, 9)} , {(9, 8)} , {(8, 7)} , {(7, 6)} , {(6, 5)} , {(5, 4) , (10, 8)} , {(9, 7)} , {(4, 3) , (8, 6)} , {(7, 5)} , {(10, 7)} , {(3, 2) , (6, 4) , (9, 6)} , {(8, 5)} , {(5, 3) , (10, 6)} , {(7, 4)} , {(9, 5)} , {(2, 1) , (4, 2) , (6, 3) , (8, 4) , (10, 5)} , {(9, 4)} , {(7, 3)} , {(5, 2) , (10, 4)} , {(8, 3)} , {(3, 1) , (6, 2) , (9, 3)} , {(10, 3)} , {(7, 2)} , {(4, 1) , (8, 2)} , {(9, 2)} , {(5, 1) , (10, 2)} , {(6, 1)} , {(7, 1)} , {(8, 1)} , {(9, 1)} , {(10, 1)}}

Veamos una gr´ afica del conjunto cociente para A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. 214

•

•

•

•

•

•

•

•

•

•

[(1, 4

•

[(1 , 2)

• [(1 ,1

)]

1 •

• 1

)] , 3• 4 ( [

•

[(2 ,3

[(1, 3

• ]

2 •

• )]

• )]

3 •

•

)]

•

[(3 ,4

•

, 1) [(2

]•

• 2

• )]

•

,2 [(3

[(3,

1)]

•

)] [(4, 1

• 3

•

• 4

)]

•

•

•

•

•

)] ,8 ([ 9 •

•

•

)] , 7• 8 [(

]• 7) , [(9

• )] 7 0, [(1

•

•

• )] ,5 [(9 4)] [(9, •

•

)]

[(7 ,8 )] )]

)] , 5• 6 [(

•

[(4 ,5

] [(3 , 5)

5)] [(2,

• )]

4 •

•

)] , 4• 5 ( [

•

)] , 6• 7 ( [

• )]

,5 [(7

•

2)]

•

•

)] [(7, 2

•

[(5, 1)]

•

•

[(7, 1)]

•

[(6, 1)]

• 5

•

)] •

,5 [(8

• )] • ,4 7 ( [ 3)] [(7,• • 3)] [(8,

• 3)] , 5 [( [(5,

• 6

• ]

[(6 ,7

•

• [(1, 5)]

5 •

•

[(5 ,7 )]

•

•

[(5 ,6 )]

•

•

[(7 ,1

8)] [(5 ,

[(4 , 7) ]

7)]

•

)]

•

•

[(7 ,9

[(4,

9)]

[(3, 1

•

[(2, 7

[(3,

•

•

]

•

•

8)]

•

[(3,

[(1, 8)]

]

•

[(1, 6)]

6 •

•

[(1, 7)]

7 •

•

0)]

8 •

•

[(9 ,1 0)

•

•

[(8 ,9 )]

•

9 •

•

0) ]

•

[(2, 9)

•

[(1, 9)] [(1, 10)]

10 •

Francisco Jos´e Gonz´ alez Guti´errez

[(5 , 9) ]

Matem´ atica Discreta

• 7

[(8, 1)]

•

[(10,

•

3)] •

•

[(9, 2)

•

• • [(9, 1)] [(10, 1)]

• 8

]•

9) 0,• 1 [(

• 9

•

• 10

Conjunto cociente  Ejemplo 8.12

Sobre Z+ × Z+ se define la relaci´on, (a, b)R(c, d) ⇐⇒ a + b = c + d

(a) Probar que R es de equivalencia. (b) Hallar las clases de equivalencia. (c) Obtener el conjunto cociente. Soluci´on 215

Universidad de C´ adiz

Departamento de Matem´ aticas

(a) Probemos que R es de equivalencia. Reflexiva. Para todo (a, b) de Z+ × Z+ se verifica que a + b = a + b, de aqu´ı que (a, b)R(a, b) y R sea reflexiva. Sim´etrica. Para todo (a, b) y (c, d) de Z+ × Z+ , se verifica, (a, b)R(c, d) ⇐⇒ a + b = c + d ⇐⇒ c + d = a + b ⇐⇒ (c, d)R(a, b) luego R es sim´etrica. Transitiva. Para todo (a, b), (c, d) y (e, f ) de AZ+ × Z+ , se verifica,  (a, b)R(c, d) ⇐⇒ a + b = c + d  y =⇒ a + b = e + f ⇐⇒ (a, b)R(e, f )  (c, d)R(e, f ) ⇐⇒ c + d = e + f luego R es transitiva y, consecuentemente, de equivalencia. (b) Hallemos las clases de equivalencia. Sea (a, b) cualquier par de enteros positivos. Entonces, [(a, b)]

= {(x, y) ∈ Z+ × Z+ : (x, y)R(a, b)} = {(x, y) ∈ Z+ × Z+ : x + y = a + b} = {(a + b − y, y) ∈ Z+ × Z+ } = {(a + b − y, y) : a + b − y ∈ Z+ e y ∈ Z+ } = {(a + b − y, y) : a + b − y > 1 e y > 1} = {(a + b − y, y) : y 6 a + b − 1 e y > 1} = {(a + b − y, y) : 1 6 y 6 a + b − 1}

Por ejemplo, [(1, 1)] = {(1 + 1 − y, y) : 1 6 y 6 1 + 1 − 1} = {(2 − y, y) : y = 1} = {(1, 1)} y [(5, 8)]

= {(5 + 8 − y, y) : 1 6 y 6 5 + 8 − 1} = {(13 − y, y) : 1 6 y 6 12} = {(12, 1), (11, 2), (10, 3), (9, 4), (8, 5), (7, 6), (6, 7), (4, 9), (3, 10), (2, 11), (1, 12)}

(c) Obtengamos el conjunto cociente.  Z+ × Z+ /R = [(a, b)] : (a, b) ∈ Z+ × Z+ donde [(a, b)]

= {(a + b − y, y) : 1 6 y 6 a + b − 1} = {(a + b − 1, 1) , (a + b − 1, 2) , . . . , (2, a + b − 2) , (1, a + b − 1)} =

[(a + b − 1, 1)]

es decir, en cada clase habr´ a un par cuya segunda componente es 1 y que elegiremos como representante, luego  Z+ × Z+ /R = [(a + b − 1, 1)] : a ∈ Z+ y b ∈ Z+ . Adem´as, a ∈ Z+ y b ∈ Z+

 =⇒ a > 1    =⇒ b > 1

=⇒ a + b > 2 =⇒ a + b − 1 > 1 =⇒ a + b − 1 ∈ Z+

   216

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

es decir, cuando el par (a, b) recorra Z+ × Z+ , a + b − 1 recorrer´a Z+ , luego si hacemos a + b − 1 igual a k, tendremos que  Z+ × Z+ /R = [(k, 1)] : k ∈ Z+ . La gr´afica siguiente es una representaci´on parcial del conjunto cociente.

(1, 10)

(1, 9)

(2, 9)

(1, 8)

(2, 8)

(3, 8)

(1, 7)

(2, 7)

(3, 7)

(4, 7)

(1, 6)

(2, 6)

(3, 6)

(4, 6)

(5, 6)

(1, 5)

(2, 5)

(3, 5)

(4, 5)

(5, 5)

(6, 5)

(1, 4)

(2, 4)

(3, 4)

(4, 4)

(5, 4)

(6, 4)

(7, 4)

(1, 3)

(2, 3)

(3, 3)

(4, 3)

(5, 3)

(6, 3)

(7, 3)

(8, 3)

(1, 2)

(2, 2)

(3, 2)

(4, 2)

(5, 2)

(6, 2)

(7, 2)

(8, 2)

(9, 2)

(1, 1)

(2, 1)

(3, 1)

(4, 1)

(5, 1)

(6, 1)

(7, 1)

(8, 1)

(9, 1)

(10, 1) [(1 )]

1 0,

)]

,1 [(9

)]

,1 [(8

)]

)]

)]

)]

,1 [(7

,1 [(6

,1 [(5

,1 [(4

)]

,1 [(3

)]

,1 [(2

)]

,1 [(1

Conjunto cociente  Ejemplo 8.13

En el conjunto Z+ se define la siguiente relaci´on R √
√ xRy ⇐⇒ E x = E ( y)

donde E(x) significa “parte entera de x”. Demostrar que se trata de una relaci´ on de equivalencia, hallar las clases de equivalencia y el conjunto cociente. Soluci´on 217

Universidad de C´ adiz

Departamento de Matem´ aticas

R es de equivalencia.

√ √ En efecto, para cada entero positivo x se verifica que E( x) = E( x), luego,
∀x x ∈ Z+ =⇒ xRx es decir, R es reflexiva. Tambi´en es sim´etrica puesto que,   √ √ √ √ ∀x, y ∈ Z+ xRy =⇒ E( x) = E( y) ⇐⇒ E( y) = E( x) =⇒ yRx y transitiva, ya que   √
√ √ √ √
√ ∀x, y, z ∈ Z+ xRy ∧ yRz =⇒ E( x) = E( y) ∧ E( y) = E( z) =⇒ E( x) = E( z) =⇒ xRz Clases de equivalencia. Sea n un n´ umero entero positivo cualquiera, entonces  [n] = x ∈ Z+ : xRn luego, x ∈ [n] ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ es decir,

xRn √ √ E ( x) = E ( n) √ √ √ E ( n) 6 x < E ( n) + 1 √ 2 √ 2 (E ( n)) 6 x < (E ( n) + 1)

n
2 o √
√

2 n 6x< E n +1 [n] = x ∈ Z+ : E

Por ejemplo, n √

2 √

2 o [1] = x ∈ Z+ : E 1 1 +1 6x< E = {x ∈ Z+ : 1 6 x < 4} = {1, 2, 3} n √
√

2
2 o 4 6x< E 4 +1 = {x ∈ Z+ : 4 6 x < 9} = {4, 5, 6, 7, 8} [4] = x ∈ Z+ : E y as´ı, sucesivamente. Conjunto cociente. Observemos lo siguiente: √ √ √ E( 1) = 1, E( 2) = 1, E( 3) = 1, √ √ √ E( 4) = 2, E( 5) = 2, E( 6) = 2, √ √ E( 9) = 3, E( 10) = 3, ... √ √ E( 16) = 4, E( 17) = 4, ... √ E( 25) = 4, ... ...

√ E( 7) = 2,

√ E( 8) = 2

...

...

√ E( 15) = 3

...

...

...

√ E( 24) = 4

...

...

...

...

y as´ı sucesivamente, de aqu´ı que el conjunto cociente sea Z+ /R

= {[1] , [4] , [9] , [16] , [25] . . . . . .}  2  = n : n ∈ Z+   √ 2  √  2  n2 6x< E n2 + 1 = x ∈ Z+ : E =



x ∈ Z+ : n2 6 x < (n + 1)2 n ∈ Z+

= {{1, 2, 3} , {4, 5, 6, 7, 8} {9, 10, 11, 12, 13, 14, 15} , {16, 17, 18, 19, 20, 21, 22, 23, 24} , . . .}  218

Matem´ atica Discreta Ejemplo 8.14

Francisco Jos´e Gonz´ alez Guti´errez

Dado A = R2 , sea R la siguiente relaci´on en A, (x1 , y1 )R(x2 , y2 ) ⇐⇒ x1 = x2

(a) Verificar que es una relaci´ on de equivalencia. (b) Describir geom´etricamente las clases de equivalencia y el conjunto cociente que la relaci´on R determina en el conjunto A. Soluci´on (a) Veamos que es una relaci´ on de equivalencia. Reflexiva. Para todo (x, y) ∈ R2 , se verifica que x = x luego (x, y)R(x, y). Sim´etrica. Dados dos puntos cualesquiera de R2 , se verifica que: (x1 , y1 )R(x2 , y2 ) ⇐⇒ x1 = x2 =⇒ x2 = x1 ⇐⇒ (x2 , y2 )R(x1 , y1 ) Transitiva. Para cada terna de puntos de R2 , se verifica: ) (x1 , y1 )R(x2 , y2 ) ⇐⇒ x1 = x2 =⇒ x1 = x3 ⇐⇒ (x1 , y1 )R(x3 , y3 ) (x2 , y2 )R(x3 , y3 ) ⇐⇒ x2 = x3 (b) Estudiemos las clases de equivalencia y el conjunto cociente. Si (a, b) es cualquier punto de R2 , entonces  [(a, b)] = (x, y) ∈ R2 : (x, y)R(a, b) luego, (x, y) ∈ [(a, b)] ⇐⇒ (x, y)R(a, b) ⇐⇒ x = a de aqu´ı que  [(a, b)] = (x, y) ∈ R2 : x = a es decir, la clase de equivalencia de un punto (a, b) es el conjunto formado por todos los puntos del plano cuya primera componente es igual a a, o lo que es igual la recta paralela al eje de ordenadas x = a. El conjunto cociente ser´ a R2 /R = {x = a : a ∈ R} es decir el plano queda partido en rectas paralelas al eje de ordenadas. Ejemplo 8.15

En R se considera la siguiente relaci´on:  x = y  ´o xRy ⇐⇒  x+y = 3

(a) Probar que R es una relaci´ on de equivalencia. (b) Calcular la clase de equivalencia de 113. (c) Calcular la clase de equivalencia de un elemento x. Soluci´on 219



Universidad de C´ adiz

Departamento de Matem´ aticas

(a) Veamos si es de equivalencia. Reflexiva. Dado cualquier n´ umero real x, se verifica que x = x, luego xRx. Sim´etrica. Dados dos n´ umeros reales cualesquiera, x e y, se tiene      x=y   y=x  ∨ ∨ xRy ⇐⇒ ⇐⇒ ⇐⇒ yRx     x+y =3 y+x=3 Transitiva. Si x, y, z son tres n´ umeros reales arbitrarios. Entonces, (xRy) ∧ (yRz)

=⇒

[(x = y) ∨ (x + y = 3)] ∧ [(y = z) ∨ (y + z = 3)]

=⇒

[((x = y) ∨ (x + y = 3)) ∧ (y = z)] ∨ [((x = y) ∨ (x + y = 3)) ∧ (y + z = 3)]

=⇒

[((x = y) ∧ (y = z)) ∨ ((x + y = 3) ∧ (y = z))] ∨ [((x = y) ∧ (y + z = 3)) ∨ ((x + y = 3) ∧ (y + z = 3))]

⇐⇒

[(x = z) ∨ (x + z = 3)] ∨ [(x + z = 3) ∨ (x = z)]

=⇒

(x = z) ∨ (x + z = 3)

⇐⇒

xRz

(b) En general, [a] = {x ∈ R : xRa} luego,   x=a ∨ x ∈ [a] ⇐⇒ xRa ⇐⇒  x + a = 3 =⇒ x = 3 − a es decir, [a] = {x ∈ R : x = a ∨ x + a = 3} = {a, 3 − a} de aqu´ı que [113] = {−110, 113} (c) Del apartado anterior [x] = {x, 3 − x}  Ejemplo 8.16 En el conjunto A = {1, 2, 3, . . . . . . , q}, siendo q un n´ umero entero positivo, se define la siguiente relaci´ on: aRb ⇐⇒ m.c.d.(a, p) = m.c.d.(b, p) Para cada a, b de A y p ∈ Z+ . (a) Probar que R es una relaci´ on de equivalencia. (b) Calcular el conjunto cociente que la relaci´on R determina sobre A para q = 7 y p = 18. Soluci´on (a) Dado que la relaci´ on R viene caracterizada por una igualdad, ser´a reflexiva, sim´etrica y transitiva, por tanto, es de equivalencia. 220

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

(b) Calculamos el conjunto cociente cuando A = {1, 2, 3, 4, 5, 6, 7} y aRb ⇐⇒ m.c.d.(a, 18) = m.c.d(b, 18). Por definici´ on, A/R = {[a] : a ∈ A} y [a] = {x ∈ A : xRa} luego, x ∈ [a] ⇐⇒ xRa ⇐⇒ m.c.d.(x, 18) = m.c.d.(a, 18) de aqu´ı que [a] = {x ∈ A : m.c.d.(x, 18) = m.c.d.(a, 18)} . Entonces, [1] =

{x ∈ A : m.c.d.(x, 18) = m.c.d.(1, 18)} = {x ∈ A : m.c.d.(x, 18) = 1} = {1, 5, 7}

[2] =

{x ∈ A : m.c.d.(x, 18) = m.c.d.(2, 18)} = {x ∈ A : m.c.d.(x, 18) = 2} = {2, 4}

[3] =

{x ∈ A : m.c.d.(x, 18) = m.c.d.(3, 18)} = {x ∈ A : m.c.d.(x, 18) = 3} = {3}

[4] =

[2]

[5] =

[1]

[6] =

{x ∈ A : m.c.d.(x, 18) = m.c.d.(6, 18)} = {x ∈ A : m.c.d.(x, 18) = 1} = {6}

[7] =

[1]

Por tanto, A/R = {[1] , [2] , [3] , [6]} = {{1, 5, 7} , {2, 4} , {3} , {6}} 

Ejemplo 8.17

En R \ {0}, se define la relaci´on: aRb ⇐⇒ a +

1 1 =b+ a b

¿De qu´e tipo de relaci´ on se trata? Soluci´on Dado que la relaci´ on viene caracterizada a trav´es de una igualdad, ser´a reflexiva, sim´etrica y transitiva, luego es de equivalencia. Clases de equivalencia. Sea a cualquiera de R \ {0}, entonces [a] = {x ∈ R \ {0} : xRa} 221

Universidad de C´ adiz

Departamento de Matem´ aticas

luego, x ∈ [a] ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒ ⇐⇒

⇐⇒

⇐⇒

xRa 1 1 =a+ x a 1 1 x−a+ − =0 x a x−a x−a− =0 ax   1 (x − a) 1 − =0 ax  x=a     ∨     1− 1 =0 ax  x = a     ∨     x= 1 a x+

Consecuentemente,  [a] =

1 ,a a



Conjunto cociente. (R \ {0}) /R = {[a] : a ∈ R \ {0}} Obs´ervese que ∀a ∈ R, se verifica que [a] =

  1 1 y = [−1, 0) ∪ (0, 1] a a

luego en este intervalo hay un representante de cada clase, de aqu´ı que (R \ {0}) /R = {[a] : a ∈ [−1, 0) ∪ (0, 1]}  Ejemplo 8.18

En el conjunto A = {12, 52, 16, 17, 26, 29, 47, 35, 53} se define la relaci´on: aRb ⇐⇒ la suma de las cifras de a es igual a la suma de las cifras de b

siendo a y b elementos arbitrarios de A. Estudiar la relaci´on. Soluci´on Dado que la relaci´ on est´ a definida por una igualdad, ser´a reflexiva, sim´etrica y transitiva, por tanto es de equivalencia. Veamos el conjunto cociente. A/R = {[a] : a ∈ R} 222

Matem´ atica Discreta

Francisco Jos´e Gonz´ alez Guti´errez

Los resultados que dan la suma de las diferentes cifras de los n´ umeros de A, son: 1+2=3 5+2=7 1+6=7 1+7=8 2+6=8 2 + 9 = 11 4 + 7 = 11 3+5=8 5+3=8 habr´a, por tanto, cuatro clases de equivalencia: [12] [52] = [16] [17] = [26] = [35] = [53] [29] = [47] y el conjunto cociente ser´ a: A/R

= {[12] , [52] , [17] , [29]} = {{12} , {16, 52} , {17, 26, 35, 53} , {29, 47}} 

223