Facultad de Ingeniería de Sistemas

Matemática Discreta

Ejemplo
Es sencillo verificar que la relación R = {(a,a), (b,b), (c,c)} sobre X = {a,b,c} es reflexiva,
simétrica y transitiva. Así, R es una relación de equivalencia. Las clases de equivalencia son
[a]={a}, [b]={b}, [c]={c}.

Ejemplo
Sea X ={ 1,2,…;10}. Definimos x R y para indicar que 3 divide a x – y. Es sencillo verificar que la
relación R es reflexiva, simétrica y transitiva. Así, R es una relación de equivalencia sobre X.
Se determinarán los miembros de las clases de equivalencia. La clase de equivalencia [1] consiste
en todas las x con x R 1. Entonces 1 = {x є X |divide x-1 } = { 1,4,7,10 }.
De manera similar, [2] = { 2, 5, 8 }, [3] = { 3, 6, 9 }. Estos tres conjuntos son una partición de X.
Observe que [1]= [4]= [7]= [10], [2]= [5]=[8], [3]=[6]=[9]. Para esta relación, equivalencia
es “tiene el mismo residuo al dividir entre 3”.
Esta sección se cierra con la prueba de un resultado especial que se necesitará más adelante. La
prueba se ilustra en la figura
X
X1 X2 Xk
|X|= rk ….….. (r elementos)
(r elementos) (r elementos)del Teorema
Prueba
|X|= rk
Prueba del Teorema

Teorema
Sea R una relación de equivalencia en un conjunto finito X. Si cada clase de equivalencia tiene r
elementos, existen |X|/r clases de equivalencia.
Demostración: Sean X1 , X2 , ….., Xk las distintas clases de equivalencia. Como estos conjuntos
hacen una partición de X.
|X|= |X1|+ |X2|+ …. + |Xk|= r + r +…… + r = kr y se deriva la conclusión.
Sugerencias para resolver problemas
Una relación de equivalencia es una relación reflexiva, simétrica y transitiva. Para probar que una
relación es de equivalencia, es necesario verificar que estas tres propiedades se cumplen. Una
relación de equivalencia en un conjunto X crea una partición de X en subconjuntos (“Crear una
partición” significa que cada x en X pertenece a exactamente uno de los subconjuntos de la
partición.) Los subconjuntos que forman la partición se determinan de la siguiente manera. Elija x 1
є X. Encuentre el conjunto, denotado por [x 1], de todos los elementos relacionados con x1. Elija
otro elemento x2 є X que no esté relacionado con x 1. Encuentre el conjunto [x2] de todos los
elementos relacionados con x2. Continúe de esta forma hasta que todos los elementos de X estén
asignados a un conjunto. Los conjuntos [x1] se llaman clases de equivalencia. La partición es [x 1],
[x2], …
Los elementos de [xi.] son equivalentes en el sentido de que todos están relacionados. Por ejemplo,
la relación R, definida por x R y si x y y son del mismo color, particiona el conjunto en
subconjuntos donde cada subconjunto contiene los elementos que son todos del mismo color.
Dentro de un subconjunto, los elementos son equivalentes en el sentido de que todos son de mismo
color.

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

 Facultad de Ingeniería de Sistemas
Matemática Discreta

En la digráfica de una relación equivalente, una clase de equivalencia es la subgráfica más grande
de la digráfica original que tiene la propiedad de que para cualesquiera vértices v y w en G, existe
una arista dirigida de v a w.
Una partición de un conjunto da lugar a una relación de equivalencia. Si x 1, …, xn es una partición
del conjunto X y se define x R y si para alguna i, x y y pertenecen ambos a x i, entonces R es una
relación de equivalencia sobre X. Las clases de equivalencia resultan ser x 1 , …., xn. Así, “relación
de equivalencia” y “partición de un conjunto” son diferentes puntos de vista de la misma
situación. Una relación de equivalencia sobre X da lugar a una partición, y una partición de X da
lugar a una relación de equivalencia.

Ejercicios
En los ejercicios 1 al 8, determine si la relación indicada es una relación de equivalencia en { 1, 2,
3, 4, 5}. Si la relación es una relación de equivalencia. (En los ejercicios 5 al 8, { 1, 2, 3, 4, 5 }.)
1. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1) }
2. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1), (3,4), (4,3) }
3. { (1,1), (2,2), (3,3), (4,4) }
4. { (1,1), (2,2), (3,3), (4,4), (5,5), (1,5), (5,1), (3,5), (5,3), (1,3), (3,1) }
5. { (x,y) |1≤x≤5 y 1≤y≤5 }
6. { (x,y) |4 divide a x-y }
7. { (x,y) |3 divide a x+y }
8. { (x,y) |x divide a 2-y }
En los ejercicios 9 al 14, determine si la relación indicada es una relación de equivalencia en el
conjunto de todas las personas.
9. { (x,y) |x y y son de la misma altura }
10. { (x,y) |x y y en algún momento han vivido en el mismo país }
11. { (x,y) |x y y son tienen el mismo nombre }
12. { (x,y) |x es más alto que y }
13. { (x,y) |x y y tienen los mismos padres }
14. { (x,y) |x y y tienen el mismo color de pelo }
En los ejercicios 15 al 20, liste los miembros de la relación de equivalencia en { 1, 2, 3, 4 }
definida por la partición dada. Además, encuentre las clases de equivalencia [1],[2],[3] y [4].
15. { { 1,2}, {3,4} }
16. { {1}, {2}, {3,4} }
17. { {1}, {2}, {3}, {4} }
18. { {1,2,3}, {4} }
19. { {1,2,3,4} }
20. { {1}, {2,4}, {3} }
En los ejercicios 21 al 23, sea X={1,2,3,4,5}, Y={3,4} y C={1,3}. Defina la relación R en P(X), el
conjunto de todos los subconjuntos de X, como A R B si A U Y = B U Y.
21. Demuestre que R es una relación de equivalencia.
22. Liste los elementos de [C], la clase de equivalencia que contiene a C.
23. ¿Cuántas clases de equivalencia diferentes hay ?
24. Sea X = { San Francisco, Pittsburg, Chicago, San Diego, Filadelfia, Los Ángeles }. Defina una
relación R sobre X como x R y si x y y están en el mismo estado.
a) Demuestre que R es una relación de equivalencia.

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

 Facultad de Ingeniería de Sistemas
Matemática Discreta

b) Liste las clases de equivalencia de X.

c) Demuestre que si R es una relación de equivalencia sobre X, entonces dominio R = rango R = X.
25. Si una relación de equivalencia tiene sólo una clase de equivalencia, ¿Cómo debe verse la
relación?
26. Si R es una relación de equivalencia en un conjunto X y [X] = [R], ¿Cómo debe verse la
relación?
27. Listando los pares ordenados, dé un ejemplo de una relación de equivalencia en {1,2,3,4,5,6}
que tiene exactamente cuatro clases de equivalencia.
28. ¿Cuántas relaciones de equivalencia hay en el conjunto {1,2,3}?
29. Sea X = {1,2, …, 10}. Defina una relación R sobre X x X como (a,b) R (c,d) si a + d = b + c.
a) Demuestre que R es una relación de equivalencia sobre X x X.
b) Liste un miembro de cada clase de equivalencia en X x X.
30. Sea X = {1,2, …, 10}. Defina una relación R sobre X x X como (a,b) R (c,d) si ad = bc.
a) Demuestre que R es una relación de equivalencia sobre X x X.
b) Liste un miembro de cada clase de equivalencia en X x X.
c) Describa la relación R en términos familiares.
31. Sea R una relación reflexiva y transitiva sobre X. Demuestre que R ∩ R-1 es una relación de
equivalencia sobre X.
32. Sean R1 Y R2 relaciones de equivalencia sobre X.
a) Demuestre que R1 ∩ R2 es una relación de equivalencia sobre X.
b) Describa las clases de equivalencia de R1 ∩ R2 en términos de las clases de equivalencia de R 1 y
las clases de equivalencia de R2.
33. Suponga que S es una colección de subconjuntos de un conjunto X y X = U S. (No se supone
que la familia S sea disjunta por pares). Defina x R y de manera que para algún conjunto S є S,
ambas x y y están en S. ¿Es R necesariamente reflexiva, simétrica y transitiva?
34. Sea S un cuadrado unitario que incluye el interior, como se muestra en la figura que sigue.
y

(0,1) (1,1)
S

x
(0,0) (1,0)
35. Defina la relación R en S por (x,y) R (x’, y’) si (x = x’ y y = y’) o (y = y’ y x= 0 y x’ = 1) o (y =
y’ y x= 1 y x’ = 0).
a) Demuestre que R es una relación de equivalencia en S.
b)Si los puntos en la misma clase de equivalencia se engomaran, ¿cómo describiría la figura que
se forma?

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

 Facultad de Ingeniería de Sistemas
Matemática Discreta

36. Sea S un cuadrado unitario que incluye el interior (como en el ejercicio 35). Defina una
relación R’ en S por (x,y) R’ (x’,y’) si (x = x’ y y = y’) o (y = y’ y x= 0 y x’ = 1) o (y = y’ y x= 1 y
x’ =0) o (x = x’ y y= 0 y y’ = 1) o (x = x’ y y= 1 y y’ =0). Sea
R = R’ U {((0,0), (1,1)), ((0,1), (1,0)), ((1,0), (0,1)), ((1,1), (0,0))}
a) Demuestre que R es una relación de equivalencia en S.
b) Si los puntos en la misma clase de equivalencia se engomaran, ¿cómo describiría la figura que
se forma?
37. Sea f una función de X a Y. Defina una relación R sobre X por x R y si f(x) = f(y). Demuestre
que R es una relación de equivalencia sobre X.
38. Sea f una función característica en X. Defina la relación R sobre X por x R y si f(x) = f(y). De
acuerdo con el ejercicio anterior, R es una relación de equivalencia. ¿Cuáles son las clases de
equivalencia?
39. Sea f una función de X a Y. Sea S = { f -1({y}) | y є Y }. Demuestre que S es una partición de X.
Describa una relación una relación de equivalencia que dé lugar a esta partición.
40. Sea R una relación de equivalencia en un conjunto A. Defina una función f de A al conjunto de
clases de equivalencia de A mediante la regla f(x) = [x]. ¿Cuándo se tiene f(x) = f(y)?
41. Sea R una relación de equivalencia en el conjunto A. Suponga que g es una función de A a un
conjunto X que tiene la propiedad de que si x R y, entonces g(x) = g(y). Demuestre que h([x]) =
g(x) define una función del conjunto de clases de equivalencia de A a X. [ Lo que debe probarse es
que h asigna de manera única un valor a [x]; es decir, si [x] = [y], entonces g(x) = g(y)].
42. Sea X el conjunto de sucesiones con dominio finito. Define una relación R sobre X como s R t
si |dominio s|= |dominio t| y, si el dominio de s es { m, m+1, …., m+k} y el dominio de t es { n,
n+1, .., n+k }, sm+i=tn+i para i=0, … , k.
a) Demuestre que R es una relación de equivalencia.
b) Explique en palabras que significa que dos sucesiones en X sean equivalentes bajo la relación R.
c) Como una sucesión es una función, una sucesión es un conjunto de pares ordenados. Dos
sucesiones son iguales si los dos conjuntos de pares ordenados son iguales. Compare las
diferencias entre las dos sucesiones equivalentes en X y las dos sucesiones iguales en X.
Sea R una relación en un conjunto X. Defina
ρ(R) = R U { (X,X) | x є X}
σ(R) = R U R-1
Rn = R o R o R o…o R (nR’s)
τ(R) = U { Rn | n = 1, 2,….}.
La relación τ(R) se llama cerredura transitiva de R.
43. Para las relaciones R1 y R2 del ejercicio 38, sección 3.1, encuentre ρ(R i), σ(Ri), τ(Ri), y
τ(σ(ρ(Ri))) para i = 1, 2.
44. Demuestre que ρ(R) es reflexiva.
45. Demuestre que σ(R) es simétrica.
46. Demuestre que τ(R) es transitiva.
47. Demuestre que τ(σ(ρ(R))) es una relación de equivalencia que contiene a R.
48. Demuestre que τ(σ(ρ(R))) es la relación de equivalencia más pequeña sobre X que contiene a
R; es decir, demuestre que si R’ es una relación de equivalencia sobre X y R’ es una relación de
equivalencia sobre X y R’ ⊇ R, entonces R’ ⊇ τ(σ(ρ(R))).
Rincón de solución de problemas – Relaciones de equivalencia
Problema

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

 Facultad de Ingeniería de Sistemas
Matemática Discreta

Responda a las siguientes preguntas para la relación R definida sobre el conjunto de cadenas de 8
bits por s1 R s2 , siempre que los primeros 4 bits de s1 y s2 coincidan.
a) Demuestre que R es una relación de equivalencia.
b) Liste un miembro de cada clase de equivalencia.
c) ¿Cuántas clases de equivalencia hay?
Resumen de la técnicas de solución de problemas
 Liste los elementos que están relacionados.
 Calcule algunas clases de equivalencia, es decir, liste todos los elementos relacionados con
un elemento específico.
 Resulta útil resolver los incisos de un problema en un orden diferente que el indicado en el
enunciado del problema.
 Para demostrar que una relación específica R es una relación de equivalencia, vaya a las
definiciones. Pruebe que R es reflexiva, simétrica y transitiva verificando directamente que
R satisface la definición de éstas.
 Si el problema es contar el número de elementos que satisfacen alguna propiedad y el
número es suficientemente pequeño, basta dar una lista de los elementos y contarlos.
Solución:
a) Se cumple que R es reflexiva, transitiva y simétrica por lo tanto es una relación de equivalencia.
b)
00000000 00010000 00100000 00110000
01000000 01010000 01100000 01110000
10000000 10010000 10100000 10110000
11000000 11010000 11100000 11110000
es una lista con un miembro de cada clase de equivalencia.
c) Existen 16 clases de equivalencia.
Matrices de relaciones
Una matriz es una manera conveniente de representar una relación R de X a Y. Se puede usar en la
computadora para analizar una relación. Se etiquetan los renglones con elementos X, y se
etiquetan las columnas con elementos de Y. El elemnto en el renglón x y la columna y se hace igual
a 1 si xRy, y a 0 de otra manera, llamándose matriz de relación R (relativa al orden de X y Y).

Ejemplo
La matriz de la relación R = { (1,b), (1,d), (2,c), (3,c), (3,b), (4,a) } de X= {1, 2, 3, 4} a Y= {a, b, c,
d} respecto a los órdenes 1, 2, 3, 4 y a, b, c, d es
a b c d
1 0 1 0 1

(
2 0 0 1 0
3 0 1 1 0
4 1 0 0 0
)
Ejemplo
La matriz de la relación R del ejemplo 3.3.1 relativa a los órdenes 2, 3, 4, 1 y d, b, a, c es

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa

 Facultad de Ingeniería de Sistemas
Matemática Discreta

d b a c
2 0 0 0 1

(
3 0 1 0 1
4 0 0 1 0
1 1 1 0 0
)
Es evidente que la matríz de una relación de X a Y es dependiente de los órdenes de X y Y.

Julián Sotomayor Isaí Flores Javier Díaz Percy Figueroa