$R$ is transitive if and only if $ R \circ R \subseteq R$

Question

Question: Let $R$ be a relation on a set $S$. Prove the following.

$R$ is transitive if and only if $ R \circ R \subseteq R$.

---

Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a set $S$. The composition of $R_2$ with $R_1$ is the relation $R_2 \circ R_1 =[(x,y) \in S \times S :(\exists v \in S)((x,v) \in R_1 \land (v,y) \in R_2$.

Definition 6.2.9 states that we let $R$ be an equivalence relation on a set $S$. For each element $x \in S $ the set $[x]=[y \in S: (x,y) \in R$ is the equivalence class with respect to $R$.

Definition 6.2.3 states that $R$ is transitive if $( \forall x, y,z \in S)((x,y) \in R \land (y,z) \in R) \rightarrow (x,z) \in R)$

Definition 3.1.2 states that we let $A$ and $B$ be sets. Then A is the subset of B, written $ A \subseteq B$ when the statement $(\forall x)[x \in A \rightarrow x \in B]$

---

My attempt:

We have a biconditional statement.

1. If $R$ is transitive, then $R \circ R \subseteq R$.

By definition 6.2.3 $R$ is transitive if $( \forall x, y,z \in S)((x,y) \in R \land (y,z) \in R) \rightarrow (x,z) \in R)$

The final result of the proof has to be $(x,z)$ but I don't know the steps...then

afterwards by applying definition 6.3.9, we have

$R \circ R =[(x,z) \in S \times S :(\exists v \in S)((x,v) \in R \land (v,z) \in R$.

Next, we apply definition 6.2.9 , so we have, $[x]=[z \in S: (x,z) \in R$

Since $ R \circ R \subseteq R$ from definition 3.1.2, we know that $R \circ R$ is a subset of $R$. They have elements in common as well.

---

1. If $R \circ R \subseteq R$, then $R$ is transitive.

By definition 3.1.2, we have $(\forall x)[x \in R \circ R \rightarrow x \in R]$

By definition 6.3.9, we have $R \circ R =[(x,y) \in S \times S :(\exists v \in S)((x,v) \in R \land (v,y) \in R$.

So, I know that we have $(x,y)$ involved for $R \circ R \subseteq R$, but what I don't understand is how to bring the $z$ into the picture because the transitive definition has $\forall x,y,z $, so there's like three elements while $ R \circ R$ and $R$ has two. I can see that they do belong to each other because both of them have $(x,y)$ in the definitions.

Somehow I need to have the $(x,z)$ as the final result, but the problem is that I don't know how to prove that R is transitive...this was a part of my last homework and I didn't do too well on that part. If only $R$ was reflexive or symmetric then I would know what's going on because there are two elements which are $x$ and $y$.

Answer 1

The main thing to understand here is the logic. If you get that right you should find that everything else is pretty easy. Just a suggestion - others may disagree - but I find that writing these things in symbolic logic makes it harder, not easier. I would put them in words as far as possible.

There are a lot of "if-then" statements to prove here. In fact if you expand the definitions there are if-thens within if-thens. For example $$\hbox{if $R\circ R\subseteq R$ then $R$ is transitive}$$ can be expanded as $$\displaylines{ \hbox{if (if $(x,y)\in R\circ R$ then $(x,y)\in R$)}\cr \hbox{then (if $(x,y)\in R$ and $(y,z)\in R$ then $(x,z)\in R$)}.\cr}$$ I hope this IS confusing because that's kind of my point - you wouldn't want to start off writing things like this, but on the other hand you do need to be aware that there are lots of if-thens around, and when you come to work out a proof you need to know how to deal with them.

So, how do you prove "if $X$ then $Y$"? There are various ways but the most straightforward is:

• Assume that $X$ is true.
• . . . [arguments] . . .
• Therefore $Y$ is true.

Let's apply this to the above statement. At a very basic level, your proof will be as follows.

• Assume that $R\circ R\subseteq R$.
• . . .
• Therefore $R$ is transitive.

How are you going to prove that $R$ is transitive? The same way, because it is also an if-then statement! So you could develop the previous proof a bit further.

• Assume that $R\circ R\subseteq R$.
• Now suppose that $(x,y)\in R$ and $(y,z)\in R$.
• . . .
• Therefore $(x,z)\in R$.
• Hence, $R$ is transitive.

Now you could go back to try and work out how the fact that $R\circ R\subseteq R$ is going to help you fill in the dots. You might start by writing in what it actually means according to the definition, and then expanding that a bit.

• Assume that $R\circ R\subseteq R$.
• That is, if $(a,b)\in R\circ R$, then $(a,b)\in R$.
• In other words, if $(a,c)\in R$ and $(c,b)\in R$ for some $c$, then $(a,b)\in R$.
• Now suppose that $(x,y)\in R$ and $(y,z)\in R$.
• . . .
• Therefore $(x,z)\in R$.
• Hence, $R$ is transitive.

Now if you look at what is given and what you want you should see that they are almost identical. In fact, if we replace $a,b,c$ by $x,z,y$ respectively then they are identical. So let's do that.

• Assume that $R\circ R\subseteq R$.
• That is, if $(x,z)\in R\circ R$, then $(x,z)\in R$.
• In other words, if $(x,y)\in R$ and $(y,z)\in R$ for some $y$, then $(x,z)\in R$.
• Now suppose that $(x,y)\in R$ and $(y,z)\in R$.
• . . .
• Therefore $(x,z)\in R$.
• Hence, $R$ is transitive.

Now the second last line follows immediately from the previous ones. In fact you can see that what we now have is rather a case of overkill as we have stated many things twice. So you could then edit the proof to streamline it as much as possible: you might end up with something like this.

• Assume that $R\circ R\subseteq R$,
• and suppose that $(x,y)\in R$ and $(y,z)\in R$.
• By definition of $R\circ R$, it follows that $(x,z)\in R\circ R$,
• but since $R\circ R\subseteq R$ we have $(x,z)\in R$.
• We have proved that if $(x,y)\in R$ and $(y,z)\in R$ then $(x,z)\in R$: hence, $R$ is transitive.

Notice how much you can do simply by using definitions to replace "high-level" concepts by simpler ones! In this case it gives you pretty much the whole proof, though you can't expect that always to happen - sometimes there is no substitute for having a "bright idea".

As you pointed out, you need to prove the converse too. See if you can get it by using the same approach.

Answer 2

Let $R$ be a relation on $A$, such that $R\circ R\subseteq R$.

Recall: $$ \begin{align} p \rightarrow q &\iff \lnot p \lor q &\text{Material Implication}\\ \lnot(\exists a\in A)p(a) &\iff (\forall a \in A)(\lnot p(a)) &\text{A Quantifier Negation}\\ (\forall a \in A)p(a) \lor q &\iff (\forall a \in A)(p(a) \lor q) &\text{A Quantifier Distribution Law} \end{align} $$ Proof: $$ \begin{align} R\circ R\subseteq R & \iff (\forall x,y \in A)((\exists t \in A)(xRt \land tRy) \rightarrow xRy) \\ & \iff (\forall x,y \in A)(\lnot(\exists t \in A)(xRt \land tRy) \lor xRy) \\ & \iff (\forall x,y \in A)((\forall t \in A)(\lnot(xRt \land tRy)) \lor xRy) \\ & \iff (\forall x,y,t \in A)(\lnot(xRt \land tRy) \lor xRy)) \\ & \iff (\forall x,y,t \in A)(xRt \land tRy \rightarrow xRy) \\ & \iff R \text{ is transitive} \end{align} $$