1
$\begingroup$

$$A = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}.$$
and the set notation for the relation is
$$R = \{(a,b),(a,c),(b,c)\}$$ Is there a fast way to show whether or not it's transitive? I thought it isn't transitive but my solution says it is. I know that a set relation $R$ is transitive on a set $A$ if
$$\forall a,b,c \in A, \ \ \text{if} \ \ aRb, bRc \ \ \text{then} \ \ aRc.$$

$\endgroup$
1
$\begingroup$

Note that $(a,b)$ and $(b,c)$ are the only two pairs that have matching middle terms ($b$ in this case). Thus, in order for the relation to be transitive, it must contain $(a,c)$ - which it does. Therefore it is transitive.


EDIT:

In general, to test if a relation is transitive, we need to grab all possible pairs in the relation (meaning pairs of pairs) that have matching middle terms. Then, one by one, look to see if the term required by transitivity is present. If any such terms are not, then the relation is not transitive. For a more complicated example, consider the relation

$$ R = \{(a,a),(a,b),(a,c),(a,e),(b,c),(b,e),(c,d) \}. $$ We find all pairs of elements with matching middle terms. They are: $$ (a,a)\ \text{and}\ (a,b) \\ (a,a)\ \text{and}\ (a,c) \\ (a,a)\ \text{and}\ (a,e) \\ (a,b)\ \text{and}\ (b,c) \\ (a,b)\ \text{and}\ (b,e) \\ (a,c)\ \text{and}\ (c,d) \\ (b,c)\ \text{and}\ (c,d) $$ Now, test them one by one until we either find a failure or terminate the whole list. $$ (a,a)\ \text{and}\ (a,b) \implies \text{need}\ (a,b)\ \checkmark \\ (a,a)\ \text{and}\ (a,c) \implies \text{need}\ (a,c)\ \checkmark \\ (a,a)\ \text{and}\ (a,e) \implies \text{need}\ (a,e)\ \checkmark \\ (a,b)\ \text{and}\ (b,c) \implies \text{need}\ (a,c)\ \checkmark \\ (a,b)\ \text{and}\ (b,e) \implies \text{need}\ (a,e)\ \checkmark \\ (a,c)\ \text{and}\ (c,d) \implies \text{need}\ (a,d)\times \\ $$ Thus we find that $R$ is not transitive and there is no need to check the pair. Note that we also could have made our list shorter by not considering the reflexive term $(a,a)$.

If things get even more complicated and our relation is no longer finite (or small), we have to go about things differently to prove transitivity or find a counter example.

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