Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive. I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for.
Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive
I guess I am a bit lost on what $R \circ R$ actually means. I understand with functions but with relations I am iffy.
 A: $R\circ R$ is a relation such that if $R(x,y)$ and $R(y,z)$, then $R\circ R(x,z)$. In general, if $R_1$ and $R_2$ are relations on $A$, and $R_1(x,y)$ and $R_2(y,z)$, then $R_2R_1(x,z)$ (note the order of composition; we apply $R_1$ first, then $R_2$).
So say $R$ is transitive, $R\circ R(x,y)$ and $R\circ R(y,z)$. You want to show that $R\circ R(x,z)$. To start you off, by definition, $R\circ R(x,y)$ basically means that $x$ relates to something that relates to $y$ and $R\circ R(y,z)$ means that $y$ relates to something that relates to $z$. Using transitivity of $R$, can you see how you get what you want?
EDIT: I just noticed the "proof by contradiction" part in the title. The argument should be very similar, except you also assume that for some $x,y,z$, $R\circ R(x,y)$, and $R\circ R(y,z)$, but $\neg R\circ R(x,z)$.
A: Suppose that $R$ is transitive, and suppose that $(x,y),(y,z)\in R^2$. We want to show that $(x,z)\in R^2$.
By definition, if $(x,y)\in R^2$ then there is an element $u$ "connecting $x$ with $y$, that is, such that $xRu$ and $uRy$. Since $R$ is transitive, this implies $xRy$. Using a similar argument we can show that $yRz$.
So, since there is an element $w=y$ "connecting $x$ with $z$, we can conclude that $(x,z)\in R^2$.
If you understand the composition with functions, you might think about the special relation given by $xRy$ iff $f(x)=y$. Then, you will realize that $(x,z)\in R^2$ if and only if there is $y$ such that $xRy$ and $yRz$, that is, $f(x)=y$ and $f(y)=z$. Equivalently, $(x,z)\in R^2$ if and only if $z=(f\circ f)(x)$. 
