Problem: Let $R$ be a relation over $X$, i.e. let $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$. Prove that $R$ is transitive if and only if $R \circ R \subset R$.

Attempt at proof: I proved one direction already. This is what I did: Suppose $R$ is transitive. Let $q \in R \circ R$ be arbitrary. Then $q = (x,y) \in X \times X$. By definition of composition there then exists a $z \in X$ such that $(x,z) \in R$ and $(z,y) \in R$. From transitivity it then follows that $(x,y) \in R$. Since $q$ was arbitrary, this proves that $R \circ R \subset R$.

Now, suppose that $R \circ R \subset R$. Let $(x,y) \in R$. Now, I don't know how to proceed since I don't know how to use my assumption this time. Any help?

  • 1
    $\begingroup$ Note that $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$ means that $R$ is the full relation ($xRy$ holds for all $x,y$ ,or simply $R=X\times X$). I assume you wanted to say $R\subseteq X\times X$ instead. $\endgroup$ – Hagen von Eitzen Aug 6 '15 at 14:53

The second part should rather start "Now, suppose that $R\circ R\subseteq R$. Let $(x,y)\in R$ and $(y,z)\in R$." Then you want to show that $ (x,z)\in R$.

  • $\begingroup$ How do I do that? I don't know how to use $R \circ R \subset R$. $\endgroup$ – Kamil Aug 6 '15 at 15:22

Hagen was right; since the question is really of the form:

$$R\circ R \subset R \to \forall x\forall y\forall z ((x,y)\in R \land (y,z)\in R \to (x,z)\in R) $$

It is legitimate for you to assume $R\circ R \subset R$ and $(x,y)\in R \land (y,z)\in R$ (since you would need to do a universal proof of the RHS of the conditional).

$R\circ R$ really comes down to this, after having done a universal instantiation:

$$(x,z)\in A\times A|\exists y \in A (x,y)\in R \land (y,z)\in R $$

But note that the 'such that' is synonymous to IFF, i.e. if you can satisfy $\exists y \in A (x,y)\in R \land (y,z)\in R$ you get $(x,z)\in R \circ R$.

With $(x,y)\in R \land (y,z)\in R$ you can existential generalise it to $\exists y \in A (x,y)\in R \land (y,z)\in R$, and you should then be able to utilise the 1st assumption.

  • $\begingroup$ This should be the answer. $\endgroup$ – Tsangares Dec 1 '17 at 22:46

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.