0
$\begingroup$

I was asked on a test to find the number of relations on a set with 10 elements which is both symmetric and asymmetric.

Now since any element of the type

$$ (a,b) \quad where \quad b \neq a $$ cannot exist in such a relation (I think).

This problem essentially reduces to the statement whether a relation which only has elements of the type $ (a,a)$ (elements found on the main diagonal of the matrix form of R) is a relation which is both symmetric and asymmetric?

$\endgroup$
1
  • 2
    $\begingroup$ You seem to be confusing antisymmetric and asymmetric. What you have is true if the question had asked about relations that are both antisymmetric and symmetric. As you've stated the question (being about asymmetric relations), there is only one possible relation. (the empty relation) $\endgroup$ Commented Feb 7, 2017 at 14:47

1 Answer 1

4
$\begingroup$

No, for any such $R$, you can't have any $(a,a) \in R$ since that would go against asymmetry (If $(a,a) \in R$, then by asymmetry, $(a,a) \not \in R$ ... so we can't have $(a,a)$!)

The only relation that works is the empty relation, i.e. $R=\{ \}$, since if any $(a,b) \in R$, we must have (by symmetry) $(b,a) \in R$, but we also must have (by asymmetry) $(b,a) \in R$. Since we can't have both, we can't have any $(a,b) \in R$.

$\endgroup$
5
  • $\begingroup$ Antisymmetry means that $(a.b) \in R \land (b,a) \in R \Rightarrow b = a$. If antisymmetry was against reflexiveness then we couldn't have order relations. $\endgroup$
    – chelivery
    Commented Feb 7, 2017 at 14:48
  • 2
    $\begingroup$ @chelivery Correct ... but the OP asked about asymmetry, not anti-symmetry. $\endgroup$
    – Bram28
    Commented Feb 7, 2017 at 14:49
  • 1
    $\begingroup$ @chelivery The problem asked about asymmetry, not about antisymmetry. These are two different terms $\endgroup$ Commented Feb 7, 2017 at 14:49
  • $\begingroup$ Oh, damn: my bad. Of course. $\endgroup$
    – chelivery
    Commented Feb 7, 2017 at 14:51
  • $\begingroup$ No problem: easily confused! :) $\endgroup$
    – Bram28
    Commented Feb 7, 2017 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .