On $R = \left \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,5),(5,5) \right \}$

  • Not reflexive because (3,3) and (4,4) are missing?

  • Not symmetric because (2,1) ,(3,2), (4,3), (5,4) are missing?

  • Not transitive because (5,1) is missing??

I believe I need help with transitive relation. I understand that by definition of transitivity If I can get from one point to another in 2 steps, then I can get there in 1 step. But if there was (5,1) it would make it transitive (notice the red dashed line)?

enter image description here


The transitivity relation is also missing: (5,3),(5,2),(5,1),(4,2),(4,1) ?

  • $\begingroup$ Definition of transitivity is that if $x\sim y$ and $y\sim z$ then $x\sim z$. I.e., if $y\in\mathscr{N}(x)\Rightarrow \mathscr{N}(y)\subset \mathscr{N}(x)$ where $\mathscr{N}(\cdot)$ is interpreted as "the neighborhood of $\cdot$". In your picture, you have $1\sim 3$ and $3\sim 4$ however $1\nsim 4$ among many other examples. $\endgroup$
    – JMoravitz
    Dec 14 '14 at 21:11

You can't get from $5$ to $1$ in any number of steps as it is now - adding $(5,1)$ doesn't actually help transitivity. If you wanted transitivity, you'd need $(x,5)$ for all $x$, since everything has a path to $5$, along with $(y,4)$ for $y=1,2,3$, since each of those has a path to $4$, and you'd also need $(2,1)$ and $(3,2)$, since there are paths between those as well. You'd lastly need $(3,3)$, since you can get from $3$ back to $3$.


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.