0

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?

Ankur Trapasiya
  • 203

4 Answers4

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.

Klaus
  • 4,105
  • 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
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.

Asaf Karagila
  • 393,674
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

jim
  • 1
  • but if (4,1) appear, (1,2)didn't, no matter (2,4) appear, it still ok – jim Apr 17 '14 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 '14 at 14:33
0

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

jwodder
  • 1,497