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

Properties of relations

A relation R on a set A is called reflexive if (a, a) Î R for every element .

Example 1. Consider the following relations on {1, 2, 3, 4}: R₁ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, R₂ = {(1, 1), (1, 2), (2, 1)}, R₃ = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}, R₄ = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R₅ = {(1, 1), (1, 2), 91, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}, R₆ = {(3, 4)}. Which of these relations are reflexive?

Example. Is the “divides” relation on the set of positive integers reflexive?

Solution: Since a | a whenever a is a positive integer, the “divides” relation is reflexive.

A relation R on a set A is called symmetric if whenever , for A relation R on a set A such that and only if a = b, for , is called antisymmetric.

The terms symmetric and antisymmetric are not opposites, since a relation can have both of these properties or may lack both of them. A relation cannot be both symmetric and antisymmetric if it contains some pair of the form (a, b) where a ¹ b.

Example. Which of the relations from Example 1 are symmetric and which are antisymmetric?

Solution: The relations R ₃, R ₄ and R ₆ are symmetric, for if or , then or . R ₄ is symmetric since a = b implies that . R ₆ is symmetric since implies that .

The relations R ₁, R ₂, R ₄ and R ₅ are antisymmetric.

Example. Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?

Solution: This relation is not symmetric since 1 | 2, but . It is antisymmetric, for if a and b are positive integers with a | b and b | a, then a = b.

A relation R on a set A is called transitive if whenever and , then , for .

Example. Which of the relations in Example 1 are transitive?

Solution: R ₄, R ₅ and R ₆ are transitive.

Example. Is the “divides” relation on the set of positive integers transitive?

Solution: Suppose that a divides b and b divides c. Then there are positive integers k and l such that b = ak and c = bl. Hence, c = akl, so that a divides c. It follows that this relation is transitive.