Equivalence Relation, transitive relation

Question

Reading about Equivalence Relation, I understand that for a equivalence relation of a set, it must be reflexive, symmetrical, and transitive, but i'm still a little fussy on transitive to be honest!

Would the below set meet the transitive relation requirement?

1. Set A = {1,2,3,4,5}
2. R1 = {(1,1) (2,2) (3,3) (4,4) (5,5)} is Reflexive, Symmetrical, and Transitive.
3. R2 = {(1,1) (2,2) (3,3) (4,4) (5,5) (1,5) (5,1)} is Reflexive, Symmetrical, and Transitive.
4. R3 = (1,1) (2,2) (3,3) (4,4) (5,5) (1,5) (5,1) (1,3)(3,1)(1,4)(4,1) (4,3)(3,4)} Would this be Equivalence relation?

I suppose my confusion with Transitive Relation lies with this definition:

(x, y) ∈ R and (y, z) ∈ R ⇒ (x, z) ∈ R for all x, y, z ∈ A.

Maybe I'm completely wrong with this next statement, but If (a,b) = R and (b,c) = R then (a,c) = R, How do I start going through the set to find which elements are missing??

Answer 1

Sometimes it is easier to try to find counter examples.

A relation is not transitive if $$\exists x{\in} A~\exists y{\in} A~\exists z{\in}A:\big[ (x,y){\in}R~\wedge~(y,z){\in}R~\wedge~(x,z){\notin}R\big]$$

Can you see any bridge (pairs of the form $(\circ, \underline{\cdot), (\cdot}, \bullet)$) where the end pair $(\circ, \bullet)$ is not also in the relation?

If you find any such a counter example, the relation cannot be transitive.   If there are certainly none, then the relation is transitive.

---

$R_1 = \{(1,1), (2,2), (3,3), (4,4), (5,5)\}$ is Reflexive, Symmetrical, and Transitive.

---

$R_2 = \{(1,1), (2,2), (3,3), (4,4), (5,5), (1,5), (5,1)\}$ is Reflexive, Symmetrical, and Transitive.

---

$R_3 = \{(1,1), (2,2), (3,3), (4,4), (5,5), (1,5), (5,1), (1,3), (1,4), (3,4)\} $ is Reflexive, but neither Symmetrical nor Transitive.

Answer 2

Your last example is not transitive, because while 1 and 5 are related and so are 1 and 3, 3 and 5 are not. Your first two examples are equivalence relations. Note that the definition says " IF $x$ and $y$ are related and so are $y$ and $z$, then $x$ and $z$ must be related as well.

In order for transitivity to be violated, you must find $x,y,z$ such that exactly two of the three pairs are related. There are no such triples in the first two examples, so they are both transitive. Similarly the first example is already symmetric, because in order for symmetry to be violated, there must be two elements $a,b$ such that $(a,b)$ is in R, but $(b,a)$ is not.

Your last example is not symmetric as well.

In order to add pairs to make a given relation an equivalence, you can take its closure. Also an equivalence relation divides the set into classes.

In the third example, the elements $\{1,3,4,5\}$ must be in the same class, so all pairs among them must be added; both $(a,b)$ as well as $(b,a)$.

Answer 3

Besides finding counter-examples as @Aravind mentioned, here is another way to check the transitivity in a more intuitive way:

1. Draw the diagram, where nodes represent elements(in your case, $1,2,3,4,5$ in set A), arrows with direction from node A to node B represent $(A,B)\in R$ (no arrows from A to B means $(A,B)\not\in R$).

2. Now you need to check whether your graph/diagram satisfies the condition that from any node, say $X$, if there is a path from $X$ along the arrows (it can be multiple arrows that form the path) to any other node $Y$, there must be a direct arrow from $X$ to $Y$.

If your graph satisfies the condition, you have got a transitive relation; if not, you can still find the transitive closure with the graph quickly, by adding the missing "direct arrows"