$R$ is transitive if and only if $ R \circ R \subseteq R$ 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.


*

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



*

*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$.  
 A: 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.
A: 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}
$$
