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?

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.

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.