Extending the transitive property

Question

Suppose we have a transitive relation $R$ on a set $S$. Suppose for some $n\in\mathbb{Z}^+\colon (s_0, s_1),(s_1,s_2),\ldots,(s_{n-1}, s_n)\in R$. Show that: $(s_0, s_n) \in R$

So I am having difficulties with everything past the basis case of showing that when $(s_0, s_1),(s_1, s_2) \in R$ that $(s_0, s_2) \in R$

Where is your problem? I would prove this by induction on $n$. — wece, Apr 20 '15 at 19:06
Definitely induction. Please include your difficulties with this problem in your post. — Mankind, Apr 20 '15 at 19:07

score 0 · Accepted Answer · answered Apr 20 '15 at 19:48

Now you know $(s_0,s_2)\in R$ so reduce your problem to: Suppose for some $n\in Z_+ :(s_0,s_2),(s_2,s_3)\dots,(s_{n−1},s_n)∈R.$ Show that: $(s_0,s_n)∈R$.

Then, as you reasoned that $(s_0,s_2)\in R$, you should see that $(s_0,s_3)\in R$. Again, you have simplified the problem. It is now, supposing for some $n\in Z_+ :(s_0,s_3),(s_3,s_4)\dots,(s_{n−1},s_n)∈R, $ show that $(s_0,s_n)∈R$.

You can repeat this process until, for a fixed $n$, you have $(s_0,s_n)\in R$.

Extending the transitive property

1 Answers1