§13. Виды отношений

Отношение эквивалентности и его связь с разбиением множества на классы.

Определение 1. Бинарное отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример. Пусть Х — множество людей. На этом множестве зададим бинарное отношение R с помощью закона: аRb, если а и b родились в один и тот же год.

Легко убедиться в том, что отношение R обладает свойствами рефлексивности, симметричности и транзитивности. Говорят, что отношение R —отношение эквивалентности.

Вместе с каждым человеком а рассмотрим множество людей Ka, которые родились в один год с а. Например, если а родились в 1958 году, то Ka — множество людей, родившихся в 1958 г. Если b родился в 1979 г., то Kb — множество людей родившихся в 1979 г. Причем, если с родился в 1979 г., то Kc = Kb. Итак, ясно, что два множества Ka и Kb либо не имеют общих элементов, либо совпадают полностью.

Совокупность множеств Ka представляет собой разбиение множества всех людей на классы, поскольку из её построения следует, что выполняются два условия: каждый человек входит в какой–нибудь класс и каждый человек входит только в один класс. Заметим, что каждый класс состоит из родившихся в один год людей.

Таким образом, отношение эквивалентности R порождает разбиение множества Х на классы (классы эквивалентности).

Допустим теперь, что множество всех людей разбито на классы следующим образом: в каждый класс входят люди, родившиеся в одном и том же году.

Введём бинарное отношение R: аRb, если а и b родились в одном и том же году. Легко убедиться, что R — отношение эквивалентности.

Следовательно, разбиение множества на классы порождает отношение эквивалентности.

Это неслучайно. Имеет место теорема.

Теорема. Каждому отношению эквивалентности на множестве Х соответствует разбиение множества Х на классы (классы эквивалентности).

Из теоремы следует, что каждый класс разбиения определяется любым (одним) своим представителем, что дает возможность вместо изучения всех элементов данного множества изучать только совокупность отдельных представителей каждого класса.

Отношение толерантности.

Определение 2. Отношение Т, заданное на множестве Х называется отношением толерантности, если оно рефлексивно, симметрично и не транзитивно.

Очевидно, что если потребовать транзитивность всех пар элементов из Х, то получим эквивалентное отношение. Эквивалентность в смысле равенства, толерантность в смысле сходства, похожести. Содержательно толерантность означает следующее. Предполагается, что объект находится в данном отношении сам с собой (рефлексивность), сходство двух объектов не зависит от порядка сравнения (симметричность), но если первый объект сходен со вторым, а второй сходен с третьим, то не обязательно, что первый был сходен с третьим.

Толерантность позволяет формализовать интуитивные представления о сходстве объектов, их похожести в чем–то. Например, отношение Т «быть на расстоянии не более r», заданное на множестве точек на плоскости. Рис. 27 иллюстрирует этот пример. Точка А отстоит от В и С, а точка В от D и С не более чем на r. В то время как точка А находится от D на расстоянии значительно большем r. Другие примеры толерантности: «отличаться не более чем одной буквой» на множестве слов из четырех букв (например: арка, река, рака), «совпадать по количеству цветов» (белый + синий + красный, зеленый + + красный + желтый) на множестве шарфов.

Рис. 27

Отношение порядка

Определение 3. Всякое антисимметричное и транзитивное отношение R на некотором множестве Х называется отношением порядка.

Множество Х, на котором задано отношение порядка, называется упорядоченным.

Отношение порядка как бы наводит порядок в своем множестве.

Определение 4. Отношение порядка R на некотором множестве Х называется отношением линейного порядка, если оно обладает следующим свойством: для любых элементов х и у множества Х либо xRy, либо yRх.

Множество , на котором задано отношение линейного порядка, называется линейно упорядоченным.

Линейно упорядоченные множества обладают рядом свойств.

Пусть а, b, с — элементы множества Х, на котором задано отношение линейного порядка R. Если aRb и bRc, то говорят, что элемент b лежит между элементами а и с.

Линейно упорядоченное множество Х называется дискретным, если между любыми двумя его элементами лежит лишь конечное множество элементов.

Если для любых двух различных элементов линейно упорядоченного множества Х существует элемент множества, лежащий между ними, то множество Х называется плотным.