0

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.

  1. 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?

Iyeeke
  • 962
  • You claim it is easy to prove. Doesn't that give you the intuition? – amrsa Aug 18 '20 at 18:29
  • Right... I don't understand the question. What distinction do you expect to see between a "mechanical" understanding and an "intuitive" understanding? If you have a mechanical understanding... that implies you have an understanding. How much do you expect must be changed to turn that into an intuitive understanding instead? This seems quite subjective. – JMoravitz Aug 18 '20 at 18:33
  • 1
    Another though occurred to me. Do you know that a relation $T$ is transitive iff $T \circ T \subseteq T$? If you know this, then just apply the fact that composition of relations is associative. But perhaps you knew that already – amrsa Aug 18 '20 at 18:47
  • @amrsa Thanks for the hint! This coupled with Brian M. Scott's diagram helped a lot. – Iyeeke Aug 19 '20 at 01:15

1 Answers1

2

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

Brian M. Scott
  • 616,228