Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
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. – JiK Mar 3 at 11:39

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.)

share|cite|improve this answer

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

share|cite|improve this answer
    
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. – user3023185 Mar 2 at 7:52
    
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. – Ove Ahlman Mar 2 at 8:40

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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