¿Por qué son las particiones y las relaciones de equivalencia la misma cosa?

Question

Mi profesor omitió la prueba en las notas de la clase. Por lo que puedo entender, es porque las clases de equivalencia siempre dividen un conjunto (la clase puede contener solo ese elemento o más y los elementos en esa clase solo pueden estar en esa clase, por lo que actúa como una partición). Sin embargo, esto, en primer lugar, no me dice por qué las relaciones de equivalencia son lo mismo que las particiones y no las clases de equivalencia, y para mí suena como que las particiones no pueden ser arbitrarias. Por lo que entendí, todo lo que tienen que ser son una colección de subconjuntos $A_i$ formando algún conjunto $A$ tal que:

1. $A_i \ne \emptyset$
2. $A_i \ \cap A_j = \emptyset , \ \ \ \text{si $j \ne i$}$
3. $\bigcup _i A_i = A$

No veo que ninguna de estas reglas exija sutilmente que haya una relación de equivalencia, y hacerlo suena como si pusiera restricciones en la creación de una partición que no veo en su definición. ¿Cómo son equivalentes?

Answer 1

Una partición y una relación de equivalencia no son lo mismo; sin embargo, pueden inducirse mutuamente (como se explica al final de esta respuesta). Una relación de equivalencia $R$ en un conjunto $A$ es un subconjunto de $A\times A$ que satisface las siguientes propiedades: $$(a,a)\in R\space\forall a\in A$$ $$(a,b)\in R\implies (b,a)\in R\space\forall a,b\in A$$ $$(a,b)\in R\space\text{y}\space (b,c)\in R\implies (a,c)\in R \space\forall a,b,c\in A$$ Sin embargo, una partición $P$ de $A$ es un subconjunto de $2^A$ que cumple las siguientes dos propiedades: $$p_i\cap p_j=\varnothing\space\forall p_i,p_j\in 2^A\space\text{con}\space p_i\ne p_j$$ $$\bigcup_{i=1}^{|P|}p_i=A$$ Tenemos que $R\subset A\times A$ y $P\subset 2^A$, por lo que ni siquiera son del mismo tipo de objeto. Sin embargo, su profesor probablemente quiso decir que toda relación de equivalencia en un conjunto $A$ induce una partición de $A$, y viceversa.

Más específicamente, si $R$ es una relación de equivalencia en $A$, entonces la partición inducida $P$ es $$P=\{\{b:(a,b)\in R\}:a\in A\}$$ y si $P$ es una partición de $A$, entonces la relación de equivalencia inducida $R$ está definida por $$R=\{(a,b):\exists p_i\in P\space\text{tal que}\space a,b\in p_i\}$$ En palabras sencillas: Si $R$ es una relación de equivalencia dada, entonces la partición inducida $P$ divide $A$ en todos los conjuntos de elementos que son equivalentes entre sí bajo $R$. Si $P$ es una partición dada, entonces la relación de equivalencia inducida $R$ es la relación para la cual $x\sim y$ si y solo si $x,y$ están en el mismo conjunto de la partición P.

Answer 2

Son "la misma cosa" en el sentido de que dada una relación de equivalencia hay una forma natural de construir una partición, y dada una partición hay una forma natural de construir una relación de equivalencia, y estas dos formas naturales se invierten entre sí. Eso es útil porque siempre que te encuentres con uno de estos objetos puedes razonar libremente sobre el otro si eso facilita tu argumento.

Tienes razón cuando dices que son las clases de equivalencia de una relación de equivalencia las que forman una partición (eso es de hecho lo natural de mirar), no la relación de equivalencia en sí misma.

La forma natural de construir una relación de equivalencia a partir de una partición es definir que dos elementos son equivalentes justo cuando están en el mismo bloque de la partición.

Answer 3

Aquí tienes una explicación visual.

Nota que los nodos en los tres primeros paneles también deberían haber tenido aristas hacia sí mismos (por la reflexividad de las relaciones de equivalencia).