Page 27 - Discrete Structure II

10/2/2020 Lecture Notes

Composition of Relations (Continued)

Definition

n
Let R be a relation on the set A. The powers R , n = 1, 2, 3,…. are defined recursively by
1
n+1
n
R = R and R = R o R

2
R = R o R
3
2
R = R o R
4
3
R = R o R
Example

n
Let R = { (1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers R , n = 2, 3, 4, 5, …..
Solution
2
R = R o R
R = { (1, 1), (2, 1), (3, 2), (4, 3)}.

R = { (1, 1), (2, 1), (3, 2), (4, 3)}.

2
R = R o R = { (1, 1), (2, 1), (3, 1), (4, 2)}

2
3
R = R o R

R = { (1, 1), (2, 1), (3, 2), (4, 3)}.

2
R = { (1, 1), (2, 1), (3, 1), (4, 2)}

3
2
R = R o R ={(1, 1), (2,1), (3, 1), (4,1)}

4
3
R = R o R
R = { (1, 1), (2, 1), (3, 2), (4, 3)}.

3
R = {(1, 1), (2,1), (3, 1), (4,2)}
4
3
R = R o R = {(1,1), (2, 1), (3,1), (4, 1)}