0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $1$ is the correct answer. I don't have the time to read your incredibly long argument. Here is my argument. First, for $a,b\in X$ (the $n$-element set), $a=b\implies aRb$ by reflexivity. Second, if $aRb,$ then $bRa$ by symmetry, and then $a=b$ follows by antisymmetry, so $aRb\implies a=b.$ Thus, $aRb$ holds if and only if $a=b,$ in other words, $R=\{(a,b)\in X\times X: a=b\},$ a unique set. $\endgroup$ – bof Feb 28 '17 at 7:08
  • $\begingroup$ Aside from some trivial mistakes ("thus the non-diagonal entries have a fixed value of 1," where you actually mean 0) your proof is based on the same idea as bof's or mine, just a lot longer. Part of the extra length comes from recalling definitions, but most of it comes from its getting lost in some irrelevant detail. Also note that your cases (a) and (b) are just one case. $\endgroup$ – Fabio Somenzi Feb 28 '17 at 7:36
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.