2
$\begingroup$

I am having a hard time identifying transitive relations. I think I understand those that are symmetric, but do correct me if I'm wrong.

For a set $S = \{0,1,2,3,4\}$ and a relation $Z = \{(0,2),(2,2),(2,3),(3,4)\}$ I have found:

I think it is not reflexive because there is no loop including 1.

I am struggling with this one, but I think it is transitive.

I believe this is not symmetric as there is no $(2,0), (3,2)$ or $(4,3)$.

Any help is much appreciated, I don't seem to be able to get my head around what I feel like are likely to be really simple concepts.

$\endgroup$
  • $\begingroup$ None of the above, but in this category (of relations). $\endgroup$ – Marc van Leeuwen Apr 9 '15 at 13:50
3
$\begingroup$

It is not reflexive because $(0,0)\notin Z$; Is is not symmetric because of the reasons you stated. For instance, $(0,2)\in Z$ but $(2,0)\notin Z$. It is not transitive; for example, $(0,2)\in Z$ and $(2,3)\in Z$ but $(0,3)\notin Z$

$\endgroup$
3
$\begingroup$

You are correct about symmetry and reflexivity.

For transitivity, we need that every time there are two pairs of the form $(a,b)$ and $(b,c)$ in the relation, it must also be the case that $(a,c)$ is in the relation. The relation you have given is not transitive, can you find two pairs $(a,b)$ and $(b,c)$ in your relation such that $(a,c)$ is not in the relation?

Since you seem to think of reflexivity in terms of "loops", perhaps the following way of thinking about transitivity will be helpful: If we consider a relation $R$ as a directed graph, where there is an arrow from $a$ to $b$ if $(a,b) \in R$, then

  • reflexivity means that there is a loop on every node,
  • symmetry means that every time there is an arrow from a node to another node, then there is also an arrow going the other way, and
  • transitivity means that every time there is an arrow from $a$ to $b$ and also from $b$ to $c$, then there must also be an arrow going directly from $a$ to $c$.
$\endgroup$
  • $\begingroup$ What about in the case where, say Z = {(1,1),(2,2),(3,3)}? This wouldn't be transitive right? $\endgroup$ – ASm Apr 9 '15 at 8:50
  • 2
    $\begingroup$ @ASm yes it would, since there are no two pairs of the form $(a,b)$ and $(b,c)$. This is called a vacuous truth. Another example of a vacuous truth is that all cows on the moon are green. Since there are no cows on the moon, this is true. $\endgroup$ – mrp Apr 9 '15 at 8:51
  • $\begingroup$ Slightly off track but does this mean the set I mentioned above is symmetric and anti-symmetric at the same time? Is this possible? Because in this case (a,b) ∈ Z and (b,a) ∈ Z making it symmetric...but also a = b making it anti-symmetric? $\endgroup$ – ASm Apr 9 '15 at 9:05
  • $\begingroup$ @ASm yep, that is also correct. $\endgroup$ – mrp Apr 9 '15 at 9:07
  • $\begingroup$ so in the case of just one element with a = b, e.g Z = {(1,3),(2,2)} would this still be anti-symmetric? Because of the (2,2)? $\endgroup$ – ASm Apr 9 '15 at 9:08
2
$\begingroup$

It is not transitive because it has (2,3) and (3,4) but doesn't have (2,4).

Correct, it's not symmetric for the reason you noted.

Also correct, it's not reflexive. To be reflexive all (a,a) must be part of the relation (for any a). That doesn't hold here apparently.

$\endgroup$
2
$\begingroup$

This set is not transitive because $(2,3),(3,4) \in Z $ but $ (2,4)\notin Z$. The reason you provided for not-symmetric is right.

$\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.