Número de clases en que una relación de equivalencia divide un conjunto X

Question

Estoy luchando un poco con respecto a los conjuntos y las relaciones y agradecería cualquier ayuda.

La pregunta es la siguiente:

Consider the relations R and S, defined on the set X = {1, 2, . . . , 99} as follows.

xRy  x + y is a multiple of 11,
xSy  x  y is a multiple of 11.

Determine which of those two is an equivalence relation , and find out into 
how many classes does it partition the set X?

Conozco la definición de relación de equivalencia, pero me parece que ambas relaciones no son reflexivas. Para R puede haber (1,10) y para S puede haber (99,88).

En cuanto a la segunda parte, no tengo ni idea de lo que significan las clases y las particiones, ya que la definición dada es bastante vaga.

Answer 1

PISTA: Es $x+x$ divisible por 11 para los enteros $x$ ? ¿Y qué pasa con $x-x$ ? (La división en tu pregunta es en enteros, no en naturales).

Las clases son $\{1,1+11,1+22,1+33,\ldots,1+88\}$ , $\{2,2+11,2+22,\ldots,2+88\}$ , $\ldots$

¿Puedes terminar esto?

Answer 2

Para la relación de equivalencia, necesitamos comprobar tres criterios: Reflexividad, simetría y transitividad.

En cuanto a la reflexividad, está comprobando que $xRx$ y $xSx$ para todos $x \in X$ . Tal y como sugirió GNU Supporter, $1R1$ fallará porque $1+1=2$ no es un múltiplo de 11. No necesitamos comprobar la simetría o la transitividad para $R$ porque si no es reflexiva, no es una relación de equivalencia.

Para ver que $xSx$ es cierto, $x-x=0=0\cdot 11$ es claramente un múltiplo de 11 para cualquier $x$ .

Para la simetría, se necesita $xSy$ implica $ySx$ . Sugerencia, si $xSy$ entonces existe un número entero $k$ tal que $x-y = 11k$ . Si $k$ es un número entero, entonces $-k$ también lo es. Usa eso para mostrar que $S$ es simétrica.

Por transitividad, supongamos que $xSy$ y $ySz$ para algunos $x,y,z \in X$ . Esto significa que existen enteros $k,m$ tal que $x-y = 11k$ y $y-z = 11m$ . Suma las dos ecuaciones y en el LHS, obtienes $x-z$ . ¿Qué obtienes en el RHS? ¿Puedes demostrar que esto implica transitividad?

Przemyslaw ya explicó qué son las clases de equivalencia. Una partición del conjunto significa que cada elemento pertenecerá a alguna clase de equivalencia, y ningún elemento estará en varias clases. La notación para la clase de equivalencia de un determinado número es añadir paréntesis alrededor de él. Así, $[1]$ es la clase de equivalencia de $1$ . Se puede escribir como $[n] = \{x \in X|nSx\}$ . Dado que la relación de equivalencia divide el conjunto, el hecho de que $1S2$ es falso (ya que $1-2=-1$ no es divisible por 11), entonces $[1] \cap [2] = \emptyset$ . Así es como se puede dividir el conjunto.