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$

1 Answer 1

Reset to default
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$ Commented Nov 29, 2020 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$ Commented Nov 29, 2020 at 14:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.