0
$\begingroup$

Let there be two sets $A$ and $B$ and let their Cartesian product be $A{\times}B$. Let there be an equivalence relation $R:R\,{\subset}\,A{\times}B$. Let's define an equivalence class now: ${\lbrack}{\lbrack}a{\rbrack}{\rbrack}_R=\{b\,{\in}\,B:(a,b)\,{\in}\,R\}$

Let $[[x]]_R$ and $[[y]]_R$ be two such equivalence classes.

We know that $[[x]]_R=[[y]]_R$. How to use this to prove that $x\,R\,y$?

$\endgroup$
  • $\begingroup$ If $R$ is just a "relation" then we don't know it. But if it is an equivalence relation, then we do. $\endgroup$ – GEdgar Nov 12 '15 at 15:03
  • $\begingroup$ How? Yes, it's supposed to be an equivalence relation. $\endgroup$ – user285146 Nov 12 '15 at 15:04
  • $\begingroup$ Use the definition of $[[a]]_R$ given, and the definition of "equivalence relation". $\endgroup$ – GEdgar Nov 12 '15 at 15:10
1
$\begingroup$
  1. Equivalence relation is a subset of $A\times B$, not an element of it, so $R\notin A\times B$ but $R\subset A\times B$.

  2. Equivalence relations are only defined in case $B = A$. An easy reminder is: any point must be equivalent to itself, so $(a,a)\in R$ for all $a\in A$. Of course that implies $R\subset A\times A$ (or at least $A\subset B$).

  3. Since $(a,a)\in R$ for any $a$, $a \in [a]$. So if $[a] = [b]$ then $b\in [b]$ implies that $b\in [a]$, hence by definition $(a,b)\in R$.

$\endgroup$
  • $\begingroup$ What's your source on the equivalence relations being defined only if $A=B$? The source I'm using says nothing about that, it just says that they must be transitive, reflexive and symmetric. $\endgroup$ – user285146 Nov 12 '15 at 20:29
  • $\begingroup$ Well, they can't be reflexive, aRa, unless a is in both A and B and $R \subset of (A \cap B) x (A \cap B)$. $\endgroup$ – fleablood Nov 12 '15 at 20:44
  • $\begingroup$ What do you mean by $of(A∩B)x(A∩B)$? $\endgroup$ – user285146 Nov 13 '15 at 21:41
  • $\begingroup$ Ilya has a point. If $R \subset of A \times B$ then aRa implies $a \in A$ and $a \in B$ so $a \in A \cap B$ so R is a subset of the cross product of the intersections. $R \subset A \cap B \times A \cap B$. $\endgroup$ – fleablood Nov 13 '15 at 22:18
1
$\begingroup$

Let $b \in [[x]]_R = [[y]]_R$. Then $b R x$ and $b R y$. By symmetry and transitivity $x R y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.