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?
- Set A = {1,2,3,4,5}
- R1 = {(1,1) (2,2) (3,3) (4,4) (5,5)} is Reflexive, Symmetrical, and Transitive.
- R2 = {(1,1) (2,2) (3,3) (4,4) (5,5) (1,5) (5,1)} is Reflexive, Symmetrical, and Transitive.
- 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??
Best Answer
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.