Transitive Chaining

From ProofWiki
Jump to navigation Jump to search

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$