Set A is given as $A = \{1,2,3,4,5,6,7,8,9,10,11,13,14\} $ And is defined as $R = \{(x,y) : 3x = y\}$

The relation that I'm getting is: $ R = \{(3,3), (6,6), (9,9), (12,12)\} $

Over here, it is clearly visible that it is symmetric but is it transitive also?

However, the main problem is that the 'answer' says that it neither symmetric nor transitive! Can someone please clear the confusion here.

  • 2
    $\begingroup$ Should it be $(1,3),(2,6),(3,9),(4,12)$? $\endgroup$ – Mythomorphic Jul 29 '15 at 7:05
  • $\begingroup$ Well, I'm feeling a bit stupid to make such a silly mistake. So, $ (1,3),(2,6),(3,9),(4,12) $ in this, it is definitely not symmetric, but, how do I check for transitive? Some hint would do :) $\endgroup$ – Anoneemus Jul 29 '15 at 7:11
  • $\begingroup$ there is (1,3) and (3,9) ,is there (1,9 ) ?$$ (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R$$ $\endgroup$ – Khosrotash Jul 29 '15 at 7:20
  • $\begingroup$ oh! So, there needs to be $ (1,3) = (x,y) $ and $ (3,9) = (y,z) $ -- and if this is exists then there needs to be $ (1,9) $ for it to be transitive. And since we don't have $ (1,9) $ therefore this is not transitive (and neither symmetric). Am I right? $\endgroup$ – Anoneemus Jul 29 '15 at 7:26
  • $\begingroup$ for transitive relation must check all of element , but if $\exists (a,b)\in R \wedge (b,c) \in R \Rightarrow $do not exist (a,c) , the relation isn't transitive $\endgroup$ – Khosrotash Jul 29 '15 at 7:44

The relation will be transitive if $xRy$ and $yRz$ imply $xRz$ for all $x,y,z \in A$.

In the language of your relation, the implication you would need to prove is

$y=3x$ and $z=3y \overset{?}{\implies} z=3x$

(If you wanted to prove this, you could try substituting equations.)

Now, to prove that it is not transitive, you just need to find some $x,y,z$ in $A$ such that $y=3x$ and $z=3y$, but $z \neq 3x$.

  • $\begingroup$ That helps! I'd like to ask you one more thing: there is a relation $ R = (1,1), (1,2), (1,3) $ And the book says that this is NOT transitive. Is it because that the first element $ (1,1) $ is not in form of $ (x,y) $ or is there any other reason? $\endgroup$ – Anoneemus Jul 29 '15 at 7:30
  • $\begingroup$ (The first line in my answer applies to any relation; note that $xRy \iff (x,y) \in R$.) Are those all the elements in the relation? If they are, I think it's transitive; you can see this by checking all pairs where the second coordinate of one pair is the same as the first coordinate of another, and then seeing if the ordered pair formed by their other coordinates is in the relation. So, for example, $(1,1),(1,2) \in R \overset{?}{\implies} (1,2)\in R$, and yes it does. Same for $(1,1)$ and $(1,3)$. But if there are no more elements in the relation, transitivity holds vacuously. $\endgroup$ – coldnumber Jul 29 '15 at 7:38
  • $\begingroup$ So that means, if I'm considering the first element of Relation R, i.e. $ (1,1) ~ (x,y) $ then, does the $x$ here needs to make a set, if $y$ is taken from any other element of relation R? Is it so? If yes, then what if I add $ (2,4) $ to the above specified relation, then, there needs to be $(1,4) $ also, in order for this relation to be transitive or else it won't be? Please do clear my doubt on this. Thanks a lot! $\endgroup$ – Anoneemus Jul 29 '15 at 16:43
  • $\begingroup$ The elements of the relation on a set $A$ are ordered pairs $(x,y)$, where both $x$ and $y$ are elements of $A$, so I'm afraid I don't understand your first question. About your example, yes, if you add $(2,4)$, then you have to worry about $(1,2), (2,4) \in R \overset{?}{\implies} (1,4) \in R$. $\endgroup$ – coldnumber Jul 29 '15 at 20:03

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.