5
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

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