2.7 Relaciones de equivalencia

 Relaciones de equivalencia

(Cerraduras, Clases de equivalencia, Particiones):

Definición.- Una relación R en un conjunto A es de equivalencia si cumple las propiedades reflexiva, simétrica y transitiva.   

Teorema.- Si R es una relación de equivalencia en un conjunto de A entonces R particiona al conjunto A en  subconjuntos disjuntos llamados clases de equivalencia     

Una partición de un conjunto está formada por subconjuntos disjuntos o sea ningún elemento aparece en dos conjuntos tal que la unión es igual al conjunto original.     

Una relación de equivalencia sobre un conjunto C es una relación R que cumple las siguientes propiedades:           

Reflexiva. ∀a ∈ C; a R a  

Simétrica. ∀a, b ∈ C; a R b ⇔ b R a       

Transitiva. ∀a, b, c ∈ C; (a R b) ∧ (b R c) ⇒ (a R c) 

Cerradura

En algunas ocasiones una relación no cumple alguna de las propiedades de equivalencia, pero hay relaciones que la incluyen y que si cumplen la propiedad. de todas las relaciones la menor posible se llama Cerradura.   

Definición.- Sea R una relación en un conjunto A.  

Una cerradura reflexiva ref(R) de R en A es la "menor" relación que la incluye y que es reflexiva, con símbolos:  (≤R' reflexiva) (A ≤ R'  ≤ ref(R)) ⇒ R' = ref(R))           

Una cerradura simétrica sim(R) de R en A es la "menor" relación que la incluye y que es simétrica  con símbolos:  (∀R' reflexiva) (A ≤ R'  ≤ ref(R)) ⇒ R' = sim(R))         

Una cerradura transitiva trans(R) de R en A es la "menor" relación que la incluye y que es transitiva, con símbolos:  (∀R' reflexiva) (A ≤ R'  ≤ ref(R)) ⇒ R' = trans(R))    

Teorema: Sea R una relación en A y MR su matriz asociada. La cerradura reflexiva y la cerradura simétrica de R son únicas y pueden obtener mediante las matrices siguientes Mref(R) MRUIn, donde In es la matriz identidad de orden │A│.     

Msim(R) = [aij], donde aji = 1 si aji = 1 en MR