3

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.

J. W. Tanner
  • 60,406
Frodo Baggins
  • 89
  • Equivalence classes are only defined for equivalence relations and $R$ is not an equivalence relation. (For instance, it is not reflexive since $(b,b)$ is not in the relation). Quotient sets using relations which are not equivalence relations does not make sense either. The quotient set using an equivalence relation results in effectively the set of equivalence classes. – JMoravitz Sep 19 '19 at 17:57
  • I suppose if you insisted, you could define it to be $A/R = {{y~:~(x,y)\in R}:~x\in A}$, which seems to be what the example did, but that seems a bit silly to me and nonstandard. – JMoravitz Sep 19 '19 at 18:00
  • I guess it's nonstandard, but it can definitely be useful. However, you would have a left and right quotient since you can also define $A/R = {{x : (x,y) \in R}: y \in A}. A useful application would be to a partial order. That would give you all increasing or decreasing "branches" of the order. For a function, the second definition gives you the set of all preimages. – Eric Spreen Sep 19 '19 at 21:54

1 Answers1

1

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.

Andrew Tindall
  • 1,165
  • 5
  • 13