Why is one relation transitive but the other is not?


Solution 1

To be transitive, $xRz$ needs to hold whenever you have $x$, $y$, and $z$ such that $xRy$ and $yRz$. You're only testing the case $x=y=1$ and $z=3$, but there might be other cases. For instance, in your first example, you can let $x=1$, $y=3$, and $z=2$, and you find that $1R3$ and $3R2$, but $1R2$ is not true. So the relation is not transitive.

(By the way, you should not call that first relation an "equivalence relation", since an equivalence relation is required to be transitive, in addition to being reflexive and symmetric.)

Solution 2

A relation $R$ of the set $S$ is transitive if: $$\forall a{\in} S~\forall b{\in}S~\forall c{\in}S: \Big(\big((a,b){\in}R\wedge(b,c){\in}R\big)\to (a,c){\in}R\Big)$$

That definition is equivalent to:

$$\neg \exists a{\in}S~\exists b{\in}S~\exists c{\in}S: \Big(\big((a,b){\in}R\wedge(b,c){\in}R\big)\wedge (a,c){\notin}R\Big)$$

Thus what you are looking for are counter examples.   Look for any $(a,b), (b, c)$ in the relation without a matching $(a,c)$ in the relation.   Just one shows the relation is not transitive, but you have to be sure there are none to claim transitivity.

My first example is a "equivalence relation" $S=\{1,2,3\}$ and $R = \{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$ My Book solutions say that this relations is Reflexive and Symmetric

This is not transitive because while $(1,3)$ and $(3,2)$ are in the relation, $(1,2)$ is not.   One counter example is all we need.

PS: Because this is not transitive, it is not an equivalence relation.   Equivalence relations are those which are reflexive, symmetric, and transitive.

My Second example is "partial order" $S=\{1,2,3\}$ and $R =\{(1,1),(2,3),(1,3)\}$ My Book solutions says is Antisymmetric and Transitive

This is transitive because there is only one pair of $(a,b),(b,c)$ elements from which a counter example could be formed, $(\color{red}1,\color{blue}1),(\color{blue}1,\color{red}3)$, but $(\color{red}1,\color{red}3)$ is indeed in the relation; so there is no counter example.

Solution 3

$xRy$ and $yRz$ should imply $xRz$ for all choises of $x,y,z$.

In your case you have just noticed that $1R3$ hold in both examples. This is however not sufficient for transifitivty, you have to check all possible cases of $x,y$ and $z$ in order to show that a relation is transitive.

In the case of $R =\{(1,1),(2,3),(1,3)\}$, the only tuples where both $xRy$ hold and $yRz$ is when $x=1$, $y=1$ and $z=3$ or when $x=1$, $y=1$ and $z=1$. If we choose $x,y$ or $z$ in any other way then either $xRy$ will not hold or $yRz$. Now it is straight forward to check that if $x=1$, $y=1$ and $z=3$ then $xRy,xRz$ and $xRz$ and if $x=1$, $y=1$ and $z=1$ then $xRy,xRz$ and $xRz$.

Now for the other relation $R = \{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\} $, choosing $x=1,y=1,z=3$ does not pose a problem as $1R1,1R3$ and $1R3$ hold. However If we choose $x=2,y=3,z=1$ then we see that $2R3$ and $3R1$ both hold, however $2R1$ does not hold (since $(2,1)\notin R$) which was supposed to hold in order for the relation to be transitive. Thus this gives one example of where the relation "$xRy$ and $yRz$ imply $xRz$" does not hold, and thus the relation is not transitive.


Related videos on Youtube

Author by


Updated on August 01, 2022


  • user3023185
    user3023185 over 1 year

    From what I have read about a transitive relation is that if xRy and yRz are both true then xRz has to be true.

    I'm doing some practice problems and I'm a little confused with identifying a transitive relation.

    My first example is a "equivalence relation" $S=\{1,2,3\}$ and $R = \{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$ My Book solutions say that this relations is Reflexive and Symmetric

    My Second example is "partial order" $S=\{1,2,3\}$ and $R =\{(1,1),(2,3),(1,3)\}$ My Book solutions says is Antisymmetric and Transitive

    I got confused with why is the partial order(second example) Transitive. So what I did is that I applied $1R1$ and $1R3$ so $1R3$($xRy$ and $yRz$ so $xRz$).

    I tried to applied this to my first example (equivalence relation). What I did is $1R1$ and $1R3$ so $1R3$ ($xRy$ and $yRz$ so $xRz$).

    Can someone explain what I'm missing or doing wrong? What can I do to identify a transitive relation? As you can see on both practice examples both have the same set of relations $1R1$ and $1R3$ so $1R3$($xRy$ and $yRz$ so $xRz$) but one is transitive and the other is not.

    • JiK
      JiK over 7 years
      As @EricWofsey points out in his answer, the first relation is not an equivalence relation. Unless the problem calls it that, I'd edit that term out, because at least I had a hard time reading this problem as I assumed that the first relation indeed is an equivalence relation (didn't check it through during the first read) and thought you had confused "first example" and "second example" later.
  • user3023185
    user3023185 over 7 years
    Am I right? So the difference is that my second example (R={(1,1),(2,3),(1,3)}) only has one example to check to be transitive. And my second example (R={(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)}) has more than 1 examples to prove. Which not all relations are proven that xRz.
  • Ove Ahlman
    Ove Ahlman over 7 years
    Well, yes. You need to check all possibilities for $x,y,z$ where you may quickly notice that in the second example there are only 2 choises (remember also to check [trivially] when $x=y=z=1$) for which $xRy$ and $yRz$ hold, while in the first example there are quite many.