1
$\begingroup$

I know that equivalence relations must be reflexive, symmetric and transitive. But how do I obtain the sets of equivalence relation from a specific relation?

Below is the question: Let S be {1,2,3}. How many binary relations R on S are there such that (i) R is reflexive? (ii) R is symmetric? (iii) R is an equivalence relation?

Attached is the solution.

For part (i) and (ii), how does the 3^2 -3 come about? I understand the 2 is the number of choices of whether the relation is symmetric or not symmetric.

For part (iii), how does the answer come up with the equivalence relations? I observed that the sets of relations are all possible relations in S = {1,2,3}.

I am really confused by the counting of number of reflexive/symmetric/transitive relations :(

$\endgroup$
0
$\begingroup$

There is a natural correspondence between relations on $n$ objects and $n×n$ binary matrices. A reflexive relation is a matrix with a diagonal of all ones and a symmetric relation is a symmetric matrix.

$3^2-3$ is the number of off-diagonal entries of the matrix for the $3$-element case. If the relation is only constrained to be reflexive, they may be any value whatsoever. If the relation is only constrained to be symmetric, the two halves of off-diagonal entries (split by the diagonal) must be equal – one half may be specified arbitrarily, then the second half is fixed.

Equivalence relations on $n$ elements are counted by the Bell numbers, being equivalent to partitions of the $n$-element set (the smaller sets being equivalence classes). For three elements, the count of five relations is easy to perform manually.

$\endgroup$
2
  • $\begingroup$ Thank you, I understand now that the 9-3 is to count the number of elements that are not diagonal. However, I don't understand (a)(iii) as I thought that equivalence relation is always the mapping of one set onto another set (in this case mapping of R onto S), so shouldn't the format of an equivalence relation be { (1,1), (2,2), (3,3)} and not { {1}, {2}, {3}} as shown in the answer? $\endgroup$ – newtocodingyikes Nov 29 '20 at 14:02
  • $\begingroup$ @newtocodingyikes It is far easier and less mentally taxing to use the set-partitioning approach. An equivalence relation is not mapping $R$ to $S$. $\endgroup$ – Parcly Taxel Nov 29 '20 at 14:33

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.