If $R$ is a transitive relation, then $R\circ R\subseteq R$

Question

Here's the question I'm struggling with:

Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R.

I'm kind of lost on how to prove this.

I've started with saying:

"If R is transitive, then R is the subset of A such that (a,b) is in R and (b,c) is in R, and, due to transitivity, (a,c) is in R when (a,b) and (b,c) have the same b for all a, b, c in A."

Now, for R composed with R, I understand that there is an (a,b) in R and an (b,c) in R, and R composed with R is the set of all (a,c) in A such that (a,b) and (b,c) have the same b.

So to continue from here, this is what I've written, continuing from the previous quotation:

"The composition of R and R on the set A is the subset of all (a,c) in A such that (a,b) in R and (b,c) in R have the same b."

And now I'm lost - I'm not sure how to show that R composed with R is a subset of R from here.

I was going to write out my attempt but I realized I was simply repeating myself and didn't make much sense, so I'd like to ask for some direction before I try again.

Thanks for any help!

Answer 1

You are very close. For brevity, denote $R$ composed with $R$ by $R\circ R$.

By the definition of composition, the pair $(a,c)$ is in $R\circ R$ if and only if there exists a $b$ such that $(a,b)$ and $(b,c)$ are both in $R$.

But if there is such a $b$, then by transitivity $(a,c)$ is in $R$. Thus if $(a,c)$ is in $R\circ R$, then $(a,c)$ is in $R$. It follows that $R\circ R\subset R$.

Answer 2

The first thing you need to do is to get the definitions absolutely clear.

A (binary) relation $R$ on a set $A$ is not a subset of $A$, it is a subset of $A\times A$. In other words, $R$ does not consist of elements of $A$, it consists of pairs of elements of $A$.

A relation $R$ on a set $A$ is transitive means: for all $a,b,c\in A$, if $(a,b)\in R$ and $(b,c)\in R$ then $(a,c)\in R$.

The composition of $R$ with $R$ is the relation (which I will write as $R^2$, don't know if your instructor uses this notation) defined as follows: for all $a,b\in A$ we have $(a,b)\in R^2$ if and only if there exists $c\in A$ such that $(a,c)\in R$ and $(c,b)\in R$.

Please learn these thoroughly: having a rough idea of what they mean is just not good enough.

So to the problem: if $R$ is transitive then $R^2\subseteq R$. We will prove this in the same way we would prove any subset statement: show that any element of the LHS is also an element of the RHS.

Assume that $R$ is transitive, and let $(a,b)\in R^2$. By definition, there exists $c\in A$ such that $(a,c)\in R$ and $(c,b)\in R$. Since $R$ is transitive, $(a,b)\in R$. We have proved that if $(a,b)\in R^2$, then $(a,b)\in R$. That is, $R^2\subseteq R$.