S^{n }contains all pairs who is n distance apart in form a to b from pair (a,b).

1 vote

2 votes

It is a theorem:

**Theorem :**The relation R on a set A is transitive if and only if $R^{n}$ ⊆ R for n = 1, 2, 3, . . . .

Proof:

For if part suppose that $R^{n}$ ⊆ R for n = 1,2, 3, . . . .

In particular, $R^{2}$ ⊆ R.

To see that this implies R is transitive, note that if (a, b) ∈ R and (b, c) ∈ R, then by the definition of composition,

(a, c) ∈ $R^{2}$ .

Because $R^{2}$ ⊆ R, this means that (a, c) ∈ R. Hence, R is transitive.

Using mathematical induction to prove the only if part of the theorem.

Trivially true for n = 1.

Assume that $R^{n}$ ⊆ R, where n is a positive integer.

Assume that (a, b) ∈ $R^{n+1}$.

Then, because $R^{n+1}$ = $R^{n}$ ◦ R, there is an element y with y ∈ A such that (a, y) ∈ R and (y, b) ∈ $R^{n}$.

The inductive hypothesis, namely, that $R^{n}$ ⊆ R, implies that (y, b) ∈ R. Furthermore, because R is transitive, and (a, y) ∈ R

and (y, b) ∈ R, it follows that (a, b) ∈ R. This shows that $R^{n+1}$ ⊆ R.

Hence proved.