Possible Duplicate:
Number of relations that are both symmetric and reflexive

Let $X$ be a set with $8$ elements.

How many binary relations on $X$ are either reflexive or symmetric or both?

show work. you need not simplify the answer.


marked as duplicate by Andrés E. Caicedo, Austin Mohr, t.b., Asaf Karagila, Zev Chonoles Jan 10 '12 at 16:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 10
    $\begingroup$ Funny -- "show work" also appears in this answer, but there the request goes in the other direction... $\endgroup$ – joriki Jan 10 '12 at 7:46
  • $\begingroup$ Here is a start. For symmetric, there are $56$ ordered pairs of distinct elements. For any such pair, you can say yes or no. So there are $2^{56}$ symmetric relations. A similar argument (but be careful about equality) will count the symmetric relations. Add. The reflexive and symmetric have been double-counted. $\endgroup$ – André Nicolas Jan 10 '12 at 8:14
  • $\begingroup$ It is the number which are reflexive plus the number which are symmetric minus the number which are both (to avoid double counting) $\endgroup$ – Henry Jan 10 '12 at 8:15

In a set with 8 elements, a binary relation, $R$ can be thought of as a set of pairs of elements of the set for which that relation is true. That is, $(a,b) \in R \leftrightarrow aRb$ is true. As such, if there are 8 elements, then there 64 possible pairs (order matters). If the relation is reflexive, then this implies that $(a,a) \in R$ for all $a$. So we know that 8 of the pairs must be in the relation. This leaves 56 pairs which can either be in or not be in. So there are $2^{56}$ possible reflexive relations.

Similar combinatorics can be applied to find the answer for symmetric and both.

  • $\begingroup$ You are saying symmetric when you mean reflexive. $\endgroup$ – Stefan Geschke Jan 10 '12 at 8:47
  • $\begingroup$ Oh, yeah, you are completely correct. How dumb of me. Fixed in most recent edit. $\endgroup$ – Keith Irwin Jan 10 '12 at 21:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.