Number of relations on 6 element set which are both symmetric and reflexive but not anti-symmetric.

168 Views Asked by At

I did this by imagining a Venn diagram.

Number of relations which are Reflexive and Symmetric would be given by

$2^{\binom{n}{2}}$ . Now, this also contains some Anti-symmetric relations.

Number of relations which are Reflexive, Symmetric and Anti-symmetric would be $2^n$

And hence final answer must be given by $2^{\binom{n}{2}}-2^n$

Am I correct in my reasoning?

1

There are 1 best solutions below

0
On

No, you are not. You should emphasize on the definition of Reflexive relations. The number of Reflexive, Symmetric, Anti-symmetric relations is only $1$ because we need to have all the diagonal elements of the grid

enter image description here

in our subset relations. $2^n$ $(n=6\ \text{here} )$ means that you are considering selections of the diagonal elements whether to take one or not. The answer should be $2^{15}-1$. (Possible selections of one side of non-diagonal elements with the other side corresponding non-diagonal element and all diagonal ones to be selected automatically "minus" case in which no non-diagonal elements are chosen which makes it Reflexive, Symmetric, Anti-symmetric altogether)