I've been learning about equivalence relations in my discrete math class. I understand that equivalence relations are relations that are symmetric, reflexive, and transitive.
I also learned about the equivalent class and the quotient set.
However, this example that we did in class was very confusing.
Example: Let A = {a,b,c} and let R be the binary relation on A defined by R = {(a,a),(b,a),(c,c)}.
Find A/R
Answer: A/R = {[a],[b],[c]} = {{a,b},empty set, {c}}
I thought to be able to find the quotient set, you needed to first find the equivalence class. But how do you find an equivalence class if R is not an equivalence relation?
Thanks!
Edit: I asked my prof this question and this is what he said.
Question: If a relation is binary, but, it is NOT an equivalence relation, does it still have a quotient set?
Nice question. You could use the same definition for any binary relation on a set A; however, only if the relation is an equivalence relation we can ensure the following properties:
(a) the set A is the union of the equivalence classes
(b) two different classes are disjoint, i.e., if the classes are different, then they do not share elements.
If we think of the classes as if they were teams, the failure of the conditions above mean that either there are elements in A that do not belong to any team or there are elements that belong to more than one team.
Best Answer
Here is something you can do with a binary relation $B$ that is not an equivalence relation: take the reflexive, transitive, symmetric closure of $B$ - this is the smallest reflexive, transitive, symmetric relation (i.e. an equivalence relation) which contains $B$ - calling the closure of $B$ by $\bar{B}$, this is the simplest equivalence relation we can make where $B(x,y) \Rightarrow \bar{B}(x,y)$. Then you can quotient $A/\bar{B}$.
This isn't exactly what was happening in the confusing example in class - I'm not sure how to rectify that with what I know about quotients by relations. If we take the closure of your example relation we get $\{(a,a), (a,b),(b,a),(b,b),(c,c)\}$, which makes your equivalence classes $\{[a],[b],[c]\} = \{\{a,b\},\{a,b\},\{c\}\}$ (so really there are only two equivalence classes).
The way to think about $\bar{B}$ is that two elements are related by $\bar{B}$ if you can connect them by a string of $B$s - say, $B(x,a)$ and $B(a,b)$ and $B(h,b)$ and $B(y,h)$ are all true. Then $\bar{B}(x,y)$ is true.