1
$\begingroup$

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?

4 Answers 4

1

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.

  • 0
    oh.. My mistake. Thanks for the answer. I understood it. Can you explain me the second one too ?2011-11-24
  • 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.2011-11-24
  • 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.2011-11-24
  • 0
    Understood it. Thank you. Then i can also call it antisymmetric right?.2011-11-24
  • 0
    @ankur.trapasiya Right!2011-11-24
1

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

0

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

  • 0
    What about R={(3,4)}. Why it is transitive?2011-11-24
0

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

  • 0
    but if (4,1) appear, (1,2)didn't, no matter (2,4) appear, it still ok2014-04-17
  • 0
    ∀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 true2014-04-17