# Rosen , Relations

1 vote
96 views

If Relation S is Transitive then what can we say about Transitivity  of Sn

reshown
0

Sn contains all pairs who is n distance apart in form a to b from pair (a,b).

0

That's true, but how does it mean that Sn is Transitive.

0
By Subset it means.

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.

## Related questions

1
191 views
Given the directed graphs representing two relations, how can the directed graph of the union, intersection, symmetric difference, difference, and composition of these relations be found?
1 vote
Let R be a relation on a set A. Explain how to use the directed graph representing R to obtain the directed graph representing the complementary relation $\overline{R}$