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?

Solutions Collecting From Web of "Number of relations that are both symmetric and reflexive"

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.

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

For reflexive and symmetric relations on an n-element set, consider the set to be in the form of an n x n matrix. This matrix consists of a total of n^2 entries.

Now the main diagonal consists of n entries, while the non-diagonal entries consist of ((n^2)-n) entries.

Reflexive relation => (a,a) in R
Symmetric relation => If (a, b) in R, then (b, a) in R, and a can be equal to b

  • Now for reflexive relations, based on the definition, this means that the main diagonal must all be present within our answer, and thus their value is set. If it were just reflexive (and not also symmetric), then we would go on to say that the non-diagonal entries can be either present or not (and the answer would be 2^((n^2)-n) relations because the non-diagonal entries have 2 possible values).
  • However, since it also includes symmetric relations, the last step need not be done yet.
  • Now, for symmetric relations on the set, this means that the non-diagonal entries can be split into two triangles divided by the main diagonal. It is of importance to note that we only need to include non-diagonal entries/2 because the lower-triangular entries are dependent on the upper or vice versa. If an upper-triangular entry is included, then by the definition of symmetric relations, the equivalent lower entry will be included as well. Thus, the lower triangular entries, like the main diagonal entries, are set to a fixed value.
  • Therefore, the only entries to consider are half of the non-diagonal entries, which corresponds to ((n^2)-n)/2 entries with 2 possible values each, and thus has a final value of 2^((n^2)-n)/2 relations