[Math] Number of reflexive, symmetric, and anti-symmetric relations on a set with 3 elements

combinatorics

For the set $X=\{1,2,3\}$, I know that

$2^{{n+1}\choose 2}$ is the number of symmetric relations on $X$,

and I also know that $2^{n^2 – n}$ is the number of reflexive relations on $X$.

How can I calculate the number of reflexive, symmetric and anti-symmetric relations on X?

Best Answer

We need to find the number of relations on $X$ that are reflexive, symmetric and anti-symmetric. Since the relation is reflexive, it contains the diagonal elements $\{(x,x): x \in X\}$. Since the relation is symmetric, if it contains an off-diagonal element $(x,y)$, where $x \ne y$, then it must also contain its transpose $(y,x)$. But since the relation is also antisymmetric, if it contains an off-diagonal element $(x,y)$, then it must NOT contain its transpose $(y,x)$. The only way both these conditions can be satisfied is that the relation not contain any off-diagonal elements at all in the first place. Hence the relation is exactly the set of diagonal elements. Thus there is only one relation on $X$ that is reflexive, symmetric and anti-symmetric.