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, liste las clases de equivalencia. (En los ejercicios 5 al 8,
x, y ∈ {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 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 (como en el teorema 3.2.1) 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 ∪ Y = B ∪ 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.
b) Liste las clases de equivalencia de X.
25. Demuestre que si R es una relación de equivalencia sobre X, entonces
dominio R = rango R = X.
26. Si una relación de equivalencia tiene sólo una clase de equivalencia,
¿cómo debe verse la relación?
27. Si R es una relación de equivalencia en un conjunto X y |X| =
|R|, ¿Cómo debe verse la relación?
28. 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.
29. ¿Cuántas relaciones de equivalencia hay en el conjunto {1, 2, 3}?
30. Sea X = {1,2, . . . , 10}. Defina una relación R sobre 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.
b) Liste un miembro de cada clase de equivalencia en X × X.
31. Sea X = {1,2, . . . , 10}. Defina una relación R sobre X × X como
(a, b) R (c, d) si ad = bc.
a) Demuestre que R es una relación de equivalencia sobre X × X.
b) Liste un miembro de cada clase de equivalencia en X × X.
c) Describa la relación R en términos familiares.
32. Sea R una relación reflexiva y transitiva sobre X. Demuestre que
R ∩ R−1 es una relación de equivalencia sobre X.
33. 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 R1 y las clases de equivalencia de R2.
34. Suponga que S es una colección de subconjuntos de un conjunto
X y X = ∪ 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?
35. Sea S un cuadrado unitario que incluye el interior, como se muestra
en la figura que sigue.
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?
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 ∪ {((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,
¿como 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. (La “función característica” se
definió en el ejercicio 62, sección 2.2). 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 }.
[La definición de f−1(B), donde B es un conjunto, precede al ejercicio
57, sección 2.2]. Demuestre que S es una partición de X. Describa
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 un 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. Defina 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 qué 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 ∪ {(x, x) | x ∈ X}
σ(R) = R ∪ R−1
Rn = R ◦ R ◦ R ◦ · · · ◦ R (nR’s)
τ (R) = ∪{Rn | n = 1, 2, . . .}.
La relación τ(R) se llama cerradura transitiva de R.
ρ(Ri ), σ(Ri ), τ (Ri ), y τ (σ(ρ(Ri ))) para i = 1, 2.
44. Demuestre que ρ (R) es reflexiva.
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 ⊇ R, entonces R ⊇ τ (σ(ρ(R)))
49. Demuestre que R es transitiva si y sólo si τ(R) = R.
En los ejercicios 50 al 56, si la afirmación es verdadera para todas las
relaciones R1 y R2 en un conjunto arbitrario X, demuéstrelo; de otra
manera dé un contraejemplo.
50. ρ(R1 ∪ R2) = ρ(R1) ∪ ρ(R2)
51. σ(R1 ∩ R2) = σ(R1) ∩ σ(R2)
52. τ (R1 ∪ R2) = τ (R1) ∪ τ (R2)
53. τ (R1 ∩ R2) = τ (R1) ∩ τ (R2)
54. σ(τ (R1)) = τ (σ(R1))
56. ρ(τ (R1)) = τ (ρ(R1))
Si X y Y son conjuntos, se define X como equivalente a Y si existe una
función uno a uno, sobre de X a Y.
57. Demuestre que la equivalencia de conjuntos es una relación de
equivalencia.
58. Si X y Y son conjuntos finitos y X es equivalente a Y, ¿qué indica
acerca de X y Y?
60. Demuestre que para cualquier conjunto X, X no es equivalente a
P(X), el conjunto potencia de X.
