I'm working on a discrete math problem to solve for reflexive, symmetric and transitive and I'm stuck on the transitive one. How do I solve for the transitive of the following?

A = {(a,a), (c,c), (d,d), (b,a)}

This is what I understand for transitive. A relation is transitive if aRb and bRc there is a aRc So, for every (a, b) and (b, c) there is an (a, c)

Thank you for your help.

  • $\begingroup$ If you are going to work on other similar problems, it might be useful for you to have a look at the past questions which are similar to this. For example, you may go through the post listed among related questions (like this one) or you can try to search for similar questions using some reasonable tags and keywords. $\endgroup$ – Martin Sleziak Oct 6 '15 at 6:57

It might be a bit confusing using the same letters in two different meanings. So I will rephrase the definition of transitive relation (simply by changing the names of the variables):

Relation $A$ on the set $S$ is transitive if for any $x,y,z\in S$ $$(x,y)\in A \land (y,z)\in A \Rightarrow (x,z)\in A.$$

So you have to check whether this is true for elements from the given set, which is - I assume - $S=\{a,b,c,d\}$.

This would mean trying $4^3$ possibilities. Luckily we do not have to try the pairs which are not in $A$. (For example, the implication is clearly true if $x=c$, $y=d$ since $(c,d)\notin A$.) This reduces the number of pairs we have to check.

We can also notice that if $x=y$, then the above implication says $$(x,x)\in A \land (x,z)\in A \Rightarrow (x,z)\in A$$ which is always true. (Basically the same arguments works for the case $y=z$.)

Since in $A$ we have only one pair where both coordinates are not the same and we are now only checking the pairs such that $x\ne y$, we only have to look at $x=b$, $y=a$. But if $y=a$ then the only possibility such that $(y,z)\in A$ is $z=a$. But we have already taken care of the case $y=z$.

In short: Since, for this particular relation $A$, we have either $x=y$ or $y=z$ whenever both $(x,y)\in A$ and $(y,z)\in A$, the relation is transitive.


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.