martes, 6 de diciembre de 2011



5.3 Relaciones De Equivalencia

(Cerraduras,

Clases De Equivalencia y Particiones)





Cerradura de una relación                  
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 = ref( 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 = ref( R )

La cerradura reflexiva y la cerradura simétrica de una relación es muy simple de encontrar, solamente se le agregan los pares necesarios de una forma directa. Cuando conocemos la matriz asociada a la relación, la forma de encontrar las cerraduras anteriores es muy simple.

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 se pueden obtener mediante las matrices siguientes
Mref(R) = MR  In, donde In es la matriz identidad de orden |A|.
Msim(R) = [a ij], donde a ji = 1 si a ij = 1 en MR.

La Matriz identidad In de orden n es:

{$ {(1,…,0), (vdots, ddots, vdots), (0,…,1)] $}

O sea que para lograr la cerradura reflexiva debemos agregar 1s en la diagonal, para la cerradura simétrica debemos agregar 1s en luagres simétricos a la diagonal principal donde existan 1s.

Cierre de equivalencia

Para calcular el cierre de equivalencia de una relación binaria R sobre un conjunto A:

Calcularemos primero su cierre reexivo, ρ(R)

Sobre el resultado calcularemos el cierre simétrico, σ(ρ(R))

nalmente el cierre transitivo del resultado anterior, τ (σ(ρ(R)))



Clases de Equivalencia


Al conjunto de los elementos del conjunto A que están relacionados con él se llama clase de equivalencia. 


Ejemplo:

La relación a - b = 2.k (múltiplo de 2), siendo a y b números enteros es una relación de equivalencia porque cumple las propiedades: Reflexiva: a - a = 0 = 2.k (k = 0). Simétrica: a - b = b - a porque b - a  = -(a - b). Si a - b es múltiplo de 2, -(a - b) también lo será. Transitiva: a - b = 2.k1   b - c = 2.k2  Sumando queda a - c = 2.k3 Entonces a - c es múltiplo de 2. 

En el ejemplo anterior, la clase de equivalencia del número cero (uno de los elementos del conjunto de los números enteros)  C(0) = {... -4, -2, 0, 2, 4, ...}, pues 0 - (-4) es múltiplo de 2, 0 - (-2) es múltiplo de 2 ya sí sucesivamente. La clase de equivalencia del número 1 será C(1) = {... -5, -3, -1, 1, 3, 5, ...} pues la diferencia entre 1 y los números indicados es múltiplo de 2. 

Del mismo modo podríamos calcular las clases de equivalencia de más números. 


El conjunto formado por las clases de equivalencia se llama conjunto cociente.


En el ejemplo anterior el conjunto cociente Z / 2 es el conjunto formado por las clases de todos los elementos Z / 2 = {C(0), C(1), C(2), ... }.



Particiones

Sea X un conjunto. P es una partición de X si y sólo si:

 
Los conjuntos de P son disyuntos 2 a 2, es decir, si  y entonces                                                                                                              

Observe que si P es una partición de X, entonces todo elemento de X está en uno y sólo un elementouno y sólo un elemento de modo que   parte a   en conjuntos disyuntos. Por ejemplo, el conjunto de barriles propuesto al comienzo de la sección es una partición del conjunto de mangos. Otro ejemplo de una partición es de la división política de un país: El país (visto como un conjunto de personas) se parte en estados o departamentos no vacíos disyuntos entre sí.
Ejemplo

   Sea ={1, 2, 3, 4, 5, 6, 7, 8, 9}
Entonces = {{1, 9}, {2, 8}, {3, 4, 5, 6, 7}}  
Es una partición de X en tres conjuntos: elementos externos (1,9), elementos semi-externos (2, 8) y elementos internos (3, 4, 5, 6, 7). 
Note que Q = {{1, 2, 9}, {2, 8}, {3, 4, 5, 6, 7}} no es partición de X 
(¿por qué?).

Como lo habíamos insinuado, resulta que toda relación de equivalencia determina de manera natural una partición.










1 comentario:

  1. Que pedo con tu "No hay comentarios: publicar un comentario en la entrada", o sea, el usuario que vera en esta pagina va a publicar sus dudas con el tema. Que oso contigo jajajajajaaj

    ResponderEliminar