Number of relations that are both symmetric and antisymmetric?

Question

Because one relation cannot be symmetric and antisymmetric in relation to another, but is always symmetric and reflexive to itself, there are 2^n relations (relations in the diagonal only). Is that right?

Answer 1

Correct. Consider representing relations $R$ as $n \times n$ matrices (where $R$ is a relation on a set of cardinality $n$; call it $S = \{a_1,\cdots,a_n\}$). Denote the elements $r_{i,j}$ for the $i^{th}$ row and $j^{th}$ column element. Then $r_{i,j} = 1$ if $a_i R a_j$ and $0$ otherwise.

With this in mind, properties arise, such as:

• $R$ is symmetric if $R=R^T$.
• $R$ is antisymmetric if, for non-diagonal entries, one of $r_{i,j}=0$ or $r_{j,i}=0$ for particular but unequal $i,j$. That is, you cannot have $r_{i,j} = r_{j,i} = 1$.

With this, we notice that, in $R^T$, $r_{i,j}$ goes to the position of $r_{j,i}$. If $R=R^T$ as well, then $r_{i,j} = r_{j,i}$. However, antisymmetry requires at least one of these be zero, and thus if $R$ represents a symmetric and antisymmetric relation, $r_{i,j}=0$ for all $i \ne j$.

Then for all $n$ elements $r_{i,i}$ on the diagonal, we have two choices: either it is or is not related to itself (i.e. we can choose any diagonal entry freely to be $0$ or $1$). This gives $2^n$ possibilities.