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