Lectura 25 - Relaciones de Equivalencia

Relaciones de equivalencia
Definición. Una relación R sobre un conjunto A que satisface las siguientes propiedades:
1. Reflexividad
2. Simetría
3. Transitividad
se llama relación de equivalencia sobre el conjunto A.
Definición. Si R es una relación de equivalencia sobre un conjunto A y a ∈ A, entonces el conjunto

definido como:
[a] = {x ∈ A : (a, x) ∈ R}
se le llama clase de equivalencia de a.
👨🏫 En palabras, este es el conjunto de todos los elementos en A que están relacionados con a.
Ejemplo 1. Sean X = {a, b, c, d} e Y = {a, d} conjuntos y R una relación de equivalencia sobre el

conjunto P(X) tal que:
R = {(A, B) : A ⋂ Y = B ⋂ Y}
a) ¿La pareja ({a, c}, {a, c, d}) ∈ R?
Hacemos {a, c} ⋂ Y = {a} & {a, c, d} ⋂ Y = {a, d} ∴ ({a, c}, {a, c, d}) ∉ R
b) ¿La pareja (Ø, {b, c}) ∈ R?
Hacemos Ø ⋂ Y = Ø & {b, c} ⋂ Y = Ø ∴ (Ø, {b, c}) ∈ R
c) Liste los elementos en la clase de equivalencia de {b,c,d}.
Primero, {b,c,d} ⋂ Y = {d}
Entonces, [{b,c,d}] = {{d}, {b,d}, {c,d}, {b,c,d}}
👨🏫 La clase de equivalencia del conjunto {b,c,d} tiene a todos los conjuntos que tienen en común el elemento d con el
conjunto Y.
⚠ Todo elemento pertenece a su propia clase de equivalencia (ver el conjunto en azul).
d) Liste los elementos en las clases de equivalencia de Ø, {a} & {a,d}.
Hacemos Ø ⋂ Y = Ø, {a} ⋂ Y = {a} & {a,d} ⋂ Y = {a,d}. Entonces:
[Ø] = {Ø, {b},{c},{b,c}}

[{a}] = {{a},{a,b},{a,c},{a,b,c}}
[{a,d}] = {{a,d},{a,b,d},{a,c,d},{a,b,c,d}}
Ejemplo 2. Sea R una relación sobre ℕ × ℕ tal que:
R = {((a,b), (c,d)) : a + d = b + c}
Demuestre que R es una relación de equivalencia.
Reflexividad:
Sea (a,b) ∈ ℕ × ℕ. Luego, a + b = a + b → ((a,b), (a,b)) ∈ R ∴ R es reflexiva
Simetría:
Sean (a,b), (c,d) ∈ ℕ × ℕ tales que ((a,b), (c,d)) ∈ R → a + d = b + c → b + c = a + d → c + b = d + a →
((c,d), (a,b)) ∈ R ∴ R es simétrica
Transitividad:
Sean (a,b), (c,d), (e, f ) ∈ ℕ × ℕ tales que ((a,b), (c,d)) ∈ R & ((c,d), (e,f )) ∈ R.
Entonces, a + d = b + c & c + f = d + e.
Luego, sumamos ambas ecuaciones: a + d + c + f = b + c + d + e → a + f = b + e → ((a,b), (e,f )) ∈ R.
∴ R es transitiva. □
Definición. Sea A un conjunto y R una relación de equivalencia sobre A. Al conjunto de todas las clases
de equivalencia del conjunto A se le llama conjunto cociente, el cual se denota como A/R.
Ejemplo 3. Para la relación de equivalencia del Ejemplo 1, el conjunto cociente es:
P(X)/R = {[Ø], [{a}], [{d}], [{a,d}]
Ejemplo 4. Para la relación de equivalencia del Ejemplo 2:
a) Escriba algunos elementos de las siguientes clases de equivalencia:
[(0, 2)] = {(0, 2), (1, 3), (2, 4),...}

[(0, 1)] = {(0, 1), (1, 2), (2, 3),...}
[(0, 0)] = {(0, 0), (3, 3), (2, 2),...}
[(1, 0)] = {(1, 0), (2, 1), (5, 4),...}
[(2, 0)] = {(2, 0), (3, 1), (7, 5),...}
b) Liste algunos elementos del conjunto cociente ℕ × ℕ / R:
ℕ × ℕ / R = {..., [(0, 2)], [(0, 1)], [(0, 0)], [(1, 0)], [(2, 0)], ...}
Se propone usar una simbología diferente para representar las clases de equivalencia:
-2 = [(0, 2)] = {(0, 2), (1, 3), (2, 4),...}

-1 = [(0, 1)] = {(0, 1), (1, 2), (2, 3),...}
0 = [(0, 0)] = {(0, 0), (3, 3), (2, 2),...}
1 = [(1, 0)] = {(1, 0), (2, 1), (5, 4),...}
2 = [(2, 0)] = {(2, 0), (3, 1), (7, 5),...}
🤯 Entonces, ℕ × ℕ / R = {..., -2, -1, 0, 1, 2, ...} es el conjunto de los números enteros ℤ.
Ejemplo 5. Sea R una relación sobre ℤ tal que:
R = {(x, y) : x - y es par}
a) Demuestre que R es una relación de equivalencia.
Reflexividad: Sea a ∈ ℤ. Luego, a - a = 0 = 2·0 es par → (a, a) ∈ R ∴ R es reflexiva.
Simetría: Sean a, b ∈ ℤ. Suponemos (a, b) ∈ R → a - b = 2n para algún n ∈ ℤ.

Luego, b - a = -(a - b) = -2n → (b, a) ∈ R. ∴ R es simétrica.
Transitividad: Sean a, b, c ∈ ℤ. Suponemos (a, b) ∈ R ∧ (b, c) ∈ R → a - b = 2n & b - c = 2m, n, m ∈ ℤ.

Luego, a - c = (a - b) + (b - c) = 2n + 2m = 2(n + m) = 2k, k ∈ ℤ → (a, c) ∈ R. ∴ R es transitiva.
En conclusión, R es una relación de equivalencia. □
b) Demuestre que todos los números pares pertenecen a la misma clase de equivalencia y que todos los
números impares pertenecen a la misma clase de equivalencia (distinta a la de los números pares).
Prueba:
Sean m = 2k₁ & n = 2k₂ dos números pares. Entonces m - n = 2k₁ - 2k₂ = 2(k₁ - k₂) es par, lo que significa
que (m, n) ∈ R.
Por otro lado, sean p = 2r₁ + 1 & q = 2r₂ + 1 dos números impares.
Entonces p - q = 2r₁ + 1 - (2r₂ + 1) = 2(r₁ - r₂) es par, lo que significa que (p, q) ∈ R. □
👨🏫 Esta relación divide o parte al conjunto ℤ en dos “categorías”, los números pares e impares.
Ejemplo 6. Sean X = {a, b, c, d} e Y = {a, d} conjuntos y R una relación de equivalencia sobre el conjunto
P(X) tal que:
R = {(A, B) : A ⋂ Y = B ⋂ Y}
Liste todos los elementos del conjunto P(X)/R.
P(X)/R = {Ø, [{a}], [{d}], [{a, d}]}
Definición. Sea A un conjunto y sea S una familia de subconjuntos de A:
S = {A₁, A₂, ..., An}

Si la familia de subconjuntos satisface las siguientes propiedades:
1. A₁ ⋃ A₂ ⋃ ... ⋃ An = A
2. Ai ⋂ Aj = Ø para todo i ≠ j
3. Ai ≠ Ø para todo i,
entonces se dice que S es una partición del conjunto A.
Continuación del Ejemplo 6.
Listemos los elementos de las clases de equivalencia de la relación R:
[Ø] = {Ø, {b},{c},{b,c}}

[{a}] = {{a},{a,b},{a,c},{a,b,c}}
[{d}] = {{d}, {b,d}, {c,d}, {b,c,d}}
[{a,d}] = {{a,d},{a,b,d},{a,c,d},{a,b,c,d}}
Notemos que [Ø] ⋃ [{a}] ⋃ [{d}] ⋃ [{a, d}] = P(X)
Además, [Ø] ⋂ [{a}] = Ø, [Ø] ⋂ [{d}] = Ø, [Ø] ⋂ [{a,d}] = Ø, [{a}] ⋂ [{d}] = Ø, [{a}] ⋂ [{a,d}] = Ø &
[{d}] ⋂ [{a,d}] = Ø.
Finalmente [Ø] ≠ Ø, [{a}] ≠ Ø, [{d}] ≠ Ø & [{a,d}] ≠ Ø.
En conclusión, la familia de subconjuntos de P(X) dada por {[Ø], [{a}], [{d}], [{a,d}]} es una partición
del conjunto P(X).
R to la
PIX
Decimos que la relación de Ha aa
equivalencia R induce una
partición sobre el conjunto P(X).

Lectura 25 - Relaciones de Equivalencia

Cargado por

Copyright:

Formatos disponibles

Lectura 25 - Relaciones de Equivalencia

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lectura 25 - Relaciones de Equivalencia

Cargado por

Copyright:

Formatos disponibles

Relaciones de equivalencia

Definición. Si R es una relación de equivalencia sobre un conjunto A y a ∈ A, entonces el conjunto

se le llama clase de equivalencia de a.

Ejemplo 1. Sean X = {a, b, c, d} e Y = {a, d} conjuntos y R una relación de equivalencia sobre el

a) ¿La pareja ({a, c}, {a, c, d}) ∈ R?

b) ¿La pareja (Ø, {b, c}) ∈ R?

Hacemos Ø ⋂ Y = Ø & {b, c} ⋂ Y = Ø ∴ (Ø, {b, c}) ∈ R

c) Liste los elementos en la clase de equivalencia de {b,c,d}.

Primero, {b,c,d} ⋂ Y = {d}

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

d) Liste los elementos en las clases de equivalencia de Ø, {a} & {a,d}.

Hacemos Ø ⋂ Y = Ø, {a} ⋂ Y = {a} & {a,d} ⋂ Y = {a,d}. Entonces:

[Ø] = {Ø, {b},{c},{b,c}}

Demuestre que R es una relación de equivalencia.

Luego, sumamos ambas ecuaciones: a + d + c + f = b + c + d + e → a + f = b + e → ((a,b), (e,f )) ∈ R.

Ejemplo 3. Para la relación de equivalencia del Ejemplo 1, el conjunto cociente es:

P(X)/R = {[Ø], [{a}], [{d}], [{a,d}]

Ejemplo 4. Para la relación de equivalencia del Ejemplo 2:

a) Escriba algunos elementos de las siguientes clases de equivalencia:

[(0, 2)] = {(0, 2), (1, 3), (2, 4),...}

-2 = [(0, 2)] = {(0, 2), (1, 3), (2, 4),...}

🤯 Entonces, ℕ × ℕ / R = {..., -2, -1, 0, 1, 2, ...} es el conjunto de los números enteros ℤ.

Ejemplo 5. Sea R una relación sobre ℤ tal que:

a) Demuestre que R es una relación de equivalencia.

Reflexividad: Sea a ∈ ℤ. Luego, a - a = 0 = 2·0 es par → (a, a) ∈ R ∴ R es reflexiva.

Simetría: Sean a, b ∈ ℤ. Suponemos (a, b) ∈ R → a - b = 2n para algún n ∈ ℤ.

Transitividad: Sean a, b, c ∈ ℤ. Suponemos (a, b) ∈ R ∧ (b, c) ∈ R → a - b = 2n & b - c = 2m, n, m ∈ ℤ.

En conclusión, R es una relación de equivalencia. □

Liste todos los elementos del conjunto P(X)/R.

P(X)/R = {Ø, [{a}], [{d}], [{a, d}]}

Definición. Sea A un conjunto y sea S una familia de subconjuntos de A:

S = {A₁, A₂, ..., An}

entonces se dice que S es una partición del conjunto A.

Continuación del Ejemplo 6.

Listemos los elementos de las clases de equivalencia de la relación R:

[Ø] = {Ø, {b},{c},{b,c}}

Notemos que [Ø] ⋃ [{a}] ⋃ [{d}] ⋃ [{a, d}] = P(X)

Finalmente [Ø] ≠ Ø, [{a}] ≠ Ø, [{d}] ≠ Ø & [{a,d}] ≠ Ø.

También podría gustarte