Take the 2-minute tour ×
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.

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive?

The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is so. Can anyone explain this?

share|improve this question
4  
this is not (number-theory); just because it numbers does not make it number theory. It's about counting, so it's combinatorics. –  Arturo Magidin Nov 27 '10 at 23:40
add comment

5 Answers 5

up vote 10 down vote accepted

To be reflexive, it must include all pairs $(a,a)$ with $a\in A$. To be symmetric, whenever it includes a pair $(a,b)$, it must include the pair $(b,a)$. So it amounts to choosing which $2$-element subsets from $A$ will correspond to associated pairs. If you pick a subset $\{a,b\}$ with two elements, it corresponds to adding both $(a,b)$ and $(b,a)$ to your relation.

How many $2$-element subsets does $A$ have? Since $A$ has $n$ elements, it has exactly $\binom{n}{2}$ subsets of size $2$.

So now you want to pick a collection of subsets of $2$-elements. There are $\binom{n}{2}$ of them, and you can either pick or not pick each of them. So you have $2^{\binom{n}{2}}$ ways of picking the pairs of distinct elements that will be related.

share|improve this answer
add comment

Being reflexive means that $(x,x)\in R$ for all $x\in A$. Being symmetric means that $(x,y)\in R$ implies that $(y,x)\in R$ as well.

Begin by listing $A$ as $A=\{a_1,\dots,a_n\}$. Then let $B$ be the set $$\{(a_i,a_j)\mid 1\le i<j\le n\}.$$ Note that if $x\ne y$ are elements of $A$, then either $(x,y)\in B$ or $(y,x)\in B$ but not both.

Let $S$ be any subset of $B$. Let $$R_S=S\cup\{(y,x)\mid (x,y)\in S\}\cup\{(x,x)\mid x\in A\}.$$ Then $R_S$ is a symmetric and reflexive relation on $A$.

Note that there are $2^{|B|}$ subsets of $B$, and that if $S\ne S'$ are subsets of $B$, then $R_S\ne R_{S'}$. Also, note that $|B|=\binom{n}2$. (If the last equality is not clear, note that $$B=\{(a_1,a_j)\mid j>1\}\cup\{(a_2,a_j)\mid j>2\}\cup\dots$$ so $|B|=(n-1)+(n-2)+\dots+1$, and it is well-known that the last sum equals $n(n-1)/2=\binom n2$.

This shows that the number of symmetric, reflexive relations on $A$ is at least $2^p$ with $p=\binom n2$.

To see the equality, it is enough to check that any such relation $R$ is $R_S$ for some $S\subseteq B$. But, given $R$, let $S=\{(a_i,a_j)\in R\mid i<j\}$. This is a subset of $B$, and it is easy to check that $R=R_S$.

share|improve this answer
add comment

Maybe you can see it like this: a relation $R$ on $A$ is a subset of $A\times A$, and it is symmetric if and only if $(x,y)\in R \implies (y,x)\in R$, moreover, if the relation is reflexive, then $(x,x)\in R$ for all $x\in A$. Then you can determine uniquely such a relation by saying which subsets of two distinct elements of $A$ "belong" to $R$, in the sense that $\{x,y\}\in R \iff (x,y),(y,x)\in R$. Now, you know that the number of subsets with two distinct elements of $A$ is $\binom{n}{2}$, and the number of subset of a set with $p$ elements is $2^p$. I'm sorry if i was too obscure.

share|improve this answer
    
I had not seen that Arturo Magidin had already answered, so that i gave almost an equal explanation. Sorry again (for my bad english too!). –  Daniele A Nov 27 '10 at 23:55
add comment

You can also think of it as a matrix of $nxn$, with the elements of the matrix being $(a_i,a_j)$ with $ a_i,a_j \in A$. The elements of the main diagonal have to be included in R because R is reflexive. For the remaining $n^2-n$, picking a pair from the upper triangle say $(a_2,a_1)$ implies that you are also picking $(a_1,a_2)$. So in reality you only have $\frac{n^2-n}{2}$ elements to pick from. This can be done in $2^{\frac{n^2-n}{2}}$ ways.

share|improve this answer
add comment

There is only one way to make the relation reflexive -- all ordered pairs $(x,x), x\in A$ must be in the relation. So the number of reflexive symmetric relations on $A$ is the same as the number of ways of adding symmetric pairs $(a,b),(b,a)$, where $a\neq b$ into the relation.

Let $S$ be a subset of $2^A$ consisting of subsets of 2 elements. Then $S$ gives rise to exactly one reflexive symmetric relation on $A$. For example, if $A=\lbrace 1,2,3,4\rbrace$, then an example of $S$ is $\lbrace \lbrace 1,2\rbrace, \lbrace 1,4\rbrace, \lbrace 3,2\rbrace\rbrace$. The relation induced by $S$ is $$\lbrace (1,2), (2,1), (1,4), (4,1), (2,3), (3,2)\rbrace$$ plus all $(x,x), x\in A$. Conversely, every reflexive symmetric relation on $A$ arises in this way.

Since there are $p={n\choose 2}$ subsets of 2 elements, there are $2^p$ such $S$'s. The answer to your question is therefore $2^p$.

share|improve this answer
    
I think this is not quite right. If the number of reflexive symmetric relations on $A$ were the same as the number of symmetric relations on $A$, then every symmetric relation would have to be reflexive. –  Rahul Nov 28 '10 at 2:00
    
@Rahul. I have edited my post. –  TCL Nov 28 '10 at 3:42
    
I just noticed that I had a $-1$ on my reputation. In checking it out, I found out that apparently I downvoted this two days ago. I don't remember this question/answer at all, and I certainly wouldn't have marked this (correct, well written) answer down intentionally. So, I apologize. If this is important to you, edit the answer (so I can revote), and then ping me. Sorry! –  Jason DeVito Apr 19 at 19:51
    
@DeVito.I have just edited it. –  TCL Apr 21 at 14:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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