I don't understand the following question, please take a look and help if you can:

Let $M$ be the set of relations over $A=\{1,2,3\}$

a) State the number of elements in $M$. Since $|A|=3$, then the number of relations in $M$ is $2^9$?

b) (The main question I don't understand) We define a relation $S$ over $M$ so that for every $R_1,R_2 \in M$: $(R_1,R_2) \in S$ iff $R_1R_2=R_2R_1$. Prove or disprove if $S$ is an equivalence relation over $M$.

(Regarding b and what i tried to do)

Equivalence relation is defined only if the relation holds reflexivity, symmetry, and transitivity properties. And $R_1R_2=R_2R_1$ is the symmetry property, but it doesn't hold here though I don't know how to write it mathematically. I know it's false, but I'm not sure how to disprove it correctly, showing $S$ doesn't hold symmetry properties.

Please help if you can, I don't know how to disprove it.


You are correct that $S$ is not an equivalence relation. However, $S$ is symmetric. Indeed, if $(R_1,R_2)\in S$, then $R_1R_2=R_2R_1$ implies $R_2R_1=R_1R_2$ and hence $(R_2,R_1)\in S$.

The issue is that $S$ is not transitive. If it were, then $R_1R_2=R_2R_1$ and $R_2R_3=R_3R_2$ would imply $R_1R_3=R_3R_1$. Let's find a counterexample to this.

Set $R_1:=\{(1,1)\}$, $R_2:=\{(2,2)\}$, and $R_3:=\{(1,3)\}$. Then $$ R_1R_2=R_2R_1=R_2R_3=R_3R_2=\emptyset $$ so that $(R_1,R_2),(R_2,R_3)\in S$. However $R_1R_3=\{(1,3)\}\ne\emptyset=R_3R_1$. Therefore $(R_1,R_3)\not\in S$.

  • 1
    $\begingroup$ thank you very much, now i understand. i was looking in the wrong direction with the symmetry even though it was right. thank you for also teaching me how to prove such things $\endgroup$ – BeginningMath Aug 20 '17 at 1:19

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.