Take the 2-minute tour ×
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.

While studying relations, I came across a strange question.

Set $A=\{1,2,3,4\}$ on which the relation $R=\{(2,4),(4,3),(2,3),(4,1)\}$ is defined. It is said in the answer that the relation is not transitive. I am not able to find out why is it so.

Let $R=\{(3,4)\}$. This is said to be transitive in the answer.

Can anyone give proper reason for it?

share|improve this question
add comment

4 Answers

up vote 1 down vote accepted

Recall that $R$ is transitive if $(a,b),(b,c)\in R\Rightarrow (a,c)\in R$.

Here, you have that $(2,4),(4,1)\in R$, but $(2,1)\not\in R$, so $R$ is not transitive.

share|improve this answer
    
oh.. My mistake. Thanks for the answer. I understood it. Can you explain me the second one too ? –  ankur.trapasiya Nov 24 '11 at 22:56
2  
Have you thought about it ? Since you have only one element, the relation is trivially transitive: no such couples $(a,b)$ and $(b,c)\in R$ exists, so you have nothing to check. –  Klaus Nov 24 '11 at 22:59
1  
@ankur.trapasiya: The second one is transitive "by vacuity" there are no pairs in $R$ of the form $(a,b)$ and $(b,c)$. Since the premise of the implication is always false, the implication itself is always true. –  Arturo Magidin Nov 24 '11 at 23:00
    
Understood it. Thank you. Then i can also call it antisymmetric right?. –  ankur.trapasiya Nov 24 '11 at 23:03
    
@ankur.trapasiya Right! –  Klaus Nov 24 '11 at 23:03
show 1 more comment

$R$ is a transitive relation if for every $a,b,c\in A$ if $(a,b), (b,c)\in R$ then $(a,c)\in R$.

As others have said, in the first relation $(2,4),(4,1)\in R$ but $(2,1)\notin R$. This proves that $R$ is not transitive.

This is because in order to prove $R$ is not transitive we need to find three elements $(a,b),(b,c)\in R$ such that $(a,c)\notin R$.

However in the case $R=\{(3,4)\}$ there is only one pair of elements. There is no possible counterexample to transitivity, and so it holds vacuously.

share|improve this answer
add comment

$(2,4)$ and $(4, 1)$ are in the relation, but $(2, 1)$ is not, and so the relation cannot be transitive.

share|improve this answer
    
What about R={(3,4)}. Why it is transitive? –  ankur.trapasiya Nov 24 '11 at 23:00
add comment

it is transitive if all possible combination are transitive, if R={(3,4)} ok but (2,1)∉R it still can't be transitive

share|improve this answer
    
but if (4,1) appear, (1,2)didn't, no matter (2,4) appear, it still ok –  jim Apr 17 at 14:32
    
∀x∀y ∀z[(x,y) ∊R ∧ (y,z) ∊ R ⟶ (x,z) ∊ R ] is transitive fomular, so if (x,y) ∊R, but (y,z) ∉ R , first argument is False, no matter the second argument (x,z) ∊ R is true or false, the final result it still true –  jim Apr 17 at 14:33
add comment

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.