0
$\begingroup$

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

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Would this now be equivalence relation? (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)} $\endgroup$ – Rickybobby Jun 24 '16 at 3:13
  • $\begingroup$ @beatles1235 $\checkmark$ Reflexive, $\checkmark$ Symmetric, $\checkmark$ Transitive $\endgroup$ – Graham Kemp Jun 24 '16 at 3:15
  • $\begingroup$ thank you!! you were right, looking for any bridges helped! $\endgroup$ – Rickybobby Jun 24 '16 at 3:16
  • 2
    $\begingroup$ The third relation is NOT transitive because of $(5,1)$ and $(1,3)$. $\endgroup$ – Aravind Jun 24 '16 at 3:20
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ So how can I fix it so it is transitive, and symmetrical? $\endgroup$ – Rickybobby Jun 24 '16 at 3:01
  • $\begingroup$ {(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 resolve my third example? or did I make it worse $\endgroup$ – Rickybobby Jun 24 '16 at 3:11
  • $\begingroup$ You have to add two more pairs for $3,5$ and $4,5$. $\endgroup$ – Aravind Jun 24 '16 at 3:18
  • $\begingroup$ may I ask why?? $\endgroup$ – Rickybobby Jun 24 '16 at 3:20
  • $\begingroup$ Otherwise you have $(5,1)$ and $(1,3)$ but not $(5,3)$. As I said before, the set of all elements that are related must form a single class. We can see that $1,3$ and $1,4$ and $3,4$ and $1,5$ are all in the same class, so all pairs among them must be in the relation. $\endgroup$ – Aravind Jun 24 '16 at 3:22
0
$\begingroup$

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"

Improve this answer
$\endgroup$

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.