Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Combining relations

Since relations from A to B are subsets of , two relations from A to B can be combined in any way two sets can be combined.

Example. Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relations R ₁ = {(1, 1), (2, 2), (3, 3)} and R ₂ = {(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain , , .

There is another way that relations are combined which is analogous to the composition of functions.

Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a, c), where , and for which there exists an element such that and . We denote the composite of R and S by .

Example. What is the composite of the relations R and S where R is the relation from {1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?

Solution: is constructed using all ordered pairs in R and ordered pairs in S, where the second element of the ordered pair in R agrees with the first element of the ordered pair in S. For example, the ordered pair (2, 3) in R and (3, 1) in S produce the ordered pair in S. For example, the ordered pair (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1) in . Computing all the ordered pairs in the composite, we find .

The powers of a relation R can be inductively defined from the definition of a composite of two relations.

Let R be a relation on the set A. The powers Rⁿ, n = 1, 2, 3, … are defined inductively by R ¹ = R and . The definition shows that , , and so on.

Example. Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Find the powers Rⁿ, n = 2, 3, 4, …

Solution: Since , we find that Furthermore, since , Additional computation shows that R ⁴ is the same as R ³, so It is also follows that for n = 5, 6, 7, …

Theorem 1. The relation R on a set A is transitive iff for n = 1, 2, 3, …