Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
8  
Funny -- "show work" also appears in this answer, but there the request goes in the other direction... – joriki Jan 10 '12 at 7:46
Added homework tag. @Q123: you're likely to get more helpful answers if you share what you've done so far (or at least what your thoughts are about how you might do the problem). – Clive Newstead Jan 10 '12 at 8:09
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. – André Nicolas Jan 10 '12 at 8:14
It is the number which are reflexive plus the number which are symmetric minus the number which are both (to avoid double counting) – Henry Jan 10 '12 at 8:15

marked as duplicate by Andres 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.

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
You are saying symmetric when you mean reflexive. – Stefan Geschke Jan 10 '12 at 8:47
Oh, yeah, you are completely correct. How dumb of me. Fixed in most recent edit. – Keith Irwin Jan 10 '12 at 21:40

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