reshown by
403 views
1 votes
1 votes

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

reshown by

1 Answer

2 votes
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.

Related questions

0 votes
0 votes
0 answers
1
Nirmal Gaur asked Apr 1, 2017
605 views
Given the directed graphs representing two relations, how can the directed graph of the union, intersection, symmetric difference, difference, and composition of these re...
1 votes
1 votes
2 answers
2
Nirmal Gaur asked Apr 1, 2017
565 views
Let R be a relation on a set A. Explain how to use the directedgraph representing R to obtain the directed graphrepresenting the complementary relation $\overline{R}$
0 votes
0 votes
1 answer
3
Abhisek Das asked Jun 29, 2018
569 views
Find a recurrence relation for the number of bit stringsof length n that contain a pair of consecutive 0s.
2 votes
2 votes
1 answer
4
h4kr asked Dec 27, 2022
337 views
Is the statement true that all reflexive relations are anti-symmetric?