2.3.
1 Relaciones de equivalencia y particiones En el rea de computacin muchos algoritmos de bsqueda se basan en una tcnica que particiona de manera sucesiva un conjunto A en subconjuntos cada vez ms pequeos, haciendo que el procedimiento de bsqueda sea ms eficiente. En esta seccin estudiaremos el concepto de particin de un conjunto, y mostraremos como este concepto est ntimamente ligado al de relacin de equivalencia. Definicin: 2.3.2 particin de un conjunto. Una particin de un conjunto A es una coleccin de subconjuntos de A, los cuales son no vacos y disyuntos entre s cuya unin es A. Formalmente, una particin de un conjunto A es una familia siguientes propiedades: de subconjuntos no vacos de A, con las
Cada conjunto Ejemplo:
se llama celda o bloque de la particin.
Sea particiones de A.
. Cada una de las siguientes colecciones son
Ejemplo: Cada una de los siguientes conjuntos son particiones de .
= el conjunto de nmeros pares, impares.
= el conjunto de nmeros
La siguiente definicin de clase de equivalencia, nos servir para mostrar como las relaciones de equivalencia y las particiones son descripciones del mismo concepto. definicin: 2.3.3 Clase de equivalencia. Sean A un conjunto y R una relacin de equivalencia en A. Para cada con respecto a R es el conjunto , la clase de equivalencia de x
definido como sigue:
En otras palabras, es el conjunto de todos los elementos de A que estn relacionados con x. Cuando solamente una relacin de equivalencia R se est considerando, escribiremos Ejemplo: en vez de .
Sea
y consideremos la siguiente relacin de equivalencia en A:
Entonces
Ejemplo: Consideremos las siguientes relaciones de equivalencia en . .
Dado , tenemos que:
. Ejemplo: Consideremos la relacin de equivalencia congruencia mdulo 5.
Dado
, tenemos que:
Es decir, la clase de equivalencia del entero a es el conjunto de nmeros y para los cuales la diferencia es un mltiplo de 5. As, por ejemplo,
Como se observa en este ejemplo, conjunto de nmeros con residuo 0 cuando se dividen por 5. conjunto de nmeros con residuo 1cuando se dividen por 5. conjunto de nmeros con residuo 2 cuando se dividen por 5. conjunto de nmeros con residuo 3 cuando se dividen por 5. conjunto de nmeros con residuo 4 cuando se dividen por 5. Adems, se tiene que .
En general para todo para algn . Es decir cada entero pertenece a exactamente uno de estos cinco conjuntos. De manera ms en general para la relacin de equivalencia congruencia mdulo
n: contiene a
, denotamos la clase de equivalencia que como . Esto es,
Generalizando el caso n = 5 podemos concluir que dado un entero positivo n,
=conjunto de nmeros con residuo r cuando se dividen por n. Adems s tiene que: para todo .
Es decir cada entero pertenece a exactamente uno de estos n conjuntos. Por lo tanto la coleccin de las clases de equivalencia de la relacin congruencia mdulo n es una particin de con n elementos.
El resultado anterior se cumple en general para cualquier relacin de equivalencia: la coleccin de las clases de equivalencia de una relacin de equivalencia en un conjunto A forman una particin de A. Para demostrar este resultado utilizaremos el siguiente teorema.
Teorema 2.3.1 Supongamos que R una relacin de equivalencia en un conjunto . Entonces
Demostracin: Como es reflexiva entonces . . Luego por definicin
de clase de equivalencia,
Hay que demostrar las dos implicaciones:
( i ) Supongamos que que:
. Hay que probar
. ( ii )supongamos que .
por la parte
. Por lo tanto
. Entonces
Demostraremos que:
De esta forma concluimos que La parte (c) del teorema anterior afirma que las clases de equivalencias solo se pueden relacionar de dos maneras: son idnticas o disyuntas. Mostraremos en el siguiente teorema como una relacin de equivalencia particiona un conjunto.
