Quotients of equivalence relations Charles C. Pinter

80 Views Asked by At

Exercise. Let $R,S$ and $T$ be equivalence relations on $A$ and suppose that $R\subset S\subset T$. Prove that $(S/R) \circ (T/R)$ is an equivalence relation on $A/R$. Note that $S/R=\{([x]_R,[y]_R) :(x,y) \in S\}$.

This is my work that I have done.

$$\begin{array}{crl} ([x]_R,[y]_R)\in (S/R)\circ (T/R) &\Rightarrow &\exists_z (x,z)\in(T/R) \wedge(z,y)\in (S/R) \\ &\Rightarrow &\ (x,z) \in T \wedge (z,y) \in S \\ &\Rightarrow&\ (x,y) \in S \circ T\\ &\Rightarrow&\ (x,y) \in A x A\\ &\Rightarrow & ([x]_R,[y]_R) \in A/R. \end{array}$$

I appreciate your contributions with the definitions used.

2

There are 2 best solutions below

3
On

What you did is wrong: you picked a pair of elements in an equivalence relation (in this case, the composition of two equivalence relations) and concluded that that pair belongs to the set where those equivalence relations are defined.
Let me explain that without quotient sets so that you see more easily the source of your confusion.
It's like you have two equivalence relations $T,S$ on the set $A$, and try to prove that the composition of those is still a subset of $A$: it isn't, it's a subset of $A^2$; moreover, it's an equivalence relation on $A$.
And in the end you don't even try to prove the main thing.

So let me try to prove the desired result following that line of though.
Suppose $S$ and $R$ are equivalence relations on $A$ with $R \subseteq S$, and let us prove that $S/R \subseteq (A/R)^2$. $$ ([x]_R, [y]_R) \in S/R \Longrightarrow (x,y) \in S \subseteq A^2 \Longrightarrow ([x]_R,[y]_R) \in (A/R)^2. $$ So $S/R$ is a binary relation on $A/R$.
Now we still have to prove that $S/R$ is a reflexive, symmetric and transitive.

To see that it is reflexive, let $[x]_R \in A/R$; it follows that $x \in A$, and since $S$ is reflexive on $A$, we get $(x,x) \in S$, whence $([x]_R, [x]_R) \in S/R$.

Now, let $([x]_R,[y]_R) \in S/R$. It follows that $(x,y) \in S$ and since $S$ is symmetric, $(y,x) \in S$, whence $([y]_R,[x]_R) \in S/R$. Thus $S/R$ is symmetric.

Can you now prove that $S/R$ is transitive, and therefore an equivalence relation?
(Notice that I used several times the definition of $S/R$ that you provided.)

Now, what happens with $S$, happens just the same with $T$, since $R \subseteq T$ too.
So we have $S/R$ and $T/R$ as two equivalence relations on $A/R$, and since $S \subseteq T$, we have $(S/R) \subseteq (T/R)$, yielding $(S/R) \circ (T/R) = T/R$.
Check this last equality, verifying a double inclusion:
if $([x]_R,[z]_R) \in (S/R) \circ (T/R)$, with $[y]_R \in A/R$ such that $([x]_R, [y]_R) \in S/R$ and $([y]_R, [z]_R) \in T/R$, then from $S/R \subseteq T/R$, we get $$([x]_R, [y]_R),\; ([y]_R, [z]_R) \in T/R,$$ whence $([x]_R,[z]_R) \in T/R$, by transitivity.
Conversely, given $([x]_R,[y]_R) \in T/R$, since $S/R$ is transitive, $([x]_R, [x]_R) \in S/R$, and so $([x]_R,[y]_R) \in (S/R) \circ (T/R)$.

1
On

Check this process

Reflexivity:

$$\begin{array}{crl} [x]_R\in A/R &\Rightarrow & x\in [x]_R\\ &\Rightarrow & (x,x) \in R \wedge (x,x) \in S \wedge (x,x) \in T \\ &\Rightarrow&\ [x]_R \in (T/R) \wedge [x]_R \in (S/R)\\ &\Rightarrow&\ (x,x) \in (S/R) \circ (T/R)\\ & \end{array}$$

Likewise, can you help me with symmetry and transitivity?