equivalencia matematicas discretas

*relaciones de equivalencia

Este tipo de relaciones binarias juegan un papel importante en todas las ciencias porque permiten clasificar
los elementos del conjunto en el que estan definidas.
Muchas veces trataremos a los elementos de un conjunto mas por sus propiedades que como objetos
individuales. En tales situaciones, podremos ignorar todas las propiedades que no sean de interes y
tratar elementos diferentes como “equivalentes” o indistinguibles, a menos que puedan diferenciarse
utilizando unicamente las propiedades que nos interesen.
La nocion de “equivalencia” tiene tres caracterısticas importantes:
1.- Todo elemento es equivalente a sı mismo. (Reflexividad).
2.- Si a es equivalente a b, entonces b es equivalente a a. (Simetrıa).
3.-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.
En definicion:
Una relacion binaria R definida sobre un conjunto A se dice que es de equivalencia cuando es reflexiva,simetrica y transitiva.relaciones equivalentes
Por ejemplo:
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.
Solucion
Reflexividad. En efecto,
(1, 1) 2 R, (2, 2) 2 R, (3, 3) 2 R y (4, 4) 2 R
luego,
8x (x 2 A =) xRx)
es decir, R es reflexiva.
Simetrıa. En efecto,
(1, 2) 2 R y (2, 1) 2 R
(3, 4) 2 R y (4, 3) 2 R
luego,
8x, y 2 A[(x, y) 2 R =) (y, x) 2 R]
es decir, la relacion propuesta es simetrica.
Transitividad. En efecto,
(1, 1) 2 R y (1, 2) 2 R =) (1, 2) 2 R
(1, 2) 2 R y (2, 1) 2 R =) (1, 1) 2 R
(1, 2) 2 R y (2, 2) 2 R =) (1, 2) 2 R
(2, 1) 2 R y (1, 1) 2 R =) (2, 1) 2 R
(2, 1) 2 R y (1, 2) 2 R =) (2, 2) 2 R
(2, 2) 2 R y (2, 1) 2 R =) (2, 1) 2 R
(3, 4) 2 R y (4, 4) 2 R =) (3, 4) 2 R
(3, 3) 2 R y (3, 4) 2 R =) (3, 4) 2 R
(4, 3) 2 R y (3, 3) 2 R =) (4, 3) 2 R
(4, 4) 2 R y (4, 3) 2 R =) (4, 3) 2 R
luego,
8x, y, z 2 A[(x, y) 2 R ^ (y, z) 2 R =) (x, z) 2 R]
y la relacion es, por tanto, transitiva.
                              

*Clases de Equivalencia y Particiones

Definicion:
Sea R una relacion de equivalencia sobre un conjunto A. Para cada a 2 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 2 A : xRa}
Observese que la clase de equivalencia de un elemento a nunca es vacıa, ya que la reflexividad de R
implica que a 2 [a].
Por ejemplo:
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.

Demostraciones:

1.-[a] = [b] si, y s´olo si aRb.
“S´olo si”. En efecto, supongamos que [a] = [b]. Como a 2 [a] y [a] = [b], entonces a 2 [b] de aqu´ı
que aRb.
“Si”. Supongamos que aRb y sea x cualquiera de A, entonces
x 2 [a] () xRa
=) xRb {Hipotesis y transitividad de R}
() x 2 [b]
tenemos, pues, que
8x 2 A(x 2 [a] =) x 2 [b])
es decir, [a] [b].
Por otra parte,
x 2 [b] () xRb
=) xRa {Simetrıa de la hipotesis y transitividad de R}
() x 2 [a]
tenemos, pues, que
8x 2 A(x 2 [b] =) x 2 [a])
es decir, [b] [a].
De la doble inclusion hallada se sigue el resultado.
2.-Si [a] 6= [b], entonces [a] \ [b] = ;
Probaremos la contrarrecıproca. Es decir,
[a] \ [b] 6= ; =) [a] = [b]
En efecto,
[a] \ [b] 6= ; =) 9x 2 A : x 2 [a] ^ x 2 [b]
() 9x 2 A : xRa ^ xRb
=) 9x 2 A : aRx ^ xRb {Simetrıa}
=) aRb {Transitividad}
() [a] = [b] {Apartado (ii)}
*ParticionesObservese 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
 Una partición de un conjunto A es una colección de subconjuntos de A, los cuales son no vacíos y disyuntos entre sí cuya unión es A. Formalmente, una partición de un conjunto A es una familia de subconjuntos no vacíos de A, con las siguientes propiedades:

Cada conjunto se llama celda o bloque de la partición.

Ejemplo:

Sea . Cada una de las siguientes colecciones son particiones de A.

• 
• 
• 
• 
• 

Ejemplo:

Cada una de los siguientes conjuntos son particiones de .

• = el conjunto de números pares, = el conjunto de números impares.
• 

La siguiente definición de clase de equivalencia, nos servirá para mostrar como las relaciones de equivalencia y las particiones son descripciones del mismo concepto.