Transitive Chaining

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R$ be a transitive relation on a set $S$.

Let $n \in \N$ be a natural number.

Let $n \ge 2$.

Let $\langle x_k \rangle_{k \in \left\{ {1, 2, \dots, n}\right\} }$ be a sequence of $n$ terms.

For each $k \in \left\{ {1, 2, \dots, n-1}\right\}$, let $x_k \mathrel {\mathcal R} x_{k+1}$.

That is, let $x_1 \mathrel {\mathcal R} x_2$, $x_2 \mathrel {\mathcal R} x_3, \dotsc, x_n-1 \mathrel {\mathcal R} x_n$.


Then $x_1 \mathrel {\mathcal R} x_n$


Proof

The proof proceeds by induction on $n$, the number of terms in the sequence.

We first define a propositional function, $P$, as follows:

For each $n \in \N$ such that $n \ge 2$, let $P(n)$ be the proposition that if both of the following hold:

$\langle x_k \rangle_{k \in \left\{ {1, 2, \dots, n}\right\} }$ is a sequence of $n$ terms
$\forall k \in \left\{ {1, 2, \dots, n-1}\right\}: x_k \mathrel {\mathcal R} x_{k+1}$

then $x_1 \mathrel {\mathcal R} x_n$.


Basis for the Induction

The case $n = 2$ is verified as follows:

In this case, the sequence has only two elements, $x_1$ and $x_2$.

Thus by the premise, $x_1 \mathrel {\mathcal R} x_2$, so $P(2)$ holds.

This is the basis for the induction.


Induction Hypothesis

Fix $n \in \N$ with $n \ge 2$.

Suppose that $P(n)$ holds.

This is our induction hypothesis.


Induction Step

This is our induction step:

Let $\langle x_k \rangle_{k \in \left\{ {1, 2, \dots, n, n+1}\right\} }$ be a sequence of $n+1$ terms.

For each $k \in \left\{ {1, 2, \dots, n-1, n}\right\}$, let $x_k \mathrel{\mathcal R} x_{k+1}$.

In particular, $x_n \mathrel{\mathcal R} x_{n+1}$.

By the induction hypothesis:

$x_1 \mathrel{\mathcal R} x_n$.

Thus since $\mathcal R$ is transitive:

$x_1 \mathrel {\mathcal R} x_{n+1}$


We conclude that $P(n+1)$ holds.

The result follows by the Principle of Mathematical Induction.

$\blacksquare$