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 :(
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.