Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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|cite|improve this question
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|cite|improve this answer
oh.. My mistake. Thanks for the answer. I understood it. Can you explain me the second one too ? – ankurtr Nov 24 '11 at 22:56
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
@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?. – ankurtr Nov 24 '11 at 23:03
@ankur.trapasiya Right! – Klaus Nov 24 '11 at 23:03

$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|cite|improve this answer

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

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

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|cite|improve this answer
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

Your Answer


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.