[Math] How many reflexive, symmetric, and antisymmetric relations are there on an n-element set

combinatoricsrelations

I believe the answer is 1, and here is my reasoning.

I worked through the number of relations for each of the three relations separately. But when I found the number of both symmetric and anti-symmetric relations on an n-element set, this was the most useful.

For this relation, I considered the $n$-element set as an $n \times n$ matrix. Therefore, there are $n^2$ entries total, $n$ entries on the main-diagonal, and $(n^2)-n$ non-diagonal entries. To be symmetric is to say that if $(a, b)$ is in $R$, then $(b, a)$ is also in $R$, where $a$ doesn't have to be equal to $b$. To be anti-symmetric is to say that if $(a, b)$ is in $R$ and $(b, a)$ is in $R$, then $a$ is equal to $b$. Now to be both symmetric and anti-symmetric is basically to just be anti-symmetric and say that if $(a, b)$ is in $R$ and $(b, a)$ is in $R$, then $a$ must be equal to $b$.

Based off of these definitions, to be both symmetric and anti-symmetric, I split it into two steps.

(1) The main-diagonal:

Now the main-diagonal consists of the reflexive relations, and these can either be present (1) or empty (0). Therefore, there are 2 possible options for the main diagonal (or $n$ entries), and thus $2^n$ relations.

(2) Non-diagonal entries:

The non-diagonal entries can be thought of as being divided into two groups that are divided by the main-diagonal. I will call them the upper-triangular entries and lower-triangular entries. Now, for both symmetric and antisymmetric entries, the lower-triangular entries are fixed, in the sense that they are dependent on the upper-triangular entries. For example, if symmetric, and $(1, 2)$ is in $R$, then $(2, 1)$ has to also be in $R$. Therefore, we only need to concern ourselves with the upper-triangular entries, which is $((n^2)-n)/2$ entries in total. To fit the definition of being symmetric and anti-symmetric, there is only one possible option of the $3$ I will mention below:

(a) $(a, b)$ is in $R$, but $(b, a)$ is not in $R$ $\Rightarrow$ Doesn't work: contradicts symmetry.

(b) $(a, b)$ is not in $R$, but $(b, a)$ is in $R$ $\Rightarrow$ Doesn't work: same as for (a).

(c) $(a, b)$ is not in $R$, and $(b, a)$ is not in $R$ $\Rightarrow$ This option works.

Therefore, for non-diagonal entries, there is only one possible option for being both symmetric and antisymmetric, and thus the non-diagonal entries have a fixed value of 1.

Thus, we only need to consider the main diagonal entries, which gives us the final value of having $2^n$ relations.


Based off of what I just did above, if you were to add the fact that there are reflexive relations, then this would mean that the main-diagonal entries would all be included, and thus have a fixed-value of 1 as well. Therefore, I believe the final answer is that there is only 1 relation.


Is my answer correct? I think it sounds pretty logical. Please let me know.

And thank you for your time.

Best Answer

Yes, the identity relation, $I_n = \{(a,a) \mid 0 \leq a < n\}$, is the only reflexive, symmetric, and antisymmetric relation on $\{0,\ldots,n-1\}$.

Clearly, any such relation must contain $I_n$; otherwise it's not reflexive. Suppose $R$ is reflexive, symmetric, antisymmetric, and a proper superset of $I_n$. Then there exists $(a,b) \in R$ such that $a \neq b$. By symmetry of $R$, $(b,a) \in R$ too, but then by antisymmetry of $R$, $a = b$ contradicting the assumption that $a \neq b$.

Therefore the $R$ proper superset of $I_n$ we seek does not exist.