No entiendo el problema siguiente:
¿Qué significa exactamente que un número de pares puede "determinar" una relación de equivalencia? Dicen que si tengo el siguiente conjunto: {1, 2, 3}, y una relación R que es cierto para (a, b) si a=b. Entonces los pares {1, 1}, {2, 2}, y {3, 3} "determinar" esta relación? Entonces, ¿cómo hace el autor llega a n/2 para esta solución?
Este problema es a partir de este conjunto de problemas.
El autor parece describir muy cuidadosamente lo que significa para una colección de pares de "determinar" una relación. Comienza con una relación que usted sabe que es una relación de equivalencia, y, a continuación, empezar a tirar las cosas hasta que no se puede tirar más.
Por ejemplo, si usted comienza con la relación $$ R = \{(1,1), (2,2), (3,3), (2,3), (3,2)\} $$ A continuación, puede deshacerse de $(2,2)$ $(2,3)$ y sólo mantener el $(3,2)$ $$ R' = \{(1,1), (3,3), (3,2)\} $$ porque una vez que usted sabe $(3,2) \in R$, usted sabe que $(2,3) \in R$ por la simetría y usted sabe $(2,2) \in R$ por transitividad.
El autor parece llegar a $n/2$ como sigue : necesita cada elemento de a $S = \{1,2,\ldots, n\}$ a estar presente en algunos de los pares. Podemos ordenar los elementos para que $$ R' = \{(1,2), (3,4), \ldots, (n-1,n)\} \text{ (suponga $n$, incluso por ahora)} $$ Ahora, $|R'| = n/2$, y este es el mínimo. Si cualquier elemento aparece en dos pares, a continuación, el elemento que es "expulsado" tendría que aparecer en otro par, aumentando así el número de pares.
Uno tiene que hacer este argumento riguroso, pero que es el quid de la cuestión.
Esto se explica, aunque ligeramente manera indirecta, en el inicio del Problema 4 en el conjunto de problemas.
Reformular la definición, esperemos un poco más claramente: si $R$ es cualquier conjunto de pares, a continuación, la relación de equivalencia se determina que es una relación $E_R$ en el conjunto de $\bigcup R$ (es decir, el conjunto de todos los elementos que aparecen en cualquier pareja en $R$); $E_R$ se define como el menor de equivalencia de la relación en $\bigcup R$ contiene $R$.
Ejercicio: para $(x,y) \in \bigcup R$, usted tiene $(x,y) \in E_R$ si y sólo si hay alguna secuencia $(x_0,x_1,\ldots,x_n)$ tal que $x_0 = x$, $x_n = y$, y para cada una de las $0 \leq i < n$, $(x_i,x_{i+1}) \in R$ o $(x_{i+1},x_i) \in R$.
El ligeramente anormales parte de la definición de tomar el dominio de la relación de equivalencia a ser también determinado por $R$, en lugar de darse por separado. Una más comunes de la versión de la definición es la siguiente: supongamos $X$ es un conjunto, y $R \subseteq X \times X$; a continuación la relación de equivalencia en $X$ generado por $R$ es el más pequeño de equivalencia de la relación en $X$ contiene $R$. (Y de nuevo, uno puede dar una definición explícita de este por las secuencias de elementos que se relacionan en $R$.)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
