search
Log In
1 vote
96 views

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

in Set Theory & Algebra
reshown by
96 views
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.

1 Answer

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 answers
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?
asked Apr 1, 2017 in Set Theory & Algebra Nirmal Gaur 191 views
1 vote
2 answers
2
135 views
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}$
asked Apr 1, 2017 in Set Theory & Algebra Nirmal Gaur 135 views
0 votes
1 answer
3
126 views
Find a recurrence relation for the number of bit strings of length n that contain a pair of consecutive 0s.
asked Jun 29, 2018 in Combinatory Abhisek Das 126 views
1 vote
1 answer
4
...