Probar que la intersección de dos relaciones de equivalencia es una relación de equivalencia.

Question

Estoy leyendo este capítulo del Libro de Pruebas, y estoy atascado en el ejercicio 10 de la sección 11.2. Es como sigue.

Supongamos que $R$ y $S$ son dos relaciones de equivalencia en un conjunto $A$ . Pruebe que $R \cap S$ es también una relación de equivalencia.

¡Gracias por la ayuda!

Answer 1

Prueba. Supongamos que $R$ y $S$ son ambas relaciones de equivalencia sobre un conjunto $A$ . En lo que sigue demostraremos que $R$ y $S$ siendo ambas relaciones de equivalencia en el conjunto $A$ implica que $R\cap S$ es también una relación de equivalencia.

Es evidente que, dado que $R$ y $S$ son relaciones de equivalencia, entonces

$$\begin{align*} x\in A \Rightarrow (xRx)\land(xSx) \Rightarrow (\langle x,x\rangle\in R) \land (\langle x,x\rangle\in S)\Rightarrow\langle x, x\rangle\in R\cap S.\end{align*}$$

Así, $x\in A\Rightarrow x(R\cap S)x$ por lo tanto $R\cap S$ es reflexivo.

Supongamos ahora que $\langle x,y \rangle\in R\cap S$ entonces $(\langle x,y \rangle\in R) \land (\langle x,y \rangle\in S)$ por definición de la intersección de dos conjuntos. Pero ambos $R$ y $S$ son simétricos por lo que debe ser que $(\langle y,x \rangle\in R) \land (\langle y,x \rangle\in S)$ lo que implica $\langle y,x \rangle\in R\cap S$ . Así, hemos demostrado $x(R\cap S)y\Rightarrow y(R\cap S)x$ por lo tanto $R\cap S$ es simétrica.

Por último, considere $(\langle x,y \rangle\in R\cap S)\land(\langle y,z \rangle\in R\cap S)$ . Entonces, como $(\langle x,y \rangle\in R)\land\langle (y,z \rangle\in R)\Rightarrow\langle x,z \rangle\in R$ ya que $R$ es transitiva, y como $(\langle x,y \rangle\in S)\land\langle (y,z \rangle\in S)\Rightarrow\langle x,z \rangle\in S$ ya que $S$ es transitivo, por lo tanto $\langle x,z\rangle\in R$ y $\langle x,z\rangle\in S$ por lo que por definición de la intersección de dos conjuntos $\langle x,z\rangle\in R\cap S$ . Así, hemos demostrado $(\langle x,y \rangle\in R\cap S)\land(\langle y,z \rangle\in R\cap S)\Rightarrow\langle x,z\rangle\in R\cap S$ .

De ello se desprende que $R\cap S$ es una relación de equivalencia ya que es reflexiva, simétrica y transitiva. $\Box$

Answer 2

Sugerencia: Utilice el hecho de que $R$ y $S$ son relaciones de EQUIVALENCIA sobre EL MISMO conjunto, y por lo tanto ambas deben ser reflexivas, simétricas y transitivas sobre ese conjunto.

A continuación, utilice la definición de intersección de conjuntos: $R\cap S$ es el conjunto de todos los pares de elementos del conjunto tales que $(x, y) \in R$ Y $(x, y) \in S$ o, dicho de otro modo, $(x, y) \in R\cap S \iff (x, y)\in R$ y $(x, y) \in S$ .

Intenta averiguar qué elementos deben estar necesariamente en $R\cap S$ y comprueba que entonces deben estar en ambos $R$ y $S$ .

---

Otro enfoque sería utilizar un prueba indirecta con las pistas anteriores:

"Dado $R$ y $S$ son relaciones de equivalencia sobre un conjunto $A$ Supongamos, en aras de la contradicción, que $R\cap S$ NO es una relación de equivalencia...". Si no es una relación de equivalencia, entonces $R\cap S$ no es reflexivo y/o no es simétrico, y/o no es transitivo. Si se puede trabajar hacia una contradicción (que esta suposición debe contradecir el hecho de que ambos $R$ y $S$ son relaciones de equivalencia), entonces has terminado.

Answer 3

Para la solución de este ejercicio, hay que demostrar que $R \cap S$ mantiene las tres propiedades de las relaciones de equivalencia (reflexiva, simétrica y transitiva).

Esto significa que para cada x hay que demostrar que $\langle x,x\rangle \in R \cap S$ y para cada par $\langle x,y\rangle \in R \cap S$ , tienes que demostrar que $\langle y,x\rangle \in R \cap S$ y para cada par $\langle x,y\rangle, \langle y,z\rangle \in R \cap S$ hay que demostrar que $\langle x,z\rangle \in R \cap S$

Answer 4

Pista (lo hice en la escuela):
Tenemos 2 relaciones

$R- antisymmetric$

$S-antisymmetric$

Tenía que demostrar que $R \cap S$ también es antisimétrico.

$P=R \cap S$

$(x,y) \in P$

$\implies (x,y) \in R \cap S $

$\implies (x,y) \in R \wedge (x,y) \in S $

$\implies ((y,x) \notin R \wedge (y,x) \notin S) \Rightarrow(x \ne y) $

$\implies (y,x) \notin R \cap S $

$\implies (y,x) \notin P $