# Number of relations that are both symmetric and reflexive

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?

-
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

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.

-

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$.

-

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.

-
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

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.

-

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$.

-
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 '14 at 19:51
@DeVito.I have just edited it. – TCL Apr 21 '14 at 14:54