I am new to relations on sets and am trying to get my head around transitive relations.

I understand the definition of $(x,y) \in R, (y,z) \in R$ and $(x,z) \in R$ However what i am not sure about is if $x$ and $z$ need to be the same number.

For example if I have the following relation: $R = \{(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,1), (4,3)\}$

Answer 1: Can you this be transitive if you say $(2,1)$ is an element of $R$ and $(1,4)$ is an element of $R$ so is $(2,4)$ which makes this transitive.

Answer 2: Or does the definition mean that if $(2,1)$ is there $(1,2)$ is there but $(2,2)$ is not there and it is not transitive.

I am not sure of which one of the answers is correct and why?

  • $\begingroup$ Not sure if this is a misunderstanding, but $z$ does not need to be the same element as $x$, it can be however. Note also that for a relation $R$ to be transitive, you have to look at all triples $x,y,z$ for which $(x,y)$ and $(y,z)$ are in $R$ and check if $(x,z) \in R$. Your example is not transitive for the reason you gave in Answer 2. $\endgroup$ – Matthias Klupsch Apr 8 '15 at 13:46

The relation $R$ is transitive if

For all $x,y,z$, if $(x,y)\in R$ and $(y,z)\in R$, then $(x,z)\in R$.

In order to prove a relation is transitive, you need to prove the previous definition holds for all $x,y,z$ in the set where the relation is defined. However, if you want to prove $R$ is not transitive, it suffices to exhibit some elements $x_0,y_0,z_0$ such that $(x_0,y_0),(y_0,z_0)\in R$ but $(x_0,z_0)\notin R$. In your example (answer two), your taking $x_0=z_0=2$ and $y_0=1$, it proves $R$ is not transitive.

The first answer you gave is wrong since you're proving the definition of transitive only for some $x,y,z$, not for all of them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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