Composition of equivalence relations and quotient set

Question

Let $R$ be an equivalence relation on non empty set $X$. Prove that $X/(X/R\circ R \circ \dots R) = R$

Since $R$ is an equivalence relation we have $$R\circ R \circ \dots R = R$$So we should prove that $X/(X/R) = R$ but I don't know the meaning of $X/(X/R)$. According to the definition $$X/R=\{[x]_R:x\in X\}$$ So what's the meaning of $X/(X/R)$?

Edit: I found that this problem belongs to Set Theory With Applications. Here are some definitions which relate to this problem:

Definition $1$: Let $X$ be a nonempty set. By a partition $\mathcal{P}$ of $X$ we mean a set of nonempty subsets of $X$ such that

a) If $A,B \in \mathcal{P}$ and $A\not = B$ then $A \cap B = \emptyset $

b) $\bigcup_{C \in \mathcal{P}}C = X$

Definition $2$: Let $R$ be an equivalence relation on a nonempty set $X$. For each $x \in X$, we define $$x/R = \{ y\in X | yRx \}$$ and $$X/R = \{ x/R | x \in X \}$$

Definition $3$: Let $\mathcal{P}$ be a partition of a nonempty set $X$. We define a relation $X/\mathcal{P}$ on $X$ by $x(X/\mathcal{P})y$ if and only if there exists a set $A \in \mathcal{P}$ such that $x,y \in A$.

Answer 1

(I'll use, in Definition 3 the notation $R_{\mathcal P}$ in place of $X/\mathcal P$, which I find ambiguous because there are two uses of the slash.)

Suppose $x R y$.
Then $x,y \in x/R$.
Since $X/R$ is a partition of $X$, you apply Definition 3 and (with $x/R$ in place of $A$) conclude that $x R_{X/R} y$.

For the converse, if $x R_{X/R} y$, again by Definition 3, there exists $A \in X/R$ such that $x,y \in A$.
Now, if $A \in X/R$ means that $A$ is an equivalence class of $R$; so if $x,y \in A$ then $x R y$.

So you see, it''s only a matter of proving that $X/R$ is a partition of $X$ (which follows almost immediately from the definitions) and that the relation defined in Definition 3 is, indeed, an equivalence relation (which is also easy).

Essentially this result tells you that equivalence relations and partitions over a set are the same, under a different guise, since you can start with an equivalence relation $R$, get the related partition $X/R$ and the equivalence related with that partition $R_{X/R}$ is the same equivalence you started with.
A related result is that if you start with a partition $\mathcal P$, then $\mathcal P = X/R_{\mathcal P}$.

Answer 2

The exercise is part of showing that, given a non-empty set $X$, there is a one-to-one correspondence between

• equivalence relations on $X$, and
• partitions of $X$.

So start with an equivalence relation $R$ on $X$. Show first that $$ X/R = \{ x/R : x \in X \} $$ is a partition of $X$. You are done, because $y, z \in X$ belong to an element $x/R$ of $X/R$ iff by definition of $x/R$ you have $y R x$ and $z R x$ iff $y R z$.

Answer 3

By definition 2, we have $X/R := \{[z]_R: z\in X\}$ where $R$ is a relation over $X$ and $[z]_R=\{y\in X:\langle y,z\rangle\in R\}$

First we note that $X/R$, being a set of $R$-equivalence classes, indeed partitions $X$.

Using the symbol $/\!\!/$ to avoid confusion, by definition 3, we have $X/\!\!/\mathcal P:=\{\langle x,y\rangle\in X^2:\exists A\in\mathcal P~.(x\in A\land y\in A)\}$ where $\mathcal P$ partitions $X$.

So let us inspect $X/\!\!/(X/R)$.

It is a relation over $X$, whose pairs of elements are both in the same part from $(X/R)$. Since these parts are the $R$-equivalence classes, that entails that $X/\!\!/(X/R)$ is exactly the relation $R$.

$$\begin{align}X/\!\!/(X/R)&=\{\langle x,y\rangle\in X^2:\exists A\in (X/R)~.(x\in A\land y\in A)\}\\&= \{\langle x,y\rangle\in X^2:\exists A\in \{[z]_R:z\in X\}~.(x\in A\land y\in A)\}\\&~~\vdots\\&=\{\langle x,y\rangle\in X^2:\langle x,y\rangle\in R\}\\&=R\end{align}$$