Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find an example of a set $A$ and a transitive relation $R$ on $A$ such that $R\circ R\neq R$.

$R\circ R$ is the relation such that $(a,c)\in R\circ R$ when $(a,b) \in R$ and $(b,c) \in R$. I know this, but I don't understand how that can not equal $R$.

share|improve this question

5 Answers 5

To solve such questions it helps to construct small examples of transitive relations in the most obvious way. So, let $A=\{1,2,3\}$ and have $R\{(1,2),(2,3),(1,3)\}$. It is constructed by force to be transitive, but computing $R\circ R$ reveals a that $R\circ R\ne R$.

The moral is not so much any of the particularities of this solution, but rather the general strategy: construct small objects and check!

share|improve this answer

Hint:

  • By transitivity you have $R \circ R \subseteq R$, but you do not have $R \subseteq R \circ R$.

  • Your relation cannot be reflexive since it would imply $R \subseteq R \circ R$.

Good luck!

share|improve this answer

$R$ is transitive iff $R \circ R \subseteq R$. But the converse inclusion is not true. For example, take $(\mathbb{N},<)$. Then $1 < 2$, but there is no $n \in \mathbb{N}$ with $1 < n < 2$.

share|improve this answer

Hint: Try making the condition of transitivity degenerate; what if $A$ only had two elements?

share|improve this answer

For a real-world example, suppose $A$ is the set of all humans who have ever lived and that $a\:R\:b$ means "$a$ is an ancestor of $b$." Well, if $S:=R\circ R$, then $a\:S\:b$ means that "$a$ is an ancestor of one of $b$'s parents." In particular, then, if $a$ is a parent of $b$, then $a\:R\:b$, but it is not the case that $a\:S\:b$. It is true that $a\:R\:b$ whenever $a\:S\:b$, of course (by definition, since $R$ is transitive), so $R\circ R=S\subsetneq R.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.