# How to determine whether a given relation on a finite set is transitive?

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)?

### Update:

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

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