This is an exercise from Velleman's "How To Prove It". It has been asked on this site before and is fairly easy to prove mechanically, but I am confused about how to interpret it intuitively.
- Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$, then $R \circ S$ is transitive.
I tried to write down a few examples using a small set $A$, but that did not really clear anything up. What is a good way to interpret this theorem for better understanding?
A diagram might help. (It may also seem merely to be a pictorial restatement of the proof, but it’s worth a try.) It’s to be read from top to bottom: it starts with $a\,(R\circ S)\,c\,(R\circ S)\,e$ and ends with $a\,(R\circ S)\,e$.
$$\begin{array}{ccc} a&\longrightarrow&\overset{R\circ S}\longrightarrow&\longrightarrow&c&\longrightarrow&\overset{R\circ S}\longrightarrow&\longrightarrow&e\\ a&\overset{S}\longrightarrow&b&\overset{R}\longrightarrow&c&\overset{S}\longrightarrow&d&\overset{R}\longrightarrow&e\\ a&\overset{S}\longrightarrow&b&\longrightarrow&\overset{S\circ R}\longrightarrow&\longrightarrow&d&\overset{R}\longrightarrow&e\\ a&\overset{S}\longrightarrow&b&\longrightarrow&\overset{R\circ S}\longrightarrow&\longrightarrow&d&\overset{R}\longrightarrow&e\\ a&\overset{S}\longrightarrow&b&\overset{S}\longrightarrow&f&\overset{R}\longrightarrow&d&\overset{R}\longrightarrow&e\\ a&\longrightarrow&\overset{S\circ S}\longrightarrow&\longrightarrow&f&\longrightarrow&\overset{R\circ R}\longrightarrow&\longrightarrow&d\\ a&\longrightarrow&\overset{S}\longrightarrow&\longrightarrow&f&\longrightarrow&\overset{R}\longrightarrow&\longrightarrow&d\\ a&\longrightarrow&\longrightarrow&\longrightarrow&\overset{R\circ S}\longrightarrow&\longrightarrow&\longrightarrow&\longrightarrow&d \end{array}$$