Supposing I have a set $A$ and binary relation $R$ such that

$A = \{1,2,3,4,5\}$ $R = \{(1,1), (1,3), (1,4), (2,2), (2,5), (3,1), (3,3), (3,4), (4,1), (4,3), (4,4), (5,2), (5,5)\}$

I want to find the quotient set $A/R$, but I'm not totally sure I understood my professor's explanation of how to do so.

From what I gathered, the quotient set is the set of all equivalence classes of $A$ under the relation $R$. Then if $R$ is an equivalence relation, the equivalence class of some element $a$ belonging to $A$ is the set of all elements related to $a$. In that case, would the quotient set of $A$ and $R$ be

$$A/R = \{\{1,3,4\}, \{2,5\}\}$$

Or would I have to include binary pairs in the quotient set, i.e. $A/R = \{\{(1,1), (1,3) ... \}\}$ since the elements of $R$ are binary pairs?

  • 2
    $\begingroup$ Your first version is correct: $A/R=\big\{\{1,3,4\},\{2,5\}\big\}$. $\endgroup$ – Brian M. Scott Oct 22 '16 at 19:37

This is easiest to digest with a diagram:

enter image description here

Here $x$ points to $y$ iff $(x,y) \in R$. From this diagram you'll also see there are two disjoint such "directed graphs," if you will. Separating them out, we have

enter image description here

What is the significance of these, though? Essentially, all elements that are related to each other form their own equivalence class. In other words, generating graphs in this way will give you a set of (possibly disjoint) graphs, the nodes of which each represent their own equivalence class!

You can see this because an equivalence class will be all of the elements that are related to each other. You can see that you can "walk" from each of $1,3,4$ to any of the other members of that group -- likewise, you can walk from $2$ to $5$ and vice versa. This is because they're all related and thus pointing to each other. However, you can't walk from any of $1,3,4$ to $2,5$, or from the latter set to the former set. That's why they're disjoint.

Remember, a quotient set is essentially a "set of sets:" more precisely, it is the set of these equivalence classes, each of which is their own set. So you would have, for the above relation,

$$A/R = \Big\{ \{1,3,4\} \; , \; \{2,5\} \Big\}$$

Altogether, hopefully this makes it clear what a quotient set actually looks like, and an easy way to visualize them.

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.


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.