This is one question I have been solving from Velleman's How to prove book:
Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible with S if for all $x,y,x'$ and $y'$ in $A$, if $xSx'$ and $ySy'$ then $xRy$ iff $x'Ry'$.
a). Prove that if $R$ is compatible with $S$, then there is a unique relation $T$ on $A/S$ such that for all $x$ and $y$ in $A$, $[x]_ST[y]_S$ iff $xRy$.
Now, I have been trying to solve this problem but without any success. The book has given an hint of assuming of assuming $T = \{ (X,Y) \in A/S \times A/S \mid \exists x \in X \exists y \in Y (xRy)\}$.
Now with that hint, I'm able to solve this problem. But I want to know how to actually come up with that set $T$. It just seems to me that I cannot pull out the set $T$ out of my mind which the author has easily done. How come he exactly know that in set $T$ it will be $\exists x \in X$ instead of say $\forall x \in X$ ?
You can solve the problem directly without making use of the hint. Just 'define' relation $T$ on $A/S$ by stating: $$[x]T[y]\text{ if and only if }xRy$$ It must be checked now wether this relation is well-defined and at that point the compatibility of $R$ with $S$ comes in. Based on it we find that there is no dependence on the representatives $x$ and $y$, which is exactly what is needed.
Having done so we now try to get a picture of this relation $T$ on $A/S$ and what rolls out is exactly the set that bothers you. We can describe it as: $$\{\langle[x],[y]\rangle\mid [x]T[y]\}$$or: $$\{\langle[x],[y]\rangle\mid xRy\}$$
Choosing for the second, and for $X=[x]$ and $Y=[y]$ we need representatives of $X$ and $Y$ and arrive at: $$\{\langle X,Y\rangle\mid\exists x\in X\exists y\in Y\text{ }xRy\}$$
In this context: $$\exists x\in X\exists y\in Y\text{ }xRy\iff\forall x\in X\forall y\in Y\text{ }xRy$$