Relaciones De Equivalencia

Relaciones de equivalencia
Las relaciones de equivalencia son un concepto matem´atico definido sobre un conjunto
dado cualquiera. Como tantos otros conceptos matem´aticos, est´a basado en una ideaintuitiva, la representaci´on de relaciones del tipo: ciudades en una misma regi´on, alumnos
de la misma clase, instrucciones dentro del mismo bloque de c´odigo, enteros con el mismo
valor dem´odulo P, etc.
Definici´on 4.2 Una relaci´on de equivalencia sobre un conjunto C es una relaci´on R
que cumple las siguientes propiedades7:
Reflexiva. ∀a ∈ C; a R a
Sim´etrica. ∀a, b ∈ C; a R b ⇔ b R aTransitiva. ∀a, b, c ∈ C; (a R b) ∧ (b R c) ⇒ (a R c)
Es f´acil comprobar estas propiedades para los ejemplos anteriores. Por ejemplo,
la propiedad reflexiva significa que una ciudad est´a en lamisma regi´on que ella misma,
¡obviamente!; la sim´etrica dir´ıa que si la ciudad a est´a en la misma regi´on que b, entonces b
est´a en la misma regi´on que a; y la transitiva, que si a est´a enmisma regi´on que b, y esta en
la misma que c, entonces a y c est´an en la misma regi´on. Las tres se cumplen de manera
trivial. En la figura 4.7 se muestra un ejemplo particular de relaci´on deequivalencia,
definida sobre un conjunto de nueve elementos.
Las relaciones de equivalencia dan lugar al concepto de clase de equivalencia.
La clase de equivalencia de un elemento a, seg´un una relaci´onR sobre un conjunto C,
es el subconjunto de todos los elementos c de C tales que c R a. Por ejemplo, en los
casos anteriores tendr´ıamos: la clase de las ciudades de la Regi´on de Murcia, la clasede los alumnos de segundo curso, etc. El conjunto de todas las clases de equivalencia
definidas sobre C seg´un la relaci´on R, forma una partici´on de ese conjunto, es decir, son
un conjunto desubconjuntos disjuntos y la uni´on de todos ellos es el conjunto de partida
C.
Nuestro inter´es, como programadores, es estudiar la implementaci´on eficiente de
relaciones de equivalencia definidas...