La comprensión de la equivalencia de clase, relación de equivalencia, partición de

Question

Estoy teniendo dificultad para agarrar un par de la teoría de conjuntos de conceptos, específicamente los conceptos que trata de las relaciones. Aquí son los que yo estoy teniendo problemas con el y sus definiciones.

1) La colección de clases de equivalencia w.r.t. $R$

Def: Vamos a $R$ ser una relación de equivalencia en un conjunto a $X$. La colección de clases de equivalencia w.r.t. $R$ es el conjunto: $$[X]/R =\{S|(\exists x)(x\in X\land X\in S=[x]/R)\}=\{[x]/R|x\in X\}$$

2) la Partición

Def: Vamos a $X$ ser un conjunto. Una colección de conjuntos de $C$ es una partición de a $X$ si:
(i) $$\bigcup_{S\in\ C} S=X.$$ (ii) $$\forall S \in C, S \neq \varnothing$$ (iii) $$\forall S, S' \in C, S' \neq S \Rightarrow S \cap S' = \varnothing$$

3) la Relación inducida por

Def: Vamos a $C$ ser una partición de $X$. La relación inducida por $C$, que se denota por a $X/C$, es una relación en $X$ tal que $$X/C = \{(x,y) | (\exists S \in C)(x \exists \in S \land y \exists \in S)\}$$

Answer 1

$\newcommand{\ms}{\mathscr}$Las relaciones de equivalencia y particiones están muy íntimamente relacionados; de hecho, es justo decir que son dos maneras diferentes de ver básicamente la misma cosa.

Comience con un conjunto $A$. Una partición de $\ms P$ $A$ es sólo una manera de picar $A$ en pedazos. Más formalmente, es una colección de subconjuntos de a $A$ con un ejemplo muy sencillo de la propiedad: cada elemento de a $A$ pertenece a exactamente uno de los conjuntos en $\ms P$. Esto se expresa a menudo en un poco más de la rotonda de la moda: una colección de $\ms P$ de los no vacía de subconjuntos de a $A$ es una partición de a $A$ si

1. $A=\bigcup_{P\in\ms P}P$, y
2. si $P_1,P_2\in\ms P$$P_1\ne P_2$,$P_1\cap P_2=\varnothing$, es decir, los miembros de $\ms P$ son pares distintos.

La primera de estas condiciones se dice que a cada elemento de a $A$ pertenecen al menos a uno de los miembros de $\ms P$, y el segundo dice que ningún elemento de la $A$ pertenece a más de un miembro de $\ms P$; poner los dos juntos, y usted consigue mi definición original.

Podemos utilizar la partición de $\ms P$ a definir un asociado de la relación $\overset{\ms P}\sim$$A$: para cualquier $x,y\in A$, $x\overset{\ms P}\sim y$ si y sólo si $x$ $y$ están en la misma pieza de la partición $\ms P$. Por ejemplo, si $A$ es un conjunto de personas, podemos dividirlos de acuerdo a sus edades: la $20$-año-olds son de una sola pieza de la partición, el $50$-año-olds son el otro, y así sucesivamente. El asociado relación es, simplemente, tiene la misma edad de: $x\overset{\ms P}\sim y$ si y sólo si $x$ $y$ son de la misma edad. Es fácil ver que en este caso se $\overset{\ms P}\sim$ es una relación de equivalencia $-$ reflexiva, simétrica y transitiva $-$ y no es difícil demostrar que este es siempre el caso: si $\ms P$ es una partición de un conjunto $A$, $\overset{\ms P}\sim$ es una relación de equivalencia en $A$.

Ahora, ¿cuáles son las clases de equivalencia de esta relación,$\overset{\ms P}\sim$? Fix $a\in A$. La clase de equivalencia de a $a$ es, por definición,$\{x\in A:a\overset{\ms P}\sim x\}$. Pero $a\overset{\ms P}\sim x$ sólo significa que $a$ $x$ están en la misma pieza de la partición $\ms P$, lo $x$ es en la clase de equivalencia de a $a$ si y sólo si es en la misma pieza como $a$. En otras palabras, la clase de equivalencia de a $a$ es la pieza de $\ms P$ que contiene $a$. Y esto es cierto para cada $a\in A$, por lo que las clases de equivalencia de la relación $\overset{\ms P}\sim$ son exactamente las piezas de la partición $\ms P$, los bloques en que se divide $A$.

Ahora se establece que a un lado por un momento, y vamos a $R$ ser una relación de equivalencia en $A$. Para cada una de las $a\in A$ establecer $[a]/R=\{x\in A:aRx\}$; esta es la clase de equivalencia de a $a$, el conjunto de cosas a las que $a$ está relacionado con el por $R$. Es un subconjunto de a $A$. Una de las primeras cosas que usted acredite acerca de clases de equivalencia es que para cualquier $a,b\in A$,$aRb$, en cuyo caso $[a]/R=[b]/R$ o $a\not Rb$, en cuyo caso $[a]/R\cap[b]/R=\varnothing$: cualquiera de las dos clases de equivalencia son el mismo conjunto o completamente distintos el uno del otro. En otras palabras, las clases de equivalencia picar $A$ en pares distintos pedazos, y cada elemento $a$ $A$ pertenece a exactamente una de estas piezas, es decir,$[a]/R$.

Pero esto es exactamente lo que significa decir que el $A/R$, la colección de todas estas clases de equivalencia, es una partición de a $A$: cada elemento de a $A$ pertenece a exactamente uno de los conjuntos de la colección de $A/R$. Así como un partición de $\ms P$ $A$ da lugar a un asociado de equivalencia de la relación de $\overset{\ms P}\sim$$A$, una relación de equivalencia $R$ $A$ da lugar a una partición asociada $A/R$$A$. ¿Qué pasa si empezamos con la partición de $A/R$ y la construcción de sus asociados de equivalencia de la relación de $\overset{A/R}\sim$$A$? Para cualquier $x,y\in A$ tenemos, por definición, $x\overset{A/R}\sim y$ si y sólo si $x$ $y$ están en la misma pieza de $A/R$. Pero las piezas de $A/R$ $R$- clases de equivalencia, por lo $x$ $y$ están en la misma pieza de la partición $A/R$ si y sólo si $[x]/R=[y]/R$, es decir, si y sólo si $xRy$. Es decir, $x\overset{A/R}\sim y$ si y sólo si $xRy$, e $\overset{A/R}\sim$ $R$ son exactamente la misma relación en $A$.

Para recapitular:

1. Cada partición $\ms P$ $A$ induce un asociado de equivalencia de la relación de $\overset{\ms P}\sim$$A$, y cada uno de equivalencia de la relación de $R$ $A$ induce una partición asociada $A/R$ $A$ en clases de equivalencias.

2. Estas operaciones de conversión de la partición de equivalencia de la relación y viceversa, son inversos. Si usted comienza con una partición de $\ms P$$A$, la construcción de la relación de equivalencia $\overset{\ms P}\sim$$A$, y luego construir la partición asociada $A/\overset{\ms P}\sim$$A$, estás de vuelta donde había empezado: $A/\overset{\ms P}\sim=\ms P$. Del mismo modo, si usted comienza con una equivalencia de la relación de $R$$A$, la construcción de la partición asociada $A/R$$A$, y luego construir a partir de la partición de sus asociados de equivalencia de la relación de $\overset{A/R}\sim$, se obtiene la relación original $R$: $\overset{A/R}\sim=R$.

Answer 2

Por qué? ¿Cómo podemos saber cómo estas definiciones están relacionadas?

Fijar un conjunto $S$

Considere la posibilidad de una relación de equivalencia $\sim$$S$. Considerar las clases de equivalencia $[a]=\{ x \in S : x \sim a \}$. Por definición, estos son subconjuntos de a $S$. Su unión es $S$ debido a que por la reflexividad $a\in[a]$ por cada $a\in S$. Finalmente, ellos son distintos, porque si $x \in [a]$$x \in [b]$$x \sim a$$a \sim x$, por simetría. Pero, a continuación, $a \sim b$ por transitividad y por lo $a\in [b]$. Cada $y \in [a]$ $[b]$ nuevo por la transitividad. Esto significa que $[a]\subseteq [b]$. Intercambio de $a$$b$, llegamos a la conclusión de $[a]=[b]$. Todo esto significa que las clases de equivalencia forma una partición de $S$.

A la inversa, dada una partición de $S$ en subconjuntos $C_\lambda$, se define una relación de equivalencia en $S$ $a\sim b$ fib hay un $\lambda$ tal que $a$ $b$ están en $C_\lambda$. Puesto que el $C_\lambda$ cubierta $S$ cada $a\in S$ es en uno de esos y lo $\sim$ es reflexiva. Por definición, $\sim$ es simétrica. Puesto que el $C_\lambda$ son distintos, $\sim$ es transitiva.

---

Nota: Cada partición de un conjunto determina una relación de equivalencia en ese conjunto, y para cada relación de equivalencia, las clases de equivalencia correspondiente a la relación que forman una partición del conjunto.

---

Para tratar de poner en palabras la relación entre una partición de un conjunto, y la relación de equivalencia determinada por la partición (o viceversa):

Piense en ejemplos sencillos de una relación de equivalencia en un conjunto X, y sus correspondientes clases de equivalencia (es decir, $\equiv \pmod 2$ en el conjunto de los números enteros). ¿Cuáles son las correspondientes clases de equivalencia? Hay dos: el conjunto de los números enteros y el conjunto de enteros impares.

Iguala: $E = \{x \in \mathbb{Z}\mid x\equiv 0 \pmod{2}\}$, Odds: $O = \{y \in \mathbb{Z} \mid x\equiv 1\pmod{2}\}$

Es la unión de las dos clases de equivalencia, equivalente al conjunto de los números enteros? (sí). Es decir, $E \cup O = \mathbb{Z}$.

Es cualquier entero en más de una de esas clases? (no). Es decir, $E\cap O = \varnothing$.

Así que tenemos dos clases de equivalencia, cuya unión es el conjunto de números enteros, y cuya intersección es vacía. Por lo tanto, tenemos una partición en $\mathbb{Z}$ en dos conjuntos: el conjunto de todos los números enteros y el conjunto de todos los enteros impares.

Por definición de cada elemento en una determinada clase de equivalencia está relacionado con todos los otros elementos en esa clase, y no a cualquier elemento perteneciente a una diferente clase de equivalencia. En el ejemplo que doy más arriba, todos los números pares están relacionados (son incluso decir, $\equiv 0 \pmod{2}$), todos los números impares están relacionados (todos ellos son impares, es decir, $\equiv 1 \pmod{2}$), pero no entero es tanto pares e impares.

---

La colección de todas las clases de equivalencia es una partición de a $X$. Cada $x \in X$ pertenece a una y sólo una clase de equivalencia.

Por ejemplo, la segunda definición se dice que la unión de todas las clases de equivalencia de a $X$ ES $X$ (dicho de otra manera, cada elemento de X está contenida en una clase de equivalencia) y que si cualquiera de las dos clases de equivalencia son no son iguales, entonces son disjuntas: su intersección es el conjunto vacío. Así que cada elemento de a $X$ es en una y sólo una clase de equivalencia.

Answer 3

1) Si $R$ es una relación de equivalencia en $X$, entonces la clase de equivalencia de un elemento a $x\in X$ con respecto al $R$ es el conjunto de todos los elementos de a$X$, que es equivalente a $x$ bajo $R$.

La definición que he escrito para el conjunto de todas las clases de equivalencia se ve muy extraño. Seguramente no debería comenzar con $\exists X$, ya que el $X$ es el conjunto específico que usted desea tomar clases de equivalencia. Acabo de escribir

$$X/R = \{ [x]/R \mid x\in X \},$$ donde $[x]/R$ denota la clase de equivalencia de a $x$ con respecto al $R$.

2) Una partición de un conjunto $X$ es sólo una colección no vacía de subconjuntos de a $X$ cuales son disjuntos a pares (es decir, no de intersección) y cuya unión es el conjunto de los $X$. Por ejemplo, $\{ \{1,3\}, \{2,4\} \}$ es una partición de a $\{1,2,3,4\}$, pero $\{ \{1,2\}, \{2,3,4\} \}$ $\{ \{1,2\}, \{2,3\} \}$ no lo son.

Como se ha mencionado en los comentarios, las colecciones de clases de equivalencia de a $X$ bajo una relación de equivalencia forma una partición de $X$. ¿Por qué?

3) La relación de equivalencia generada por una partición $P$ $X$ es simplemente la relación donde declaramos dos elementos de $X$ estar relacionado con si y sólo si están en el mismo conjunto en $P$. Es fácil comprobar que la definición de una partición garantías de que esto realmente es una relación de equivalencia.

Answer 4

Las definiciones de los conceptos en palabras

1. Las clases de equivalencia de una relación de equivalencia son subconjuntos del conjunto en el que la relación de equivalencia definida, de tal manera que dos elementos están en la misma clase de equivalencia si y sólo si están relacionados por la relación de equivalencia.

2. Una partición de un conjunto es una colección de subconjuntos de un conjunto, cuya unión es el conjunto, y de tal manera que no hay dos subconjuntos comparten elementos en común, y ninguno de los cuales es el conjunto vacío.

3. La relación inducida por una partición es la relación dada por "los dos objetos están relacionados si se encuentran en la misma celda de la partición" (donde una "celda" es uno de los subconjuntos del conjunto de particiones que forman la partición.).