Transitive Chaining
Theorem
Let $\RR$ be a transitive relation on a set $S$.
Let $n \in \N$ be a natural number.
Let $n \ge 2$.
Let $\sequence {x_k}_{k \mathop \in \set {1, 2, \dots, n} }$ be a sequence of $n$ terms.
For each $k \in \set {1, 2, \dots, n - 1}$, let $x_k \mathrel \RR x_{k + 1}$.
That is, let $x_1 \mathrel \RR x_2$, $x_2 \mathrel \RR x_3, \dotsc, x_n - 1 \mathrel \RR x_n$.
Then:
- $x_1 \mathrel \RR 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 $\map P n$ be the proposition that if both of the following hold:
- $\sequence {x_k}_{k \mathop \in \set {1, 2, \dots, n} }$ is a sequence of $n$ terms
- $\forall k \in \set {1, 2, \dots, n - 1}: x_k \mathrel \RR x_{k + 1}$
then:
- $x_1 \mathrel \RR 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 \RR x_2$, so $\map P 2$ holds.
This is the basis for the induction.
Induction Hypothesis
Fix $n \in \N$ with $n \ge 2$.
Suppose that $\map P n$ holds.
This is our induction hypothesis.
Induction Step
This is our induction step:
Let $\sequence {x_k}_{k \mathop \in \set {1, 2, \dots, n, n + 1} }$ be a sequence of $n + 1$ terms.
For each $k \in \set {1, 2, \dots, n - 1, n}$, let $x_k \mathrel \RR x_{k + 1}$.
In particular:
- $x_n \mathrel \RR x_{n + 1}$
By the induction hypothesis:
- $x_1 \mathrel \RR x_n$.
Thus since $\RR$ is transitive:
- $x_1 \mathrel \RR x_{n + 1}$
We conclude that $\map P {n + 1}$ holds.
The result follows by the Principle of Mathematical Induction.
$\blacksquare$